离散数学数理逻辑部分综合练习辅导.doc

《离散数学数理逻辑部分综合练习辅导.doc》由会员分享，可在线阅读，更多相关《离散数学数理逻辑部分综合练习辅导.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学数理逻辑部分综合练习辅导本次活动（2008.12.17）是本学期的第三次活动，主要是针对第三单元数理逻辑的重点学习内容进行辅导，方式还是通过讲解一些典型的综合练习题目，帮助大家进一步理解和掌握数理逻辑的基本概念和方法数理逻辑作为离散数学的一部分，主要介绍命题逻辑和谓词逻辑命题逻辑部分的主要内容：命题及其表示法、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴含式、范式、推理理论等；谓词逻辑部分的主要内容：谓词及其表示法、命题函数与量词、谓词公式与翻译、变元约束、谓词演算的等价式与蕴含式、前束范式、谓词演算的推理理论等。本次综合练习主要是复习这一部分的主要概念与计算方法，与前两个单元

2、不同的是，这一部分除了有单项选择题、填空题，判断说明题、计算题、证明题等五种题型外，还要增加一种公式翻译题，这种题型也是期末考试题型的一种，因此希望同学们要熟悉所有的题型，使我们在考试中能够顺利地解答题目，获得好成绩。下面按题型分别讲解。一、单项选择题1设P：我将去市里，Q：我有时间命题“我将去市里，仅当我有时间时”符号化为( )A B C D 正确答案：B因为语句“仅当我有时间时”是“我将去市里”的必要条件，所以答案B是正确的。问：如果把“我将去市里”改成“我将去打球”、“我将去旅游”等，会符号化吗？2设命题公式G：,则使公式G取真值为1的P，Q，R赋值分别是 ( )A0, 0, 0 B0,

