Son || y! operadores suficientes para hacer todas las expresiones lógicas posibles?
La expresión lógica( a && b ) (tanto a como b tienen valores booleanos) se pueden escribir como !(!a || !b), por ejemplo. ¿No significa esto que && es "innecesario"? ¿Significa esto que todas las expresiones lógicas se pueden hacer solo usando || y !?
6 answers
Sí, como las otras respuestas señalaron, el conjunto de operadores que comprende || y ! es funcionalmente completo. Aquí hay una prueba constructiva de eso, mostrando cómo usarlos para expresar los dieciséis posibles conectivos lógicos entre las variables booleanas A y B:
-
Verdadero :
A || !A -
A NAND B :
!A || !B -
B implica A :
!B || A -
A implica B :
!A || B -
A O B :
A || B -
No B :
!B -
No A :
!A -
A XOR B :
!(!A || B) || !(A || !B) -
A XNOR B :
!(!A || !B) || !(A || B) -
A :
A -
B :
B -
A NI B :
!(A || B) -
A no implica B :
!(!A || B) -
B no implica A :
!(!B || A) -
A Y B :
!(!A || !B) -
False :
!(A || !A)
Tenga en cuenta que tanto NAND como NOR son por sí mismos funcionalmente completos (lo que se puede probar usando el mismo método anterior), por lo que si desea verificar que un conjunto de operadores está funcionalmente completo, es suficiente para mostrar que puede expresar NAND o NOR con él.
Aquí hay un gráfico que muestra los diagramas de Venn para cada uno de los conectivos enumerados anteriormente:
[fuente]
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-10-16 05:51:57
Lo que estás describiendo es integridad funcional.
Esto describe un conjunto de operadores lógicos que es suficiente para "expresar todas las tablas de verdad posibles". Su conjunto de operadores Java, {||, !}, es suficiente; corresponde al conjunto {},}, que aparece en la sección "Conjuntos de operadores funcionalmente completos mínimos".
El conjunto de todas las tablas de verdad significa todos los conjuntos posibles de 4 valores booleanos que pueden ser el resultado de una operación entre 2 valores booleanos. Debido a que hay 2 valores posibles para un booleano, hay 24, o 16, posibles tablas de verdad.
A B | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
----+------------------------------------------------
T T | T T T T T T T T F F F F F F F F
T F | T T T T F F F F T T T T F F F F
F T | T T F F T T F F T T F F T T F F
F F | T F T F T F T F T F T F T F T F
Aquí hay una tabla de los números de la tabla de verdad (0-15), las combinaciones || y ! que lo producen, y una descripción.
Table | Operation(s) | Description
-------+----------------------------------+-------------
0 | A || !A | TRUE
1 | A || B | OR
2 | A || !B | B IMPLIES A
3 | A | A
4 | !A || B | A IMPLIES B
5 | B | B
6 | !(!A || !B) || !(A || B) | XNOR (equals)
7 | !(!A || !B) | AND
8 | !A || !B | NAND
9 | !(A || !B) || !(!A || B) | XOR
10 | !B | NOT B
11 | !(!A || B) | NOT A IMPLIES B
12 | !A | NOT A
13 | !(A || !B) | NOT B IMPLIES A
14 | !(A || B) | NOR
15 | !(A || !A) | FALSE
Hay muchos otros conjuntos funcionalmente completos, incluyendo los conjuntos de un elemento {NAND} y {NOR}, que no tienen operadores individuales correspondientes en Java.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-10-20 18:57:40
Sí.
Todas las puertas lógicas se pueden hacer de puertas NOR.
Dado que una puerta NOR se puede hacer a partir de un NOT y un OR, el resultado sigue.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-10-15 18:01:34
Tómese el tiempo para leer sobre Las Leyes de DeMorgan si puede.
Encontrará la respuesta en la lectura allí, así como referencias a las pruebas lógicas.
Pero esencialmente, la respuesta es sí.
EDITAR: Para explicitar, mi punto es que uno puede inferir lógicamente una expresión OR de una expresión AND, y viceversa. También hay más leyes para la equivalencia lógica y la inferencia, pero creo que esta es la más apropiada.
EDITAR 2: Aquí hay una prueba vía truth-table que muestra la equivalencia lógica de la siguiente expresión.
Ley de DeMorgán: !(!A || !B) -> A && B
_____________________________________________________ | A | B | !A | !B | !A || !B | !(!A || !B) | A && B | ------------------------------------------------------- | 0 | 0 | 1 | 1 | 1 | 0 | 0 | ------------------------------------------------------- | 0 | 1 | 1 | 0 | 1 | 0 | 0 | ------------------------------------------------------- | 1 | 0 | 0 | 1 | 1 | 0 | 0 | ------------------------------------------------------- | 1 | 1 | 0 | 0 | 0 | 1 | 1 | _______________________________________________________
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-10-20 17:20:23
NAND and NOR are universal they can be used to build up any logical operation you want anywhere; other operator are available in programming languages to make it easy to write and make readable codes.
También todas las operaciones lógicas que se necesitan para ser cableadas en el circuito también se desarrollan utilizando NAND o NOR solo ICs.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-10-21 04:45:34
Sí, de acuerdo con el álgebra booleana, cualquier función booleana puede expresarse como una suma de mintermas o un producto de maxtermas, que se llama forma normal canónica. No hay ninguna razón por la que tal lógica no pueda aplicarse a los mismos operadores utilizados en ciencias de la computación.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-10-20 16:41:17