文档库 最新最全的文档下载
当前位置:文档库 › 离散数学作业5_集合与关系_关系的闭包

离散数学作业5_集合与关系_关系的闭包

离散数学作业5_集合与关系_关系的闭包

离散数学作业5 ——关系的闭包运算

1. 若X上的关系R1?R2,则

⑴ r(R1)?r(R2)

⑵ s(R1)?s(R2)

⑶ t(R1)?t(R2)

2. R是X上的关系,

⑴若R是自反的,则 s(R)和t(R)也是自反的。

⑵若R是对称的,则 r(R)和t(R)也是对称的。

⑶若R是传递的,则 r(R)也是传递的。

3. 设R是X上的关系,则

⑴ rs(R)=sr(R);⑵ rt(R)=tr(R);⑶st(R)?ts(R)。4.设R和S都是A上的关系,证明下列各式。

⑴ r(R∪S)=r(R)∪r(S)

⑵ t(R)∪t(S) ? t(R∪S)

⑶ s(R∪S)=s(R)∪s(S)

⑷用反例证明 t(R∪S)≠t(R)∪t(S)

5.⑴用反例证明语句“如果R是传递的,那么s(R)也是传递的”为假。

⑵举一实例证明即使R是一有限集,st(R)和ts(R)也可以不相等。

离散数学形成性考核作业4题目与答案

离散数学形成性考核作业4作业与答案 离散数学综合练习书面作业 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档. 3. 自备答题纸张,将答题过程手工书写,并拍照上传. 一、公式翻译题 1.请将语句“小王去上课,小李也去上课.”翻译成命题公式. 设P:小王去上课 Q:小李去上课 则:命题公式P∧Q 2.请将语句“他去旅游,仅当他有时间.”翻译成命题公式. 设P:他去旅游 Q:他有时间 则命题公式为P→Q

3.请将语句“有人不去工作”翻译成谓词公式. 设A(x):x是人 B(x):去工作 则谓词公式为?x(A(x)∧-B(x)) 4.请将语句“所有人都努力学习.”翻译成谓词公式. 设A(x): x是人 B(x):努力学习 则谓词公式为?x(A(x)∧B(x)) 二、计算题 1.设A={{1},{2},1,2},B={1,2,{1,2}},试计算 (1)(A-B);(2)(A∩B);(3)A×B. 解: (1)(A-B)={{1},{2}} (2)(A∩B)={1,2} (3)A×B= {<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1, 2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>} 2.设A={1,2,3,4,5},R={|x∈A,y∈A且x+y≤4},S={|x∈A,y∈A且x+y<0},试求R,S,R?S,S?R,R-1,S-1,r(S),s(R). 解: R={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>} S=空集 R?S=空集 S?R =空集 R-1={<1,1>,<2,1>,<3,1>,<1,2>,<2,2>,<1,3>} S-1=空集 r(S) ={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R) ={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>} 3.设A={1, 2, 3, 4, 5, 6, 7, 8},R是A上的整除关系,B={2, 4, 6}. (1) 写出关系R的表示式;(2) 画出关系R的哈斯图; (3) 求出集合B的最大元、最小元.

离散数学作业答案

离散数学作业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 去工作,

应用离散数学-集合与关系

集合与关系《应用离散数学》 第3章 21世纪高等教育计算机规划教材

目录 3.1 集合及其运算 3.2 二元关系及其运算3.3 二元关系的性质与闭包3.4 等价关系与划分 3.5 偏序关系与拓扑排序3.6 函 数 3.7 集合的等势与基数3.8 多元关系及其应用

集合是现代数学中最重要的基本概念之一,数学概念的建立由于使用了集合而变得完善并且统一起来。集合论已成为现代各个数学分支的基础,同时还渗透到各个科学技术领域,成为不可缺少的数学工具和表达语言。对于计算机科学工作者来说,集合论也是必备的基础知识,它在开关理论、形式语言、编译原理等领域中有着广泛的应用。 本章首先介绍集合及其运算,然后介绍二元关系及其关系矩阵和关系图,二元关系的运算、二元关系的性质、二元关系的闭包,等价关系与划分、函数,最后介绍多元关系及其在数据库中的应用等。

