UNIT V-LOGIC

1
1.1 Propositional Logic
Propositions
A proposition is a declarative sentence (that is, a sentence that
declares a fact) that is either true or false, but not both.

EXAMPLE l All the following declarative sentences are propositions.

1 . Washington, D.C., is the capital of the United States of America.
2 . Toronto is the capital of Canada.
3. 1 + 1 =2
4. 2 + 2 = 3

2
Some sentences that are not propositions are given in
Example.

EXAMPLE Consider the following sentences.

1 . What time is it?

2 . Read this carefully.

3.x+1=2.

4 . x + y = Z.

The truth value of a proposition is true, denoted by T, if it is a

true proposition and false, denoted by F, if it is a false
proposition.
3
 NEGATION

TRUTH TABLE

p ¬p

T F
F T
DEFINITION 1 : Let p be a proposition. The negation of p, denoted by ¬p
(also denoted by p), is the statement

"It is not the case that p."

The proposition ¬ p is read "not p." The truth value of the negation of p, -
p, is the opposite of the truth value of p.

5
EXAMPLE : Find the negation of the proposition

"Today is Friday.“ and express this in simple English.

Solution:

6
EXAMPLE : Find the negation of the proposition

"Today is Friday.“ and express this in simple English.

Solution:

It is not the case that today is Friday

(or)

Today is not Friday

7
CONJUNCTION

8
DEFINITION 2

Let p and q be propositions. 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.

9
EXAMPLE Find the conjunction of the propositions p and q
where p is the proposition "Today is Friday"

and q is the proposition "It is raining today.“

Solution:

10
EXAMPLE Find the conjunction of the propositions p and q
where p is the proposition "Today is Friday"

and q is the proposition "It is raining today.“

Solution:

“Today is Friday and it is raining today”. This proposition is true on rainy

Fridays and is false on any day that is not a Friday and on Fridays when it
does not rain.

11
DISJUNCTION

12
DEFINITION 3:

Let p and q be propositions. The disjunction of p and q, denoted by p V

q, is the proposition

"p or q ." The disjunction p V q is false when both p and q are false and
is true otherwise.

13
EXAMPLE :

What is the disjunction of the propositions p and q where p is the

proposition "Today is Friday“ and q is the proposition "It is raining
today.“

Solution:

14
EXAMPLE :

What is the disjunction of the propositions p and q where p is the

proposition "Today is Friday“ and q is the proposition "It is raining
today.“

Solution:

“Today is Friday or it is raining today”. This is true on any day that is either
a Friday or a rainy day (including rainy Fridays). It is only false on days
that are not Fridays when it also does not rain.

15
CONDITIONAL STATEMENT

16
DEFINITION 4:

Let p and q be propositions. The conditional statement

𝑝 → 𝑞 is the proposition "if p, then q ." The conditional statement 𝑝 → 𝑞

is false when p is true and q is false, and true otherwise.

In the conditional statement 𝑝 → 𝑞 , p is called the hypothesis (or

antecedent or premise) and q is called the conclusion (or consequence)

17
The statement 𝑝 → 𝑞 is called a conditional statement because 𝑝 → 𝑞
asserts that q is true

on the condition that p holds. A conditional statement is also called an

implication.

statement 𝑝 → 𝑞 is true when both p and q are true and when p is false
(no matter what truth value q has).

18
EXAMPLE:

What is the conditional statement of the propositions p and q where p is

the proposition “Maria learns discrete mathematics“ and q is the
proposition “Maria will find a good job.“

Solution:

19
EXAMPLE:

What is the conditional statement of the propositions p and q where p is

the proposition “Maria learns computer science“ and q is the
proposition “Maria will find a good job.“

Solution:

“If Maria learns computer science, then she will find a good job”.

20
BICONDITIONAL STATEMENT

21
DEFINITION 5:

Let p and q be propositions. The biconditional statement p ⟷ 𝑞 is the

proposition "p if and only if q ." The biconditional statement p ⟷ 𝑞 is
true when p and q have the same truth values, and is false otherwise.
Biconditional statements are also called bi-implications.

22
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 ."

23
EXAMPLE:

What is the Biconditional statement of the propositions p and q where p

is the proposition “ You can take the flight“ and q is the proposition
“You buy a ticket“

Solution:

24
EXAMPLE:

What is the Biconditional statement of the propositions p and q where p

is the proposition “ You can take the flight“ and q is the proposition
“You buy a ticket“

Solution:

“You can take the flight iff if you buy a ticket”.

25
Truth Tables of Compound Propositions

26
 TYPE STATEMENT SYMBOL
Statement If p, then q. 𝑝→𝑞

Converse If q, then p. 𝑞→𝑝

Inverse If not p, then not q. ¬𝑝 → ¬𝑞

¬𝑞 → ¬𝑝
Contrapositive If not q, then not p.
 If two angles are congruent, then they
Statement
have the same measure.

If two angles have the same measure,

Converse
then they are congruent.

If two angles are not congruent, then they

Inverse
do not have the same measure.

If two angles do not have the same

Contrapositive
measure, then they are not congruent.
 APPLICATIONS OF PROPOSITIONAL LOGIC
