Chapter 1
Logic and Proofs

 Modified: 

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

 

Variables

Use letters such as p, q, r, ... to represent propositions.

Example

p is "I paid my taxes"

 

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.

 

Definition 2

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?

What is the truth value?

 

Definition 3

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"

What is p v q in English?

What is the truth value?

 

Definition 4

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

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

 

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.

 

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

 

Definition 6

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

 

Truth Tables of Compound Propositions

 

Precedence of Operators

Question

Parenthesize to the corresponding logical operator precedence:

p ^ ¬q V p « q ® r

 

System Specifications

Definition

Consistent when specifications do not contain conflicts that could lead to contradictions.

Question

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"

Solution

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

Complete the following truth table

 p    q   p V q ¬p p ® q
F F      
F T      
T F      
T T      

 

Logic Puzzles

Example - Two

"Knights always tell the truth"

"Knaves always lie"

A says "B is a knight."

B says "The two of us are always opposites."

What are A and B?

Problem

Determine what A and B are, either a knight or a knave.

Solution

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 "B is a knight.".

q ® ¬p is "If B is a knight, then p is a knave", since knights tell the truth "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 "B is a knight" is a lie. This is the inverse of: p ® q

 

Because "Knights always tell the truth" and "Knaves always lie", the implications must all be true, that is consistent.

 

Complete the following truth table to determine what are A and B:

 p    q   ¬p ¬q p ® q q ® ¬p ¬p ® ¬q
F F          
F T          
T F          
T 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
0100
1101		 1101
0100
1001
0100
1101

Note that XOR is its own inverse, particularly useful in computer graphics.

 

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.

Proof logically equivalent: ¬(p v q) Ξ ¬p ^ ¬q

 p    q   ¬p ¬q p v q ¬(p v 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."

 

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

 

Example

Q(x, y) denotes      "x = y + 3"

Q(4, 1) is true        "4 = 1 + 3"

Q(1, 4) is false       "1 = 4 + 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 + 1 > x"

The domain of P(x) is -2, -1, 0

x Î {-2, -1, 0}

P(-2) is "-1 > -2"

P(-1) is "0 > -1"

P(0) is "1 > 0"

"x P(x) is true

 

 Example - Another way of thinking of universal quantification

P(x) is "x + 1 > x"

The domain of P(x) is -2, -1, 0

x Î {-2, -1, 0}

Must show conjunction P(x) is true for all x Î {-2, -1, 0}:

P(-2) ^ P(-1) ^ P(0)

P(x) is                 "x + 1 > x"

P(-2) is true        "-1 > -2"

P(-1) is true        "0 > -1"

P(0) is true          "1 > 0"

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

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

 

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}

Must 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

 

Quantifiers with Restricted Domains

"x < 0 (x2 > 0) says that for all real numbers x < 0, x2 > 0

$x < 0 (x2 > x) says what?

 

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

 

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.

 

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:

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
  1. Suppose "x ( P(x) ^ Q(x) ) is true
     
  2. Then for any a in domain P(a) ^ Q(a) is true
     
  3. So P(a) is true and Q(a) is true for any a in domain
     
  4. Therefore "x P(x) is true  and  "x Q(x) is true
     
  5. Meaning that "x P(x) ^ "x Q(x) is true
  
  1. Suppose "x P(x) ^ "x Q(x) is true
     
  2. Then "x P(x) is true and "x Q(x) is true
     
  3. Then for any a in domain P(a) is true and Q(a) is true
     
  4. So P(a) ^ Q(a) is true for any a in domain
     
  5. Meaning that "x ( P(x) ^ Q(x) ) is true

Therefore "x ( P(x) ^ Q(x)) Ξ "x P(x) ^ "x Q(x)

 

Negating Quantified Expressions

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

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)

  • "Some one in C251 that has a cell phone."
     
  • "There exists at least one person in C251 with a cell phone."

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 everyone in C251, no one has a cell phone."
¬$x Q(x)  Ξ  "x ¬Q(x)

 

Example

  1. "x (x2 > x)

    ¬"x (x2 > x)  Ξ  $x ¬(x2 > x)

    Rewriting:  $x (x2 £ x)

     

  2. $x ( x2 = 2)

    ¬$x (x2 = 2)  Ξ  "x ¬( x2 = 2)

    Rewriting:  "x ( x2 ¹ 2)

 

 

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)

 

 

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

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

