# Chapter 1 Logic and Proofs

Modified

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Rosen text Web site learning resources, requires registration.

http://highered.mcgraw-hill.com/classware/selfstudy.do?isbn=0072880082 - Extra examples with solutions, self-assessments, 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

1. This course is C251, Ballroom Dancing.

2. I paid my taxes by sending a check for \$30,000.

Examples that are not propositions

1. What is your name?                                                                                Not declarative.

2. I paid my taxes by sending a check for x + 1 dollars.                              Neither True nor False, x is undefined.

Question 1 - Which are propositions?

1. The sky is blue.

2. 2 + 2 = 3.

3. No smoking.

4. 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?

1. Today is Monday.

2. 2 + 2 < 3

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"

1. Express p ^ q in English.

"Today is Tuesday" and "I am in the Ball Room dancing class"

2. Which row of the truth table matches the p and q values right now?

p   q     p ^ q
T   F        F

3. What is the truth value of p ^ q?

F

Question 3:

p is “It is hot outside”            q is “It is snowing

1. Express p ^ q in English.

2. Which row of the truth table matches the p and q values at this moment in time?

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

1. Express p v q in English.

"Today is Tuesday" or "I am in the Ball Room dancing class"

2. Which row of the truth table matches the p and q values right now?

p   q     p v q
T   F        T

3. What is the truth value of p v q?

T

Question 4

p is “It is below freezing”            q is “Today is Monday"

1. p v q as English sentence.

2. Which row of the truth table matches the p and q values at this moment in time?

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

1. p → q in English?

If "Today is Tuesday"  then  "I am in the Ball Room Dancing class"

2. Which row of the truth table matches the p and q values at this moment in time?

p   q     p → q
T   F        F

3. p → q truth value?

F

Question 5.1

p is “I win a million dollars”            q is “I give you a million dollars"

1. p → q as English sentence.

2. Which row of the truth table matches the p and q values at this moment in time?

3. 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.

 pI win a million dollars q I give you a million dollars p → qIf I win a million dollars then I give you a million dollars T T T T F F F T T F F T

Example

p 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.

 pI am in C251 q 2+2=5 p → qIf I am in C251 then2+2=5 T I am in C251 T 2 + 2 = 5 T T I am in C251 F 2 + 2 = 5 F F I am in C251 T  2 + 2 = 5 T F  I am in C251 F 2 + 2 = 5 T

Question 5.2 - Conditional   p q

p is “It is Sunday"            q is “I eat grass hoppers for lunch”

1. Express as English sentence.

2. 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 = T If I am in C251 then it is Monday q → p "It is Monday" → "I am in C251" T → T = T If it is Monday then I am in C251 ¬q → ¬p "It is NOT Monday" → "I am NOT in C251" F → F = T If it is NOT Monday then I am NOT in C251 ¬p → ¬q "I am NOT in C251"  → "It is NOT Monday" F → F = T If 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 p is “It is below freezing” q is “It is snowing Express as English sentence.   What is the truth value? Question 7 - Contrapositive   ¬q → ¬p p is “It is below freezing” q is “It is snowing Express as English sentence.   What is the truth value? Question 8 - Inverse        ¬p → ¬q p is “It is below freezing” q is “It is snowing Express as English sentence.   What is the truth value?
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 dollars q I give you a million dollars p ↔ q I win a million dollars if and only if I give you a million dollars T I win a million dollars T I give you a million dollars T T I win a million dollars F I give you a million dollars F F I win a million dollars T I give you a million dollars F F I win a million dollars F I give you a million dollars T

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 8-bit ASCII code representation for the letter 'A'

1111

is the 4-bit 2's complement representation for -1

1000 0000 0000 0000

is 16-bit binary value corresponding to 3276810

 Truth Value Bit T 1 F 0

Definition

 Bit operations extend bit operations to bit strings.

Example

 AND OR XOR 1101 ^ 0100   0100 1101 v 0100   1101 1101 ⊕  0100   1001 ⊕ 0100   1101

Note 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

1. variable "x"

2. 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 x4.

Truth values of:

1. P(0)

2. P(4)

3. 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:

1. P(0, 4)

2. P(4, 4)

3. 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}

1. ∀x P(x)

2. ∀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 }

1. ∀x ( P(x) ^ Q(x) )

2. ∀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:

1. ∀x ( C(x) → F(x) )

2. ∀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 }

1. ∃x P( x )

2. ∃x Q( x )