TRANSLATING ENGLISH SENTENCES
Problem 1
Translate the following sentence into logical expression:
“You can access the internet from campus only if are a
computer science major or you are not a freshman”.
Answer.
𝒑 → (𝒒 ∨ ¬ 𝒓 )
Problem 2
Let p, q, and r be the proposition
p: You have flu
q: You miss the final examination
r: You pass the course
Express each of these propositions as an English
sentences:
i) (𝑝 → 𝑞) ii) (𝑝∧𝑞)∨(¬𝑞∧𝑟)
iii) ¬𝑞 ⟷ 𝑟 iv) (𝑝 → ¬𝑟)∨(𝑞∧𝑟).
Answer.
i) If you have the flu then you will miss the final
examination.
ii) You have the flu and you miss the final examination or you
don’t miss the final examination and you pass the course.
iii) You don’t miss the final examination if and only if you pass
the course.
iv) If you have the flu then you will not pass that course or
you miss the final examination and you will pass the
course.
Problem 3
Let p, q, and r be the proposition
p: It is below freezing q: It is snowing
Write the propositions using p and q and logical connectives.
a) It is below freezing but not snowing
b) If it is below freezing, it is also snowing
c) It is either below freezing or it is snowing, but it is not snowing if it is
below freezing.
Answer.
a) 𝒑 ∧ ¬ 𝒒 b) 𝒑 → 𝒒 c) (𝒑 ∨ 𝒒) ∧ (𝒑 → ¬𝒒)
 LOGIC AND BIT OPERATIONS
• Computers represent information using bits. A bit is a symbol with two
possible values, namely, 0 (zero) and 1 (one).
• A bit can be used to represent a truth value. That is, 1 represents T (true), 0
represents F (false).
• A variable is called a Boolean variable if its value is either true or false.
Consequently, a Boolean variable can be represented using a bit.
• Computer bit operations correspond to the logical connectives.
• We will also use the notation OR, AND, and XOR for the operators ∨, ∧, and
⊕, as is done in various programming languages.
Give the table for the Bit operators OR, AND, and XOR.
Find the bitwise OR, bitwise AND, and bitwise XOR of the bit
strings 01 1011 0110 and 11 0001 1101.
Tautology
Contradiction
 LOGICAL EQUIVALENCES
• Compound propositions that have the same truth
values in all possible cases are called logically
equivalent.
• The compound propositions p and q are called
logically equivalent if 𝑝 ↔ 𝑞 is a tautology.
• The notation p ≡ q denotes that p and q are
logically equivalent.
Show that ¬ (𝑝 ∨ 𝑞) and ¬𝑝 ∧ ¬𝑞 are logically equivalent.
Show that 𝑝 ∨ 𝑞 ∧ 𝑟 and 𝑝 ∨ 𝑞 ∧ (𝑝 ∨ 𝑟) are logically
equivalent.
Show that ¬ (𝑝 ∨ ¬𝑝 ∧ 𝑞 ) and ¬𝑝 ∧ ¬𝑞 are logically
equivalent by developing a series of logical equivalences.
Show that 𝑝 ∧ 𝑞 → 𝑝 ∨ 𝑞 is a tautology.
 PREDICATE LOGIC

A predicate is a proposition that is a function of one

or more variables.
E.g.: P(x): x is an even number.
So P(1) is false, P(2) is true,…
1. Let A(x) denote the statement “Computer x is under attack by an
intruder.” Suppose that of the computers on campus, only CS2 and
MATH1 are currently under attack by intruders. What are truth
values of A(CS1), A(CS2), and A(MATH1)?
• A(CS1) is obtained by setting x = CS1 in the statement
“Computer x is under attack by an intruder.”
• Because CS1 is not on the list of computers currently under
attack, A(CS1) is false.
• Similarly, CS2 and MATH1 are on the list of computers under
attack, therefore A(CS2) and A(MATH1) are true.
 n-place PREDICATE

A statement involving the n variables 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

can be denoted by 𝑃(𝑥1 , 𝑥2 , … , 𝑥𝑛 ).
A statement of the form 𝑃(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) is the value of
the propositional function 𝑃 at the n-tuple
(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) and P is also called an n-place predicate
or a n-ary predicate.
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)?

• To obtain Q(1,2), set x = 1 and y = 2 in the statement

Q(x,y). Hence, Q(1,2) is the statement “1=2+3,” which
is false.
• The statement Q(3,0) is the proposition “3 = 0+3,”
which is true.
 QUANTIFIERS

• When the variables in a propositional function are

assigned values, the resulting statement becomes a
proposition with a certain truth value.
• Quantifiers express the extent to which the
predicate is true.
• In English, the words all, some, many, none, and
few are used in quantifications.
There are two types:
• Universal: a predicate is true for every
element under consideration.
• Existential: a predicate is true for there is one
or more elements under consideration.
Predicate Calculus:
The area of logic that deals with predicates and
quantifiers.
 Universal Quantifier ∀
• Statement: 𝑃 𝑥 for all values of 𝑥 in the domain ∀𝑥 𝑃 𝑥 .
• The notation ∀𝑥 𝑃 𝑥 denotes the universal quantification
of 𝑃 𝑥 .
• Here ∀ is called the universal quantifier.
• We read ∀𝑥 𝑃 𝑥 as “for all 𝑥 𝑃 𝑥 ” or “for every 𝑥 𝑃 𝑥 .”
• An element for which P(x)is false is called a counterexample
of ∀𝑥 𝑃 𝑥 .
 Existential Quantifier ∃
