Considere a proposição composta
definida pela tabela abaixo.
Mostre que
é logicamente equivalente à proposição
. Compare essa proposição com as três linhas da tabela que terminam com
. Utilize a mesma ideia para justificar que qualquer tabela verdade em um número qualquer de proposições
é a tabela verdade de alguma proposição composta envolvendo as
e usando apenas os conectivos
. Consequentemente qualquer proposição composta (envolvendo os conectivos usuais ou algum outro que venha a ser inventado) é equivalente a uma proposição que utiliza somente esses três conectivos.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Passo 1
O enunciado nos dá a tabela de verdade de
e pede para mostrar que ela é equivalente à proposição
Estamos, portanto, trabalhando com a construção de uma forma normal disjuntiva (DNF) de uma função booleana. Para isso, basta olhar para cada linha em que
é verdadeira e montar uma conjunção que seja verdadeira só nessa linha.
Passo 2
Da tabela,
exatamente nas linhas
Para cada uma, construímos uma conjunção que valide cada variável na forma correta:
- Na linha 1:
. - Na linha 2:
. - Na linha 3:
.
Passo 3
Agora juntamos essas três conjunções com uma disjunção para obter uma fórmula que seja verdadeira exatamente nessas e somente nessas linhas. Assim,
Comparando com a tabela, cada linha que dá
em
corresponde a uma das conjunções, e em todas as outras linhas todas as conjunções dão
, logo o disjuntor geral também dá
. Isso prova a equivalência.
Passo 4
O mesmo procedimento vale para qualquer número
de proposições
. Dada qualquer tabela verdade, basta:
- Enumerar as linhas em que a função booleana
vale . - Para cada linha i, montar a conjunção
, onde - Fazer a disjunção de todas essas conjunções:
Passo 5
Como qualquer proposição composta pode ser vista como uma função booleana por sua tabela-verdade, concluímos que ela é sempre equivalente a uma DNF que usa apenas os conectivos
,
e
. Isso mostra que esses três conectivos são suficientes (formam um conjunto funcionalmente completo) para expressar qualquer proposição.
Resposta
e, em geral, qualquer tabela verdade em
variáveis tem uma DNF da forma