離散數(shù)學(xué)第五版第二章(耿素云、屈婉玲、張立昂編著)(編輯修改稿)
2024-09-03 10:55 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 1) ?x(F(x,y)?G(x,z)) 5) ?x(F(x)?G(y))??y(H(x)?L(x,y,z)) 23 2. 封閉的公式（定義 ） 設(shè) A是任意的公式，若 A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則 稱 A為 封閉的公式 ，簡(jiǎn)稱 閉式 。 例如： ?x(F(x)?G(x)),?x?y(F(x)?G(x,y)) 閉式 ?x(F(x)?G(x,y)),?x?yL(x,y,z) 不是閉式 換名規(guī)則 將量詞轄域中出現(xiàn)的某個(gè)約束出現(xiàn)的個(gè)體變項(xiàng)及對(duì)應(yīng)的指導(dǎo)變項(xiàng)，該成另一個(gè)轄域中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)，公式中其余部分不變。 代替規(guī)則 對(duì)某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)用與原公式中所有個(gè)體變項(xiàng)符號(hào)不同的變項(xiàng)符號(hào)去代替，且處處代替。 24 1. 定義 三、解釋 （ a）非空個(gè)體域 DI 封閉公式在任何解釋下都變成命題 ? 的解釋 I由下面 4部分組成： （ b） DI中一些特定元素的集合 （ c） DI上特定函數(shù)集合 （ d） DI上特定謂詞集合 25 2) F(f(x,a),y)?F(g(x,y),z) 3) ?F(g(x,y),g(y,z)) 1) F(f(x,y),g(x,y)) 5) ?xF(g(x,a),x)?F(x,y) 6) ?xF(g(x,a),x) 8) ?x?y?zF(f(x,y),z) 7) ?x?y(F(f(x,a),y)?F(f(y,a),x) 9) ?xF(f(x,x),g(x,x)) 4) ?xF(g(x,y),z) 26 2. 說(shuō)明 （ 2）在解釋的公式 A中的個(gè)體變項(xiàng)均取值于 DI （ 6）被解釋的公式不一定全部包含解釋中的四個(gè)部分 （ 1）在解釋的定義中引進(jìn)了幾個(gè)元語(yǔ)言符號(hào)， 如： （ 3）若 A中含個(gè)體常項(xiàng)，就解釋成 （ 4） 為第 i個(gè) n元函數(shù) （ 5） 為第 i個(gè) n元謂詞 27 1. 定義 三、公式的類型 設(shè) A為一公式，若 A在任何解釋下均為真，則稱 A為 永真式 （或稱邏輯有效式）。若 A在任何解釋下均為假，則稱 A為 矛盾式 （或永假式）。若至少存在一個(gè)解釋使 A為真，則 稱 A是 可滿足式 。 2. 如何判斷公式的類型？ 在一階邏輯中，由于公式的復(fù)雜性和解釋的多樣性，到 目前為止， 沒(méi)有找到 一種可行的方法來(lái)判斷公式的類型。 28 3. 代換實(shí)例（定義 ） 設(shè) A0是含命題變項(xiàng) p1,p2,……pn的 命題公式 ， A1,A2,……An 是 n個(gè) 謂詞公式 ，用 Ai（ 1=I=n）處處代替 A0中的 pi， 所得公式 A稱為 A0的 代換實(shí)例 。 例如： F(x)?G(x),?xF(x)??yG(y)都是 p?q的代換實(shí)例，而 ?x(F(x)?G(x))不是 p?q的代換實(shí)例。 重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是 矛盾式。 29 例 3：判斷下列公式哪些是永真式，哪些是矛盾式： 2) ?x(F(x)?G(x)) 3) ?xF(x)?(?x?yG(x,y)??xF(x)) 1) ?x(F(x)?G(x)) 5) ?xF(x)?(?xF(x)??yG(y)) 4) ?(?xF(x)??yG(y))??yG(y) 可以根據(jù)命題公式重言式的代換實(shí)例來(lái)判斷公式的類型！ 30 例 4：判斷下列公式的類型： 1) ?xF(x)??xF(x) 2) ?x?yF(x,y)??x?yF(x,y) 3) ?x(F(x)?G(x))??yG(y) 通過(guò)構(gòu)造一些特殊的解釋，來(lái)判斷公式的類型！ 31 第二章 一階邏輯基本概念 一階邏輯的基本概念 一階邏輯合式公式及解釋 一階邏輯等值式 一階邏輯推理理論 32 一階邏輯等值式 將下面命題符號(hào)化： 沒(méi)有不犯錯(cuò)誤的人。 (1)??x(F(x)??G(x)) (2)?x(F(x)?G(x)) 在一階邏輯中，有些命題可以有不同的符號(hào)化形式！ 33 一階邏輯等值式 1. 等值式（定義 ） 一、一階邏輯等值式 設(shè) A， B是一階邏輯中任意兩個(gè)公式，若 A?B是永真式， 則稱 A與 B是等值的。記作 A?B，成 A?B是 等值式。 2. 一階邏輯中的幾個(gè)基本的等值式 (1)命題邏輯中 16組等值式 例如： ?xF(x)????xF(x) F(x)?G(x)??F(x)?G(x) 34 一階邏輯等值式 (2)一階邏輯中的 4組特殊的等值式 1) 消去量詞等值式 設(shè)個(gè)體域?yàn)橛邢藜?D＝｛ a1， a2， ……， an｝，則有 ?xA(x)?A(
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1