• Statement: There exists an element 𝑥 in the domain such that
𝑃(𝑥) .
• The notation ∃ 𝑥 𝑃(𝑥) denotes the existential quantification of
𝑃(𝑥).
• Here ∃ is called the universal quantifier.
• We read ∃ 𝑥 𝑃(𝑥) as “There is an 𝑥 such that 𝑃(𝑥), There is at
least one 𝑥 such that 𝑃(𝑥),” or “For some 𝑥 𝑃(𝑥).”
What is the truth value of ∀𝑥 𝑃 𝑥 , where 𝑃 𝑥 is the statement
“𝑥 2 < 10” and the domain consists of the positive integers not
exceeding 4?

Answer.
Here domain = {1,2,3,4}. ∀𝑥 𝑃 𝑥 is the same as the conjunction
𝑃(1) ∧ 𝑃(2) ∧ 𝑃(3) ∧ 𝑃(4).
𝑃(4), which is the statement “42 < 10,” is false.
Therefore, ∀𝑥 𝑃 𝑥 is false.
Let 𝑃(𝑥) denote the statement “𝑥 > 3.” What is the truth
value of the quantification ∃ 𝑥 𝑃(𝑥), where the domain
consists of all real numbers?

Answer.
Because “𝑥 > 3” is sometimes true. For instance, when 𝑥
= 4, the existential quantification of 𝑃(𝑥), which is ∃ 𝑥 𝑃(𝑥),
is true.
Let 𝑄(𝑥) denote the statement “𝑥 = 𝑥 + 1.” What is the
truth value of the quantification ∃ 𝑥 𝑄(𝑥), where the domain
consists of all real numbers?

Answer.
Because 𝑄(𝑥) is false for every real number 𝑥, the existential
quantification of 𝑄(𝑥), which is ∃ 𝑥 𝑄(𝑥), is false.
 Precedence of Quantifiers

• The quantifiers ∀ and ∃ have higher precedence than all

logical operators from propositional calculus.
• For example, ∀ 𝑥 𝑃(𝑥) ∨ 𝑄(𝑥) is the disjunction of
∀ 𝑥 𝑃(𝑥) and 𝑄(𝑥).
• In other words, it means ∀ 𝑥 𝑃 𝑥 ∨ 𝑄 𝑥 .
 Logical Equivalences Involving Quantifiers

• The notation 𝑃  𝑄 indicates that two statements 𝑃

and 𝑄 involving predicates and quantifiers are logically
equivalent.
• 𝑃  𝑄 iff they have same truth value no matter which
domain is used and no matter which predicates are
assigned to predicate variables.
Negating Quantified Expressions
¬ ∀𝑥𝑃 𝑥 ≡ ∃ 𝑥 , ¬ 𝑃(𝑥)
¬ ∃ 𝑥 𝑃 𝑥 ≡ ∀ 𝑥 , ¬ 𝑃(𝑥)
¬ 𝑃∧ 𝑄 ≡¬𝑃∨¬𝑄
¬ 𝑃∨𝑄 ≡¬𝑃∧¬𝑄
¬ 𝑃 → 𝑄 ≡ 𝑃∧¬𝑄
¬ ¬𝑃 ≡ 𝑃
Show that ¬ ∀ 𝑥 (𝑃(𝑥) → 𝑄(𝑥)) and ∃ 𝑥 (𝑃(𝑥) ∧ ¬ 𝑄(𝑥)) are
logically equivalent.

Solution:
By De Morgan’s law for universal quantifiers,
¬∀𝑥(𝑃(𝑥) → 𝑄(𝑥)) ≡ ∃𝑥(¬(𝑃(𝑥) → 𝑄(𝑥))). ---- (1)
W. K. T. , ¬ 𝑃 𝑥 → 𝑄 𝑥 ≡ 𝑃 𝑥 ∧ ¬𝑄 𝑥 . ----(2)
Substituting (2) in (1) it follows that,
¬∀𝑥 𝑃 𝑥 → 𝑄 𝑥 ≡ ∃𝑥(𝑃(𝑥) ∧ ¬𝑄(𝑥)).
 Translating from English into Logical Expressions
Express the statement “Every student in this class has studied calculus”
using predicates and quantifiers.
Solution.
Rewrite: “For every student in this class, that student has studied
calculus.”
Introduce variable: “For every student 𝑥 in this class, 𝑥 has studied
calculus.”
Introduce Predicate: 𝐶(𝑥), which is the statement “𝑥 has studied
calculus.”
Translation: ∀𝑥 𝐶 𝑥 .
Use predicates and quantifiers to express the system specifications “Every
mail message larger than one megabyte will be compressed” and “If a
user is active, at least one network link will be available.”

