吉林大学20192020学年第一学期期末考试《离散数学》大作业参考答案.pdf

《吉林大学20192020学年第一学期期末考试《离散数学》大作业参考答案.pdf》由会员分享，可在线阅读，更多相关《吉林大学20192020学年第一学期期末考试《离散数学》大作业参考答案.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、吉林大学网络教育学院2019-20202019-2020 学年第一学期期末考试离散数学大作业学年第一学期期末考试离散数学大作业学学生生姓姓名名专专业业层层次次年年级级学学号号学学习习中中心心成成绩绩年年月月日日作业完成要求：大作业要求学生手写手写，提供手写文档的清晰扫描图片，并将图片添加到 word文档内，最终wod 文档上传平台，不允许学生提交其他格式文件（如JPG，RAR 等非 word文档格式），如有雷同、抄袭成绩按不及格处理。一、简答题（每小题一、简答题（每小题 7 7 分，共分，共 5656 分）分）1、什么是命题公式的演绎？答：首先定义了消解复杂性的两种范式:最简范式和文字范式,在

2、此基础上采用演绎方法证明了 L 中的可判定性定理,并设计了命题公式的演绎判定算法 P(F).P(F)的时间复杂度为 O(n3),远远小于基于真值表法的 O(2n)和基于策略方案 HAL 的O(n5)。2、什么是子句？请给出一例。答：子句是一组包含一个主词和一个动词的关连字。子句与片语有明显的不同，后者为一组不含主词与动词关系的关连字，如in the morning 或 runningdown the street 或 having grown used to this harassment.3、什么是短语？请给出一例。答：短语是由句法、语义和语用三个层面上能够搭配的语言单位组合起来的没有句调的

3、语言单位，又叫词组。它是大于词而又不成句的语法单位。简单的短语可以充当复杂短语的句法成分，短语加上句调可以成为句子。由语法上能够搭配的词组合起来的没有句调的语言单位例如：粮食/丰收（名/动）（什么/怎么样）4、什么是命题逻辑中的文字？答：检测和消除命题逻辑公式中的冗余文字,是人工智能领域广泛研究的基本问题。针对命题逻辑的子句集中子句的划分,结合冗余子句和冗余文字的概念,将命题逻辑的子句集中的文字分为必需文字、有用文字和无用文字 3 类。5、什么是析取范式？请给出一例。答：在离散数学中，仅由有限个文字构成的合取式称为简单合取式，而由有限个简单合取式构成的析取式称为析取范式。范式存在定理说明了它的

4、存在性：任一命题公式都存在着与之等值的析取范式与合取范式。但它并不是惟一的。主析取范式是惟一的。例如，等为一个文字构成的简单析取式。一个文字既是简单析取式，又是简单合取式。6、什么是关于 P1，P2，Pn的极小项？请给出一例。答：关于 P1,P2,Pn 的极小项（0 k1 k2 ks 2n-1）则称 mk1 mk2 mks 为关于 P1,P2,Pn 的主析取范式，并简记为k1，k2，ks*定理7 7、什么是谓词逻辑中的项？答：谓词逻辑中的项指变项和常项，变项又分为自由变项和约束变项。变项都用 x、y、z 表示（注意是小写），常项用小写 a-w 表示。例如，所有人都会死牛顿会死。令所有人为 x（

5、所有人是无确定的对象，所以用变项来表示），牛顿为 b（牛顿是具体的一个人，用常项表示），会死为 B（大写字母）。符号化 B（x）B（b）。8 8、什么是 Skolem 范式？答;Skolem 标准型是 Skolem 于 1920 年提出的一个使一阶公式标准化的方法，其定义如下：Skolem 标准型是如下任意一种形式的一阶命题：(1)x1x2.xmy1y2.ynUx1x2.xmy1y2.yn(型)；(2)x1x2.xmUx1x2.xm(型)；(3)x1x2.xmUx1x2.xm(型)。其中，U 是不包含量词且连接符仅仅为，的公式。二、综合题（共二、综合题（共 4444 分）分）1、求证若 G 的

6、元数是一个质数，则 G 必是循环群。(7(7 分）分）证明：设 G 的元数为质数 P，任取 G 中 非单位元 a，则（a）是 G 的一个循环子群，设a 的周期为 r，则（a）的元数为r，因此 rIP。但P 是质数，则 a 为非单位元，知 r1，故 r=P，所以 G=（a），即 G 是由 a 生成的循环群。2、令 S=所有正偶数集合。证明：(I+，D)与(S，D)同构。（7 7分）分）证明:对任意 n,I，规定 I 到 S 的映射:g:n,2n+显然此映射是一对一的。与这两个格等价的代数格的*，?运算都是求最大公因和最小公倍。对任 n,n,I,n*n 为其最大公因，记为d.而 2n,2n,S,2

7、n*2n 为 2n 和 2n 的最大公因。12+12121212 为 2d。故 g(n*n)=g(d)=2d=2n*2n=g(n)*g(n).121212同理可证 g(n n)=g(n)g(n)1212即 g 是同态映射，故(I，D)和(S，D)同构。3、证明：4 个元素的格(L，*，)必同构于格(I4，)或者格(S6，D)。（1010分）分）证明:设 4 个元素的格 L=a,a,a,a，L 有限，故必有最大，最小元素，不妨设为1234a,a,则 a,a,a,a 其中，a,a 有两种可能:。41123423(1)a,a(a,a 有关系,，不妨设为如此)则成为链，因此与(I，,)同构。23234

8、(2)a,a 没有,关系，则此格与(S，D)同构。4、试 证 明 群 G的 所 有 内 自 同 构 映 射 在 映 射 的 乘 法 下 作 成 群。（1010 分）分）证明:同一变换可表示成，故此集合非空。对任意属于该集合的，因为对任 1xy,-1-11-1意的 g,G，有(g)=(xgx)=y(xgx)y=(yx)g(yx)=(g)，所以此集合在乘 yxyyx 法运算下是封闭的。显然该集合在乘法运算下满足结合律。该集合内有单位元素，容易 1-1 验证 =在该集合中。5、求证任意无零因子的有限环必是一个体。假定环中不只有一个元素。（1010 分）分）证明:因若 ax=ay,则 a(x-y)=0，无零因子故，若 a,0 必 x-y=0，x=y，由此不难推知，无零因子的有限环中消去律成立。又有限元，所以环中非零元做成乘法群因而是体。