吉大——离散数学

吉林大学网络教育学院2019-2020学年第一学期期末考试《离散数学》大作业学生姓名专业层次年级学号学习中心成绩年月日作业完成要求：大作业要求学生手写，提供手写文档的清晰扫描图片，并将图片添加到word 文档内，最终wod文档上传平台，不允许学生提交其他格式文件（如JPG，RAR等非word 文档格式），如有雷同、抄袭成绩按不及格处理。

一、简答题（每小题7分，共56分）1、什么是命题公式的演绎？答：首先定义了消解复杂性的两种范式:最简范式和文字范式,在此基础上采用演绎方法证明了L中的可判定性定理,并设计了命题公式的演绎判定算法P(F).P(F)的时间复杂度为O(n3),远远小于基于真值表法的O(2n)和基于策略方案HAL的O(n5)。

2、什么是子句？请给出一例。

答：子句是一组包含一个主词和一个动词的关连字。

子句与片语有明显的不同，后者为一组不含主词与动词关系的关连字，如"in the morning" 或"running down the street" 或"having grown used to this harassment."3、什么是短语？请给出一例。

答：短语是由句法、语义和语用三个层面上能够搭配的语言单位组合起来的没有句调的语言单位，又叫词组。

它是大于词而又不成句的语法单位。

简单的短语可以充当复杂短语的句法成分，短语加上句调可以成为句子。

由语法上能够搭配的词组合起来的没有句调的语言单位例如：粮食//丰收（名//动）（什么//怎么样）4、什么是命题逻辑中的文字？答：检测和消除命题逻辑公式中的冗余文字,是人工智能领域广泛研究的基本问题。

针对命题逻辑的子句集中子句的划分,结合冗余子句和冗余文字的概念,将命题逻辑的子句集中的文字分为必需文字、有用文字和无用文字3类。

5、什么是析取范式？请给出一例。

答：在离散数学中，仅由有限个文字构成的合取式称为简单合取式，而由有限个简单合取式构成的析取式称为析取范式。

一、简要回答下列问题（每小题5分，共30分）1、请给出集合的吸收率。

2、设A={1，2}，请给出A上的所有关系。

答：集合A上的全部关系有2^(2^2)=16种：空关系{}，全关系{<1,1>,<1,2>,<2,1>,<2,2>}{<1,1>}{<2,2>}{<1,2>}{<2,1>}{<1,1>,<1,2>}{<1,1>,<2,1>}{<1,1> ,<2,2>}{<1,2>,<2,1>}{<1,2>,<2,2>}{<2,1>,<2,2>}{<1,1>,<1,2>,<2,1>}{<1,1>,<1,2>,<2,2>}{< 1,1>,<2,1>,<2,2>}{<1,2>,<2,1>,<2,2>}3、什么是子句？请给出一例。

答：子句集S称为是可满足的，如果存在一个个体域和一种解释，使S中的每一个子句均为真，或者使得S的每一个子句中至少有一个文字为真。

否则, 称子句集S是不可满足的4、什么是前束范式？答：前束范式亦称前束式，一种谓词演算公式。

指其一切量词都未被否定地处于公式的最前端且其辖域都延伸至公式的末端的谓词演算公式。

设Q∈{∃，ᗄ}，一个公式α是前束范式，当且仅当存在一个不含量词的公式β，使得α=(Q₁x₁)(Q₂x₂)…(Qₑxₑ)β.5、什么是谓词逻辑中的项？答：谓词逻辑中的项指变项和常项，变项又分为自由变项和约束变项。

6、什么是命题公式的演绎？答：用A'表示非A,则(A+B)'=A'B',(AB)'=A'+B'.二、设A是m元集合，B是n元集合。

吉大离散数学试题及答案一、选择题1. 以下哪个选项不是离散数学中的基本概念？A. 集合B. 函数C. 微积分D. 关系答案：C2. 在集合论中，以下哪个操作不是基本的集合运算？A. 并集B. 交集C. 差集D. 微分答案：D3. 逻辑运算中的“与”操作，其结果为真当且仅当两个操作数都为真。

这个操作的符号是：A. ∧B. ∨C. ¬D. →答案：A二、填空题1. 一个集合的幂集包含该集合的所有_________。

