Verifique se os conjuntos que seguem são completos:
(d)
, wed>=

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 0land0=0, mas para → temos 0to0=1. 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 1land1=1 e para → temos 1to1=1. 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.

Exercícios relacionados