資料內容僅供您學習參考，如有不當或者侵權，請聯(lián)系改正或者刪除。離散數學數理邏輯部分期末復習輔導一、單項選擇題1．設P:我將去打球,Q:我有時間．命題”我將去打球,僅當我有時間”符號化為()．A．B．C．D．復習:P→Q表示的邏輯關系是,P是Q的充分條件,或Q是P的必要條件．因此”只要P則(就)Q”,”P僅當Q”,”只有Q才P”等,都可用復合命題P→Q表示．解因為語句”我有時間”是”我將去打球”的必要條件,因此選項B是正確的．記住:”P僅當Q”即表示為P→Q．答B(yǎng)問:如果把”我將去打球”改成”我將去市里”、”我將去旅游”等,會符號化嗎?2．設命題公式G:,則使公式G取真值為1的P,Q,R賦值分別是()．A．0,0,0B．0,0,1C．0,1,0D．解對于選項A、B、C、D中,QR的真值為0,要使公式G取真值為1,必須P的真值為0,從而P的真值為1,因此選項D是正確的．答D若題目改為:設命題公式P(QR)取真值為1,則P,Q,R的賦值是．答1,0,0;1,0,1;1,1,0;1,1,1;0,1,13．命題公式(PQ)R的析取范式是()．A．(PQ)RB．(PQ)RC．(PQ)RD．(PQ)R復習:范式:一個命題公式稱為析取(合取)范式,當且僅當它具有形式:A1A2…An(A1A2…An),(n其中A1,A2,…,An均是由命題變元或其否定所組成的簡單合取(析取)式．對于給定的命題公式,如果有一個等價公式,它僅僅由小項(大項)的析取(合取)組成,則該等價式稱為原式的主析取(主合取)范式．求命題公式的主析取(主合取)范式的推演步驟:(1)首先將公式化為析取(合取)范式．①將公式中的聯(lián)結詞化歸成,及．(利用雙條件等價式PQ(PQ)(QP)消去,利用蘊含等價式PQPQ消去)②利用德·摩根律將否定符號直接移到各個命題變元之前．③利用合取對析取(析取對合取)的分配律、結合律將公式歸約為析取范式(合取范式)．(2)除去析取(合取)范式中永假(真)的析取(合取)項,并將析取(合取)范式中重復出現的合取(析取)項和相同變元合并．(3)對于不是小項(大項)的合取(析取)式,補入沒有出現的命題變元,即經過合取(析取)添加(PP)((PP))式,然后應用合取(析取)對析取(合取)的分配律展開公式．(4)合并相同的小項(大項),并將小項(大項)按編碼從小到大的順序排列,可用∑(∏)表示之．主析取范式與主合取范式的關系:一般地,若命題公式A的主析取范式為∑(i1,i2,…,ik)則公式A的主合取范式為∏(0,1,…,i1-1,i1+1,…,ik-1,ik+1,…,2n-1)解答D4．命題公式(PQ)的合取范式是()．A．PQB．(PQ)(PQ)C．PQD．(PQ)答C5．命題公式的析取范式是()．A．BC．D．解答A注意:第3、4、5題復習了合取范式和析取范式的概念,大家一定要記住的。如果題目改為求一個變元(P或P)命題公式的合取范式或析取范式,那么答案是什么?6．下列等價公式成立的為()．A．PQPQB．P(QP)P(PQ)C．Q(PQ)Q(PQ)D．P(PQ)Q解A．PQ(PQ)B．P(QP)P(QP)P(PQ)P(PQ)C．Q(PQ)Q(PQ)D．P(PQ)(PP)(PQ)1(PQ)PQ答B(yǎng)7．下列公式成立的為()．A．PQPQB．PQPQC．QPPD．P(PQ)Q解A．PQ(PQ)B．PQPQC．(QP)P(QP)P(QP)P(QP)(PP)(QP)1PQ(不是永真式)D．P(PQ)Q(析取三段論,P171公式(10))或者直接推導:P(PQ)Q(P(PQ))Q(P(PQ))Q((PP)(PQ))Q(PQ)QP(QQ)P11因此P(PQ)Q答D8．下列公式中()為永真式．A．ABABB．AB(AB)C．ABABD．AB(AB)解由定理6.5.3有,AB的充分必要條件是AB為永真式(重言式)A．,B．,C．,D．,答B(yǎng)9．下列公式()為重言式．A．PQPQB．(Q(PQ))(Q(PQ))C．(P(QP))(P(PQ))D．(P(PQ))Q解A．,B．C．因此,(P(QP))(P(PQ))1D．答C說明:(1)如果本題題目改為”下列公式()為永真式”,應該是一樣的．(2)上述兩題也能夠利用公式AB(AB)(BA)直接驗證．10．設A(x):x是人,B(x):x是學生,則命題”不是所有人都是學生”可符號化為()．A．(x)(A(x)B(x))B．(x)(A(x)B(x))C．(x)(A(x)B(x))D．(x)(A(x)B(x))解(x)(A(x)B(x))表示”所有人都是學生”,它的否定即為公式C．答C11．設A(x):x是人,B(x):x是工人,則命題”有人是工人”可符號化為()．A．(x)(A(x)B(x))B．(x)(A(x)B(x))C．(x)(A(x)B(x))D．(x)(A(x)B(x))答A12．設C(x):x是國家級運動員,G(x):x是健壯的,則命題”沒有一個國家級運動員不是健壯的”可符號化為()．A．B．C．D．答D13．表示式中的轄域是()．A．P(x,y)B．P(x,y)Q(z)C．R(x,y)D．P(x,y)R(x,y)答B(yǎng)注意:如果該題改為判斷題,即表示式中的轄域是P(x,y)．如何判斷并說明理由呢?14．在謂詞公式(x)(A(x)→B(x)C(x,y))中,()．A．x,y都是約束變元B．x,y都是自由變元C．x是約束變元,y是自由變元D．x是自由變元,y是約束變元答C注:如果該題改為填寫約束變元或自由變元的填空題,大家也應該掌握．補充題:設個體域為自然數集合,下列公式中是真命題的為()．A．B．C．D．解因為選項A表示:對任一自然數x存在自然數y滿足xy=1,這樣的y是不存在的選項B表示:對任一自然數x存在自然數y滿足x+y=0,這樣的y也是不存在的選項C表示:存在一自然數x對任意自然數y滿足xy=x,取x=0即可,故選項C正確選項D表示:存在一自然數x對任意自然數y滿足x+y=2y,這樣的x是不存在的答C15．設個體域D={a,b,c},那么謂詞公式消去量詞后的等值式為．A．(A(a)A(b)A(c))(B(a)B(b)B(c))B．(A(a)A(b)A(c))(B(a)B(b)B(c))C．(A(a)A(b)A(c))(B(a)B(b)B(c))D．(A(a)A(b)A(c))(B(a)B(b)B(c))答A16．命題公式的主合取范式是()．A．B．C．D．答C17．下列等價公式成立的為()．A．PPQQB．QPPQC．PQPQD．PPQ解A．PP0QQB．QPP(Q)PQPQC．PQPQD．PP1Q18．命題公式為()．A．矛盾式B．可滿足式C．重言式D．合取范式解是可滿足式．答B(yǎng)19．謂詞公式xA(x)xA(x)是()．A．不可滿足的B．可滿足的C．有效的D．蘊含式答A20．前提條件的有效結論是()．A．PB．PC．QD．Q答D(假言推理)二、填空題1．命題公式的真值是．解答1或T問:命題公式、的真值是什么?2．設P:她生病了,Q:她出差了,R:我同意她不參加學習．則命題”如果她生病或出差了,我就同意她不參加學習”符號化的結果為．答一般地,當語句是由”如果……,那么……”,或”若……,則……”組成,它的符號化用條件聯(lián)結詞．3．含有三個命題變項P,Q,R的命題公式PQ的主析取范式是．解答4．設P(x):x是人,Q(x):x去上課,則命題”有人去上課．”為．答5．設個體域D＝{a,b},那么謂詞公式消去量詞后的等值式為．答注:如果個體域是D＝{1,2},D={a,b,c},或謂詞公式變?yōu)閤(A(x)B(x)),怎么做?6．設個體域D＝{1,2,3},A(x)為”x小于3”,則謂詞公式(x)A(x)的真值為解(x)A(x)A(1)A(2)A(3)1101答1注:若個體域D＝{1,2},A(x)為”x小于3”,則謂詞公式(x)A(x)或:設個體域D＝{1,2,3},A(x)為”x是奇數”,則謂詞公式(x)A(x)的真值是什么?7．謂詞命題公式(x)((A(x)B(x))C(y))中的自由變元為．答y問:公式中的約束變元是什么?判斷:謂詞命題公式(x)((A(x)B(x))C(y))中的自由變元為x,是否正確?為什么?8．謂詞命題公式(x)(P(x)→Q(x)R(x,y))中的約束變元為．答x三、公式翻譯題1．請將語句”今天是天晴”翻譯成命題公式．解設P:今天是天晴．則命題公式為:P．問:”今天不是天晴”的命題公式是什么?2．請將語句”小王去旅游,小李也去旅游．”翻譯成命題公式．解設P:小王去旅游,Q:小李去旅游．則命題公式為:PQ．注:語句中包含”也”、”且”、”但”等連接詞,命題公式要用合取””．3．請將語句”如果明天天下雪,那么我就去滑雪”翻譯成命題公式．解設P:明天天下雪,Q:我去滑雪．則命題公式為:．4．請將語句”她去旅游,僅當她有時間”翻譯成命題公式．解設P:她去旅游,Q:她有時間．則語句表示為．5．請將語句”有人不去工作”翻譯成謂詞公式．解設P(x):x是人,Q(x):x去工作．則語句表示為．6．請將語句”所有人都努力工作．”翻譯成謂詞公式．解設P(x):x是人,Q(x):x努力工作．則語句表示為．注意:命題公式的翻譯還要注意”不可兼或”的表示．例如,教材第164頁的例6”T2次列車5點或6點鐘開．”怎么翻譯成命題公式?這里的”或”為不可兼或．四、判斷說明題(判斷下列各題,并說明理由．)1．命題公式的真值是1．解錯誤．是永假式(教材167頁的否定律)．2．命題公式P(PQ)P為永真式．解正確．(否定律)或由真值表PQPQPQP(PQ)P(PQ)P0011111011011110011011100001可知,該命題公式為永真式．注:如果題目改為該命題公式為永假式,如何判斷并說明理由?3．謂詞公式是永真式．解正確．4．下面的推理是否正確,請給予說明．(1)(x)A(x)B(x)前提引入(2)A(y)B(y)US(1)解錯因為A(x)中的x是約束變元,而B(x)中的x是自由變元,約束變元與自由變元不能混淆．應為:(1)(x)A(x)B(x)前提引入(2)(u)A(u)B(x)T(1)換名規(guī)則(3)(u)(A(u)B(x))T(2)量詞轄域擴張(4)A(y)B(x)ES(3)五、計算題1．求PQR的析取范式、合取范式、主析取范式、主合取范式．解PQRPQR(析取范式、合取范式、主合取范式)(P(QQ)(RR))((PP)Q(RR))((PP)(QQ)R)(補齊命題變項)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(對的分配律)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)解二(利用主析取范式與主合取范式的關系)PQRPQR(析取范式、合取范式、主合取范式)M100m000m001m010m011m101(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)2．求命題公式(PQ)(RQ)的主析取范式、主合取范式．解(析取范式)(對的分配律)(主合取范式)(同上題)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)(根據上題)解二(利用命題公式的真值表)列出命題公式(PQ)(RQ)的真值表如下:PQRPQRQ(PQ)(RQ)小項大項000001PQR001011PQR010111PQR011111PQR100100PQR101111PQR110111PQR111111PQR表中所有小項的析取就是公式的主析取范式,所有大項的合取就是公式的主合取范式,故所求公式的主析取范式為:(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR),主合取范式為:PQR．注:如果題目只是求”析取范式”或”合取范式”,大家就不必再進一步求”主析取范式”或”主合取范式”．例如:求(PQ)R[或(PQ)(RQ),PQR]的合取范式、析取范式．解(析取范式)(合取范式)(析取范式)(合取范式)(析取范式)(合取范式)3．設謂詞公式．(1)試寫出量詞的轄域;(2)指出該公式的自由變元和約束變元．解(1)量詞的轄域為,的轄域為,的轄域為．(2)自由變元為中的y,中的z．約束變元為中的x,中的z,中的y．4．設個體域為D={a1,a2},求謂詞公式y(tǒng)xP(x,y)消去量詞后的等值式．解六、證明題1．試證明(P(QR))PQ與(PQ)等價．證明(蘊含等價)(結合律)(吸收律)(德·摩根律)2．試證明(x)(P(x)R(x))(x)P(x)(x)R(x)．證明(1)(x)(P(x)R(x))P(2)P(a)R(a)