答案：子集2. 如果函数f: A → B 是单射的，那么对于 A 中的任意两个不同的元素 a1 和 a2，f(a1) 和 f(a2) 在 B 中是_________的。

答案：不同的三、简答题1. 简述什么是图论中的“图”？答案：图是由顶点（或称为节点）和连接这些顶点的边组成的数学结构。

图可以是有向的或无向的，边可以是有权重的或无权重的。

2. 什么是逻辑中的“真值表”？答案：真值表是一种列出逻辑表达式中所有可能的真值组合及其结果的表格。

它用于展示逻辑表达式在不同输入值下的结果。

四、计算题1. 给定集合 A = {1, 2, 3} 和 B = {2, 3, 4}，请找出 A 和 B 的交集。

答案：A ∩ B = {2, 3}2. 假设有一个函数 f(x) = x^2，计算 f(-3) 和 f(3) 的值。

答案：f(-3) = 9，f(3) = 9五、论述题1. 论述离散数学在计算机科学中的应用。

答案：离散数学是计算机科学的基础，它提供了处理计算机科学问题所需的数学工具和理论。

例如，集合论是数据库理论的基础；图论在网络和算法设计中有着广泛应用；逻辑和布尔代数是计算机硬件设计和编程语言的基础。

2. 讨论命题逻辑和谓词逻辑的区别。

答案：命题逻辑关注简单命题及其逻辑关系，而谓词逻辑则引入了量词和变量，允许表达更复杂的逻辑关系。

命题逻辑使用逻辑连接词（如与、或、非等）来构建表达式，而谓词逻辑则使用量词（如全称量词∀和存在量词∃）来描述涉及个体的命题。

一些数学课程视频的链接1.1《数学分析》：复旦，陈纪修，214集，151小时/playlist_show/id_3559597_ascending_1_mode_pic_page_1.html /playlist_show/id_3657450.html1.2《数学分析》：中科大，史济怀，203集，149小时/playlist_show/id_3941515_ascending_1_mode_pic_page_1.html 1.3《微积分》：清华，58集，47小时/playlist_show/id_1543503_ascending_1_mode_pic_page_3.html 2.1《高等代数》：清华，18集，14小时/playlist_show/id_1602163.html2.2《高等代数》：厦大，杜妮，133集，93小时/playlist_show/id_4364793_ascending_1_mode_pic_page_1.html 2.3《线性代数》：中科大，李尚志，25集，35小时/playlist_show/id_3979326.html3.1《高等代数与解析几何》：南开，100集，67小时/playlist_show/id_5281512.html4.1《概率论与数理统计》：中科大，缪柏其，33集，35小时/playlist_show/id_5270389.html4.2《统计学》：加州伯克利分电视棒校，43集，35小时/playlist_show/id_3769636.html5.1《微分方程》：麻省理工，33集，网易公开课/special/opencourse/equations.html/playlist_show/id_4025396_ascending_1_mode_pic_page_1.html 5.3《常微分方程》：北师大，袁荣，61集，47小时/playlist_show/id_3950648_ascending_1_mode_pic_page_1.html 5.4《偏微分方程》：台湾国立交大，39集，48小时/playlist_show/id_3764702.html6.1《实变函数》：台湾国立交大，吴培元，35集，40小时/playlist_show/id_5609383.html7.1《复变函数》：台湾国立交大，吴培元，29集，33小时/playlist_show/id_4088706.html7.2《复变函数》钟玉泉三版：北师大，袁荣，61集，47小时/playlist_show/id_4253743_ascending_1_mode_pic_page_1.html 8.1《泛函分析》：台湾国立交大，吴培元，30集，30小时/playlist_show/id_15443160_ascending_1_mode_pic_page_1.html 9.1《抽象代数》：北大，石生明，61集，41小时/playlist_show/id_3250211_ascending_1_mode_pic_page_1.html 9.2《近世代数》张禾瑞：北师大，袁荣，60集，44小时/playlist_show/id_4102229.html10.1《点集拓扑》：河北师大，王彦英，28集，22小时/playlist_show/id_3250377.html11.1《微分几何与广义相对论教程》：北师大，梁灿彬，118集，107小时/playlist_show/id_3250546.html12.1《初等数论》：北师大，袁荣，51集/playlist/index_1958524.html/playlist_show/id_3250322.html14.1《数理逻辑》：中科院，陆钟万，29集，28小时/playlist_show/id_2901699.html15.1《图论》：北师大，袁荣，60集，42小时/playlist_show/id_4236391_ascending_1_mode_pic_page_1.html 16.1《离散数学》：吉大，69集，50小时/playlist_show/id_2026088.html16.2《离散数学》：中南，24集，17小时/playlist_show/id_2741559.html16.3《离散数学》：上交，35集，38小时/playlist_show/id_1593746_ascending_1_mode_pic_page_1.html 17.1《MATLAB基础视频》：14集，6小时/playlist_show/id_4993577.html17.2《MATLAB论坛视频》：67集，26小时/playlist_show/id_1710770_ascending_1_mode_pic_page_1.html 18.1《小波分析》：28集，29小时/playlist_show/id_5475022.html19.1《最优化-凸分析》：斯坦福大学，38集，47小时/playlist_show/id_5434039.html。

