logic - equal - Son || y! operadores suficientes para hacer todas las expresiones lógicas posibles?

struts 1 tags

Question

La expresión lógica ( a && b ) (tanto a como b tienen valores booleanos) se puede 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 ! ?

Answer 1

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 se enumera 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 2 ⁴ , 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), el || y ! combinaciones 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, incluidos los conjuntos de un elemento {NAND} y {NOR}, que no tienen operadores individuales correspondientes en Java.

Answer 2

Sí, como señalaron las otras respuestas, el conjunto de operadores que comprende || y ! Está funcionalmente completo . Aquí hay una prueba constructiva de eso, que muestra cómo usarlos para expresar las dieciséis posibles conexiones lógicas entre las variables booleanas A y B :

• True : A || !A A || !A
• A NAND B:! !A || !B !A || !B
• B implica A !B || A !B || A
• A implica B !A || B !A || B
• A O B : A || B A || B
• No B : !B
• No A !A
• A XOR B:! !(!A || B) || !(A || !B) !(!A || B) || !(A || !B)
• A XNOR B:! !(!A || !B) || !(A || B) !(!A || !B) || !(A || B)
• A : A
• A : 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 utilizando el mismo método anterior), por lo que si desea verificar que un conjunto de operadores esté funcionalmente completo, es suficiente para demostrar que puede expresar NAND o NOR con eso.

Aquí hay un gráfico que muestra los diagramas de Venn para cada uno de los conectores enumerados anteriormente:

[ source ]

Answer 3

Sí, de acuerdo con el álgebra booleana, cualquier función booleana se puede expresar como una suma de minterms o un producto de maxterms, que se llama forma canónica normal . No hay ninguna razón por la cual dicha lógica no pueda aplicarse a los mismos operadores que se usan en informática.

https://en.wikipedia.org/wiki/Canonical_normal_form

Answer 4

Si.

Todas las puertas lógicas pueden estar hechas de puertas NOR.

Dado que una compuerta NOR se puede hacer desde un NOT y un OR, el resultado sigue.

Answer 5

Tómese el tiempo para leer 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 ser explícito, mi punto es que uno puede inferir lógicamente una expresión OR a partir 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 adecuada.

EDITAR 2 : Aquí hay una prueba a través de la tabla de verdad que muestra la equivalencia lógica de la siguiente expresión.

Ley de DeMorgan:! !(!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 | _______________________________________________________

Answer 6

NAND y NOR son universales; pueden usarse para construir cualquier operación lógica que desee en cualquier lugar; otros operadores están disponibles en lenguajes de programación para facilitar la escritura y la creación de códigos legibles.

Además, todas las operaciones lógicas que se necesitan para estar cableadas en el circuito también se desarrollan utilizando circuitos integrados NAND o NOR solamente.