Determine o comprimento e as subfórmulas das fórmulas a seguir:
\neg(\mathrm{P} \rightarrow \neg \mathrm{P})

Passo 1

O enunciado pede para calcular o comprimento (isto é, o número de conectivos contando-se inductivamente) e listar todas as subfórmulas da fórmula
\neg(\mathrm P \rightarrow \neg \mathrm P).
O conteúdo aqui é sintaxe de lógica proposicional, em particular a definição indutiva de comprimento de fórmula e de subfórmula.

Passo 2

Definimos o comprimento \ell(\varphi) de forma indutiva por:
\ell(\mathrm P)=1,
\ell(\neg\varphi)=\ell(\varphi)+1,
\ell(\varphi\rightarrow\psi)=\ell(\varphi)+\ell(\psi)+1.

Passo 3

Vamos calcular do “dentro para fora”:
  1. Para \neg \mathrm P:
\ell(\neg \mathrm P)=\ell(\mathrm P)+1=1+1=2.
  1. Para \mathrm P\rightarrow\neg \mathrm P:
\ell(\mathrm P\rightarrow\neg \mathrm P) =\ell(\mathrm P)+\ell(\neg \mathrm P)+1 =1+2+1=4.
  1. Para \neg(\mathrm P\rightarrow\neg \mathrm P):
\ell\bigl(\neg(\mathrm P\rightarrow\neg \mathrm P)\bigr) =\ell(\mathrm P\rightarrow\neg \mathrm P)+1 =4+1=5.

Passo 4

Uma subfórmula de \varphi é toda fórmula que aparece em \varphi segundo a mesma construção indutiva. Assim, as subfórmulas de \neg(\mathrm P\rightarrow\neg \mathrm P) são:
\mathrm P,\quad \neg \mathrm P,\quad \mathrm P\rightarrow\neg \mathrm P,\quad \neg(\mathrm P\rightarrow\neg \mathrm P).

Resposta

Comprimento: \;5
Subfórmulas:
\{\mathrm P,\;\neg \mathrm P,\;\mathrm P\rightarrow\neg \mathrm P,\;\neg(\mathrm P\rightarrow\neg \mathrm P)\}.

Exercícios relacionados