Bentuk Normal dan Logika Backus

Question

Diberikan alfabet ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$, tulis tata bahasa bentuk normal Backus yang menghasilkan semua rumus proposisional hukum. Untuk permulaan sudah diberikan itu

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

integer :: = digit | digit, integer

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

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

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

Itu sudah cukup untuk menghasilkan rumus dengan tanda kurung penuh yang tidak menghilangkan tanda kurung. Anda dapat menggunakan$“...”$ untuk menunjukkan kelalaian seperti pada tata bahasa BNF di atas.

Kemajuan saya: Saya telah berhasil memahami topik bentuk normal Backus dan aplikasinya, tetapi saya kesulitan untuk mengaitkan tata bahasa bentuk normal Backus dengan aturan proposisional hukum. Jelas, aturan ini terkenal dan dapat dimengerti, tetapi saya tidak menyadari bagaimana menunjukkan rumus yang sepenuhnya dikurung?

Answer 1

Mari kita tuliskan tata bahasa BNF dari semua rumus proposisional atom (dilambangkan dengan$\mathcal{A}$):

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

dimana $A$, $B$, $C$, $\dots$ditentukan di postingan asli. Perhatikan bahwa definisi ini tidak memerlukan bentuk induksi apa pun, selain yang digunakan dalam definisi bilangan bulat di postingan asli.

Kemudian, tata bahasa BNF dari semua rumus proposisional (dilambangkan dengan $\mathcal{F}, \mathcal{G}$, $\dots$) adalah sebagai berikut:

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

Perhatikan bahwa, menurut definisi ini, $P \to Q$bukan rumus proposisional, karena tanda kurung tidak ada. Rumus proposisional yang benar dalam hal ini adalah$(P \to Q)$.

Penggunaan tanda kurung secara masif ini diperlukan untuk menghindari ekspresi ambigu seperti $P \land Q \lor R$dapat dianggap sebagai rumus proposisional. Memang, di$P \land Q \lor R$tidak jelas apa yang menjadi penghubung utama. Rumus proposisional yang benar adalah$((P \land Q) \lor R)$ dan $(P \land (Q \lor R))$, di mana tidak ada ambiguitas yang muncul.