São || e! operadores suficientes para criar todas as expressões lógicas possíveis?

294

A expressão lógica ( a && b ) (ambos ae bcom valores booleanos) pode ser escrita como !(!a || !b), por exemplo. Isso não significa que &&é "desnecessário"? Isso significa que todas as expressões lógicas podem ser feitas apenas usando ||e !?

JakeTheSnake
fonte
83
Esta é mais uma questão lógica lógica simbólica do que uma questão Java, mas sim. OR e NOT em combinação podem ser usados ​​para construir todo o resto. O mesmo com AND e NOT. Por exemplo, quando eu estava na escola, fomos ensinados a construir tudo usando apenas portões NAND porque eles levavam menos transistores.
azurefrog
79
Não confunda a capacidade de escrever uma declaração dessa maneira com a conveniência de fazê-lo. O açúcar sintático é uma coisa boa .
azurefrog
20
Muitos chips de porta lógica fornecem apenas portas NAND ou NOR, pois é possível implementar todas as operações com eles e isso os torna baratos de produzir - A and B == !A nor !B == !(!A or !B). Da mesma forma A or B == !A nand !B == !(!A and !B). Obviamente, passar o mesmo valor para as duas entradas de um NAND ou NOR dará o mesmo resultado que um simples NOT. XOR e XNOR também são possíveis, mas mais complexos. Veja o teorema de De Morgan
Básico
16
Não é uma questão de ciência da computação? Não vejo código aqui. Em particular, se isso é verdade na prática variará de acordo com a implementação, por exemplo, em C ++ com sobrecarga operacional, isso não é geral.
Lightness Races em órbita
6
@SnakeDoc Acho que ninguém aqui está defendendo isso. Acredito que essa questão fosse mais uma questão de lógica teórica do que de programação, realmente.
ryuu9187

Respostas:

425

Sim, como as outras respostas apontaram, o conjunto de operadores que compreende ||e !é funcionalmente completo . Aqui está uma prova construtiva disso, mostrando como usá-los para expressar todos os dezesseis possíveis conectores lógicos possíveis entre as variáveis ​​booleanas Ae B:

Observe que NAND e NOR são eles próprios funcionalmente completos (o que pode ser comprovado usando o mesmo método acima); portanto, se você deseja verificar se um conjunto de operadores está funcionalmente completo, basta mostrar que você pode expressar NAND ou NOR com isso.

Aqui está um gráfico mostrando os diagramas de Venn para cada um dos conectivos listados acima:

insira a descrição da imagem aqui

[ fonte ]

Peter Olson
fonte
20
É difícil dizer se a pergunta pretende isso, mas essa resposta não aborda o comportamento de curto-circuito (relevante, já que a pergunta é mais ||do que |) ou efeitos colaterais (relevante porque a expansão de true, false, XOR e XNOR avaliam seus argumentos mais vezes do que a constante ou o operador original).
David Richerby
5
Os círculos que contêm círculos e as transições formam um diagrama de Hasse ( en.wikipedia.org/wiki/Hasse_diagram ). (Yay, eu aprendi algo novo hoje!)
Kasper van den Berg
5
@DavidRicherby Isso é verdade. Além de XOR, XNOR, true e false, tanto quanto posso dizer, os efeitos colaterais e o número de avaliações devem ser os mesmos que os equivalentes embutidos (por exemplo, !(!A || !B)tem a mesma contagem de curto-circuito e avaliação que A && B). Eu não acho que você possa fazer isso para XOR e XNOR sem construções adicionais (por exemplo a ? !b : b), e verdadeiro ou falso não é um problema se você pode salvar valores, pois você pode iniciar seu programa definindo truee falseusando alguma variável booleana fictícia.
Peter Olson
É interessante notar que a lista acima compreende 16 operações. Isso é consistente com o fato de haver 16 tabelas verdadeiras possíveis para o caso em que você possui 2 entradas e 1 saída.
Paul R
1
Só queria adicionar outra visualização como uma tabela para referência das pessoas. Mesma fonte que acima.
agosto
125

