I have been able to verify this via truth tables but not with logical equivalencies yet. I understand some of the basic principles of logical equivalencies but I cannot seem to get to the end of this problem where one side equals the other.

  • 1
    $\begingroup$ Your question isn't very clear: what logical equivalences are you taking as primitive? The laws of boolean algebras perhaps? $\endgroup$
    – Rob Arthan
    Dec 17, 2020 at 22:03
  • $\begingroup$ @RobArthan logical equivalencies such as De Morgan's Laws, for example. Others might include distributing negation, etc $\endgroup$
    – user863697
    Dec 17, 2020 at 22:07
  • $\begingroup$ Well if you have enough equivalences to show that a formula is equivalent to a disjunctive normal form or a conjunctive normal form, you are pretty well there. $\endgroup$
    – Rob Arthan
    Dec 17, 2020 at 22:12

1 Answer 1


Notice that $A\vee(B\wedge C)\equiv (A\vee B)\wedge(A\vee C)$.

On the left hand side, we have

$\neg(P\leftrightarrow Q)\equiv \neg[(P\to Q)\wedge(Q\to P)]\equiv(P\wedge\neg Q)\vee(Q\wedge\neg P)\equiv[(P\wedge\neg Q)\vee Q]\wedge[(P\wedge\neg Q)\vee\neg P]\\\equiv[(P\vee Q)\wedge(\neg Q\vee Q)]\wedge [(P\vee\neg P)\wedge(\neg Q\vee\neg P)]\equiv(P\vee Q)\wedge(\neg Q\vee\neg P)$

Consider the negation of the right hand side and we have

$\neg[(P\to\neg Q)\wedge(\neg Q\to P)]\equiv(P\wedge Q)\vee(\neg Q\wedge\neg P)$

Now we negate it back

$\neg[(P\wedge Q)\vee(\neg Q\wedge\neg P)]\equiv[\neg(P\wedge Q)]\wedge[\neg(\neg Q\wedge\neg P)]\equiv(\neg P\vee\neg Q)\wedge(Q\vee P)$

Hence it gives the result that we are asked to verify.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy