To prove that two compound propositions are logically equivalent, we need to prove that they have the same truth values.
We can do this in two ways: (1) by creating the truth table for both propositions and comparing the truth values or (2) by using a series of proven logical equivalences that allows concluding the two propositions have the same truth value.
For the second case, we will need the logical equivalences in the following table, and also the logical equivalences related to conditional and biconditional statements.
Let’s examine both approaches.
Using truth tables
The number under the columns is the order in which I created the truth table.
Because p↔ q and (p∧q)∨(¬p∧¬q) have the same truth values (look at columns 3 and 8), they are logically equivalent.
Without using truth tables
p↔ q ≡ (p->q)^(q->p), by biconditional logical equivalences
≡(¬pvq)^(¬qvp), by conditional logical equivalence
≡ ((¬pvq)^ ¬q) v ((¬pvq)^p), by distributive law
≡ (¬q ^ (¬pvq)) v (p ^ (¬pvq)), by commutative law
≡ ((¬q ^¬p) v (¬q^q)) v ((p ^¬p)v(p^q)), by distributive law
≡ ((¬q ^¬p) v F)) v (F v (p^q)), by Negation law
≡ (¬q ^¬p) v (p^q), by Identity law
≡ (p^q) v (¬p^¬q) v by commutative law ∎
Related exercises:
- What are propositional equivalences in Discrete Mathematics?
- Use truth tables to verify these equivalences (Ex 1. pp. 34)
- Show that ¬(¬p) and p are logically equivalent (Ex 2. pp. 34)
- Use truth tables to verify the associative laws (Ex. 4 pp. 34)
- Show that p → q and ¬q → ¬p are logically equivalent (Ex 18 pp 35)
