## Proof of Implications

### Subjects to be Learned

• Proving implications using truth table
• Proving implications using tautologies

### Contents

1. All the implications in Implications can be proven to hold by constructing truth tables and showing that they are always true.

For example consider the first implication "addition":  P  (P  Q).
To prove that this implication holds,  let us first construct a truth table for the proposition P  Q.

Q (P  Q)
F
T
F
T

Then by the definition of ,   we can add a column for P  (P  Q) to obtain the following truth table.

Q (P  Q)  (P  Q)
F
T
F
T

The first row in the rightmost column results since P is false,  and the others in that column follow since (P  Q) is true.

The rightmost column shows that P  (P  Q) is always true.

2. Some of the implications can also be proven by using identities and implications that have already been proven.

For example suppose that the identity "exportation":
[(X Y) Z] [X (Y Z)] ,
and the implication "hypothetical syllogism":
[(P Q) (Q R)] (P R)
have been proven. Then the implication No. 7:
(P Q) [(Q R) (P R)]
can be proven by applying the "exportation" to the "hypothetical syllogism" as follows:

Consider   (P Q) ,  (Q R)  , and   (P R)   in the "hypothetical syllogism" as X,   Y  and   Z  of the "exportation", respectively.
Then since   [ (X Y ) Z ] [ X ( Y Z ) ]   implies   [ ( X Y ) Z ] [ X ( Y Z ) ] ,   the implication of No. 7 follows.

Similarly the modus ponens (implication No. 3) can be proven as follows:
Noting that ( P Q ) ( P Q ) ,
P ( P Q )
P ( P Q )

( P P ) ( P Q )     ---   by the distributive law
F ( P Q )
( P Q )
Q

Also the exportation (identity No. 20),   ( P ( Q R ) )     ( P Q ) R )   can be proven using identities as follows:
( P ( Q R ) )     P ( Q R )
P ( Q R )
( P Q ) R
( P Q ) R
( P Q ) R

3. Some of them can be proven by noting that a proposition in an implication can be replaced by an equivalent proposition without affecting its value.

For example by substituting ( Q P ) for ( P Q ) , since they are equivalent being contrapositive to each other, modus tollens (the implication No. 4): [ ( P Q ) Q ]   P , reduces to the modus ponens: [ X ( X Y ) ] Y.   Hence if the modus ponens and the "contrapositive" in the "Identities" have been proven, then the modus tollens follows from them.

Next -- Why Predicate Logic ?

Back to Schedule