Chapter 1

Modified: 
© Ray Wisman
Resources
http://highered.mcgrawhill.com/sites/0072880082/student_view0/index.html  Rosen text Web site learning resources, requires registration.
http://highered.mcgrawhill.com/classware/selfstudy.do?isbn=0072880082  Extra examples with solutions, selfassessments, interactive problems and other supplementary material.
1.1 Propositional Logic
Propositions  A declarative sentence (declares a fact) that is either True or False.
Examples of propositions
 This course is C251, Ballroom Dancing.
 I paid my taxes by sending a check for $30,000.
Examples that are not propositions
 What is your name? Not declarative.
 I paid my taxes by sending a check for x + 1 dollars. Neither True nor False, x is undefined.
Question 1  Which are propositions?
The sky is blue.
2 + 2 = 3.
No smoking.
 Where am I?
Variables
Use letters such as p, q, r, ... to represent propositions.
Example
p is "I paid my taxes"
q is "I am now broke"
Truth value
T denotes True propositions
F denotes False propositions
Example
p is "I paid my taxes"
p = T
"I paid my taxes" is True
p = F
"I paid my taxes" is False
Definition 1
Negation of p, denoted by ¬p
¬p is the opposite truth values of p
Example
p is "My name is Ray Wisman"
which is True.
¬p is "My name is not Ray Wisman"
which is False.
Question 2  What is the negation of the following propositions?
Today is Monday.
 2 + 2 < 3
 I did not win the lottery.
Definition 2 p ^ q
Conjunction of p and q denoted by p ^ q
p ^ q is True
when both p and q are True
Example
p is "Today is Tuesday" q is "I am in the Ball Room dancing class"
 Express p ^ q in English.
"Today is Tuesday" and "I am in the Ball Room dancing class"
 Which row of the truth table matches the p and q values right now?
p q p ^ q
T F F
 What is the truth value of p ^ q?
F
Question 3:
p is “It is hot outside” q is “It is snowing
 Express p ^ q in English.
 Which row of the truth table matches the p and q values at this moment in time?
 What is the truth value at this moment in time of p ^ q?
Definition 3 p v q
Disjunction of p and q, denoted by p v q
p v q is True
when either p or q are True
Example
p is "Today is Tuesday" q is "I am in the Ball Room dancing class"
 Express p v q in English.
"Today is Tuesday" or "I am in the Ball Room dancing class"
 Which row of the truth table matches the p and q values right now?
p q p v q
T F T
 What is the truth value of p v q?
T
Question 4
p is “It is below freezing” q is “Today is Monday"
 p v q as English sentence.
Which row of the truth table matches the p and q values at this moment in time?
p v q truth value?
Definition 4 p ⊕ q
Exclusive or of p and q, denoted by p ⊕ q
p ⊕ q is True
when only one of p or q are True
Also known as the difference operator.
Definition 5 p → q
Conditional of p and q, denoted by p → q
is the proposition "if p, then q".
p → q is False only
when p is True and q is False.
Example
p is "Today is Tuesday" q is "I am in the Ball Room Dancing class"
 p → q in English?
If "Today is Tuesday" then "I am in the Ball Room Dancing class"
 Which row of the truth table matches the p and q values at this moment in time?
p q p → q
T F F
 p → q truth value?
F
Question 5.1
p is “I win a million dollars” q is “I give you a million dollars"
 p → q as English sentence.
 Which row of the truth table matches the p and q values at this moment in time?
 p → q truth value?
p q p → q T T T T F F F T T F F T Example
p is "I win a million dollars" q is "I give you a million dollars"
p → q is "If I win a million dollars then I give you a million dollars".
p → q is True when "I win a million dollars" is True and "I give you a million dollars" is True.
p → q is False when "I win a million dollars" is True and "I give you a million dollars" is False.
p → q is True when "I win a million dollars" is False and "I give you a million dollars" is True.
p → q is True when "I win a million dollars" is False and "I give you a million dollars" is False.
p
I win a million dollarsq
I give you a million dollarsp → q
If I win a million dollars then
I give you a million dollarsT T T T F F F T T F F T
Examplep is "I am in C251" q is "2 + 2 = 5"
p → q is True in every class except C251 even though q is False.
Check the p → q definition truth table.
p
I am in C251q
2+2=5p → q
If I am in C251 then
2+2=5T
I am in C251T
2 + 2 = 5T T
I am in C251F
2 + 2 = 5F F
I am in C251T
2 + 2 = 5T F
I am in C251F
2 + 2 = 5T
Question 5.2  Conditional p → q
p is “It is Sunday" q is “I eat grass hoppers for lunch”
 Express as English sentence.
 What is the truth value right now?
p q p → q T T T T F F F T T F F T
CONVERSE, CONTRAPOSITIVE, INVERSE
Conditional Converse Contrapositive Inverse p → q q → p ¬q → ¬p ¬p → ¬q Example
p is "I am in C251" = T q is "It is Monday" = T
p → q "I am in C251" → "It is Monday"
T → T = TIf I am in C251 then it is Monday q → p "It is Monday" → "I am in C251"
T → T = TIf it is Monday then I am in C251 ¬q → ¬p "It is NOT Monday" → "I am NOT in C251"
F → F = TIf it is NOT Monday then I am NOT in C251 ¬p → ¬q "I am NOT in C251" → "It is NOT Monday"
F → F = TIf I am NOT in C251 then it is NOT Monday
p q p → q q → p F F T T F T T F T F F T T T T T
Question 6  Converse q
→
p

Question 7  Contrapositive ¬q
→
¬p

Question 8  Inverse
¬p
→
¬q

