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