Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.