Question 9  Complete the truth table
p q ¬p ¬q p → q q → p ¬p → ¬q ¬q → ¬p F F F T T F T T
p q p → q T T T T F F F T T F F T
Definition 6 p ↔ q
Biconditional of p and q, denoted by p ↔ q,
is the proposition "p, if and only if q".
p ↔ q is True
when p and q are same truth values.
Also known as the equivalence operator.
Example
p is "I win a million dollars" q is "I give you a million dollars"
p ↔ q is "I give you a million dollars, if and only if I win a million dollars".
p ↔ q is True when "I win a million dollars" and "I give you a million dollars".
p ↔ q is False when "I win a million dollars" and "I do not give you a million dollars".
p ↔ q is False when "I do not win a million dollars" and "I give you a million dollars".
p ↔ q is True when "I do not win a million dollars" and "I do not give you a million dollars".
p
I win a million dollarsq
I give you a million dollarsp ↔ q
I win a million dollars
if and only if
I give you a million dollarsT
I win a million dollarsT
I give you a million dollarsT T
I win a million dollarsF
I give you a million dollarsF F
I win a million dollarsT
I give you a million dollarsF F
I win a million dollarsF
I give you a million dollarsT
Truth Tables of Compound Propositions
Example
p q p v q p → q (p → q) ^ (p v q) F F F T F F T T T T T F T F F T T T T T Question 10  Complete the truth table for (p → q) ^ ¬p
p q ¬p p → q (p → q) ^ ¬p F F F T T F T T Question 11  Create a truth table similar to Question 10 for (p → q) v ¬(p ^ q)
p q ¬p p → q p ^ q p v q F F T T F F F T T T F T T F F F F T T T F T T T
Precedence of Operators ¬ is highest
Example
¬p → q ↔ p ^ q v r = [((¬p) → q) ↔ ((p ^ q) v r)]
Example (left associative)
p ^ q v ¬p = ((p ^ q) v (¬p))
Question 12  Parenthesize corresponding to logical operator precedence:
p ^ ¬q v p ↔ q → r ^ p
Application of logic
System Specifications
Definition
Consistent when specifications do not contain conflicts that could lead to contradictions. Example 1
Are the following statements consistent? That is, are all True at the same time?
"It snowed or I went to school"
"It did not snow"
"If snowed, then I went to school"
Represent as logic
p is "It snowed"
q is "I went to school"
p v q "It snowed or I went to school"
¬p "It did not snow"
p → q "If snowed, then I went to school"
Question 13.1
Complete the following truth table.
The three specifications are consistent when all are True.
p q p V q ¬p p → q F F F T T F T T
Logic Puzzles
Example
Truths
"Knights always tell the truth" is true
"Knaves always lie" is true
Propositions
A says "B is a knight."
B says "The two of us are always opposites." (i.e. If one is a knight then the other is a knave)
Prove
Determine what A and B are, either a knight or a knave.
Proof
p is "A is a knight" q is "B is a knight"
¬p is "A is a knave" ¬q is "B is a knave"
From the statements made by A and B:
p → q "If A is a knight, then B is a knight"
since knights tell the truth, A says "B is a knight."
q → ¬p "If B is a knight, then A is a knave"
since knights tell the truth, B says "The two of us are always opposites."
¬p → ¬q "If A is not a knight, then B is not a knight"
since knaves lie, A says "B is a knight" is a lie. This is the inverse of: p → q
The implications are based on "Knights always tell the truth" and "Knaves always lie", statements assumed True.
So the implications must all be True, that is consistent.
Question 13.2 Complete the following truth table to determine what A and B are:
p q ¬p ¬q p → q q → ¬p ¬p → ¬q F F T T F T T F T F F T T T F F p is "A is a knight" q is "B is a knight"
p q p → q T T T T F F F T T F F T
Logic and Bit Operations
Definition 7
Bit string is a sequence of zero or more bits. Example
0100 0001
is the 8bit ASCII code representation for the letter 'A'
1111
is the 4bit 2's complement representation for 1
1000 0000 0000 0000
is 16bit binary value corresponding to 32768_{10}
Truth Value Bit T 1 F 0
Definition
Bit operations extend bit operations to bit strings. Example
AND OR XOR 1101
^ 0100
01001101
v 0100
11011101
⊕ 0100
1001
⊕ 0100
1101Note that XOR is its own inverse, particularly useful in computer graphics.
Question 14  Find the bitwise OR, AND and XOR of:
1001 1001 1001
^ 1110 v 1110 ⊕ 1110
1.2 Propositional Equivalences
Important in simplifying mathematical arguments to replace statements with those of equivalent truth value.
Definition 1
Tautology is a compound proposition that is always True.
Contradiction
is a compound proposition that is always False.
Logical Equivalences
Definition 2
Logically equivalent statements if p ↔ q is a tautology. Denoted by p Ξ q.
Example  Proof that one of De Morgan's Laws is logically equivalent
¬(p ^ q) Ξ ¬p v ¬q
p q p ^ q ¬(p ^ q) ¬p ¬q ¬p v ¬q F F F T T T T F T F T T F T T F F T F T T T T T F F F F Question 14  Prove that one of De Morgan's Laws is logically equivalent by completing the table
¬(p v q) Ξ ¬p ^ ¬q
p q p v q ¬(p v q) ¬p ¬q ¬p ^ ¬q F F F T T F T T
Using De Morgan's Laws
Example
p is "Miguel has a cell phone." q is "Miguel has a laptop computer."
p ^ q is "Miguel has a cell phone." and "Miguel has a laptop computer."
¬(p ^ q) is "Miguel does not have a cell phone and a laptop computer."
¬p v ¬q is "Miguel does not have a cell phone or Miguel does not have a laptop computer."
¬(p ^ q) ≡ ¬p v ¬q
Constructing New Logical Equivalences
Can use truth tables to prove that compound statements are equivalent.
Can also use previously established equivalencies.
Example
Prove: ¬(p → q) Ξ p ^ ¬q
¬(p → q) Ξ ¬(¬p v q)
1. By Table 4: p → q Ξ ¬p v q
¬(¬p v q) Ξ ¬(¬p) ^ ¬q 2. By Table 2.
¬(¬p) ^ ¬q Ξ p ^ ¬q 3. ¬(¬p) Ξ p by double negation law.
1.3 Predicates and Quantifiers
Propositional logic cannot adequately express all mathematics and natural language statements.
Example
"2 > 3" is valid proposition.
"x > 3" is not valid proposition, x is undefined.
Predicates
Example
"x > 3" has two parts
 variable "x"
 P( x ), the propositional function " > 3 ", P at x
P(4) is True "4 > 3"
P(2) is False "2 > 3"
Question 15
P(x) is x ≤ 4.
Truth values of:
 P(0)
 P(4)
 P(6)
Example
Q(x, y) denotes "x = y + 3"
Q(4, 1) is True "4 = 1 + 3"
Q(1, 4) is False "1 = 4 + 3"
Question 16
P(x, y) is x ≤ y.
Truth values of:
 P(0, 4)
 P(4, 4)
 P(6, 3)
Quantifiers
Definition 1
Universal quantification of P( x ) is the statement: "P( x ) for all values of x in the domain."
∀x P( x )
denotes universal quantification of P( x )
Example
P(x) is "x > x  1"
P(2) is "2 > 2  1"
For domain of P(x) = { 0, 1, 2 }
x ∈ { 0, 1, 2 }
P(0) is "0 > 0  1"
P(1) is "1 > 1  1"
P(2) is "2 > 2  1"
∀x P(x) is True
Example  Another way of thinking of universal quantification
P(x) is "x > x  1"
P(2) is "2 > 2  1"
Show conjunction P(x) is True for all x ∈ { 0, 1, 2 }
P(0) ^ P(1) ^ P(2)
P(x) is "x > x = 1"
P(0) is True "0 > 0  1"
P(1) is True "1 > 1  1"
P(2) is True "2 > 2  1"
P(0) ^ P(1) ^ P(2) = (True ^ True ^ True) which is True
∀x P(x) is True
Example
P(x) is "x * x > x"
The domain of P(x) is {2, 1, 0}
x ∈ {2, 1, 0}
Show conjunction P(x) is True for all x ∈ {2, 1, 0}:
P(2) ^ P(1) ^ P(0)
P(x) is "x * x > x"
P(2) is True "4 > 2"
P(1) is True "1 > 1"
P(0) is False "0 > 0"
P(2) ^ P(1) ^ P(0) = (True ^ True ^ False) which is False
∀x P(x) is False
when one or more P(x) is False.
Question 17.1  True or False
P(x) is "x + 4 < 3"
Q(x) is "x < 4"
The domain of P(x) and Q(x) is {2, 0, 2}
x ∈ {2, 0, 2}
 ∀x P(x)
 ∀x Q(x)
Example ∀x ( P(x) v Q(x) )
P(x) is "x < 0"
Q(x) is "x < 2"
The domain P(x) v Q(x) is {2, 0, 2}
x ∈ {2, 0, 2}
Show P(x) v Q(x) all x ∈ {2, 0, 2}:
( P(2) v Q(2) ) ^ ( P(0) v Q(0) ) ^ ( P(2) v Q(2) )
( P(x) v Q(x) ) is "x < 0 v x < 2"
( P(2) v Q(2) ) is True "2 < 0 v 2 < 2"
( P(0) v Q(0) ) is True "0 < 0 v 0 < 2"
( P(2) v Q(2) ) is False "2 < 0 v 2 < 2"
( P(2) v Q(2) ) ^ ( P(0) v Q(0) ) ^ ( P(2) v Q(2) ) = (True ^ True ^ False) which is False
∀x ( P(x) v Q(x) ) is False
when one or more ( P(x) v Q(x) ) is False.
Question 17.2  True or False P(x) is "x + 4 < 3"
Q(x) is "x < 4"
The domain of P(x) and Q(x) is {2, 0}
x ∈ { 2, 0 }
 ∀x ( P(x) ^ Q(x) )
 ∀x ( P(x) → Q(x) )
p q p ^ q p → q F F F T F T F T T F F F T T T T Question 18  C(x) is “x is a comedian”
F(x) is “x is funny”
x ∈ { Curly, Larry, Moe }
∀x ( C(x) ^ F(x) ) in English:
"For all x, x is a comedian and x is funny"
Translate to English:
 ∀x ( C(x) → F(x) )
 ∀x (¬F(x) → ¬C(x) )
Definition 2
Existential quantification of P(x) is the statement: "There exists an element x in the domain such that P(x) is True."
∃x P(x)
denotes existential quantification of P(x)
Example
∃x P(x) is True
when at least one P(x) is True
P(x) is "x * x > x"
The domain of P(x) is {2, 1, 0}
x ∈ {2, 1, 0}
Show disjunction P(x) is True for at least one x ∈ {2, 1, 0}:
P(2) v P(1) v P(0)
P(x) is "x * x > x"
P(2) is True "4 > 2"
P(1) is True "1 > 1"
P(0) is False "0 > 0"
P(2) v P(1) v P(0) = (True v True v False) which is True
∃x P(x) is True
when at least one P(x) is True
Example
P(x) is "x  1 > x"
The domain of P(x) is {2, 1, 0}
x ∈ {2, 1, 0}
P(x) is "x  1 > x"
P(2) is False "3 > 2"
P(1) is False "2 > 1"
P(0) is False "1 > 0"
P(2) v P(1) v P(0) = (False v False v False) which is False
∃x P(x) is False
when all P(x) are False
Question 19  True or False P(x) is "x + 4 < 3"
Q(x) is "x < 1"
The domain of P(x) and Q(x) is { 2, 0 }
x ∈ { 2, 0 }
 ∃x P( x )
 ∃x Q( x )
 ∃x( P( x ) ^ Q( x ) )
 ∃x( P( x ) → Q( x ) )
