I know that $A\Rightarrow B$ is equivalent to $\neg A \lor B$. Also that $\neg (A\Rightarrow B)$ is given by $A \land \neg B$. But can $\neg (A\Rightarrow B)$ be written in terms of $A$, $B$, $\Rightarrow$, and $\neg$ alone (i.e. without the use of $\lor$ and $\land$)?

  • $\begingroup$ An implication is an "or"-statement. The negation of an "or"-statement is an "and"-statement. So I would say no, not apart from what you already have, namely $\lnot(A\Rightarrow B)$. $\endgroup$ – Arthur Nov 13 '15 at 14:28
  • 1
    $\begingroup$ Wait a minute, haven't you just done so? $\neg(A\Rightarrow B)$ is obviously written in terms of only $\neg, \Rightarrow, A, B$. $\endgroup$ – BrianO Nov 13 '15 at 17:03
  • $\begingroup$ @BrianO I think he also wants to get rid of the parentheses. $\endgroup$ – Akiva Weinberger Nov 13 '15 at 19:14
  • $\begingroup$ Or, perhaps, to write it in terms of $A$, $B$, $\lnot A$, $\lnot B$, and $\Rightarrow$. $\endgroup$ – Akiva Weinberger Nov 13 '15 at 19:20
  • $\begingroup$ @AkivaWeinberger Yes, must be. I realized that after seeing Rob Arthan's answer. $\endgroup$ – BrianO Nov 13 '15 at 19:25

I think you are asking for the principal connective to be an implication rather than a negation. If that's right, a suitable equivalent to $\lnot (A \Rightarrow B)$ is $(A \Rightarrow B) \Rightarrow \lnot(A \Rightarrow A)$.

Note that it is impossible to write $\lnot(A \Rightarrow B)$ in terms of implication alone. If $\phi(A, B)$ is equivalent to $\lnot(A \Rightarrow B)$ , then $\phi(A \Rightarrow A, A)$ is equivalent to $\lnot A$, so as $\lnot$ and $\Rightarrow$ are functionally complete, if $\phi$ is constructed with $\Rightarrow$ alone, then $\Rightarrow$ on its own would be functionally complete, but by Post's characterisation of functionally complete sets of connectives, it is not (see link above).


I use Polish notation.

The formation rules go:

  1. All lower case letters of the Latin alphabet qualify as well-formed formulas.
  2. 0 consists of a well-formed formula standing for the constant false proposition.
  3. If $\alpha$ and $\beta$ qualify as well-formed formulas, then so does C$\alpha$$\beta$. C stands for implication, or equivalently conditional.

Now let us adopt the definition that the negation of a proposition Np, comes as abbreviation for Cp0, since C00 = 1 and N0 = 1, and C10 = 0 and N1 = 0.

Thus, NCab abbreviates CCab0.

More formally, we can take as a definition:

  1. C$\delta$Np$\delta$Cp0 where $\delta$ consists of a functioral variable of one argument (in other words $\delta$ comes as a variable which ranges over the four unary-truth functors of two-valued logic).

Substituting p with Cab and dropping $\delta$ or equivalently substituting $\delta$' with the apostrophe symbol ' where the apostrophe symbol ' consists of the argument of $\delta$ we have

  1. CNCabCCab0

as a thesis obtained from the definition. Thus, given NCab by definition we obtain CCab0. From 1. and the rule of uniform substitution for $\delta$ and the rule of uniform substitution for propositional variables we can also obtain NCab from CCab0.

  • $\begingroup$ Using "false" strikes me as not in the spirit of the question . . . $\endgroup$ – Noah Schweber Nov 14 '15 at 6:20
  • $\begingroup$ @NoahSchweber You might speak correctly, but I can't tell at this point in time. $\endgroup$ – Doug Spoonwood Nov 16 '15 at 17:49

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.