第2章一階邏輯-資料下載頁
2025-07-20 09:17本頁面
【正文】 B 57 定 理 量詞分配等值式 ? ?x (A(x)∧ B(x))??x A(x)∧ ?x B(x) ??x (A(x)∨ B(x))? ?x A(x)∨ ?x B(x) 兩個(gè)蘊(yùn)涵式 ?x A(x)∨ ?xB(x) ?x (A(x)∨ B(x)) ?x (A(x)∧ B(x)) ?x A(x)∧ ?xB(x) ??58 兩個(gè)成立的等值式 ??x?yQ(x,y) ??y?xQ(x,y) ??x?yQ(x,y) ??y?xQ(x,y) 利用基本公式可以做公式的 等價(jià)變換 ，可以將 公式化簡 ，可以將公式 化成某種標(biāo)準(zhǔn)形式。 ~?x(φ→ ψ) ??x ~(φ→ ψ) ??x (φ∧ ~ψ) ?x ~(φ→ ψ) ??x(φ∧ ~ψ) ??xφ∧ ?x ~ψ??xφ∧ ~?x ψ 59 前束范式 設(shè) A為一謂詞公式，如果 A具有如下形式： Q1x1Q2x2…QkxkB, 則稱 A是前束范式。其中每個(gè) Qi (1≤i≤k)為 ?或 ?,B為 不含量詞 的謂詞公式。 前束標(biāo)準(zhǔn)型：所有量詞都在公式最前面，轄域?yàn)檎麄€(gè)公式。 60 定 理 定理 任何一個(gè)一階公式都等價(jià)于一個(gè)前束標(biāo)準(zhǔn)型公式。 61 例：求下列公式的前束范式 (1) ?x F(x)∧ ~?x G(x) ? ?x F(x)∧ ?x~ G(x) *量詞否定等值式 ?~?x P(x)??x~ P(x)* ? ?x (F(x)∧ ~ G(x)) *量詞分配等值式 ? ?x (A(x)∧ B(x))??x A(x)∧ ?x B(x)* 62 例：求下列公式的前束范式 (2) ?x F(x)∨ ~?x G(x) ? ?x F(x) ∨ ?x~ G(x) *量詞否定等值式 ?~?x P(x)??x~ P(x)* ? ?x F(x) ∨ ?y~ G(y) (換名規(guī)則 ) ? ?x?y (F(x)∨ ~ G(y)) *量詞轄域收縮與擴(kuò)張等值式 ? ?x (A(x)∨ B)??x A(x)∨ B * 63 例：求下列公式的前束范式 (3) ?x F(x) → ?x G(x) ? ~?x F(x)∨ ?x G(x) *蘊(yùn)涵等值式 * ? ?x~F(x)∨ ?x G(x) *量詞否定等值式 ? ~?x P(x)??x~ P(x)* ? ?x(~F(x)∨ G(x)) *量詞分配等值式??x (A(x)∨ B(x))? ?x A(x)∨ ?x B(x)* 還有沒有其他的解法？ 64 (4) ?xF(x) → ?xG(x) ? ~?x F(x) ∨ ?x G(x) *蘊(yùn)涵等值式 * ? ?x~F(x) ∨ ?x G(x) *量詞否定等值式 ? ~?x P(x)??x~ P(x)* ? ?x~F(x) ∨ ?yG(y) *換名規(guī)則 * ? ?x(~F(x) ∨ ?yG(y)) *量詞轄域收縮與擴(kuò)張等值式 ? ?x (A(x)∨ B)??x A(x)∨ B* ? ?x?y (~F(x) ∨ G(y)) *同上 * 65 (5) (?x F(x,y) → ?yG(y)) → ?x H(x,y) ? (?uF(u,y) → ?zG(z)) → ?x H(x,y) *換名規(guī)則 * ? ?u(F(u,y) → ?zG(z)) → ?x H(x,y) *??x (A(x)→ B)??x A(x)→ B* ? ?u?z (F(u,y) → G(z)) → ?x H(x,y) *? ?x (B→ A(x))? B→ ?x A(x)* ? ?u?z ((F(u,y) → G(z)) → ?x H(x,y)) *? ?x (A(x)→ B)??x A(x)→ B* ? ?u?z?x ((F(u,y) → G(z))→ H(x,y)) *??x (B→ A(x))? B→ ?x A(x)* 66 實(shí) 例 例 ?x P(x,y) → ?yQ(x,y)→ ?zR(x,z) ? ?u P(u,y) → ?vQ(x,v)→ ?zR(x,z) ? ?u P(u,y) → ?z(?vQ(x,v)→R(x,z)) ? ?u P(u,y) → ?z?v (Q(x,v)→R(x,z)) ? ?z?v(?u P(u,y) →(Q(x,v)→R(x,z))) ? ?z?v?u (P(u,y) →(Q(x,v)→R(x,z))) 67 1. ,4。,5,6。,4 2. ,4。,2。1。 68 一階邏輯推理理論 1. 關(guān)于量詞分配的推理定律 2. 全稱量詞消去規(guī)則 3. 全稱量詞引入規(guī)則 4. 存在量詞引入規(guī)則 5. 存在量詞消去規(guī)則
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1