Mathematical Logic

Mathematical Logic

At the end of this lesson, students will be able to:

• Distinguish statement from sentences or mathematical expressions
• Infer the relation among statement using logical connectives and truth values
• Apply the inference rules to construct the correct mathematical arguments

Mathematical Logic 2
 Mathematical Logic

Contents
• Statement and Truth value
• Truth Table
• Logical Equivalence
• Quantifier Statements
• Validity of an Argument

Mathematical Logic 3
 Statement and Truth Table

A proposition (or statement) is a declarative sentence that is either true or false

but not both.
• Examples
• Washington, D.C., is the capital of the United States of America. ← True
• Toronto is the capital of Canada. ←False
• 1+1=2 ← True
• 2+2=3 ←False
• What time is it? ←Not proposition
• Read this carefully. ←Not proposition Truth value
• x+1=2 ←neither true nor false
True (T)
• False (F)
x+y=z ←neither true nor false

Mathematical Logic 4
 Compound Statements
Propositional variables (or statement variables): p, q, r, s, . . . .
Logical operators: Negation(⇁), Conjunction(∧), Disjunction(˅),
conditional (→), biconditional (↔)
Negation The Truth Table for
not the Negation of
Let p be a proposition. ↓
The negation of p, denoted by ￢p, is the statement Proposition
It is not the case that p. p ⇁p
T F
• Example
F T
• p: New York is the capital of France. (False)
• ⇁p : It is not the case that New York is the capital of France. (True)
• ⇁p : New York is not the capital of France. (True)

Mathematical Logic 5
 Compound Statements
Truth value of Truth value of
Conjunction
and p q
Let p and q be propositions. ↓ T T ⇒ T T
• The conjunction of p and q, denoted by p ∧ q, is the F ⇒TF
proposition “p and q.” F T ⇒FT
• In logic the word “but” sometimes is used instead of “and” in F ⇒FF
a conjunction. The Truth Table for
• Rule:The conjunction p ∧ q is true when both p and q are true the Conjunction of
and is false otherwise. Two Propositions
• Example: The propositions p q p∧q
• p : 2+3 = 5 (True)
T T T
• q : 5 is a composite number. (False) T F F
• p ∧ q: 2+3 = 5 and 5 is a composite number. (False) F T F
F F F
Mathematical Logic 6
 Compound Statements
inclusive or
Disjunction (and/or, at
or least one)
Let p and q be propositions. ↓ or
• The disjunction of p and q (inclusive or) , denoted by p ˅ q, is exclusive or
(exactly one
the proposition “p or q.”
but not both)

• Rule: A disjunction is true when at least one of the two

propositions in it is true. Truth Table for p ˅ q
p q p˅q
• Example: The propositions T T T
• p : 2+3=5. (True) T F T
• q : 5 is a composite number. (False) F T T
• p ˅ q: 2+3=5 or 5 is a composite number. (True) F F F

Mathematical Logic 7
 Compound Statements
Exclusive or
exclusive or
Let p and q be propositions. ↓
• The exclusive or of p and q, denoted by p ⊕ q, is the proposition “p or q (but not both)”
(p ∨ q) ∧ ⇁ (p ∧ q)
Rule: The p ⊕ q is true when exactly one of p and q is true and is false otherwise.

Truth values of p ⊕ q
p q p ∨ q p ∧ q ⇁ (p ∧ q) (p ∨ q) ∧ ⇁ (p ∧ q)
T T T T F F
T F T F T T
F T T F T T
F F F F T F

Mathematical Logic 8
 Compound Statements
Conditional Statements implies
↓
Let p and q be propositions. The conditional statement p → q is
the proposition “if p, then q.”
Rule:The conditional statement p → q is false when p is true and
q is false, and true otherwise.
Truth Table for p → q
p: Hypothesis
q: Consequence p q p→q
(or antecedent
(or conclusion)
or premise) T T T
• Example: The propositions T F F
F T T
• p : ΔABC is equilateral.
F F T
• q : ΔABC is isosceles.
• p → q : If ΔABC is equilateral, then it is isosceles.
Mathematical Logic 9
 Conditional Statements
