Two statements are said to be logically equivalent if they have the same truth values for every input value.

Showing Equivalence

Using Truth Tables

Draw the truth tables for both statements and check if they are equal (for complex statements this typically takes too long)

Using Laws to Change One Statement into the other

1. State the theorem being proved
2. Indicate the beginning of the proof by Proof:
3. Start with one side and work towards the other, one step at a time, justifying each step (simplify the more complicated statement, instead of trying to complicate the simpler one)
4. Indicate the end of the proof by QED (Quod erat demonstrandum) or the symbol .

Examples

Using a Sequence of Logical Equivalences Prove that

Using a Sequence of Logical Equivalences Prove that