离散数学数理逻辑部分期末复习题

PAGE\*MERGEFORMAT#/6离散数学数理逻辑部分综合练习辅导一、单项选择 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 设P：我将去打球，Q：我有时间.命题“我将去打球，仅当我有时间时”符号化为().A.QtPB.PtQD.「Pv^Q因为语句“仅当我有时间时”是“我将去打球”的必要条件，所以选项B是正确的.正确答案：B一般地，当语句是由“……，仅当……”组成，它的符号化用条件联结词T.问：如果把“我将去打球”改成“我将去学习”、“我将去旅游”等，会符号化吗？设命题公式G：「Pt(QaR)，则使公式G取真值为1的P，Q，R赋值分别是().A.0,0,0B.0,0,1C.0,1,0D.1,0,0当P为真值为1时，「P的真值为0,无论(QaR)的真值是1还是0,命题公式G的真值为1.所以选项D是正确的.正确答案：D命题公式PvQ的合取范式是().A.PaQB.(PaQ)v(PvQ)C.PvQD.「(「Pa「Q)复习合取范式的定义：定义6.6.2—个命题公式称为合取范式，当且仅当它具有形式：A1AA2A^AAn，(n上1)其中A1,A2，…，A均是由命题变元或其否定所组成的析取式.12n由此可知，选项B和D是错的.又因为PaQ与PvQ不是等价的，选项A是错的.所以，选项C是正确的.正确答案：C命题公式「(PtQ)的析取范式是().A.Pa「QB「PaQC.Pv「Q复习析取范式的定义：定义6.6.3一个命题公式称为析取范式，当且仅当它具有形式:A1VA2V^VA，(n>1)12n其中A1,A2，…，A均是有命题变元或其否定所组成的合取式.12n公式「(PtQ)与Pa「Q是等价的，Pa「Q满足析取范式的定义，所以,选项A是正确的.正确答案：A5•下列公式成立的为().A.―Pa―Q^^PvQB・P—―~P-QC・QtP=PD・「Pa(PvQ)=Q因为：「Pa(PvQ)=Q所以，选项D是正确的.正确答案：D6•下列公式()为重言式.A.「pA「QopvQB・(qt(PvQ))o(「Qa(PvQ))C.(Pt(「QtP))分(「Pt(PtQ))D.(「Pv(PaQ))分Q(Pt(「QtP))o「Pv(QvP),(「Pt(PtQ))oPv(「PvQ)所以，C是重言式，也就是永真式.正确答案：C说明：如果题目改为“下列公式()为永真式”，应该是一样的.7.设A(x)：x是人，B(x)：x是学生，则命题“不是所有人都是学生”可符号化为()•A.(Vx)(A(x)aB(x))B.「(3x)(A(x)aB(x))C.「(Vx)(A(x)tB(x))D.「(3x)(A(x)a「B(x))由题设知道，A(x)tB(x)表示只要是人，就是学生，而“不是所有”应该用全称量词的否定，即「Vx,得到公式C.个人收集整理勿做商业用途正确答案：C8.设C(x)：x是国家级运动员，G(x)：x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为().个人收集整理勿做商业用途A.「Vx(C(x)a「G(x))B.「Vx(C(x)T「G(x))C.「3x(C(x)T「G(x))D.「3x(C(x)a「G(x))由题设知道，C(x)A「G(x)表示国家级运动员不是健壮的，而“没有一个”就是“不存在一个”，因此用存在量词的否定，即「3x,得到公式D.个人收集整正确答案：D9•表达式Vx(P(x,y)vQ(z))a3y(R(x,y)tVzQ(z))中Vx的辖域是().A.P(x,y)B.P(x,y)vQ(z)C.R(x,y)D.P(x,y)AR(x,y)所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域”.那么看题中紧接于量词Vx之后最小的子公式是什么呢？显然是P(x,y)vQ(z),因此，选项B是正确的.个人收集整理勿做商业田途正确答案：B10.在谓词公式(Vx)(A(x)-B(x)vC(x,y))中，().A.x,y都是约束变元B.x,y都是自由变元C.x是约束变元，y都是自由变元D.x是自由变元，y都是约束变元约束变元就是受相应的量词约束的变元.而自由变元就是不受任何量词约束的变元.所以选项C是正确的.正确答案：C注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握.二、填空题命题公式PT(QVP)的真值是.因为PT(QVP)o「Pv(QvP)o1,所以应该填写：1.应该填写：1问：命题公式QTQ、Qv「Q的真值是什么？设P：他生病了，Q：他出差了.R：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为.个人收集整理勿做商一般地，当语句是由“如果……，那么……”，或“若……，则……”组成,它的符号化用条件联结词T.应该填写：(PvQ)tR3•含有三个命题变项P，Q，R的命题公式PaQ的主析取范式是•复习主析取范式的定义：定义6.6.5对于给定的命题变元，如果有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式的主析取范式.个人收集整理勿做商业用途而小项的定义是：定义6.6.4n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次.个人收集整理勿做商业用途由小项的定义知道，命题公式PaQ中缺少命题变项R与它的否定，因此，应该补上，即PaQoPaQa(Rv「R)o(PaQaR)v(PaQa「R)得到命题公式PaQ的主析取范式.应该填写：(PaQaR)v(PaQa「R)4.设个体域D={a,b},那么谓词公式3xA(x)vVyB(y)消去量词后的等值式为.因为在有限个体域下，消除量词的规则为：设D={a「a2,…,a},贝U所以，应该填写：(A(a)vA(b))v(B(a)AB(b))应该填写：(A(a)vA(b))v(B(a)AB(b))如果个体域是D={1,2},D={a,b,c},或谓词公式变为3x(A(x)vB(x)),怎么做？设个体域D={1,2,3},A(x)为“x小于3”，贝V谓词公式(3x)A(x)的真值为•因为Gx)A(x)oA(l)vA(2)vA(3)olvlv0ol应该填写：1谓词命题公式(Vx)((A(x)M(x))vC(y))中的自由变元为.因为自由变元就是不受任何量词约束的变元，在公式(Vx)((A(x)M(x))vC(y))中，y是不受全称量词V约束的变元.所以应该填写：y.个人收集整理勿做商业用途应该填写：y问：公式中的约束变元是什么？三、公式翻译题请将语句“今天是天晴”翻译成命题公式•解：设P：今天是天晴；则命题公式为：P.问：“今天不是天晴”的命题公式是什么？请将语句“小王去旅游，小李也去旅游.”翻译成命题公式•解：设P：小王去旅游，Q：小李去旅游，则命题公式为：PaQ.注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“a”.请将语句“他去旅游，仅当他有时间.”翻译成命题公式•解：设P：他去旅游，Q：他有时间，则命题公式为：PtQ.请将语句“所有人都努力工作.”翻译成谓词公式•解：设P(x)：x是人，Q(x)：x努力工作.谓词公式为：(Vx)(P(x)TQ(x)).四、判断说明题(判断下列各题，并说明理由.)命题公式-PaP的真值是1.解错误.因为-PaP是永假式(教材167页的否定律).命题公式-PA(P^-Q)VP为永真式.解：正确因为，由真值表PQ-P-QPT-Q-PA(P—-Q)VP001111011011100111110001可知，该命题公式为永真式.注：如果题目改为该命题公式为永假式，如何判断并说明理由？下面的推理是否正确，请给予说明.(1)(Vx)A(x)aB(x)前提引入⑵A(y)AB(y)US⑴解：错第2步应为：A(y)AB(x)因为A(x)中的x是约束变元，而B(x)中的x是自由变元，换名时，约束变元与自由变元不能混淆.五•计算题1.求PtQvR的析取范式，合取范式、主析取范式，主合取范式.解P—QyROrPyQyR(析取范式、合取范式、主合取范式)o(「Pa(Q—Q)a(Rv「R)M(PsP)aQa(Rv「R)M(P—P)a(QsQ)aR)个人收(补齐命题变项)o(「PaQaR)v(「PaQa「RM「Pa「QaR)v(「Pa「Qa「R)(a对v的分配律)(主析取范式)v(PaQaR)v(PaQa^R)v(^PaQaR)v(^PaQa^R)v(PaQaR)v(Pa^QaR)v(^PaQaR)v(^Pa^QaR)o(「Pa「Qa「R)v(「Pa「QaR)v(「PaQa「R)v(「PaQaR)v(Pa「QaR)v(PaQa「R)v(PaQaR)注：如果题目只是求“析取范式”或“合取范式”，大家一定不要再进一步求“主析取范式”或“主合取范式”.2•设谓词公式(3x)(P(x,y)T(Vz)Q(y,x,z))a(Vy)R(y,z).试写出量词的辖域；指出该公式的自由变元和约束变元.解(1)量词3x的辖域为P(x,y)tVzQ(y,x,z)，Vz的辖域为Q(y,x,z)，Vy的辖域为R(y,z).(2)自由变元为P(x,y)tVzQ(y,x,z)中的y，R(y,z)中的z.约束变元为P(x,y)tVzQ(y,x,z)中的x，Q(y,x,z)中的z，R(y,z)中的y.3.设个体域为D={a1,a2}，求谓词公式Vy3xP(x,y)消去量词后的等值式.解：Vy3xP(x,y)o(3xP(x,a1))A(3xP(x,a2))o(P(a],a1)vP(a2,a1))A(P(a1,a2)vP(a2,a2))六、证明题1.试证明命题公式（Pt（Q—R）"「P八Q与「（Pv^Q）等价.证：(P^(Qv^R))a^PaQ^(^Pv(Qv^R))a^PaQo((「PvQv「R)八「P)八Qo「PaQ(吸收律)o「(Pv「Q)(摩根律)2.试证明(3x)(P(x)aR(x))^(3x)P(x)a(3x)R(x).分析：前提：(3x)(P(x)aR(x)),结论：(3x)P(x)a(3x)R(x).证明⑴(3x)(P(x)aR(x))P(a)AR(a)P(a)⑷(3x)P(x)R(a)(3x)R(x)(3x)P(x)a(3x)R(x)ES(1)（存在指定规则）T(2)（化简）EG⑶（存在推广规则）T(2)（化简）EG(5)（存在推广规则）T(4)(6)（合取引入）