The x is the same, "y.

"For every y, there is a x such that Q(x, y) is true"

The x can be different, "y.

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

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

Questions

In the questions below suppose P(x,y) is a predicate and the universe for the variables x is {1,2} and y is {R, G}.

Suppose P(1,R), P(1,G) are true, and P(x, y) is false otherwise.

  x=1 x=2
y=R T F
y=G T F
  • Translate into English.
     
  • Determine the truth value.

  1. "x $y P(x, y)
     
  2. $y "x P(x, y)
     
  3. $x "y P(x, y)
     
  4. $x $y P(x, y)
     
  5. "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) Ξ
     
  2. ¬$x (x > 2x) Ξ
     
  3. $x "y ¬(xy = 1) Ξ
     
  4. $x ¬$y (xy = 1) Ξ
     
  5. ¬"x $y (xy = 1) Ξ
     

Questions

In the questions below suppose P(x,y) is a predicate and the universe for the variables x is {1,2} and y is {R, G}.

Suppose P(1,R), P(1,G) are true, and P(x, y) is false otherwise.

  x=1 x=2
y=R T F
y=G T F
  • Translate into English.
     
  • Determine the truth value.

  1. $x $y (P(x, y) ^ ¬P(x, y))
     

  2. ¬$x $y P(x, y)
     

  3. ¬$x "y ¬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 - Modus ponens

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

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, cannot conclude the conclusion is true.

 

 

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.

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

 

Using Rules of Inference to Build Arguments

Example

Premises - assumed to be true

  • "It is not sunny this afternoon and it is colder than yesterday"
     
  • "We will go swimming only of it is sunny"
     
  • "If we do not go swimming, then we will take a canoe trip"
     
  • "If we take a canoe trip, then we will be home by sunset.

Propositions

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

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

 

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

 

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}

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}

 

Existential instantiation

Concludes some c in domain where P(c) is true given $x P(x) 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(c) is "c + 1 > c" is true where c = -2

 

 

Example proof

Premise

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

 

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

 

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 a consequent.

 

Direct Proof

Assume hypothesis is true and show through valid rules of inference, that the conclusion is true.

 

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)

Odd      n = 23 = 2(11) + 1

 

Example proof

Propositions

  1. P(n) is "n is an odd integer" or n = 2k + 1
     
  2. Q(n) is "n2 is odd" or n2 = (2k + 1)2

Prove

"If n is an odd integer, then n2 is odd"

"n (P(n) ® Q(n))

Hypothesis

"n is an odd integer"

Show (conclusion) is true

"Given any odd integer n, n2 is odd."

P(n)   Assume hypothesis, n is odd: n = 2k + 1
n = 2k + 1 Definition of odd n
n2 = (2k + 1)2 Square both sides
  = (4k2 + 4k + 1) Multiply
  = 2(2k2 + 2k) + 1 Factor
  = 2(2k2 + 2k) + 1 Definition of odd integer = 2k+1.
  \ n2 is odd  

 

Example

  • "a is an odd integer" or a = 2i + 1
     
  • "b is an odd integer" or b = 2j + 1
     

Prove

    "If a and b are odd, then a+b is even"

Hypothesis

"a and b are odd"

Show

"Given any two odd integers, the sum is even."

a = 2i + 1

b = 2j + 1

   Assume hypothesis, a and b are odd
a+b = (2i + 1) + (2j + 1) By definition of odd integer
  = 2i + 2j + 2 Addition
  = 2(i + j + 1) Simplification
  = 2(i+j+1) Definition of even integer, 2k
  \ a+b is even  

 

Proof by Contraposition (or Proof by Contrapositive)

p ® q Ξ ¬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

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

Show

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

n = 2k+1 Assume ¬q, n is odd, n = 2k + 1. 
n3 + 5  = (2k+1)3+5 Substitute 2k+1 for n
  = 8k3 + 12k2 + 6k + 6 Multiply
  = 2(4k3 + 6k2 + 3k + 3) Factor
n3 + 5  = 2(4k3 + 6k2 + 3k + 3) ¬p from definition of 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

 

Proofs by Contradiction

Direct proof shows theorem is true using rules of inference.

Contradiction proof assumes theorem is false; using rules of inference, shows contradiction.

Only source of contraction was assumption that theorem false.

Many variations of proof by contradiction.

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

Premise

p is x2 + x - 2 = 0

