Forma normalna i logika Backusa

Question

Biorąc pod uwagę alfabet ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$, napisz gramatykę postaci normalnej Backusa, która generuje wszystkie formuły zdań prawniczych. Na początek jest to podane

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

liczba całkowita :: = cyfra | cyfra, liczba całkowita

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

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

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

Wystarczy wygenerować formuły w pełni ujęte w nawiasy, bez pominięcia nawiasów. Możesz użyć$“...”$ wskazać pominięcie, jak w powyższej gramatyce BNF.

Mój postęp: udało mi się zrozumieć temat formy normalnej Backusa i jego zastosowania, ale starałem się skojarzyć gramatykę formy normalnej Backusa z regułami zdań prawniczych. Oczywiście te zasady są dobrze znane i zrozumiałe, ale nie zdawałem sobie sprawy, jak wskazać formuły w nawiasach?

Answer 1

Najpierw napiszmy gramatykę BNF wszystkich atomowych formuł zdań (oznaczonych$\mathcal{A}$):

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

gdzie $A$, $B$, $C$, $\dots$są zdefiniowane w oryginalnym poście. Zauważ, że ta definicja nie wymaga żadnej formy indukcji, poza tą używaną w definicji liczby całkowitej w oryginalnym poście.

Następnie gramatyka BNF wszystkich formuł zdań (oznaczona $\mathcal{F}, \mathcal{G}$, $\dots$) wygląda następująco:

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

Zauważ, że zgodnie z tą definicją $P \to Q$nie jest formułą zdaniową, ponieważ brakuje nawiasów. Prawidłowa formuła zdaniowa w tym przypadku to$(P \to Q)$.

To masowe użycie nawiasów jest wymagane, aby uniknąć niejednoznacznych wyrażeń, takich jak $P \land Q \lor R$można uznać za formuły zdaniowe. Rzeczywiście, w$P \land Q \lor R$nie jest jasne, co jest głównym łącznikiem. Prawidłowe formuły zdań to$((P \land Q) \lor R)$ i $(P \land (Q \lor R))$, gdzie nie ma dwuznaczności.