2022年离散数学数理逻辑部分综合考试辅导 .pdf

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

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

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

3、值为 1 的 P，Q，R赋值分别是 ( ) A0, 0, 0 B0, 0, 1 C0, 1, 0 D1, 0, 0 正确答案： D由教材 162页的条件联结词“”运算的真值表可知，当P 取真值时，P取假值，则无论后件Q R取真值还是假值，结果都是真的。因此答案D 是正确的。3下列公式( )为重言式A( P (P Q) QB(B(A B) ( A (A B) C(P( QP)(P(PQ) DABA B正确答案： C 因为：P(PQ)P (PQ) P ( P Q) P (PQ) P (Q P) P ( Q P) P ( Q P)精选学习资料 - - - - - - - - - 名师归纳总结 - -

4、 - - - - -第 1 页，共 6 页2 / 6 所以， C 是重言式4命题公式)(QP的主析取范式是 ( )AQPBQPCQPDQP正确答案： A复习主析取范式的定义：定义 6.6.5 对于给定的命题变元，如果有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式的主析取范式 而小项的定义是：定义 6.6.4 n 个命题变元的合取式， 称为布尔合取 或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次由此可知，答案 C 和 D 是错的。又因为 (PQ ) (P Q) PQ所以，答案 A 是正确的。5设 C(x): x是国家级运动员， G(x): x 是健壮的，则命题

5、“没有一个国家级运动员不是健壮的”可符号化为( )A)()(xGxCxB)()(xGxCxC)()(xGxCxD)()(xGxCx正确答案： D由题设知道， C(x) G(x)表示国家级运动员不是健壮的，而“没有一个”就是“不存在一个”，因此用存在量词的否定，即x，得到公式 D。如果把命题改为 :“不是所有人都是运动员”,你会符号化吗 ?6表达式)(),()(),(zzQyxRyzQyxPx中x的辖域是 ( )AP(x, y) BP(x, y) Q(z) CR(x, y) DP(x, y) R(x, y) 正确答案： B所谓辖域是指 “紧接于量词之后最小的子公式称为量词的辖域”那么看题中紧接于

6、量词x 之后最小的子公式是什么呢？显然是P(x, y) Q(z)，因此，答案B 是正确的。二、填空题1命题公式()PQP的真值是应该填写： 1 因为()PQPP (Q P) 1，所以应该填写： 1。2设 P：他生病了， Q：他出差了 R：我同意他不参加学习 . 则命题“如果他生病或出差了， 我就同意他不参加学习” 符号化的结果为应该填写： (P Q)R 一般地，当语句是由“如果,，那么, ”，或“若 , ，则, ”组成，它的符号化用条件联结词3含有三个命题变项P，Q，R的命题公式 P Q 的主析取范式是应该填写： (P Q R) (P QR) 精选学习资料 - - - - - - - - -

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

8、(A(1) A(2) (B(1) B(2)因为在有限个体域下，消除量词的规则为：设Da1, a2, , , an，则)(.)()()(21naAaAaAxxA)(.)()()(21naAaAaAxxA所以，应该填写： (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请将语句“今天不是天晴”翻

9、译成命题公式解：设 P：今天是天晴；命题公式为：P2请将语句“我去书店，仅当天不下雨”翻译成命题公式解：设 P：我去书店， Q：天不下雨，命题公式为： PQ3请将语句“有人不去工作”翻译成谓词公式解：设 P(x)：x 是人， Q(x)：x 去工作，谓词公式为：( x)(P(x)Q(x)如果语句是“所有人都不去上课”,那么谓词公式应该怎样呢?4请将语句“所有人都努力工作”翻译成谓词公式解：设 P(x)：x 是人， Q(x)：x 努力工作精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页4 / 6 谓词公式为：(x)(P(x) Q(x)

10、四、判断说明题（ 判断下列各题，并说明理由）1命题公式PPQ)(为永假式解：正确因为，由真值表P Q QP ( QP) ( QP) P0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 可知，该命题公式为永假式2下面的推理是否正确，请给予说明(1) xA(x) xB(x) 前提引入(2) 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) 如果把原

11、题中的推理过程改为(1) (x)A(x) B(x) 前提引入(2) A(y) B(y) US (1) 更好些。这个推理的第2 步也是错的，正确的应该是：A(y) B(z)，因为约束变元与自由变元不能混淆。五计算题1（1）求命题公式)()(QPQP的主析取范式、主合取范式；（2）求该命题公式的成假赋值解：（1）)()()()(QPQPQPQP)()()()(QQPPQPQPQP)(QP(主析取范式 ) )()(QPPQQP)()()()(QPQPQPQP精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页5 / 6 )()()(QPQP

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

13、),(),(zxyzQyxP，z量词的辖域为),(zxyQ, y 量词的辖域为),(zyR（2）自由变元为),(),(zxyzQyxP与)( yF中的 y，以及),(zyR中的 z 约束变元为),(),(zxyzQyxP中的 x 与),(zxyQ中的 z，以及),(zyR中的 y六、证明 题1试证明命题公式(P(QR)P Q 与（PQ）等价证：(P(QR)P Q(P (QR)P Q( P QR)P Q( PP Q) (QP Q) ( RP Q) ( P Q) ( P Q) (P QR) P Q（吸收律）(PQ) （摩根律）2试证明xA(x)xB(x)x(A(x) B(x) 分析： 前提：xA(

14、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) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页6 / 6 下面对本课程的考核做一些说明。考核对象：本课程的考核是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的学生考核依据： 以本课程的教学大纲（ 2007年 6月审定） 和指定的参考教材为依据制定的 本课程指定的参考教材是李伟生主编的

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