Informática
Tabela-verdade de uma expressão booleana
Escreva a expressão na notação que preferir — AND/OR/NOT, os símbolos · + ', ou && || ! — e obtenha a tabela-verdade completa.
Como ler uma tabela-verdade
Uma tabela-verdade lista todas as combinações possíveis das entradas e o valor que a expressão assume em cada uma. Com n variáveis há 2ⁿ linhas: duas variáveis dão quatro, três dão oito, quatro dão dezesseis. A ordem convencional é a de um contador binário, com a primeira variável mudando mais devagar, e existe para garantir que nenhuma combinação seja pulada.
Os três operadores básicos se resumem em três frases. AND é verdadeiro só quando as duas entradas são, OR é falso só quando as duas são falsas, NOT inverte. O XOR, menos usado nos primeiros exercícios mas central nos circuitos aritméticos, é verdadeiro quando as entradas diferem: é a soma binária sem o vai-um.
A tabela é também a ferramenta para provar uma identidade. Duas expressões são equivalentes quando as suas colunas de saída coincidem linha a linha, e é assim que se verificam as leis de De Morgan: a negação de um AND é o OR das negações, e vice-versa. É a transformação que permite construir qualquer circuito com um único tipo de porta.
Erros frequentes
- Errar a precedência dos operadores: NOT liga mais forte que AND, que liga mais forte que OR. Sem parênteses, A OR B AND C significa A OR (B AND C), não (A OR B) AND C.
- Aplicar a lei de De Morgan negando só um termo: a negação de (A AND B) é (NOT A) OR (NOT B), com o operador do meio mudando também.
- Pular combinações na tabela: três variáveis significam oito linhas e todas precisam ser listadas, mesmo as que parecem óbvias. Seguir a ordem binária é como nenhuma se perde.
Perguntas frequentes
Quantas linhas tem uma tabela-verdade?
Dois elevado ao número de variáveis: 2ⁿ. Duas variáveis dão quatro linhas, três dão oito, quatro dão dezesseis. Cada linha é uma combinação diferente de zeros e uns.
Qual é a precedência dos operadores booleanos?
Primeiro NOT, depois AND, depois XOR, depois OR. É a mesma hierarquia da álgebra comum se você pensar em AND como multiplicação e em OR como soma, e é por isso que se escrevem · e +.
O que dizem as leis de De Morgan?
Que a negação de uma conjunção é a disjunção das negações, e vice-versa: NOT(A AND B) = NOT A OR NOT B, e NOT(A OR B) = NOT A AND NOT B. Verificam-se comparando as colunas de saída.
Qual a diferença entre OR e XOR?
O OR é verdadeiro mesmo quando as duas entradas são verdadeiras; o XOR não. O XOR só é verdadeiro quando as entradas diferem entre si, e por isso também se chama OU exclusivo.
Como funciona este cálculo
Operadores: NOT A vale 1 quando A vale 0. A AND B vale 1 só se A = B = 1. A OR B vale 0 só se A = B = 0. A XOR B vale 1 quando A ≠ B. Precedência, da mais forte: NOT, AND, XOR, OR; os parênteses a alteram. Linhas com n variáveis: 2ⁿ. Leis de De Morgan: ¬(A·B) = ¬A + ¬B e ¬(A + B) = ¬A · ¬B. Identidades úteis: A + A·B = A (absorção), A·(A + B) = A, A + ¬A = 1 (terceiro excluído), A·¬A = 0 (não contradição). O leitor aceita a notação por palavras, a simbólica (· + ') e os operadores de programação (&& || !).