3.1 集合及其运算 3.1.1 基本概念 集合是数学中最基本的概念之一,如同几何中的点、线、面等概念一样,是不能用其他概念精确定义的原始概念。集合是什么呢?直观地说,把一些东西汇集到一起组成一个整体就叫做集合,而这些东西就是这个集合的元素或叫成员。 例3.1 (1)一个班级里的全体学生构成一个集合。 (2)平面上的所有点构成一个集合。 (3)方程 的实数解构成一个集合。 (4)自然数的全体(包含0)构成一个集合,用N表示。 (5)整数的全体构成一个集合,用Z表示。 (6)有理数的全体构成一个集合,用Q表示。 (7)实数的全体构成一个集合,用R表示。

(8)复数的全体构成一个集合,用C表示。 (9)正整数集合Z+,正有理数集合Q+,正实数集合R+。(10)非零整数集合Z*,非零有理数集合Q*,非零实数集合R*。(11)所有n 阶(n≥2)实矩阵构成一个集合,用M n(R)表示,即

(完整版)离散数学作业答案一

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外) 安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了,Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了,我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P,Q,R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人,Q(x): x去上课,则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3},A(x)为“x大于3”,则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x,y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式

离散数学第5章作业答案

第5章作业答案 1. 用枚举法给出下列集合 解(2) {-3,2} (4) {5,6,7,8,9,10,11,12,13,14,15} 2. 用抽象法说明下列集合 解(6) {x|?k (k∈I∧x = 2k + 1)} 6.写出下列集合的幂集 解(2) ρ({1, ?}) = {?, {1}, {?}, {1, ?}} (4) ρ({?, {a}, {?}}) = {?, {?}, {{a}}, {{?}}, {?, {a}}, {?, {?}}, {{a}, {?}}, {?, {a}, {?}}} 9. 证明:如果B?C,则ρ(B) ?ρ(C)。 证明任取x∈ρ(B),则x?B,又因为B?C,所以x?C,x∈ρ(C)。 10.设U = {1, 2, 3, 4, 5},A = {1, 4},B = {1, 2, 5}和C = {2, 4},试写出下列集合。解(8) ρ(A) -ρ(C) = {?, {1}, {4}, {1, 4}} - {?, {2}, {4}, {2, 4}} = {{1}, {1, 4}} 11.证明下列恒等式 (7) (A-B) -C = (A-C) - (B-C) 证法1 对于任意x, x∈ (A-C) - (B-C) ?x∈A-C ∧x? B-C ?x∈A∧x?C ∧?(x∈ B∧x?C) ? x∈A∧x?C ∧ ( x?B ∨ x∈C) ?( x∈A∧x?C ∧ x?B)∨( x∈A∧x?C ∧ x∈C) ? x∈A∧x?C ∧ x?B ? x∈A∧ x?B∧x?C ? x∈A-B ∧ x?C ? x∈(A-B) -C 证法2 (A-C) - (B-C) = A?~C?~( B?~C) = A?~C? (~ B? C) = ( A?~C?~ B) ?( A?~C? C) =(A?~C?~ B) ?? = A?~B?~ C = (A-B) ?~ C = (A-B) -C 12.设A, B, C是集合,下列等式成立的条件是什么? (3) (A-B ) ? (A-C) = ? 解因为(A- B) ?( A-C) = (A?~B) ? ( A?~C) = A? (~B?~C) = A?~(B ?C) = A- (B ?C) 所以(A-B)?(A-C) = ?iff A- (B?C) = ?iff A? (B?C)

电大 离散数学作业7答案

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值是 1或T . 2.设P :他生病了,Q :他出差了.R :我同意他不参加学习. 则命题“如 果他生病或出差了,我就同意他不参加学习”符号化的结果为 (P ∨Q )→R . 3.含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) . 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 ) 的真值为 0(F) . 7.谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y . 8.谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ,y ))中的约束变元为 x . 三、公式翻译题 1.请将语句“今天是天晴”翻译成命题公式. 设P :今天是晴天。 姓 名: 学 号: 得 分: 教师签名:

离散数学作业答案完整版

离散数学作业答案 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={, , , },则R具有的性质是没有任何性质. 6.设集合A={a, b, c, d},A上的二元关系R={, , , },若在R中再增加两个元素{,} ,则新得到的关系就具有对 称性. 7.如果R1和R2是A上的自反关系,则R1∪R2,R1∩R2,R1-R2中自反关系有 2 个. 8.设A={1, 2}上的二元关系为R={|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是ECNU二年级的学生集合,B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求: (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中,能被3或5整除,但不能被15整除的正整数共有多少个? 能被5整除的有40个, 能被15整除的有13个, ∴能被3或5整除,但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗? (1)2是正数吗? (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了,那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r),其中p、q、r为如下命题: p:你得流感了 q:你错过了最后的考试

3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语,其中C(x)表示x有电脑,F(x,y) 表示x和y是同 班同学,个体域是学校全体学生的集合。 解: 学校的全体学生要么自己有电脑,要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解: ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章

离散数学 作业及答案

2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解:掌握两点:(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解:掌握两点:(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数,因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数,证明:6|n(n+1)(2n+1) 证明:用数学归纳法: 归纳基础:当n=1时,n(n+1)(2n+1)=1*2*3=6,6|6 归纳假设:假设当n=m时,6|m(m+1)(2m+1) 归纳推导:当n=m+1时, n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时,命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数,则(A ):

离散数学作业标准答案

离散数学作业 一、选择题 1、下列语句中哪个是真命题(C )。 A .我正在说谎。 B .如果1+2=3,那么雪是黑色的。 C .如果1+2=5,那么雪是白色的。 D .严禁吸烟! 2、设命题公式))((r q p p G →∧→=,则G 是( C )。 A. 恒假的 B. 恒真的 C. 可满足的 D. 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( C )。 A .是自由变元但不是约束变元 B .既不是自由变元又不是约束变元 C .既是自由变元又是约束变元 D .是约束变元但不是自由变元 4、设A={1,2,3},则下列关系R 不是等价关系的是(C ) A .R={<1,1>,<2,2>,<3,3>} B .R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>} C .R={<1,1>,<2,2>,<3,3>,<1,4>} D .R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>, <3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R ,σ(x )= -x 2+2x-1,则σ是( D )。 A .单射而非满射 B .满射而非单射 C .双射 D .既不是单射,也不是满射 6、下列二元运算在所给的集合上不封闭的是( D ) A. S={2x-1|x ∈Z +},S 关于普通的乘法运算 B. S={0,1},S 关于普通的乘法运算 C. 整数集合Z 和普通的减法运算 D. S={x | x=2n ,n ∈Z +},S 关于普通的加法运算 7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D ) b a b b a a b a * b b b a a a b a * a a b a a a b a * a b b b a a b a * A B C D 8、下列图中是欧拉图的是( A )。

离散数学作业7答案(数理逻辑部分)

离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,并在07任务界面下方点击“保存”和“交卷”按钮,以便教师评分.作业应手工书写答题,字迹工整,解答题要有解答过程,完成后上交任课教师(不收电子稿). 一、填空题 1.命题公式() →∨的真值是 1 . P Q P 2.设P:他生病了,Q:他出差了.R:我同意他不参加学习.则命题“如果他生病或出差了,我就同意他不参加学习”符号化的结果为P∨Q→R . 3.含有三个命题变项P,Q,R的命题公式P∧Q的主析取范式是(P∧Q∧┐R)∨(P∧Q∧R) . 4.设P(x):x是人,Q(x):x去上课,则命题“有人去上课.”可符号化为?x ( P ( x) ∧Q ( x)). 5.设个体域D={a, b},那么谓词公式) xA? ∨ x ?消去量词后的等值式为 yB ( ) (y (A(a)∨A(b))∨(B(a) ∧B(b)). 6.设个体域D={1, 2, 3},A(x)为“x大于3”,则谓词公式(?x)A(x) 的真值为0 . 7.谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y .8.谓词命题公式(?x)(P(x) →Q(x) ∨R(x,y))中的约束变元为x . 三、公式翻译题 1.请将语句“今天是天晴”翻译成命题公式. 解:

国开放大学离散数学本离散数学作业答案

国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021

离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第一次作业,大家要认真及时地完成集合论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档 3. 自备答题纸张,将答题过程手工书写,并拍照上传. 一、填空题

1.设集合{1,2,3},{1,2} ==,则P(A)-P(B )= {{1,2},{2,3},{1,3}, A B {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>,<>,<> } .4.设集合A={1, 2, 3, 4 },B={6, 8, 12},A到B的二元关系 R=} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R-1= {< 6,3>,<8,4> } . 5.设集合A={a, b, c, d},A上的二元关系R={, , , },则R具有的性质是反自反性. 6.设集合A={a, b, c, d},A上的二元关系R={, , , },若在R中再增加两个元素 , ,则新得到的关系就具有对称性. 7.如果R1和R2是A上的自反关系,则R1∪R2,R1∩R2,R1-R2中自反关系有2 个.

离散数学 作业 3~4 答案

『离散数学』课程 作业3: P64:3 某班有25个学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。 解:直接使用容斥原理。我们做如下设定: A:会打篮球的学生;B:会打排球的学生;C:会打网球的学生; 根据题意:|E|=25,|A|=14,|B|=12,|C|=6,|A∩B|=6,|A∩C|=5,|B∩C|=4,|A∩B∩C|=2 由容斥原理: |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|=14+12+6-6-5-4+2=19 —————————————————————————————————————— 但相当一部分同学没有直接使用容斥原理, 而是画了文氏图。 使用文氏图的方法,会发现此题存在问题: 表示只会打网球的同学是-1人, 此种情况与实际不符。 这可能是作者的疏忽,该教材第一版中, “已知6个会打网球的人中有4人会打排球。” 一句是写作 “已知6个会打网球的人都会打篮球或排球。” 则用容斥原理或文氏图,都可以得到5的结果。 A:会打篮球的学生;B:会打排球的学生;C:会打网球的学生; 根据题意:|E|=25,|A|=14,|B|=12,|C|=6,|A∩B|=6,|A∩C|=5,|A∩B∩C|=2 因为“会打网球的人都会打篮球或排球。” 所以C =(A∩C)∪(B∩C) 由容斥原理: |C|=|(A∩C)∪(B∩C)| = |(A∩C)|+|(B∩C)|-|(A∩C)∩(B∩C)| 可知|(B∩C)|= |C|-|(A∩C)|+|(A∩C)∩(B∩C)| = 6-5+2=3 |A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C| =14+12+6-6-5-3+2=20

离散数学作业答案

离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外) 安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出 掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第一次作业,大家要认真及时地完成集合论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有 解答过程,要求本学期第11周末前完成并上交任课教师(不收电子稿)。并在 03任务界面下方点击“保存”和“交卷”按钮,完成并上交任课教师。 一、填空题 1.设集合{1,2,3},{1,2} ==,则P(A)-P(B )= {{3},{1,3},{2,3}, A B {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={, , , },则R具有的性质是没有任何性质. 6.设集合A={a, b, c, d},A上的二元关系R={, , , },若在R中再增加两个元素{,} ,则新得到的关系就具 有对称性. 7.如果R1和R2是A上的自反关系,则R1∪R2,R1∩R2,R1-R2中自反关系有 2 个. 8.设A={1, 2}上的二元关系为R={|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的双射函数是

北京大学2017秋课件作业【离散数学】及答案

2017秋课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1设集合A={{2,3,4},5,1},下面命题为真是(选择题)[A] A.1∈A;B.2∈A;C.3∈A;D.{3,2,1}?A。 1-2A,B,C为任意集合,则他们的共同子集是(选择题)[D] A.C;B.A;C.B;D.?。 1-3设S={N,Z,Q,R},判断下列命题是否正确(是非题) (1)N?Q,Q∈S,则N?S,[错](2)-1∈Z,Z∈S,则-1∈S。[错] 1-4设集合B={4,3}∩?,C={4,3}∩{?},D={3,4,?},E={x│x∈R并且x2-7x+12=0},F={4,?,3,3},试问:集合B与那个集合之间可用等号表示(选择题)[A] A.C; B.D; C.E; D. F. 1-5用列元法表示下列集合:A={x│x∈N且3-x〈3}(选择题)[D] A.N; B.Z; C.Q; D.Z+ 1-6为何说集合的确定具有任意性?(简答题) 答:按研究的问题来确定集合的元素。我们所要研究的问题当然是随意的呗。之所以,集合的定义(就是集合成分的确定)当然带有任意性哪。 第二章二元关系 2-1设A={1,2,3},A上的关系R={〈1,2〉,〈2,1〉}∪IA, 试求:(综合题) (1)domR=?;(2)ranR=?;(3)R的性质。 (4)商集A/R=?(5)A的划分∏=?(6)合成运算(R。R)=? 答:R={<1,2>,<1,3>,<2,3>,<1,1>,<2,2>,<3,3>}; (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={2,1,3}; (3)R的性质:自反,反对称,传递性质.这时,R不是等价关系。 (4)商集A/R={{1,2,3},{2,3},{3}}。由于R不是等价关系,所以,等价类之间出现交集。这是不允许的。请看下面的划分问题。 (5)A的划分∏={{1,2,3},{2,3},{3}};也由于R不是等价关系,造成划分的荒谬结果:出现交集。试问:让“3”即参加第一组,又参加第二组,她该如何分配呢!!! 所以,关系R必须是等价关系。至于作业中,此两题应说:因为R不是等价关系,此题无解。 2-2设R是正整数集合上的关系,由方程x+3y=12决定,即 R={〈x,y〉│x,y∈Z+且x+3y=12}, 试给出dom(R。R)。(选择题)[B] A.3; B.{3}; C.〈3,3〉; D.{〈3,3〉}。

离散数学(第2版)_在线作业_4

离散数学(第2版)_在线作业 _4 交卷时间:2017-01-12 14:00:56 一、单选题 1. (5分) ? A. q ∧┐q ? B. p →┐q ? C. p → (p ∨q) ? D. (p ∨┐p)→q 纠错 得分: 5 知识点: 离散数学(第2版) 收起解析 答案 C 解析 2. (5分) ? A. ? B. ? C. ? D. 下列命题公式为重言式的是( )。 设,下列式子正确的是( )。

纠错 得分: 5 知识点: 离散数学(第2版 ) 收起解析 答案 C 解析 3. (5分) ? A. ? B. ? C. ? D. 纠错 得分: 5 知识点: 离散数学(第2版) 收起解析 答案 D 解析 4. (5分) ? A. ? B. ? C. 下列是两个命题变元的极小项的是( )。 设G 是有个顶点, 条边和个面的连通平面图,则 等于( )。

? D. 纠错 得分: 5 知识点: 离散数学(第2版) 收起解析 答案 C 解析 5. (5分) ? A. 满射函数 ? B. 非单射非满射函数 ? C. 双射函数 ? D. 单射函数 纠错 得分: 5 知识点: 离散数学(第2版) 收起解析 答案 C 解析 6. (5分) 设R 是实数集合,函数,则是( )。

? A. 11,3,4 ? B. 10,4,3 ? C. 11,3,5 ? D. 12,3,6 纠错 得分: 5 知识点: 离散数学(第2版) 收起解析 答案 A 解析 7. (5分) ? A. x*y=gcd(x,y),即x,y 的最大公约数 ? B. x*y=lcm(x,y),即x,y 的最小公倍数 ? C. x*y=max{x,y} ? D. x*y=min{x,y} 纠错 得分: 5 知识点: 离散数学(第2版) 下列平面图的三个面的次数分别是( )。 设集合A={1,2,3,…,10},下面定义的哪种运算关于集合A 是不封闭的?( )。

离散数学 集合与关系 函数 习题 测验

一、已知A、B、C是三个集合,证明(A∪B)-C=(A-C)∪(B-C) 证明:因为 x∈(A∪B)-C?x∈(A∪B)-C ?x∈(A∪B)∧x?C ?(x∈A∨x∈B)∧x?C ?(x∈A∧x?C)∨(x∈B∧x?C) ?x∈(A-C)∨x∈(B-C) ?x∈(A-C)∪(B-C) 所以,(A∪B)-C=(A-C)∪(B-C)。 二、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>},求r(R)、s(R)和t(R),并作出它们及R的关系图。 解:r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R2=R5={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R3={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R4={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>, <5,5>} 三、证明等价关系 设R是集合A上的一个具有传递和自反性质的关系,T是A上的关系,使得∈T?∈R且∈R,证明T是一个等价关系。 证明因R自反,任意a∈A,有∈R,由T的定义,有∈T,故T自反。 若∈T,即∈R且∈R,也就是∈R且∈R,从而∈T,故T对称。 若∈T,∈T,即∈R且∈R,∈R且∈R,因R 传递,由∈R和∈R可得∈R,由∈R和∈R可得∈R,由∈R和∈R可得∈T,故T传递。 所以,T是A上的等价关系。 四、函数 设A、B、C、D是集合,f是A到B的双射,g是C到D的双射,令h:A×C→B×D且?∈A×C,h()=。证明h是双射。 证明:1)先证h是满射。 ?∈B×D,则b∈B,d∈D,因为f是A到B的双射,g是C到D的双射,所以存在a∈A,c∈C,使得f(a)=b,f(c)=d,亦即存在∈A×C,使得h()=

离散数学形成性考核作业7答案

一、填空题 1.命题公式() →∨的真值是 1 . P Q P 2.设P:他生病了,Q:他出差了.R:我同意他不参加学习.则命题“如果他生病或出差了,我就同意他不参加学习”符号化的结果为(P∨Q )→R .3.含有三个命题变项P,Q,R的命题公式P∧Q的主析取范式是 (P∧Q∧R)∨(P∧Q∧┐R) . 4.设P(x):x是人,Q(x):x去上课,则命题“有人去上课.”可符号化为x P Q x∧ ?. (x ( )) ( ) 5.设个体域D={a, b},那么谓词公式) x ∨ ?消去量词后的等值式为 xA? yB ) ( (y b B a A B ∨. ∨ A∧ a ) (b ( )) ( ( ) ) ( 6.设个体域D={1, 2, 3},A(x)为“x大于3”,则谓词公式(?x)A(x) 的真值为0 . 7.谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y .8.谓词命题公式(?x)(P(x) →Q(x) ∨R(x,y))中的约束变元为x . 三、公式翻译题 1.请将语句“今天是天晴”翻译成命题公式. 解:设P:今天是晴天, 命题“今天是晴天”翻译成命题公式为P。 2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式. 解:设P:小王去旅游,Q:小李去旅游. 命题“小王去旅游,小李也去旅游”翻译成命题公式为P∧Q。 3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式. 解:设P:明天天下雪,Q:我就去滑雪. 命题“如果明天天下雪,我就去滑雪”翻译成命题公式为P→Q。 4.请将语句“他去旅游,仅当他有时间.”翻译成命题公式.

《离散数学》作业参考答案

《离散数学》作业参考答案一、选择或填空: 1. B C D 2. A, F B,F C,F D,T 3. 2n-2 4. I A 5.单位元,1 6. A 7. A D 8. (1) P→?Q (2) P??Q 9.偶数 10.自反性、对称性和传递性 11. 1,单位元,0 12.所有边一次且恰好一次 13. B C D E F 14. B D 15. 5,10 16. D 17. B 18. D 19. A 20.(1)R R={ 〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉} (2)R-1={〈1,2〉,〈2,1〉,〈3,2〉,〈4,3〉} 21. m=n-1 22. 9,3 23. A 24. D 25 (1) 26 (2) 27 (3) 28 (1) 29 (1) 30 (3) 31 (2) 32 (3) 33 (2) 34 (4)

35 (2) 36 (1) 二、求下列各公式的主析取范式和主合取范式 解:1. P∨?Q (主合取范式) ?(P∧(?Q∨Q))∨((?P∨P)∧?Q) ?(P∧?Q)∨(P∧Q)∨(?P∧?Q)∨(P∧?Q) ?(P∧?Q)∨(P∧Q)∨(?P∧?Q)(主析取范式) 2.Q→( P∨?R) ??Q∨P∨?R(主合取范式) ?(Q→( P∨?R)) ?(?P∨?Q∨?R)∧(?P∨?Q∨R)∧(?P∨Q∨?R)∧(?P∨Q∨R)∧(P∨?Q∨R)∧ (P∨Q∨?R)∧(P∨Q∨R)(原公式否定的主合取范式) Q→( P∨?R) ?(P∧Q∧R)∨(P∧Q∧?R)∨(P∧?Q∧R)∨(P∧?Q∧?R)∨(?P∧Q∧?R)∨(?P∧?Q∧R)∨(?P∧?Q∧?R)(主析取范式) 3. P→Q??P∨Q(主合取范式) ?(?P∧(Q∨?Q))∨((?P∨P)∧Q) ?(?P∧Q)∨(?P∧?Q)∨(?P∧Q)∨(P∧Q) ?(?P∧Q)∨(?P∧?Q)∨(P∧Q)(主析取范式) 4.?(P→Q)∨(R∧P)??(?P∨Q)∨(R∧P) ?(P∧?Q)∨(R∧P)(析取范式) ?(P∧?Q∧(R∨?R))∨(P∧(?Q∨Q) ∧R) ?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R) ?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)(主析取范式) ?(?(P→Q)∨(R∧P)) ?(P∧Q∧?R)∨(?P∧Q∧R)∨(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R) (原公式否定的主析取范式) ?(P→Q)∨(R∧P) ?(?P∨?Q∨R)∧(P∨?Q∨?R)∧(P∨Q∨?R)∧(P∨Q∨R)∧(P∨?Q∨R)(主合取范式)5.P∧Q(主析取范式) ?(P∨(Q∧?Q))∧((P∧?P)∨Q) ?(P∨?Q)∧(P∨Q)∧(P∨Q)∧(?P∨Q) ?(P∨?Q)∧(P∨Q)∧(?P∨Q)(主合取范式) 6 Q→(P∨?R) ??Q∨P∨?R(主合取范式) ?(Q→(P∨?R))

离散数学形成性考核作业4答案教案资料

1. 设有向图(a)、(b)、(c)与(d)如图所示,则下列结论成立的是( ). A. (a)是强连通的 B. (b)是强连通的 C. (c)是强连通的 D. (d)是强连通的 2. 设有向图(a)、(b)、(c)与(d)如图所示,则下列结论成立的是( ). A. (a)是弱连通的 B. (b)是弱连通的 C. (c)是弱连通的 D. (d)是弱连通的 3. 设无向图G的邻接矩阵为则G的边数 为( ). A. 1 B. 6 C. 7 D. 14 4. 设无向图G的邻接矩阵为则G的边数为 ( ). A. 6 B. 5 C. 4

D. 3 5. 已知无向图G的邻接矩阵为则G有 (). A. 5点,8边 B. 6点,7边 C. 6点,8边 D. 5点,7边 6. 如图所示,以下说法正确的是( ). A. e是割点 B. {a,e}是点割集 C. {b, e}是点割集 D. {d}是点割集 7. 如图所示,以下说法正确的是( ) . A. {(a, e)}是割边 B. {(a, e)}是边割集 C. {(a, e) ,(b, c)}是边割集 D. {(d, e)}是边割集 8. 图G如图所示,以下说法正确的是( ).

A. a是割点 B. {b,c}是点割集 C. {b, d}是点割集 D. {c}是点割集 9. 图G如图所示,以下说法正确的是( ) . A. {(a, d)}是割边 B. {(a, d)}是边割集 C. {(a, d) ,(b, d)}是边割集 D. {(b, d)}是边割集 10. 设图G=,v V,则下列结论成立的是 ( ) . A. deg(v)=2|E| B. deg(v)=|E| C. D. 11. 设完全图K n有n个结点(n 2),m条边,当()时,K n中存在欧拉回路. A. m为奇数 B. n为偶数 C. n为奇数 D. m为偶数 12. 若G是一个汉密尔顿图,则G一定是( ).

相关文档
相关文档 最新文档