Exercício 10:
Mostre que
é um conjunto de conectivos funcionalmente completo.
Passo 1
O enunciado pede para mostrar que o conjunto de conectivos
é funcionalmente completo. Esse conceito faz parte de lógica proposicional, e vamos precisar da definição de completude funcional e da equivalência de De Morgan.
Passo 2
Uma base de conectivos é funcionalmente completa se, usando apenas ela, podemos expressar todas as funções booleanas. Um critério prático é que basta mostrar que conseguimos expressar tanto a negação
quanto a conjunção
(ou a disjunção
) para obter uma base completa, pois qualquer fórmula pode ser escrita em forma normal disjuntiva, que usa apenas
,
e
.
Passo 3
Para exprimir a conjunção usando somente
e
, aplicamos a lei de De Morgan:
Passo 4
Com essa equivalência, já demonstramos que conseguimos construir
a partir de
e
. Como a base
já contém a disjunção, concluímos que ela gera todos os conectivos necessários para escrever qualquer fórmula proposicional em forma normal disjuntiva.
Resposta
O conjunto
é funcionalmente completo porque, além de conter a negação e a disjunção, permite definir a conjunção via De Morgan, garantindo a expressão de qualquer fórmula proposicional.