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

**Answer**

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.

**Attribution***Source : Link , Question Author : Dilawar , Answer Author : SteeveDroz*