Unicidade e Equilíbrio de Fórmulas

Unicidade de Representação de Fórmulas

Teorema: Toda fórmula se escreve de uma e uma só maneira como sucessão finita (justaposição, arranjo ou concatenação) de símbolos do alfabeto.

Prova por indução na complexidade das fórmulas:

Seja D o conjunto das fórmulas que se escrevem de uma e uma só maneira como sucessão finita de símbolos do alfabeto.

Caso base: Seja p uma letra proposicional. Como p é um símbolo do alfabeto, há uma e uma só forma de escrever esta sucessão finita de símbolos do alfabeto. Logo, p ∈ D.

Passo indutivo:

• Negação: Seja Φ uma fórmula em D. Então Φ admite uma única forma de escrita como sucessão finita de símbolos do alfabeto. Como o conetivo principal de ¬Φ é a negação, ¬Φ também admite uma única forma de escrita como sucessão finita de símbolos do alfabeto.
• Conectivos binários: Sejam Φ e Ψ fórmulas em D. Então Φ e Ψ admitem formas únicas de serem escritas como sucessões finitas de símbolos do alfabeto. Seja ♦ um dos conectivos ∧, ∨ ou →. Então, como ♦ é o conectivo principal de Φ ♦ Ψ, esta fórmula também se escreve de forma única como sucessão finita de símbolos do alfabeto.

Logo, ¬Φ, Φ ∧ Ψ, Φ ∨ Ψ, Φ → Ψ ∈ D.

Portanto, D é indutivo e, pelo princípio da indução na complexidade das fórmulas, D = PROP(P).

Lema do Equilíbrio

Lema: Toda fórmula é equilibrada (o número de parênteses esquerdos é igual ao número de parênteses direitos).

Prova por indução na complexidade das fórmulas:

Seja D o conjunto das fórmulas que são equilibradas.

Caso base: Se Φ for uma letra proposicional, então Φ não tem parênteses, portanto Φ ∈ D.

Passo indutivo: Sejam Φ, Ψ ∈ D. Seja m o número de parênteses esquerdos de Φ (igual ao número de parênteses direitos de Φ). Seja n o número de parênteses esquerdos de Ψ (igual ao número de parênteses direitos de Ψ). Então:

• Conjunção: Φ ∧ Ψ tem m + n + 1 parênteses esquerdos e m + n + 1 parênteses direitos. Logo, Φ ∧ Ψ ∈ D.
• Disjunção e Condicional: Analogamente, D é fechado para a disjunção e para a condicional.
• Negação: A fórmula ¬Φ tem m parênteses esquerdos e m parênteses direitos. Portanto, é equilibrada. Logo, D é fechado para a negação.

Assim, D é um conjunto indutivo e, pelo princípio da indução na complexidade das fórmulas, D = FORM(fº).