# How can logical equivalence be derived from this..

(p ∨∼q) ∧ (∼p ∨∼q)

≡ (∼q ∨ p) ∧ (∼q ∨∼p)

by (a)

≡∼q ∨ (p ∧∼p)

by (b)

≡∼q ∨ c

by (c)

≡∼q

by (d)

Therefore, (p ∨∼q) ∧ (∼p ∨∼q) ≡∼q

What are the laws being used in each of the four steps?

Commutative, associative, distributive, identity, negation, double negative, idempotent, universal bound, de morgans, absorption or the negations of t and c.

For $(a)$ you have first used the fact that $\lor$ is commutative. In both brackets the expressions have first been changed to $( \lnot q \lor p)$ and $(\lnot q \lor \lnot p)$.

Then for $(b)$ the author has used the distribution law of the conjunction over the disjunction. That is, $( \lnot q \lor p) \land (\lnot q \lor \lnot p) \equiv ( \lnot q \lor (p \land \lnot p ))$

For $(c)$ the derivation should be obvious since $(p \land \lnot p )$ is a contradiction. All he has done is a substitution.

For $(d)$ I'm not sure how the book defines it. Sometimes this is used as one of the idempotent laws. But either way, you can write a small natural deduction proof to say that $(p \lor c) \equiv p$. For the implication assume $\lnot p$ and then arrive at a contradiction. For the reverse implication just use the introduction of a disjunction.

(a) commutative

(b) distributive

(c) Law of (non-)contradiction (negated on both sides)

(d) identity

although some of these can be named differently depending on the author.