p q p ^ q p → q F F F T F T F T T F F F T T T T Question 20.1  C(x) is “x is a comedian”
F(x) is “x is funny”
x ∈ { Curly, Larry, Moe }
∃x ( C(x) ^ F(x) ) in English:
"There exists an x such that x is a comedian and x is funny"
Translate to English:
 ∃x ( C(x) → F(x) )
 ∃x (¬F(x) → ¬C(x) )
Quantifiers with Restricted Domains
∀x < 0 (x^{2} > 0)
For all real numbers x < 0 such that x^{2} > 0
which is True.
Question 20.2
 ∃x < 0 (x^{2} > x) says what in English?
 Is it True?
Precedence of Quantifiers
∃ and ∀ are higher than all operators.
Example
∃x P(x) ^ Q(x)
means (∃x P(x) ) ^ Q(x)
not ∃x ( P(x) ^ Q(x) )
need parenthesis.
Binding Variables
All variables used in a propositional function must be quantified (e.g. ∃x or ∀x) or set equal to some value.
Example
∃x (x + y = 1) has y free so is meaningless.
∃x ∃y (x + y = 1) has x and y bound so has meaning.
x ∈ {2, 0}
y ∈ {0, 3}
True for x = 2, y = 3
Logical Equivalences Involving Quantifiers
Definition 3
Logically equivalent statements involving predicates and quantifiers, if and only if have 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.
S Ξ T denotes S is logically equivalent to T.
Example
Prove that ∀ distributes over ^
∀x ( P(x) ^ Q(x)) Ξ ∀x P(x) ^ ∀x Q(x)
Logically equivalent must show each statement always has same truth value.
Show two conditionals:
If ∀x ( P(x) ^ Q(x) ) is True then ∀x P(x) ^ ∀x Q(x) is True 
If ∀x P(x) ^ ∀x Q(x) is True then ∀x ( P(x) ^ Q(x) ) is True 



∴ ∀x ( P(x) ^ Q(x)) Ξ ∀x P(x) ^ ∀x Q(x)
Note that because using predicates and not restricting x to specific domain, have infinite number of possible x's, cannot use truth table for proof.
Negating Quantified Expressions
¬∀x P( x ) Ξ ∃x ¬P( x )
¬∃x Q( x ) Ξ ∀x ¬Q( x )
Example
"Everyone in C251 has a cell phone."
P is "has a cell phone"
x is in domain "C251".
P(x) is x in domain "C251 has a cell phone".
∀x P(x) is "Everyone in C251 has a cell phone."
¬∀x P(x) Ξ ∃x ¬P(x)
the negation would be:
¬∀x P(x) "Not everyone in C251 has a cell phone."
∃x ¬P(x) "There exists at least one person in C251 without a cell phone."
¬∀x P(x) Ξ ∃x ¬P(x)
Example
"Some one in C251 that has a cell phone."
Q is "has a cell phone"
x is in domain "C251".
Q(x) is some x in domain C251 has a cell phone.
∃x Q(x) is
 "Some one in C251 that has a cell phone."
 "There exists at least one person in C251 with a cell phone."
¬∃x Q(x) Ξ ∀x ¬Q(x)
the negation would be:
"There does not exist at least one person in C251 with a cell phone."
"No one in C251 has a cell phone."
"For students in C251, no student has a cell phone."
¬∃x Q(x) Ξ ∀x ¬Q(x)
Example
 ∃x ( x = 2)
¬∃x ( x = 2) Ξ ∀x ¬( x = 2) Ξ ∀x ( x ≠ 2 )
 ∀x (x^{2} > x)
¬∀x (x^{2} > x) Ξ ∃x ¬( x^{2} > x ) Ξ ∃x ( x^{2} ≤ x )
 ∃x ( x^{2 }= 2)
¬∃x (x^{2 }= 2) Ξ ∀x ¬( x^{2 }= 2 ) Ξ ∀x ( x^{2 } ≠ 2 )
¬∀x P(x) Ξ ∃x ¬P(x)
¬∃x Q(x) Ξ ∀x ¬Q(x)
Question 21
 ¬∀x ( x = x^{2 }) Ξ
 ¬∃x ( x^{2 }< 0 ) Ξ
 ∃x ¬( x^{2 }> 0 ) Ξ
Example  Use De Morgan's Laws to show:
¬∀x (P(x) → Q(x)) Ξ ∃x (P(x) ^ ¬Q(x))
¬∀x (P(x) → Q(x)) Ξ ∃x ¬(P(x) → Q(x)) by De Morgan's Ξ ∃x ( P(x) ^ ¬Q(x)) by fifth rule in Table 7, Section 1.2 (below)
Question 22  Give a logical equivalent using Table 7.
 p v q Ξ
 ∃x( P( x ) v Q( x ) ) Ξ
 p → q Ξ
 ∀x( P( x ) → Q( x ) ) Ξ
