2023年电大离散数学数理逻辑部分期末复习辅导

离散数学数理逻辑部分期末复习辅导一、单项选择题1．设P：我将去打球,Q：我有时间.命题“我将去打球,仅当我有时间”符号化为().A．B．C.Ｄ.复习：P→Ｑ表达的逻辑关系是,Ｐ是Ｑ的充足条件,或Q是P的必要条件.因此“只要P则（就)Ｑ”,“Ｐ仅当Ｑ”,“只有Ｑ才Ｐ”等,都可用复合命题P→Q表达．解由于语句“我有时间”是“我将去打球”的必要条件，所以选项Ｂ是对的的.记住：“P仅当Q”即表达为P→Q．答B问：假如把“我将去打球”改成“我将去市里”、“我将去旅游”等,会符号化吗？2.设命题公式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若题目改为:设命题公式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复习：范式：一个命题公式称为析取（合取)范式，当且仅当它具有形式:Ａ1A2…An(Ａ1A２…An),(n1其中Ａ1,Ａ2,…，An均是由命题变元或其否认所组成的简朴合取(析取）式．对于给定的命题公式，假如有一个等价公式，它仅仅由小项(大项）的析取(合取)组成,则该等价式称为原式的主析取(主合取)范式.求命题公式的主析取（主合取）范式的推演环节:(1)一方面将公式化为析取（合取)范式.①将公式中的联结词化归成,及.（运用双条件等价式PQ(ＰQ)(QP)消去,运用蕴含等价式PQPQ消去)②运用德·摩根律将否认符号直接移到各个命题变元之前．③运用合取对析取(析取对合取）的分派律、结合律将公式归约为析取范式（合取范式)．(2)除去析取（合取）范式中永假（真)的析取（合取）项,并将析取(合取）范式中反复出现的合取(析取)项和相同变元合并.(3)对于不是小项（大项)的合取(析取)式,补入没有出现的命题变元，即通过合取(析取)添加(PＰ)（(PP))式，然后应用合取（析取)对析取（合取)的分派律展开公式.（4)合并相同的小项（大项），并将小项(大项)按编码从小到大的顺序排列，可用∑（∏)表达之．主析取范式与主合取范式的关系:一般地，若命题公式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、５题复习了合取范式和析取范式的概念，大家一定要记住的。假如题目改为求一个变元(Ｐ或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答B7．下列公式成立的为()．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))或者直接推导:Ｐ(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．,答B9．下列公式（)为重言式．Ａ．ＰQPＱB．（Q(PQ))（Q(ＰＱ)）C.（P(QP))(P(PQ)）Ｄ.(P(PQ))Q解A．，B．C.所以，(Ｐ(QP)）（P(PQ))1D.答C说明:（1）假如本题题目改为“下列公式()为永真式”，应当是同样的.(２)上述两题也可以运用公式AB(AB)（ＢA）直接验证.10.设A(x):x是人,Ｂ(ｘ):x是学生，则命题“不是所有人都是学生”可符号化为（).A．（ｘ)（A（ｘ)Ｂ(x）)B．(x）(A(ｘ)B(x）)C．(ｘ)(A(x)B(ｘ)）D．(x)(Ａ(x）B(x))解（x)(A(x)B(x))表达“所有人都是学生”，它的否认即为公式C.答C11.设Ａ(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.设C(ｘ):ｘ是国家级运动员,Ｇ(ｘ):x是健壮的,则命题“没有一个国家级运动员不是健壮的”可符号化为()．A.B.Ｃ.D.答D1３.表达式中的辖域是(）．A．P（x,y)B．Ｐ(x,y)Q(z)C．Ｒ(x,ｙ)D．P(x,y）R(x,y)答Ｂ注意：假如该题改为判断题，即表达式中的辖域是P(x,y）.如何判断并说明理由呢？14．在谓词公式（x)(A(x)→Ｂ(x)Ｃ(x,y)）中，（）．A.x,ｙ都是约束变元B．x，y都是自由变元C.x是约束变元,ｙ是自由变元D.x是自由变元，y是约束变元答C注:假如该题改为填写约束变元或自由变元的填空题，大家也应当掌握．补充题：设个体域为自然数集合,下列公式中是真命题的为()．A．B.Ｃ.D．解由于选项A表达：对任一自然数x存在自然数y满足xｙ=1，这样的y是不存在的选项B表达：对任一自然数x存在自然数ｙ满足ｘ+y=0,这样的ｙ也是不存在的选项Ｃ表达：存在一自然数ｘ对任意自然数y满足xy=ｘ，取x＝０即可,故选项C对的选项Ｄ表达：存在一自然数ｘ对任意自然数y满足ｘ+y=2y,这样的x是不存在的答C１５.设个体域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.合取范式解是可满足式.答B19．谓词公式xA(x）xＡ(ｘ）是（）.Ａ．不可满足的B.可满足的C．有效的D.蕴含式答Ａ20．前提条件的有效结论是()．A．ＰB.ＰC．ＱD．Q答D(假言推理)二、填空题１．命题公式的真值是.解答１或Ｔ问：命题公式、的真值是什么?2.设P:他生病了,Q:他出差了，R:我批准他不参与学习.则命题“假如他生病或出差了,我就批准他不参与学习”符号化的结果为．答一般地，当语句是由“假如……,那么……”，或“若……,则……”组成,它的符号化用条件联结词.３.具有三个命题变项Ｐ,Q，R的命题公式ＰQ的主析取范式是．解答４.设P(x)：x是人，Q(ｘ)：x去上课,则命题“有人去上课．”为.答５.设个体域D={a，b},那么谓词公式消去量词后的等值式为.答注：假如个体域是D＝{1,２｝，D=｛a,b,ｃ｝,或谓词公式变为x(A(x)B(x）),怎么做?６．设个体域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)或:设个体域D＝{1,2，３}，A(x)为“x是奇数”,则谓词公式(ｘ)Ａ(ｘ）的真值是什么?７．谓词命题公式(x）((Ａ(x)Ｂ(x)）Ｃ(y)）中的自由变元为.答y问：公式中的约束变元是什么?判断:谓词命题公式(x)(（A(x)Ｂ(ｘ))Ｃ(ｙ))中的自由变元为x,是否对的？为什么?8.谓词命题公式(x）(Ｐ(x)→Ｑ（x）R(x,y))中的约束变元为．答x三、公式翻译题1．请将语句“今天是天晴”翻译成命题公式.解设P：今天是天晴.则命题公式为:P.问：“今天不是天晴”的命题公式是什么?２.请将语句“小王去旅游,小李也去旅游．”翻译成命题公式．解设Ｐ:小王去旅游,Q:小李去旅游.则命题公式为：PＱ.注:语句中包含“也”、“且”、“但”等连接词,命题公式要用合取“”．３．请将语句“假如明天天下雪，那么我就去滑雪”翻译成命题公式．解设P:明天天下雪，Q:我去滑雪.则命题公式为：．４.请将语句“他去旅游,仅当他有时间”翻译成命题公式．解设P:他去旅游,Ｑ:他有时间.则语句表达为．5．请将语句“有人不去工作”翻译成谓词公式.解设P(x）：x是人，Ｑ（ｘ)：x去工作．则语句表达为.6.请将语句“所有人都努力工作.”翻译成谓词公式．解设P(x):ｘ是人,Q(x）:x努力工作.则语句表达为．注意：命题公式的翻译还要注意“不可兼或”的表达．例如,教材第164页的例6“T2次列车5点或6点钟开．”怎么翻译成命题公式?这里的“或”为不可兼或.四、判断说明题(判断下列各题,并说明理由．）1.命题公式的真值是１.解错误.是永假式(教材１67页的否认律).2.命题公式Ｐ(PQ)P为永真式.解对的．(否认律）或由真值表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是自由变元,约束变元与自由变元不能混淆．应为：(1)(x)Ａ(x)B（ｘ)前提引入(2）(u)Ａ（u)B(ｘ)Ｔ（１）换名规则（3)（u)(A（ｕ)B（x）)T(2)量词辖域扩张(4）Ａ(y)Ｂ（x)EＳ(3)五、计算题1．求PQR的析取范式、合取范式、主析取范式、主合取范式.解ＰＱRPＱR（析取范式、合取范式、主合取范式)(P（ＱQ）(RR))(（PP)Q(RR）)((PP）(QQ)R）(补齐命题变项）(PQR)(PＱR)(ＰＱＲ)(ＰQR)(PQR）(PＱＲ)(PQR）(PQＲ)(PＱR）(PＱＲ)(ＰQR)（ＰQR)（对的分派律）(PQＲ)（ＰQR)(ＰQR)(PＱR)（PQR)(PQR)（PQR)（主析取范式)解二（运用主析取范式与主合取范式的关系）Ｐ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)(主析取范式）（根据上题)解二(运用命题公式的真值表)列出命题公式(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.注：假如题目只是求“析取范式”或“合取范式”，大家就不必再进一步求“主析取范式”或“主合取范式”．例如：求(PＱ）R［或(PQ）(RQ),PＱＲ]的合取范式、析取范式．解（析取范式)（合取范式)(析取范式）(合取范式)（析取范式）（合取范式)3.设谓词公式.(１)试写出量词的辖域;(２）指出该公式的自由变元和约束变元.解（１）量词的辖域为,的辖域为,的辖域为.(2）自由变元为中的y，中的z．约束变元为中的ｘ，中的z,中的ｙ．4.设个体域为Ｄ＝{ａ1,a２},求谓词公式yxP(x，ｙ)消去量词后的等值式．解六、证明题1.试证明(P（ＱR))PQ与(PＱ)等价．证明(蕴含等价）（结合律）(吸取律）(德·摩根律)２.试证明(x)(P(ｘ)R(x)）(ｘ)P（x)（x)R(x)．证明（1)(x)(P(x)R（x))P（２)P(a）R(a)ＥＳ(