• To express this conditional statement p → 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
• a necessary condition for p is q
• q follows from p
• q unless ￢p
Mathematical Logic 10
 Conditional Statements
• Three conditional statements formed from p → q
• The proposition q → p is called the converse of p → q.
• The proposition ￢p →￢q is called the inverse of p → q.
• The contrapositive of p → q is the proposition ￢q →￢p.
• The contrapositive always has the same truth value as p → q.
p q p→q q→p ￢p ￢q ￢p →￢q ￢q →￢p
T T T T F F T T
T F F T F T T F
F T T F T F F T
F F T T T T T T

converse inverse contrapositive

of p→q of p→q
Mathematical Logic
of p→q 11
 Conditional Statements
Biconditional statement
• p ↔ q is the proposition “p if and only if q.” (p if q and p only if q)
• also called bi-implications. (q→p) ∧ (p→q)
Rule:p ↔ q is true when p and q have the same truth values, and is false otherwise.

Truth Table for p ↔ q • Example: The propositions

p q q→p p→q (q→p)∧(p→q) • p : ΔABC is equilateral.
T T T T T • q : ΔABC is equiangular.
T F T F F • p ↔ q : ΔABC is equilateral if and
F T F T F only if it is equiangular.
F F T T T

Mathematical Logic 12
 Truth Table of Compound Propositions

p q p∧q p∨q p⊕q p→q p↔q

T T T T F T T
T F F T T F F
F T F T T T F
F F F F F T T

Mathematical Logic 13
 Precedence of Logical Operators

Operator Precedence
⇁ 1
∧ 2 (p → q) ∧⇁q → ⇁p ⇨ [(p → q) ∧⇁q ] → (⇁p)
∨ 3 p → q ↔ ⇁q → ⇁p ⇨ (p → q ) ↔[(⇁q) → (⇁p)]
→ 4
↔ 5

⇁: unary operator
∧, ˅, →, ↔: binary operators

Mathematical Logic 14
 Logical Equivalences
Definition 1
A compound proposition that is
• always true, no matter what the truth values of the propositional variables that occur in it,
is called a tautology.
• always false is called a contradiction.
• neither a tautology nor a contradiction is called a contingency.

• Example 1: Consider the truth tables of p ∨￢p and p ∧￢p.

p ￢p p ∨￢p p ∧￢p
T F T F
F T T F

↑ ↑
tautology contradiction
Mathematical Logic 15
 Logical Equivalences
Definition 2
The compound propositions p and q are called logically equivalent
• if p ↔ q is a tautology.
• the columns headed by them in a truth table are identical.
• The notation p ≡ q denotes that p and q are logically equivalent.
↑
equivalent
Example 2: Show that ￢(p ∨ q) and ￢p ∧￢q are logically equivalent.
p q p ∨ q ￢(p ∨ q) ￢p ￢q ￢p ∧￢q ￢(p ∨ q) ↔(￢p ∧￢q )
T T T F F F F T
T F T F F T F T
F T T F T F F T
F F F T T T T T

identical column

∴￢(p ∨ q) ≡ ￢p ∧￢q. (DeMathematical

Morgan’s Logic
laws) tautology
16
 Logical Equivalences
Truth value of three different
propositional variables p, q, Example 3: Show that p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r)
and r are logically equivalent.
p q r Truth values of p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r)
T ⇒TTT p q r q ∧ r p ∨ (q ∧r) p ∨ q p ∨ r (p ∨ q) ∧ (p ∨ r)
T F ⇒TTF
T T T T T T T T T
T ⇒TFT T T F F T T T T
F
F ⇒TFF T F T F T T T T
T ⇒FTT T F F F T T T T
T F ⇒FTF F T T T T T T T
F T ⇒FFT F T F F F T F F
F F ⇒FFF F F T F F F T F
Nos: of propositions =1 ⇒2 (T, F) F F F F F F F F
Nos: of propositions =2 ⇒ 4 = 22 (TT, TF, FT, FF)
Nos: of propositions =3 ⇒ 8 = 23 ∴ p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (Distributive law)
Nos: of propositions =n ⇒ 2𝑛
Mathematical Logic 17
 Logical Equivalences
