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
), 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 é
e
é par.
Passo 3
Passo indutivo – negação: suponha que
seja uma fbf cujo número de símbolos de pontuação é par. A negação
não acrescenta parênteses, pois a regra de formação é apenas
é fbf, então
é fbf.})
Logo o número total de parênteses em continua sendo o mesmo de
, o qual, por hipótese indutiva, é par.
Logo o número total de parênteses em
Passo 4
Passo indutivo – conectivo binário: suponha que
e
sejam fbf com número par de símbolos de pontuação. Para formar
, onde
é qualquer conectivo binário
, introduzimos exatamente um “
” e um “
” novos. Assim, se
tem
pontuações e
tem
, então
terá
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.