Forma normal e lógica de Backus

Question

Dado o alfabeto de ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$, escreva uma gramática de forma normal Backus que gere todas as fórmulas proposicionais legais. Para começar é dado que

dígito :: = $“0” | “1” | “2” | “3” | ... | “8” | “9”$

inteiro :: = dígito | dígito, inteiro

$A ::= P \mid P, \text{integer} \quad $ // gera $P, P_1, ...$

$B ::= Q \mid Q, \text{integer} \quad $ // gera $Q, Q_1, ...$

$C ::= R \mid R, \text{integer} \quad$ // gera $R, R_1, ...$

É suficiente gerar fórmulas totalmente entre parênteses sem omissão de parênteses. Você pode usar$“...”$ para indicar omissão como na gramática BNF acima.

Meu progresso: consegui entender o tópico da forma normal do Backus e suas aplicações, mas tive dificuldade em associar a gramática da forma normal do Backus com as regras legais proposicionais. Obviamente, essas regras são bem conhecidas e compreensíveis, mas eu não sabia como indicar fórmulas totalmente entre parênteses?

Answer 1

Vamos primeiro escrever a gramática BNF de todas as fórmulas proposicionais atômicas (denotadas por$\mathcal{A}$):

\begin{align} \mathcal{A} ::= A \mid B \mid C \mid \dots \end{align}

Onde $A$, $B$, $C$, $\dots$são definidos na postagem original. Observe que esta definição não requer nenhuma forma de indução, além daquela usada na definição de inteiro na postagem original.

Então, a gramática BNF de todas as fórmulas proposicionais (denotadas por $\mathcal{F}, \mathcal{G}$, $\dots$) é o seguinte:

\begin{align} \mathcal{F}, \mathcal{G} ::= \mathcal{A} \mid \lnot \mathcal{F} \mid (\mathcal{F} \land \mathcal{G}) \mid (\mathcal{F} \lor \mathcal{G}) \mid (\mathcal{F} \to \mathcal{G}) \end{align}

Observe que, de acordo com esta definição, $P \to Q$não é uma fórmula proposicional, porque faltam parênteses. A fórmula proposicional correta neste caso é$(P \to Q)$.

Este uso massivo de parênteses é necessário para evitar expressões ambíguas, como $P \land Q \lor R$podem ser considerados como fórmulas proposicionais. Na verdade, em$P \land Q \lor R$não está claro qual é o conectivo principal. Fórmulas proposicionais corretas são$((P \land Q) \lor R)$ e $(P \land (Q \lor R))$, onde nenhuma ambigüidade surge.