Qual a paridade do número de símbolos de pontuação de uma fórmula da LógicaProposicional?

Passo 1

O enunciado pergunta qual é a paridade do número de símbolos de pontuação em qualquer fbf (fórmula bem formada) da Lógica Proposicional. Aqui “símbolos de pontuação” referem-se aos parênteses “ (” e “ )”. Para resolver, vamos usar indução estrutural sobre a formação de fbf, mostrando que em toda fbf esse número é sempre par.

Passo 2

Caso base: toda fórmula atômica, como \(p), não contém parênteses de formação (ela é simplesmente um átomo sem pontuação extra). Logo o número de símbolos de pontuação é 0, e 0 é par.

Passo 3

Passo indutivo – negação: suponha que \varphi seja uma fbf cujo número de símbolos de pontuação é par. A negação \neg \varphi não acrescenta parênteses, pois a regra de formação é apenas \text{se \(\varphi é fbf, então \neg\varphi é fbf.})
Logo o número total de parênteses em \neg\varphi continua sendo o mesmo de \varphi, o qual, por hipótese indutiva, é par.

Passo 4

Passo indutivo – conectivo binário: suponha que \varphi e \psi sejam fbf com número par de símbolos de pontuação. Para formar (\varphi \,\Box\, \psi), onde \Box é qualquer conectivo binário \wedge,\vee,\to,\leftrightarrow, introduzimos exatamente um “ (” e um “ )” novos. Assim, se \varphi tem 2k pontuações e \psi tem 2\ell, então
(\varphi \,\Box\, \psi)
terá
2k + 2\ell + 2 = 2(k+\ell+1)
símbolos de pontuação, que é par.

Passo 5

Conclusão da indução: pela formação de fbf (átomos, negações e conectivos binários), mostramos que a cada passo o número de parênteses permanece par. Logo toda fórmula bem formada da Lógica Proposicional contém sempre um número par de símbolos de pontuação.

Resposta

O número de símbolos de pontuação em qualquer fórmula bem formada da Lógica Proposicional é sempre par.

Exercícios relacionados