And - Or - Not in terms of one another

  • Thread starter Thread starter N123
  • Start date Start date
  • Tags Tags
    Terms
AI Thread Summary
Boolean expressions can express AND using OR and NOT, as demonstrated by the equivalences a AND b <=> NOT (NOT a OR NOT b) and a OR b <=> NOT (NOT a AND NOT b). The inability to express NOT solely in terms of AND and OR is attributed to NOT being a monadic operator, unlike the dyadic nature of AND and OR. The discussion highlights that computer logic utilizes NAND and NOR gates to construct all logical circuits, including AND, OR, and NOT. An example illustrates that if a boolean expression equates to NOT A, it leads to a contradiction when substituting variables, emphasizing the independence of truth values. The conversation also touches on the Sheffer stroke, which can express AND, OR, and NOT, but this was not the primary focus.
N123
Messages
8
Reaction score
0
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?
 
Physics news on Phys.org
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.
 
  • Like
Likes jedishrfu and N123
Erland said:
ϕ(A,B,C…)≡¬A\phi(A,B,C\dots)\equiv\neg A.
Since the truth value of ¬A\neg A is independent of the truth values of B,C,…B,C,\dots, the equivalence will still hold if we replace B,C,…B,C,\dots with any sentences,

Clever! I am almost ready to buy it.
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.
 
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:
  • Like
Likes jedishrfu and N123
OP: Have you considered using the Sheffer stroke?
 
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.
 

Similar threads

Replies
21
Views
2K
Replies
4
Views
1K
Replies
12
Views
7K
Replies
7
Views
1K
Replies
40
Views
8K
Replies
6
Views
2K
Replies
3
Views
2K
Back
Top