Verifique se os conjuntos que seguem são completos:
(d)
(d)
Passo 1
O enunciado pede para a gente verificar se o conjunto de conectivos {→, ∧} é funcionalmente completo, ou seja, se com eles conseguimos expressar todas as funções booleanas. O tema é completude funcional e vamos usar o Teorema de Post, que diz que um conjunto é completo se, e somente se, não ficar contido em nenhum dos cinco clones fechados: preserva-0, preserva-1, monotônico, auto-dual ou linear.
Passo 2
Primeiro vamos checar a preservação de 0: uma função f é preserva-0 se f(0,…,0)=0. Para ∧ temos
, mas para → temos
. Logo, → não preserva 0, então o conjunto quebra o clone preserva-0.
Passo 3
Agora vamos checar a preservação de 1: uma função f é preserva-1 se f(1,…,1)=1. Para ∧ temos
e para → temos
. Ambos preservam 1, então todo o clone gerado por {→, ∧} ficará contido em preserva-1.
Passo 4
Embora o conjunto quebre preserva-0, ele NÃO quebra preserva-1 (já que ambos conectivos produzem 1 quando as entradas são todas 1). Isso significa que o clone gerado está contido no conjunto de funções preserva-1, e portanto não é abrangente a ponto de produzir, por exemplo, a função constante 0.
Passo 5
Como o Teorema de Post exige que o conjunto gerador quebre TODOS os cinco clones ao mesmo tempo para ser completo, e aqui falha em quebrar preserva-1, concluímos que {→, ∧} não é funcionalmente completo.
Resposta
O conjunto {→, ∧} não é funcionalmente completo, pois preserva 1 e fica contido no clone das funções que mandam todas as entradas 1 em saída 1.