Solution.
Let 𝑆(𝑚, 𝑦) be “Mail message 𝑚 is larger than 𝑦 megabytes,” where the
variable 𝑥 has the domain of all mail messages and the variable 𝑦 is a
positive real number.
Let 𝐶(𝑚) denote “Mail message 𝑚 will be compressed.”
Therefore, ∀ 𝑚 (𝑆(𝑚, 1) → 𝐶(𝑚)).
Let 𝐴(𝑢) represent “User 𝑢 is active,” where the variable 𝑢 has the
domain of all users.
Let 𝑆(𝑛, 𝑥) denote “Network link 𝑛 is in state 𝑥,” where 𝑛 has the
domain of all network links and 𝑥 has the domain of all possible
states for a network link.
Therefore, ∃ 𝑢 𝐴 𝑢 → ∃ 𝑛 𝑆(𝑛, 𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒).
 Nested Quantifiers

• Nested quantifiers involve using multiple quantifiers in a

statement, often resulting in more complex logical
expressions.
• Allows simultaneous quantification of many variables.
EXPRESSION INTERPRETATION
∀𝑥 ∀𝑦 𝑃(𝑥, 𝑦) 𝑃(𝑥, 𝑦) is true for all x and all y.

∃𝑥 ∃𝑦 𝑃(𝑥, 𝑦) There exists at least one 𝑥 and one 𝑦

such that 𝑃(𝑥, 𝑦) is true.
∃𝑥 ∀𝑦 𝑃(𝑥, 𝑦) There exists an 𝑥 for which 𝑃(𝑥, 𝑦) is
true for every 𝑦.
∀𝑥 ∃𝑦 𝑃(𝑥, 𝑦) For each 𝑥, there exists a 𝑦 such that
𝑃(𝑥, 𝑦) is true.
Translate into English statement ∀ 𝑥 ∀ 𝑦 (𝑥 > 0) ^ (𝑥𝑦 < 0),
where the domain for both variables consists of all real
numbers.
Solution.
"For all real numbers 𝑥 and for all real numbers 𝑦, if 𝑥 is
positive, then 𝑥𝑦 is negative."
Let P(x,y) be the statement “𝑥 + 𝑦 = 𝑦 + 𝑥.”What are the truth values
of the quantifications ∀ 𝑥 ∀ 𝑦 𝑃 𝑥, 𝑦 and ∀ 𝑦 ∀ 𝑥 𝑃(𝑥, 𝑦) where the
domain for all variables consists of all real numbers?

Solution.
Given 𝑃(𝑥, 𝑦) is the statement “𝒙 + 𝒚 = 𝒚 + 𝒙.”
∀𝒙 ∀𝒚 𝑷 𝒙, 𝒚 reads as: "For all real numbers 𝑥 and for all real numbers 𝑦, 𝑥
+ 𝑦 = 𝑦 + 𝑥."
Since addition is commutative, 𝑥 + 𝑦 = 𝑦 + 𝑥 holds true for any pair of real
numbers 𝑥 and 𝑦.
Therefore, ∀ 𝑥 ∀ 𝑦 𝑃(𝑥, 𝑦) is true.
∀ 𝒚 ∀ 𝒙 𝑷 𝒙, 𝒚 reads as: "For all real numbers 𝑦 and for all real
numbers 𝑥, 𝑥 + 𝑦 = 𝑦 + 𝑥."
Since addition is commutative for real numbers, this statement
also holds true for any 𝑥 and 𝑦.
Thus, ∀ 𝑦 ∀ 𝑥 𝑃(𝑥, 𝑦) is also true.
 Translating Mathematical Statements into Statements
Involving Nested Quantifiers
Translate the statement “The sum of two positive integers is always
positive” into a logical expression.
Solution.
Rewrite: : “For every two integers, if these integers are both positive,
then the sum of these integers is positive.”
Introduce variable: Let 𝑥 and 𝑦 be variables. “For all positive integers
𝑥 and 𝑦, 𝑥 + 𝑦 is positive.”
Translation: ∀ 𝑥 ∀ 𝑦 ((𝑥 > 0) ∧ (𝑦 > 0) → (𝑥 + 𝑦 > 0)), where the
domain for both variables consists of all integers.
 Negating Nested Quantifiers
Given ∀ 𝑥 ∃ 𝑦 (𝑥𝑦 = 1). This reads as: "For every 𝑥, there
exists a y such that 𝑥𝑦 = 1.“
¬ ( ∀ 𝑥 ∃ 𝑦 (𝑥𝑦 = 1))
Apply the Negation Rules:
The negation of ∀𝒙 is ∃𝒙. The negation of ∃𝒚 is ∀𝒚.
So, we rewrite the negation as:
∃𝑥∀𝑦¬
(𝑥𝑦 = 1)
Use quantifiers to express the statement that "There does not exist a
woman who has taken a flight on every airline in the world".

Solution.
Let ‘𝑤′ represent woman and ‘a’ represent airline. Let 𝑃(𝑤, 𝑓) represent
“𝑤 has taken 𝑓” and 𝑄(𝑓, 𝑎) represent " 𝑓 is a flight on 𝑎.“
Statement: ¬ ∃ 𝑤 ∀ 𝑎 ∃ 𝑓 (𝑃(𝑤, 𝑓) ∧ 𝑄(𝑓, 𝑎))
By successively applying De Morgan’s laws for quantifiers,
∀𝑤¬∀𝑎∃𝑓 𝑃 𝑤, 𝑓 ∧ 𝑄 𝑓, 𝑎 ≡ ∀ 𝑤 ∃ 𝑎 ¬ ∃ 𝑓 𝑃 𝑤, 𝑓 ∧ 𝑄 𝑓, 𝑎

