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

Passo 1

Estamos com a fórmula varphi = P to l((Q to R) to ((P to R) to (P to R))r). O conteúdo é lógica proposicional (subfórmulas e comprimento de fórmulas) e vamos usar definições recursivas para subfórmulas e para comprimento.

Passo 2

Definição de subfórmulas: para toda fórmula psi:
  • Se psi é atômica, Sub(psi)=psi.
  • Se psi = negchi, Sub(psi)=psicup Sub(chi).
  • Se psi = chi1 to chi2, Sub(psi)=psicup Sub(chi1)cup Sub(chi2).

Passo 3

Aplicando recursivamente em varphi obtemos as seguintes subfórmulas:
  1. P
  2. Q
  3. R
  4. Q to R
  5. P to R
  6. (P to R) to (P to R)
  7. (Q to R) to ((P to R) to (P to R))
  8. P to ((Q to R) to ((P to R) to (P to R)))

Passo 4

Definição de comprimento |cdot|:
  • |P|=1 para atômica.
  • |negchi| = |chi| + 1.
  • |chi1 to chi2| = |chi1| + |chi2| + 1.

Passo 5

Calculando o comprimento passo a passo:
  • |Q|=1,;|R|=1 então |Qto R| = 1 + 1 + 1 = 3.
  • |P|=1,;|R|=1 então |Pto R| = 1 + 1 + 1 = 3.
  • |(Pto R)to(Pto R)| = 3 + 3 + 1 = 7.
  • |(Qto R)to((Pto R)to(Pto R))| = 3 + 7 + 1 = 11.
  • |Pto((Qto R)to((Pto R)to(Pto R)))| = 1 + 11 + 1 = 13.

Resposta

As subfórmulas são P, Q, R, Qto R, Pto R, (Pto R)to(Pto R), (Qto R)to((Pto R)to(Pto R)) e a própria fórmula Pto((Qto R)to((Pto R)to(Pto R))). O comprimento da fórmula é 13.

Exercícios relacionados