This topic deals with propositional logic,

logical connectives and truth tables and

validity. Predicate logic, universal and
existential quantification are discussed.
1.1 Derive Propositional Logic
1.2 Derive Predicate Logic
1.3 Demonstrate Proofs
➢ A proposition is a declarative sentence (a sentence that declares a fact) that is
either true or false, but not both.

➢ Example 1: All the following declarative sentences are propositions.

(Propositions have truth value.)
▪ Kuala Lumpur is the capital of Malaysia. (True)
▪ Perak is the biggest state in Malaysia. (False)
▪ 1 + 1 = 2 (True)
▪ 2 + 2 = 3 (False)

➢ Example 2: All the following not declarative sentences are not propositions.
(Not propositions do not have truth value.)
▪ What time is it?
▪ Read this carefully.
▪ x+1=2
▪ x+y=z

➢ Letter (p, q, r, s,…) are used to denote the propositional variable.

➢ True propositional – truth value is True and denoted by T.
➢ False propositional – truth value is False and denoted by F.
➢ We use the formulae in proposition logic to form the compound
proposition, which is a combination of one or more propositions.
➢ Compound propositions are formed from existing propositions
using logical operators.
➢ The types of compound propositions:-
▪ Negation
▪ Conjunction
▪ Disjunction – inclusive or
▪ Disjunction – exclusive or
▪ Conditional statements
▪ Biconditional statements
• Let p be a proposition. The negation of p, denoted by ¬ p (also
denoted by ~p), read as not p, is the statement “It is not the
case that p”.
• Example 3:
Proposition (p) Negation of proposition (¬ p)
Today is Friday Today is not Friday
John dislikes reading. John likes reading.
3+5≠7 3+5=7
3≥2 3<2

TABLE 1: The Truth Table for the negation of a proposition:-

p ¬p
T F
F T
• Let p and q be a proposition. The conjunction of p and q, denoted by p ∧ q, is
the proposition “p and q”. The conjunction p ∧ q is true when both p and q are
true and is false otherwise.
• Example 4:
p : It is raining.
q : It is cold.
• The proposition “It is raining and cold.” (p ∧ q) is consider as TRUE when it is
raining (p is True) and it is cold (q is True). Otherwise or other situation is
FALSE.
• In Logic the word “but” sometimes is used instead of “and” in a conjunction. For
example, the statement “The sun is shining, but it is raining.” is another way of
saying “The sun is shining and it is raining.”
TABLE 2: The Truth Table for the conjunction of two propositions:-
p q p∧q
T T T
T F F
F T F
F F F
• Let p and q be a proposition. The disjunction of p and q, denoted by
p ∨ q, is the proposition “p or q”. The disjunction p ∨ q is false when
both p and q are false and is true otherwise.
• Example 5:
p : It is raining.
q : It is cold.
• The proposition “It is raining and cold.” (p ∨ q) is consider as FALSE
when it is not raining (p is False) and it is not cold (q is False).
Otherwise or other situation is TRUE.

TABLE 3: The Truth Table for the disjunction of two propositions:-

p q p∨q
T T T
T F T
F T T
F F F
• Let p and q be a proposition. The exclusive or of p and q,
denoted by p ⨁ q, is the proposition that is true when exactly
one of p and q is true and is false otherwise.

TABLE 4: The Truth Table for the Exclusive Or of two propositions:-