≡ ∀ 𝑤 ∃ 𝑎 ∀ 𝑓 ¬ 𝑃 𝑤, 𝑓 ∧ 𝑄 𝑓, 𝑎
≡ ∀ 𝑤 ∃ 𝑎 ∀ 𝑓 (¬𝑃(𝑤, 𝑓) ∨ ¬𝑄(𝑓, 𝑎)).
 RULES OF INFERENCE
• An argument is a sequence of propositions.
• The final proposition is called the conclusion of the argument
while the other propositions are called the premises or
hypotheses of the argument.
• An argument is valid whenever the truth of all its premises
implies the truth of its conclusion.
• Rules of inference are patterns of logically valid deductions
from hypotheses to conclusions.
• Proofs in mathematics are valid arguments that establish the
truth of mathematical statements.
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
“If 2> , then 2 > . We know that 2 > . Consequently,
2 2 2
2 3 2 9
2 =2> = .”
2 4
3 3 2
Solution. Let 𝑝: 2 > and 𝑞: 2 > .
2 2

Premises: 𝑝 → 𝑞, 𝑝
Conclusion: 𝑞
The argument is valid by the rule Modus ponens.
3
But 2 > is false. Consequently, we cannot conclude that the
2

conclusion is true. Furthermore, note that the conclusion of this

9
argument is false, because 2 < .
4
State which rule of inference is the basis of the following
argument: “It is below freezing now. Therefore, it is
either below freezing or raining now.”
Solution.
Let p: “It is below freezing now.”
q: “It is raining now.”
Then this argument is of the form
𝑝
∴𝑝∨𝑞
This argument uses the addition rule.
State which rule of inference is the basis of the following
argument: “It is below freezing and raining now.
Therefore, it is below freezing now.”
Solution.
Let p: “It is below freezing now.”
q: “It is raining now.”
Then this argument is of the form
𝑝∧𝑞
∴𝑝
This argument uses the simplification rule.
Show that the premises “A student in this class has not read the
book,” and “Everyone in this class passed the first exam” imply the
conclusion “Someone who passed the first exam has not read the
book.”
Solution.
Let 𝑝: It is sunny this afternoon.
𝑞: It is colder in the dark.
𝑟: We will go swimming.
𝑠: We will take a canoe trip.
𝑡: We will be home by sunset.
Premises: ¬𝑝 ∧ 𝑞, 𝑟 → 𝑝, ¬𝑟 → 𝑠, and 𝑠 → 𝑡
Conclusion: 𝑡
STEPS REASON

¬𝑝 ∧ 𝑞 Premise

¬𝑝 Simplification using (1)

𝑟→𝑝 Premise

¬𝑟 Modus tollens using (2) and (3)

¬𝑟 → 𝑠 Premise

𝑠 Modus ponens using (4) and (5)

𝑠→𝑡 Premise

𝑡 Modus ponens using (6) and (7)

 RESOLUTION
• Computer programs have been developed to
automate the task of reasoning and proving
theorems.
• Many of these programs make use of a rule of
inference known as resolution.
• This rule of inference is based on the tautology
((𝒑 ∨ 𝒒) ∧ (¬ 𝒑 ∨ 𝒓)) → (𝒒 ∨ 𝒓).
• The final disjunction in the resolution rule, 𝒒 ∨ 𝒓,
is called the resolvent.
 FALLACIES
• A fallacy is an inference rule or other proof method
that is not logically valid.
• Fallacy of affirming the conclusion:
“𝑝→𝑞 is true, and q is true, so p must be true.”
(No, because F→T is true.)
• Fallacy of denying the hypothesis:
“𝑝→𝑞 is true, and p is false, so q must be false.”
(No, again because F→T is true.)
Show that the premises “It is not sunny this afternoon and it is
colder than yesterday,” “We will go swimming only if it is sunny,”
“If we do not go swimming, then we will take a canoe trip,” and
“If we take a canoe trip, then we will be home by sunset” lead to
the conclusion “We will be home by sunset.”
Solution.
Let 𝐶 𝑥 be “x is in this class.”
B(x) be “x has read the book,”
𝑃(𝑥) be “x passed the first exam”.
Premises: ∃𝑥(𝐶(𝑥) ∧ ¬𝐵(𝑥)) and ∀𝑥(𝐶(𝑥) → 𝑃(𝑥))
Conclusion: ∃𝑥(𝑃(𝑥) ∧ ¬𝐵(𝑥))
 STEPS REASON
∃𝑥(𝐶(𝑥) ∧ ¬𝐵(𝑥)) Premise
𝐶(𝑎) ∧ ¬𝐵(𝑎) Existential instantiation from (1)

𝐶(𝑎) Simplification from (2)

∀𝑥(𝐶(𝑥) → 𝑃(𝑥)) Premise

𝐶(𝑎) → 𝑃(𝑎) Universal instantiation from (4)

𝑃(𝑎) Modus ponens from (3) and (5)

¬𝐵(𝑎) Simplification from (2)

