32
$\begingroup$

Take Boolean Algebra for instance, the underlying finite field/ring $0, 1, \{AND, OR\}$ is equivalent to $ 0, 1, \{NAND\} $ or $ 0, 1, \{ NOR \}$ where NAND and NOR are considered as universal gates. Does this property, that AND ('multiplication') and OR ('addition') can be written in terms of a single universal binary relation (e.g. NAND or NOR), hold with every finite field (or finite ring)?

EDIT : I am interested in mathematical structures where boolean algebra holds (so that I can design a digital circuit.). Comments from JDK and jokiri point out that this is a valid question for finite rings at least and for finite fields in one case (i.e. $1, 0$ case).

  • 0
    How do you define AND, OR and NAND for other finite fields?2011-03-04
  • 1
    Say AND is 'multiplication' and OR is 'addition' ($+, .$). Can one find or define a binary operation which resemble NAND.2011-03-04
  • 4
    Boolean algebras are never fields, except the two element algebra, since only $1$ has a multiplicative inverse. But I find your question interesting for rings. I interpret it as the question: Does every ring admit a single binary operation from which both $+$ and $\cdot$ are expressible?2011-03-04
  • 0
    @JDH: The question was restricted to finite rings.2011-03-04
  • 0
    @joriki, I have edited the question. I made a mistake first. Sorry, should have pointed out clearly in EDIT.2011-03-04
  • 0
    @JDH, thanks edited.2011-03-04
  • 0
    @Dilawar: Now I'm confused :-). My comment to JDH was because he had written "every ring" and your question said "every finite field (or ring)", so I wanted to point out the finiteness restriction. Now in response to that you've edited your question to say "Question is posed for rings". That makes it less clear to me. Are you saying that you're interested in all rings after all, not just finite ones? Or are you saying that you're no longer interested in fields?2011-03-04
  • 0
    @jakiri, oh!! Sorry!! I am interested in finite rings at-least. Actually, in any mathematical structure where boolean-algebra holds. Let me edit the question again!2011-03-04
  • 1
    The question makes sense for fields also (which of course are rings and so included in the rings case). I was objecting to the characterization of Boolean algebras as examples of fields, which of course is seldom true.2011-03-04
  • 3
    I asked a question on MathOverflow at http://mathoverflow.net/questions/57465/can-we-unify-addition-and-multiplication-into-one-binary-operation-to-what-exten concerning what I find to be the very interesting core of this question.2011-03-05
  • 0
    @JDH, thanks! Though you may have to translate the solution you get there.2011-03-05
  • 0
    I think you mean {NOT, AND, OR} instead of {AND, OR} since {AND, OR} can't generate all 16 truth operations on {0, 1}, while {NOT, AND, OR}, {NAND}, and {NOR} can. I would guess that your conjecture fails for rings with three elements, though that's just a guess.2011-06-21
  • 0
    I know that George Spencer Brown ('The Laws of Form') has developed a boolean algebra that he used to design and simplify circuits. It is my understanding that he has some key simplifications on standard boolean algebra.2011-11-28
  • 0
    I'm afraid I don't quite understand the constraints of the question. Say, if the ring has 4 elements, then we represent a single element of the ring with two bits, right? And the question is, whether there is a single function (or circuit) $f$ with two incoming buses, each two bits wide, and a single outgoing bus, also two bits wide, such that we can represent the ring operations by intelligently composing $f$:s. But we are not allowed to e.g. work on individual bits (because then you could do everythin with NAND), right?2012-05-06

1 Answers 1

2

I'm not sure I get the question right, I understand you are asking if it is true that you can express any boolean operation using only one gate. If this is your question, the answer is yes.

Take the NAND, for example (represented in boolean argebra by the sheffer stroke |). It can replace any unary or binary gate.

  • We already know that anything can be expressed with AND and NOT.
  • If we can express AND and NOT with NAND,
  • therfore we can express anything with NAND.

Reminder, NAND can be understood in English as "At most one", which means it's true except if both p and q are true:

p    q    p|q
-------------
0    0     1
0    1     1
1    0     1
1    1     0

Let's prove that NOT (¬) can be expressed with NAND (|):

p    ¬p    p|p
---------------------
0     1     1 (0|0=1)
1     0     0 (1|1=0)

NOT can be expressed with NAND: ¬p = p|p

Let's now prove that AND (^) can be expressed with NAND(|). p^q = ¬(p|q) and we already know how to express NOT with NAND:

p    q    p^q    p|q    (p|q)|(p|q)
----------------------------------
0    0     0      1          0 (1|1=0)
0    1     0      1          0 (1|1=0)
1    0     0      1          0 (1|1=0)
1    1     1      0          1 (0|0=1)

AND can be expressed with NAND: p^q = (p|q)|(p|q)

For your information, the OR gate can be expressed (p|p)|(q|q), I'm sure you can prove it for yourself.