Mostre que o conjunto neg, wed>= é 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 A lor B é logicamente equivalente a “não (não A e não B)”. Então definimos
A lor B equiv neg(neg A wed>= neg B)
Aqui usamos apenas ¬ e ∧.

Passo 3

Implicação como negação de conjunção: lembrando que A to B é equivalente a “não (A e não B)”, temos
A to B equiv neg(A wed>= neg B)
Novamente só aparecem ¬ e ∧.

Passo 4

Equivalência a partir de → e ∧: o bicondicional A rightarrow B vale quando A to B e B to A são verdadeiros. Assim
A rightarrow B equiv (A to B) wed>= (B to A)
Para completar, substituímos cada to pela sua definição em ¬ e ∧, obtendo só esses dois conectivos.

Passo 5

Definição de constantes lógico-verdade top e contradição bot: muitas vezes precisamos de constantes. Podemos definir
bot equiv P wed>= neg P,
para qualquer proposição P, e então
top equiv neg(P wed>= neg P) equiv negbot
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.

Exercícios relacionados