3. ∃x( P( x ) ^ Q( x ) )

4. ∃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:

1. ∃x ( C(x) → F(x) )

2. ∃x (¬F(x) → ¬C(x) )

Quantifiers with Restricted Domains

∀x < 0 (x2 > 0)

For all real numbers x < 0 such that x2 > 0

which is True.

Question 20.2

1. ∃x < 0 (x2 > x) says what in English?

2. 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 Suppose ∀x ( P(x) ^ Q(x) ) is True  Then for any a in domain P(a) ^ Q(a) is True  So P(a) is True and Q(a) is True for any a in domain  Therefore ∀x P(x) is True  and  ∀x Q(x) is True  Meaning that ∀x P(x) ^ ∀x Q(x) is True Suppose ∀x P(x) ^ ∀x Q(x) is True  Then ∀x P(x) is True and ∀x Q(x) is True  Then for any a in domain P(a) is True and Q(a) is True  So P(a) ^ Q(a) is True for any a in domain  Meaning that ∀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

1. ∃x ( x = 2)

¬∃x ( x = 2)  Ξ   ∀x ¬( x = 2)   Ξ   ∀x ( x ≠ 2 )

2. ∀x (x2 > x)

¬∀x (x2 > x)  Ξ  ∃x ¬( x2 > x )   Ξ   ∃x ( x2 ≤ x )

3. ∃x ( x2 = 2)

¬∃x (x2 = 2)   Ξ   ∀x ¬( x2 = 2 )   Ξ   ∀x ( x2 ≠ 2 )

 ¬∀x P(x)  Ξ  ∃x ¬P(x)

 ¬∃x Q(x)  Ξ ∀x ¬Q(x)

Question 21

1. ¬∀x ( x = x2 )   Ξ

2. ¬∃x ( x2 < 0 )  Ξ