3、 0, 1 C0, 1, 0 D1, 0, 0 正确答案：D 由教材162页的条件联结词“”运算的真值表可知，当P取真值时，P取假值，则无论后件QR取真值还是假值，结果都是真的。因此答案D是正确的。3下列公式 ( )为重言式A(P(PQ) Q B(B(AB) (A(AB) C(P(QP)(P(PQ) DABAB正确答案：C 因为： P(PQ) P (PQ) P (PQ) P (P Q) P (Q P) P (Q P) P (Q P) 所以，C是重言式 4命题公式的主析取范式是( )A B C D正确答案：A复习主析取范式的定义：定义6.6.5 对于给定的命题变元，如果有一个等价公式，它仅仅有小

4、项的析取组成，则该等价式称为原式的主析取范式而小项的定义是：定义6.6.4 n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次由此可知，答案C和D是错的。又因为 (P Q ) (P Q) P Q所以，答案A是正确的。5设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( ) A BC D正确答案：D 由题设知道，C(x) G(x)表示国家级运动员不是健壮的，而“没有一个”就是“不存在一个”，因此用存在量词的否定，即$x，得到公式D。 如果把命题改为:“不是所有人都是运动员”,你会符号

5、化吗? 6表达式中的辖域是( ) AP(x, y) BP(x, y)Q(z) CR(x, y) DP(x, y)R(x, y)正确答案：B 所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域”那么看题中紧接于量词x之后最小的子公式是什么呢？显然是P(x, y)Q(z)，因此，答案B是正确的。 二、填空题1命题公式的真值是 应该填写：1因为P(QP) 1，所以应该填写：1。2设P：他生病了，Q：他出差了R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 应该填写：(PQ)R一般地，当语句是由“如果，那么”，或“若，则”组成，它的符号化用条件联结词3含有

6、三个命题变项P，Q，R的命题公式PQ的主析取范式是 应该填写：(PQR) (PQR) 关于主析取范式的定义，在单选题的第4题已经复习了，由小项的定义知道，命题公式PQ中缺少命题变项R与它的否定，因此，应该补上，即PQPQ (RR) (PQ R) (PQR)得到命题公式PQ的主析取范式。4设F(x)：x是鸟，G(x)：x会飞翔则命题“鸟会飞”符号化为 应该填写：(x)(F(x) G(x)注意，一般情况下，谓词逻辑中命题符号化时，使用全称量词，特性谓词后用；使用存在量词$，特性谓词后用5设个体域D=1, 2,那么谓词公式消去量词后的等值式为 应该填写：(A(1) A(2) (B(1) B(2) 因

7、为在有限个体域下，消除量词的规则为：设Da1, a2, , an，则所以，应该填写：(A(1) A(2) (B(1) B(2)如果个体域D=a, b, c, 怎么做?6谓词命题公式(x)(P(x)Q(x)R(x，y)中的约束变元为 应该填写：x 因为约束变元就是受相应的量词约束的变元，在公式(x)(P(x)Q(x)R(x，y)中， x是受全称量词约束的变元所以应该填写：x。问: 公式中的自由变元是什么?三、公式翻译题 1请将语句“今天不是天晴”翻译成命题公式解：设P：今天是天晴； 命题公式为： P 2请将语句“我去书店，仅当天不下雨”翻译成命题公式解：设 P：我去书店，Q：天不下雨， 命题公式

8、为：P Q 3请将语句 “有人不去工作”翻译成谓词公式 解：设P(x)：x是人，Q(x)：x去工作， 谓词公式为： ($x)(P(x) Q(x)如果语句是“所有人都不去上课”,那么谓词公式应该怎样呢? 4请将语句“所有人都努力工作”翻译成谓词公式 解：设P(x)：x是人，Q(x)：x努力工作 谓词公式为： (x)(P(x) Q(x)四、判断说明题（判断下列各题，并说明理由） 1命题公式为永假式 解：正确 因为，由真值表 PQQP( QP)( QP) P00100010101010011100可知，该命题公式为永假式 2下面的推理是否正确，请给予说明(1) xA(x)$ xB(x) 前提引入(2

9、) A(y)B(y) US (1) 解：错推理过程应为：(1) xA(x)$xB(x) 前提引入(2) xA(x)$uB(u) T(1)（换名规则）(3) x$u(A(x)B(u) T(2)(4) x(A(x)B(y) ES(3)(5) A(y)B(y) US (4)如果把原题中的推理过程改为(1) (x)A(x) B(x) 前提引入(2) A(y)B(y) US (1)更好些。这个推理的第2步也是错的，正确的应该是：A(y)B(z)，因为约束变元与自由变元不能混淆。五计算题1（1）求命题公式的主析取范式、主合取范式；（2）求该命题公式的成假赋值解：（1） (主析取范式) (主合取范式)（2）

10、因为命题公式的成真赋值是(1, 0)，所以它的成假赋值是(0, 0)，(0, 1)，(1, 1)2求公式的析取、合取、主析取、主合取范式 解： （析取、合取、主合取范式）(P(QQ)(RR)(PP)Q(RR)(PP)(QQ)R) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) （主析取范式）问: 公式的析取、合取、主析取、主合取范式?3设谓词公式试（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元 解:（1）$x量词的辖域为， z量词的辖域为, y量词的辖域为 （2）自由变元为与中的y，以及中的z 约束变元为中的x与中的z，以及中的y 六、证明题 1试证明命题公

11、式 (P(QR)PQ与（PQ）等价 证：(P(QR)PQ(P(QR)PQ (PQR)PQ (PPQ)(QPQ)(RPQ) (PQ)(PQ)(PQR) PQ （吸收律） (PQ) （摩根律） 2试证明 xA(x)xB(x)x(A(x)B(x)分析：前提：xA(x)xB(x)结论：x(A(x)B(x)证：(1) xA(x)P(2) A(a) US(1) (3) xB(x) P(4) B(a) US(3)(5) A(a) B(a) T(2),(4) I (6) x(A(x)B(x) UG(5)下面对本课程的考核做一些说明。 考核对象：本课程的考核是中央广播电视大学开放教育本科电气信息类计算机科学与技

12、术专业的学生考核依据：以本课程的教学大纲（2007年6月审定）和指定的参考教材为依据制定的本课程指定的参考教材是李伟生主编的、中央广播电视大学出版社出版的离散数学 考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式其中终结性考核采用半开卷、笔试方式，试卷满分100分 半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考 考试时间：90分钟试题类型及结构：单项选择题的分数占15，填空题的分数占15，公式翻译题的分数占12，判断说明题的分数占14，计算题的分数占36；证明题的分数占8单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算单项选择题给出四个备选答案，其一是正确选项填空题只需填写正确结论，不写计算、推论过程或理由逻辑公式翻译题主要是利用命题逻辑和谓词逻辑的基本概念及命题联结词、谓词量词，将一个陈述句翻译成命题公式或谓词公式判断说明题是对给定的一个命题或结论作出对与错的判断，并给出简单的说明计算题主要考核学生的基本运算技能和速度，要求写出化简、计算过程证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程。