1

I mean, is it possible to convert AND OR NOT to simple algebraic expressions?

If it's not possible, how do you prove it?

MathGeek
  • 831
user3698446
  • 27
  • Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please [edit] the question. This will help you recognize and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. – José Carlos Santos Apr 24 '22 at 08:27
  • My thought on this is that it may be impossible, but I don't have a proof yet. It's like how to prove there's no formula to quintic equations, not that easy IMO. – user3698446 Apr 24 '22 at 08:30
  • If you allow subtraction or the constant $-1$, this is possible even without needing to work mod 2. – Magma Apr 24 '22 at 08:37
  • @Magma can you post your answer? Basically, how to do AND OR NOT in purely algebraic way? – user3698446 Apr 24 '22 at 08:38

2 Answers2

2

I would assume that the "boolean operations" you mentioned are "boolean functions", i.e. functions of the form $f:\{0, 1\}^{k} \to \{0, 1\}$. Any boolean function can be expressed as a combination of NAND gates (which is called functional completeness of NAND gate), and we have $\mathrm{NAND}(x, y) = 1 - xy$, so it is possible.

Seewoo Lee
  • 15,137
  • 2
  • 19
  • 49
  • Can you show how to express OR, AND ,NOT with NAND only? – user3698446 Apr 24 '22 at 08:37
  • First, $\mathrm{NOT}(x) = \mathrm{NAND}(x, x)$. Then $\mathrm{AND}(x, y) = \mathrm{NOT}(\mathrm{NAND}(x, y))$ and $\mathrm{OR}(x,y)=\mathrm{NOT}(\mathrm{AND}(\mathrm{NOT}(x), \mathrm{NOT}(y)))$ also can be expressed only with $\mathrm{NAND}$. – Seewoo Lee Apr 24 '22 at 08:42
  • Cool! Do you also know how many different basis of boolean operations are there for OR, AND ,NOT ? – user3698446 Apr 24 '22 at 08:45
  • If you mean basis as a functionally complete set, then ${\mathrm{NOR}}$ or ${\mathrm{NOT}, \mathrm{AND}}$ are also the examples. See Wikipedia - https://en.wikipedia.org/wiki/NAND_gate – Seewoo Lee Apr 24 '22 at 08:48
  • Do you know the general method to find all functionally complete set for boolean algebra? – user3698446 Apr 24 '22 at 08:51
  • @user3698446 Maybe the most naive way is to add functions until the set can express $\mathrm{NAND}$. I don't know any efficient methods for it. Maybe someone would answer instead of me. – Seewoo Lee Apr 24 '22 at 08:54
0

Sure, classic Boolean logic is equivalent to operations on $\mathbb Z_2$. You might be aware that $\land,\mathrm{xor}$ similar to $\cup,\triangle$ on sets create the structure of a ring.

But there is up to isomorphy only one ring with to elements, which is $\mathbb Z_2$. In fact we can easily see $\land\sim +$ and $\mathrm{xor} \sim \cdot$: $a+b = 1$ exactly if either $a=1$ or $b=1$ but not both. $a\cdot b = 1$ exactly if $a=1$ and $b=1$.

Furthermore we can also easily see that $\lnot$ corresponds to $+1$.

This suffices to express any other possible logical operation:

$a\lor b = \lnot(\lnot a \land \lnot b) \sim 1 + ((1+a)(1+b)) = ab + a + b \sim (a\land b) \,\mathrm{xor}\, a \,\mathrm{xor}\, b $

$a\rightarrow b = \lnot a \lor b \sim (1+a)b + (1+a) + b = ab + a + 1$

and so on.

Lazy
  • 4,519