Seja H uma fórmula que não contém o conectivo
.
a) Qual a paridade de comp[H]?
b) Qual a relação entre comp[H] e o número de conectivos de H ?
a) Qual a paridade de comp[H]?
b) Qual a relação entre comp[H] e o número de conectivos de H ?
Passo 1
O enunciado fala de uma fórmula
que não contém o conectivo
. Define-se a função de complexidade
por indução:
onde
é qualquer conectivo binário
. Como
não tem
, cada ocorrência de conectivo em
é binária. Precisamos então descobrir a paridade de
e relacioná-la com o número de conectivos de
.
Passo 2
Fazemos indução sobre a árvore de construção de
.
Caso base: se
é um proposicional atômico
, então
e o número de conectivos em
é zero. Logo
Isso fecha o caso base.
Passo 3
Passo indutivo: suponha que a propriedade valha para quaisquer subfórmulas
e
, ou seja,
Considere então a fórmula
. Como
é binário e não há
, nem
nem
contêm
. Então
Mas o número total de conectivos em
é justamente
porque somamos todos os de
, todos os de
e mais a raiz
. Logo
Isso conclui a indução.
Passo 4
Da igualdade
segue imediatamente que a paridade de
é a mesma paridade do número de conectivos de
. Em particular,
Resposta
a) A paridade de
é exatamente a mesma paridade do número de conectivos em
.
b) De fato vale
b) De fato vale