Backus Normal Form ve Mantık

Question

Alfabesi göz önüne alındığında ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$, tüm yasal önerme formüllerini üreten bir Backus normal form dilbilgisi yazın. Başlangıç ​​için verilir ki

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

tamsayı :: = basamak | rakam, tamsayı

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

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

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

Hiçbir parantez içermeyen tam olarak parantezli formüller oluşturmak yeterlidir. Kullanabilirsin$“...”$ yukarıdaki BNF dilbilgisinde olduğu gibi ihmali belirtmek için.

İlerlemem: Backus normal form konusunu ve uygulamalarını anlamayı başardım, ancak Backus normal form dilbilgisini yasal öneri kuralları ile ilişkilendirmekte zorlandım. Açıkçası, bu kurallar iyi biliniyor ve anlaşılır, ancak tam olarak parantez içine alınmış formülleri nasıl göstereceğimi bilmiyordum?

Answer 1

Öncelikle tüm atomik önermesel formüllerin BNF gramerini yazalım ($\mathcal{A}$):

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

nerede $A$, $B$, $C$, $\dots$orijinal gönderide tanımlanmıştır. Bu tanımın, orijinal gönderideki tamsayı tanımında kullanılan dışında herhangi bir tümevarım biçimi gerektirmediğine dikkat edin.

Ardından, tüm önerme formüllerinin BNF dilbilgisi ( $\mathcal{F}, \mathcal{G}$, $\dots$) takip ediliyor:

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

Bu tanıma göre, $P \to Q$bir önerme formülü değildir, çünkü parantezler eksiktir. Bu durumda doğru önerme formülü şöyledir:$(P \to Q)$.

Parantezlerin bu kadar yoğun şekilde kullanılması, aşağıdaki gibi belirsiz ifadelerden kaçınmak için gereklidir: $P \land Q \lor R$önerme formülleri olarak düşünülebilir. Gerçekten$P \land Q \lor R$ana bağlayıcının ne olduğu açık değildir. Doğru önerme formülleri$((P \land Q) \lor R)$ ve $(P \land (Q \lor R))$, belirsizliğin olmadığı yerde.