Demonstre que para toda fórmula alpha vale que grau( alpha ) é no máximo o número de conectivos lógicos que aparecem em alpha. Demonstre também que grau (beta) para toda subfórmula própria beta da fórmula alpha.

Passo 1

Beleza, vamos começar resumindo o que o exercício está pedindo. Precisamos mostrar duas coisas sobre fórmulas lógicas:
  1. Grau da fórmula: Para qualquer fórmula lógica alpha, o grau de alpha (denotado por grau(alpha)) é no máximo igual ao número de conectivos lógicos que aparecem nela.
  2. Grau das subfórmulas: Para toda subfórmula própria beta de alpha, o grau de beta é menor que o grau de alpha.
Aqui, estamos lidando com Lógica Proposicional, especificamente analisando conectivos lógicos e a estrutura das fórmulas. Vamos precisar entender o que significa o “grau” de uma fórmula e como identificar e contar os conectivos lógicos.

Passo 2

Primeiro, vamos definir o que é o grau de uma fórmula lógica. O grau de uma fórmula, grau(alpha), é o número máximo de conectivos aninhados em qualquer parte da fórmula. Isso significa que estamos medindo a profundidade da estrutura lógica da fórmula.
Conectivos lógicos são símbolos como:
  • neg (negação)
  • land (conjunção)
  • lor (disjunção)
  • (implicação)
  • rightarrow (bicondicional)
Por exemplo, na fórmula alpha = neg (p land q), temos dois conectivos: neg e land. O grau dessa fórmula é 2, já que a negação está “aninhada” sobre a conjunção.

Passo 3

Agora, vamos mostrar que o grau de qualquer fórmula alpha é no máximo o número de conectivos nela. Para isso, vamos usar indução estrutural na fórmula alpha.
Base da Indução:
  • Se alpha é uma proposição atômica (como p, q, etc.), não há conectivos, então grau(alpha) = 0. E o número de conectivos também é 0. Logo, grau(alpha) <= número de conectivos.
Passo Indutivo:
  • Suponha que para todas as subfórmulas menores de alpha, a afirmação seja verdadeira.
  • Se alpha é formada por um conectivo aplicado a subfórmulas, por exemplo, alpha = neg beta, então:
    • O número de conectivos em alpha é 1 (do neg) mais o número de conectivos em beta.
    • Pelo passo indutivo, grau(beta) <= número de conectivos em beta.
    • Assim, grau(alpha) = grau(beta) + 1 <= número de conectivos em beta + 1 = número de conectivos em alpha.
  • O mesmo raciocínio vale para outros conectivos binários como land, lor, etc.
Portanto, por indução, a afirmação é verdadeira: grau(alpha) <= número de conectivos em alpha.

Passo 4

Agora, vamos demonstrar que para qualquer subfórmula própria beta de alpha, o grau(beta) < grau(alpha).
Novamente, usaremos indução estrutural.
Base da Indução:
  • Se alpha é formada por um único conectivo aplicado a uma proposição atômica, então sua única subfórmula própria é a proposição atômica, que tem grau 0. E grau(alpha) = 1. Logo, 0 < 1.
Passo Indutivo:
  • Suponha que para todas as subfórmulas de fórmulas menores que alpha, a afirmação seja verdadeira.
  • Se alpha = C(beta), onde C é um conectivo lógico e beta é uma subfórmula, então:
    • grau(alpha) = grau(beta) + 1.
    • Pela hipótese indutiva, grau(beta) < grau(alpha), já que adicionamos um conectivo.
  • Isso vale para qualquer conectivo que forme alpha a partir de subfórmulas.
Portanto, grau(beta) < grau(alpha) para toda subfórmula própria beta de alpha.

Resposta

Demonstramos que para toda fórmula lógica alpha, o grau de alpha é no máximo o número de conectivos lógicos presentes nela. Além disso, mostramos que qualquer subfórmula própria beta de alpha tem grau menor que o de alpha. Isso confirma as duas afirmações propostas no exercício.

Exercícios relacionados