Backus Normal Form และ Logic

Question

ระบุตัวอักษรของ ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$เขียนไวยากรณ์รูปแบบปกติของ Backus ที่สร้างสูตรทางกฎหมายทั้งหมด สำหรับการเริ่มต้นนั้นจะได้รับว่า

หลัก :: = $“0” | “1” | “2” | “3” | ... | “8” | “9”$

จำนวนเต็ม :: = หลัก | หลักจำนวนเต็ม

$A ::= P \mid P, \text{integer} \quad $ // สร้าง $P, P_1, ...$

$B ::= Q \mid Q, \text{integer} \quad $ // สร้าง $Q, Q_1, ...$

$C ::= R \mid R, \text{integer} \quad$ // สร้าง $R, R_1, ...$

มันเพียงพอที่จะสร้างสูตรในวงเล็บเต็มรูปแบบที่ไม่มีการละเว้นของวงเล็บ คุณอาจใช้$“...”$ เพื่อบ่งชี้การละเว้นตามไวยากรณ์ BNF ข้างต้น

ความคืบหน้าของฉัน: ฉันเข้าใจหัวข้อแบบฟอร์มปกติของ Backus และแอปพลิเคชันได้แล้ว แต่ฉันพยายามเชื่อมโยงไวยากรณ์รูปแบบปกติของ Backus กับกฎเชิงประพจน์ทางกฎหมาย เห็นได้ชัดว่ากฎเหล่านี้เป็นที่รู้จักและเข้าใจได้ดี แต่ฉันไม่รู้ว่าจะระบุสูตรในวงเล็บทั้งหมดอย่างไร?

Answer 1

ก่อนอื่นให้เราเขียนไวยากรณ์ BNF ของสูตรเชิงอะตอมทั้งหมด(แสดงโดย$\mathcal{A}$):

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

ที่ไหน $A$, $B$, $C$, $\dots$ถูกกำหนดไว้ในโพสต์ต้นฉบับ โปรดทราบว่าคำจำกัดความนี้ไม่ต้องการการเหนี่ยวนำรูปแบบใด ๆ นอกเหนือจากคำจำกัดความที่ใช้ในนิยามของจำนวนเต็มในโพสต์ต้นฉบับ

จากนั้นไวยากรณ์ BNF ของสูตรเชิงประพจน์ทั้งหมด (แสดงโดย $\mathcal{F}, \mathcal{G}$, $\dots$) ดังต่อไปนี้:

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

โปรดทราบว่าตามคำจำกัดความนี้ $P \to Q$ไม่ใช่สูตรเชิงประพจน์เนื่องจากไม่มีวงเล็บ สูตรประพจน์ที่ถูกต้องในกรณีนี้คือ$(P \to Q)$.

จำเป็นต้องใช้วงเล็บขนาดใหญ่เพื่อหลีกเลี่ยงนิพจน์ที่ไม่ชัดเจนเช่น $P \land Q \lor R$ถือได้ว่าเป็นสูตรเชิงประพจน์ อันที่จริงใน$P \land Q \lor R$ยังไม่ชัดเจนว่าอะไรคือความเชื่อมโยงหลัก สูตรประพจน์ที่ถูกต้องคือ$((P \land Q) \lor R)$ และ $(P \land (Q \lor R))$ซึ่งไม่มีความคลุมเครือเกิดขึ้น