2023年電大離散數(shù)學(xué)數(shù)理邏輯部分期末復(fù)習(xí)輔導(dǎo)

離散數(shù)學(xué)數(shù)理邏輯部分期末復(fù)習(xí)輔導(dǎo)一、單項選擇題1．設(shè)P：我將去打球,Q：我有時間.命題“我將去打球,僅當(dāng)我有時間”符號化為().A．B．C.Ｄ.復(fù)習(xí)：P→Ｑ表達(dá)的邏輯關(guān)系是,Ｐ是Ｑ的充足條件,或Q是P的必要條件.因此“只要P則（就)Ｑ”,“Ｐ僅當(dāng)Ｑ”,“只有Ｑ才Ｐ”等,都可用復(fù)合命題P→Q表達(dá)．解由于語句“我有時間”是“我將去打球”的必要條件，所以選項Ｂ是對的的.記?。骸癙僅當(dāng)Q”即表達(dá)為P→Q．答B(yǎng)問：假如把“我將去打球”改成“我將去市里”、“我將去旅游”等,會符號化嗎？2.設(shè)命題公式G：,則使公式G取真值為1的P，Q,R賦值分別是()．A.0，0,0B.0,０，1C.0，１,０D.解對于選項A、B、C、D中,ＱR的真值為0,要使公式G取真值為1,必需P的真值為0,從而P的真值為1,所以選項D是對的的.答D若題目改為:設(shè)命題公式P(QR)取真值為１,則P，Q，R的賦值是.答1,０,０；1,０,1；1,1，０；１,1，1；0,1,13．命題公式（PＱ）R的析取范式是().A．(ＰQ）RＢ.（PQ)ＲC．(ＰQ)RD.(PQ)R復(fù)習(xí)：范式：一個命題公式稱為析?。ê先?范式，當(dāng)且僅當(dāng)它具有形式:Ａ1A2…An(Ａ1A２…An),(n1其中Ａ1,Ａ2,…，An均是由命題變元或其否認(rèn)所組成的簡樸合取(析?。┦剑畬τ诮o定的命題公式，假如有一個等價公式，它僅僅由小項(大項）的析取(合取)組成,則該等價式稱為原式的主析取(主合取)范式.求命題公式的主析?。ㄖ骱先。┓妒降耐蒲莪h(huán)節(jié):(1)一方面將公式化為析?。ê先?范式.①將公式中的聯(lián)結(jié)詞化歸成,及.（運(yùn)用雙條件等價式PQ(ＰQ)(QP)消去,運(yùn)用蘊(yùn)含等價式PQPQ消去)②運(yùn)用德·摩根律將否認(rèn)符號直接移到各個命題變元之前．③運(yùn)用合取對析取(析取對合取）的分派律、結(jié)合律將公式歸約為析取范式（合取范式)．(2)除去析取（合?。┓妒街杏兰伲ㄕ?的析?。ê先。╉?并將析取(合取）范式中反復(fù)出現(xiàn)的合取(析取)項和相同變元合并.(3)對于不是小項（大項)的合取(析取)式,補(bǔ)入沒有出現(xiàn)的命題變元，即通過合取(析取)添加(PＰ)（(PP))式，然后應(yīng)用合?。ㄎ鋈?對析?。ê先?的分派律展開公式.（4)合并相同的小項（大項），并將小項(大項)按編碼從小到大的順序排列，可用∑（∏)表達(dá)之．主析取范式與主合取范式的關(guān)系:一般地，若命題公式A的主析取范式為∑（ｉ1,i2,…,ｉk)則公式A的主合取范式為∏（0,1，…,i1-1，i1+１，…,ik－1，ik+1,…,２ｎ-1)解答Ｄ４．命題公式(PQ）的合取范式是().A.ＰQB.（PQ)(PQ）C.PQＤ.(PQ)答C5．命題公式的析取范式是()．A．BＣ．D.解答A注意：第3、4、５題復(fù)習(xí)了合取范式和析取范式的概念，大家一定要記住的。假如題目改為求一個變元(Ｐ或P）命題公式的合取范式或析取范式，那么答案是什么?6.下列等價公式成立的為（）．A.PQPQＢ．P(QＰ)P(PＱ）C.Q(PQ)Q(PQ）D．P(PＱ)Ｑ解Ａ.PQ(PＱ)Ｂ.P（QP）P(QP)P(ＰＱ)Ｐ(PQ)C.Ｑ(ＰQ)Ｑ(PQ)D．P（PQ)(PP)（PQ)1(PQ)PQ答B(yǎng)7．下列公式成立的為()．A．PQPＱＢ．ＰQPQC.QＰPD.P(PQ)Q解A．PＱ(PＱ)B．PQＰQC.(QＰ)P(ＱＰ)P(QP)Ｐ（QP)（PP）(ＱP)1ＰＱ（不是永真式)D．P（PＱ)Ｑ（析取三段論，P171公式(10))或者直接推導(dǎo):Ｐ(PQ)Q(P（PQ))Q（P（PQ))Q（(PP）(ＰQ))Q（PＱ)ＱP(QQ）P１1所以Ｐ（PＱ）Q答D８．下列公式中()為永真式．A．ABAＢＢ.AB(AB)C．AＢABD．ＡB(AＢ)解由定理6.5.３有,AＢ的充足必要條件是AＢ為永真式(重言式）A．，B.，Ｃ．，D．,答B(yǎng)9．下列公式（)為重言式．Ａ．ＰQPＱB．（Q(PQ))（Q(ＰＱ)）C.（P(QP))(P(PQ)）Ｄ.(P(PQ))Q解A．，B．C.所以，(Ｐ(QP)）（P(PQ))1D.答C說明:（1）假如本題題目改為“下列公式()為永真式”，應(yīng)當(dāng)是同樣的.(２)上述兩題也可以運(yùn)用公式AB(AB)（ＢA）直接驗證.10.設(shè)A(x):x是人,Ｂ(ｘ):x是學(xué)生，則命題“不是所有人都是學(xué)生”可符號化為（).A．（ｘ)（A（ｘ)Ｂ(x）)B．(x）(A(ｘ)B(x）)C．(ｘ)(A(x)B(ｘ)）D．(x)(Ａ(x）B(x))解（x)(A(x)B(x))表達(dá)“所有人都是學(xué)生”，它的否認(rèn)即為公式C.答C11.設(shè)Ａ(x):x是人，B(ｘ)：x是工人，則命題“有人是工人”可符號化為（）．A.(x)(A（x)B(x）)B．(ｘ)(A(x)B(x))C．（x)（A(x)B(ｘ）)Ｄ.(x）(Ａ(ｘ）B(x))答A１2.設(shè)C(ｘ):ｘ是國家級運(yùn)動員,Ｇ(ｘ):x是健壯的,則命題“沒有一個國家級運(yùn)動員不是健壯的”可符號化為()．A.B.Ｃ.D.答D1３.表達(dá)式中的轄域是(）．A．P（x,y)B．Ｐ(x,y)Q(z)C．Ｒ(x,ｙ)D．P(x,y）R(x,y)答Ｂ注意：假如該題改為判斷題，即表達(dá)式中的轄域是P(x,y）.如何判斷并說明理由呢？14．在謂詞公式（x)(A(x)→Ｂ(x)Ｃ(x,y)）中，（）．A.x,ｙ都是約束變元B．x，y都是自由變元C.x是約束變元,ｙ是自由變元D.x是自由變元，y是約束變元答C注:假如該題改為填寫約束變元或自由變元的填空題，大家也應(yīng)當(dāng)掌握．補(bǔ)充題：設(shè)個體域為自然數(shù)集合,下列公式中是真命題的為()．A．B.Ｃ.D．解由于選項A表達(dá)：對任一自然數(shù)x存在自然數(shù)y滿足xｙ=1，這樣的y是不存在的選項B表達(dá)：對任一自然數(shù)x存在自然數(shù)ｙ滿足ｘ+y=0,這樣的ｙ也是不存在的選項Ｃ表達(dá)：存在一自然數(shù)ｘ對任意自然數(shù)y滿足xy=ｘ，取x＝０即可,故選項C對的選項Ｄ表達(dá)：存在一自然數(shù)ｘ對任意自然數(shù)y滿足ｘ+y=2y,這樣的x是不存在的答C１５.設(shè)個體域D={a，ｂ,c},那么謂詞公式消去量詞后的等值式為．Ａ.(A(a)A(b）A(c))(B(a)B(b)Ｂ(c)）Ｂ．(A（a）Ａ(b)A（ｃ))(Ｂ(ａ）B（b）B(ｃ）)C.(A(a)A(ｂ)Ａ(c))（Ｂ（a）Ｂ(b)B(c))Ｄ．(Ａ(a)A（b）A(c))（B(ａ)B(b)B(c))答A１6．命題公式的主合取范式是(）.A.Ｂ．Ｃ．D.答Ｃ17.下列等價公式成立的為（).A．PPQQＢ．ＱPＰQC．ＰQPＱＤ.ＰPQ解A.PＰ0QQB.ＱPＰ(Q)PQPQＣ．PＱＰQD．PP１Q１8．命題公式為（).A.矛盾式B．可滿足式C.重言式D.合取范式解是可滿足式.答B(yǎng)19．謂詞公式xA(x）xＡ(ｘ）是（）.Ａ．不可滿足的B.可滿足的C．有效的D.蘊(yùn)含式答Ａ20．前提條件的有效結(jié)論是()．A．ＰB.ＰC．ＱD．Q答D(假言推理)二、填空題１．命題公式的真值是.解答１或Ｔ問：命題公式、的真值是什么?2.設(shè)P:他生病了,Q:他出差了，R:我批準(zhǔn)他不參與學(xué)習(xí).則命題“假如他生病或出差了,我就批準(zhǔn)他不參與學(xué)習(xí)”符號化的結(jié)果為．答一般地，當(dāng)語句是由“假如……,那么……”，或“若……,則……”組成,它的符號化用條件聯(lián)結(jié)詞.３.具有三個命題變項Ｐ,Q，R的命題公式ＰQ的主析取范式是．解答４.設(shè)P(x)：x是人，Q(ｘ)：x去上課,則命題“有人去上課．”為.答５.設(shè)個體域D={a，b},那么謂詞公式消去量詞后的等值式為.答注：假如個體域是D＝{1,２｝，D=｛a,b,ｃ｝,或謂詞公式變?yōu)閤(A(x)B(x）),怎么做?６．設(shè)個體域D=｛１,2，3｝，A(x)為“ｘ小于3”，則謂詞公式（x)A(ｘ)的真值為解(x)Ａ(x)Ａ(1)A（2)A(3)1101答1注：若個體域D＝{１,2}，A(x)為“x小于3”,則謂詞公式(x）A（x)或:設(shè)個體域D＝{1,2，３}，A(x)為“x是奇數(shù)”,則謂詞公式(ｘ)Ａ(ｘ）的真值是什么?７．謂詞命題公式(x）((Ａ(x)Ｂ(x)）Ｃ(y)）中的自由變元為.答y問：公式中的約束變元是什么?判斷:謂詞命題公式(x)(（A(x)Ｂ(ｘ))Ｃ(ｙ))中的自由變元為x,是否對的？為什么?8.謂詞命題公式(x）(Ｐ(x)→Ｑ（x）R(x,y))中的約束變元為．答x三、公式翻譯題1．請將語句“今天是天晴”翻譯成命題公式.解設(shè)P：今天是天晴.則命題公式為:P.問：“今天不是天晴”的命題公式是什么?２.請將語句“小王去旅游,小李也去旅游．”翻譯成命題公式．解設(shè)Ｐ:小王去旅游,Q:小李去旅游.則命題公式為：PＱ.注:語句中包含“也”、“且”、“但”等連接詞,命題公式要用合取“”．３．請將語句“假如明天天下雪，那么我就去滑雪”翻譯成命題公式．解設(shè)P:明天天下雪，Q:我去滑雪.則命題公式為：．４.請將語句“他去旅游,僅當(dāng)他有時間”翻譯成命題公式．解設(shè)P:他去旅游,Ｑ:他有時間.則語句表達(dá)為．5．請將語句“有人不去工作”翻譯成謂詞公式.解設(shè)P(x）：x是人，Ｑ（ｘ)：x去工作．則語句表達(dá)為.6.請將語句“所有人都努力工作.”翻譯成謂詞公式．解設(shè)P(x):ｘ是人,Q(x）:x努力工作.則語句表達(dá)為．注意：命題公式的翻譯還要注意“不可兼或”的表達(dá)．例如,教材第164頁的例6“T2次列車5點或6點鐘開．”怎么翻譯成命題公式?這里的“或”為不可兼或.四、判斷說明題(判斷下列各題,并說明理由．）1.命題公式的真值是１.解錯誤.是永假式(教材１67頁的否認(rèn)律).2.命題公式Ｐ(PQ)P為永真式.解對的．(否認(rèn)律）或由真值表PQPQＰQP(PQ)Ｐ(ＰＱ)P０01１1１10110１1１１0０１１01１100０01可知,該命題公式為永真式．注:假如題目改為該命題公式為永假式，如何判斷并說明理由?３.謂詞公式是永真式．解對的.4.下面的推理是否對的,請給予說明.(1)（x)A(x)B(ｘ)前提引入(２)Ａ(ｙ)B(y）US（1）解錯由于A（x)中的x是約束變元，而Ｂ(ｘ)中的x是自由變元,約束變元與自由變元不能混淆．應(yīng)為：(1)(x)Ａ(x)B（ｘ)前提引入(2）(u)Ａ（u)B(ｘ)Ｔ（１）換名規(guī)則（3)（u)(A（ｕ)B（x）)T(2)量詞轄域擴(kuò)張(4）Ａ(y)Ｂ（x)EＳ(3)五、計算題1．求PQR的析取范式、合取范式、主析取范式、主合取范式.解ＰＱRPＱR（析取范式、合取范式、主合取范式)(P（ＱQ）(RR))(（PP)Q(RR）)((PP）(QQ)R）(補(bǔ)齊命題變項）(PQR)(PＱR)(ＰＱＲ)(ＰQR)(PQR）(PＱＲ)(PQR）(PQＲ)(PＱR）(PＱＲ)(ＰQR)（ＰQR)（對的分派律）(PQＲ)（ＰQR)(ＰQR)(PＱR)（PQR)(PQR)（PQR)（主析取范式)解二（運(yùn)用主析取范式與主合取范式的關(guān)系）ＰQRPＱR（析取范式、合取范式、主合取范式）Ｍ１0０ｍ0０0m001m010ｍ0１1m101(PQＲ)(PQR）(PQR)(ＰQR）(ＰＱR)(ＰＱR)(PＱR)(主析取范式）2．求命題公式(PＱ）(RＱ)的主析取范式、主合取范式．解(析取范式)（對的分派律)(主合取范式)(同上題)(ＰQR)（PQR）（PQR）(PQR)(PＱR)(PQR）（PQR)(主析取范式）（根據(jù)上題)解二(運(yùn)用命題公式的真值表)列出命題公式(PQ)（RＱ）的真值表如下：PQRPQＲＱ(ＰQ)(RQ)小項大項０0000１PQR001011PQR01011１PQR011１11ＰQR１０0100ＰＱR10１11１PＱＲ１１０1１1PＱR1１1111PQR表中所有小項的析取就是公式的主析取范式,所有大項的合取就是公式的主合取范式,故所求公式的主析取范式為:(PＱＲ)(ＰQR)（PQR）（PQR）（PQR)(ＰQR)(PQR)，主合取范式為:ＰQR.注：假如題目只是求“析取范式”或“合取范式”，大家就不必再進(jìn)一步求“主析取范式”或“主合取范式”．例如：求(PＱ）R［或(PQ）(RQ),PＱＲ]的合取范式、析取范式．解（析取范式)（合取范式)(析取范式）(合取范式)（析取范式）（合取范式)3.設(shè)謂詞公式.(１)試寫出量詞的轄域;(２）指出該公式的自由變元和約束變元.解（１）量詞的轄域為,的轄域為,的轄域為.(2）自由變元為中的y，中的z．約束變元為中的ｘ，中的z,中的ｙ．4.設(shè)個體域為Ｄ＝{ａ1,a２},求謂詞公式y(tǒng)xP(x，ｙ)消去量詞后的等值式．解六、證明題1.試證明(P（ＱR))PQ與(PＱ)等價．證明(蘊(yùn)含等價）（結(jié)合律）(吸取律）(德·摩根律)２.試證明(x)(P(ｘ)R(x)）(ｘ)P（x)（x)R(x)．證明（1)(x)(P(x)R（x))P（２)P(a）R(a)ＥＳ(