Forma normal y lógica de Backus

Question

Dado el alfabeto de ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$, escribe una gramática de forma normal de Backus que genere todas las fórmulas proposicionales legales. Para empezar se da que

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

entero :: = dígito | dígito, entero

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

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

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

Basta con generar fórmulas completamente entre paréntesis que no tengan omisión de paréntesis. Puedes utilizar$“...”$ para indicar omisión como en la gramática BNF anterior.

Mi progreso: Me las arreglé para comprender el tema de la forma normal de Backus y sus aplicaciones, pero había tenido problemas para asociar la gramática de la forma normal de Backus con las reglas proposicionales legales. Obviamente, estas reglas son bien conocidas y comprensibles, pero no me di cuenta de cómo indicar fórmulas completamente entre paréntesis.

Answer 1

Primero escribamos la gramática BNF de todas las fórmulas proposicionales atómicas (denotadas por$\mathcal{A}$):

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

dónde $A$, $B$, $C$, $\dots$se definen en la publicación original. Tenga en cuenta que esta definición no requiere ninguna forma de inducción, aparte de la utilizada en la definición de entero en la publicación original.

Entonces, la gramática BNF de todas las fórmulas proposicionales (denotada por $\mathcal{F}, \mathcal{G}$, $\dots$) es el siguiente:

\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}

Tenga en cuenta que, según esta definición, $P \to Q$no es una fórmula proposicional, porque faltan paréntesis. La fórmula proposicional correcta en este caso es$(P \to Q)$.

Este uso masivo de paréntesis es necesario para evitar expresiones ambiguas como $P \land Q \lor R$pueden considerarse como fórmulas proposicionales. De hecho, en$P \land Q \lor R$no está claro cuál es el conectivo principal. Las fórmulas proposicionales correctas son$((P \land Q) \lor R)$ y $(P \land (Q \lor R))$, donde no surge ninguna ambigüedad.