Chapter 1
Logic and Proofs

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter1/self_assessments.html - Chapter 1 self-assessment with answers and explanations .

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter1/extra_examples.html - Extra examples with solutions.

1.1 Propositional Logic

Propositions - A declarative sentence (declares a fact) that is either True or False.

Examples of propositions

1. I paid my taxes.
2. This course is C251, Ballroom Dancing.

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.

 

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

 

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 Monday"            q is "I am in C251 class"

What is p ^ q in English?

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

What is the truth value right now of p ^ q?

Question 3: 

p is “It is warm”            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 C251 class"

p v q in English?

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

p v q truth value?

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

 

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 Monday"                q is "I am in Ball Room Dancing class"

p → q in English?

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

p → q truth value?

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?

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" 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 true 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 If I win a million dollars then 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 do not give you a million dollars	F
F I do not win a million dollars	T I give you a million dollars	T
F I do not win a million dollars	F I do not give you a million dollars	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 definition truth table.

p I am in C251	q 2+2=5	p → q If I am in C251 then 2+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 not in C251	T  2 + 2 ≠ 5	T
F  I am not in C251	F 2 + 2 = 5	T

Question 5.2 - Conditional   p → q

p is “It is below freezing”            q is “It is sunny"

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"                q is "It is Monday"

p → q	"I am in C251"  → "It is Monday"	If I am in C251 then it is Monday
q → p	"It is Monday" → "I am in C251"	If it is Monday then I am in C251
¬q → ¬p	"It is NOT Monday" → "I am NOT in C251"	If it is NOT Monday then I am NOT in C251
¬p → ¬q	"I am NOT in C251"  → "It is NOT Monday"	If I am NOT in C251 then it is NOT Monday

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

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

 

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.

 

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 do not give you a million dollars	F
F I do not win a million dollars	T I give you a million dollars	F
F I do not win a million dollars	F I do not 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 Question 10 for  (p → q) v ¬(p ^ q)

 

Precedence of Operators         ¬ is highest

Question 12 - Parenthesize to the corresponding 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 consistent? That is, are all true at the same time.

"The diagnostic message is stored in the buffer or it is transmitted"

"The diagnostic message is not stored in the buffer"

"The diagnostic message is stored in the buffer, then it is transmitted"

Represent as logic

p is "The diagnostic message is stored in the buffer"

q is "The diagnostic message is transmitted"

p v q is "The diagnostic message is stored in the buffer or it is transmitted"

¬p is "The diagnostic message is not stored in the buffer"

p → q is "The diagnostic message is stored in the buffer, then it is transmitted"

 

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 2

Truths

"Knights always tell the truth"

"Knaves always lie"

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 is "If A is a knight, then B is a knight"

since knights tell the truth, A says "B is a knight.".

q → ¬p is "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 is "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 32768₁₀

 

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

    1001         1001
^ 1110       v 1110
 

1.2 Propositional Equivalences

Important to 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 logically equivalent by completing the table

¬(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 - Proof that one of De Morgan's Laws 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:

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} ∀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:

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

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 < 4" 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 - 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 (x² > 0) says

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

which is true.

 

Question 20

1. ∃x < 0 (x² > 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 is logically equivalent to T denoted by S Ξ 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:

Therefore ∀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) the negation would be:

• "Not everyone in C251 has a cell phone."
   
• "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 ) 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 student 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 (x² > x)

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

    

3. ∃x ( x² = 2)

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

    

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

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

 

Question 21

1. ¬∀x (x = x²)   Ξ
    
2. ¬∃x ( x² < 0)  Ξ
    
3. ∃x ¬( x² > 0)  Ξ

 

 

Example - Use De Morgan's Laws

Show: ¬∀x (P(x) → Q(x))  Ξ  ∃x (P(x) ^ ¬Q(x))

1. ¬∀x (P(x) → Q(x))  Ξ  ∃x ¬(P(x) → Q(x))	by De Morgan's
2. ¬(P(x) → Q(x))  Ξ  P(x) ^ ¬Q(x)	by fifth rule in Table 7, Section 1.2 (below)
3. ¬∀x (P(x) → Q(x))  Ξ  ∃x (P(x) ^ ¬Q(x))	by substituting logically equivalent  ¬(P(x) → Q(x)) in 1. with P(x) ^ ¬Q(x)

Question 22 - Give a logical equivalent

1. p v q  Ξ
    
2. p → q  Ξ
    
3. ∀x( P( x ) → Q( x ) )  Ξ
    