第二章命题逻辑§2.2 主要解题方法2.2.1 证明命题公式恒真或恒假主要有如下方法：方法一.真值表方法。

即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。

真值表法比较烦琐，但只要认真仔细，不会出错。

例2.2.1 说明 G= (P Q R)(P Q)(P R)是恒真、恒假还是可满足。

解：该公式的真值表如下：P Q R P QR PQ(P QR)(P Q)P R G0 0 0 1 1 1 1 10 0 1 1 1 1 1 10 1 0 1 1 1 1 10 1 1 1 1 1 1 11 0 0 1 0 0 1 11 0 1 1 0 0 1 11 1 0 0 1 0 0 11 1 1 1 1 1 1 1表2.2.1由于表2.2.1中对应公式G所在列的每一取值全为1，故G恒真。

方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。

例2.2.2 说明 G= ((P R) R) ( (Q P) P)是恒真、恒假还是可满足。

解：由(P R) R=P R R=1，以及(Q P) P= （Q P） P = Q PP=0知，((P R) R) ( (Q P) P)=0，故G恒假。

方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。

方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G恒假，若最终结果有1，有0，则是可满足的。

3.6从1到300的整数中（1）同时能被3、5、和7这3个数整除的数有A个。

（2）不能被3、5，也不能被7整除的数有B个。

（3）可以被3整除，但不能被5和7整除的数有C个。

（4）可被3或5整除，但不能被7整除的数有D个。

（5）只能被3、5和7之中的一个数整除的数有E个。

供选择的答案A、B、C、D、E：①2；②6；③56；④68；⑤80；⑥102；⑦120；⑧124；⑨138；⑩162。

解：设1到300之间的整数构成全集E，A、B、C分别表示其中可被3、5或7整除的数的集合。

文氏图如下图：在A∩B∩C中的数一定可以被3、5和7的最小公倍数105整除，即∣A∩B∩C∣=⎣300/105⎦=2，同样可得∣A∩B∣=⎣300/15⎦=20，∣A∩C∣=⎣300/21⎦=14，∣B∩C∣=⎣300/35⎦=8.然后将20-2=18，14-2=12，8-2=6分别填入邻近的3块区域.再计算∣A∣=⎣300/3⎦=100，∣B∣=⎣300/5⎦=60，∣C∣=⎣300/7⎦=42.所以∣A∪B∪C∣=162.所以本题的答案是：A=①2；B=⑨138；C=④68；D=⑦120；E=⑧124.3.10列元素法表示下列集合。

（1）A={ x | x ∈N ∧x2 ≤7}.（2）A={ x | x ∈N ∧|3-x|<3}.（3）A={ x | x ∈R ∧(x+1)2≤0}.（4）A={<x,y> |x,y∈N∧x+y≤4}.解：(1) A={0，1，2}.(2) A={1,2,3,4,5}.(3) A={-1}.(4) A={<0,0>,<0,1>,<0,2>,<0,3>,<0,4>,<1,0>,<2,0>,<3,0>,<4,0>,<1,1>,<1,2>,<1,3>,<2,1>,<3,1>,<2,2>}.3.11求使得以下集合等式成立时，a,b,c,d应满足的条件。