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

Passo 1

O enunciado pede o comprimento e as subfórmulas de \displaystyle \varphi = \bigl((\neg \neg \mathrm P \,\vee\, \mathrm Q)\;\leftrightarrow\;(\mathrm P \rightarrow \mathrm Q)\bigr)\;\wedge\;\text{true}.
O conteúdo é lógica proposicional, e vamos usar a definição recursiva de comprimento de fórmula e a noção de subfórmula.

Passo 2

Definição de comprimento \lvert\cdot\rvert:
para átomo ou constante tem-se \lvert \alpha\rvert = 1;
para negação \lvert \neg \varphi\rvert = 1 + \lvert \varphi\rvert;
para conectivo binário \Box \lvert \varphi \Box \psi\rvert = 1 + \lvert \varphi\rvert + \lvert \psi\rvert.

Passo 3

Calculemos passo a passo:
\lvert \mathrm P\rvert = 1,\quad \lvert \mathrm Q\rvert = 1,\quad \lvert \text{true}\rvert = 1.
\lvert \neg \mathrm P\rvert = 1 + \lvert \mathrm P\rvert = 2,\quad \lvert \neg \neg \mathrm P\rvert = 1 + 2 = 3.
\lvert \neg \neg \mathrm P \vee \mathrm Q\rvert = 1 + 3 + 1 = 5,\quad \lvert \mathrm P \rightarrow \mathrm Q\rvert = 1 + 1 + 1 = 3.
\bigl\lvert(\neg \neg \mathrm P \vee \mathrm Q)\leftrightarrow(\mathrm P \rightarrow \mathrm Q)\bigr\rvert = 1 + 5 + 3 = 9.
\lvert \varphi\rvert = \Bigl\lvert\bigl((\neg \neg \mathrm P \vee \mathrm Q)\leftrightarrow(\mathrm P \rightarrow \mathrm Q)\bigr)\wedge\text{true}\Bigr\rvert = 1 + 9 + 1 = 11.

Passo 4

O conjunto de subfórmulas de \varphi é
\mathrm{Sub}(\varphi) = \bigl\{\mathrm P,\;\neg \mathrm P,\;\neg \neg \mathrm P,\;\mathrm Q,\;(\neg \neg \mathrm P \vee \mathrm Q),\; (\mathrm P \rightarrow \mathrm Q),\; ((\neg \neg \mathrm P \vee \mathrm Q)\leftrightarrow(\mathrm P \rightarrow \mathrm Q)),\;\text{true},\;\varphi\bigr\}.

Resposta

O comprimento de \varphi é 11 e suas subfórmulas são \mathrm P, \neg \mathrm P, \neg \neg \mathrm P, \mathrm Q, (\neg \neg \mathrm P \vee \mathrm Q), (\mathrm P \rightarrow \mathrm Q), ((\neg \neg \mathrm P \vee \mathrm Q)\leftrightarrow(\mathrm P \rightarrow \mathrm Q))), \text{true} e \varphi.

Exercícios relacionados