4. ∃x( P( x ) v 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."

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

for every x in {1, 2, 3} for every y in {-5, -4, -3} Q(x, y) is true

Example

• ∃x ∀y Q(x, y)

"There is a x such that for every y, Q(x, y) is true"

The x is the same, ∀y.
 

• ∀y ∃x Q(x, y)

"For every y, there is a 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)

"For every x, for every y, Q(x, y) is true"
 

• ∃x ∃y Q(x, y)

"There is a x and y such that Q(x, y) is true"

 

Question 22

In the questions below P(x, y) is a predicate with domain:

x ∈ { 1, 2 }

y ∈ { R, G }

Table shows P( 1, R ), P( 1, G ) are true, P(x, y) is false otherwise.

P(x, y)	x=1	x=2
y=R	T	F
y=G	T	F

• Translate into English in your head.
   
• Determine the truth value.

1. P(2, G)
    
2. ∀y P(1, 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. ∃x ∀y 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, there exists a smaller integer."

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

Question 23

In the questions below, P(x, y) is a predicate with domain:

x ∈ {1, 2}

y ∈ {R, G}

	x=1	x=2
y=R	T	F
y=G	T	F

• Express so that no negation precedes a quantifier.
   
• Determine the truth value.

1. ∃y P(2, y)
    

2. ¬∃y P(2, y)
    

3. ∃x ∃y (P(x, y) ^ ¬P(x, y))  Ξ
    

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

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

p q _______ ∴p ^ q

true premise true 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 → q p _____ ∴q

true premise true 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 → q p _____ ∴q

true premise true premise ___ ∴true conclusion

 

Example

4 > 2 → 42 > 22 4 > 2                                                 ∴can conclude 42 > 22 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 → 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.

Example

(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

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 < 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. Therefore, Alice is a CS and math major.   Alice is a math and CS major. Therefore, Alice is a CS major   If it snows today then school will close. School is not closed. Therefore, it did not snow today.   It snowed today. If it snows today then school will close. Therefore, school is closed.

 

Using Rules of Inference to Build Arguments

Example

Propositions - may be true or false

• p is "It is sunny this afternoon"
   
• q is "It is colder than yesterday"
   
• r is "We will go swimming"
   
• s is "We will take a canoe trip"
   
• t is "We will be home by sunset"

Premises - assumed to be true

• ¬p ^ q is "It is not sunny this afternoon and it is colder than yesterday"
   
• r → p is "We will go swimming only if it is sunny"
   
• ¬r → s is "If we do not go swimming, then we will take a canoe trip"
   
• s → t is "If we take a canoe trip, then we will be home by sunset.

Conclusion

"We will be home by sunset"

"It is not sunny this afternoon" ^ "It is colder than yesterday" ___ ∴"It is not sunny this afternoon"	¬p ^ q ___ ∴ ¬p	Simplification
"It is not sunny this afternoon" "We will go swimming" →"It is sunny this afternoon" ___ ∴"We will not go swimming"	¬p r → p ___ ∴¬r	Modus tollens
"We will not go swimming"→"We will take a canoe trip" "We will not go swimming" ___ ∴"We will take a canoe trip"	¬r → s ¬r ___ ∴ s	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"	s → t s ___ ∴ t	Modus ponens

 

Resolution - Only rule of inference required, useful for computer implementation of logic solvers (Prolog).

Definition

Clause is a disjunction of variables or their negation.

Resolution can be used as only rule of inference 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 Law Both (r v p) and (r v q) are true
r → s Ξ ¬r v s	Replace with equivalent
r v p ¬r v s _____ p v s	By resolution       p v s is true

 

Resolution Truth Table Proof

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 → q q _____ ∴p

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

Prove that modus tollens is a valid rule of inference. Modus Tollens p q ¬q p → q ¬q ^ (p → q) ¬p ¬q ^ (p → q)  → ¬p F F           F T           T F           T T

¬q  p → q _____ ∴¬p

 

Rules of Inference for Quantified Statements

Universal instantiation

Concludes P(c) is true 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) 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}

∀x P(x) is true

 

Existential instantiation

Concludes some c in domain where P(c) is true 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) when a particular c with P(c) true is known. If we know one c with P(c) true, then ∃x P(x).

P(x) is "x + 1 > 0" where x ∈ { -2, -1, 0 }

P( 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)
         C(c)
    