Equivalences Name
p ∧ T ≡ p, T-Tautology Identity laws
p ∨ F ≡ p, F-Contradiction
p∨T≡T Domination laws
p∧F≡F
p∨p≡p Idempotent laws
p∧p≡p
￢(￢p) ≡ p Double negation law
p∧q≡q∧p Commutative laws
p∨q≡q∨p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Mathematical Logic 18
 Logical Equivalences
Equivalences Name Logical Equivalences
￢(p ∧ q) ≡ ￢p ∨￢q De Morgan’s laws Involving Conditional Statements
￢(p ∨ q) ≡ ￢p ∧￢q p → q ≡ ￢p ∨ q
p ∨ (p ∧ q) ≡ p Absorption laws
p → q ≡ ￢q →￢p
p ∧ (p ∨ q) ≡ p
p ∨￢p ≡ T Negation laws p ∨ q ≡ ￢p → q
p ∧￢p ≡ F p ∧ q ≡ ￢(p →￢q)
Logical Equivalences Involving ￢(p → q) ≡ p ∧￢q
Biconditional Statements
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
p ↔ q ≡ (p → q) ∧ (q → p)
(p → r) ∧ (q → r) ≡ (p ∨ q) → r
p ↔ q ≡ ￢p ↔￢q
p ↔ q ≡ (p ∧ q) ∨ (￢p ∧￢q) (p → q) ∨ (p → r) ≡ p → (q ∨ r)
￢(p ↔ q) ≡ p ↔￢q (p → r) ∨ (q → r) ≡ (p ∧ q) → r
Mathematical Logic 19
 De Morgan’s Laws
• Example 4: Use De Morgan’s laws to express the negations of “Miguel has a cellphone
and he has a laptop computer” and “Heather will go to the concert or Steve will go to the
concert.”
• Solution: Let p : Miguel has a cellphone.
q : Miguel has a laptop computer.
p ∧ q:“Miguel has a cellphone and he has a laptop computer”
• By the first of De Morgan’s laws, ￢(p ∧ q) ≡ ￢p ∨￢q.
• ￢(p ∧ q): “Miguel does not have a cellphone or he does not have a laptop computer.”
• Let r : “Heather will go to the concert” and
s : “Steve will go to the concert.”
• r ∨ s:“Heather will go to the concert or Steve will go to the concert”
• By the second of De Morgan’s laws, ￢(r ∨ s) ≡ ￢r ∧￢s.
• ￢(r ∨ s):“Heather will not go to the concert and
Mathematical Steve will not go to the concert.”
Logic 20
 Constructing New Logical Equivalences
• Example 5: Show that ￢(p ∨ (￢p ∧ q)) and ￢p ∧￢q are logically equivalent by
developing a series of logical equivalences.
• Solution: ￢(p ∨ (￢p ∧ q)) ≡ ￢p ∧￢(￢p ∧ q) by the second De Morgan law
• ≡ ￢p ∧ [￢(￢p)∨￢q] by the first De Morgan law
• ≡ ￢p ∧ (p ∨￢q) by the double negation law
• ≡ (￢p ∧ p) ∨ (￢p ∧￢q) by the second distributive law
• ≡ F ∨ (￢p ∧￢q) because ￢p ∧ p ≡ F
• ≡ (￢p ∧￢q) ∨ F by the commutative law for disjunction
• ≡ ￢p ∧￢q by the identity law for F
• Consequently ￢(p ∨ (￢p ∧ q)) and ￢p ∧￢q are logically equivalent.

