Primeiro, vamos começar com uma pergunta mais simples: O que é uma tabuada?
Uma tabuada é uma tábua que lista vários valores possíveis de uma conta a ser realizada. Por exemplo, na tabuada do 3, temos 3 × 0 = 0, 3 × 1 = 3, 3 × 2 = 6, 3 × 3 = 9... Observe que o formato é sempre 3 × a = n, onde a é um valor de entrada e n é um valor de saída.
Já em uma tabuada completa daquela que se aprende nas escolas, temos todos os valores de a × b = n, onde a e b variam de 0 a 10 e n é a saída. Neste caso, temos duas entradas.
Você pode montar tabelas desse tipo para qualquer função, operador ou expressão matemática. Por exemplo, eis a tabela da função f(x) = x² + 2:
x | f(x)
----+------
0 | 2
1 | 3
2 | 6
3 | 11
4 | 18
5 | 27
6 | 38
...
Agora, imagine que ao invés de números, você utilize valores booleanos para montar essas tabelas. Os valores de entrada e de saída agora são apenas conjuntos de verdadeiro e falso. Por exemplo, eis a tabela da função f(x) = NÃO x:
x | f(x)
---+-----
V | F
F | V
Essa tabela para funções ou operadores booleanos é a tabela-verdade. É o equivalente em lógica booleana para as tabelas de tabuadas das operações matemáticas.
Há uma coisa interessante a se notar aqui. As tabelas de tabuadas matemáticas são geralmente infinitas. Isso ocorre porque os possíveis valores de entrada também são infinitos. Por exemplo, numa tabela de tabuada do 3 (3 × a = n), há infinitos possíveis valores para a, e portanto, infinitas linhas na tabela. Já no caso das tabelas verdade, como cada variável só pode ter um número finito de valores (e esse número é 2 - verdadeiro ou falso), então o tamanho da tabela é finita.
Os operadores básicos da lógica booleana são o NÃO (denotador pelo símbolo ¬
), o OU (denotado por ∨
) e o E (denotado por ∧
). Outros operadores que você vai encontrar também são o OU-EXCLUSIVO (também chamado de XOR, denotado por ⊻
), a EQUIVALÊNCIA (denotado por ↔
) e a IMPLICAÇÃO (denotado por →
). Estas são as tabelas-verdade deles:
x | ¬x
---+----
V | F
F | V
x | y | x ∧ y
---+---+-------
V | V | V
V | F | F
F | V | F
F | F | F
x | y | x ∨ y
---+---+-------
V | V | V
V | F | V
F | V | V
F | F | F
x | y | x ⊻ y
---+---+-------
V | V | F
V | F | V
F | V | V
F | F | F
x | y | x ↔ y
---+---+-------
V | V | V
V | F | F
F | V | F
F | F | V
x | y | x → y
---+---+-------
V | V | V
V | F | F
F | V | V
F | F | V
Podemos ver que todas as tabelas verdade acima (exceto a do NÃO) têm as mesmas variáveis como entrada. Podemos construir então uma tabela assim:
x | y | x ∧ y | x ∨ y | x ⊻ y | x ↔ y | x → y
---+---+-------+-------+-------+-------+-------
V | V | V | V | F | V | V
V | F | F | V | V | F | F
F | V | F | V | V | F | V
F | F | F | F | F | V | V
Isso daí na verdade são 5 tabelas verdades colocadas lado a lado, pois as entradas são as mesmas. Mas isso serve para poder comparar os diferentes valores de saída quando os valores de entrada são os mesmos.
Um exemplo de uma tabela-verdade mais complicadinha é a de uma função f(x, y, z) = (x ∧ y) ∨ ¬z:
x | y | z | f(x, y, z)
---+---+---+------------
V | V | V | V
V | F | V | F
F | V | V | F
F | F | V | F
V | V | F | V
V | F | F | V
F | V | F | V
F | F | F | V
Quanto ao tamanho da tabela-verdade, podemos ver que a tabela lista em cada linha, uma possível combinação de valores de entrada. Sabendo que cada variável têm dois possíveis valores, então uma tabela-verdade de uma função/operador/expressão booleana de n variáveis precisará de 2n linhas da tabela para listar todas as combinações de entrada possíveis.
Uma forma de se comparar se duas ou mais funções/operadores/expressões são equivalentes é comparando as tabelas-verdade. Por exemplo, vamos comparar as expressões x → y, y ∨ ¬x e y → x:
x | y | x → y | y ∨ ¬x | y → x
---+---+-------+--------+-------
V | V | V | V | V
V | F | F | F | V
F | V | V | V | F
F | F | V | V | V
Olhando para essas tabelas, podemos concluir que a expressão x → y produz o mesmo resultado que y ∨ ¬x, pois as tabelas-verdades delas são iguais. Se são iguais então são expressões equivalentes (tal como c + c é equivalente a 2 × c ou como c × c é equivalente a c2). Entretanto, elas são diferentes que y → x.