Determine quais as subfórmulas e o comprimento das fórmulas a seguir.
neg(P neg P)

Passo 1

O enunciado pede para listar todas as subfórmulas de ¬(P → ¬P) e calcular o comprimento de cada uma. O conteúdo é lógica proposicional e vamos precisar usar a definição de subfórmula (qualquer parte que também seja fórmula) e a definição de comprimento (número de ocorrências de conectivos e variáveis atômicas).

Passo 2

Uma subfórmula de uma fórmula é qualquer ocorrência de parte da fórmula que, por si só, seja também uma fórmula válida; inclui as fórmulas atômicas, fórmulas formadas por conectivos intermediários e a própria fórmula inteira.

Passo 3

Aplicando isso a ¬(P → ¬P), as subfórmulas são:
As fórmulas atômicas aparecem primeiro: P
A seguir, aparece a negação interna: ¬P
Depois, a implicação completa dentro da negação externa: (P → ¬P)
E por fim a própria fórmula original: ¬(P → ¬P)

Passo 4

O comprimento de uma fórmula ℓ(φ) é dado pela soma de todas as ocorrências de variáveis atômicas e conectivos. Vamos contar cada caso:
Para φ = P temos ℓ§ = 1 (apenas a variável).
Para φ = ¬P temos ℓ(¬P) = ℓ§ + 1 = 1 + 1 = 2 (a variável e o conectivo ¬).
Para φ = (P → ¬P) temos ℓ(P → ¬P) = ℓ§ + ℓ(¬P) + 1 = 1 + 2 + 1 = 4 (duas variáveis, um ¬ e um →).
Para φ = ¬(P → ¬P) temos ℓ(¬(P → ¬P)) = ℓ(P → ¬P) + 1 = 4 + 1 = 5 (a implicação interna e o ¬ externo).

Resposta

As subfórmulas de neg(P neg P) são P, neg P, (P neg P) e neg(P neg P). Os comprimentos são:
ell(P)=1, ell(neg P)=2, ell(P neg P)=4 e ell(neg(P neg P))=5.

Exercícios relacionados