Translating from English into Logical Expressions
See http://highered.mcgrawhill.com/sites/dl/free/0072880082/299355/ExtraExamples_1_3.pdf for worked examples.
Example
x is in domain of "all people."
S(x) is "x is a student in C251".
M(x) is "x has visited Mexico.
"Some student in C251 has visited Mexico."
"There exists a student x in C251 such that x has visited Mexico"
∃x (S(x) ^ M(x))
Note, cannot use S(a) → M(a)
"If a is student in C251 then a has visited Mexico"
because S(a) → M(a) is True when S(a) is False:
∃x (S(x) ^ M(x)) ≠ ∃x (S(x) → M(x))
∃x (S(x) → M(x)) would be True for everyone not in C251.
p q p ^ q p → q F F F T F T F T T F F F T T T T
Example
x is in domain of "all people."
S(x) is "x is a student in C251."
M(x) is "x has visited Mexico."
C(x) is "x has visited Canada."
"Every student in C251 has visited Mexico or Canada."
∀x ( S(x) ^ ( M(x) v C(x) )
Note cannot use:
∀x ( S(x) → (M(x) v C(x) )
"If a student is in C251 then they have visited Mexico or Canada."
Consider any person a.
S(a) → M(a) is True when S(a) is False.
The statement is True for all C251 students that have visited Mexico and everyone else not in C251 whether they visited Mexico or not.
S(a) M(a) S(a) ^ M(a) S(a) → M(a) F F F T F T F T T F F F T T T T
Introduction
Example
 ∃y (1 + y = 0) is True for y = 1
 ∃x ∃y (x + y = x * y) is True for the pair y = 0, x = 0
 ∀x ∃y (x + y = 0) is True for y = x
 ∃x ∀y (x * y = 0) is True for x = 0 and all y
 ∀y ∃x (x * y = 0) is True for x = 0 and all y
 ∀x ∀y (x + y = y + x) is True by the commutative law of addition
The Order of Quantifiers
Example
x ∈{1, 2, 3}
y ∈{5, 4, 3}
∀x ∀y Q(x, y) The inner y can change for each outer x.
for all x in {1, 2, 3} for all y in {5, 4, 3}
Q(x, y) is True
Example
Below Q(x, y) is a predicate with domain:x ∈ { 1, 2 }
y ∈ { R, G }
Table shows Q( 1, G ), Q( 2, R ) are True, Q(x, y) is False otherwise.
Q(x, y) y=R y=G x=1 F T x=2 T F
 ∃x ∀y Q(x, y) is False
"There exists x such that for all y, Q(x, y) is True"
The x is the same, ∀y.
 ∀y ∃x Q(x, y) is True
"For all y, there exists x such that Q(x, y) is True"
The x can be different, ∀y.
 ∀y ∃x Q(x, y) is not equivalent to ∃x ∀y Q(x, y)
 ∀x ∀y Q(x, y) is False
"For all x, for all y, Q(x, y) is True"
 ∃x ∃y Q(x, y) is True
"There exists x and y such that Q(x, y) is True"
Question 23.1
In the questions below P(x, y) is a predicate with domain:x ∈ { 1, 2 }
y ∈ { R, G }
Table shows P( 1, G ), P( 2, G ) are True, P(x, y) is False otherwise.
P(x, y) y=R y=G x=1 T F x=2 F T
 Translate into English in your head.
 Determine the truth value.
 P(2, R)
 ∀y P(2, y)
 ∀x ∀y P(x, y)
 ∃x ∃y P(x, y)
 ∀x ∃y P(x, y)
 ∃y ∀x P(x, y)
 ∀y ∃x P(x, y)
Translating Mathematical Statements into Statements Involving Nested Quantifiers
Example
"For every two integers, if both are negative, then their product is positive."
∀x ∀y ((x < 0) ^ (y < 0)) → (x * y > 0))
Example
"For every integer x, there exists a smaller integer y."
∀x ∃y (y < x)
Translating from Nested Quantifiers into English
Example
x and y is the domain of current C251 students
tookNotes(x) is "x took notes"
F(x, y) is "x and y are friends"
∀x∀y F(x, y)
"Every C251 student is a friend of every C251 student."
∀x∃y F(x, y)
"Every C251 student is a friend of at least one C251 student."
∃x∀y F(x, y)
"At least one C251 student is a friend every C251 student."
∀x (tookNotes(x) v ∃y( tookNotes(y) ^ F(x, y)) )
"Every C251 student took notes or had a friend in the class that took notes."
Translating English Sentences into Logical Expressions
Example
x and y are from the domain of all people
L(x, y) is "x loves y"
 "Everybody loves everybody" is ∀x ∀y L(x, y)
 "Everybody loves everybody else" is ∀x ∀y (L(x, y) ^ (x ≠ y))
 "Everybody loves somebody else" is ∀x ∃y (L(x, y) ^ (x ≠ y))
 "Somebody loves somebody else" is ∃x ∃y (L(x, y) ^ (x ≠ y))
 "Everybody loves themselves" is ∀x ∃y (L(x, y) ^ (x = y))
 "Somebody loves only themselves" is ∃x ∃y (L(x, y) ^ (x = y))
Negating Nested Quantifiers
Example
Express so that no negation precedes a quantifier.
 ¬∀x (x = 1) Ξ ∃x ¬(x = 1) Ξ ∃x (x ¬= 1)
 ¬∃x (x > 2x) Ξ ∀x ¬(x > 2x) Ξ ∀x (x ≤ 2x)
 ∃x ∀y ¬(xy = 1) Ξ ∃x ∀y (xy ¬= 1)
 ∃x ¬∃y (xy = 1) Ξ ∃x ∀y ¬(xy = 1) Ξ ∃x ∀y (xy ¬= 1)
 ¬∀x ∃y (xy = 1) Ξ ∃x ¬∃y (xy = 1) Ξ ∃x ∀y ¬(xy = 1) Ξ ∃x ∀y (xy ¬= 1)
Example
Q(x, y) is a predicate with domain:x ∈ { 1, 2 }
y ∈ { R, G }
Table shows Q( 1, G ), Q( 2, R ) are True, Q(x, y) is False otherwise.
Q(x, y) y=R y=G x=1 F T x=2 T F
 ∃y Q(2, y) Ξ T
 ¬∃y Q(2, y) Ξ ∀y ¬Q(2, y) Ξ F
 ∀x ∃y Q(x, y) Ξ T
 ¬∀x ∃y Q(x, y) Ξ ∃x ¬∃y Q(x, y) Ξ ∃x ∀y ¬Q(x, y) Ξ F
 ∃y ∀x ¬Q(x, y) Ξ F
 ¬∃y ∀x ¬Q(x, y) Ξ ∀y ¬∀x ¬Q(x, y) Ξ ∀y ∃x ¬¬Q(x, y) Ξ ∀y ∃x Q(x, y) Ξ T
Question 23.2
In the questions below, P(x, y) is a predicate with domain:x ∈ {1, 2}
y ∈ {R, G}
P(x, y) y=R y=G x=1 F T x=2 F T
 Express so that no negation precedes a quantifier.
 Determine the truth value.
∃y P(2, y) Ξ
 ¬∃y P(2, y) Ξ
 ¬∃x P(x, R) Ξ
∀x ∃y P(x, y) Ξ
¬∀x ∃y P(x, y) Ξ
¬∀y ∃x P(x, y) Ξ
¬∃x ∃y P(x, y) Ξ
¬∃y ∀x ¬P(x, y) Ξ
1.5 Rules of Inference
Definition
Proof is a sequence of True statements (premises) that end in a valid conclusion.
Valid Arguments in Propositional Logic
Example
p
_______
∴ pTrue premise
______________
∴ True conclusionIf p is True then p is True.
p p p → p F F T T T T
Example  Conjunction
p
q
_______
∴p ^ qTrue premise
True premise
___
∴True conclusionIf p is True and q is True
then p ^ q is True.
p q p ^ q p ^ q → p ^ q F F F T F T F T T F F T T T T T
"You buy a lottery ticket" "You win a million dollars"
∴"You buy a lottery ticket" ^ "You win a million dollars"
p q
_____
∴p ^ q
Example  Modus ponens
If p → q is True and p is True
then q is True.
p → q
p
_____
∴qTrue premise
True premise
___
∴True conclusionKnow that when all premises are True, the conclusion, q, is True.
( (p → q) ^ p ) → q
p q p → q (p → q) ^ p ((p → q) ^ p) → q F F T F T F T T F T T F F F T T T T T T Note in table:
 only when the premises p → q is True and p is True, (p → q) ^ p, is q also True.
 when any one of the premises is False, either (p → q) or p, q can be True or False.
 ( (p → q) ^ p ) → q is a tautology,
implies Modus Ponens is valid rule of inference, it is always True.
Example
"You have a current password" → "You can log on the network" "You have a current password"
∴"You can log on the network"
p → q
p
_____
∴q
True premise
True premise
___
∴True conclusion
Example
4 > 2 → 4^{2} > 2^{2} 4 > 2
∴can conclude 4^{2} > 2^{2} is True
p → q
p
_____
∴q
True premise
True premise
___
∴True conclusion
p q p → q (p → q) ^ p (p → q) ^ p → q F F T F T F T T F T T F F F T 4 > 2 → 4^{2} > 2^{2 }p q T T T T T
Example
2 > 4 → 2^{2} > 4^{2} 2 > 4
∴cannot conclude 2^{2} > 4^{2} is True
p → q
p
_____
∴q
True premise
False premise
___
∴False conclusionBecause one of the premises, p, is False, the conclusion is False.
Invalid inference rules
Example
p → q
¬p
_____
∴qTrue premise
True premise
___
Conclusion not valid(p → q) ^ ¬p → q is not a valid rule of inference.
Result (last column) not always True.
p q ¬p p → q (p → q) ^ ¬p (p → q) ^ ¬p → q 2 > 4 → 2^{2} > 4^{2} F F T T T F F T T T T T T F F F F T T T F T F T Question 24.0
a. Complete the table below to prove inference rule valid: Modus tollens
If p → q is True and ¬q is True then ¬p is True.
b. In which row is the conclusion True?
p → q
¬q
_____
∴¬pTrue premise
True premise
___
∴True conclusion
p q p → q ¬q (p → q) ^ ¬q ¬p ((p → q) ^ ¬q) → ¬p F F F T T F T T
Rules of Interference for Propositional Logic
Example
Conjunction "You buy a lottery ticket" "You win a million dollars"
∴"You buy a lottery ticket" ^ "You win a million dollars"
p q
_____
∴p ^ q
Simplification "You buy a lottery ticket" ^ "You win a million dollars"
∴"You win a million dollars"
p ^ q
_____
∴q
Disjunctive Syllogism "You buy a lottery ticket" v "You win a million dollars" "You did not buy a lottery ticket"
∴"You win a million dollars"
p v q
¬p
_____
∴q
Resolution 3 = 4 v 5 < 10
¬(3=4) v 9 < 0
∴5 < 10 v 9 < 0p v q
¬p v r
_____
∴q v rNote that ALL inference rules require ALL premises to be True.
The inference rule is always True, a tautology.
Question 24.1  What rule of inference is used in the following?

Using Rules of Inference to Build Arguments
Example
Propositions  may be True or False
p "It is sunny this afternoon" q "It is colder than yesterday" r "We will go swimming" s "We will take a canoe trip" t "We will be home by sunset" Premises  assumed to be True
¬p ^ q "It is not sunny this afternoon and it is colder than yesterday" r → p "If we will go swimming, then it is sunny" ¬r → s "If we do not go swimming, then we will take a canoe trip" s → t "If we take a canoe trip, then we will be home by sunset.

Resolution  Only rule of inference required, useful for computer implementation of logic solvers (e.g. Prolog).
Definition
Clause is a disjunction of variables or their negation. Resolution is the only rule of inference needed but requires hypotheses and conclusion to be in clause form.
p v q
¬p v r
_____
∴q v rExample
Given the following are True:
(p ^ q) v r
r → s
(p ^ q) v r Ξ (r v p) ^ (r v q) Distributive Law
Both (r v p) and (r v q) are True(r v p) Simplification r → s Ξ ¬r v s Replace with equivalent clause r v p
¬r v s
_____
∴ p v sBy resolution p v s
is True
Resolution Truth Table Proof p v q
¬p v r
_____
∴q v rp q r ¬p p v q ¬p v r (p v q) ^ (¬p v r) q v r (p v q) ^ (¬p v r) → q v r F F F T F T F F T F F T T T T T T T F T F T T T T T T F T T T T T T T T T F F F T F F F T T F T F T T T T T T T F F T F T T T T T T F T T T T T
Fallacies
Example
p → q
q
_____
∴pTrue premise
True premise
___
∴invalid conclusionNot a tautology, therefore not valid as a rule of inference.
(p → q) ^ q → p
p q p → q (p → q) ^ q (p → q) ^ q → p F F T F T F T T T F T F F F T T T T T T
Example
p → q
¬p
_____
∴ ¬qTrue premise
True premise
___
∴invalid conclusionNot a tautology, therefore not valid as a rule of inference.
(p → q) ^ ¬p → ¬q
p q ¬p ¬q p → q (p → q) ^ ¬p (p → q) ^ ¬p → ¬q F F T T T T T F T T F T T F T F F T F F T T T F F T F T
Question 24.2
a. Complete the table to prove that Disjunctive Syllogism is a valid rule of inference. b. In which row is the conclusion True?
Disjunctive Syllogism p q p v q ¬p (p v q) ^ ¬p (p v q) ^ ¬p → q F F F T T F T T p v q
¬p
_____
∴q
Rules of Inference for Quantified Statements
Universal instantiation
P(c) is True for all c in domain given ∀x P(x)
P(x) is "x + 1 > x" where x ∈ { 2, 1, 0 }
∀x P(x) is True
P(c) is True for c ∈ {2, 1, 0}
P( 1 ) is True
Universal generalization
∀x P(x) is True given P(c) is True for all c in domain.
Show ∀x P(x) by showing that for any arbitrary c in domain, P(c) is True.
P(c) is "c + 1 > c" is True where c ∈ {2, 1, 0}
P( 2 ) = 2 + 1 > 2 is True
P( 1 ) = 1 + 1 > 1 is True
P( 0 ) = 0 + 1 > 0 is True
∀x P(x) is True
Existential instantiation
P(c) is True for some c in domain given ∃x P(x) is True
P(x) is "x + 1 > 0" where x ∈ { 2, 1, 0 }
∃x P(x) is True
P( c ) is True
Existential generalization
∃x P(x) is True when a particular c with P(c) True is known.
If we know one c with P(c) True, then ∃x P(x) is True.
P(x) is "x + 1 > 0" where x ∈ { 2, 1, 0 }
P( 0 ) = 0 + 1 > 0 is True
∃x P(x) is True
Question 25.1  Valid inference rule?
 ∃x P(x)
∴ P(c)
 C(c) ^ ¬B(c) p ^ q by Simplification
∴ C(c) ∴ p
 ∃x ((P(x) ^ Q(x)) x identical for P(x) ^ Q(x)
∴ P(c) ^ Q(c)
 ∀x (P(x) → Q(x))
∴ P(c) → Q(c)
 P(c) ^ Q(c) c identical for P(c) ^ Q(c)
∴ ∃x ((P(x) ^ Q(x))
Combining Rules of Inference for Propositions and Quantified Statements
Universal modus ponens
∀x (P(x) → Q(x)) P(a)
____∴Q(a)
P(a) → Q(a) P(a)
____∴Q(a)
Given ∀x (P(x) → Q(x)),
when P(a) for a particular a, Q(a).
Universal modus tollens
∀x (P(x) → Q(x)) ¬Q(a)
____∴¬P(a)
P(a) → Q(a) ¬Q(a)
____∴¬P(a)
Given ∀x (P(x) → Q(x)),
when ¬Q(a) for a particular a, ¬P(a).
Example proof
Premises are True
 ∃x (C(x) ^ ¬B(x))
 ∀x (C(x) → P(x))
Show Conclusion
∃x (P(x) ^ ¬B(x))
∃x (C(x) ^ ¬B(x)) Premise 1 C(a) ^ ¬B(a) Existential instantiation of ∃x (C(x) ^ ¬B(x))
∃x P(x)
∴ P(a) true for some aC(a) Simplification of C(a) ^ ¬B(a) ∀x (C(x) → P(x)) Premise 2 C(a) → P(a) Universal instantiation of ∀x (C(x) → P(x)) ∀x P(x)
∴ P(a) true for some aC(a)
C(a) → P(a)
P(a)Modus ponens P(a) true
¬B(a) Simplification of C(a) ^ ¬B(a) P(a) ^ ¬B(a) Conjunction of two truths ∃x (P(x) ^ ¬B(x)) Existential generalization P(a) true for some a
∴∃x P(x)
Eliminating Software Failures: Testing vs Verification
Testing = running the program with a set of inputs to gain confidence that the software has few defects (in this case, the program is said to be “tested”)
Goal: reduce the frequency of failures
When done: after the programming is complete
Methodology: develop test cases, normally including boundary conditions; run the program with each test case
Verification = formally proving that the software has no defects (in this case, the program is said to be “correct”)
Goal: detect errors and eliminate failures
When done: before, during and after the programming is complete
Methodology:
 write separate specifications for the code (e.g. pre and post conditions)
 prove that the code and the specifications are mathematically equivalent (i.e. the code produces results consistent with specifications).
Program Correctness
The correctness of a program is based on a specific standard.
That standard is called a specification.
// Compute max of a and b int max (int a, int b) {
int m;
if (a ≥ b)
m ← a;
else
m ← b;
return m;
}An informal specification for the above program might be that it "finds the maximum value of any two integers."
Formalizing a Specification
Formal specification is written as a logical expression called an assertion.
Assertion describes the state of the program's variables.Two key assertions are the program's precondition and its postcondition; P and Q respectively.
Domain is a set of values over which a variable is well defined.The primitive types (int, float, boolean, etc.) and standard Java classes (String, Vector, HashMap, etc.) provide domains for reasoning about programs.
Precondition  Country bridges often have a weight limit sign posted that specifies the precondition for a safe crossing.
Postcondition  Violating the bridge weight limit, its precondition, may result in the bridge failure.
Preconditions describe minimum requirements for the program to run correctly.
max, the precondition is P = True because a and b can be any integers.
Postconditions describes what will be computed when the precondition is True.
max, a postcondition is Q = m ≥ a ^ m ≥ b, defining m to be greater than or equal both a and b.
Before proving a program's correctness, we first write its specifications:
{P is True} int max (int a, int b) {
int m;
if (a ≥ b)
m ← a;
else
m ← b;
return m;
}{Q is m ≥ a ^ m ≥ b}
Proof must show that: if preconditions P = True then postconditions Q = True for the code of max:
P → Q
True → m ≥ a ^ m ≥ b
P Q P → Q F F T F T T T F F T T T
Example
{ P is x = 1 ^ y = 3} int sum (int x, int y) {
z ← x + y;
return z;
}{ Q is z = 4 }
x=1 ^ y=3 → z=4 x=1 ^ y=3 z=4 x=1 ^ y=3 → z=4 P Q P → Q F F T F T T T F F T T T
Assume preconditions True { P is x = 1 ^ y = 3 }
int sum (int x, int y) {
z ← x + y;
return z;
}Prove algorithm ensures postcondition True { Q is z = 4 }
Proof: if P = True then Q = True
{ P is x = 1 ^ y = 3} int sum (int x, int y) {
z ← x + y;
return z;
}{ Q is z = 4 }
x = 1 ^ y = 3 Assume P (precondition) is True z ← x + y Definition of z z ← 1 + 3 Substitution of x and y z ← 4 Addition 1 + 3 z = 4 Q (post condition) is True by z ← 4 z = 4 ∴ P → Q Question 25.2
 For the algorithm above, does x = 1 ^ y = 3 → z = 4?
 What other values of x and y result in z = 4?
 Did our proof ensure those other preconditions produce the postcondition is True, z=4?
 Redo the proof for:
{ P is x = 5 ^ y = 9 } int sum (int x, int y) {
z ← x + y;
return z;
}{ Q is z = 4 }
1.6 Introduction to Proofs
Some Terminology
Theorem
Statement that can be shown to be True. Propositions
Statement that can be shown to be True but not as important as theorems. Proof
Valid argument that establishes the truth of a theorem. Axiom
Statements assumed to be True. Hypothesis
"If P, then Q" P denotes the hypothesis
Q is the conclusion.
Direct Proof
Assume hypothesis is True and
show through valid rules of inference,
that the conclusion is True.
Example
p is "I won the lottery"
q is "I have a lottery ticket"
Prove p → q
If I won the lottery then I have a lottery ticket.
Hypothesis:
Assume p is True, "I won the lottery"
Conclusion:
Prove q is True, "I have a lottery ticket"
Proof
p is True "I won the lottery" assumed True. q is True "I have a lottery ticket" must prove True by having a lottery ticket. ∴ p is True
q is True
∴ p → q is True
p q p → q F F T F T T T F F T T T
Definition 1
Even integer n has k such that n = 2k
Odd integer n has k such that
n = 2k+1
Example
Even
n = 12 = 2(6) k = 6
Odd
n = 13 = 2(6) + 1 k = 6
Example direct proof
Propositions
 p is "n is odd" n = 2k + 1
 q is "n^{2} is odd" n^{2} = (2k + 1)^{2}
Prove
"If n is odd, then n^{2} is odd"
"n is odd" → "n^{2} is odd"
p → q
Hypothesis:
p assumed True
"n is odd" n = 2j + 1
Conclusion:
q, must show to be True
"n^{2} is odd" n^{2} = 2i + 1
n = 2j + 1 p is True, n is odd. (n)^{2} = (2j + 1)^{2} Square both sides, to show "n^{2} is odd" = (4j^{2} + 4j + 1) Multiply = 2(2j^{2} + 2j) + 1 Factor = 2(2j^{2} + 2j) + 1 q is True, n^{2} is odd
n^{2} = 2i+1i = 2j^{2} + 2j
∴ n^{2} is odd ∴ p is True
q is True
∴ p → q is TrueAssumed p, "n is odd" to be True.
Proved by algebra and odd definition, with p True, q is "n^{2} is odd" to be True.
"n is odd" → "n^{2} is odd"
p is True
q is True
∴ p → q is True"n is odd" is True
"n^{2} is odd" is True
∴ "n is odd" → "n^{2} is odd" is True
n is odd n^{2} is odd n is odd → n^{2} is odd p q p → q F F T F T T T F F T T T
Question 26.0
Propositions
 p is "n is even" n = 2k
 q is "n^{2} is even" n^{2} = 2k
Prove
"If n is even, then n^{2} is even"
"n is even" → "n^{2} is even"
p → q
Hypothesis p assumed True
"n is even" n = 2j
Conclusion q, must show to be True
"n^{2} is even" n^{2} = 2i
n = 2j p is True, n is even. (n)^{2} = ______________ a. Square both sides = ______________ b. Multiply = ______________ c. Factor out 2, e.g. 6x^{2} = 2*(3x^{2}) = ______________ e. q is True, n^{2} is even
n^{2} = 2ii = _____________ f.
∴ n^{2} is even ∴ p is True
q is True
∴ p → q is True
Example  Program Correctness Proof
{ P: n is odd } int square ( int n ) {
z ← n^{2};
return z;
}{ Q: z is odd }
Assume preconditions True { P: n is odd }
int square ( int n ) {
z ← n^{2};
return z;
}Prove algorithm ensures postcondition True { Q: z is odd }
Proof
n is odd P is True n = 2j+1 Definition of odd n^{2 }= (2j+1)^{2} From z ← n^{2} = 4j^{2}+4j + 1 Multiply = 2(2j^{2}+2j) + 1 n^{2} odd
for k = 2j^{2}+2jz = n^{2} z ← n^{2} z is odd P is True n is odd
Q is True z is odd
∴ P → QQuestion 26.1
Redo the proof for:
{ P: n is even } int square ( int n ) {
z ← n^{2};
return z;
}{ Q: z is even }
n is even P is True n = ____________ a. Definition of even n^{2 }= ___________ b. Square both sides = ___________ c. Multiply = ___________ d. n^{2} is even
for k = ________ e.z = n^{2} ______________ f. z is even P is True n is even
Q is True z is even
∴ P → Q
Definition 1
Even integer n has k such that n = 2k
Odd integer n has k such that
n = 2k+1
Example
a is odd integer a = 2i + 1
b is odd integer b = 2j + 1
Prove
"If a and b are odd, then a + b is even"
p → q
Hypothesis p is assumed True
"a and b are odd"
a = 2i + 1
b = 2j + 1Show q is True
"a + b is even."
a = 2i + 1
b = 2j + 1p, hypothesis, is True,
a and b are odda + b = (2i + 1) + (2j + 1) Substitution for a and b = 2i + 2j + 2 Addition = 2(i + j + 1) Factor = 2(i + j + 1) q is True
a + b = 2k
for k = i+j+1∴a + b is even a and b odd → a + b even
∴ q is True
p is True
∴ p → q is TrueQuestion 26.2
If a and b are even then a + b is even.
 What is the hypothesis, p?
 What is the conclusion, q?
 Give a direct proof similar to above.
a = ______ i.
b = ______ ii.p, hypothesis, is True,
a and b are evena + b = ________________ iii. Substitution for a and b = ________________ iv. Addition = ________________ v. Factor q is True
a + b = __________ vi.
for k = __________ vii.∴a + b is even a and b even → a + b even
∴ q is True
p is True
∴ p → q is TrueDefinition 1
Even integer n has k such that n = 2k
Odd integer n has k such that
n = 2k+1
Proof by Contraposition (or Proof by Contrapositive)
p → q Ξ ¬q → ¬p
p q p → q ¬q ¬p ¬q → ¬p T T T F F T F T T F T T T F F T F F F F T T T T When p → q difficult to prove, consider direct proof of ¬q → ¬p
Example
Prove p → q
"If n^{3} + 5 is odd then n is even."
p is "n^{3} + 5 is odd."
q is "n is even."
Contrapositive
¬q → ¬p
"If n is not even, then n^{3} + 5 is not odd."
"If n is odd, then n^{3} + 5 is even."
¬q is "n is odd."
¬p is "n^{3} + 5 is even."
Prove
"If n is odd, then n^{3} + 5 is even."
¬q → ¬p
Hypothesis ¬q assumed True
"n is odd", n = 2j + 1
Show ¬p True
"n^{3} + 5 is even"
n = 2j+1 ¬q is True, n is odd. n^{3} + 5 = (2j + 1)^{3 }+ 5 Substitute 2j + 1 for n = 8j^{3} + 12j^{2} + 6j + 6 Multiply = 2(4j^{3} + 6j^{2} + 3j + 3) Factor n^{3} + 5 = 2(4j^{3} + 6j^{2} + 3j + 3) ¬p is True
n^{3} + 5 = 2k is even∴"If n is odd, then n^{3} + 5 is even." ∴ ¬p is True
¬q is True
∴ ¬q → ¬p∴"If n^{3} + 5 is odd, then n is even." p → q Ξ ¬q → ¬p by contraposition Question 27
If n^{2} is an odd integer then n is an odd integer.
p is "n^{2} is an odd integer"
q is "n is an odd integer"
 What is the contraposition in English, ¬q → ¬p?
 What is the hypothesis, ¬q?
 What is the conclusion, ¬p?
 Give a direct proof of ¬q → ¬p.
Definition 1
Even integer n has k such that n = 2k
Odd integer n has k such that
n = 2k+1
Proofs by Contradiction
Direct proof assumes hypothesis is True and using rules of inference shows theorem is True.
∴ p
q
∴ p → qContradiction proof assumes theorem is False; using rules of inference, shows contradiction of assuming to be False.
Only source of contradiction was assumption that theorem False.
Contradiction, not possible for both p and ¬p to be true.
p ¬p p ^ ¬p T F F F T F Example
p is "I won the lottery"
q is "I have a lottery ticket"
Prove p → q
If I won the lottery then I have a lottery ticket.
Hypothesis:
Assume p True, "I won the lottery"
Conclusion:
Assume ¬q True, "I do not have a lottery ticket"
Proof
p is True "I won the lottery" assumed True. ¬q is True "I do not have a lottery ticket" assumed True. ¬p is True When ¬q is True "I do not have a lottery ticket",
¬p is True
"I did not win the lottery", because of lottery rules.
¬p ^ p Contradiction, not possible for both p and ¬p to be true. ¬q cannot be True. Source of contradiction. q must be True. "I do have a lottery ticket" p is True
q is True
∴p → q is True
Contradiction proofs
Following are three different proofs by contradiction of same theorem and one by use of contrapositive.
Premise
p is x^{2} + x  2 = 0
q is x ≠ 0
Prove
"If x^{2} + x  2 = 0 then x ≠ 0"
x^{2} + x  2 = 0 → x ≠ 0
p → q
*Example 1
Assume
Hypothesis:
p is True, x^{2} + x  2 = 0
Conclusion:
¬q is True, x = 0.
q is x ≠ 0.
Derive contradiction that by assuming ¬q is True that p is False: x^{2} + x  2 ≠ 0
Proof
x^{2} + x  2 = 0 Assumption p x = 0 Assumption ¬q x^{2} + x  2 = 0^{2} + 0  2 Substitute x=0 = 2 Have shown ¬p
x^{2} + x  2 ≠ 0x^{2} + x  2 = 2 Contradiction of p: x^{2} + x  2 = 0 ¬p ^ p
Result of assuming ¬q True, x=0
∴ q must be true
∴x^{2} + x  2 = 0 → x ≠ 0 p
q
∴p → q
By assuming:p: x^{2} + x  2 = 0
¬q: x = 0
leads to:
¬p: x^{2} + x  2 ≠ 0
Contradiction:
p ^ ¬p
Source of contradiction from assuming ¬q True.
Can conclude ¬q is False, so q is True.
and by assuming p is True
p → q is True
"If x^{2} + x  2 = 0 then x ≠ 0"
p q p → q F F T F T T T F F T T T
Rule of inference: Proof by Contradiction
If, from assuming p and ¬q, can derive both r and ¬r for some statement r, can conclude p → q.
Prove p → q
Assume p and ¬q
Derive ¬p
Contradiction p ^ ¬p
Conclude p → q
Note here: r = p, ¬r = ¬p
Example 2
Premise
p is x^{2} + x  2 = 0
q is x ≠ 0
Prove
x^{2} + x  2 = 0 → x ≠ 0
p → q
Assume:
Hypothesis: p is True, x^{2} + x  2 = 0
Conclusion: ¬q is True, x = 0.
Derive contradiction of a known fact.
Proof
x^{2} + x  2 = 0 Assumption of hypothesis p True 0^{2} + 0  2 = 0 Substituting into p,
assumption ¬q: x = 02
= 0 Contradiction of known fact,
showing ¬p is True∴x^{2} + x  2 = 0 → x ≠ 0 Assuming p and ¬q both True leads to contradiction
p ^ ¬p, therefore q is True.∴x^{2} + x  2 = 0 → x ≠ 0 p
q
∴p → q
*Example 3
Premise
p is n^{2} is even
q is n is even
Prove
n^{2} is even → n is even
p → q
Assume:
Hypothesis: p is True, n^{2} is even
Conclusion: ¬q is True, n is odd.
Derive contradiction of a known fact.
Proof n^{2} is even → n is even
n = 2i+1 Assumptions
p: n^{2} is even
¬q: n is oddn^{2} = (2i+1)^{2}
= 4i^{2}+4i+1 = 2(2i^{2}+2i) + 1 n^{2} is odd, ¬p
p ^ ¬p cannot be True∴ n^{2} is even → n is even Assuming p and ¬q both True
leads to contradiction p ^ ¬p,
therefore q is True.q: n is even
p
q
∴p → qQuestion 28
If n^{2} is an odd integer then n is an odd integer.
 What is the hypothesis, p?
 What is the conclusion, q?
 What is ¬q?
 What is ¬p?
 Prove by contradiction, p → q.
Hint: Assume p and ¬q are True, show that assuming ¬q results in ¬p.Proof n^{2} is odd → n is odd
n = ______________ i. Assumption
p: n^{2} is odd
¬q: n is ____________ ii.n^{2} = ______________ iii.
= ______________ iv. n^{2} is ______________, ¬p is True
v.
p ^ ¬p∴ n^{2} is ______ → n is _______
vi. vii.Assuming p and ¬q both True
leads to contradiction p ^ ¬p,
therefore q is True.q: n is ______________ viii.
Definition 1
Even integer n has k such that n = 2k
Odd integer n has k such that
n = 2k+1
Example 4
Premise
p is x^{2} + x  2 = 0
q is x ≠ 0
Assume:
Hypothesis: p is True, x^{2} + x  2 = 0
Conclusion: ¬q is True, x = 0.
Proof
x^{2} + x  2 = 0 Assumption of hypothesis p x^{2} + x
= 2 Add 2 to both sides 0^{2} + 0
= 2 Substituting assumption ¬q, x = 0 0
= 2 p: x^{2} + x  2 = 0 False assuming ¬q, x = 0 ¬p is True
∴x^{2} + x  2 = 0 → x ≠ 0 p and ¬q both True leads to contradiction p ^ ¬p
Rule of Inference: Proof by Contraposition
p → q Ξ ¬q → ¬p
p q p → q ¬q ¬p ¬q → ¬p T T T F F T F T T F T T T F F T F F F F T T T T
Example 5
Premise
p is x^{2} + x  2 = 0
q is x ≠ 0
Prove
"If x^{2} + x  2 = 0, then x ≠ 0."
Contrapositive
p → q Ξ ¬q → ¬p "If x = 0, then x^{2} + x  2 ≠ 0."
x = 0 → x^{2} + x  2 ≠ 0
¬q → ¬p
Hypothesis
¬q is True, x = 0.
Show
¬p is True, x^{2} + x  2 ≠ 0
Proof
x
= 0 Assumption of hypothesis, ¬q x^{2} + x  2 = 0^{2} + 0  2 = 2 Substituting x = 0 x^{2} + x  2 = 2≠ 0 ¬p is True ∴x = 0 → x^{2} + x  2 ≠ 0 ¬q
¬p
¬q → ¬p is True∴x^{2} + x  2 = 0 → x ≠ 0 By contrapositive, p → q Ξ ¬q → ¬p
*Example 6
p is "n^{3} + 5 is odd."
q is "n is even."
"If n^{3} + 5 is odd, then n is even."
p → q
Contradiction
p is "n^{3} + 5 is odd."
¬q is "n is odd."
Assume p and ¬q are True, p → ¬q
"If n^{3} + 5 is odd, then n is odd."
Hypothesis
p is "n^{3} + 5 is odd."
¬q is "n is odd."
Show
p → q from contradiction
"If n^{3} + 5 is odd, then n is even."
Proof
n = 2j+1 ¬q is True, n is odd (Assumed) n^{3} + 5 = (2j + 1)^{3 }+ 5 Substitute 2j + 1 for n = 8j^{3} + 12j^{2} + 6j + 6 Multiply and factor n^{3} + 5 = 2(4j^{3} + 6j^{2} + 3j + 3) n^{3} + 5 is even (Proven)
¬p is Truen^{3} + 5 is odd (Assumed)
p is TrueAssuming p and ¬q both True
leads to contradiction p ^ ¬p∴"If n^{3} + 5 is odd, then n is even." ¬q is False, source of contradiction
so q is Truep
q
∴p → q
Counterexamples
Can show ∀x P(x) False by finding one counterexample.
Example
∀x (x^{2 }> 0)
False when x = 0
Example
∀x P(x) is "Every prime number is odd"
2 is a prime number but is even ∀x P(x) is False Example
∀x P(x) is "Every positive integer is the sum of the squares of two integers"
Examples
0^{2 }+ 1^{2 }= 1 1^{2 }+ 1^{2 }= 2 ∀x P(x) requires some x^{2 }+ y^{2 } = 3 Since x^{2 }+ 2^{2 }> 3 for any integer x, 2 < y^{ }< 2. Either:
x^{2 }+ 1^{2 }= 3
x^{2 }+ (1)^{2 }= 3
x^{2 }+ 0^{2 }= 3x^{2 }+ 1^{2 }= 3 implies x^{2 }= 2, x is not an integer x^{2 }+ (1)^{2 }= 3 implies x^{2 } = 2, x is not an integer x^{2 }+ 0^{2 }= 3 implies x^{2 }= 3, x is not an integer ∀x P(x) is False Question 29  Give a counterexample to the statement: "If n^{2 } is positive, then n is positive"
Mistakes in Proofs
p is "n is positive"
q is "n^{2 }is positive""If n is positive then n^{2 } is positive", p → q, known to be True.
p Assumed True
p → q Known True (we proved)
q Modus PonensProve
"If n^{2 }is positive then n is positive"
q Assumed True
p → q Known True
p Invalid inference rule
p q p → q F F T F T T T F F T T T
q
p → q
p True or False
If n is positive then n^{2 }is positive p → q, known to be True n^{2 }is positive Assumption q ∴n is positive False conclusion based on invalid inference rule
p → q
q
∴p
To show q → p, use Modus Ponensq → p
q
∴pSummary of Proof Methods (so far)
Direct
p is "I won the lottery"
q is "I have a lottery ticket"
Prove p → q
If I won the lottery then I have a lottery ticket.
Hypothesis: Assume p is True, "I won the lottery"
Conclusion: Prove q is True, "I have a lottery ticket"
Proof
p is True "I won the lottery" assumed True. q is True "I have a lottery ticket" must prove True by having a lottery ticket. p is True
q is True
p → q is True
Question 29.1  Give a direct proof that:
If n is even then 3n+2 is even
Contrapositive
p is "I won the lottery"
q is "I have a lottery ticket"
Prove p → q
If I won the lottery then I have a lottery ticket.
Contrapositive
¬q → ¬p
If I do not have a lottery ticket then I have not won the lottery.
Hypothesis: Assume ¬q is True, "I do not have a lottery ticket"
Conclusion: Prove ¬p is True, "I have not won the lottery"
Proof
¬q is True "I do not have a lottery ticket" assumed True. ¬p is True "I have not won the lottery" by the lottery rules. ¬q is True
¬p is True
¬q → ¬pp → q is True Question 29.2
Give the contrapositive of:
If 3n+2 is odd then n is odd
Contradiction
p is "I won the lottery"
q is "I have a lottery ticket"
Prove p → q
If I won the lottery then I have a lottery ticket.
Hypothesis: Assume p is True, "I won the lottery"
Conclusion: Assume ¬q is True, "I do not have a lottery ticket"
Proof
p is True "I won the lottery" assumed True. ¬q is True "I do not have a lottery ticket" assumed True. ¬p is True "I did not win the lottery" by lottery rules when ¬q "I do not have a lottery ticket". ¬p ^ p Contradiction. ¬q cannot be True. Source of contradiction. q must be True. p is True
q is True
p → q is TrueQuestion 29.3
Give a contradictive proof of:
If 3n+2 is odd then n is odd
p qAssume true:
p "3n+2 is odd"
¬q "n is even"
Show the contradiction that results:
¬p "3n + 2 is even"
Proof of Correctness of ifelse
The algorithm below determines the maximum of two values.
Question 30
 Is the then or else executed for maxOf( 5, 3)?
 What is maxOf( 5, 3)?
Precondition is True (assuming two integers are supplied).
 P: True
procedure maxOf( x, y : integers)
if x > y then maxOf ← x else maxOf ← y
 Q: maxOf ≥ x ^ maxOf ≥ y
p q p → q F F T F T T T F F T T T
Both the True and False case must be proven to produce the same postcondition.
True: { x > y ^ P }
maxOf ← x
{ maxOf ≥ x ^ maxOf ≥ y }False: { !(x > y) ^ P }
maxOf ← y
{ maxOf ≥ x ^ maxOf ≥ y }Proof of True case:
x > y ^ P Assume True on then x > y Simplification Rule of Inference maxOf = x From assignment: maxOf ← x maxOf ≥ y x > y ^ maxOf = x maxOf ≥ x ^ maxOf ≥ y ∴ Q is True, maxOf ≥ x ^ maxOf ≥ y Proof of False case:
!(x > y) ^ P Assume True on else !(x > y) Simplification Rule of Inference y ≥ x !(x > y) maxOf = y From assignment: maxOf ← y maxOf ≥ x y ≥ x ^ maxOf = y maxOf ≥ x ^ maxOf ≥ y ∴ Q is True, maxOf ≥ x ^ maxOf ≥ y
Question 31
 P: True
procedure abs( x : integer)
if x ≥ 0 then abs ← x else abs ← x
 Q: abs = x ^ x ≥ 0 ⊕ abs = x ^ x < 0
p q p → q F F T F T T T F F T T T
Prove the postcondition holds for the ifelse True case:
 Prove True: abs = x ^ x ≥ 0
Hint: if x ≥ 0 then abs ← x is executed
Proof of False case: abs = x ^ x < 0
!(x ≥ 0) ^ P Assume True on else !(x ≥ 0) Simplification Rule of Inference x < 0 x < 0 Ξ !(x ≥ 0) abs = x From assignment: abs ← x abs = x ^ x < 0 is True Conjunction abs = x ^ x ≥ 0 is False x < 0 ∴ Q is True
abs = x ^ x ≥ 0 ⊕ abs = x ^ x < 0
a b a ⊕ b F F F F T T T F T T T T
1.7 Proof Methods and Strategy
Exhaustive Proof and Proof by Cases
To prove
(p_{1} v p_{2} v p_{3} v ... v p_{n}) → q
use tautology
(p_{1} → q) ^ (p_{2} → q) ^ (p_{3} → q) ^ ... ^ (p_{n} → q)
that is, prove each n case.
Example  Exhaustive proof
"If positive integer n < 3, then n is the sum of the squares of two integers"
1 and 2 are the only positive integers less than 3. (1 < 3 ^ 2 < 3)
n < 3 → n = x^{2 }+ y^{2}
sum of the squares of two positive integers, x and y.
p_{1} is n = 1 < 3
p_{2} is n = 2 < 3
q is n = x^{2 }+ y^{2}
Show
(p_{1} → q) ^ (p_{2} → q)
( n_{a }= 1 < 3 → n_{a} = x_{a}^{2}+y_{a}^{2}) ^ (n_{b} = 2 < 3 → n_{b} = x_{b}^{2}+y_{b}^{2})
n_{a} = 1 < 3 n_{a} = 0^{2}+1^{2 }= 1 1 < 3 → 0^{2}+1^{2 }= 1 n_{b} = 2 < 3 n_{b} = 1^{2}+1^{2 }= 2 2 < 3 → 1^{2}+1^{2 } = 2 ∴(1 < 3 → 0^{2}+1^{2 }= 1) ^ (2 < 3 → 1^{2}+1^{2 } = 2) (p_{1} → q) ^ (p_{2} → q)
Example  Cases
Theorem: "If x is a nonzero real number, then x^{2} is a positive number."
p is "x is a nonzero real number"
q is "x^{2} is a positive number."
Show
p → q
by showing (p_{1} → q) ^ (p_{2} → q)
Case 1:
p_{1} is x < 0
q is x^{2} > 0
Show
p_{1} → q
x < 0 Hypothesis p_{1} x^{2 }> 0 x^{2}, the product of two negative reals, is positive q is True
∴p_{1} → q x < 0 → x^{2 }> 0
Case 2:
p_{2} is x > 0
q is x^{2} > 0
Show
p_{2} → q
x > 0 Hypothesis p_{2} x^{2 }> 0 x^{2}, the product of two positive reals, is positive q is True
∴p_{2} → q x > 0 → x^{2 }> 0 p → q proven by proving cases (p_{1} → q) ^ (p_{2} → q)
Existence Proofs
Asserts that at least one x exists such that P(x) is True.
∃P(x)
Example  Constructive existence proof
Show:
There exist n < 0 where n^{2} > 0.
∃n<0 (n^{2} > 0)
Solution:
n = 3
3^{2} = 9
Example  Constructive existence proof
Show:
There exist three consecutive integers where the sum of the squares of the first two are equal to the square of the third.
∃x∃y∃z P(x, y, z) (y = x + 1 ^ z = y + 1 ^ x^{2 }+ y^{2} = z^{2})
Solution:
3, 4, 5 are consecutive integers where 3^{2 }+ 4^{2} = 5^{2}
P(3, 4, 5) is
4 = 3 + 1 ^ 4 is consecutive with 3
5 = 4 + 1 ^ 5 is consecutive with 4
3^{2 }+ 4^{2} = 5^{2} = 25