p q p⨁q
T T F
T F T
F T T
F F F
• Let p and q be a proposition. The conditional statement (or implication)
p→q is the proposition “if p, then q”. The conditional statement p → q is
false when p is true and q is false and true otherwise.
• In the conditional statement p → q, p is called the hypothesis (or
antecedent or premise) and q is called the conclusion (or consequence).
• The following common ways to express the conditional statement p → q:
“if p, then q” “p implies q”
“if p, q” “p only if q”
“p is sufficient for q” “a sufficient condition for q is p”
“q if p” “q whenever p”
“q when p” “q is necessary for p”
“q follows from p” “q unless ⌐p”
“a necessary condition for p is q”
• Example 6:
p : Maria learns Discrete Mathematics.
q : Maria will find a good job..
• There are many ways to represent this conditional statement in English:
o “If Maria learns Discrete Mathematics, then she will find a good job.”
o “Maria will find a good job when she learns Discrete Mathematics.”
o “A sufficient condition for Maria to find a good job is learns Discrete Mathematics.”
o “Maria will find a good job unless she does not learn Discrete Mathematics.”
• The conditional statement “If Maria learns Discrete Mathematics, then she will
find a good job.” (p → q) is consider as FALSE when Maria learns Discrete
Mathematics (p is True) but she does not get a good job (q is False). Otherwise
or other situation is TRUE.
TABLE 5: The Truth Table for the conditional statement p → q:
p q p→q
T T T
T F F
F T T
F F T
• Let p and q be propositions. The biconditional statement (or bi-
implications) p↔q is the proposition “p if and only if q”. The
biconditional statement p↔q is true when p and q have the same
truth values, and is false otherwise.
• There are some other common ways to express p ↔ q:
“p is necessary and sufficient for q”
“if p then q, and conversely”
“p iff q”
• p ↔ q has exactly the same truth value as (p → q) ˄ (q → p).
• Example 7:
p : You can take the flight.
q : You buy a ticket.
• The statement “You can take the flight if and only if you buy a ticket” (p ↔ q) is
consider as TRUE if p and q are either both true or both false, that is
✓ If you buy a ticket (q is True) and you can take a flight (p is True).
✓ If you do not buy a ticket (q is False) and you cannot take the flight (p is False).
• The statement “You can take the flight if and only if you buy a ticket” (p ↔ q) is
consider as FALSE if p and q have opposite truth values, that is
✓ When you do not buy a ticket (q is False) but you can take the flight (p is True).
✓ When you buy a ticket (q is True) but you cannot take the flight (p is False).

TABLE 6: The Truth Table for the biconditional statement p ↔ q:

p q p↔q
T T T
T F F
F T F
F F T
• We can construct a truth table of the compound proposition by using
the precedence of logical operator:
Operator Precedence
¬ 1
∧ 2
∨ 3
→ 4
↔ 5

• Example 8: Construct the truth table of the compound proposition

(p ∨ ¬ q) → (p ∧ q).
p q ¬q p ∨ ¬q p∧q (p ∨ ¬ q) → (p ∧ q)
T T F T T T
T F T T F F
F T F F F T
F F T T F F
• Example 9: Construct the truth table of the compound proposition
¬ (p ∧ q) ∨ (¬ r).
p q r p∧q ¬ (p ∧ q) ¬ r ¬ (p ∧ q) ∨ (¬ r)
T T T T F F F
T T F T F T T
T F T F T F T
T F F F T T T
F T T F T F T
F T F F T T T
F F T F T F T
F F F F T T T
• A tautology is the compound proposition that is always true.
• Example 10: Show that p → q ↔ ¬ q → ¬ p is tautology.
p q ¬p ¬q p→q ¬q → ¬p p → q ↔ ¬q →
¬p
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T
Because all the truth values are True, thus (p → q) ↔ (¬ q → ¬ p) is tautology.
• The proposition logic is not powerful enough to represent all types of assertions that are used in computer
science and mathematics.
• Predicate logic is a more powerful type of logic to express the meaning of a wide range of statements in
mathematics and computer science in ways to reason and explore relationships between objects.
• Statement involving variables, such as:-
“x > 3”
“x = y +3”
“x + y = z”
“computer x is functioning properly.”
are often found in mathematical assertions, in computer programs,
and in system specifications.
• These statements are neither true nor false when the values of the
variables are not specified.
• The statement “x is greater than 3” has two part:-
➢First part – the variable x, is the subject of the statement.
➢Second part – the predicate, “is greater than 3”
• The statement “x is greater than 3” denote by P(x), where P
denotes the predicate “is greater than 3” and x is the variable.
• Example 17: Let P(x) denote the statement “x > 3”. What are the
truth values of P(4) and P(2)?
➢For P(4), the x = 4, thus the truth value is T since “4 > 3” is a true
statement.
➢For P(2), the x = 2, thus the truth value is F since “2 > 3” is a
false statement.
• Example 18: Let Q(x, y) denote the statement “x = y +3”. What
are truth values of the propositions Q(1, 2) and Q(3, 0)?
➢ For Q(1, 2), set x = 1 and y = 2 in the statement Q(x, y). Hence
the truth value is F since “1 = 2 + 3” is a false statement.
➢ For Q(3, 0), set x = 3 and y = 0 in the statement Q(x, y). Hence
the truth value is T since “3 = 0 + 3” is a true statement.
• Quantification is another important way to create a proposition
from a propositional function.
• Quantification expresses the extent to which a predicate is true
over a range of elements.
• In English, the words all, some, many, none, and few are used in
quantification.
• Two types of quantification:-
➢ Universal Quantifier (a predicate is true for every element
under consideration.)
➢ Existential Quantifier (there is one or more element under
consideration for which predicate is true.)
• The universal quantifier of P(x) is the statement “P(x) for all values of x in
the domain,” denoted by ∀xP(x), which read as “for all x P(x)” or “for
every x P(x)” and ∀ called the universal quantifier.
• An element for which P(x) is false is called a counterexample of ∀xP(x).
• ∀xP(x) is same as conjunction.

