33
$\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).

$\endgroup$
14
  • $\begingroup$ How do you define AND, OR and NAND for other finite fields? $\endgroup$
    – Aryabhata
    Mar 4, 2011 at 5:32
  • 1
    $\begingroup$ Say AND is 'multiplication' and OR is 'addition' ($+, .$). Can one find or define a binary operation which resemble NAND. $\endgroup$
    – Dilawar
    Mar 4, 2011 at 8:06
  • 4
    $\begingroup$ 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? $\endgroup$
    – JDH
    Mar 4, 2011 at 9:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – JDH
    Mar 4, 2011 at 11:52
  • 3
    $\begingroup$ I asked a question on MathOverflow at mathoverflow.net/questions/57465/… concerning what I find to be the very interesting core of this question. $\endgroup$
    – JDH
    Mar 5, 2011 at 15:40

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .