Transcript Methods of Proof for Boolean Logic

Language, Proof and
Logic
Methods of Proof for
Boolean Logic
Chapter 5
5.0
Beyond truth tables
Why truth tables are not sufficient:
• Exponential sizes
• Inapplicability beyond Boolean connectives
Need: proofs, whether formal or informal.
For informal proofs, it is relevant who your listener is.
This section talks about some informal proof methods.
5.1
Valid inference steps in informal proofs
1. In giving an informal proof from some premises, if Q is already
known to be a logical consequence of some already proven sentences,
then you may assert Q in your proof.
2. Each step should be significant and easily understood (this is where
your audience’s level becomes relevant).
Valid patterns of inference that generally go unmentioned:
• From PQ, infer P
• From P and Q, infer PQ
• From P, infer PQ
(conjunction elimination)
(conjunction introduction)
(disjunction introduction)
5.2
Proof by cases (disjunction elimination)
To prove Q from a disjunction, prove it from each disjunct separately.
“There are irrational numbers b,c such that bc is rational”.
22 is either rational or irrational.
1. If rational, then take b=c= 2, known to be irrational.
2. If irrational, take b=22 and c= 2.
5.3
Indirect proof (proof by contradiction)
Contradiction --- any claim that cannot possibly be true.
Proof of Q by contradiction: assume Q and derive a contradiction.
Proving that “2 is irrational”:
Suppose 2 is rational. So, 2= a/b for some integers a,b. We may
assume at least one of a,b is odd, for otherwise divide both a and b by
their greatest common divisor.
From 2=a/b we find 2=a2/b2. Hence a2=2b2. So, a is even. So, a2 is
divisible by 4. So, b2 is even. So, b is even. Contradiction.
5.4
Arguments with inconsistent premises
Premises from which a contradiction follows are said to be inconsistent.
You can prove anything from such premises!
An argument with inconsistent premises is always valid yet never sound!