2017华东理工,离散数学作业

离散数学2017作业⼀、命题逻辑部分1．计算真值表、并由此写出主析取与主合取范式(⼀个命题公式的主范式具有唯⼀的表⽰形式，这样可以精减⼀个推理系统，去掉多余的等价的前提。

其唯⼀性借助于⼩项或⼤项的设计，⼀个公式中所⽤到的⼩项或⼤项个数与其真值表中所对应的1或0的个数相对应，不能多也不能少)。

注意：真值表与公式有什么区别？2．设 A 、B 是两个命题公式，证明：a) A B 当且仅当A B 是永真式。

b) A B 的充要条件是A B 且B A 。

等价与蕴涵是对两个公式进⾏⽐较的概念，性质b)说明两者之间的关系，相对⽽⾔蕴涵⽐等价更重要。

与上⾯两个性质相关联的⼀个等价公式是：A B A →B ∧ B →A. 3．证明 P →(Q →R )?Q →(P →R )? ┐R →(Q →┐P ) 4．证明从前提P →Q ，┐(Q ∨R)可演绎出┐P .5．证明R →S 可从前提P →(Q →S)，┐R ∨P 和Q 推出。

├ 6、使⽤推理规则或归结推理，论证推理形式 1) P →Q, R →?Q ,R ∨S, S →?Q ├?P2) ?P ?Q, S →?Q, ?R, R ∨S ├ P⼆、谓词逻辑1、写出谓词的含义、⼀个谓词公式的解释应包含什么内容？a) 谓词是命题中⽤于判断的部分，从语法上看就是陈述句的谓语部分，因⽽并不⼗分关注特定的个体，⽽是将个体作为⼀个变化的量来对待(类似于函数的⾃变量_函数1 1 1 1 1 1 1 11 1 1 1 0 0 1 11 1 1 1 0 0 1 10 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1((p →q ) →(?q →?p )) ∨rq →?p p →q p q r形式)，当这个变化的量指定为⼀个固定的个体时，谓词转变为⼀个命题(类似于函数值)。

所以，谓词的逻辑表达能⼒⽐命题更精细。

b)谓词概念的产⽣源于命题概念，因⽽，对其进⾏研究的基本内容和思路与命题相同，如谓词公式的基本构成⽅式，公式的等价与蕴涵，公式的判定等。

