Forme normale et logique de Backus

Question

Compte tenu de l'alphabet de ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$, écrivez une grammaire de forme normale Backus qui génère toutes les formules propositionnelles légales. Pour commencer, il est donné que

chiffre :: = $“0” | “1” | “2” | “3” | ... | “8” | “9”$

entier :: = chiffre | chiffre, entier

$A ::= P \mid P, \text{integer} \quad $ // génère $P, P_1, ...$

$B ::= Q \mid Q, \text{integer} \quad $ // génère $Q, Q_1, ...$

$C ::= R \mid R, \text{integer} \quad$ // génère $R, R_1, ...$

Il suffit de générer des formules entièrement entre parenthèses sans omission de parenthèses. Vous pouvez utiliser$“...”$ pour indiquer une omission comme dans la grammaire BNF ci-dessus.

Mes progrès: J'ai réussi à comprendre le sujet de la forme normale de Backus et ses applications, mais j'avais eu du mal à associer la grammaire de la forme normale de Backus aux règles de proposition légales. Évidemment, ces règles sont bien connues et compréhensibles, mais je ne savais pas comment indiquer des formules entièrement entre parenthèses?

Answer 1

Écrivons d'abord la grammaire BNF de toutes les formules propositionnelles atomiques (notées$\mathcal{A}$):

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

où $A$, $B$, $C$, $\dots$sont définis dans le message d'origine. Notez que cette définition ne nécessite aucune forme d'induction, en dehors de celle utilisée dans la définition d'entier dans le message d'origine.

Ensuite, la grammaire BNF de toutes les formules propositionnelles (notée $\mathcal{F}, \mathcal{G}$, $\dots$) est le suivant:

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

Notez que, selon cette définition, $P \to Q$n'est pas une formule propositionnelle, car les parenthèses manquent. La formule propositionnelle correcte dans ce cas est$(P \to Q)$.

Cette utilisation massive de parenthèses est nécessaire pour éviter les expressions ambiguës telles que $P \land Q \lor R$peuvent être considérées comme des formules propositionnelles. En effet, dans$P \land Q \lor R$on ne sait pas quel est le principal connecteur. Les formules propositionnelles correctes sont$((P \land Q) \lor R)$ et $(P \land (Q \lor R))$, où aucune ambiguïté ne se pose.