Propositional Logic

Proof of Implications

Subjects to be Learned


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) 

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)

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 )

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