3. ∃x ((P(x) ^ Q(x))
        P(c) ^ Q(c)
    
4. ∀x (P(x) → Q(x))
          P(c) → Q(c)
    
5.      P(c) ^ Q(c)      
   ∃x ((P(x) ^ Q(x))
    

Example proof

Premises are true

1. ∃x (C(x) ^ ¬B(x))
    
2. ∀x (C(x) → P(x))

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(c)
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)
C(a) C(a) → P(a) P(a)	Modus ponens
¬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)    ∃x P(x)

 

Combining Rules of Inference for Propositions and Quantified Statements

Universal modus ponens

∀x (P(x) → Q(x)) 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)

Given ∀x (P(x) →Q(x)), when ¬Q(a) for a particular a, ¬P(a).

 

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
   
2. prove that the code and the specifications are mathematically equivalent

 

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

A formal specification is written as a logical expression called an assertion.

An assertion describes the state of the program's variables.

Two key assertions are the program's precondition and its postcondition; P and Q respectively.

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

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

For 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 preconditions True imply postconditions True for the code of max:

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

x = 1 ^ y = 3	Assume P is true
z ← x + y	Definition of z
z ← 1 + 3	Substitution of x and y
z ← 4	Addition 1 + 3
z = 4	Q is true by z ← 4
z = 4	∴ P → Q

Question 25.2

1. For the algorithm, 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 values are also valid preconditions?
    
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 = 23 = 2(11) + 1                   k = 11

 

Example direct proof

Propositions

1. p is "n is odd"             n = 2k + 1
    
2. q is "n² is odd"            n² = (2k + 1)²

Prove

"If n is odd, then n² is odd"

"n is odd" → "n² is odd"

p → q

Hypothesis p assumed true

"n is odd"                n = 2j + 1

Conclusion q, must show to be true

"n² is odd"               n² = 2k + 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 = 2k+1 k = 2j2 + 2j.
	∴ n2 is odd	∴ p is true     q is true ∴ p → q is true

Remember, we assumed p, "n is odd" to be true.

We proved by algebra and odd definition, with p true, q is "n² is odd" to be true.

"n is odd" → "n² 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
F	F	T
F	T	T
T	F	F
T	T	T

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
= 4j2+4j + 1	Multiply
= 2(2j2+2j) + 1	n2 odd for k = 2j2+2j
z = n2	z ← n2
z is odd	Q is true ∴ 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 }

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)	Simplification
	= 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 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.
    

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

Example

Prove p → q

"If n³ + 5 is odd then n is even."

p is "n³ + 5 is odd."

q is "n is even."

Contrapositive

¬q → ¬p

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

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

¬q is "n is odd."

¬p is "n³ + 5 is even."

Prove

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

¬q → ¬p

Hypothesis ¬q assumed true

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

Show ¬p true

"n³ + 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."	¬q → ¬p
	∴"If n3 + 5 is odd, then n is even."	p → q Ξ ¬q → ¬p by contraposition

Question 27

If n² is an odd integer then 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

 

Proofs by Contradiction

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

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.

Many variations of proof by contradiction.

 

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: 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		When ¬q, "I do not have a lottery ticket" is true, ¬p, "I did not win the lottery" is true.
¬p ^ p		Contradiction.
¬q cannot be true.		Source of contradiction.
q must be true.
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² + x - 2 = 0

q is x ≠ 0

Prove

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

x² + x - 2 = 0 → x ≠ 0

p → q

Example 1

Assume

Hypothesis: p is true, x² + 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² + x - 2 ≠ 0

Proof

x2 + x - 2	= 0	Assumption p
x2 + x - 2	= 02 + 0 - 2	Assumption ¬q: x = 0
	= -2	Have shown ¬p       x2 + x - 2 ≠ 0
x2 + x - 2	= -2	Contradiction of p: x2 + x - 2 = 0
	∴x2 + x - 2 = 0 → x ≠ 0	p → q

By assuming: p: x2 + x - 2 = 0 ¬q: x = 0 leads to: ¬p: x2 + x - 2 ≠ 0 Contradiction: p ^ ¬p 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 x² + x - 2 = 0

q is x ≠ 0

Prove

x² + x - 2 = 0 → x ≠ 0

p → q

Assume:

Hypothesis: p is true, x² + x - 2 = 0

Conclusion: ¬q is true, x = 0.

Derive contradiction of a known fact.

Proof

x2 + x - 2	= 0	Assumption of hypothesis p
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.

Example

Premise

p is n² is even

q is n is even

Prove

n² is even → n is even

p → q

Assume:

Hypothesis: p is true, n² is even