O que você está descrevendo é integridade funcional .

Isso descreve um conjunto de operadores lógicos que é suficiente para "expressar todas as tabelas verdadeiras possíveis". O seu Java do operador, { ||, !}, é suficiente; corresponde ao conjunto {∨, ¬}, listado na seção "Conjuntos mínimos de operadores funcionalmente completos".

O conjunto de todas as tabelas verdadeiras significa todos os conjuntos possíveis de 4 valores booleanos que podem ser o resultado de uma operação entre 2 valores booleanos. Como existem 2 valores possíveis para um booleano, existem 2 4 ou 16 tabelas de verdade possíveis.

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

Aqui está uma tabela dos números da tabela verdade (0-15), as combinações ||e !que a produzem e uma descrição.

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

Existem muitos outros conjuntos funcionalmente completos, incluindo os conjuntos de um elemento {NAND} e {NOR}, que não possuem operadores únicos correspondentes em Java.

rgettman
fonte
4
+1 para a edição. Apesar da diferença na contagem de votos, acho que sua resposta é realmente mais detalhada que a minha agora.
Peter Olson
Tabelas verdade eu pensei que eu tinha deixado para trás após primeiro ano na universidade
Barkermn01
80

Sim.

Todas as portas lógicas podem ser feitas a partir de portas NOR.

Como uma porta NOR pode ser feita a partir de um NOT e um OR, o resultado segue.

Paul Boddington
fonte
64
@PaulDraper ou NAND gates
slebetman
25
Foram necessários 4100 portões NOR para pousar duas pessoas na lua.
Hans Passant
4
@HansPassant E alguma corda. Muita corda. (Memória da corda do núcleo, não a variedade da lata).
um CVn
3
@HansPassant Às vezes eu gostaria que o Stack Exchange fosse a Wikipedia, então eu inseria uma [citation-needed]marca ali.
Simon Forsberg
11
Sim, desculpe, computador de orientação Apollo .
Hans Passant
64

Reserve um tempo para ler as leis de DeMorgan, se puder.

Você encontrará a resposta na leitura, assim como referências às provas lógicas.

Mas essencialmente, a resposta é sim.

EDIT : Para explicitação, o que quero dizer é que é possível inferir logicamente uma expressão OR a partir de uma expressão AND e vice-versa. Também existem mais leis para equivalência lógica e inferência, mas acho que essa é mais apropriada.


EDIT 2 : Aqui está uma prova via tabela de verdade mostrando a equivalência lógica da expressão a seguir.

Lei 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 |
_______________________________________________________
ryuu9187
fonte
19
Algumas pessoas têm que votar negativamente como parte de sua "integridade funcional"
Jesse
3
Com + 27 / -2, não me preocuparia muito com um voto negativo perdido.
um CVn
2
@ MichaelKjörling Estou curioso para saber por que algumas pessoas pensaram que minha resposta não foi útil / prejudicial.
ryuu9187
3
Geralmente, as respostas que dependem de links não são muito apreciadas (como os links morrem), mas, neste caso, existem tantas explicações alternativas das Leis de DeMorgan, que não vejo um problema - ainda assim, esse é meu palpite quanto à questão. do DV
user2813274
@ user2813274 Obrigado pela explicação. Felizmente, minhas edições ajudarão a preencher a lacuna entre a pesquisa pessoal e a resposta.
ryuu9187
11

NAND e NOR são universais, podem ser usados ​​para criar qualquer operação lógica que você deseja em qualquer lugar; outro operador está disponível nas linguagens de programação para facilitar a gravação e a criação de códigos legíveis.

Além disso, todas as operações lógicas que precisam ser conectadas no circuito também são desenvolvidas usando ICs NAND ou NOR apenas.

anand
fonte
10

Sim, de acordo com a álgebra booleana, qualquer função booleana pode ser expressa como uma soma de mintermos ou um produto de maxtermos, chamado forma normal canônica . Não há razão para que essa lógica não possa ser aplicada aos mesmos operadores usados ​​na ciência da computação.

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

Michał Szydłowski
fonte