第2章一階邏輯(參考版)
2025-07-23 09:17本頁面
【正文】 68 一階邏輯推理理論 1. 關(guān)于量詞分配的推理定律 2. 全稱量詞消去規(guī)則 3. 全稱量詞引入規(guī)則 4. 存在量詞引入規(guī)則 5. 存在量詞消去規(guī)則 。,2。,5,6。 60 定 理 定理 任何一個(gè)一階公式都等價(jià)于一個(gè)前束標(biāo)準(zhǔn)型公式。其中每個(gè) Qi (1≤i≤k)為 ?或 ?,B為 不含量詞 的謂詞公式。命題邏輯的等價(jià)形式也是一階邏輯的等價(jià)形式 ?x P(x) ??x P(x) ∧ ?x P(x) 55 定理 — 量詞否定等值式 ? ~?x P(x)??x~ P(x) ? ~?x P(x)??x~ P(x) 公式的驗(yàn)證 ： D={a1, a2, …,an} ? ~?x P(x) ? ~(P(a1)∧ P(a2)∧ … ∧ P(an)) ? ~P(a1) ∨ ~P(a2) ∨ … ∨ ~P(an)) ??x~ P(x) 56 量詞轄域收縮與擴(kuò)張等值式 A(x)是含 x自由出現(xiàn)的任意公式 ,而 B中不含 x的出現(xiàn) ? ?x (A(x)∨ B)??x A(x)∨ B ? ?x (A(x)∧ B)??x A(x)∧ B ? ?x (B→ A(x))? B→ ?x A(x) ? ?x (A(x)∨ B)??x A(x)∨ B ? ?x (A(x)∧ B)??x A(x)∧ B ? ?x (B→ A(x))? B→ ?x A(x) ? ?x (A(x)→ B)??x A(x)→ B ? ?x (A(x)→ B)??x A(x)→ 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)形式。 53 一階邏輯等值式 1. 等值式 2. 定理 量詞否定等值式 量詞轄域收縮與擴(kuò)張等值式 量詞分配等值式 兩個(gè)成立的等值式 3. 謂詞公式的規(guī)范形式 —— 前束范式 54 等值式 1. 設(shè) A， B是一階邏輯中任意的兩公式，若 A? B為邏輯有效式 ，則稱 A與 B是等值的 ，記作 A?B,稱 A?B為等值式。 蘊(yùn)涵式為假 ； Q(x,y)： x≤y。 2. 命題公式中的重言式的代換實(shí)例在謂詞公式中可仍稱為重言式，這樣的重言式都是邏輯有效式。 50 代換實(shí)例 A0是 命題公式 ， x1, x2, …, xn是 命題變項(xiàng) ，用 n個(gè) 謂詞公式 A1 ,A2,…,An分別代換 x1, x2, …, xn ，所得公式 A稱為 A0的 代換實(shí)例 。 L(x,y)為 L(2,2)= L(3,3)=1。 3. 函數(shù) f(x)為 f(2)=3， f(3)=2； 4. 謂詞 F(x)為 F(2)=0， F(3)=1。 1） ?y(P(y) → Q (y,y)) ∧ R (x,y) 2） ?z(P(z) → Q (x,y)) ∧ R (x,y) 3） ?z(P(z) → Q (z,y)) ∧ R (x,y) 3）正確 46 解釋 一個(gè)解釋 I由下面 4部分組成 D； 2. D中一部分特定元素； 3. D上一些特定的函數(shù)； 4. D上一些特定的謂詞。 ?v1 (v1 + v2+1=0 → ?v2 (v1+ v2 +10)) 在上面這個(gè)公式中， v1 和 v2有時(shí)自由出現(xiàn)，有時(shí)是約束出現(xiàn)的，為了避免混淆我們引入 換名規(guī)則 42 換名規(guī)則 將量詞轄域中出現(xiàn)的某個(gè) 約束出現(xiàn) 的個(gè)體變項(xiàng)及對應(yīng)的指導(dǎo)變項(xiàng)，改成 另一個(gè)轄域中 未曾出現(xiàn)過 的個(gè)體變項(xiàng)符號，公式中其余部分不變，稱為 換名規(guī)則 。?v1的轄域是全公式， v1是約束變元，第二個(gè) v2是約束變元，第一個(gè) v2是自由變元 . 41 閉式 公式常記作 φ(x1, x2, …, xn), φ中自由變元都在 x1, x2, …, xn中。v1是約束變元 2. ?v2 (v1+ v2 +10) 量詞的轄域是全公式。 4. 只有有限次地應(yīng)用 14構(gòu)成的符號串才是合式公式（謂詞公式） 38 實(shí)例 1. ?x (x +1=0) 2. ?y (x+ y +10) 3. ?x
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1