Pregunta originalmente respondida: ¿Qué propiedades hacen que un operador sea universal?
NAND es universal, NOR es universal, pero ¿qué propiedades hacen que cualquier operador (no necesariamente lógico o binario) sea un operador universal (aparte de la propiedad tautológica de la universalidad, que es obvio)?
Esta es una pregunta bastante interesante. Sus ejemplos de universalidad utilizan los operadores lógicos NAND y NOR. Así que primero echemos un vistazo a ellos, antes de pasar a su pregunta más general.
- ¿Cómo se eleva un número o matriz a una potencia matricial?
- ¿Cómo se muestra rigurosamente que si [math] w '<w \ implica b ^ {w'} <b ^ {w} [/ math]?
- ¿Cuáles son algunos buenos ejemplos y analogías para las matemáticas discretas?
- Soy estudiante de matemáticas. ¿Cómo debo prepararme para estudiar finanzas matemáticas en la escuela de posgrado?
- Cómo aceptar el hecho de que las matemáticas no son realidad
Ahora, los operadores lógicos son funciones desde tuplas de valores de verdad, [math] \ mathbb {B} ^ n [/ math], a [math] \ mathbb {B} [/ math], donde [math] n \ geq 1 [ /matemáticas]. Tenga en cuenta que excluyo el caso de [math] n = 0 [/ math], que sería un operador nulo, en esencia una constante, como [math] true [/ math] y [math] false [/ math].
Por lo tanto, el conjunto de todos los operadores lógicos puede especificarse mediante: [math] \ displaystyle \ mathcal {B} = \ bigcup_ {n = 1} ^ {\ infty} \ mathcal {B} _n [/ math], donde [math] \ mathcal {B} _n = \ {f | f \ in (\ mathbb {B} ^ n \ to \ mathbb {B}) \} [/ math].
Ahora, lo que llama la universalidad de los operadores NAND y NOR, es un caso especial del concepto más general de la integridad funcional, a veces llamada integridad expresiva, de un conjunto de operadores. El caso especial es que aquí, el conjunto de operadores solo contiene un elemento.
La idea básica es que si este conjunto de operadores es lo suficientemente rico como para expresar cualquier otra función en [math] \ mathcal {B} [/ math], este conjunto se llama funcionalmente completo.
Ahora, los conceptos básicos utilizados anteriormente también se pueden aplicar a clases de funciones más generales. Nuevamente tendríamos algún dominio [math] \ mathbb {D} [/ math], y la clase de todas las funciones en [math] \ mathbb {D} ^ n \ to \ mathbb {D} [/ math]. Y preguntaríamos sobre la existencia de algún conjunto de funciones [matemáticas] \ matemáticas [F} = \ {f_1, f_2, \ cdots f_n \} [/ matemáticas], de modo que todas las funciones de la clase se puedan expresar en términos de Estas funciones solo.
Usted pregunta, además de la propiedad definitoria de integridad, qué hace que este conjunto de funciones sea completo. A esa pregunta, no creo que realmente haya una respuesta. No creo que haya otra propiedad que tengan tales conjuntos de funciones funcionalmente completas.
