Backus Dạng bình thường và Logic

Question

Đưa ra bảng chữ cái của ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$, viết một ngữ pháp dạng chuẩn Backus tạo ra tất cả các công thức mệnh đề hợp pháp. Để bắt đầu, nó được đưa ra rằng

chữ số :: = $“0” | “1” | “2” | “3” | ... | “8” | “9”$

số nguyên :: = chữ số | chữ số, số nguyên

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

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

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

Nó đủ để tạo ra các công thức có dấu ngoặc đơn đầy đủ mà không bỏ sót dấu ngoặc đơn. Bạn có thể sử dụng$“...”$ để chỉ ra sự thiếu sót như trong ngữ pháp BNF ở trên.

Tiến trình của tôi: Tôi đã cố gắng hiểu chủ đề Backus form normal và các ứng dụng của nó, nhưng tôi đã phải vật lộn để liên kết ngữ pháp của Backus form normal với các quy tắc mệnh đề pháp lý. Rõ ràng, những quy tắc này rất nổi tiếng và dễ hiểu, nhưng tôi không biết làm thế nào để chỉ ra các công thức được đặt trong ngoặc đơn đầy đủ?

Answer 1

Đầu tiên chúng ta hãy viết ngữ pháp BNF của tất cả các công thức mệnh đề nguyên tử (ký hiệu là$\mathcal{A}$):

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

Ở đâu $A$, $B$, $C$, $\dots$được định nghĩa trong bài gốc. Lưu ý rằng định nghĩa này không yêu cầu bất kỳ hình thức quy nạp nào, ngoài định nghĩa được sử dụng trong định nghĩa số nguyên trong bài viết gốc.

Sau đó, ngữ pháp BNF của tất cả các công thức mệnh đề (được biểu thị bằng $\mathcal{F}, \mathcal{G}$, $\dots$) như sau:

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

Lưu ý rằng, theo định nghĩa này, $P \to Q$không phải là công thức mệnh đề, vì thiếu dấu ngoặc đơn. Công thức mệnh đề đúng trong trường hợp này là$(P \to Q)$.

Việc sử dụng nhiều dấu ngoặc đơn này là cần thiết để tránh các biểu thức không rõ ràng như $P \land Q \lor R$có thể coi là công thức mệnh đề. Thật vậy, trong$P \land Q \lor R$nó không rõ ràng là kết nối chính. Các công thức mệnh đề đúng là$((P \land Q) \lor R)$ và $(P \land (Q \lor R))$, nơi không có sự mơ hồ phát sinh.