# And - Or - Not in terms of one another

1. Dec 22, 2015

### N123

It is possible to express the boolean AND in terms of boolean OR and boolean NOT:
a AND b <=> NOT (NOT a OR NOT b)
Similarly,
a OR b <=> NOT (NOT a AND NOT b)

Why can't we express NOT in terms of OR and AND?

2. Dec 22, 2015

### Staff: Mentor

3. Dec 22, 2015

### Erland

Suppose we have a boolean expression $\phi(A,B,C,\dots...)$ built up by the atomic sentences $A,B,C,\dots$and the connectives $\land$ and $\lor$ only, such that $\phi(A,B,C\dots)\equiv\neg A$.
Since the truth value of $\neg A$ is independent of the truth values of $B,C,\dots$, the equivalence will still hold if we replace $B,C,\dots$ with any sentences, in particular, if we replace them all with $A$, so $\phi(A,B,C,\dots)\equiv \phi(A,A,A,\dots)$, the latter being built up from $A$, $\land$, and $\lor$ only. But since $A\land A\equiv A$ and $A\lor A \equiv A$, $\phi(A,A,A,\dots)$ can be successively reduced to $A$, so, $\phi(A,A,A,\dots)\equiv A$.
Thus, $A\equiv\neg A$, which clearly is a contradiction.

4. Dec 22, 2015

### N123

What do you mean by atomic sentences? Are B, C etc propositions or are they literals? Not sure yet if it matters, but if A, B, C are themselves composed of other "variables" X, Y, Z then their truth values may not be independent.
But then again, they are independent in the general case.
For example: NOT A = B U C if the universal set is {A, B, C}.
Apologies for the lack of rigor in the language used to express these ideas, I am not a mathematician.

5. Dec 22, 2015

### Erland

I mean that $A,B,C, \dots$ are atomic sentences or propostions, i.e. that they are not built up from simpler propositions by connectives. But as you say, it doesn't really matter, everything I wrote still holds whether $A,B,C,\dots$ are atomic or not, independent or not, etc...

Edit: $\equiv$ means logical equivalence, which means that e.g. $\neg(A\land B)\equiv \neg A \lor \neg B$ means that $\neg(A\land B)$ and $\neg A \lor \neg B$ either are both true or both false, no matter which truth values we assign to $A$ and $B$. We can have an interpretation where $\neg A\leftrightarrow (B\lor C)$ is true, but this is not true for all interpretations.

Last edited: Dec 22, 2015
6. Dec 26, 2015

### WWGD

OP: Have you considered using the Sheffer stroke?

7. Dec 29, 2015

### N123

WWGD - that is not my question. I know that AND, OR, NOT can be expressed in terms of NAND (Sheffer stroke.) Also, just using NOR.