1

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$

Charles
  • 32,122
ahorn
  • 2,236
  • 1
    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 ?$. – Joffysloffy Jun 13 '14 at 15:39
  • Use $(A\Rightarrow B)\Leftrightarrow ({^¬}A ∨ B)$ and $^¬(A ∨ B)\Leftrightarrow ({^¬}A\wedge {^¬}B)$ – Hippalectryon Jun 13 '14 at 15:42

3 Answers3

1

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$")

Marco13
  • 2,043
  • Would it help for me to draw a Venn diagram? – ahorn Jun 13 '14 at 16:01
  • @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. – Marco13 Jun 13 '14 at 16:12
  • @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$. – amWhy Jun 13 '14 at 16:45
  • @amWhy Thanks, corrected it (that was what already mentioned as the solution in the question) – Marco13 Jun 13 '14 at 18:55
  • 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! (+) – amWhy Jun 13 '14 at 19:01
  • "Most important" equivalences yet there exists a solution without using any of them (no I didn't down-vote this answer). – Doug Spoonwood Jun 13 '14 at 23:42
  • @DougSpoonwood I called them the "most "important" ones to learn by heart". Of course, you can derive many things with truth tables, but some of these equivalences should be ready-to-use in the mental toolbox. (And things like the identity laws don't really have to be "learned" at all. But I already feared that this formulation might be considered as inappropriate...) – Marco13 Jun 14 '14 at 00:03
  • @Marco13 don't worry, I understand it now. – ahorn May 12 '16 at 22:06
  • @ahorn I hope it didn't take two years to understand it - otherwise, I'd likely have explained it poorly ;-) – Marco13 May 12 '16 at 22:14
  • @Marco13 I was just going through my old questions to accept answers. At the time, I had no idea about those equivalences, but I've learnt a lot since then and of course $(A \Rightarrow B) \Leftrightarrow (\neg A \lor B)$ is fundamental to learn/memorize. The reference to "De Morgan" was a bit too academic at the time. – ahorn May 12 '16 at 22:23
1

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

¬(A⇒B)

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

¬$\lnot$(A$\land$$\lnot$B).

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

(A$\land$$\lnot$B).

Doug Spoonwood
  • 11,211
0

$\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.

beep-boop
  • 11,595