• Example 19: Let P(x) be the statement “x + 1 > x”. What is the truth value of
the quantification ∀xP(x), where the domain consists of all real numbers?
➢The quantification is true since P(x) is true for all real numbers x.

• Example 20: Let Q(x) be the statement “x < 2”.What is the truth value of the
quantification ∀xQ(x), where the domain consists of all real numbers?
➢Q(x) is not true for every real number x, because, for instance Q(3) is false.
That is,
➢x = 3 is a counterexample for the statement . Thus is false.
• The existential quantifier of P(x) is the proposition “There exist an element
x in the domain such that P(x)”, denoted by ∃xP(x) , which read as
“there is an x such that P(x)” , “there is at least one x such that P(x)” or
“for some x P(x)”. ∃ is called the existential quantifier.
• ∃xP(x) is false if and only if P(x) is false for every element of the P(x).
• ∃xP(x) is same as disjunction.

• Example 21: Let P(x) denote the statement “x > 3”. What is the truth value of
the quantification ∃xP(x), where the domain consists of all real numbers?
➢Because “x > 3” is sometimes true – for instance, when x = 4, thus ∃xP(x) is
true.

• Example: Let Q(x) denote the statement “x = x + 1”. What is the truth value of
the quantification ∃xQ(x), where the domain consists of all real numbers?
➢Because Q(x) is false for every real number x, the existential quantifier of
Q(x), which is ∃xP(x), is false.
• Translating English into logical expression becomes more complex
when quantifiers are needed.
• There can be many ways to translate a particular sentence.

• Example 22: Express the statement “Every student in this class has studied
calculus” using predicates and quantifiers.
➢First step: Rewrite the statement so that can identify the appropriate
quantifiers to use.
“For every student in this class, that student has studied calculus.”
➢Second step: Introduce a variable x so that the statement becomes
“For every student x in this class, x has studied calculus.”
➢Third step: Introduce C(x), which is the statement “x has studied calculus.” If the
domain for x consists of the students in the class, then the statement translate as
∀xC(x).
• Example 23: Express the statements “Some student in this class has
visited Malacca” using predicates and quantifiers.
➢First step: Rewrite the statement so that can identify the
appropriate quantifiers to use.
“There is a student in this class, that the student has visited Malacca.”
➢Second step: Introduce a variable x so that the statement
becomes
“There is a student in x this class, that x has visited Malacca.”
➢Third step: Introduce M(x), which is the statement “x has visited
Malacca.” If the domain for x consists of the students in the class,
then the statement translate as ∃xM(x) .
• Example 24: Let C(x, y) be the predicate “x clever than y” and let
the universe of discourse be the set of all students. Use quantifiers
to express the statement “Not everyone is not clever than
someone.”
➢First step: Rewrite the statement so that can identify the
appropriate quantifiers to use.
“Not every students is not clever than some students.”
➢Second step: Introduce a variable x so that the statement
becomes
“Not every x is not clever than some y.”
➢Third step: Hence, the statement translate as ¬ ∀x∃y¬ C(x,y).
• Example 25: Let P(x, y) be the predicate “x loves y” and let the
universe of discourse be the set of all people in Malaysia. Express
the quantification ∃x∀y¬P(x, y) in sentences.
• ∃x express to someone in Malaysia.
• ∀y express to everyone in Malaysia.
• Because P(x, y) is the predicate “x loves y”, thus ¬ P(x, y) express
to “x not love y”
• Combine all the sentences and will become “Someone in Malaysia
not love everyone in Malaysia.”
• An argument is a sequence of propositions which contains premises and a
conclusion.
P1
P2
P3
.
Premises (Hypotheses)
.
.
____________
∴𝑞 Conclusion
• Consider the following argument involving propositions:
“If you have the password, then you can log onto the
network.”
“You have the password.”
Therefore, “You can log onto the network.”
• The argument has the form
p→q
p We would like to determine whether this
________ argument is a valid argument.
∴q
• An argument is valid when all its premises are true implies that the
conclusion is true.
• We can always use a truth table to show that an argument form is valid or
invalid.
✓ The argument form with premises P1, P2, …, Pn and conclusion q is valid when (P1 ∧ P2 ∧ …
∧ Pn) → q is a tautology.
• Example 26: Is the argument below is valid?
p→q
p
________
∴q
Premises P1 ˄ P2 Conclusion (P1 ˄ P2) → q
p q p→q p (p → q) ˄ p q [(p → q) ˄ p]→p
T T T T T T T
T F F T F F T
F T T F F T T
F F T F F F T

