Operación binaria universal y campos finitos (anillo)

Question

Tomemos como ejemplo el Álgebra de Boole, el campo/anillo finito subyacente $0, 1, \{AND, OR\}$ equivale a $ 0, 1, \{NAND\} $ o $ 0, 1, \{ NOR \}$ donde NAND y NOR se consideran puertas universales. ¿Esta propiedad de que AND ("multiplicación") y OR ("adición") pueden escribirse en términos de una única relación binaria universal (por ejemplo, NAND o NOR), se mantiene con cada campo finito (o anillo finito)?

EDIT : Me interesan las estructuras matemáticas en las que se cumple el álgebra de boole (para poder diseñar un circuito digital). Los comentarios de JDK y jokiri señalan que esta es una pregunta válida para anillos finitos al menos y para campos finitos en un caso (es decir $1, 0$ caso).

Answer 1

No sé si entiendo bien la pregunta, entiendo que preguntas si es cierto que se puede expresar cualquier operación booleana utilizando una sola puerta. Si esta es tu pregunta, la respuesta es sí .

Por ejemplo, la NAND (representada en el álgebra booleana por el trazo de sheffer | ). Puede sustituir a cualquier puerta unaria o binaria.

• Ya sabemos que cualquier cosa se puede expresar con AND y NOT.
• Si podemos expresar AND y NOT con NAND,
• Por lo tanto, podemos expresar cualquier cosa con NAND.

---

Recordemos que NAND puede entenderse en inglés como "At most one", lo que significa que es verdadero excepto si tanto p como q son verdaderos:

p    q    p|q
-------------
0    0     1
0    1     1
1    0     1
1    1     0

Demostremos que NO ( ¬ ) puede expresarse con NAND ( | ):

p    ¬p    p|p
---------------------
0     1     1 (0|0=1)
1     0     0 (1|1=0)

NOT se puede expresar con NAND: ¬p = p|p

Demostremos ahora que AND ( ^ ) puede expresarse con NAND( | ). p^q = ¬(p|q) y ya sabemos cómo expresar NO con 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 se puede expresar con NAND: p^q = (p|q)|(p|q)

Para su información, la puerta OR se puede expresar (p|p)|(q|q) Estoy seguro de que puedes probarlo por ti mismo.