Demonstre que para toda fórmula
vale que grau(
) é no máximo o número de conectivos lógicos que aparecem em
. Demonstre também que grau
para toda subfórmula própria
da fórmula
.
Passo 1
Beleza, vamos começar resumindo o que o exercício está pedindo. Precisamos mostrar duas coisas sobre fórmulas lógicas:
- Grau da fórmula: Para qualquer fórmula lógica
, o grau de (denotado por ) é no máximo igual ao número de conectivos lógicos que aparecem nela. - Grau das subfórmulas: Para toda subfórmula própria
de , o grau de é menor que o grau de .
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,
, é 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:
-
(negação) -
(conjunção) -
(disjunção) -
(implicação) -
(bicondicional)
Por exemplo, na fórmula
, temos dois conectivos:
e
. 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
é no máximo o número de conectivos nela. Para isso, vamos usar indução estrutural na fórmula
.
Base da Indução:
- Se
é uma proposição atômica (como , , etc.), não há conectivos, então . E o número de conectivos também é 0. Logo, número de conectivos.
Passo Indutivo:
- Suponha que para todas as subfórmulas menores de
, a afirmação seja verdadeira. - Se
é formada por um conectivo aplicado a subfórmulas, por exemplo, , então: - O número de conectivos em
é 1 (do ) mais o número de conectivos em . - Pelo passo indutivo,
número de conectivos em . - Assim,
número de conectivos em + 1 = número de conectivos em .
- O número de conectivos em
- O mesmo raciocínio vale para outros conectivos binários como
, , etc.
Portanto, por indução, a afirmação é verdadeira:
número de conectivos em
.
Passo 4
Agora, vamos demonstrar que para qualquer subfórmula própria
de
, o
.
Novamente, usaremos indução estrutural.
Base da Indução:
- Se
é 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 . Logo, .
Passo Indutivo:
- Suponha que para todas as subfórmulas de fórmulas menores que
, a afirmação seja verdadeira. - Se
, onde é um conectivo lógico e é uma subfórmula, então: -
. - Pela hipótese indutiva,
, já que adicionamos um conectivo.
-
- Isso vale para qualquer conectivo que forme
a partir de subfórmulas.
Portanto,
para toda subfórmula própria
de
.
Resposta
Demonstramos que para toda fórmula lógica
, o grau de
é no máximo o número de conectivos lógicos presentes nela. Além disso, mostramos que qualquer subfórmula própria
de
tem grau menor que o de
. Isso confirma as duas afirmações propostas no exercício.