Mathematical Logic 21
 Predicates and Quantifiers
x>3 P(x): x > 3 where P denotes the predicate “is greater than 3”
and x is the variable.
Subject predicate The statement P(x) is said to be the value of the propositional
function P at x.

• Example 1: Let P(x) denote the statement “x > 3.” What are the truth values of P(4) and
P(2)?
• Solution: P(4) ⇒ 4 > 3. ∴ P(4) is true.
P(2) ⇒ 2≯ 3. ∴ P(2) is false.
• Example 2: Let Q(x, y) denote the statement “x = y + 3.” What are the truth values of the
propositions Q(1, 2) and Q(3, 0)?
Solution: Q(1, 2) ⇒ 1 = 2 + 3, which is false.
Q(3, 0) ⇒ 3 = 0 + 3, which is true.
Mathematical Logic 22
 Predicates and Quantifiers
• A predicate P(x) involves just one variable, it is a unary predicate.
• A predicate that contains two variables, Q(x, y) is a binary predicate.
• If a predicate contains n variables, P(𝑥1 ,𝑥2 , . . . , 𝑥𝑛 ) it is an n-ary predicate.
Quantification
• to create a proposition from a propositional function.
• expresses the extent to which a predicate is true over a range of elements.
• the words all, some, many, none, and few are used in quantifications.
• Two types of quantification
• universal quantification: a predicate is true for every element under consideration, (for
all, for every, all of, for each, given any, for arbitrary, for
each, and for any)
• existential quantification : there is one or more element under consideration for which
the predicate is true.(for some, for at least one, or there is)

Mathematical Logic 23
 Universal Quantifiers
• The universal quantification of P(x) is the statement “P(x) for all values of x in the domain.”
• The notation: ∀xP(x).
• ∀ is called the universal quantifier.
• read ∀xP(x) as “for all xP(x)” or “for every xP(x).”
• An element for which P(x) is false is called a counterexample of ∀xP(x).
• When all the elements in the domain can be listed—say, 𝑥1 , 𝑥2 , . . . , 𝑥𝑛 —it follows that the
universal quantification ∀xP(x) is the same as the conjunction
P(𝑥1 ) ∧ P(𝑥2 ) ∧ ・ ・ ・ ∧ P(𝑥𝑛 ),
• because this conjunction is true if and only if P(𝑥1 ), P(𝑥2 ), . . . , P (𝑥𝑛 ) are all true.
• Example 3: 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?
• Solution: Because P(x) is true for all real numbers x, the quantification ∀xP(x) is true.
Mathematical Logic 24
 Universal Quantifiers
2
• Example 4: What is the truth value of ∀xP(x), where P(x) is the statement “𝑥 < 10” and
the domain consists of the positive integers not exceeding 4?
• Solution: domain ={1, 2, 3, 4}
The statement ∀xP(x) is the same as the conjunction P(1) ∧ P(2) ∧ P(3) ∧ P(4).
2
• P(1) = 1 < 10 ⇨ P(1) is true.
2
• P(2) = 2 < 10 ⇨ P(2) is true.
2
• P(3) = 3 < 10 ⇨ P(3) is true.
2
• P(4) = 4 > 10 ⇨ P(4) is false.
P(1) ∧ P(2) ∧ P(3) ∧ P(4) is false.
∴∀xP(x) is false.

Mathematical Logic 25
 Existential Quantifier
• The existential quantification of P(x) is the proposition “There exists an element x in the
domain such that P(x).”
• the notation ∃xP(x) and ∃ is called the existential quantifier.
The existential quantification ∃xP(x) is read as
• “There is an x such that P(x),” “There is at least one x such that P(x),”or “For some
xP(x).”
• When all elements in the domain can be listed—say, 𝑥1 , 𝑥2 , . . . , 𝑥𝑛 —the existential
quantification ∃xP(x) is the same as the disjunction
P(𝑥1 ) ∨ P(𝑥2 ) ∨ ・ ・ ・ ∨ P(𝑥𝑛 )
• because this disjunction is true if and only if at least one of P(𝑥1 ), P(𝑥2 ), . . . , P (𝑥𝑛 ) is
true.

