When considering the question:

Rewrite the following using only the symbols $A, B, \lor, \land, \neg$ : $$\neg(A\Rightarrow B)$$

I do not understand how to interpret this and what method to use to show the statement in a different form. If A and B are statements, should I assume that $A \Rightarrow B$ is true and then look for a false statement?

The answer is $A\land \neg B$

  • 1
    $\begingroup$ Make a truth table or try a bit intuitively to see what would happen. For instance, if $A$ is false, then the implication is true, hence the complete statement is false by the negation symbol. Hence on the righthand side you need $A$ to be true for the statement to be true. So you will have something with $A\wedge ?$. $\endgroup$ – Joffysloffy Jun 13 '14 at 15:39
  • $\begingroup$ Use $(A\Rightarrow B)\Leftrightarrow ({^¬}A ∨ B)$ and $^¬(A ∨ B)\Leftrightarrow ({^¬}A\wedge {^¬}B)$ $\endgroup$ – Hippalectryon Jun 13 '14 at 15:42

As suggested in the comment, a truth table may be used to find these equivalences. However, there are some Logical Equivalences that you can build on. Particularly, you can use the facts that

  • $A \rightarrow B \Leftrightarrow \neg A \lor B$
  • $\neg ( A \lor B ) \Leftrightarrow (\neg A \land \neg B)$ (De Morgan's Law)

Applied to your problem, you can state that

$\neg (A \rightarrow B) \Leftrightarrow$ (according to first equaivalence)

$\neg (\neg A \lor B) \Leftrightarrow$ (according to De Morgan)

$A \land \neg B$

(although the first step would already qualify for "writing it only with $A, B, \lor, \land, \neg$")

  • $\begingroup$ Would it help for me to draw a Venn diagram? $\endgroup$ – ahorn Jun 13 '14 at 16:01
  • $\begingroup$ @ahorn Not sure whether showing implication in a Venn diagram would be easy or helpful. The equivalences that are used in this particular case are the most "important" ones to learn by heart, and should help you to solve these kind of tasks. $\endgroup$ – Marco13 Jun 13 '14 at 16:12
  • $\begingroup$ @Marco13 Your last line is incorrect: push the negation inward with DeMorgan's, and you get $\lnot(\lnot A \lor B) \equiv A \land \lnot B$. $\endgroup$ – Namaste Jun 13 '14 at 16:45
  • $\begingroup$ @amWhy Thanks, corrected it (that was what already mentioned as the solution in the question) $\endgroup$ – Marco13 Jun 13 '14 at 18:55
  • $\begingroup$ Marco, I didn't downvote you. I rarely downvote answers, especially when I see that an error is more of a typo, than anything else! (+) $\endgroup$ – Namaste Jun 13 '14 at 19:01

So, let's look at the truth table for "⇒"

p   q   (p⇒q)
0   0     1
0   1     1
1   0     0
1   1     1

Thus, the only time that (p⇒q) ends up false is when p holds true, and q is false. Otherwise (p⇒q) is true. So, if it is not the case that p holds true, and q is false, then (p⇒q) is true. Or in symbols if ¬(p$\land$$\lnot$q), then (p⇒q) holds true. If you check the truth table for ¬(p$\land$$\lnot$q) you can also observe that if (p⇒q) holds true, then ¬(p$\land$$\lnot$q) holds true. Consequently, in


we can replace (A⇒B) by $\lnot$(A$\land$$\lnot$B). Doing such we obtain


Since ¬¬p is logically equivalent to p, from the above we can obtain



$\neg(A \implies B) \iff \neg [ (\neg A) \vee B] \iff [\neg(\neg A)] \wedge[\neg B] \iff A \wedge(\neg B)$.

As an exercise, you can show how each of these statements is logically equivalent to its successor.


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.