離散數(shù)學(xué)26謂詞演算的推理理論.ppt

離散數(shù)學(xué)DiscreteMathematics,第6講2—7謂詞演算的推理理論,要求：熟練掌握謂詞的推理理論與推理方法，會用謂詞的推理理論與推理方法進(jìn)行推理。重點：應(yīng)用謂詞的推理理論與推理方法進(jìn)行推理。難點：正確理解和運(yùn)用有關(guān)量詞規(guī)則。,,謂詞邏輯是命題邏輯的進(jìn)一步深化和發(fā)展，謂詞演算的推理方法，可以看作是命題演算推理方法的擴(kuò)張。因此命題邏輯的推理理論在謂詞邏輯中幾乎可以完全照搬，只不過這時涉及的公式是謂詞邏輯的公式罷了。在謂詞邏輯中，某些前提和結(jié)論可能受到量詞的約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)系，有必要消去量詞和添加量詞，因此正確理解和運(yùn)用有關(guān)量詞規(guī)則是謂詞邏輯推理理論中十分重要的關(guān)鍵所在。,,,,下面在介紹有關(guān)量詞規(guī)則之前做些必要準(zhǔn)備。下面給出A(x)對y是自由的這個概念。其目的是，允許用y代入x后得到A(y)，它不改變原來公式A(x)的約束關(guān)系。定義2.7.1在謂詞公式A(x)中，若x自由出現(xiàn)在量詞(?y)或(?y)的轄域，則稱A(x)對于y是自由的。由定義可知，若y在A(x)中不是約束出現(xiàn)，則A(x)對于y一定是自由的。,一、有關(guān)量詞消去和添加規(guī)則量詞消去規(guī)則：(1)全稱量詞消去規(guī)則(稱為全稱指定規(guī)則，簡稱UI或US規(guī)則)有兩種形式：(?x)A(x)?A(c)其中c為任意個體常元(?x)A(x)?A(y)A(x)對y是自由的,(2)存在量詞消去規(guī)則(稱為存在指定規(guī)則，簡稱EI或ES規(guī)則)有兩種形式：(?x)A(x)?A(c)其中c為特定個體常元(?x)A(x)?A(y)成立充分條件是：①c或y不得在前提中或者居先推導(dǎo)公式中出現(xiàn)或自由出現(xiàn)；②若A(x)中有其它自由變元時，不能應(yīng)用本規(guī)則。值得注意的是，A(y)只是新引入的暫時假設(shè)，它不是對y的一切值都是成立的。y是一個暫時的、表面上的自由變元。,量詞產(chǎn)生規(guī)則：(3)存在量詞產(chǎn)生規(guī)則(稱為存在推廣規(guī)則，簡稱EG規(guī)則)有兩種形式：A(c)?(?y)A(y)其中c為特定個體常元A(x)?(?y)A(y)成立充分條件：①取代c的個體變元y不在A(c)中出現(xiàn)；②A(x)對y是自由的；③若A(x)是推導(dǎo)行中的公式，且x是由使用EI引入的，那么不能用A(x)中除x外的個體變元作約束變元，或者說，y不得為A(x)中的個體變元。,(4)全稱量詞產(chǎn)生規(guī)則(稱為全稱推廣規(guī)則，簡稱UG規(guī)則)A(x)?(?y)A(y)成立條件：①前提A(x)對于x的任意取值都成立；②A(x)對y是自由的；③對于由于使用EI規(guī)則所得到的公式中原約束變元及與其在同一個原子公式的自由變元，都不能使用本規(guī)則而成為指導(dǎo)變元，否則將產(chǎn)生錯誤推理。,二、Lp中推理實例Lp的推理方法是Ls推理方法的擴(kuò)展，因此在Lp中利用的推理規(guī)則也是T規(guī)則、P規(guī)則和CP規(guī)則，還有已知的等價式，蘊(yùn)含式以及有關(guān)量詞的消去和產(chǎn)生規(guī)則。使用的推理方法是直接構(gòu)造法和間接證法。,例題1證明蘇格拉底論證：所有的人都是要死的。蘇格拉底是人。所以蘇格拉底是要死的。,解設(shè)H(x)：x是一個人。M(x)：x是要死的。s：蘇格拉底。故蘇格拉底論證可符號化為：(?x)(H(x)→M(x))∧H(s)?M(s),證明,(1)(?x)(H(x)→M(x))P,(2)H(s)→M(s)US(1),(3)H(s)P,(4)M(s)T(2)(3)I,例題2證明,證明,,注意（3）（4）兩條次序不能顛倒。,練習(xí)79頁（1）題,(?x)(C(x)→W(x)∧R(x))∧(?x)(C(x)∧Q(x))?(?x)(Q(x)∧R(x)),(1)(?x)(C(x)→W(x)∧R(x))P,(2)(?x)(C(x)∧Q(x))P,(4)C(a)→W(a)∧R(a)US(1),(3)C(a)∧Q(a)ES(2),(5)C(a)T(3)I,(6)W(a)∧R(a)T(4)(5)I,(7)Q(a)T(3)I,(8)R(a)T(6)I,(9)Q(a)∧R(a)T(7)(8)I,(10)(?x)(Q(x)∧R(x))EG,例題3證明,(?x)(P(x)∨Q(x))?(?x)P(x)∨(?x)Q(x),,用間接證法。要證S?C，即要證S?C?T，而S?C?┐S∨C，所以S?C?T即┐S∨C?T，亦就是┐(┐S∨C)?F，S∧┐C?F。假定┐C為T，推出矛盾。,(1)┐((?x)P(x)∨(?x)Q(x))P(附加前提),(2)(?x)┐P(x)∧(?x)┐Q(x)T(1)E,(3)(?x)┐P(x)T(2)I,(4)(?x)┐Q(x)T(2)I,(5)┐P(c)ES(3),(6)┐Q(c)US(4),(7)┐P(c)∧┐Q(c)T(5)(6)I,(8)┐(P(c)∨Q(c))T(7)E,(9)(?x)(P(x)∨Q(x))P,(10)P(c)∨Q(c)US(9),(11)┐(P(c)∨Q(c))∧(P(c)∨Q(c))(矛盾)T(8)(10)I,證法2本題可用CP規(guī)則,原題為,(?x)(P(x)∨Q(x))?┐(?x)P(x)?(?x)Q(x),復(fù)習(xí)CP規(guī)則要證S?R?C，即要證S?(R?C)?T,即┐S∨(┐R∨C)?T,(┐S∨┐R)∨C?T,┐(S∧R)∨C?T,(S∧R)?C?T也就是證明(S∧R)?C。,(1)┐(?x)P(x)P（附加前提）,(2)(?x)┐P(x)T（1）E,(3)┐P(c)ES(2),(4)(?x)(P(x)∨Q(x))P,(5)P(c)∨Q(c)US(3),(6)Q(c)T(3)(5)I,(7)(?x)Q(x)EG(6),(8)┐(?x)P(x)?(?x)Q(x)CP,例題4構(gòu)造下面推理的證明：每個學(xué)術(shù)會的成員都是專家并且是工人，有些成員是青年人，所以有些成員是青年專家。,證明,設(shè)P(x)：x是學(xué)術(shù)會的成員。Q(x)：x是專家。R(x)：x是工人。S(x)：x是青年人。,證明過程如下：,則本題要證明：(?x)(P(x)→Q(x)∧R(x))，(?x)(P(x)∧S(x))?(?x)(P(x)∧Q(x)∧S(x)),(1)(?x)(P(x)∧S(x))P,(2)P(a)∧S(a)ES(1),(3)P(a)T(2)I,(4)S(a)T(2)I,(5)(?x)(P(x)→Q(x)∧R(x))P,(6)P(a)→Q(a)∧R(a)US(5),(7)Q(a)∧R(a)T(3)(6)I,(8)Q(a)T(7)I,(9)P(a)∧Q(a)∧S(a)T(3)(4)(8)I,(10)(?x)(P(x)∧Q(x)∧S(x))EG(9),數(shù)理邏輯在計算機(jī)科學(xué)中的用途有兩個：一個是作為知識表示的手段，因為日常生活中的或數(shù)學(xué)領(lǐng)域中的命題，大多能用謂詞邏輯的符號表達(dá)式，便于計算機(jī)處理；另一個用途是研究形式推理，為計算機(jī)進(jìn)行自動推理提供方法和理論。第二個用途過于專門和復(fù)雜，已超過本課程教學(xué)大綱的要求。但是，第一個用途確是非常重要，所以應(yīng)該掌握。,,作業(yè)79頁（3）,練習(xí)79頁（2）,