Mathematical Logic 26
 Existential Quantifier
2
Example 5: What is the truth value of ∃xP(x), where P(x) is the statement “𝑥 > 10” and
the universe of discourse consists of the positive integers not exceeding 4?
• Solution: domain ={1, 2, 3, 4}
The statement ∃ xP(x) is the same as the disjunction P(1) ∨ P(2) ∨ P(3) ∨ P(4).
2
• P(1) = 1 < 10 ⇨ P(1) is false.
2
• P(2) = 2 < 10 ⇨ P(2) is false.
2
• P(3) = 3 < 10 ⇨ P(3) is false.
2
• P(4) = 4 > 10 ⇨ P(4) is true.
P(1) ∨ P(2) ∨ P(3) ∨ P(4) is true.
∴∃xP(x) is true.

Mathematical Logic 27
 Precedence of Quantifiers

Statement When True? When False?

∀xP(x) P(x) is true for every x. There is an x for which P(x) is
false.
∃xP(x) There is an x for which P(x) P(x) is false for every x.
is true.
• Precedence of Quantifiers
• The quantifiers ∀ and ∃ have higher precedence than all logical operators(⇁, ∧, ∨, →, ↔)
• For example, ∀xP(x) ∨ Q(x) is the disjunction of ∀xP(x) and Q(x).
• In other words, it means (∀xP(x)) ∨ Q(x) rather than ∀x(P(x) ∨ Q(x)).

Mathematical Logic 28
 Logical Equivalences Involving Quantifiers
Definition 3
• Statements involving predicates and quantifiers are logically equivalent if and only if they
have the same truth value no matter which predicates are substituted into these statements
and which domain of discourse is used for the variables in these propositional functions.
• The notation S ≡ T to indicate that two statements S and T involving predicates and
quantifiers are logically equivalent.

Mathematical Logic 29
 De Morgan's laws for Quantifiers
Negating Quantified Expressions
• The proposition; All apples are green.⇨ ∀xP(x) where P(x): x are green.
• Its negation: All apples are not green. That is, there exists an apple that is not green. In
symbols, this can be written as ∃x⇁P(x) .
• Thus, ⇁[(∀x)P(x)] ≡(∃x)[⇁P(x)].
• Similarly, ⇁[ (∃x)P(x)] ≡ (∀ x)[⇁ P(x)].
De Morgan's laws for Quantifier
• ⇁[(∀x)P(x)] ≡(∃x)[⇁P(x)].
• ⇁[ (∃x)P(x)] ≡ (∀ x)[⇁ P(x)].

Mathematical Logic 30
 Quantifiers

2 2
Example 5: What are the negations of the statements ∀x(𝑥 > x) and ∃x(𝑥 = 2)?
2 2
• Solution: ⇁∀x(𝑥 > x) ≡ ∃x￢(𝑥 > x) ≡ ∃x(𝑥 2 ≤ x)
2 2
⇁∃x(𝑥 = 2) ≡∀x￢(𝑥 = 2) ≡ ∀x(𝑥 2 ≠ 2)
• The truth values of these statements depend on the domain.

Mathematical Logic 31
 Valid Arguments
• Argument: a sequence of statements that end with a conclusion.
• Valid: the conclusion, or final statement of the argument must follow from the truth of the
preceding statements, or premises, of the argument.
• Example: Consider the following argument involving propositions:
“If you have a current password, then you can log onto the network.” ⇨ p → q
“You have a current password.” ⇨ p
Therefore,
“You can log onto the network.” ⇨ q
Solution: Let p: “You have a current password” and q : “You can log onto the network.”
p→q
p [(p → q)∧ p ]→q
∴q
• when both p → q and p are true, q must also be true. This argument is valid because its form is valid.