𝑃(𝑎) ∧ ¬𝐵(𝑎) Conjunction from (6) and (7)

∃𝑥(𝑃(𝑥) ∧ ¬𝐵(𝑥)) Existential generalization from (8)

 Terminology
• Theorem – statement that can be shown to be true.
• Axioms or postulates – statements which are given and assumed to be true.
• Proof – sequence of statements, a valid argument, to show that a theorem is
true.
• Rules of Inference – rules used in a proof to draw conclusions from assertions
known to be true.
Note:
• Lemma is a “pre-theorem” or a result that needs to be proved to prove the
theorem.
• A corollary is a “post-theorem”, a result which follows directly the theorem
that has been proved.
• Conjecture is a statement believed to be true but for which there is no proof.
 Methods of Proof
• Direct Proof
• Proof by Contraposition
• Proof by Contradiction
• Proof of Equivalences
• Proof by Cases
• Existence Proofs
• Uniqueness
 DIRECT PROOF
• A direct proof shows that a conditional statement 𝑝 →
𝑞 is true by showing that if p is true, then q must also
be true, so that the combination p true and q false
never occurs.
• In a direct proof, we assume that p is true and use
axioms, definitions, and previously proven theorems,
together with rules of inference, to show that q must
also be true.
Give a direct proof of the theorem “If 𝑛 is an odd integer, then 𝑛2 is
odd.”
Proof.
Assume that the hypothesis of this conditional statement is true,
namely, we assume that n is odd.
By the definition of an odd integer, 𝒏 = 𝟐𝒌 + 𝟏, where 𝑘 is some
integer.
Squaring on both sides, we get
𝒏𝟐 = 2𝑘 + 1 2
= 4𝑘 2 + 4𝑘 + 1 = 𝟐(𝟐𝒌𝟐 + 𝟐𝒌) + 𝟏.
By the definition of an odd integer, we can conclude that 𝑛2 is an
odd integer.
Give a direct proof that if 𝑚 and 𝑛 are both perfect squares, then
𝑛𝑚 is also a perfect square.

Proof.
Assume that the hypothesis of this conditional statement is true,
namely, we assume that m and n are both perfect squares.
By the definition of perfect square, it follows that there are
integers 𝑠 and 𝑡 such that 𝒎 = 𝒔𝟐 and 𝒏 = 𝒕𝟐 .
Hence 𝒎𝒏 = 𝑠 2 𝑡 2 = (𝑠𝑠)(𝑡𝑡) = (𝑠𝑡)(𝑠𝑡) = 𝒔𝒕 𝟐 , using
commutativity and associativity of multiplication.
By the definition of perfect square, it follows that 𝑚𝑛 is also a
perfect square, because it is the square of 𝑠𝑡, which is an integer.
 PROOF BY CONTRAPOSITION
• Proofs that are not direct proofs, that do not start with the
premises and end with the conclusion, are called indirect proofs.
• An extremely useful type of indirect proof is known as proof by
contraposition.
• Proofs by contraposition make use of the fact that the conditional
statement 𝑝 → 𝑞 is equivalent to its contrapositive, ¬𝑞 → ¬𝑝.
• This means that the conditional statement 𝑝 → 𝑞 can be proved
by showing that its contrapositive, ¬𝑞 → ¬𝑝, is true.
• In a proof by contraposition of 𝑝 → 𝑞, we take ¬𝑞 as a premise,
and using axioms, definitions, and previously proven theorems,
together with rules of inference, we show that ¬𝑝 must follow.
Prove that if 𝑛 is an integer and 3𝑛 + 2 is odd, then 𝑛 is odd.
Direct Proof
Assume 3𝑛 + 2 is an odd integer. i.e. 3𝑛 + 2 = 2𝑘 + 1, for some
integer 𝑘.
This implies 3𝑛 + 1 = 2𝑘, but there does not seem to be any direct way
to conclude that 𝑛 is odd.
Proof by contraposition
Assume that the conclusion of the conditional statement is false; namely,
assume that 𝑛 is even. Then 𝑛 = 2𝑘 for some integer 𝑘. Substituting we
get
3𝑛 + 2 = 3(2𝑘) + 2 = 6𝑘 + 2 = 2 3𝑘 + 1 which is even.
Because the negation of the conclusion of the conditional statement
implies that the hypothesis is false, the original conditional statement is
true.
Prove that if 𝑛 is an integer and 𝑛2 is odd, then 𝑛 is odd.

Direct Proof
Suppose that 𝑛 is an integer and 𝑛2 is odd. Then, there exists an integer 𝑘
such that 𝑛2 = 2𝑘 + 1. There is no obvious approach to show that 𝑛 is
odd because solving for 𝑛 produces the equation 𝑛 = ±√2𝑘 + 1.

Proof by contraposition
Assume that the hypothesis of the statement is false; namely, assume that
𝑛 is even. Then 𝑛 = 2𝑘 for some integer 𝑘. Squaring on both sides, we
obtain
𝑛2 = 4𝑘 2 = 2(2𝑘 2 ) which is even.
Because the negation of the hypothesis statement implies that the
conclusion is false, the original conditional statement is true.
 PROOF BY CONTRADICTION