3. ∃x ¬( x2 > 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.

1. p v q  Ξ

2. ∃x( P( x ) v Q( x ) )  Ξ

3. p → q  Ξ

4. ∀x( P( x ) → Q( x ) )  Ξ

Translating from English into Logical Expressions

See http://highered.mcgraw-hill.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

1.4 Nested Quantifiers

Introduction

Example

1. ∃y (1 + y = 0) is True for y = -1

2. ∃x ∃y (x + y = x * y) is True for the pair y = 0, x = 0

3. ∀x ∃y (x + y = 0) is True for y = -x

4. ∃x ∀y (x * y = 0) is True for x = 0 and all y

5. ∀y ∃x (x * y = 0) is True for x = 0 and all y

6. ∀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.

1. P(2, R)

2. ∀y P(2, y)

3. ∀x ∀y P(x, y)

4. ∃x ∃y P(x, y)

5. ∀x ∃y P(x, y)

6. ∃y ∀x P(x, y)

7. ∀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.

1. ¬∀x (x = 1)  Ξ  ∃x ¬(x = 1)  Ξ  ∃x (x ¬= 1)

2. ¬∃x (x > 2x)  Ξ  ∀x ¬(x > 2x)  Ξ  ∀x (x 2x)

3. ∃x ∀y ¬(xy = 1)  Ξ  ∃x ∀y (xy ¬= 1)

4. ∃x ¬∃y (xy = 1)  Ξ  ∃x ∀y ¬(xy = 1)  Ξ  ∃x ∀y (xy ¬= 1)

5. ¬∀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
1. ∃y Q(2, y) Ξ T

2. ¬∃y Q(2, y)  Ξ ∀y ¬Q(2, y) Ξ F

3. ∀x ∃y Q(x, y)  Ξ T

4. ¬∀x ∃y Q(x, y)  Ξ ∃x ¬∃y Q(x, y)  Ξ ∃x ∀y ¬Q(x, y)  Ξ F

5. ∃y ∀x ¬Q(x, y)  Ξ F

6. ¬∃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.

1. ∃y P(2, y)  Ξ

2. ¬∃y P(2, y)  Ξ

3. ¬∃x P(x, R)  Ξ

4. ∀x ∃y P(x, y)  Ξ

5. ¬∀x ∃y P(x, y)  Ξ

6. ¬∀y ∃x P(x, y)  Ξ

7. ¬∃x ∃y P(x, y)  Ξ

8. ¬∃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_______ ∴ p True premise______________ ∴ True conclusion

If p is True then p is True.

 p p p → p F F T T T T

Example - Conjunction

 pq_______ ∴p ^ q True premiseTrue premise___ ∴True conclusion

If 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 → qp_____ ∴q True premiseTrue premise___ ∴True conclusion

Know 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 → qp_____ ∴q True premiseTrue premise___ ∴True conclusion

Example

 4 > 2 → 42 > 224 > 2                                                 ∴can conclude 42 > 22 is True p → qp_____ ∴q True premiseTrue 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 → 42 > 22 p             q T T T T T

Example

 2 > 4 → 22 > 42 2 > 4                                                 ∴cannot conclude 22 > 42 is True p → q p _____ ∴q True premise False premise ___ ∴False conclusion

Because one of the premises, p, is False, the conclusion is False.

Invalid inference rules

Example

 p → q¬p_____ ∴q True premiseTrue 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 → 22 > 42 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_____ ∴¬p True premiseTrue 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

 "You buy a lottery ticket" "You win a million dollars"                                                 ∴"You buy a lottery ticket" ^ "You win a million dollars" p q_____ ∴p ^ q
 "You buy a lottery ticket" ^ "You win a million dollars"                                                ∴"You win a million dollars" p ^ q_____ ∴q
 "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
 3 = 4 v 5 < 10¬(3=4) v 9 < 0                                                ∴5 < 10 v 9 < 0 p v q¬p v r_____ ∴q v r

Note 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?

 Alice is a math major.  Alice is a CS major.∴ Alice is a CS and math major.   Alice is a math and CS major. ∴ Alice is a CS major   If it snows today then school will close. School is not closed. ∴ It did not snow today.   It snowed today. If it snowed today then school will close. ∴ School is closed.   If it is cold today then it snowed today. If it snowed today then school will close. ∴ If it is cold today then school will close.   Alice swims or runs. Alice does not swim or Alice skis. ∴ Alice runs or skis.

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.

Show Conclusion

"We will be home by sunset"

 ¬p ^ q___∴ ¬p Simplification "It is not sunny this afternoon" ^ "It is colder than yesterday"___∴"It is not sunny this afternoon" ¬pr → p___∴¬r Modus tollens "It is not sunny this afternoon""We will go swimming" → "It is sunny this afternoon"___∴"We will not go swimming" ¬r → s¬r___∴ s Modus ponens "We will not go swimming" → "We will take a canoe trip""We will not go swimming"___∴"We will take a canoe trip" s → ts___∴ t Modus ponens "We will take a canoe trip" → "We will be home by sunset""We will take a canoe trip"___∴"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 r

Example

Given the following are True:

(p ^ q) v r
r → s

 (p ^ q) v r   Ξ   (r v p) ^ (r v q) Distributive LawBoth (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 s By resolution      p v s is True
 p 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 → qq_____ ∴p True premiseTrue premise___∴invalid conclusion

Not 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_____ ∴ ¬q True premiseTrue premise___∴invalid conclusion

Not 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?

 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?

1. x P(x)
∴   P(c)

2. C(c) ^ ¬B(c)                           p ^ q  by Simplification
∴   C(c)                                 ∴ p

3. x ((P(x) ^ Q(x))                   x identical for P(x) ^ Q(x)
∴ P(c) ^ Q(c)

4. ∀x (P(x) → Q(x))
∴   P(c) → Q(c)

5.        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

1. ∃x (C(x) ^ ¬B(x))

2. ∀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 a C(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 a C(a) C(a) → P(a) P(a) Modus ponensP(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:

1. write separate specifications for the code (e.g. pre and post conditions)

2. 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.

Pre and Postconditions

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 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

1. For the algorithm above, does x = 1 ^ y = 3 → z = 4?

2. What other values of x and y result in z = 4?

3. Did our proof ensure those other preconditions produce the postcondition is True, z=4?

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

1. p is "n is odd"             n = 2k + 1

2. q is "n2 is odd"            n2 = (2k + 1)2

Prove

"If n is odd, then n2 is odd"

"n is odd" → "n2 is odd"

p → q

Hypothesis:

p assumed True

"n is odd"                n = 2j + 1

Conclusion:

q, must show to be True

"n2 is odd"               n2 = 2i + 1

 n = 2j + 1 p is True, n is odd. (n)2 = (2j + 1)2 Square both sides, to show "n2 is odd" = (4j2 + 4j + 1) Multiply = 2(2j2 + 2j) + 1 Factor = 2(2j2 + 2j) + 1 q is True, n2 is odd n2 = 2i+1 i = 2j2 + 2j ∴ n2 is odd ∴ p is True    q is True                  ∴ p → q is True

Assumed p, "n is odd" to be True.

Proved by algebra and odd definition, with p True, q is "n2 is odd" to be True.

"n is odd" → "n2 is odd"

 p is True    q is True∴ p → q is True "n is odd" is True          "n2 is odd" is True               ∴ "n is odd" → "n2 is odd" is True
 n is odd n2 is odd n is odd → n2 is odd p q p → q F F T F T T T F F T T T

Question 26.0

Propositions

1. p is "n is even"              n = 2k

2. q is "n2 is even"            n2 = 2k

Prove

"If n is even, then n2 is even"

"n is even" → "n2 is even"

p → q

Hypothesis p assumed True

"n is even"                n = 2j

Conclusion q, must show to be True

"n2 is even"               n2 = 2i

 n = 2j p is True, n is even. (n)2 = ______________ a. Square both sides = ______________ b. Multiply = ______________ c. Factor out 2, e.g. 6x2 = 2*(3x2) = ______________ e. q is True, n2 is even n2 = 2i i =  _____________ f. ∴ n2 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 ← n2;  return z;} { Q: z is odd }
 Assume preconditions True{ P: n is odd } int square ( int n ) {  z ← n2;  return z;} Prove algorithm ensures postcondition True{ Q: z is odd }

Proof

 n is odd P is True n = 2j+1 Definition of odd n2 = (2j+1)2 From z ← n2 = 4j2+4j + 1 Multiply = 2(2j2+2j) + 1 n2 odd for k = 2j2+2j z = n2 z ← n2 z is odd P is True   n is odd   Q is True   z is odd ∴ P → Q

Question 26.1

Redo the proof for:

 { P: n is even }int square ( int n ) {  z ← n2;  return z;} { Q: z is even }
 n is even P is True n = ____________ a. Definition of even n2 = ___________ b. Square both sides = ___________ c. Multiply = ___________ d. n2 is even for k =  ________ e. z = n2 ______________ 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 + 1

Show q is True

"a + b is even."

 a = 2i + 1 b = 2j + 1 p, hypothesis, is True, a and b are odd a + 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 evena and b odd → a + b even ∴ q is True     p is True ∴ p → q is True

Question 26.2

If a and b are even then a + b is even.

1. What is the hypothesis, p?

2. What is the conclusion, q?

3. Give a direct proof similar to above.

 a = ______ i. b = ______ ii. p, hypothesis, is True, a and b are even a + b = ________________ iii. Substitution for a and b = ________________ iv. Addition = ________________ v. Factorq is True a + b = __________ vi. for k =  __________ vii. ∴a + b is evena and b even → a + b even ∴ q is True     p is True ∴ p → q is True

Definition 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 n3 + 5 is odd then n is even."

p is "n3 + 5 is odd."

q is "n is even."

Contrapositive

¬q → ¬p

"If n is not even, then n3 + 5 is not odd."

"If n is odd, then n3 + 5 is even."

¬q is "n is odd."

¬p is "n3 + 5 is even."

Prove

"If n is odd, then n3 + 5 is even."

¬q → ¬p

Hypothesis ¬q assumed True

"n is odd", n = 2j + 1

Show ¬p True

"n3 + 5 is even"

 n = 2j+1 ¬q is True, n is odd. n3 + 5 = (2j + 1)3 + 5 Substitute 2j + 1 for n = 8j3 + 12j2 + 6j + 6 Multiply = 2(4j3 + 6j2 + 3j + 3) Factor n3 + 5 = 2(4j3 + 6j2 + 3j + 3) ¬p is True n3 + 5 = 2k is even ∴"If n is odd, then n3 + 5 is even." ∴ ¬p is True    ¬q is True ∴ ¬q → ¬p ∴"If n3 + 5 is odd, then n is even." p → q Ξ ¬q → ¬p by contraposition

Question 27

If n2 is an odd integer then n is an odd integer.

p is "n2 is an odd integer"
q is "n is an odd integer"

1. What is the contraposition in English, ¬q → ¬p?

2. What is the hypothesis, ¬q?

3. What is the conclusion, ¬p?

4. 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

Direct proof assumes hypothesis is True and using rules of inference shows theorem is True.

 ∴ p     q  ∴ p → q

Contradiction 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

Following are three different proofs by contradiction of same theorem and one by use of contrapositive.

Premise

p is x2 + x - 2 = 0

q is x ≠ 0

Prove

"If x2 + x - 2 = 0 then x ≠ 0"

x2 + x - 2 = 0 → x ≠ 0

p → q

*Example 1

Assume

Hypothesis:

p is True, x2 + 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: x2 + x - 2 ≠ 0

Proof

 x2 + x - 2 = 0 Assumption p x = 0 Assumption ¬q x2 + x - 2 = 02 + 0 - 2 Substitute x=0 = -2 Have shown ¬p      x2 + x - 2 ≠ 0 x2 + x - 2 = -2 Contradiction of p: x2 + x - 2 = 0 ¬p ^ p Result of assuming ¬q True, x=0∴ q must be true ∴x2 + x - 2 = 0 → x ≠ 0 p  q      ∴p → q

By assuming:

p: x2 + x - 2 = 0

¬q: x = 0

¬p: x2 + x - 2 ≠ 0

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 x2 + 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 x2 + x - 2 = 0

q is x ≠ 0

Prove

x2 + x - 2 = 0 → x ≠ 0

p → q

Assume:

Hypothesis: p is True, x2 + x - 2 = 0

Conclusion: ¬q is True, x = 0.

Derive contradiction of a known fact.

Proof

 x2 + x - 2 = 0 Assumption of hypothesis p True 02 + 0 - 2 = 0 Substituting into p,     assumption ¬q: x = 0 -2 = 0 Contradiction of known fact,     showing ¬p is True ∴x2 + x - 2 = 0 → x ≠ 0 Assuming p and ¬q both True leads to contradiction p ^ ¬p, therefore q is True. ∴x2 + x - 2 = 0 → x ≠ 0 p  q      ∴p → q

*Example 3

Premise

p is n2 is even

q is n is even

Prove

n2 is even → n is even

p → q

Assume:

Hypothesis: p is True, n2 is even

Conclusion: ¬q is True, n is odd.

Derive contradiction of a known fact.

Proof        n2 is even → n is even

 n = 2i+1 Assumptions      p: n2 is even   ¬q: n is odd n2 = (2i+1)2 = 4i2+4i+1 = 2(2i2+2i) + 1 n2 is odd, ¬p p ^ ¬p cannot be True ∴ n2 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 → q

Question 28

If n2 is an odd integer then n is an odd integer.

1. What is the hypothesis, p?

2. What is the conclusion, q?

3. What is ¬q?

4. What is ¬p?

5. Prove by contradiction, p → q.

Hint: Assume p and ¬q are True, show that assuming ¬q results in ¬p.

Proof        n2 is odd → n is odd

 n = ______________ i. Assumption      p: n2 is odd   ¬q: n is ____________ ii. n2 = ______________ iii. = ______________ iv. n2 is ______________, ¬p is True                    v. p ^ ¬p ∴ n2 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 x2 + x - 2 = 0

q is x ≠ 0

Assume:

Hypothesis: p is True, x2 + x - 2 = 0

Conclusion: ¬q is True, x = 0.

Proof

 x2 + x - 2 = 0 Assumption of hypothesis p x2 + x = 2 Add 2 to both sides 02 + 0 = 2 Substituting assumption ¬q, x = 0 0 = 2 p: x2 + x - 2 = 0 False assuming ¬q, x = 0¬p is True ∴x2 + 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 x2 + x - 2 = 0

q is x ≠ 0

Prove

"If x2 + x - 2 = 0, then x ≠ 0."

Contrapositive

 p → q Ξ ¬q → ¬p

"If x = 0, then x2 + x - 2 ≠ 0."

x = 0 → x2 + x - 2 ≠ 0

¬q → ¬p

Hypothesis

¬q is True, x = 0.

Show

¬p is True, x2 + x - 2 ≠ 0

Proof

 x = 0 Assumption of hypothesis, ¬q x2 + x - 2 = 02 + 0 - 2 = -2 Substituting x = 0 x2 + x - 2 = -2≠ 0 ¬p is True ∴x = 0 → x2 + x - 2 ≠ 0 ¬q    ¬p          ¬q → ¬p is True ∴x2 + x - 2 = 0 → x ≠ 0 By contrapositive, p → q Ξ ¬q → ¬p

*Example 6

p is "n3 + 5 is odd."

q is "n is even."

"If n3 + 5 is odd, then n is even."

p → q

p is "n3 + 5 is odd."

¬q is "n is odd."

Assume p and ¬q are True, p → ¬q

"If n3 + 5 is odd, then n is odd."

Hypothesis

p is "n3 + 5 is odd."

¬q is "n is odd."

Show

p → q from contradiction

"If n3 + 5 is odd, then n is even."

Proof

 n = 2j+1 ¬q is True, n is odd            (Assumed) n3 + 5 = (2j + 1)3 + 5 Substitute 2j + 1 for n = 8j3 + 12j2 + 6j + 6 Multiply and factor n3 + 5 = 2(4j3 + 6j2 + 3j + 3) n3 + 5 is even                   (Proven) ¬p is True n3 + 5 is odd                     (Assumed) p is True Assuming p and ¬q both True leads to contradiction p ^ ¬p ∴"If n3 + 5 is odd, then n is even." ¬q is False, source of contradiction so q is True p  q      ∴p → q

Counterexamples

Can show ∀x P(x) False by finding one counterexample.

Example

∀x (x2 > 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

 02 + 12 = 1 12 + 12 = 2 ∀x P(x) requires some x2 + y2 = 3 Since x2 + 22 > 3 for any integer x,  -2 < y < 2.Either:     x2 + 12 = 3     x2 + (-1)2 = 3     x2 + 02 = 3 x2 + 12 = 3 implies x2 = 2, x is not an integer x2 + (-1)2 = 3 implies x2 = 2, x is not an integer x2 + 02 = 3 implies x2 = 3, x is not an integer ∀x P(x) is False

Question 29 - Give a counterexample to the statement: "If n2 is positive, then n is positive"

Mistakes in Proofs

p is "n is positive"
q is "n2 is positive"

"If n is positive then n2 is positive", p → q, known to be True.

p                            Assumed True
p → q                     Known True (we proved)
q                            Modus Ponens

Prove

"If n2 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 n2 is positive p → q, known to be True n2 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         ∴p

Summary 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 Trueq is Truep → 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 → ¬p p → q is True

Question 29.2

Give the contrapositive of:

If 3n+2 is odd then n is odd

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 True

Question 29.3

Give a contradictive proof of:

If 3n+2 is odd then n is odd
p                    q

Assume true:

p       "3n+2 is odd"

¬q    "n is even"

Show the contradiction that results:

¬p    "3n + 2 is even"

Proof of Correctness of if-else

The algorithm below determines the maximum of two values.

Question 30

1. Is the then or else executed for maxOf( 5, -3)?

2. 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 if-else True case:

1. 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

(p1 v p2 v p3 v ... v pn) → q

use tautology

(p1 → q) ^ (p2  → q) ^ (p3  → q) ^ ... ^ (pn → 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 = x2 + y2

sum of the squares of two positive integers, x and y.

p1 is n = 1 < 3

p2 is n = 2 < 3

q is n = x2 + y2

Show

(p1 → q) ^ (p2  → q)

( na = 1 < 3 → na = xa2+ya2) ^ (nb = 2 < 3 → nb = xb2+yb2)

 na =  1 < 3 na = 02+12 = 1 1 < 3 → 02+12 = 1 nb = 2 < 3 nb = 12+12 = 2 2 < 3 → 12+12 = 2 ∴(1 < 3 → 02+12 = 1) ^ (2 < 3 → 12+12 = 2)   (p1 → q) ^ (p2  → q)

Example - Cases

Theorem: "If x is a non-zero real number, then x2 is a positive number."

p is "x is a non-zero real number"

q is "x2 is a positive number."

Show

p → q

by showing (p1 → q) ^ (p2  → q)

Case 1:

p1 is x < 0

q is x2 > 0

Show

p1 → q

 x < 0 Hypothesis p1 x2 > 0 x2, the product of two negative reals, is positiveq is True ∴p1 → q x < 0 → x2 > 0

Case 2:

p2 is x > 0

q is x2 > 0

Show

p2 → q

 x > 0 Hypothesis p2 x2 > 0 x2, the product of two positive reals, is positiveq is True ∴p2 → q x > 0 → x2 > 0

p → q proven by proving cases (p1 → q) ^ (p2  → 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 n2 > 0.

∃n<0 (n2 > 0)

Solution:

n = -3

-32 = 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 ^ x2 + y2 = z2)

Solution:

3, 4, 5 are consecutive integers where 32 + 42 = 52

P(3, 4, 5) is

4 = 3 + 1 ^                          4 is consecutive with 3

5 = 4 + 1 ^                          5 is consecutive with 4

32 + 42 = 52 = 25