離散數(shù)學(xué)復(fù)習(xí)資料2195

-------------精選文檔-----------------第1章命題邏輯本章重點(diǎn)：命題與聯(lián)結(jié)詞，公式與解釋，真值表，公式的類型及判定,(主)析取(合取)范式，命題邏輯的推理理論.一、重點(diǎn)內(nèi)容1.命題命題表述為具有確定真假意義的陳述句。命題必須具備二個(gè)條件：其一，語句是陳述句；其二，語句有唯一確定的真假意義.2.六個(gè)聯(lián)結(jié)詞及真值表h“?”否定聯(lián)結(jié)詞，P是命題，?P是P的否命題，是由聯(lián)結(jié)詞?和命題P組成的復(fù)合命題.P取真值1，?P取真值0，P取真值0，?P取真值1.它是一元聯(lián)結(jié)詞.h“ù”合取聯(lián)結(jié)詞，PùQ是命題P，Q的合取式，是“ù”和P，Q組成的復(fù)合命題.“ù”在語句中相當(dāng)于“不但…而且…”，“既…又…”.PùQ取值1，當(dāng)且僅當(dāng)P，Q均取1；PùQ取值為0，只有P，Q之一取0.h“ú”析取聯(lián)結(jié)詞，“`ú”不可兼析取(異或)聯(lián)結(jié)詞，PúQ是命題P，Q的析取式，是“ú”和P，Q組成的復(fù)合命題.P`úQ是聯(lián)結(jié)詞“`ú”和P，Q組成的復(fù)合命題.聯(lián)結(jié)詞“ú”或“`ú”在一個(gè)語句中都表示“或”的含義，前者表示相容或，后者表示排斥或不相容的或.即“P`úQ”?“(?PùQ)ú(Pù?Q)”.PúQ取值1，只要P，Q之一取值1，PúQ取值0，只有P，Q都取值0.h“?”蘊(yùn)含聯(lián)結(jié)詞，P?Q是“?”和P，Q組成的復(fù)合命題，只有P取值為1，Q取值為0時(shí)，P?Q取值為0；其余各種情況，均有P?Q的真值為1，亦即1?0的真值為0，0?1，1?1，0?0的真值均為1.在語句中，“如果P則Q”或“只有Q，才P，”表示為“P?Q”.可編輯

-------------精選文檔-----------------h“?”等價(jià)聯(lián)結(jié)詞，P?Q是P，Q的等價(jià)式，是“?”和P，Q組成的復(fù)合命題.“?”在語句中相當(dāng)于“…當(dāng)且僅當(dāng)…”，P?Q取值1當(dāng)且僅當(dāng)P，Q真值相同.3.命題公式、賦值與解釋，命題公式的分類與判別h命題公式與賦值，命題P含有n個(gè)命題變項(xiàng)P1，P2,…,Pn，給P1，P2,…,Pn各指定一個(gè)真值，稱為對P的一個(gè)賦值(真值指派).若指定的一組值使P的真值為1，則這組值為P的真指派；若使P的真值為0，則稱這組值稱為P的假指派.h命題公式分類，在各種賦值下均為真的命題公式A，稱為重言式(永真式)；在各種賦值下均為假的命題公式A，稱為矛盾式(永假式)；命題A不是矛盾式，稱為可滿足式；判定命題公式類型的方法：其一是真值表法，任給公式，列出該公式的真值表，若真值表的最后一列全為1，則該公式為永真式；若真值表的最后一列全為0，則該公式是永假式；若真值表的最后一列既非全1，又非全0，則該公式是可滿足式.其二是推導(dǎo)演算法.利用基本等值式(教材P.16的十六個(gè)等值式或演算律)，對給定公式進(jìn)行等值推導(dǎo)，若該公式的真值為1，則該公式是永真式；若該公式的真值為0，則該公式為永假式.既非永真，也非用假，成為非永真的可滿足式.其三主析取(合取)范式法，該公式的主析取范式有2n個(gè)極小項(xiàng)(即無極大項(xiàng))，則該公式是永真式；該公式的主合取范式有2n個(gè)極大項(xiàng)(即無極小項(xiàng))，則該公式是永假式；該公式的主析取(或合取)范式的極小項(xiàng)(或極大項(xiàng))個(gè)數(shù)大于0小于2n,，則該公式是可滿足式.h等值式A?B，命題公式A，B在任何賦值下，它們的真值均相同，稱A，B等值。定理1設(shè)F(A)是含命題公式A的命題，F(xiàn)(B)是用命題公式B到的命題公式.如果A?B，則F(A)?F(B).4.范式F(A)中的A后之得h析取(合取)范式，僅有有限個(gè)簡單合取式(析取式)構(gòu)成的析取式(合取式)，就是析取(合可編輯

-------------精選文檔-----------------取)范式.h極小項(xiàng)(極大項(xiàng))，n個(gè)命題變項(xiàng)P1,P2,…,Pn，每個(gè)變項(xiàng)或它的否定兩者只有其一出現(xiàn)且僅出現(xiàn)一次，第i個(gè)命題變項(xiàng)或者其否定出現(xiàn)在從左起第i個(gè)位置上(無腳標(biāo)時(shí)，按字典序排列)，這樣的簡單合取式(析取式)為極小項(xiàng)(極大項(xiàng)).以兩個(gè)命題變項(xiàng)為例，m00=?Pù?Q，m01=?PùQ,m10=Pù?Q,m11=PùQ是極小項(xiàng);M00=PùQ，M01=Pù?Q,M10=?PùQ,M11=?Pù?Q是極大項(xiàng).h主析取范式(主合取范式)含有n個(gè)命題變項(xiàng)的命題公式，如果與一個(gè)僅有極小項(xiàng)(極大項(xiàng))的析取(合取)構(gòu)成的析取(合取)范式等值，則該等值式稱為原命題公式的主析取(合取)范式。每項(xiàng)含有n個(gè)命題變項(xiàng)(變項(xiàng)字母齊全)的合取式(析取式)的析取(合取)為主析取(合取)范式.任意命題公式都存在與之等值的范式，存在與之等值的主范式，且是惟一的.求范式，包括求析取范式、合取范式、主析取范式和主合取范式.關(guān)鍵有兩點(diǎn)：其一是準(zhǔn)確掌握范式定義；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，結(jié)果的前一步適當(dāng)使用冪等律.求析取(合取)范式的步驟：①將公式中的聯(lián)結(jié)詞都化成?，ù，ú(個(gè)去數(shù)中的聯(lián)結(jié)詞?，?，`ú②將否定聯(lián)結(jié)詞?消或去移到各命題變項(xiàng)之前；③利用分配律、結(jié)合律等，將公式化為析取(合取)范式.求命題公式A的主析取(合取)范式的步驟)；①求公式A的析取(合取)范式；②“消去”析取(合取)范式中所有永假式(永真式)的析取項(xiàng)(合取項(xiàng))，如Pù?P(Pú?P)可編輯

