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.
\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.