Backus Normalform und Logik

Question

Angesichts des Alphabets von ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$Schreiben Sie eine Backus-Normalform-Grammatik, die alle gesetzlichen Satzformeln generiert. Für den Anfang ist das gegeben

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

Ganzzahl :: = Ziffer | Ziffer, Ganzzahl

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

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

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

Es reicht aus, vollständig in Klammern gesetzte Formeln zu generieren, bei denen keine Klammern weggelassen werden. Sie können verwenden$“...”$ um eine Auslassung wie in der obigen BNF-Grammatik anzuzeigen.

Mein Fortschritt: Ich habe es geschafft, das Backus-Normalform-Thema und seine Anwendungen zu verstehen, aber ich hatte Mühe, die Backus-Normalform-Grammatik mit gesetzlichen Satzregeln zu verknüpfen. Natürlich sind diese Regeln bekannt und verständlich, aber ich wusste nicht, wie man vollständig in Klammern gesetzte Formeln angibt?

Answer 1

Schreiben wir zunächst die BNF-Grammatik aller atomaren Satzformeln (bezeichnet mit$\mathcal{A}$):

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

wo $A$, $B$, $C$, $\dots$sind im ursprünglichen Beitrag definiert. Beachten Sie, dass diese Definition keine Form der Induktion erfordert, abgesehen von der Definition, die bei der Definition der Ganzzahl im ursprünglichen Beitrag verwendet wurde.

Dann die BNF-Grammatik aller Satzformeln (bezeichnet mit $\mathcal{F}, \mathcal{G}$, $\dots$) ist das Folgende:

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

Beachten Sie, dass gemäß dieser Definition $P \to Q$ist keine Satzformel, da Klammern fehlen. Die richtige Satzformel ist in diesem Fall$(P \to Q)$.

Diese massive Verwendung von Klammern ist erforderlich, um mehrdeutige Ausdrücke wie z $P \land Q \lor R$kann als Satzformeln betrachtet werden. In der Tat in$P \land Q \lor R$Es ist nicht klar, was der Hauptkonnektiv ist. Richtige Satzformeln sind$((P \land Q) \lor R)$ und $(P \land (Q \lor R))$, wo keine Mehrdeutigkeit entsteht.