-------------精選文檔-----------------用0(1)替代.用冪等律將析取(合取)范式中重復(fù)出現(xiàn)的合取項(xiàng)(析取項(xiàng))或相同的變項(xiàng)合并，如PùP(PúP)用P替代，miúmi(MiùMi)用mi(Mi)替代.③若析取(合取)范式的某個(gè)合取項(xiàng)(析取項(xiàng))B不含有命題變項(xiàng)Pi或?Pi，則添加Piú?Pi(Più?Pi)，再利用分配律展開，使得每個(gè)合取項(xiàng)(析取項(xiàng))的命題變項(xiàng)齊全；④將極小(極大)項(xiàng)按由小到大的順序排列，用S(P)表示.5.命題演算的推理理論AAC是重言式，稱C是前提集nh設(shè)A1,A2,…,An,C是命題公式，如果A12AAC合{A1,A2,…,An}的有效結(jié)論或{A1,A2,…,An}邏輯地推出C。記作A12n掌握演繹或形式證明.要理解并掌握14個(gè)重言蘊(yùn)含式(即I1～I(xiàn)14)，17個(gè)等值式(E1～E17)；二是會(huì)使用三個(gè)規(guī)則(P規(guī)則、T規(guī)則和CP規(guī)則)。推理方法有：真值表法；等值演算法；主析取范式法，構(gòu)造證明法(直接證明法、附加前提證明法和間接證明法)二、實(shí)例例1.1判別下列語句是否命題？如果是命題，指出真其值.(1)中國是一個(gè)人口眾多的國家.(3)這座樓可真高?。?2)存在最大的質(zhì)數(shù).(4)請你跟我走!(5)火星上也有人.解(1)是命題，真值為1.(3),(4)不是命題因?yàn)椴皇顷愂鼍?(2)是命題，真值為0.(5)是命題.真值是唯一的，遲早會(huì)被指出.可編輯

