《离散数学》第三次在线作业
第三次
第1题
不能再分解的命题称为原子命题，至少包含一个联结
词的命题称为复合命题
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查原子命题和复合命题的基本概念
第2题
命题是能够表达判断（分辩其真假）的陈述语句
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的基本概念
第3题
一个命题可赋予一个值，称为真值
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题真值的基本概念
第4题
复合命题是由连结词、标点符号和原子命题复合构成
的命题
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查复合命题的基本概念
第5题
在条件命题P→Q中，命题P称为P→Q的前件或前
提，命题Q称为P→Q的后件或结论
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查条件命题的基本概念
第6题
给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为T，则称该命题公式为重言式或永真公式
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查永真公式的基本概念
第7题
给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为F，则称该命题公式为矛盾式或永假公式
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查永假公式的基本概念
第8题
任何两个重言式的合取或析取仍然是一个重言式
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查重言式的基本概念
第9题
一个命题称为合取范式，当且仅当它具有如下的形式： A1∧A2∧…∧An，(n≥1)其中A1,A2,…,An都是由命题变元或其否定所组成的析取式
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查合取范式的基本概念
第10题
一个命题称为析取范式，当且仅当它具有如下的形式： A1∨A2∨… ∨An，(n≥1)其中A1,A2,…,An都是由命题变元或其否定所组成的合取式
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查析取范式的基本概念
第11题
一个命题的合取范式或析取范式不是唯一的
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查合取范式或析取范式的不唯一性
第12题
推理理论中的四个推理规则是全称指定规则 (US规则)、全称推广规则 (UG规则)、存在指定规则 (ES规则) 、存在推广规则 (EG规则)
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查推理理论中的四个推理规则
第13题
如果p表示王强是一名大学生，则?p表示王强不是一名大学生
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的运算
第14题
设p：2008年将在北京举办奥运会，q：中国是世界四大文明古国之一，则p∧q：2008年将在北京举办奥运会并且中国是世界四大文明古国之一
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的∧运算
第15题
设p：小王努力学习，q：小王学习成绩优秀，则：p→q：如果小王努力学习，那么他的学习成绩就优秀您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查条件命题的基本概念
第16题
设p：张华是三好学生，q：张华德、智、体全优秀，则：p?q：张华是三好学生当且仅当德、智、体全优秀
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查等价命题的基本概念
第17题
与一个个体相关联的谓词叫做一元谓词
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查一元谓词的基本概念
第18题
一般的，把与n个个体相关联的谓词叫做n元谓词
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查n元谓词的基本概念
第19题
量词分两种：全称量词和存在量词
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查量词的种类
第20题
设A1是合式公式A的子公式，若A1等价B1，并且将A中的A1用B1 替换得到公式B，则A等价B，称该定理为替换规则
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查替换规则的基本概念
第21题
对于任何一命题公式，都存在与其等价的析取范式和合取范式
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题公式的基本概念
第22题
“全体立正”不是命题
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的基本概念
第23题
“禁止吸烟！”不是命题
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的基本概念
第24题
“我正在说谎。”不是命题
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的基本概念
第25题
“你会讲英语吗？”不是命题
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的基本概念
第26题
用A表示“是个大学生”，c表示“张三”，则A(c)：张三是个大学生
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的基本概念
第27题
用A表示“是个教师”，d表示“李四”，则A(d)：李四是教师
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的基本概念
第28题
用B表示“大于”，e代表“5”，f代表“3”，则B(e,f)：5大于3
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的基本概念
第29题
一元谓词表达了客体的“性质”，多元谓词表达了客体之间的“关系”
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查谓词的基本概念
第30题
将命题“小李比小赵高”符号化为L(a,b),其中L(x,y):x 比y高；a:小李；b:小赵
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第31题
符号化“每个自然数都是实数”。引入特性谓词N(x)：x是自然数；R(x)：x是实数。?x(N(x)→R(x))
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第32题
符号化“有的有理数是整数”。引入特性谓词R(x)：x 是有理数；G(x)：x是整数。?x(R(x) ∧G(x))
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第33题
符号化“凡偶数均能被2整除”。F(x)：x是偶数，
G(x)：x能被2整除。?x(F(x)→G(x))
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第34题
符号化“在北京工作的人未必都是北京人”。F(x)：x 在北京工作，G(x)：x是北京人??x(F(x)→G(x))
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第35题
符号化“一切的人都不一样高”。M(x)：x是人，
H(x,y)：x≠y， L(x,y)：x与y一样高，?x?y
(M(x)∧M(y)∧H(x,y)→?L(x,y))
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第36题
用量词、谓词表示命题“所有大学生都热爱祖国”。令S(x)：x是大学生，L(x)：x热爱祖国，
?x(S(x)→L(x))
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第37题
并不是所有的兔子都比所有的乌龟跑得快。设F(x)：x是兔子。G(x)：x是乌龟。H(x,y)：x比y跑得快。该命题符号化为：??x?y(F(x)∧G(y)→H(x,y))
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第38题
符号化命题“2是素数且是偶数”。设 F(x)：x是素数。 G(x)：x是偶数。 a： 2，则命题符号化为
F(a)∧G(a)
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第39题
符号化命题“如果2大于3，则2大于4。”。设
L(x,y)：x大于y， a：2， b：3， c：4，则命题符号化为L(a,b)→L(a,c)
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
第40题
符号化命题“每个学生都要参加考试”。Q(x)：x要参加考试。 P(x)：x是学生。?x(P(x)→Q(x))
您的答案：正确
题目分数：0.5
此题得分：0.5
批注：本题考查命题的符号化
《离散数学》-教案.doc
《离散数学》教案 第一章集合与关系 集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普 遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的 一个分支。 G. Cantor( 康脱 ) 是作为数学分支的集合论的奠基人。1870 年前后，他关于无穷序列的研究导致集合论的系统发展。 1874 年他发表了关于实数集合不能与自然数集合建立 一一对应的有名的证明。 1878 年，他引进了两个集合具有相等的“势”的概念。然 而，朴素集合论中包含着悖论。第一个悖论是布拉利 - 福尔蒂的最大序数悖论。 1901 年罗素发现了有名的罗素悖论。 1932 年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908 年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称 为策梅罗 - 弗兰克尔集合论（ ZF），其中包括 1904 年策梅罗引入的选择公理。另外一种系 统是冯·诺伊曼 - 伯奈斯 - 哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗 - 弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗 - 弗兰克尔集合论的独立性。现在把策梅罗 - 弗兰克尔集合论与选择公理一起称为 ZFC系统。 一、学习目的与要求 本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。 通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系运 算方法，为学习后续章节打下良好基础。 二、知识点 1．集合的基本概念与表示方法； 2．集合的运算； 3．序偶与笛卡尔积； 4．关系及其表示、关系矩阵、关系图； 5．关系的性质，符合关系、逆关系； 6．关系的闭包运算； 7．集合的划分与覆盖、等价关系与等价类；相容关系； 8．序关系、偏序集、哈斯图。
离散数学作业
第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 -
四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 -
第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 -
离散数学作业答案
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
吉林大学离散数学精品试卷
2006-2007学年第2学期 2005级《离散数学2》期末考试试题(A卷) 考试时间：2007年6月班级_______________________ 学号_____________________ 姓名_____________________ 请将答案写在答题纸上，写明题号，不必抄题，字迹工整、清晰； 请在答题纸和试题纸上都写上你的班级，学号和姓名，交卷时请将试题纸、答题纸和草纸一并交上来。 一.综合体(30分，每题3分) 1. 求( 1 3 5 ) (2 5 4 ) (3 4 ) 2. 只有两个生成元的循环群一定是有限循环群吗？并说明理由。 3. 有限循环群中是否一定存在周期与群的元数相等的元素？ 4. 下面哪个是域GF( 16)的真子域 (A)GF (6) ;(B)GF ⑷;(C)GF(8);(D)GF(16) 5. 有限布尔代数的元素个数必定是如下哪个形式？ (A)2n;(B)n 2 ;(C)2 n;(D)4n. 6. 下列代数系统(S, *)中，哪个是群？ (A) S={0,1,3,5},* 是模7的乘法；(B) S是有理数集合，*运算是普通乘法； (C) S是整数集合，*是普通乘法；(D) S={1,3,4,9},* 是模11的乘法。 7. 设A={0,1,2,3,4},运算为模5加法，请给出A的所有子群。 8. n元恒等置换是奇置换还是偶置换？对换呢？ 9?请给出一个有余，但不是分配格的例子。 10.设R是模12的整数环，R={0,1,2,…,11},下面哪一个是极大理想： (A) 6R; (B)2R; (C)4R; (D)8R 二.计算题(25分，每题5分) 1. 计算分圆多项式①24(X). 2. 设(Z,+)为整数加法群，(C*,??)为非零复数的乘法群，令 f: n -i n ,是Z到C*中的同态映射，请求出f的同态核。 3. 在R上求出x+2除2X5+4X3+3X2+1所得的商式和余式。 4. 设G是3次对称群，H是由I和(13)作成的子群，求H得所有右陪集。 5. 设A={0,1,2,3,4,5}, 运算为模6加法，请给出A中所有元素的周期。 三.(10分)证明或者反驳：f(x)=3x 5+5X2+1 四.(10分)设(G, *)是群，(A, *)和(B，*)是它的两个子群，C={a*b|a € A, b€ B}.证明：若*满足交换律，则(C, *)也是(G，*)的子群。 五.(10分)设Z是整数集合，X={(a,b)|a,b € Z},定义X上的二元运算①和。 如下：对任意(ab) ,(a 2,b2)€ X,有： (a1b"e (a2,b2)= (a+a?,b1+b2), (a1bJ O (a2,b2)= (ax a2,b 1X b)，其中，+，x分别是整数加法与乘法。 证明：(X，?，O)是环，如果此环有零因子请给出它们
离散数学(大作业)与答案
一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<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,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)
大学本科高等数学《离散数学》试题及答案
本科高等数学离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
离散数学教案
学习目标: 1.深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、相容关系、(最大)相容类、偏序关系、极大元、极小元、上(下)界、上(下)确界、最大(小)元、全序关系、良序关系等概念; 2.掌握集合的交、并、差、补、对称差的运算及其运算规律; 3.掌握关系的交、并、逆、复合运算、闭包运算及其性质; 4.掌握关系的矩阵表示与关系图; 5.深刻理解关系的自反性、反自反性、对称性、反对称性与传递性,掌握其判别方法; 6.掌握集合的覆盖与划分的联系与区别; 7.掌握偏序关系的判别及其哈斯图的画法;会求偏序集中给定集合的极大元、极小元、上(下)界、上(下)确界、最大(小)元。 主要内容: 1.集合的基本概念及其运算 2.序偶与笛卡尔积 3.关系及其表示 4.关系的性质及其判定方法 5.复合关系与逆关系 6.关系的闭包运算 7.等价关系与相容关系 8.偏序关系 重点: 1.关系的性质及其判别; 2.关系的复合运算及其性质; 3.等价关系与等价类、等价关系与集合的划分的联系; 4.偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点: 1.关系的传递性及其判别; 2.等价关系的特性; 3.偏序关系的哈斯图的画法;偏序集中特异位置元素的求法。 教学手段: 通过多个实例的精讲帮助同学理解重点与难点的内容,并通过大量的练习使同学们巩固与掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题: 习题3、1:4,6;习题3、2:3(8),4(12),6(m);习题3、4:1 (2)、(4),3;习题3、5:1,4;习题3、6:2,5,6;习题3、7:2,5,6;习题3、8:1(1)-(6);习题3、9:3(2)、(4),4(3);习题3、10:1 ,4,5。
离散数学作业(2)
离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
太原理工大学离散数学试题
一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝__{3}__________________; ρ(A) - ρ(B)＝___________________{3},{1,3},{2,3},{123}______ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = _____2^(n^2)_____________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是__自反，对称，传递 ____________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2= {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 16. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公
离散数学教案
学习目标： 1．深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、相容关系、（最大）相容类、偏序关系、极大元、极小元、上（下）界、上（下）确界、最大（小）元、全序关系、良序关系等概念； 2．掌握集合的交、并、差、补、对称差的运算及其运算规律； 3．掌握关系的交、并、逆、复合运算、闭包运算及其性质； 4．掌握关系的矩阵表示和关系图； 5．深刻理解关系的自反性、反自反性、对称性、反对称性和传递性，掌握其判别方法； 6．掌握集合的覆盖与划分的联系与区别； 7．掌握偏序关系的判别及其哈斯图的画法；会求偏序集中给定集合的极大元、极小元、上（下）界、上（下）确界、最大（小）元。 主要内容： 1．集合的基本概念及其运算 2．序偶与笛卡尔积 3．关系及其表示 4．关系的性质及其判定方法 5．复合关系和逆关系 6．关系的闭包运算 7．等价关系与相容关系 8．偏序关系 重点： 1．关系的性质及其判别； 2．关系的复合运算及其性质； 3．等价关系与等价类、等价关系与集合的划分的联系； 4．偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点： 1．关系的传递性及其判别； 2．等价关系的特性； 3．偏序关系的哈斯图的画法；偏序集中特异位置元素的求法。 教学手段： 通过多个实例的精讲帮助同学理解重点和难点的内容，并通过大量的练习使同学们巩固和掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题：
习题 3.1：4，6；习题 3.2：3（8），4（12），6（m ）；习题 3.4：1 （2）、 (4)，3；习题 3.5：1，4；习题 3.6：2，5，6；习题 3.7：2，5，6；习题 3.8：1（1）-（6）；习题3.9：3（2）、（4），4（3）；习题3.10：1 ，4，5。 3.1 集合的基本概念 集合(set)（或称为集）是数学中的一个最基本的概念。所谓集合，就是指具有共同性质的或适合一定条件的事物的全体，组成集合的这些“事物”称为集合的元素。 集合常用大写字母表示，集合的元素常用小写字母表示。若A 是集合，a 是A 的元素，则称a 属于A ，记作a A ∈；若a 不是A 的元素，则称a 不属于A ，记作。若组成集合的元素个数是有限的，则称该集合为有限集(Finite Set)，否则称为无限集(Infinite Set)。 常见集合专用字符的约定： N —自然数集合(非负整数 集) I (或Z )—整数集合(I +，I -) Q —有理数集合(Q +，Q -) R —实数集合(R +，R -) F —分数集合(F +，F -) 脚标+和-是对正、负的区分 C —复数集合 P —素数集合 O —奇数集合 E —偶数集合 幂集 定义 3.1.1 对于每一个集合A ，由A 的所有子集组成的集合，称为集合A 的幂集(Power Set)，记为 ()P A 或2A ．即(){}P A B B A =?。 例如：{,,}A a b c =, (){,{},{},{},{,},{,},{,},{,,}}P A a b c a b b c a c a b c φ=。 定理3.1.1 如果有限集A 有n 个元素，则其幂集()P A 有2n 个元素。 证明 A 的所有由k 个元素组成的子集数为从n 个元素中取k 个的组合数。 (1)(2)(1)! k n n n n n k C k ---+= L 另外，因A φ?，故()P A 的元素个数N 可表示为 1 201n k n k n n n n n k N C C C C C ==++++++=∑L L 又因 0()n n k k n k n k x y C x y -=+= ∑ 令 1x y == 得 02n n k n k C ==∑ 故()P A 的元素个数是2n 。 人们常常给有限集A 的子集编码，用以表示A 的幂集的各个元素。具体方法是： 设12{,,,}n A a a a =L ，则A 子集B 按照含i a 记1、不含i a 记0(1,2,,)i n =L 的规定
离散数学作业
命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
2018国家开放大学离散数学本形考任务答案
离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸，将答题过程手工书写，并拍照上传． 一、填空题 1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15 ． 2．设给定图G(如右由图所示)，则图G的点割集是 { f }，{ e,c} ． 3．设G是一个图，结点集合为V，边集合为E，则 G的结点度数之和等于边数的两倍． 4．无向图G存在欧拉回路，当且仅当G连通且不含奇数度结 点． 5．设G=
8．结点数v与边数e满足e=v - 1 关系的无向连通图就是树． 9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i = 4 ． 二、判断说明题（判断下列各题，并说明理由．） 1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路． 答：错误。应叙述为：“如果图G是无向连通图，且其结点度数均为偶数，则图G存在一条欧拉回路。” 2．如下图所示的图G存在一条欧拉回路． 答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。 3．如下图所示的图G不是欧拉图而是汉密尔顿图．
离散数学作业
离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元.
解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。
3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素.
离散数学作业答案完整版
离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,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的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
大学离散数学期末重点知识点总结(考试专用)
1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={