离散数学作业答案

1、姓名：学号：得分：教师签名：离散数学作业7离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外)安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。要求：将此作业用A4纸打印岀来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

2、一、填空题1 命题公式P(QP)的真值是_1.2设P:他生病了，Q他岀差了.R:我同意他不参加学习.则命题“如果他生病或岀差了，我就同意他不参加学习”符号化的结果为(P?Q)?R命题变项P，Q,R的命题公式P?Q的主析取范式是(P?Q?R)?(P?Q?R).4设P(x):x是人，Q(x):x去上课，则命题“有人去上课可符号化为_(?x)(P(x)TQ(x)5 设个体域D=a,b,那么谓词公式xA(x)yB(y)消去量词后的等值式为(A(a)?A(b)?(B(a)?B(b)6 设个体域A1,2,3，A(x)为“x大于3”，则谓词公式(?x)A(x)的真值为.7 谓词命题公式(?x)(A(x)?B

3、(x)?C(y)中的自由变元为8 谓词命题公式(?x)(P(x)?Q(x)?R(x，y)中的约束变元为X三、公式翻译题1 请将语句“今天是天晴”翻译成命题公式.1.解：设P:今天是天晴；则？P2 请将语句“小王去旅游，小李也去旅游翻译成命题公式.解：设P:小王去旅游，Q:小李去旅游，则P?Q.3 请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式解：设P:明天天下雪。Q:我去滑雪则P?Q4请将语句“他去旅游，仅当他有时间”翻译成命题公式.7.解：设P:他去旅游，Q:他有时间，则P?Q5 请将语句“有人不去工作”翻译成谓词公式.11解：设P(x):x是人，Q(x):x去工作，则谓词公式(?

4、x)(P(x)?nQ(x).6 请将语句“所有人都努力工作.”翻译成谓词公式.13.解：设P(x):x是人，Q(x):x努力工作.则谓词公式为(?x)(P(x)?Q(x)四、判断说明题(判断下列各题，并说明理由.)1 命题公式？P?P的真值是1.错误。命题公式？P?P是典型的恒假公式，其真值是02 .命题公式？P?(P?Q)?P为永真式.2. 解：正确.nPA(PnQ)VP是由rPA(PnQ与P组成的析取式，如果P的值为真，则nPA(P-nQ)VP为真，如果P的值为假，则nP与P-nQ为真，即nPA(P-nQ)为真，也即nPA(P-nQ)VP为真，所以nPA(PnQ)VP是永真式.另种说明：n

5、PA(P-nQ)VP是由nPA(P-nQ与P组成的析取式，只要其中一项为真，则整个公式为真.可以看到，不论P的值为真或为假，nPA(P-nQ)与P总有一个为真，所以nPA(P-nQ)VP是永真式.或用等价演算nPA(P-nQ)VP?T3 谓词公式xP(x)(yG(x,y)xP(x)是永真式.解：正确?xP(x)?(?yG(x，y)?xP(x)?n?xP(x)V(n?yG(x，y)V?xP(x)?(n?xP(x)V?xP(x)V(n?yG(x，y)?1Vn?yG(x，y)?14 下面的推理是否正确，请给予说明.(1)(?x)A(x)?B(x)前提引入A(y)?B(y)US(1)解：错误.因为B(

6、x)不受全称量词？x的约束，不能使用全称指定规则(2)应为A(y)-B(x)，换名时，约束变元与自由变元不能混淆.四计算题1. 求P?Q?R的析取范式，合取范式、主析取范式，主合取范式.3. 解：P-(RVQ?nPV(RVQ)?nPVQVR(析取、合取、主合取范式)?(nPAnQAnR)V(nPAnQAR)V(nPAQAR)V(nPAQAnR)V(PAnQAR)V(PAQAnR)V(PAQAR)(主析取范式)2求命题公式(P?Q)?(R?Q)的主析取范式、主合取范式.3设谓词公式(x)(P(x,y)(z)Q(y,x,z)(y)R(y,z).(1) 试写出量词的辖域；(2) 指岀该公式的自由变元

7、和约束变元.解：(1)?x量词的辖域为(P(x,y)zQ(y,x,z)，?z量词的辖域为Q(y,x,z),?y量词的辖域为R(y,z).(2)自由变元为(P(x,y)zQ(y,x,z)与F(y)中的y,以及R(y,z)中的z约束变元为(P(x,y)zQ(y,x,z)中的x与Q(y,x,z)中的z，以及R(y,z)中的y.4.设个体域为D=a1,a2，求谓词公式?y?xP(x,y)消去量词后的等值式；?y?xp(x,y)?y(?xp(x,y)?y(P(al,y)VP(a2,y)?p(a1,a1)Vp(a2,a1)AP(a1,a2)VP(a2,a2)五、证明题1.试证明(P?(Q?R)?P?Q与？(P?Q)等价.证明：(P?(Q?R)?P?Q?(?P?(Q?R)?P?Q?(?P?Q?R)?P?Q（吸收律）（摩根律）?(?P?P?Q)?(Q?P?Q)?(?R?P?Q)?(?P?Q)?(?P?Q)?(?P?Q?R)?P?Q?(P