Propositional Logic
Proof of Identities
Subjects to be Learned
- Proving identities using truth table
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