Exercício 10:

Mostre que neg, vee é um conjunto de conectivos funcionalmente completo.

Passo 1

O enunciado pede para mostrar que o conjunto de conectivos neg,vee é 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 neg quanto a conjunção land (ou a disjunção vee) para obter uma base completa, pois qualquer fórmula pode ser escrita em forma normal disjuntiva, que usa apenas land, vee e neg.

Passo 3

Para exprimir a conjunção usando somente neg e vee, aplicamos a lei de De Morgan:
p land q equiv negl(neg p vee neg qr)

Passo 4

Com essa equivalência, já demonstramos que conseguimos construir land a partir de neg e vee. Como a base neg,vee 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 neg,vee é 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.

Exercícios relacionados