Seja H uma fórmula que não contém o conectivo \neg.
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 H que não contém o conectivo \neg. Define-se a função de complexidade \mathsf{comp}(\cdot) por indução:
\mathsf{comp}(p)=0,\quad \mathsf{comp}(\neg\varphi)=\mathsf{comp}(\varphi)+1,\quad \mathsf{comp}(\varphi\;\Box\;\psi)=\mathsf{comp}(\varphi)+\mathsf{comp}(\psi)+1,
onde \Box é qualquer conectivo binário \wedge,\vee,\to,\leftrightarrow. Como H não tem \neg, cada ocorrência de conectivo em H é binária. Precisamos então descobrir a paridade de \mathsf{comp}(H) e relacioná-la com o número de conectivos de H.

Passo 2

Fazemos indução sobre a árvore de construção de H.
Caso base: se H é um proposicional atômico p, então
\mathsf{comp}(p)=0
e o número de conectivos em p é zero. Logo
\mathsf{comp}(p)=0=\#\{\text{conectivos em }p\}.
Isso fecha o caso base.

Passo 3

Passo indutivo: suponha que a propriedade valha para quaisquer subfórmulas \varphi e \psi, ou seja,
\mathsf{comp}(\varphi)=\#\{\text{conectivos em }\varphi\}, \qquad \mathsf{comp}(\psi)=\#\{\text{conectivos em }\psi\}.
Considere então a fórmula H=(\varphi\;\Box\;\psi). Como \Box é binário e não há \neg, nem \varphi nem \psi contêm \neg. Então
\mathsf{comp}(H) =\mathsf{comp}(\varphi)+\mathsf{comp}(\psi)+1 =\#\{\text{conectivos em }\varphi\}+\#\{\text{conectivos em }\psi\}+1.
Mas o número total de conectivos em H é justamente
\#\{\text{conectivos em }\varphi\}+\#\{\text{conectivos em }\psi\}+1,
porque somamos todos os de \varphi, todos os de \psi e mais a raiz \Box. Logo
\mathsf{comp}(H)=\#\{\text{conectivos em }H\}.
Isso conclui a indução.

Passo 4

Da igualdade
\mathsf{comp}(H)=\#\{\text{conectivos em }H\},
segue imediatamente que a paridade de \mathsf{comp}(H) é a mesma paridade do número de conectivos de H. Em particular,
\mathsf{comp}(H)\bmod2 =\bigl(\#\{\text{conectivos em }H\}\bigr)\bmod2.

Resposta

a) A paridade de \mathsf{comp}(H) é exatamente a mesma paridade do número de conectivos em H.
b) De fato vale
\mathsf{comp}(H)=\#\{\text{conectivos de }H\}.

Exercícios relacionados