吉大2019-2020学年第一学期期末考试《离散数学》大作业答案

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

2、真值表法的O(2n)和基于策略方案HAL的O(n5).2、 什么是子句？请给出一例。答：子句是一组包含一个主词和一个动词的关连字。子句与片语有明显的不同，后者为一组不含主词与动词关系的关连字，如 "in the morning" 或 "running down 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、 什么是谓词逻辑中的项？8、 什么是Skolem范式？ 答; Skolem标准型是Skolem于1920年提出的一个使一阶公式标准化的方法，其定义如下：Skolem标准型是如下任意一种形式的一阶命题：(1

5、)x1x2.xmy1y2.ynUx1x2.xmy1y2.yn(型 )；(2)x1x2.xmUx1x2.xm(型)；(3)x1x2.xmUx1x2.xm(型)。其中，U是不包含量词且连接符仅仅为，的公式。二、综合题（共44分）1、求证若G的元数是一个质数，则G必是循环群。 (7分）2、令S=所有正偶数集合。证明：(I+，D)与(S，D)同构。 （7分）证明:对任意n,I，规定I到S的映射:g:n,2n +显然此映射是一对一的。与这两个格等价的代数格的*，?运算都是求最大公因和最小公倍。 对任n,n,I,n*n为其最大公因，记为d.而2n,2n,S,2n*2n为2n和2n的最大公因。12+1212

6、1212为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)。 （10分）证明:设4个元素的格L=a,a,a,a，L有限，故必有最大，最小元素，不妨设为1234a,a,则a,a,a,a其中，a,a有两种可能: 。41123423(1)a,a(a,a有关系,，不妨设为如此)则成为链，因此与(I，,)同构。 23234(2)a,a没有,关系，则此格与(S，D)同构. 4、试证明群G的所有内自同构映射在映射的乘法下作成群。 （10分）证明:同一变换可表示成，故此集合非空。对任意属于该集合的，因为对任1xy,-1-11 -1意的g,G，有(g)= (xgx)=y(xgx)y=(yx) g(yx)= (g)，所以此集合在乘yxyyx法运算下是封闭的。显然该集合在乘法运算下满足结合律。该集合内有单位元素，容易1-1验证 =在该集合中。5、求证任意无零因子的有限环必是一个体。