I have to find a formula equivalent to $A \leftrightarrow B$ using just $\neg$ and $\rightarrow$ symbols. This is what I have tried, but from the truth table that I made, it seems not to be correct..

$(P \rightarrow Q) \land (Q \rightarrow P)$

$\neg(\neg(P \rightarrow Q) \lor \neg(Q \rightarrow P))$

Now suppose:

A = $\neg(P \rightarrow Q)$ % left side of the internal OR

B = $\neg(Q \rightarrow P)$ % right side of the internal OR

Now we have:

$\neg(A \lor B)$ by conditional equivalence... maybe the error is here.

$\neg(\neg A \rightarrow B)$

Now I replace again A and B with their real values:

$\neg(\neg(\neg(P \rightarrow Q)) \rightarrow \neg(Q \rightarrow P))$ by double negation

$\neg((P \rightarrow Q) \rightarrow \neg(Q \rightarrow P))$

If I am not wrong, the truth table of the above expression is:

P  Q
T  T       F
T  F       F
F  T       T
F  F       F

Where am I wrong?


The answer you get is correct; the truth table you computed is not exactly right. When $P,Q$ both true, $P\to Q$ is true and $\neg(Q\to P)$ is false, so $((P\to Q)\to\neg(Q\to P))$ is false and the negation is true.

Similarly, you probably made a mistake when $P$ false and $Q$ true and likewise when $P$ and $Q$ both false.

  • $\begingroup$ Yes, I have just noticed I did not consider the $\neg$ of the right $\rightarrow$ side expression. Thank you anyways! $\endgroup$ – nbro Oct 9 '14 at 21:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.