Universal binary operation and finite fields (ring)
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).
Solution 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.