Fórmula bem formada

Question

Prove que qualquer expressão (para lógica proposicional) com mais parênteses à esquerda do que à direita não é uma fórmula bem formada.

Meus pensamentos: Sempre que o problema afirma "qualquer expressão", fico muito desconfiado de como é possível provar essa afirmação. Seria muito bem-vindo saber suas idéias sobre a prova desta tarefa.

Nota: Fórmulas bem formadas de lógica de predicado 1) Fórmulas atômicas são wffs. 2) Se α e β são wffs, então o são (¬α), (α ∧ β), (α ∨ β) e (α → β). 3) Se x é uma variável e α é uma wff, então (∀x) α e (∃x) α são wffs.

Answer 1

Observe que a contraposição da afirmação que queremos provar é:

Uma fórmula bem formada não tem mais parênteses à esquerda do que à direita.

A definição de fórmulas bem formadas tem uma estrutura recursiva, que se presta a uma abordagem indutiva para tais provas. Na verdade, provaremos o resultado ligeiramente mais forte de que o número de parênteses à esquerda é igual ao número de parênteses à direita em qualquer fórmula bem formada.

A etapa básica em nossa indução segue a maneira como os wff s são definidos recursivamente, começando com "fórmulas atômicas":

1. As fórmulas atômicas são wffs.

Na lógica proposicional, as fórmulas atômicas são variáveis ​​proposicionais, tipicamente representadas por letras, mas tecnicamente queremos um suprimento inesgotável, então formalmente uma linguagem lógica terá infinitas variáveis ​​proposicionais disponíveis.

Entretanto, o ponto crucial de qualquer linguagem usada é que as variáveis ​​proposicionais não contêm parênteses, então zero parênteses à esquerda é igual à contagem de zero parênteses à direita. E isso estabelece a etapa básica.

Agora, para a etapa de indução. A lógica proposicional nos dá essas operações para transformar fórmulas mais simples em outras mais complicadas:

1. E se $α$ e $β$ são wffs, então são $(¬α)$, $(α ∧ β)$, $(α ∨ β)$ e $(α → β)$.

A hipótese de indução é que separadamente as wffs $\alpha$ e $\beta$cada um tem um número igual de parênteses esquerdo e direito. Como cada uma das "regras de produção" mostradas em (2) introduz exatamente um parêntese esquerdo e um parêntese direito, as novas fórmulas bem formadas geradas por essas regras também terão um número igual de parênteses esquerdo e direito.

E isso completa a etapa de indução, mostrando que wffs sempre têm um número igual de parênteses à esquerda como parênteses à direita.