Verifique se os conjuntos que seguem são completos:
(a)
(a)
Passo 1
O enunciado pede para verificar se o conjunto de conectivos {
,
} é 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
e
são monotônicas: se trocarmos algum argumento de
de falso para verdadeiro, o valor da fórmula nunca muda de verdadeiro para falso. Logo, qualquer fórmula construída só com
e
é 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
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
usando só
e
.
Passo 5
Portanto, não conseguimos gerar todas as funções booleanas (especificamente a negação) com {
,
}, logo esse conjunto não é funcionalmente completo.
Resposta
O conjunto {
,
} não é funcionalmente completo.