Propositional Logic

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

P |
Q |
(P Q) |

F |
F |
F |

F |
T |
T |

T |
F |
T |

T |
T |
T |

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

P |
Q |
(P Q) |
P (P Q) |

F |
F |
F |
T |

F |
T |
T |
T |

T |
F |
T |
T |

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

Back to Table of Contents