• Suppose we want to prove that a statement 𝑝 is true.
Furthermore, suppose that we can find a contradiction 𝑞
such that ¬𝑝 → 𝑞 is true.
• Because 𝑞 is false, but ¬𝑝 → 𝑞 is true, we can conclude
that ¬𝑝 is false, which means that 𝑝 is true.
• Because the statement 𝑟 ∧ ¬𝑟 is a contradiction whenever
𝑟 is a proposition, we can prove that 𝑝 is true if we can
show that ¬𝑝 → 𝑟 ∧ ¬𝑟 is true for some proposition 𝑟.
• Proofs of this type are called proofs by contradiction. It is
another type of indirect proof.
Prove that √2 is irrational by giving a proof by contradiction.
Proof.
Let 𝑝 be the proposition “√2 is irrational.” Suppose that ¬𝑝 is true.
¬𝑝 : “It is not the case that √2 is irrational,” which says that √2 is
rational.
If √2 is rational, there exist integers 𝑎 and 𝑏 with √2 = 𝑎/𝑏, where
𝑏 = 0 and 𝑎 and 𝑏 have no common factors.
𝑎2
Squaring on both sides of the equation, 2 = .
𝑏2

Hence 2𝑏 2 = 𝑎2 .
By the definition of an even integer it follows that 𝑎2 is even.
Furthermore, since 𝑎 is even, 𝑎 = 2𝑐 for some integer 𝑐. Thus,
2𝑏 2 = 4𝑐 2 .
Dividing both sides of this equation by 2 gives 𝑏 2 = 2𝑐 2 . By the
definition of even, this means that 𝑏 2 is even which implies 𝑏 is even.
Thus, If √2 is rational, there exist integers 𝑎 and 𝑏 with √2 = 𝑎/𝑏,
where 𝑏 = 0 and a and 𝑏 have no common factors, but 𝑎 and 𝑏 are
even.
i.e. 2 divides a and b.
This is a contradiction to our assumption that 𝑎 and 𝑏 have no
common factors.
Then ¬𝑝 must be false. That is, the statement 𝑝,“√2 is irrational,” is
true.
Give a proof by contradiction of the theorem “If 3𝑛 + 2 is odd, then
𝑛 is odd.”
Proof. Let 𝑝 be “3𝑛 + 2 is odd” and 𝑞 be “𝑛 is odd.”
Assume that both 𝑝 and ¬𝑞 are true. That is, 3𝑛 + 2 is odd and 𝑛 is
not odd.
𝑛 is not odd implies that it is even. Then there is an integer 𝑘 such
that 𝑛 = 2𝑘.
This implies that 3𝑛 + 2 = 3(2𝑘) + 2 = 6𝑘 + 2 = 2(3𝑘 + 1).
Then 3𝑛 + 2 is even. The statement “3𝑛 + 2 is even” is equivalent
to the statement ¬𝑝, because an integer is even if and only if it is not
odd.
Because both 𝑝 and ¬𝑝 are true, we have a contradiction.
Thus, if 3𝑛 + 2 is odd, then 𝑛 is odd.
 PROOF BY CASES
To prove
𝑝1 ∨ 𝑝2 ∨ ⋯ ∨ 𝑝𝑛 → 𝑞
we need to prove
𝑝1 → 𝑞 ∧ 𝑝2 → 𝑞 ∧ ⋯ ∧ 𝑝𝑛 → 𝑞

Problem. Use a proof by cases to show that |𝑥𝑦| = |𝑥||𝑦|, where 𝑥

and 𝑦 are real numbers.
Solution: We know that, |𝑎| = 𝑎 when 𝑎 ≥ 0 and |𝑎| = −𝑎 when
𝑎 < 0.
Thus, we need four cases:
(i) 𝑥 and 𝑦 both nonnegative,
(ii)𝑥 nonnegative and 𝑦 is negative,
(iii)𝑥 negative and 𝑦 nonnegative, and
(iv) 𝑥 negative and 𝑦 negative.
We denote by 𝑝1 , 𝑝2 , 𝑝3 , and 𝑝4 , the proposition stating the
assumption for each of these four cases, respectively.
Case (i): 𝑝1 → 𝑞. If 𝑥 ≥ 0 and 𝑦 ≥ 0, then 𝑥𝑦 ≥ 0, and
|𝑥𝑦| = 𝑥𝑦 = |𝑥||𝑦|.
Case (ii): 𝑝2 → 𝑞. If 𝑥 ≥ 0 and 𝑦 < 0, then 𝑥𝑦 ≤ 0, and
𝑥𝑦 = −𝑥𝑦 = (𝑥)(−𝑦) = |𝑥||𝑦|.
Case (iii): 𝑝3 → 𝑞. If 𝑦 ≥ 0 and 𝑥 < 0, then 𝑥𝑦 ≤ 0, and
𝑥𝑦 = −𝑥𝑦 = (−𝑥)(𝑦) = |𝑥||𝑦|.
Case (iv): 𝑝4 → 𝑞. If 𝑥 < 0 and 𝑦 < 0, then 𝑥𝑦 < 0, and
|𝑥𝑦| = 𝑥𝑦 = (−𝑥)(−𝑦) = |𝑥||𝑦|.
Because |𝑥𝑦| = |𝑥||𝑦| holds in each of the four cases and these cases
exhaust all possibilities, we can conclude that |𝑥𝑦| = |𝑥||𝑦| ,
whenever 𝑥 and 𝑦 are real numbers.
 EXISTENCE PROOFS

