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