精品文档离散数学习题答案习题一及答案：（ P14-15 ）14、将下列命题符号化：（ 5）李辛与李末是兄弟解：设 p：李辛与李末是兄弟，则命题符号化的结果是p（ 6）王强与刘威都学过法语解：设 p：王强学过法语； q：刘威学过法语；则命题符号化的结果是p q （ 9）只有天下大雨，他才乘班车上班解：设 p：天下大雨； q：他乘班车上班；则命题符号化的结果是q p（ 11）下雪路滑，他迟到了解：设 p：下雪； q：路滑； r ：他迟到了；则命题符号化的结果是( p q)r15、设 p： 2+3=5.q：大熊猫产在中国 .r：太阳从西方升起 .求下列复合命题的真值：（ 4）(p q r )(( p q)r )解： p=1， q=1，r=0 ，(p q r )(110)1，((p q)r )((11)0)(00)1(p q r )(( p q)r ) 1 1119、用真值表判断下列公式的类型：（ 2）( p p)q解：列出公式的真值表，如下所示：p q p qp) ( p p)q( p001111011010100101110001由真值表可以看出公式有 3 个成真赋值，故公式是非重言式的可满足式。

20、求下列公式的成真赋值：精品文档（ 4）( p q)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：( p q)1p0q0q0所以公式的成真赋值有： 01，10， 11。

习题二及答案：（ P38）5、求下列公式的主析取范式，并求成真赋值：（ 2）(p q) (q r )解：原式( p q) q r q r( p p) q r( p q r ) ( p q r )m3m7，此即公式的主析取范式，所以成真赋值为011， 111。

6、求下列公式的主合取范式，并求成假赋值：（ 2）( p q) ( p r )解：原式( pp r ) ( p q r )( p q r )M 4，此即公式的主合取范式，所以成假赋值为 100。

2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（A ）．选择一项：A. 数理逻辑B. 集合论C. 图论D. 谓词逻辑题目2答案已保存满分10.00标记题目题干本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）．选择一项：A. 函数B. 关系的概念及其运算C. 关系的性质与闭包运算D. 几个重要关系题目3答案已保存满分10.00标记题目题干本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲．选择一项：A. 18B. 20C. 19D. 17题目4答案已保存满分10.00标记题目题干本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项：A. 集合恒等式与等价关系的判定B. 图论部分书面作业C. 集合论部分书面作业D. 网上学习问答题目5答案已保存满分10.00标记题目题干课程学习平台左侧第1个版块名称是：（C）．选择一项：A. 课程导学B. 课程公告C. 课程信息D. 使用帮助题目6答案已保存满分10.00标记题目题干课程学习平台右侧第5个版块名称是：（D）．选择一项：A. 典型例题B. 视频课堂C. VOD点播D. 常见问题题目7答案已保存满分10.00标记题目题干“教学活动资料”版块是课程学习平台右侧的第（ A ）个版块．选择一项：A. 6B. 7C. 8D. 9题目8答案已保存满分10.00标记题目题干课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）．选择一项：A. 复习指导B. 视频C. 课件D. 自测请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交．解答：学习计划学习离散数学任务目标：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中，培养自学能力、抽象思维能力和逻辑推理能力，解决实际问题的能力，以提高专业理论水平。

离散数学集合论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。

一、填空题1．设集合{1,2,3},{1,2}==，则P(A)-P(B )= {{3}, {1,2,3}, {1, 3 },A B{2,3}} ，A⨯B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，∈∈R⋂x∈>且=且y<{BA,,}yxAyBx则R的有序对集合为{<2, 2>，<2, 3>，<3, 2>}，<3, 3>．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系R＝}yyx∈=>x∈<,,x,2{ByA那么R－1＝{<6，3>，<8，4>}5．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R具有的性质是反自反性，反对称性．6．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素<c, b>, <d, c>，则新得到的关系就具有对称性．7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．8．设A={1, 2}上的二元关系为R={<x, y>|x∈A，y∈A, x+y =10}，则R的自反闭包为{<1, 1>, <2, 2>} ．9．设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含<1, 1>, <2, 2>, <3, 3> 等元素．10．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是{<1, a >, <2, b >}，或{<1, b >, <2, a >}二、判断说明题（判断下列各题，并说明理由．）1．若集合A = {1，2，3}上的二元关系R={<1, 1>，<2, 2>，<1, 2>}，则(1) R是自反的关系；(2) R是对称的关系．(1) R 不是自反关系，因为没有有序对<3,3>. (2) R 不是对称关系，因为没有有序对<2,1>2．如果R 1和R 2是A 上的自反关系，判断结论：“R -11、R 1∪R 2、R 1∩R 2是自反的” 是否成立？并说明理由．解：成立．因为R 1和R 2是A 上的自反关系，即I A ⊆R 1，I A ⊆R 2。

离散数学集合论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业．要求：学生提交作业有以下三种方式可供选择：1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2. 在线提交word文档3. 自备答题纸张，将答题过程手工书写，并拍照上传．一、填空题1．设集合{1,2,3},{1,2}A B==，则P(A)-P(B )={{1,2},{2,3},{1,3},{1,2,3}} ，A⨯B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，R⋂y∈x=且且<>∈∈{B,,xAyAyBx}则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系R＝}yyx∈=<>∈A2,x,,xy{B那么R－1＝{<6,3>,<8,4>} ．5．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R具有的性质是反自反性．6．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素<c,b>,<d,c>，则新得到的关系就具有对称性．7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．8．设A={1, 2}上的二元关系为R={<x, y>|x∈A，y∈A, x+y =10}，则R的自反闭包为{<1,1>,<2,2>} ．9．设R 是集合A 上的等价关系，且1 , 2 , 3是A 中的元素，则R 中至少包含 <1,1>,<2,2>,<3,3> 等元素．10．设A ={1，2}，B ={a ，b }，C ={3，4，5}，从A 到B 的函数f ={<1, a >, <2, b >}，从B 到C 的函数g ={< a ，4>, < b ，3>}，则Ran(g ︒ f )= {<1,a>,<2,b>}或{<1,b>,<2,a>} ．二、判断说明题（判断下列各题，并说明理由．）1．若集合A = {1，2，3}上的二元关系R ={<1, 1>，<2, 2>，<1, 2>}，则 (1) R 是自反的关系； (2) R 是对称的关系．解：(1) 结论不成立．因为关系R 要成为自反的，其中缺少元素<3, 3>． (2) 结论不成立． 因为关系R 中缺少元素<2, 1>2．设A ={1，2，3}，R ={<1，1>, <2，2>, <1，2> ，<2，1>}，则R 是等价关系．解：(1) 结论不成立．因为关系R 要成为自反的，其中缺少元素<3, 3>． (2) 结论不成立．因为关系R 中缺少元素<2, 1>3．若偏序集<A ，R >的哈斯图如图一所示，则集合A 的最大元为a ，最小元不存在．答：错误，按照定义，图中不存在最大元和最小元。

离散数学习题及解答作业题与解答第⼀章19 (2)、(4) 、(6)21 (1)、(2) 、(3)19、(2)解答: (p→┐p)→┐q 真值表如下:所以公式(p→┐q)→┐q 为可满⾜式19、(4)解答: (p→q)→(┐q→┐p) 真值表如下:所以公式(p→q)→(┐q→┐p)为永真式19、(6)解答: ((p→q)∧(q→r))→(p→r) 真值表如下:所以公式((p→q)∧(q→r))→(p→r)为永真式21、(1)解答: ┐(┐p∧q)∨┐r 真值表如下:所以成假赋值为:01121、(2)解答: (┐q∨r)∧(p→q)真值表如下:所以成假赋值为:010,100,101,11021、(3)解答: (p→q)∧(┐(p∧r)∨p)真值表如下:所以成假赋值为:100,101第⼆章5、(1) (2) (3) 6、(1) (2) (3) 7、(1) (2) 8、(1) (2) (3) 5、求下列公式的主析取范式,并求成真赋值(1) (┐p→q)→(┐q∨p)┐(┐p→q) ∨(┐q∨p)┐(┐(┐p) ∨q) ∨(┐q∨p)(┐p ∧┐q) ∨(┐q∨p)(┐p ∧┐q) ∨(p ∧┐q)∨(p ∧q)所以00，10，11 为成真赋值。

(2) (┐p→q)∧(q∧r)(┐┐p∨q)∧(q∧r)(p∨q)∧(q∧r)(p∧q∧r)∨(q∧r)(p∧q∧r)∨(p∧q∧r)∨(┐p∧q∧r)(p∧q∧r)∨(┐p∧q∧r)m3∨m 7，所以011，111 为成真赋值。

(3) (p∨(q∧r))→(p∨q∨r)┐(p∨(q∧r))∨(p∨q∨r)(┐p∧(┐q∨┐r))∨(p∨q∨r)(┐p∧┐q)∨(┐p∧┐r)∨(p∨q∨r)(┐p∧┐q)∨((┐p∧┐r)∨(p∨q∨r))(┐p∧┐q)∨((┐p∨p∨q∨r)∧(┐r∨p∨q∨r) )(┐p∧┐q)∨(1∧1)(┐p∧┐q)∨11m0∨m1∨m 2∨m3∨m4∨m5∨m 6 ∨m 7，所以000, 001, 010, 011, 100, 101, 110, 111 为成真赋值。

考生答题情况作业名称：2017年秋季网上作业1 出卷人：SA 作业总分：100 通过分数：60 起止时间：2017/12/11 23:43:18 至2017/12/12 0:17:07 学员姓名：学员成绩：85 标准题总分：100 标准题得分：85 详细信息：题号:1 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列语句中是命题的为（）. A、上帝是万能的么？！B、X = 3. C、如果2+3＝23，那么雪是蓝色的. D、敬礼！标准答案:C 学员答案:C 本题得分:5题号:2 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列图形中是平面图的是（）. A、B、C、.D、（彼得森）图标准答案:B 学员答案:B 本题得分:5题号:3 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:若完全图是图的一个子图，则图的色数至少应为（）. A、2 B、3 C、4 D、5 标准答案:B 学员答案:B 本题得分:5题号:4 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:已知集合上偏序关系，其中属于的序偶有（）. A、B、和C、D、标准答案:B 学员答案:B 本题得分:5题号:5 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:集合上的二元关系、，下列选项中唯一正确的是（）. A、如果、都是对称的，那么也是对称的B、如果、都是反对称的，那么也是反对称的C、如果、都是传递的，那么也是传递的D、如果、都是自反的，那么也是自反的标准答案:D 学员答案:D 本题得分:5题号:6 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:对有限连通平面图，则其边数、点数、面数必满足的是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:7 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:一棵树中的任意两点之间相连的通路条数必为（）. A、2 B、3 C、1 D、5 标准答案:C 学员答案:C 本题得分:5题号:8 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:交换群是只须同时满足（）等特征的独异点. A、存在生成元B、存在零元C、存在幺元D、可交换性且中每个元素都有逆元标准答案:D 学员答案:D 本题得分:5题号:9 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:设：我去看电影;：我有时间，将命题“我去看电影，仅当我有时间.” 符号化为（）. A、B、C、D、标准答案:A 学员答案:A 本题得分:5题号:10 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:已知上偏序关系对应的，则的子集的极小元为（）. A、4 B、2 C、1 D、3 标准答案:C 学员答案:B 本题得分:0题号:11 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:与命题公式唯一不等价的选项是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:12 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列各式中，为永假式的是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:13 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:对代数系统，下列四个论述中正确的只有（）. A、若存在零元，则零元是唯一的B、若存在左幺元，则左幺元必是唯一的C、若同时存在左、右幺元，则左、右幺元必相等D、若一个元素存在左逆元，则它一定也存在右逆元标准答案:A 学员答案:D 本题得分:0题号:14 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:集合，为上的一个二元关系，则下列命题中（）为真. A、不是自反的B、不是反自反的C、不是传递的D、不是对称的标准答案:B 学员答案:B 本题得分:5题号:15 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:前提，，，下的结论是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:16 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:集合的幂集的幂集是（）. A、B、C、D、标准答案:D 学员答案:D 本题得分:5题号:17 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:平面图的点数与边数一定满足的关系式为（）. A、B、C、标准答案:C 学员答案:C 本题得分:5题号:18 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:设是非空集合上的二元关系，则的对称闭包（）. A、B、C、D、标准答案:D 学员答案:B 本题得分:0题号:19 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:前提，下的结论是（）. A、B、C、D、标准答案:A 学员答案:A 本题得分:5题号:20 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列图形中不是汉密尔顿图的是（）. A、B、C、D、（彼得森）图E、标准答案:D 学员答案:D 本题得分:5。

欢迎共阅为
，
、完全二部图、完全图
、圈
上的关系中，不具有传递性的是（、
、
、
、
、
、
、
、
的点数
;：我有时间，将命题“我去看电影，仅当我有时间
、
、
、
、
，其中属于的序偶有（）.
D、
标准答案:B
学员答案:C
本题得分:0
对应的，则唯一不是
，则其边数、面数
中每个元素的逆元存在且唯
关于“”运算满足消去律
、群中除了么元外，还存在其他元素也满足
集合上的以下四个关系中，既是对称又是反对称的有（、
、
是由
、
、
、
的对偶图的对偶图同构于
是个集合，表示的幂集，则对代数系统
是实数集合，，则“”在上唯一满足的
集合上有两个自反关系
、
、
，则谓词表达式消去量词后等价于（、
与点数
、、、。