A proof of a statement of the form 𝑥 𝑃(𝑥) is called

an existence proof.
If the proof demonstrates how to actually find or
construct a specific element 𝑎 such that 𝑃(𝑎) is true,
then it is called a constructive proof.
Otherwise, it is called a non-constructive proof.
Constructive Existence Proof
Show that there is a positive integer that can be written as
the sum of cubes of positive integers in two different ways.
Proof. To show that there exists a '𝑛' such that 𝑛 = 𝑗 3
+ 𝑘3 and 𝑛 = 𝑙 3 + 𝑚3 where 𝑗, 𝑘, 𝑙, 𝑚 are positive
integers, and {𝑗, 𝑘} ≠ {𝑙, 𝑚}.
Let 𝑛 = 1729, 𝑗 = 9, 𝑘 = 10, 𝑙 = 1, 𝑚 = 12.
Then 1729 = 93 + 103 and 1729 = 13 + 123 .
Therefore, there is a positive integer that can be written as
the sum of cubes of positive integers in two different ways.
Nonconstructive Existence Proof
Show that there exist irrational numbers 𝑥 and 𝑦 such that 𝑥 𝑦
is rational.
2
Proof. We know that, √2 is irrational. Consider the number 2 .

If it is rational, we have two irrational numbers 𝑥 and 𝑦 with 𝑥 𝑦

rational, namely, 𝑥 = √2 and 𝑦 = √2.
2 2
If 2 is irrational, then we can let 𝑥 = 2 and 𝑦 = 2 so that

2
2 ( 2. 2) 2
𝑥𝑦 = 2 = 2 = 2 = 2.

This proof is an example of a nonconstructive existence proof

because we have not found irrational numbers 𝑥 and 𝑦 such that 𝑥 𝑦
is rational.
 UNIQUENESS PROOFS
Some theorems assert the existence of a unique element with a
particular property. In other words, these theorems assert that
there is exactly one element with this property. To prove a
statement of this type we need to show that an element with this
property exists and that no other element has this property.
The two parts of a uniqueness proof are:
• Existence: We show that an element 𝑥 with the desired property
exists.
• Uniqueness: We show that if 𝑦 = 𝑥, then y does not have the
desired property.
• Equivalently, we can show that if 𝑥 and 𝑦 both have the desired
property, then 𝑥 = 𝑦.
Show that if a and b are real numbers and 𝑎 = 0, then there is a
unique real number 𝑟 such that 𝑎𝑟 + 𝑏 = 0.
Proof.
Existence: First, note that the real number 𝑟 = −𝑏/𝑎 is a solution of
𝑎𝑟 + 𝑏 = 0 because 𝑎(−𝑏/𝑎) + 𝑏 = −𝑏 + 𝑏 = 0.
Consequently, a real number 𝑟 exists for which 𝑎𝑟 + 𝑏 = 0.
Uniqueness: Suppose that s is also a real number such that 𝑎𝑠 + 𝑏 =
0.
Then 𝑎𝑟 + 𝑏 = 𝑎𝑠 + 𝑏, where 𝑟 = −𝑏/𝑎.
Subtracting 𝑏 from both sides, we get 𝑎𝑟 = 𝑎𝑠.
Dividing by 𝑎 ≠ 0, we obtain 𝑟 = 𝑠.
This means that if 𝑠 ≠ 𝑟, then 𝑎𝑠 + 𝑏 ≠ 0.
 MISTAKES IN PROOFS

• There are many common errors made in constructing

mathematical proofs.
• Among the most common errors are mistakes in arithmetic
and basic algebra.
• Each step of a mathematical proof needs to be correct and
the conclusion needs to follow logically from the steps that
precede it.
• Many mistakes result from the introduction of steps that do
not logically follow from those that precede it.
What is wrong with this “proof?”
If 𝑥 is a real number, then 𝑥 2 is a positive real number.
“Proof:” Let 𝑝1 be “𝑥 is positive,” let 𝑝2 be “𝑥 is negative,”
and let 𝑞 be “𝑥 2 is positive.” To show that 𝑝1 → 𝑞 is true,
note that when 𝑥 is positive, 𝑥 2 is positive because it is the
product of two positive numbers, 𝑥 and 𝑥. To show that 𝑝2
→ 𝑞, note that when 𝑥 is negative, 𝑥 2 is positive because it
is the product of two negative numbers, 𝑥 and 𝑥. This
completes the proof.
Solution. The problem with this “proof” is that we missed
the case of 𝑥 = 0.
When 𝑥 = 0, 𝑥 2 = 0 is not positive, so the supposed
theorem is false.
If 𝑝 is “𝑥 is a real number,” then we can prove results
where 𝑝 is the hypothesis with three cases, 𝑝1 , 𝑝2 , and
𝑝3 , where 𝑝1 is “𝑥 is positive,” 𝑝2 is “𝑥 is negative,” and
𝑝3 is “𝑥 = 0” because of the equivalence 𝑝 ↔ 𝑝1 ∨ 𝑝2 ∨
𝑝3 .