• It is tautology, therefore the argument is valid.

• Example 27: So, is this argument a valid argument?
p→q
q
________
∴p
Premises P1 ˄ P2 Conclusion (P1 ˄ P2) → q
p q p→q q (p → q) ˄ q p [(p → q) ˄ p]→p
T T T T T T T
T F F F F T T
F T T T T F F
F F T F F F T
• It is not tautology, therefore the argument is invalid.
• Example 28: show that the argument below is valid with using tautology.
p ∨ (q ∨ r)
¬ r________
∴p˅q

p q r q∨r p ∨ (q ∨ r) ¬r (p ∨ (q ∨ r)) ∧ (¬ r) p∨q (p ∨ (q ∨ r)) ∧ (¬ r) → (p ∨ q)

T T T T T F F T T

T T F T T T T T T

T F T T T F F T T

T F F F T T T T T

F T T T T F F T T

F T F T T T T T T

F F T T T F F F T

F F F F F T F F T

• It is not tautology, therefore the argument is invalid.

• Rules of inference are the validity of some relatively simple
argument forms which do not have to resort to truth table.
Table of the rules of inference:
Let p : It is a raining day.
q : I will stay at home.
r : I will cook dinner for you.
Rules of Tautology Name Example 15
Inference
p→q [(p → q) ∧ p] → q Modus Ponens If it is a raining day, then I will stay at home. It is a
p raining day. Therefore, I will stay at home.
∴q
p→q [(p → q) ∧ ¬ q] → ¬ p Modus Tollens If it is a raining day, then I will stay at home. I will
¬ q not stay at home. Thus, it is not a raining day.
∴¬ p
p→q [(p→q)∧(q→r)]→(p→r) Hypothetical If it is a raining day, then I will stay at home. If I
q→r Syllogism stay at home, then I will cook dinner for you.
∴p → r Therefore, if it is a raining day, then I will cook
dinner for you.
p∨q [(p ∨ q) ∧ ¬ p] → q Disjunctive It is either a raining day or I will stay at home. It is
¬p Syllogism not a raining day. Therefore, I will stay at home.
∴q
p p → (p ∨ q) Addition It is a raining day. Therefore, it is either a raining
∴p ∨ q day or I will stay at home.
• When there are many premises, several rules of inference are often
needed to show that an argument is valid.
• There are two steps to build valid argument by using rules of inference:-
❖First step:
- List out all the premises and the conclusion which denoted by letter such
as p, q, r, s, t, and so on and build the valid argument
❖Second step:
- Show that the hypotheses lead to conclusion by using the rules of
inference and state what kind of rules are using.
• Example 29: Show that the hypothesis “If I do not finish writing the report,
then you do not send me an e-mail message,” “If you do not send me an e-
mail message, then I will go to sleep early,” and “If I go to sleep early,
then I will wake up early” lead to the conclusion “If I do not finish writing
the report, then I will wake up early.”
❖ Step 1:
• Let p : I do not finish writing the report.
• q : You do not send me an e-mail message.
• r : I will go to sleep early.
• s : I will wake up early.
So, the premises are p → q, q → r, r → s and the conclusion is p → s.
The argument form is
p→q
q→r
r→s
∴ p→ s
❖ Step 2:
Steps Reasons
1) p → q Hypothesis / Premise
2) q → r Hypothesis / Premise
3) P → r Use step (1), (2), and Hypothetical Syllogism
4) r → s Hypothesis / Premise
5) ∴ p → s Use step (3), (4), and Hypothetical Syllogism

❖ This argument form shows that the hypotheses lead to the desired conclusion.