Transcript The Logic of Conditionals

Language, Proof and
Logic
The Logic of Conditionals
Chapter 8
8.1.a
Informal methods of proof
Valid steps:
1. Modus ponens: From PQ and P, infer Q.
2. Biconditional elimination: From P and either PQ or QP, infer Q.
3. Contraposition: PQ  Q P
The method of conditional proof:
To prove PQ , temporarily assume P and derive Q based on that
assumption.
8.1.b
Informal methods of proof
Proving Even(n2)Even(n):
Assume n2 is even. To prove that n is even, assume, for a contradiction,
that n is odd. Then, for some k, n=2k+1. Hence n2=(2k+1)(2k+1)=
=4k2+4k+1=2(2k2+k)+1. Hence n2 is odd, which is a contradiction.
So, n is even.
Proving the same using contraposition:
Assume n is odd. Then, for some k, n=2k+1. Hence n2=(2k+1)(2k+1)=
=4k2+4k+1=2(2k2+k)+1. Hence n2 is odd
8.1.c
Informal methods of proof
Proving biconditionals: To prove a number of biconditionals, try to
arrange them into a cycle of conditionals, and then prove each
conditional.
1. n is even
2. n2 is even
3. n2 is divisible by 4
Cycle: (3)(2)(1)(3)
8.2
Formal rules of proof for  and 
 Elim:
PQ
…
P
…
Q
 Intro:
P
…
Q
PQ
 Elim:
PQ (or QP)
…
P
…
Q
 Intro:
P
…
Q
Q
…
P
PQ
You try it, pages 208, 211
8.3.a
Soundness and completeness
FT --- the portion of F that contains the rules for ,,,,,.
P1,…,Pn -T Q --- provability of Q in FT from premises P1,…,Pn.
CLAIM:
FT is sound and complete with respect to tautological consequence.
Soundness: If P1,…,Pn -T Q, then Q is a tautological consequence of
P1,…,Pn.
So, once you see that Q is not a tautological consequence of P1,…,Pn,
you can be sure that there is no way to FT-prove Q from P1,…,Pn.
Completeness: If Q is a tautological consequence of P1,…,Pn, then
P1,…,Pn -T Q.
So, once you see that Q is a tautological consequence of P1,…,Pn,
you can be sure that there is an FT-proof of Q from P1,…,Pn,
even if you have not actually found such a proof.
8.3.b
Soundness and completeness
Would the system be sound if it had the following rule for
“exclusive OR” ? How about the same rule with the ordinary ?
PQ
P
…
S
Q
…
T
ST
See page 215 for a proof idea for the soundness of FT.