q is x ¹ 0

Prove

x2 + x - 2 = 0 ® x ¹ 0

p ® q

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

Example 1

Assume:

Hypothesis, p is true, x2 + x - 2 = 0

Conclusion, q is false, x = 0.

Derive contradiction that p is false: x2 + x - 2 ¹ 0

Proof

x2 + x - 2 = 0 Assumption p
x2 + x - 2 = 02 + 0 - 2 Assumption Øq: x = 0
  = -2 ¬p: x2 + x - 2 = -2
x2 + x - 2 = -2 Contradiction of p: x2 + x - 2 = 0
  \ x2 + x - 2 = 0 ® x ¹ 0 p ® q

By assuming:

Øq, x=0

p, x2 + x - 2 = 0

leads to:

¬p, x2 + x - 2 ¹ 0

Contradiction:

p ^ ¬p

Can conclude:

p ® q is true

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

 

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 that: r = p, ¬r = ¬p

 

Example 2

Prove

x2 + x - 2 = 0 ® x ¹ 0

p ® q

Assume p is true, x2 + x - 2 = 0

Assume q is false, x = 0.

Derive contradiction of a known fact.

Proof

x2 + x - 2 = 0 Assumption of hypothesis
02 + 0 - 2 = 0 Substituting assumption x = 0

-2

= 0 Contradiction of known fact
  \ x2 + x - 2 = 0 ® x ¹ 0 p and ¬q both true leads to contradiction p ^ ¬p

 

Example 3

Assume p is true, x2 + x - 2 = 0

Assume q is false, x = 0.

Derive contradiction as proof develops.

Proof

x2 + x - 2 = 0 Assumption of hypothesis

x2 + x

= 2  
  = 0 + 0 Substituting assumption, x = 0

x2 + x

= 0 Contradicts x2 + x = 2
  \ x2 + x - 2 = 0 ® x ¹ 0 p and ¬q both true leads to contradiction p ^ ¬p

 

Rule of Inference: Proof by Contraposition

Example 4

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

Hypothesis

¬q is true, x = 0.

Show

¬p is true, x2 + x - 2 ¹ 0

Proof

x

= 0 Assumption of hypothesis, ¬q
x2 + x - 2 = 0 + 0 - 2 = -2 Substituting x = 0
x2 + x - 2  ¹ 0 ¬p is true
  \ x = 0 ® x2 + x - 2 ¹ 0 ¬q ® ¬p is true
  \ x2 + x - 2 = 0 ® x ¹ 0 By contrapositive, p ® q Ξ ¬q ® ¬p

 

Example 5

p is "n3 + 5 is odd."

q is "n is even."

p ® q

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

Contradiction

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 is odd Assumption ¬q
If n is odd then n2 is odd and n*n2=n3 is odd" The product of two odd numbers is odd
n3 + 5 = n3 + 5 Identity
5 = (n3 + 5) - n3 Difference of two odd numbers, n3 + 5 and n3, must be even
n3 + 5 is even From above
n3 + 5 is odd Assumption p
  Contradiction from assumption p
p ® q p and ¬q both true leads to contradiction p ^ ¬p
\ "If n3 + 5 is odd, then n is even."  

 

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
There must be some x2+y2 = 3
x2+22 > 3 for any integer x, either x2+12=3 or x2+02=3
x2+12 = 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

Is there a counterexample to the statement: "If n2 is positive, n is positive"

 

Mistakes in Proofs

Prove

q is "n2 is positive"

p is "n is positive"

"If n2 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

 

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)

or prove each n case.

 

Example - Exhaustive proof

"If a positive integer n < 3, then it is the sum of the squares of two integers"

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

(p1 ® q) ^ (p2  ® q) ^ (p3  ® q) ^ ... ^ (pn ® q)

(1 < 3 v 2 < 3) ® Sum of the squares of two integers.

(1 < 3 ® 02+12 = 1) ^ (2 < 3 ® 12+12 = 2)

02+12=1
12+12=2

 

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

p1 ® 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 positive

q is true
\ p1 ® q  

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 positive

q is true
\ p2 ® q  

p ® q proven by proving cases (p1 ® q) ^ (p2  ® q)

 

Existence Proofs

$x P(x) asserts that at least one x exists such that P(x) is true.

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.

Solution:

The numbers are 3, 4, 5

32 + 42 = 9 + 16 = 25 = 52