1
$\begingroup$

The problem: Prove that $p↔q$ is logically equivalent to $(p∧q)∨(¬p∧¬q)$.

Work so far:

$p↔q≡(p→q)∧(q→p)$

$≡(¬p∨q)∧(¬q∨p)$

$≡(¬p∨q)∧(p∨¬q)$ by communicative Law

My question: I was thinking I could use the distributive law for the final step, but the way they show it in the book (Discrete Mathematics and its Applications 7ed by Kenneth H. Rosen) it seems it's only applicable for

$(p∨(q∧r)≡(p∨q)∧(p∨r)$ or $(p∧(q∨r)≡(p∧q)∨(p∧r)$.

Am I going about this correctly so far?

v/r

$\endgroup$
2
  • $\begingroup$ So far so good. The distributive law will get you to the final answer. I am not sure exactly what the line showed in your textbook is referring to. But it is safe to say it does not restrict the applicability of the distributive law. $\endgroup$
    – user400188
    Feb 4, 2017 at 2:20
  • $\begingroup$ The textbook line seems to be two different relations that are shortcuts in simplifying logic. $\endgroup$
    – user400188
    Feb 4, 2017 at 2:21

1 Answer 1

0
$\begingroup$

In continuation of your worked answer:

p↔q≡(p→q)∧(q→p)

≡(¬p∨q)∧(¬q∨p)

≡(¬p∨q)∧(p∨¬q) by communicative Law

By the distributive law:

$p\bar p\lor \bar p\bar q\lor pq\lor q\bar q$

≡ $\bar p\bar q\lor pq$

Thus $p\leftrightarrow q$ ≡ $\bar p\bar q\lor pq$ is proven.

From your textbook: the relations ($\ref{1}$) and ($\ref{2}$) are simply shortcuts for simplifying expressions.

(p∨(q∧r)≡(p∨q)∧(p∨r)$\tag{1}\label{1}$

(p∧(q∨r)≡(p∧q)∨(p∧r)$\tag{2}\label{2}$

They can be proved via a truth table, karnaugh map or by expanding them.

Interestingly, we are using $\equiv$ (which in logic, has the same meaning as $\leftrightarrow$) to prove $\equiv$ itself. This does not invalidate the proof though.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .