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

Passo 1

O enunciado pede para verificar se o conjunto de conectivos { wed>=, vee} é funcionalmente completo na lógica proposicional, ou seja, se com ele podemos expressar toda função booleana.

Passo 2

Uma base de conectivos é funcionalmente completa quando, combinando-a, conseguimos obter todas as funções booleanas possíveis. Em particular, é preciso poder expressar a negação, pois ela inverte valores de verdade.

Passo 3

As operações wed>= e vee são monotônicas: se trocarmos algum argumento de F de falso para verdadeiro, o valor da fórmula nunca muda de verdadeiro para falso. Logo, qualquer fórmula construída só com wed>= e vee é monotônica.

Passo 4

A negação não é monotônica, já que mudar a proposição de falso para verdadeiro faz o valor de neg p mudar de verdadeiro para falso. Como não podemos obter um comportamento não-monotônico apenas com operações monotônicas, não há como expressar neg usando só wed>= e vee.

Passo 5

Portanto, não conseguimos gerar todas as funções booleanas (especificamente a negação) com { wed>=, vee}, logo esse conjunto não é funcionalmente completo.

Resposta

O conjunto { wed>=, vee} não é funcionalmente completo.

Exercícios relacionados