-------------精選文檔-----------------例1.2將下列命題符號(hào)化：(1)雖然交通堵塞，但是老王還是準(zhǔn)時(shí)到達(dá)火車站；(2)張力是三好生，他是北京人或是天津人.(3)除非天下雨，否則我騎車上班.解(1)設(shè)P：交通堵塞，Q：老王準(zhǔn)時(shí)到達(dá)火車站.該命題符號(hào)化為：PùQ.(2)設(shè)P：張力是三好生；Q：張力是北京人，R：張力是天津人.該命題符號(hào)化為Pù(Q`úR).(3)設(shè)P：天下雨，Q：我不騎車上班.該命題符號(hào)化為：Q?P，義即“只有天下雨，我才不騎車上班”，不下雨是我騎車上班的必要條件。它的等價(jià)說法是“如果天不下雨，我就騎車上班”，即?P??Q“如果天下雨，我就不騎車上班”，這是蘊(yùn)含關(guān)系，符號(hào)化為：P?Q注：本例各小題都是復(fù)合命題。如“李枚和張櫻花是好朋友”是簡單命題，用字母P表示。顯然P：李枚是好朋友，Q：張櫻花是好朋友，符號(hào)化為QùP是不通的.例1.3證明：P?(Q?R)?PùQ?R.證明方法1真值表法.列公式P?(Q?R)與PùQ?R的真值表如表1－1..表1－1公式P?(Q?R)與PùQ?R的真值表PQRQ?RP?(Q?R)PùQPùQ?RP?(Q?R)?PùQ?R000001010110111000111111可編輯-------------精選文檔-----------------0111001011101111110111101000111110111111由表可知，公式P?(Q?R)與PùQ?R的真值完全相同，故P?(Q?R)?PùQ?R..或由表的最后一列可知，P?Q??PúQ是重言式，故P?(Q?R)?PùQ?R.注：作為本例的證明可以不要最后1列。若本例改為判斷P?(Q?R)?PùQ?R的類型，由最后列可知P?(Q?R)?PùQ?R是重言式.方法2等值演算法.P?（Q?R）?P?(?QúR)(等值蘊(yùn)含式)(等值蘊(yùn)含式)(結(jié)合律)??Pú(?QúR)?（?Pú?Q）úR??(PùQ)úR(摩根律)?PùQ?R(等值蘊(yùn)含式)所以，P?（Q?R）?(PùQ)?R例中等值演算的每一步都用到了置換規(guī)則.由等值演算的傳遞性，可知第一個(gè)公式P?(Q?R)和最后一個(gè)公式PùQ)?R等值.方法3主范式法.P?(Q?R)??Pú(?QúR)??Pú?QúR(主合取范式)PùQ?R??(PùQ)úR??Pú?QúR(主合取范式)可編輯-------------精選文檔-----------------P?(Q?R)與PùQ?R的主合取范式相同，故P?(Q?R)?PùQ?R。注：(1)容易寫出P?(Q?R)與PùQ?R的主析取范式均為m0úm1úm2úm3úm4úm5úm7即(?Pù?Qù?R)ú(?Pù?QùR)ú(?PùQù?R)ú(?PùQùR)ú(Pù?Qù?R)ú(Pù?QùR)ú(PùQùR)(2)由真值表求公式P?(Q?R)的主析取范式，先列出P?(Q?R)的真值表，見表1－1。主析取范式是公式P?(Q?R)真值為1的項(xiàng)的析取，真值為1的項(xiàng)，即極小項(xiàng)，有第1,2,3,4,5,6,8共7項(xiàng).而極小項(xiàng)是合取式，合取式為1，必定是每個(gè)變元或其否定為1，如表1－1中第1行P，Q，R均取1，所以這一項(xiàng)為?Pù?Qù?R，類似地，7個(gè)極小項(xiàng)為：?Pù?Qù?R，?Pù?QùR，?PùQù?R，?PùQùR，Pù?Qù?R，Pù?QùR，PùQùR所以P?(Q?R)的主析取范式為：(?Pù?Qù?R)ú(?Pù?QùR)ú(?PùQù?R)ú(?PùQùR)ú(Pù?Qù?R)ú(Pù?QùR)ú(PùQùR)例1.4用等值演算法判定公式P`ú(QùR)?PúQúR是永真式？永假式？可滿足式？解等值運(yùn)算法.P`ú(QùR)?PúQúR??(P`ú(QùR)úPúQúR??(Pù?(QùR)ú?Pù(QùR))úPúQúR??((Pù?(QùR))ú(?PùQùR))úPúQúR?(?(Pù?(QùR))ù?(?PùQùR))úPúQúR?((?Pú(QùR))ù(Pú?Qú?R))úPúQúR?((?Pú(QùR))úPúQúR)ù((Pú?Qú?R)úPúQúR)(ú對ù的分配律)?(?PúP)úQúRú(QùR)ù1可編輯

-------------精選文檔-----------------?1ù1?1因此，P`ú(QùR)?PúQúR是永真式.注：也可以用真值表法或主范式法.例1.5化簡下式：(AùBùC)ú(?AùBùC)解(AùBùC)ú(?AùBùC)(AA)(BC)1(BC)BC（分配律）（否定律）（同一律）例1.6求公式(PR)(PQ)的主合取范式和主析取范式.解先將公式(PR)(PQ)化為合取范式.(PR)(PQ)(PR)(PQ)(QP)(去掉?)(PR)(PQ)(QP)(去掉?)(合取范式)(P(QQ)R)(P(RR)Q)(Q(RR)P)(添齊命題變項(xiàng))(PQR)(PQR)(PQR)(PQR))(PQR)(PQR)（展開）(PQR)(PQR)(PQR)(PQR)(PQR))(消去相同項(xiàng)，順序排列（所求主合取范式）)MMMMM50234(0,2,3,4,5)所求主析取范式為主合取范式的缺項(xiàng)所對應(yīng)的三個(gè)極小項(xiàng)，即為m1úm6úm7?(PQR)(PQR)(PQR)?或通過求析取范式求主析取范式.(1,6,7)(PR)(PQ)可編輯

-------------精選文檔-----------------(PR)(PQ)(QP)(去掉?)(PR)(PQ)(QP)(去掉?)(合取范式)((RP)(PQ)(QR))(QP)(PQR)(PQ)(PQR)(對分配,析取范式）(PQR)(PQ（R）)(PQRR（添齊命題變項(xiàng)）)(PQR)(PQR)(PQR）(PQR（展開）)(PQR)(PQR）(PQR)（消去相同項(xiàng)，按順序排列）（所求主析取范式）mmm(1,6,7)167注：也可以用列真值表的方法，求主析取或主合取范式，見例1.3的注.試用P，Q和聯(lián)結(jié)詞，，構(gòu)造命題公式A，使得A與F等值.例1.7已知P，Q，F(xiàn)的真值表如下表.解取真值表中F為1的成真賦值01,10的析取,即為A(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)P0011Q0101F0110A(PQ)(PQ)與F等值.即命題公式例1.8試證明：(P(QR))(SP)QSR方法1欲證明(P(QR))(SP)QSR，只需證明((P(QR))(SP)Q)(SR)是重言式，即其真值是1.((P(QR))(SP)Q)(SR)證明可編輯-------------精選文檔-----------------((PQR)(SP)Q)(SR)((PQR)(SP)Q)(SR)((PQR)Q(SP)SR((PR)Q)(PS)R(PR)PQSR1所以，推理正確。方法2構(gòu)造推理附加前提證明法(1)SCP規(guī)則(2)?SúP(3)PP(1),(2)析取三段論(4)P?(Q?R)(5)Q?RP(3),(4)假言推理(6)Q(7)RP(5),(6)假言推理例1.9填空題1.1.設(shè)命題公式G＝Pù(?QúR)，則使G的真值為1的指派是，，.答案：(1,0,0,),(1,0,1),(1,1,1)解答PQ0R?QG＝Pù(?QúR)0由真值表知：P，Q，R的真值01指派為(1,0,0,),(1,0,1),(1,1,1)則公式G的真值為1.應(yīng)填寫(1,0,0,),(1,0,1),(1,1,1)可編輯-------------精選文檔-----------------0000111101100111100100111001000011012.已知命題公式為G＝(?PúQ)?R,則命題公式G的析取范式是答案：(Pù?Q)úR解答故應(yīng)填寫(Pù?Q)úR.注：一個(gè)命題公式的析取范式一般不唯一。如(Pù?Q)ú(PùR)ú(?PùR)也是該公式的一個(gè)析取范式.(?PúQ)?R??(?PúQ)úR?(Pù?Q)úR例1.10單項(xiàng)選擇題1.設(shè)命題公式?(Pù(Q??P))，記作G，使G的真值指派為0的P，Q的真值是()(A)(0,0)(B)(0,1)(C)(1,0)(D)(1,1)答案：(C)解答Pù(Q??P)?Pù(?Qú?P)?(Pù?Q)ú(Pù?P)?Pù?Q當(dāng)P，Q取值(1，0)時(shí)，?PúQ取真值為0.故選擇(C).2.與命題公式P?（Q?R）等值的公式是()(A)(PúQ)?R(B)(PùQ)?R(C)(P?Q)?R(D)P?(QúR)可編輯-------------精選文檔-----------------答案：(B)解答P?（Q?R）?P?(?QúR)??Pú?QúR??(PùQ)úR?(PùQ)?R故應(yīng)選擇(B)3.命題公式(PùQ）?P是()(A)永真式(B)永假式答案：(A)(C)可滿足式(D)合取范式解答(PùQ）?P(PQ)PPQP1Q1所以是永真式.故選擇(A).4.設(shè)命題公式G(PQ),HP(QP)，則公式G與H滿足()(A)GH答案：(D)解答(B)HG(C)HG(D)GHG(PQ)PQHP(QP)PQGH，即GH為重言式.GH(PQ)(PQ)(PQ(PQ)P11或列真值表.PQ0101?P1?Q1G??(P?Q)H?P?(Q??P)G?H0011001011101111100100可編輯-------------精選文檔-----------------可見，GTH，故應(yīng)選擇(D).三、練習(xí)題1.判定下列語句是否為命題，若是命題，指出是簡單命題或復(fù)合命題.(1)2是無理數(shù).(2)5能被2整除.(3)現(xiàn)在開會(huì)嗎？(4)2是素?cái)?shù)當(dāng)且僅當(dāng)三角形有3條邊.(5)如果雪是黑的，則太陽從東方升起.2.將第1題的命題符號(hào)化，并討論其真值.3.設(shè)命題P,Q的真值為0，命題R,S的真值為1，求命題公式(P真值.4.用多種方法判定命題公式(P(R)(QS)的PQ))R)的類型.5.用多種方法證明等值式(PQ)(PQ)P成立.6.已知命題P，Q和真值函數(shù)F的真值，(P,Q,F)?(,00,0),(0,1,0),(1,0,1),(1,1,0).試用P，Q和聯(lián)結(jié)詞?，ú構(gòu)造命題公式C，使得F?C.7.求命題公式(PQ)(QP)的主析取范式和主合取范式.8.試證明：(PQ)(QR)RP四、練習(xí)題答案1.(1),(2)是簡單命題，(3)不是命題，(4)，(5)是復(fù)合命題.2.(1)P:2是無理數(shù),P是真命題，真值為1.(2)P：5能被2整除，P是假命題，真值為0(4)P：2是素?cái)?shù)，Q：三角形有3條邊，原命題符號(hào)化為P?Q.，真值為1可編輯-------------精選文檔-----------------(5)P：雪是黑的，Q：太陽從東方升起，原命題符號(hào)化為P?Q，其真值為1..3.真值為0.PQR，是非永真的可滿足式。4.原式等值于5.提示：用分配律、否定律、同一律.6.C(PQ)7主析取范式：(PQ)(PQ)(PQ)mmm302主合取范式：PQM18.前提：(PQ),(QR),R結(jié)論：P證明方法1，直接證明法(1)?QúR(2)?RPP(3)?Q(1),(2)析取三段論(4)?(Pù?Q〕(5)?PúQ(6)P?QP(4)置換(5)置換(7)?P(3),(6)拒取式方法2，間接證明法(1)?(?P)結(jié)論否定引入(2)P(1)置換(3)?(Pù?Q)P(4)P?Q(5)Q(3)置換(2),(4)假言推理可編輯

-------------精選文檔-----------------(6)?QúR(7)RP(5),(6)析取三段論P(yáng)(8)?R(9)Rù?R(7),(8)合取引入有(9)可知，構(gòu)造推理是正確的.??第2章謂詞邏輯本章重點(diǎn)：謂詞與量詞，公式與解釋，前束范式，謂詞邏輯推理證明.一、重點(diǎn)內(nèi)容1.謂詞與量詞h謂詞，在謂詞邏輯中，原子命題分解成個(gè)體詞和謂詞.個(gè)體詞是可以獨(dú)立存在的客體，它可以是具體事物或抽象的概念。謂詞是用來刻劃個(gè)體詞的性質(zhì)或事物之間關(guān)系的詞.個(gè)體詞分個(gè)體常項(xiàng)(用a,b,c,…表示)和個(gè)體變項(xiàng)(用x,y,z,…表示)；謂詞分謂詞常項(xiàng)(表示具體性質(zhì)和關(guān)系)和謂詞變項(xiàng)(表示抽象的或泛指的謂詞)，用F,G,P,…表示.注意，單獨(dú)的個(gè)體詞和謂詞不能構(gòu)成命題，將個(gè)體詞和謂詞分開不是命題.h量詞，是在命題中表示數(shù)量的詞，量詞有兩類：全稱量詞"，表示“所有的”或“每一個(gè)”；存在量詞$，表示“存在某個(gè)”或“至少有一個(gè)”.在謂詞邏輯中，使用量詞應(yīng)注意以下幾點(diǎn)：(1)(1)在不同個(gè)體域中，命題符號(hào)化的形式可能不同，命題的真值也可能會(huì)改變.(2)(2)在考慮命題符號(hào)化時(shí)，如果對個(gè)體域未作說明，一律使用全總個(gè)體域.可編輯

-------------精選文檔-----------------(3)(3)多個(gè)量詞出現(xiàn)時(shí)，不能隨意顛倒它們的順序，否則可能會(huì)改變命題的含義.謂詞公式只是一個(gè)符號(hào)串，沒有什么意義，但我們給這個(gè)符號(hào)串一個(gè)解釋，使它具有真值，就變成一個(gè)命題.所謂解釋就是使公式中的每一個(gè)變項(xiàng)都有個(gè)體域中的元素相對應(yīng).在謂詞邏輯中，命題符號(hào)化必須明確個(gè)體域，無特別說明認(rèn)為是全總個(gè)體域。一般地，使用全稱量詞"，特性謂詞后用?；使用存在量詞$，特性謂詞后用ù.2.公式與解釋h謂詞公式，由原子公式、聯(lián)結(jié)詞和量詞可構(gòu)成謂詞公式(嚴(yán)格定義見教材).命題的符號(hào)化結(jié)果都是謂詞公式.例如"x(F(x)?G(x))，$x(F(x)ùG(x))，"x"y(F(x)ùF(y)ùL(x,y)?H(x,y))等都是謂詞公式.h變元與轄域，在謂詞公式"xA和$xA中，x是指導(dǎo)變元，A是相應(yīng)量詞的轄域.在"x和$x的轄域A中，x的所有出現(xiàn)都是約束出現(xiàn)，即x是約束變元，不是約束出現(xiàn)的變元，就是自由變元.也就是說，量詞后面的式子是轄域.量詞只對轄域內(nèi)的同一變元有效.h換名規(guī)則，就是把公式中量詞的指導(dǎo)變元及其轄域中的該變元換成該公式中沒有出現(xiàn)的個(gè)體變元，公式的其余部分不變.h代入規(guī)則，就是把公式中的某一自由變元，用該公式中沒有出現(xiàn)的個(gè)體變元符號(hào)替代，且要把該公式中所有的該自由變元都換成新引入的這個(gè)符號(hào).h解釋(賦值)，謂詞公式A的個(gè)體域D是非空集合，則(1)每一個(gè)常項(xiàng)指定D中一個(gè)元素；(2)每一個(gè)n元函數(shù)指定Dn到D的一個(gè)函數(shù)；(3)每一個(gè)n元謂詞指定Dn到{0,1}的一個(gè)謂詞；按這個(gè)規(guī)則做的一組指派，稱為A的一個(gè)解釋或賦值.在有限個(gè)體域下，消除量詞的規(guī)則為：如D＝{a1,a2,…,an}，則可編輯

-------------精選文檔-----------------xA(x)A(a)A(a)...A(a)xA(x)A(a)A(a)...A(a)12n12nh謂詞公式分類，在任何解釋下，謂詞公式A取真值1，公式A為邏輯有效式(永真式)；在任何解釋下謂詞公式A取真值0，公式A為永假式；至少有一個(gè)解釋使公式A取真值1，公式A稱為可滿足式.3.前束范式一個(gè)謂詞公式的前束范式仍是謂詞公式.若謂詞公式F等值地轉(zhuǎn)化成QxQx...QxBk1122k那么QxQx...QxB就是F的前束范式，其中Q1，Q2，…，Qk只能是"或$，x1,x2,…,xk1122kk是個(gè)體變元，B是不含量詞的謂詞公式.每個(gè)謂詞公式F都可以變換成與它等值的前束范式.其步驟如下：①消去聯(lián)結(jié)詞?，?，`ú；②將聯(lián)結(jié)詞?移至原子謂詞公式之前；③利用換名或代入規(guī)則使所有約束變元的符號(hào)均不同，并且自由變元與約束變元的符號(hào)也不同；④將"x,$x移至整個(gè)公式最左邊；⑤得到公式的前束范式.4.謂詞邏輯的推理理論謂詞演算的推理是命題演算推理的推廣和擴(kuò)充，命題演算中的基本等值公式，重言蘊(yùn)含式以及P，T，CP規(guī)則在謂詞演算中仍然使用.在謂詞演算推理中，某些前提和結(jié)論可能受到量詞的限制，為了使用這些推理，引入消去和附加量詞的規(guī)則，有US規(guī)則(全稱量詞消去規(guī)則)，UG規(guī)則(全稱量詞附加規(guī)則)，ES規(guī)則(存在量詞消去規(guī)則)，EG規(guī)則(存在量詞附加規(guī)則)等，以便使謂詞演算公式的推理過程可類似于命題演算的推理進(jìn)行.二、實(shí)例可編輯

-------------精選文檔-----------------例2.1將下列命題符號(hào)化：(1)有某些實(shí)數(shù)是有理數(shù)；(2)所有的人都呼吸；(3)每個(gè)母親都愛自己的孩子.注意：一般地，全稱量詞“"”后，跟蘊(yùn)含聯(lián)結(jié)詞“?”；存在量詞“$”后，跟合取聯(lián)結(jié)詞“ù”.解(1)設(shè)R(x)：x是實(shí)數(shù)，Q(x)：x是有理數(shù)。該命題符號(hào)化$x(R(x)ùQ(x)).(2)設(shè)全總個(gè)體域，設(shè)M(x)：x是人.，H(x)：x要呼吸，該命題符號(hào)化為："x(M(x)?H(x))該命題等價(jià)說法：“不存在不需要呼吸的人”，符號(hào)化為：?$x(M(x)ù?H(x)).其實(shí)它們是等值的，"x(M(x)?H(x))???"x(M(x)?H(x))??(?"x(?M(x)úH(x)))??$x(M(x)ù?H(x))若個(gè)體域D為人的集合。H(x)：x要呼吸.則該命題符號(hào)化為"xH(x).(3)在全總個(gè)體域，設(shè)M(x):x是母親，L(x,y):x愛y，A(y):y是孩子,H(x,y):x屬于y命題符號(hào)化為：x(M(x)y(A(y)H(y,x)L(x,y)))或xy(M(x)A(y)H(y,x)L(x,y)))若個(gè)體域D是所有母親的集合.M(x)：x愛自己的孩子，該命題符號(hào)化為"xM(x).例2.2指出公式xy(R(x,y)L(y,z))xH(x,y)中量詞的每次出現(xiàn)轄域，并指出變元的每次出現(xiàn)是約束出現(xiàn)，還是自由出現(xiàn)，以及公式的約可編輯

-------------精選文檔-----------------束變元，自由變元.解在公式xy(R(x,y)L(y,z))xH(x,y)中，"x只有一次出現(xiàn)，轄域是y(R(x,y)L(y,z))；"y只有一次出現(xiàn)，轄域是R(x,y)L(y,z)；$x只有一次出現(xiàn)，轄域是H(x,y).變元x在該公式中有四次出現(xiàn)，其中第1次、第2次出現(xiàn)是在"x及其轄域中，故是約束出現(xiàn)；第3次，第4次出現(xiàn)是在$x及其轄域中，也是約束出現(xiàn)。這四次出現(xiàn)都是約束出現(xiàn)，所以x是該公式的約束變元.變元y在該公式中也有四次出現(xiàn).其中第1次是在"y中，第2次和第3次出現(xiàn)是在"y的轄域中，是約束出現(xiàn)，第4次出現(xiàn)是自由出現(xiàn)，故y在該公式中有3次約束出現(xiàn)，1次自由出現(xiàn)，因此變元y既是該公式的約束變元，也是自由變元.變元z在該公式中只有一次自由出現(xiàn)，所以z是該公式的自由變元.注意，由例2.2看到，同一個(gè)個(gè)體變項(xiàng)，在同一個(gè)公式中，既可以是約束出現(xiàn)，也可以是自由出現(xiàn)，這種情況有時(shí)會(huì)造成一些混淆，帶來不便.要改變這種情況，使一個(gè)個(gè)體變項(xiàng)在同一個(gè)公式中，不同時(shí)既是約束出現(xiàn)，又是自由出現(xiàn)，采取換名規(guī)則或代入規(guī)則.在求前束范式時(shí)，尤其需要.例2.3給定解釋I如下：①①D＝{2,3};②D中特定元素a=2；③函數(shù)為f(2)3,f(3)2；④謂詞F(x)為F(2)=0,F(3)=1，G(x,y)為G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)為L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0求在解釋I下各公式的真值.(1)xF(x)G(x,a);(2)xyL(x,y)；(3)x(F(f(x))G(x,f(x))).(1)(F(2)G(2,2))(F(3)G(3,2))(00)(10)000解(2)yL(2,y)yL(3,y){L(2,2)L(2,3)){L(3,2)L(3,3)}(10)(01)1(3)x(F(f(x))G(x,f(x)))(F(f(2))G(2,f(2)))(F(f(3))G(3,f(3)))可編輯

-------------精選文檔-----------------(10)(00)0這是給定解釋下，求謂詞公式的真值，個(gè)體域有限，比較好求。只需將量詞消去，函數(shù)值代入謂詞，根據(jù)謂詞的真值，即可求出謂詞公式的真值.要判斷一個(gè)謂詞公式的真、假是較為難的.在謂詞邏輯中，在任何解釋下都真的公式，才是永真式；在任何解釋下公式A為假，才是永假式；公式A不總是假，或者至少有一個(gè)解釋使得公式A為真，才是可滿足式.困難之點(diǎn)是在全總個(gè)體域中所有的解釋如何說清楚.因此只能要求會(huì)作簡單問題.例2.4討論公式xyF(x,y)yxF(x,y)的類型.解用A表示該公式.對任意解釋I，A的前件為假，無論后件真假，公式A為真.這說明A不是永假式；取解釋I如下：個(gè)體域?yàn)檎麛?shù)集，F(xiàn)(x,y)：x￡y，在I下，"x$yF(x,y)，即在整數(shù)中，任給整數(shù)x，存在y使得x￡y，顯然為真，即A的前件為真.但后件$y"xF(x,y)，即存在y對任給x使得x￡y，顯然這是不成立的，亦即后件為假.由蘊(yùn)含聯(lián)結(jié)詞的真值表1?0的真值為0，故A為假。這說明A不是永真式.綜上所述，A是可滿足式.由例2.4可知，量詞的次序不能隨便顛倒.Fx(A(x)B(x,y))(yC(y)zD(y,z))化為前束范式.例2.5將公式解①消去聯(lián)結(jié)詞?(若有?，`ú也要消去).F(x(A(x)B(x,y))(yC(y)zD(y,z))②將聯(lián)結(jié)詞?移至原子公式之前.Fx(A(x)B(x,y))(yC(y)zD(y,z))x(A(x)B(x,y))(yC(y)zD(y,z))③換名.可編輯

-------------精選文檔-----------------Fx(A(x)B(x,y))(tC(t)zD(y,z))(自由變元的y未改)④把量詞提到整個(gè)公式的前面.Fxtz((A(x)B(x,y))C(t)D(y,z))為所求前束范式.寫在一起，所求前束范式是F(x(A(x)B(x,y))(yC(y)zD(y,z))x(A(x)B(x,y))(yC(y)zD(y,z))x(A(x)B(x,y))(yC(y)zD(y,z))xAx(()BxytC(t)zD(y,z))(自由變元的y未改)(,))(xtzAx((()B(x,y))C(t)D(y,z))注：重要的是弄清楚前束范式的定義，求前束范式主要是利用基本等值式、蘊(yùn)含式和換名規(guī)則，把一個(gè)謂詞公式化為量詞在最前面，后面不含量詞的公式，即前束范式.雖然前束范式是謂詞公式的一種標(biāo)準(zhǔn)形式，但是一般一個(gè)謂詞公式的前束范式并不是唯一的.例2.6構(gòu)造推理證明前提：$xF(x),"x(F(x)?G(x)ùH(x))結(jié)論：$x(F(x)ùH(x))證明：①$xF(x)[前提引入]②F(c)[①ES]③"x(F(x)?G(x)ùH(x))[前提引入]④F(c)?G(c)ùH(c)[③US]⑥H(c)ùG(c)[⑤置換]⑧F(c)ùH(c)[②,⑦合取]⑤G(c)ùH(c)[②,④假言推理]⑦H(c)[⑥化簡]⑨$x(F(x)ùH(x))[EG]例2.7單項(xiàng)選擇題1.謂詞公式x(P(x)yR(y))Q(x)中量詞"x的轄域是()(A)x(P(x)yR(y))(B)P(x)(C)P(x)yR(y)(D)Q(x)答案：(C)解答："x后面的公式是P(x)(yR(y)).故應(yīng)選擇(C).可編輯

-------------精選文檔-----------------2.謂詞公式xA(x)?xA(x)的類型是（）(A)永真式(B)矛盾式(C)非永真式的可滿足式(D)不屬于(A),(B),(C)任何類型答案：(B)解答：對于任意解釋I，xA(x)?xA(x)?0所以xA(x)?xA(x)是永假式.選擇(B).3設(shè)個(gè)體域?yàn)檎麛?shù)集，下列公式中其真值為1的是()(xyxy0)(B)yx(xy0)(D)xy(xy0)(A)(xyxy0)(C)答案：(A)解答：任意一個(gè)整數(shù)x，都能找到y(tǒng)＝－x，使x+y=0,故(A)式是永真式.4設(shè)L(x)：x是演員，J(x)：x是老師，A(x,y)：x佩服y.那么命題“所有演員都佩服某些老師”符號(hào)化為()(A)xL(x)A(x,y)(B)x(L(x)y(J(y)A(x,y))(D)xy(L(x)J(y)A(x,y))(C)xy(L(x)J(y)A(x,y))答案：(B)解答：將命題符號(hào)化為x(L(x)y(J(y)A(x,y))，故應(yīng)選擇(B).5在謂詞演算中，P(a)是xP(x)的有效結(jié)論，根據(jù)是()(A)US規(guī)則答案：(A)(B)UG規(guī)則(C)ES規(guī)則(D)EG規(guī)則xA(x)A(c),即A(c)是xA(x)的有效結(jié)論.應(yīng)選擇(A).解答：全稱量詞消去規(guī)則的定義為例2.8填空題可編輯-------------精選文檔-----------------1.公式x(P(x)Q(x,y))zR(y,z)S(x))的自由變元是,約束變元是答案：y,x;x,z.解答："x的轄域是P(x)Q(x,y),故x是約束出現(xiàn)，y是自由出現(xiàn)，z的轄域是R(y,z)，故z是約束出現(xiàn)，y是自由出現(xiàn)，而S(x)中的x是自由出現(xiàn).總之y,x是自由變元，x,z是約束變元.2.謂詞邏輯公式xP(x)xQ(x)的前束范式是答案：x(P(x)Q(x)).解答：求前束范式xP(x)xQ(x)(xP(x))xQ(x)xP(x)xQ(x)x(P(x)Q(x))3.設(shè)個(gè)體域D＝{a,b},消去公式中的量詞，則xP(x)xQ(x)答案：P(a)P(b)(Q(a)Q(b))解答：由"x和$x真值的定義，xP(x)xQ(x)P(a)P(b)(Q(a)Q(b))4.換名規(guī)則施于變元，代入規(guī)則施于變元答案：約束；自由.解答：見換名規(guī)則和代入規(guī)則的定義.三、練習(xí)題1.將下列命題符號(hào)化：(1)丘華和李兵都是學(xué)生；(2)存在偶素?cái)?shù)；2.指出謂詞公式x(P(x)Q(x))xP(x)Q(x)中量詞的轄域，并指出變元的每可編輯

-------------精選文檔-----------------次出現(xiàn)是約束出現(xiàn)，還是自由出現(xiàn)，以及公式的約束變元，自由變元.3.設(shè)個(gè)體域D＝{岳飛，文天祥，秦薈}，謂詞F(x)：x是民族英雄。求"xF(x)的真值。4.設(shè)P是二元謂詞，給定解釋I如下：D＝{a,b},P(a,a)=P(b,a)=1，P(b,a)=P(b,b)=0求下列公式的真值：(1)xP(x,x)；(2)xyP(x,y);(3)xyP(x,y)5.討論公式xF(x)xF(x)的類型.6.用歸謬法，構(gòu)造下面的推理證明.xA(x)xB(x)Tx(A(x)B(x))四、練習(xí)題答案1.(1)設(shè)P(x)：:x是學(xué)生。.a：丘華，b：黎兵該命題符號(hào)化為：P(a)ùP(b)(2)設(shè)N(x):x是自然數(shù)，F(xiàn)(x)：x是偶數(shù)，Q(x)：x是素?cái)?shù)該命題符號(hào)化為$x(N(x)ùF(x)ùQ(x))2.在公式x(P(x)Q(x))xP(x)Q(x)中,"x有二次出現(xiàn)，第一次出現(xiàn)的轄域是P(x)Q(x)Q(x)中;第二次出現(xiàn)的轄域是P(x).變元x在該公式中有六次出現(xiàn)，其中第1，4次出現(xiàn)和第2，3，5次出現(xiàn)均是約束出現(xiàn)；第6次是自由出現(xiàn).變元x在該公式中5次約束出現(xiàn)，1次自由出現(xiàn).因此變元x既是該公式的約束變元，也是自由變元.3.設(shè)a,b,c分別為岳飛，文天祥和秦檜，"xF(x)?F(a)ùF(b)ùF(c)?04.(1)0；(2)"x$y(P(y,x)?$yP(y,a)ù$yP(y,b)?(P(a,a)úP(b,a))ù(P(a,b)úP(b,b))?1ù0?0(3)$x$y(P(x,