Forma normale e logica di Backus

Question

Dato l'alfabeto di ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$, scrivi una grammatica in forma normale di Backus che generi tutte le formule proposizionali legali. Per l'inizio è dato quello

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

intero :: = cifra | cifra, numero intero

$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, ...$

È sufficiente generare formule completamente tra parentesi che non hanno omissione di parentesi. Puoi usare$“...”$ per indicare l'omissione come nella grammatica BNF di cui sopra.

I miei progressi: sono riuscito a comprendere l'argomento della forma normale di Backus e le sue applicazioni, ma ho avuto difficoltà ad associare la grammatica della forma normale di Backus con le regole proposizionali legali. Ovviamente queste regole sono ben note e comprensibili, ma non mi ero reso conto come indicare formule completamente tra parentesi?

Answer 1

Scriviamo prima la grammatica BNF di tutte le formule proposizionali atomiche (denotate da$\mathcal{A}$):

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

dove $A$, $B$, $C$, $\dots$sono definiti nel post originale. Si noti che questa definizione non richiede alcuna forma di induzione, a parte quella utilizzata nella definizione di intero nel post originale.

Quindi, la grammatica BNF di tutte le formule proposizionali (denotate da $\mathcal{F}, \mathcal{G}$, $\dots$) è il seguente:

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

Si noti che, secondo questa definizione, $P \to Q$non è una formula proposizionale, perché mancano le parentesi. La formula proposizionale corretta in questo caso è$(P \to Q)$.

Questo uso massiccio delle parentesi è necessario per evitare espressioni ambigue come $P \land Q \lor R$possono essere considerate come formule proposizionali. In effetti, in$P \land Q \lor R$non è chiaro quale sia il principale connettivo. Le formule proposizionali corrette sono$((P \land Q) \lor R)$ e $(P \land (Q \lor R))$, dove non sorge ambiguità.