Mostre que o conjunto
é completo. Basta mostrar que as fórmulas básicas podem ser reescritas usando-se somente os conectivos de negação e conjunção, além dos símbolos proposicionais (regras de conversão).
Passo 1
Resumo do enunciado: queremos mostrar que a família de conectivos {¬, ∧} é completa, isto é, que toda fórmula proposicional construída com outros conectivos (∨, →, ↔, constantes) pode ser reescrita usando apenas negação e conjunção, além dos símbolos proposicionais. Para isso, vamos dar regras de conversão que substituem cada conectivo extra por expressões com ¬ e ∧.
Passo 2
Disjunção via De Morgan: a ideia é usar a lei de De Morgan. Sabemos que
é logicamente equivalente a “não (não A e não B)”. Então definimos
Aqui usamos apenas ¬ e ∧.
Passo 3
Implicação como negação de conjunção: lembrando que
é equivalente a “não (A e não B)”, temos
Novamente só aparecem ¬ e ∧.
Passo 4
Equivalência a partir de → e ∧: o bicondicional
vale quando
e
são verdadeiros. Assim
Para completar, substituímos cada
pela sua definição em ¬ e ∧, obtendo só esses dois conectivos.
Passo 5
Definição de constantes lógico-verdade
e contradição
: muitas vezes precisamos de constantes. Podemos definir
para qualquer proposição
, e então
Isso usa apenas ¬ e ∧.
Passo 6
Conclusão geral: como mostramos que ∨, →, ↔ e as constantes podem ser reescritas usando apenas ¬ e ∧, qualquer fórmula proposicional pode ser convertida para uma equivalente que use somente esses dois conectivos. Portanto, {¬, ∧} é completo.
Resposta
Qualquer conectivo e constante pode ser expresso só com negação e conjunção, logo {¬, ∧} é uma base funcionalmente completa.