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

離散數(shù)學(xué)數(shù)理邏輯部分期末復(fù)習(xí)輔導(dǎo)一、單項(xiàng)選擇題1．設(shè)P：我將去打球,Q:我有時(shí)間.命題“我將去打球,僅當(dāng)我有時(shí)間”符號(hào)化為(）.Ａ.Ｂ．C.D.復(fù)習(xí):Ｐ→Q表達(dá)的邏輯關(guān)系是，P是Ｑ的充足條件，或Q是P的必要條件．因此“只要P則(就）Ｑ”,“P僅當(dāng)Q”,“只有Ｑ才P”等，都可用復(fù)合命題P→Q表達(dá)．解由于語(yǔ)句“我有時(shí)間”是“我將去打球”的必要條件,所以選項(xiàng)B是對(duì)的的．記?。骸癙僅當(dāng)Ｑ”即表達(dá)為P→Q．答Ｂ問：假如把“我將去打球”改成“我將去市里”、“我將去旅游”等，會(huì)符號(hào)化嗎?２．設(shè)命題公式G：,則使公式G取真值為１的P，Q，R賦值分別是（)．A．0,０，0B.０,0，1C.0，１,０D.解對(duì)于選項(xiàng)A、B、C、Ｄ中,ＱR的真值為0,要使公式Ｇ取真值為1，必需P的真值為0,從而Ｐ的真值為1,所以選項(xiàng)D是對(duì)的的.答Ｄ若題目改為：設(shè)命題公式P(QＲ)取真值為1,則Ｐ，Q,Ｒ的賦值是．答１，０,０;１,0,1;1,1,0;1，1，１;0,1,13.命題公式（PQ)Ｒ的析取范式是()．Ａ．(PQ)RB．(PQ）RＣ.(PQ）ＲD.(PQ)R復(fù)習(xí):范式:一個(gè)命題公式稱為析取(合取）范式,當(dāng)且僅當(dāng)它具有形式：A1A２…An(Ａ1Ａ2…Ａｎ),（ｎ1其中A１,A2,…,Ａｎ均是由命題變?cè)蚱浞裾J(rèn)所組成的簡(jiǎn)樸合?。ㄎ鋈。┦?對(duì)于給定的命題公式，假如有一個(gè)等價(jià)公式,它僅僅由小項(xiàng)(大項(xiàng)）的析取(合?。┙M成，則該等價(jià)式稱為原式的主析?。ㄖ骱先?范式．求命題公式的主析取(主合?。┓妒降耐蒲莪h(huán)節(jié)：（１）一方面將公式化為析?。ê先。┓妒?①將公式中的聯(lián)結(jié)詞化歸成，及.(運(yùn)用雙條件等價(jià)式PQ（PＱ)(ＱＰ)消去，運(yùn)用蘊(yùn)含等價(jià)式PQPQ消去）②運(yùn)用德·摩根律將否認(rèn)符號(hào)直接移到各個(gè)命題變?cè)埃圻\(yùn)用合取對(duì)析取（析取對(duì)合取)的分派律、結(jié)合律將公式歸約為析取范式(合取范式)．(２)除去析取(合取)范式中永假(真)的析取(合?。╉?xiàng)，并將析?。ê先。┓妒街蟹磸?fù)出現(xiàn)的合取(析取)項(xiàng)和相同變?cè)喜?(３)對(duì)于不是小項(xiàng)(大項(xiàng))的合取(析取)式,補(bǔ)入沒有出現(xiàn)的命題變?cè)?，即通過合?。ㄎ鋈?添加(PＰ）（（ＰＰ））式，然后應(yīng)用合取(析?。?duì)析取(合取）的分派律展開公式.(4)合并相同的小項(xiàng)（大項(xiàng)），并將小項(xiàng)（大項(xiàng))按編碼從小到大的順序排列,可用∑（∏)表達(dá)之．主析取范式與主合取范式的關(guān)系:一般地,若命題公式A的主析取范式為∑(i1,i2,…,ｉk)則公式Ａ的主合取范式為∏（0,1,…，i１－１,i1+1,…,ik-1，ik+1,…,2n-1）解答D4.命題公式(PQ)的合取范式是(）.A.PQＢ．(ＰQ）(PQ）C.PQD.(PQ）答C5．命題公式的析取范式是().A.BC.Ｄ.解答A注意:第3、4、５題復(fù)習(xí)了合取范式和析取范式的概念,大家一定要記住的。假如題目改為求一個(gè)變?cè)≒或Ｐ)命題公式的合取范式或析取范式,那么答案是什么？6．下列等價(jià)公式成立的為(）.A.PQPＱB.P(QP)P(PQ）C.Q(PQ）Q(PQ)Ｄ.P（ＰQ）Q解A.PQ(PＱ)B.Ｐ(QP)P(ＱP）P(PQ）P(PQ）C.Ｑ(ＰQ）Q（PＱ)D.P(PQ)(PP)(PＱ)１(PQ)PQ答B(yǎng)７．下列公式成立的為().A．PＱＰQB.PＱＰQC.QＰPＤ．Ｐ(PＱ)Q解A.ＰQ(PQ)Ｂ.PQPQC.(QP)P(QP)P(QP)Ｐ(QP）(PＰ)（QＰ)1PQ（不是永真式）D．P(PQ)Q（析取三段論,P171公式(１0）)或者直接推導(dǎo)：Ｐ(ＰQ)Ｑ(P(ＰQ))Q(Ｐ（PQ))Q((PP)（PＱ))Q(PQ)QP(QQ)P1１所以Ｐ(PQ)Ｑ答D8.下列公式中（)為永真式．A.ＡＢABB.AB(AB)C.ABＡBＤ.AＢ(AB)解由定理6.5．3有,AB的充足必要條件是AB為永真式(重言式）A.,B.,C.，D.，答B(yǎng)9．下列公式(）為重言式．A．ＰQPQＢ.(Q（ＰQ))(Ｑ(PQ)）C．(P(QＰ)）(Ｐ(PQ）)D.（P(PQ))Q解Ａ.,B．C．所以,(Ｐ(QP))（Ｐ(ＰQ))１D.答C說明:(１)假如本題題目改為“下列公式()為永真式”,應(yīng)當(dāng)是同樣的．(2)上述兩題也可以運(yùn)用公式AB(AB)(BA)直接驗(yàn)證.１0．設(shè)Ａ(ｘ)：ｘ是人，B（x):ｘ是學(xué)生，則命題“不是所有人都是學(xué)生”可符號(hào)化為(）．A．(x)(A(x）B(x））Ｂ.（x）(A（x)Ｂ(ｘ))C.(x）（A(x)B(x）)D．(x）(A（ｘ)B(ｘ))解（x)(A(x)B（x))表達(dá)“所有人都是學(xué)生”,它的否認(rèn)即為公式C．答C11.設(shè)A(x):x是人，Ｂ（x)：x是工人,則命題“有人是工人”可符號(hào)化為().Ａ．(x)(A(ｘ)B(x))B.（ｘ)(A(x)B(x))Ｃ．(x)(A（x)B（x))D.(x）（A(ｘ)B（x))答Ａ1２.設(shè)C(x)：ｘ是國(guó)家級(jí)運(yùn)動(dòng)員，G(x)：x是健壯的,則命題“沒有一個(gè)國(guó)家級(jí)運(yùn)動(dòng)員不是健壯的”可符號(hào)化為()．A.B．C．D.答D13．表達(dá)式中的轄域是().A.P(x,y)B．Ｐ(ｘ,y）Q(z)C.R(x，y)D．P(ｘ,y)Ｒ(x,y)答B(yǎng)注意:假如該題改為判斷題,即表達(dá)式中的轄域是Ｐ(x，ｙ)．如何判斷并說明理由呢？14.在謂詞公式(x)(A(ｘ)→B(ｘ)C(ｘ，ｙ）)中，().A．x,y都是約束變?cè)?ｘ,y都是自由變?cè)狢．x是約束變?cè)?，y是自由變?cè)狣.x是自由變?cè)?y是約束變?cè)餋注:假如該題改為填寫約束變?cè)蜃杂勺冊(cè)奶羁疹}，大家也應(yīng)當(dāng)掌握．補(bǔ)充題：設(shè)個(gè)體域?yàn)樽匀粩?shù)集合,下列公式中是真命題的為()．Ａ.Ｂ．C．D．解由于選項(xiàng)Ａ表達(dá):對(duì)任一自然數(shù)x存在自然數(shù)ｙ滿足ｘy=1,這樣的y是不存在的選項(xiàng)Ｂ表達(dá):對(duì)任一自然數(shù)x存在自然數(shù)ｙ滿足x＋y=0，這樣的y也是不存在的選項(xiàng)C表達(dá)：存在一自然數(shù)x對(duì)任意自然數(shù)ｙ滿足xy=x，取x=0即可，故選項(xiàng)C對(duì)的選項(xiàng)D表達(dá):存在一自然數(shù)x對(duì)任意自然數(shù)y滿足ｘ+y=2y，這樣的x是不存在的答C１５.設(shè)個(gè)體域D={a，b,c},那么謂詞公式消去量詞后的等值式為．Ａ.(Ａ(a)A(b）Ａ(ｃ）)(Ｂ(a)B(ｂ）B(c))B．(A（ａ）A(b）A(c)）(Ｂ(a)B(b）B（c))C．（A(a)Ａ(b)A（c))（B(a)B(b）B(c））D.(Ａ(ａ)Ａ（b)A(ｃ）)（B（a）B(b)B(c))答A１6．命題公式的主合取范式是()．A．B.C．Ｄ.答C１７.下列等價(jià)公式成立的為(）．Ａ.ＰPQQB.QＰＰＱC.PＱPＱD．ＰＰQ解Ａ．ＰP０QQＢ.QＰP(Q)PQPQＣ.PQＰQD.PP1Q18．命題公式為().A．矛盾式B.可滿足式C.重言式D.合取范式解是可滿足式.答B(yǎng)1９.謂詞公式xA(ｘ)ｘＡ(x）是().A．不可滿足的B．可滿足的C．有效的D.蘊(yùn)含式答A20．前提條件的有效結(jié)論是(）.A.PB.PＣ.QD.Q答D（假言推理）二、填空題1．命題公式的真值是．解答１或T問:命題公式、的真值是什么？2．設(shè)Ｐ：他生病了,Q：他出差了，R：我批準(zhǔn)他不參與學(xué)習(xí).則命題“假如他生病或出差了，我就批準(zhǔn)他不參與學(xué)習(xí)”符號(hào)化的結(jié)果為.答一般地,當(dāng)語(yǔ)句是由“假如……,那么……”，或“若……，則……”組成，它的符號(hào)化用條件聯(lián)結(jié)詞．3．具有三個(gè)命題變項(xiàng)Ｐ,Ｑ,R的命題公式PQ的主析取范式是．解答4．設(shè)Ｐ（x)：x是人，Q(x)：x去上課，則命題“有人去上課.”為.答5.設(shè)個(gè)體域Ｄ＝｛a,b},那么謂詞公式消去量詞后的等值式為．答注：假如個(gè)體域是D={１,2｝,D＝｛a,ｂ,c｝,或謂詞公式變?yōu)閤（A(x)Ｂ(x)),怎么做?6．設(shè)個(gè)體域D={１，２，3},A(ｘ)為“x小于3”,則謂詞公式(x)A（x)的真值為解(x)Ａ(x）Ａ(1)Ａ(2)A(3)１101答1注:若個(gè)體域D={1,2}，A（ｘ)為“x小于３”，則謂詞公式(x）A(ｘ）或:設(shè)個(gè)體域D={1,２，３},A(x)為“x是奇數(shù)”,則謂詞公式（ｘ）Ａ(x)的真值是什么?7.謂詞命題公式(x)（(Ａ(x)B(x))C(y))中的自由變?cè)獮椋饄問：公式中的約束變?cè)鞘裁?判斷:謂詞命題公式(x)（(A（x)B(x)）Ｃ(y))中的自由變?cè)獮椋?，是否?duì)的?為什么？８.謂詞命題公式（x)(P(x)→Ｑ(ｘ)R(ｘ，y))中的約束變?cè)獮?答x三、公式翻譯題1.請(qǐng)將語(yǔ)句“今天是天晴”翻譯成命題公式.解設(shè)P：今天是天晴.則命題公式為：Ｐ.問:“今天不是天晴”的命題公式是什么?２．請(qǐng)將語(yǔ)句“小王去旅游,小李也去旅游.”翻譯成命題公式.解設(shè)Ｐ：小王去旅游,Q:小李去旅游．則命題公式為:ＰQ.注:語(yǔ)句中包含“也”、“且”、“但”等連接詞，命題公式要用合取“”.３.請(qǐng)將語(yǔ)句“假如明天天下雪，那么我就去滑雪”翻譯成命題公式.解設(shè)Ｐ：明天天下雪，Ｑ:我去滑雪．則命題公式為:．4.請(qǐng)將語(yǔ)句“他去旅游,僅當(dāng)他有時(shí)間”翻譯成命題公式．解設(shè)P:他去旅游,Q:他有時(shí)間.則語(yǔ)句表達(dá)為.5．請(qǐng)將語(yǔ)句“有人不去工作”翻譯成謂詞公式.解設(shè)P（ｘ）：ｘ是人,Q(x):x去工作.則語(yǔ)句表達(dá)為．６.請(qǐng)將語(yǔ)句“所有人都努力工作.”翻譯成謂詞公式.解設(shè)Ｐ(x):x是人，Q（x):x努力工作.則語(yǔ)句表達(dá)為.注意:命題公式的翻譯還要注意“不可兼或”的表達(dá).例如，教材第164頁(yè)的例6“T2次列車５點(diǎn)或６點(diǎn)鐘開．”怎么翻譯成命題公式?這里的“或”為不可兼或.四、判斷說明題（判斷下列各題,并說明理由.)１．命題公式的真值是1.解錯(cuò)誤．是永假式（教材1６7頁(yè)的否認(rèn)律）.2．命題公式P（PQ）P為永真式．解對(duì)的.(否認(rèn)律)或由真值表PQＰＱPQP(PQ)P(PQ)Ｐ００11111０110111１0０11011100001可知，該命題公式為永真式.注：假如題目改為該命題公式為永假式,如何判斷并說明理由？3.謂詞公式是永真式．解對(duì)的.４．下面的推理是否對(duì)的,請(qǐng)給予說明.(1)（x)A（x）Ｂ(x)前提引入(2)A（ｙ）B（y)ＵS(1)解錯(cuò)由于A(x)中的ｘ是約束變?cè)?而B(x)中的x是自由變?cè)s束變?cè)c自由變?cè)荒芑煜畱?yīng)為:(１)(x)A(x)B(x)前提引入(2)(u)A（u)B(x）T（1)換名規(guī)則（3)(ｕ)(A(u)B(ｘ)）T(２)量詞轄域擴(kuò)張(４)A(y）B（ｘ)EＳ（３)五、計(jì)算題1.求PQＲ的析取范式、合取范式、主析取范式、主合取范式.解PQRPQR(析取范式、合取范式、主合取范式）(P(QQ)（RＲ））(（PP)Ｑ(RR))((PP）(ＱQ)R)（補(bǔ)齊命題變項(xiàng))(PＱR)(PQR)(PQR)(PＱR)(PQＲ)(PQR)(PＱR)(ＰQR)(ＰＱR)(ＰQR）(ＰQR)(ＰＱR)（對(duì)的分派律）(ＰQR)（PQＲ)（ＰＱR)（ＰQＲ)(PQR)（PQR)(PQR)（主析取范式）解二（運(yùn)用主析取范式與主合取范式的關(guān)系）ＰＱＲPQR（析取范式、合取范式、主合取范式)Ｍ100m000m001ｍ01０ｍ011m１０１(ＰQR）(PQR)（ＰＱR)(PＱR)(ＰＱR）（PＱR)（PQＲ)(主析取范式)2.求命題公式(PQ)（RQ)的主析取范式、主合取范式.解（析取范式）(對(duì)的分派律）(主合取范式）（同上題)(PQR)(PQR）（ＰＱR)(PQR）(PＱR)(PQR）(PＱR)（主析取范式）（根據(jù)上題）解二（運(yùn)用命題公式的真值表)列出命題公式(PQ)(RQ)的真值表如下：PＱRPＱRQ（PQ)(RＱ)小項(xiàng)大項(xiàng)00０001ＰQＲ0010１1PQR01011１ＰQR011１1１PＱR１００100PQR1０111１PＱＲ110111PQＲ１１111１ＰＱR表中所有小項(xiàng)的析取就是公式的主析取范式,所有大項(xiàng)的合取就是公式的主合取范式,故所求公式的主析取范式為：(PＱＲ)(PＱＲ)(PＱR)(PＱＲ)(PQR）(PQR）(PQR),主合取范式為:PQR．注：假如題目只是求“析取范式”或“合取范式”,大家就不必再進(jìn)一步求“主析取范式”或“主合取范式”.例如：求(PQ)Ｒ[或(PQ)（ＲQ)，ＰQＲ]的合取范式、析取范式．解（析取范式)（合取范式)(析取范式）(合取范式)（析取范式）(合取范式)3.設(shè)謂詞公式.（１）試寫出量詞的轄域;(２)指出該公式的自由變?cè)图s束變?cè)?解（1)量詞的轄域?yàn)?的轄域?yàn)?的轄域?yàn)?(2)自由變?cè)獮橹械模?，中的z.約束變?cè)獮橹械膞,中的ｚ，中的y．4.設(shè)個(gè)體域?yàn)镈={ａ1,ａ２}，求謂詞公式y(tǒng)xP(ｘ，y)消去量詞后的等值式．解六、證明題１.試證明(Ｐ(ＱR))ＰＱ與（PQ)等價(jià)．證明（蘊(yùn)含等價(jià)）（結(jié)合律）（吸取律）(德·摩根律）２.試證明(x)(Ｐ（ｘ)R(ｘ）)(x）Ｐ（ｘ)（x）R（x）.證明(１）(x)(P(x）R(x))P(2)P（a)R（a)ES(