Propositional Logic

Proof of Identities



Subjects to be Learned

Contents

All the identities in Identities can be proven to hold using truth tables as follows. In general two propositions are logically equivalent if they take the same value for each set of values of their variables. Thus to see whether or not two propositions are equivalent, we construct truth tables for them and compare to see whether or not they take the same value for each set of values of their variables.

For example consider the commutativity of :
(P Q) (Q P).

To prove that this equivalence holds, let us construct a truth table for each of the proposition (P Q) and (Q P).

A truth table for (P Q) is, by the definition of ,

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








A truth table for (Q P) is, by the definition of ,

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








As we can see from these tables (P Q) and (Q P) take the same value for the same set of value of P and Q. Thus they are (logically) equivalent.

We can also put these two tables into one as follows:

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










Using this convention for truth table we can show that the first of De Morgan's Laws also holds.

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








By comparing the two right columns we can see that (P Q) and P Q are equivalent.


Next -- Proof of Implications

Back to Schedule
Back to Table of Contents