Conclusion: ¬q is true, n is odd.

Derive contradiction of a known fact.

Proof        n² is even → n is even

n	= 2i+1	Assumption      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
	∴ 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

Question 28

If n² 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. Prove by contradiction, p → q.
   
   Hint: Assume p and ¬q, show assuming ¬q results in ¬p.
    

Definition 1

Even integer n has k such that n = 2k Odd integer n has k such that n = 2k+1

Example 3

Premise

p is x² + x - 2 = 0

q is x ≠ 0

Assume:

Hypothesis: p is true, x² + x - 2 = 0

Conclusion: ¬q is true, x = 0.

                     q is false, 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

Example 4

Premise

p is x² + x - 2 = 0

q is x ≠ 0

Prove

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

Contrapositive

p → q Ξ ¬q → ¬p

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

x = 0 → x² + x - 2 ≠ 0

Hypothesis

¬q is true, x = 0.

Show

¬p is true, x² + 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 5

p is "n³ + 5 is odd."

q is "n is even."

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

p → q

Contradiction

p is "n³ + 5 is odd."

¬q is "n is odd."

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

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

Hypothesis

p is "n³ + 5 is odd."

¬q is "n is odd."

Show

p → q from contradiction

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

Proof

n is odd	Assumption ¬q
If n is odd then n2 is odd and n*n2=n3 is odd"	Product of two odd numbers is odd
n3 + 5 is even	n3 is odd (product of two odds, n*n2) 5 is odd Sum of two odds is even so ¬p.
n3 + 5 is odd	Assumption p.
	Assuming p and ¬q both true leads to contradiction p ^ ¬p
∴"If n3 + 5 is odd, then n is even."	By contradiction, p → q

 

Counterexamples

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

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 n² is positive, then n is positive"

 

Mistakes in Proofs

Prove

q is "n² is positive"

p is "n is positive"

"If n² is positive, n is positive"

q → p

If n is positive then n2 is positive"	Known to be true, p → q
n2 is positive	Assumption q
∴n is positive	False conclusion based on invalid inference rule p → q q         ∴p To show q → p q → p q         ∴p

Summary of Proof Methods

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

 

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

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 true

 

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

Both the true and false case must be proven to produce the same postcondition.

true:   {x > y ^ true}                    maxOf ← x            { maxOf  ≥ x ^ maxOf  ≥ y }

false: { !(x > y) ^ true}                    maxOf ← y           { maxOf  ≥ x ^ maxOf  ≥ y }

Proof of true case:

x > y ^ true	True on then
x > y	Simplification Rule of Inference
maxOf = x	From assignment: maxOf ← x
maxOf  ≥ x ^ maxOf  ≥ y	x > y ^ maxOf = x
	∴ Q is true, maxOf  ≥ x ^ maxOf  ≥ y

Proof of false case:

!(x > y) ^ true	True on else
!(x > y)	Simplification Rule of Inference
maxOf = y	From assignment: maxOf ← y
maxOf  ≥ x ^ maxOf  ≥ y	!(x > y) ^ 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

Prove the postcondition holds for the if-else true case:

1. Prove true:  abs = x ^ x ≥ 0
    
2. Prove false: abs = -x  ^ x < 0

   Hint: if  x ≥ 0 then abs ← x is executed

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₁ v p₂ v p₃ v ... v p_n) → q

use tautology

(p₁ → q) ^ (p₂  → q) ^ (p₃  → 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 positive integers less than 3.        (1 < 3 v 2 < 3)

 n < 3 → n = x² + y²

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

p₁ is n = 1 < 3

p₂ is n = 2 < 3

q is n = x² + y²

Show

(p₁ → q) ^ (p₂  → q)

( n_a = 1 < 3 → n_a = x_a²+y_a²) ^ (n_b = 2 < 3 → n_b = x_b²+y_b²)

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 x² is a positive number."

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

q is "x² is a positive number."

Show

p → q

by showing (p₁ → q) ^ (p₂  → q)

Case 1:   

p₁ is x < 0

q is x² > 0

Show

p₁ → q

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

Case 2:   

p₂ is x > 0

q is x² > 0

Show

p₂ → q

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

p → q proven by proving cases (p₁ → q) ^ (p₂  → 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 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² + y² = z²)

Solution:

3, 4, 5 are consecutive integers where 3² + 4² = 5²

P(3, 4, 5) (4 = 3 + 1 ^ 5 = 4 + 1 ^ 3² + 4² = 5²)