Mathematical Logic 32
 Valid Arguments
Definition
• An argument in propositional logic is a sequence of propositions. All but the final
proposition in the argument are called premises and the final proposition is called the
conclusion.
• An argument is valid if the truth of all its premises implies that the conclusion is true.
• An argument form in propositional logic is a sequence of compound propositions
involving propositional variables.
• An argument form is valid no matter which particular propositions are substituted for the
propositional variables in its premises, the conclusion is true if the premises are all true.
• The argument form with premises 𝑝1
𝑝1 , 𝑝2 , . . . , 𝑝n and conclusion q is valid, 𝑝2
when (𝑝1 ∧ 𝑝2 ∧ ・ ・ ・ ∧ 𝑝n ) → q is a tautology. ⋮ ⇦ inferential form
𝑝n
∴𝑞
Mathematical Logic 33
 Valid Arguments
Inference Rules
1. (p)∧(q )→ (p∧q) conjunction
2. p∧q → p simplification
3. p→ p˅q addition
4. [p ∧ (p → q)] → q law of detachment
5. [(p →q) ∧ (⇁q)] → ⇁p law of the contrapositive
6. [(p ˅q) ∧ (⇁p)] → q disjunctive syllogism
7. [(p → q) ∧(q → r)] →(p → r) hypothetical syllogism

Mathematical Logic 34
 Valid Arguments
Example1: Determine whether the argument given here is valid and determine whether its conclusion must be
true because of the validity of the argument.
3 2 3 2 3 2 3 2 9
• “If 2 > , then 2 > .We know that 2 > . Consequently, 2 = 2 > = .”
2 2 2 2 4
3 2 3 2
• Solution: Let p be the proposition “ 2 > ” and q the proposition “ 2 > .”
2 2
3 2 3 2
If 2 >
2
, then 2 >
2
⇨p→q
3
We know that 2 > ⇨p [(p → q)∧ p ]→q (Law of detachment)
2
2 3 2 9
Consequently, 2 = 2 > = . ⇨ ∴q
2 4
Therefore, the argument given is valid.
3
p: 2 > , is false.
2
2 3 2 9 2 3 2 9
The conclusion q: 2 = 2 > = is false, because 2 = 2 < = .
2 4 2 4

Mathematical Logic 35
 Using Rules of Inference to Build Arguments
• Example 2: Show that the premises “It is • Then the premises become ￢p ∧ q, r → p,
not sunny this afternoon and it is colder ￢r → s, s → t and conclusion is t .
than yesterday,” “We will go swimming
only if it is sunny,” “If we do not go Step Reason
swimming, then we will take a canoe trip,” 1. ￢p ∧ q Premise
and “If we take a canoe trip, then we will be 2. ￢p Simplification using (1)
home by sunset” lead to the conclusion “We 3. r → p Premise
will be home by sunset.” 4. ￢r Law of contrapositive using (2) and
• Solution: Let p:It is sunny this afternoon. (3)
5. ￢r → s Premise
• q :It is colder than yesterday. 6. s Law of detachment using (4) and (5)
• r :We will go swimming. 7. s → t Premise
• s:We will take a canoe trip. 8. t Law of detachment using (6) and (7)

• t :We will be home by sunset..

Mathematical Logic 36
 Mathematical Logic

Summary
• Statement and Truth value
• Truth Table for compound propositions
• Logical Equivalence
• Quantifier Statements
• Validity of an Argument

Mathematical Logic 37
 Mathematical Logic
• References
• Discrete Mathematics with Applications, First Edition, December 8,2003, Thomas Koshy.
• Discrete Mathematics and its Applications, Seventh Edition, Kenneth H. Rosen,
Monmouth University.
• Fundamental Approach to Discrete Mathematics, Second Edition, D.P Acharjya,
Sreekumar.

Mathematical Logic 38