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

Passo 1

O enunciado pede para calcular o comprimento (ou seja, o tamanho) e as subfórmulas da fórmula proposicional
P \rightarrow \bigl((Q \rightarrow R)\rightarrow\bigl((P \rightarrow R)\rightarrow(P \rightarrow R)\bigr)\bigr).
Aqui usamos a definição recursiva de comprimento: toda proposição atômica tem comprimento 1 e, se \varphi e \psi têm comprimentos c(\varphi) e c(\psi), então
c(\varphi\rightarrow\psi)=c(\varphi)+c(\psi)+1.

Passo 2

Identifiquemos subfórmulas auxiliares:
A = Q\rightarrow R,
B = P\rightarrow R,
D = B\rightarrow B (ou seja, (P\rightarrow R)\rightarrow(P\rightarrow R)),
E = A\rightarrow D (ou seja, (Q\rightarrow R)\rightarrow((P\rightarrow R)\rightarrow(P\rightarrow R)))),
e enfim F=P\rightarrow E.

Passo 3

Calculemos os comprimentos: c(P)=1, c(Q)=1, c(R)=1.
Para A:
c(A)=c(Q)+c(R)+1=1+1+1=3.
Para B:
c(B)=c(P)+c(R)+1=1+1+1=3.
Para D:
c(D)=c(B)+c(B)+1=3+3+1=7.
Para E:
c(E)=c(A)+c(D)+1=3+7+1=11.
Finalmente, para F:
c(F)=c(P)+c(E)+1=1+11+1=13.

Passo 4

As subfórmulas de \,F=P \rightarrow ((Q \rightarrow R)\rightarrow((P \rightarrow R)\rightarrow(P \rightarrow R)))
são exatamente os nós da sua árvore sintática: P, Q, R, (Q\rightarrow R), (P\rightarrow R), (P\rightarrow R)\rightarrow(P\rightarrow R), (Q\rightarrow R)\rightarrow((P\rightarrow R)\rightarrow(P\rightarrow R))),
e a própria P\rightarrow((Q\rightarrow R)\rightarrow((P\rightarrow R)\rightarrow(P\rightarrow R))).

Resposta

Comprimento: 13
Subfórmulas: P, Q, R, (Q\rightarrow R), (P\rightarrow R), (P\rightarrow R)\rightarrow(P\rightarrow R), (Q\rightarrow R)\rightarrow((P\rightarrow R)\rightarrow(P\rightarrow R))), P\rightarrow((Q\rightarrow R)\rightarrow((P\rightarrow R)\rightarrow(P\rightarrow R))).

Exercícios relacionados