1
$\begingroup$

I need to prove that the expression $(p\leftrightarrow q) \wedge (q\leftrightarrow r) \rightarrow (p\leftrightarrow r) $ is a tautology, I have managed to simplify it down to the expression $pr+p'r'+pq'+p'q+rq'+r'q$ or alternatively $(p\land r)\lor(\lnot p\land \lnot r) \lor (p\land \lnot q)\lor(\lnot p\land q)\lor(r\land \lnot q)\lor(\lnot r\land q) $ . But I haven't been able to show that it is a tautology without using a truth table. How can I simplify it further?

$\endgroup$
11
  • 1
    $\begingroup$ What do the dashes in the superscript mean? $\endgroup$ Commented Jan 30, 2022 at 19:23
  • $\begingroup$ Thanks for pointing it out, they mean complement. I'll edit it to remove the dashes from the last expression $\endgroup$ Commented Jan 30, 2022 at 19:24
  • $\begingroup$ Why don't you use the table of truth? $\endgroup$
    – Essaidi
    Commented Jan 30, 2022 at 19:29
  • $\begingroup$ I agree. I tried simplifying it. But that probably just makes it more difficult or complex. $\endgroup$ Commented Jan 30, 2022 at 19:33
  • $\begingroup$ I verified it using a truth table but I just want to try and prove it without a truth table $\endgroup$ Commented Jan 30, 2022 at 19:33

1 Answer 1

1
$\begingroup$

Note that $p = p1 = p(q+q')=pq+pq'$

We can use this to 'split' all your $6$ terms:

$pr+p'r'+pq'+p'q+rq'+r'q=$

$prq+prq'+p'r'q+p'r'q'+pq'r+pq'r'+p'qr+p'qr'+rq'p+rq'p'+r'qp+r'qp'$

Reorder each term alphabetically:

$pqr+pq'r+p'qr'+p'q'r'+pq'r+pq'r'+p'qr+p'qr'+pq'r+p'q'r+pqr'+p'qr'$

And reorder the 12 terms:

$pqr+pqr'+pq'r+pq'r+pq'r+pq'r'+p'qr+p'qr'+p'qr'+p'qr'+p'q'r+p'q'r'$

Remove duplicates:

$pqr+pqr'+pq'r+pq'r'+p'qr+p'qr'+p'q'r+p'q'r'$

And put them back together:

$$pqr+pqr'+pq'r+pq'r'+p'qr+p'qr'+p'q'r+p'q'r'=$$

$$pq+pq'+p'q+p'q'=$$

$$p+p'=$$

$$1$$

$\endgroup$

You must log in to answer this question.

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