Formula involving only $\neg$ and $\rightarrow$

Question

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?

score 3 · Accepted Answer · answered Oct 09 '14 at 21:45

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.

Formula involving only $\neg$ and $\rightarrow$

1 Answers1