Can $\neg$ be defined only using $\{ \wedge , \vee\}$?

Question

In propositional logic, can '$\neg$' symbol be defined only using $\{ \wedge , \vee\}$ ?

I don't think that $\neg$ (negation) can defined using the conjunction and disjunction operators, since its independently mentioned in the five common logic connectives $(\neg, \vee, \wedge, \rightarrow, \leftrightarrow)$.

I want to prove that this cannot be done (maybe by induction).

Any help will be appreciated!

No it cannot, but your point about $\neg, \vee, \wedge, \rightarrow, \leftrightarrow$ is not the reason, as some of those can be defined using the others — Henry, Oct 17 '22 at 09:37
@Henry yeah, I agree as $\rightarrow$ can be defined using $\neg$ and $\vee$. But then how do I go about proving it? — V.G, Oct 17 '22 at 09:39
A hint: formulas only using $\wedge$ and $\vee$ are always true when their variables are true, so no such formula can be logically equivalent to $\neg p$ — Matthew Towers, Oct 17 '22 at 09:42
$A\land A\leftrightarrow A$ and $A\lor A\leftrightarrow A$ hence if $\neg A$ was defined only in terms of $\land$ and $\lor$ and $A$, it would be equivalent to $A.$ — Anne Bauval, Oct 17 '22 at 09:44
Does this answer your question? Is the set $\tau := \left{\vee, \wedge, 0\right}$ adequate? Prove your answer — Anne Bauval, Oct 17 '22 at 09:45

Just a user · Accepted Answer · 2022-10-18T03:47:10.943

It would be cool if this is true, because we would have known P$\not=$NP!

A circuit without $\neg$ is called monotone, and it has been shown that such circuit cannot solve NP hard problems in general.

I don't like the "always true" or "always false" argument. What if we throw in both of the constants $0$ and $1$?

Indeed, if we start with three functions $0, 1, x$, then any $\wedge, \vee$ of any two of them must be also be one of them, e.g. $x\wedge x=x, 0\wedge x=0, 1\vee x=1$, etc. Therefore by doing induction on the number of $\wedge, \vee$ in the boolean expression, the result would be just one of $0, 1, x$.

What if we throw in other helpful dumb variables $x_1, x_2, \cdots$? This still won't help since we may focus on the subset $x=x_1=x_2\cdots$ and apply the argument above.

ChrisoLosoph · Answer 2 · 2023-11-22T13:53:18.610

As the other answer says, it is impossible.

When I read your question, I thought of an easy to understand reason, why it is impossible:

the NOT conjunctive is always evaluated to a "different value" than the "input value"
the AND and OR conjunctive can only be evaluated to the "value" of one of both sides and never to a "value" that is different to both sides. (That's even the case in the standard definition for multi-valued logic, the miniumum and maximum.)

Sane reasoning says, if you apply AND or OR multiple times to a (truth) value or constants it consequentially still cannot produce a "different value" than those input values whereas a NOT would be able to produce a new truth value that is negatively correlated to the input, in lay words: it produces both a true from a false and a false from a true.

(The same reasoning can be made if we connect different truth values with the conjuctives, such as "constants" and "variables". AND and OR cannot produce new Literals or constants that did not already exist at the start.)

EDIT for technical correctness:

Note, that "different value" is just slang for differently correlated value (not just value domain). A new value is like a function value (when being viewed as the result of a truth table) whose correlation to the Gate inputs differs from the input values' own correlations to the inputs.

What I technically meant to say is, NOT produces a negative correlation while AND and OR cannot produce a negative correlation. They only copy the correlation of the inputs. So if you feed in a "constant" or a positive Literal, you only get a constant or a positive Literal as output but never a negative Literal. But if you have already an input of the desired correlation, the negative Literal, then there is no reason to pass it through another gate. Of course you can compute a negation when you know the result beforehand but AND and OR cannot compute it if they don't know it beforehand.

Can $\neg$ be defined only using $\{ \wedge , \vee\}$?

2 Answers2