离散数学作业6
离散数学数理逻辑部分形成性考核书面作业
本课程形成性考核书面作业共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 :今天是晴天。
姓 名: 学 号: 得 分: 教师签名:
则P
2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式.
设P:小王去旅游。
Q:小李去旅游。
则P∧Q
3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式.
设P:明天下雪。
Q:我去滑雪。
则P→Q
4.请将语句“他去旅游,仅当他有时间.”翻译成命题公式.
设P:他去旅游。
Q:他有时间。
则P→Q
5.请将语句“有人不去工作”翻译成谓词公式.
设A(x):x是人
B(x):去工作
?x(A(x) ∧?B(x))
6.请将语句“所有人都努力工作.”翻译成谓词公式.
设A(x):x是人
B(x):努力工作
?x(A(x) ∧B(x))
四、判断说明题(判断下列各题,并说明理由.)
1.命题公式?P∧P的真值是1.
答:错。因为P和P的否不能同时为真。
2.命题公式?P∧(P→?Q)∨P为永真式.
答:对。?P∧(?P∨Q)∨P??P∨P?1
3.谓词公式))
x
xP?
yG
?是永真式.
x
→
?
→
xP
,
y
(
(
)
(x
)
(
答:对。它同P→(Q→P)是等价形式P→(Q→P)??P∨(?Q∨P)??P∨?Q∨P?1∨Q
4.下面的推理是否正确,请给予说明.
(1) (?x)A(x)→ B(x) 前提引入
(2) A(y) →B(y) US (1)
答:对。
四.计算题
1.求P→Q∨R的析取范式,合取范式、主析取范式,主合取范式.
P→Q∨R??P∨Q∨R (析取范式)
?(?P∨Q∨R)(合取范式)
真值表:
P Q R ?P 原式极小项及大项
0 0 0 1 1 ?P∧?P∧?
P
0 0 1 1 1 ?P∧?Q∧R
0 1 0 1 1 ?P∧Q∧?R
0 1 1 1 1 ?P∧Q∧R
1 0 0 0 0 ?P∨Q∨R 1 0 1 0 1 P∧?Q∧R
1 1 0 0 1 P∧Q∧?R
1 1 1 0 1 P∧Q∧R
主析取范式(?P∧?P∧?P)∨(?P∧?Q∧R)∨(?P∧Q∧?R)∨(?P∧Q∧R)∨(P∧?Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)
主合取范式(?P∨Q∨R)
2.求命题公式(P∨Q)→(R∨Q) 的主析取范式、主合取范式.
真值表:
P Q R ?(P∨Q)R∨Q 原式极小项及大项
0 0 0 1 0 1 ?P∧?P∧?
P
0 0 1 1 1 1 ?P∧?Q∧R
0 1 0 0 1 1 ?P∧Q∧?R
0 1 1 0 1 1 ?P∧Q∧R
1 0 0 0 0 0 ?P∨Q∨R 1 0 1 0 1 1 P∧?Q∧R
1 1 0 0 1 1 P∧Q∧?R
1 1 1 0 1 1 P∧Q∧R
主析取范式(?P∧?P∧?P)∨(?P∧?Q∧R)∨(?P∧Q∧?R)∨
(?P∧Q∧R)∨(P∧?Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)
主合取范式(?P∨Q∨R)
3.设谓词公式()((,)()(,,))()(,)
?→?∧?.
x P x y z Q y x z y R y z
(1)试写出量词的辖域;
(2)指出该公式的自由变元和约束变元.
答:(1)?x的辖域为P(x,y)→?zQ(x,y,z)
?z的辖域为Q(x,y,z)
?y的辖域为R(y,z)
(2) 约束变元为
P(x,y)→?zQ(x,y,z)中的x
Q(x,y,z) 中的z
R(y,z)中的y
自由变元为
P(x,y)→?zQ(x,y,z)中的y
R(y,z)中的z
4.设个体域为D={a1, a2},求谓词公式?y?xP(x,y)消去量词后的等值式;
答:谓词公式?y?xP(x,y)消去量词后的等值式为
(R(a,a)∧R(a,b))∨ (R(b,a)∧R(b,b))
五、证明题
1.试证明(P→(Q∨?R))∧?P∧Q与? (P∨?Q)等价.
证明:(P→(Q∨?R))∧?P∧Q
??P∨(Q∨?R))∧?P∧Q
??P∧Q
??(P∨?Q)
2.试证明(?x)(P(x) ∧R(x))?(?x)P(x) ∧ (?x)R(x).
证明:(1)?x(A(x) ∧B(x)) P
(2)A(c)∧B(c) ES(1) 公式A∧B?A
A∧B?B
(3)A(c) T(2)
(4) ?x(A(x) EG(3)
(5) B(c) T(2) 公式A∧B?A
A∧B?B
(6) ?xB(x) EG(5)
(7) (?x)A(x) ∧ (?x)B(x) T(4)(6) 公式A∧B?A
A∧B?B
离散数学作业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 :今天是晴天。 姓 名: 学 号: 得 分: 教师签名:
离散数学形成性考核作业( 一) 集合论部分 分校_________ 学号____________________ 姓名__________________ 分数 本课程形成性考核作业共 4 次, 内容由中央电大确定、统一布置。本次形考作业是第一次作业, 大家要认真及时地完成集合论部分的形考作业, 字迹工整, 抄写题目, 解答题有解答过程。 第 1 章集合及其运算 1.用列举法表示”大于2而小于等于9 的整数” 集合. 2.用描述法表示”小于5 的非负整数集合” 集合. 3 .写出集合B={1, {2, 3 }} 的全部子集. 4 .求集合A={ ,{ } } 的幂集. 5 .设集合A={{ a }, a }, 命题: { a } P(A) 是否正确, 说明理由. 6 .设 A {1,2,3}, B { 1,3,5}, C { 2,4,6}, 求 (1) A B (2) A B C (3) C - A (4) A B 7 .化简集合表示式: (( A B ) B) - A B.
试证:A - ( B C ) = ( A - B ) - C. 9 .填写集合{4, 9 } {9, 10, 4} 之间的关系. 10 .设集合A = {2, a , {3}, 4}, 那么下列命题中错误的是() A .{a } A B . { a , 4, {3}} A C . {a } A D . A 11 .设B = { {a }, 3, 4, 2}, 那么下列命题中错误的是() 第2章关系与函数 并验证 A (B C ) = ( A B ) (A C ). 4 .写出从集合A = { a , b , c }到集合B = {1}的所有二元关系. 8 .设A B C 是三个任意集合 A . {a } B B .{2, { a }, 3, 4} B C . {a } B D .设集合A = {a , b }, B = {1, 2, 3}, C = {3, 4}, 求 A (B C ), (A B) (A C ) .对任意三个集合 B 和 C 若ABA C 是否一定有B C ?为什么? .对任意三个集合 B 和 C 试证若A B = AC 」A
离散数学作业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 .请将语句“今天是天晴”翻译成命题公式
离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第一次作业,大家要认真及时地完成集合论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年11月7日前完成并上交任课教师(不收电子稿)。并在03任务界面下方点击“保存”和“交卷”按钮,完成并上交任课教师。 一、填空题 1.设集合{1,2,3},{1,2} ==,则P(A)-P(B )= A B {{3},{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? x ∈ > y 且 =且 ∈ < {B , , x A y A y B x } 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}. 4.设集合A={1, 2, 3, 4 },B={6, 8, 12},A到B的二元关系 R=} y y x∈ = < > ∈ x , , x , 2 {B y A 那么R-1={<6,3>,<8,4>} 5.设集合A={a, b, c, d},A上的二元关系R={, , ,
一、请给出一个集合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)
离散数学作业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 去工作,
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月5日前完成并上交任课教师(不收电子稿)。并在05任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数是 15 . 2.设给定图G (如右由图所示),则图G 的点割集是 {}f {}c e ,. 3.设G 是一个图,结点集合为V ,边集合为E ,则 G 的结点 度数之和 等于边数的两倍. 4.无向图G 存在欧拉回路,当且仅当G 连通且 不含奇数度结点 . 5.设G=
一、单项选择题(每小题2分,共38分) 题目1 正确 获得2.00分中的2.00分 未标记标记题目 题干 假定一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为()。 选择一项: A. 16 B. 47 C. 15 D. 17 题目2 正确 获得2.00分中的2.00分 未标记标记题目 题干 二叉树第k层上最多有()个结点。 选择一项: A. 2k-1 B. 2k-1 C. 21 k D. 2k 题目3 正确 获得2.00分中的2.00分 未标记标记题目 题干 将含有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为()。 选择一项: A. 34 B. 35 C. 33 D. 36 题目4 正确 获得2.00分中的2.00分 未标记标记题目
如果将给定的一组数据作为叶子数值,所构造出的二叉树的带权路径长度最小,则该树称为()。 选择一项: A. 二叉树 B. 哈夫曼树 C. 完全二叉树 D. 平衡二叉树 题目5 正确 获得2.00分中的2.00分 未标记标记题目 题干 在一棵度具有5层的满二叉树中结点总数为()。 选择一项: A. 33 B. 32 C. 31 D. 16 题目6 正确 获得2.00分中的2.00分 未标记标记题目 题干 一棵完全二叉树共有6层,且第6层上有6个结点,该树共有()个结点。 选择一项: A. 37 B. 72 C. 38 D. 31 题目7 正确 获得2.00分中的2.00分 未标记标记题目 题干 利用3、6、8、12这四个值作为叶子结点的权,生成一棵哈夫曼树,该树中所有叶子结点中的最长带权路径长度为()。 选择一项: A. 18 B. 30
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月5日前完成并上交任课教师(不收电子稿)。并在05任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数是 15 . 2.设给定图G (如右由图所示),则图G 的点割集是 {}f {}c e ,. 3.设G 是一个图,结点集合为V ,边集合为E ,则 G 的结点 度数之和 等于边数的两倍. 4.无向图G 存在欧拉回路,当且仅当G 连通且 不含奇数度结点 . 5.设G=
计算机科学与技术专业级第二学期离散数学试题 2012年1月 一、单项选择题(每小题3分,本题共15分)1. C 2. C 3. B 4. A 5. D 1-若集合4的元素个数为10,则其幕集的元素个数为()? A. 10 B. 100 C. 1024 D. 1 2. 设A={a, d},伊{1,2}, R、,电、足是刀到8的二元关系,旦用二{<Q, 2>,<。】>},他二{<。 1>,<。2>,<》,】>},足={<。,】>,</?, 2>),则()是从/到8的函数. A. R[和R? B . R仁 C. R3 D. R\和足 3. 设木{1,2,3,45,6,7,8}, /?是/上的整除关系,位{2, 4, 6},则集合8的最大元、最小元、上界、下界依次为()? A. 8、2、8、2 B.无、2、无、2 C. 6、2、6、2 D. 8、1、6、1 4.若完全图G中有77个结点777条边,则当()时,图G中存在欧拉回路. A.。为奇数 B. ”为偶数 C. "7为奇数 D. s为偶数 5.已知图G的邻接矩阵为 % o o 1 T 0 0 0 0 1 0 0 0 1 1 10 10 1 11110 则。有(). A. 6 点,8 边 B.6点,6边 C. 5 点,8 边 D.5点,6边 二、埴空题(每小题3分,本题共15分) 6. 设集合乂 = {况,那么集合/的富集是{。腥}}. 7. 若吊和%是/上的对称关系,则R\U电,R、nw R'-电,传用中对称关系有个. 8. 设图G是有5个结点的连通图,结点度数总和为10,则可从G中删去1 条边后使之变成树. 9. 设连通平面图G的结点数为5,边数为6,贝1|面数为 3 . 10. 设个体域D = G d},则谓词公式(VA)MW A B(X))消去重词后的等值式为(乂(Q) A8(Z?))A(4 (。)AB(/?)) . 三、逻辑公式翻译(每小题6分,本题共12分) 11. 将语句“今天有联欢活动,明天有文艺晚会翻译成命题公式. 设户:今天有联欢活动,Q:明天有文艺晚会,(2分) PN Q.(6 分)
吉林大学网络教育学院2019-2020学年第一学期期末考试《离散数学》大作业 学生姓名专业 层次年级学号 学习中心成绩 年月日
作业完成要求:大作业要求学生手写,提供手写文档的清晰扫描图片,并将图片添加到word 文档内,最终wod文档上传平台,不允许学生提交其他格式文件(如JPG,RAR等非word 文档格式),如有雷同、抄袭成绩按不及格处理。 一、简答题(每小题7分,共56分) 1、什么是命题公式的演绎? 答:首先定义了消解复杂性的两种范式:最简范式和文字范式,在此基础上采用演绎方法证明了L中的可判定性定理,并设计了命题公式的演绎判定算法P(F).P(F)的时间复杂度为O(n3),远远小于基于真值表法的O(2n)和基于策略方案HAL的O(n5)。 2、什么是子句?请给出一例。 答:子句是一组包含一个主词和一个动词的关连字。子句与片语有明显的不同,后者为一组不含主词与动词关系的关连字,如"in the morning" 或"running down the street" 或"having grown used to this harassment." 3、什么是短语?请给出一例。 答:短语是由句法、语义和语用三个层面上能够搭配的语言单位组合起来的没有句调的语言单位,又叫词组。它是大于词而又不成句的语法单位。简单的短语可以充当复杂短语的句法成分,短语加上句调可以成为句子。由语法上能够搭配的词组合起来的没有句调的语言单位 例如:粮食//丰收(名//动)(什么//怎么样) 4、什么是命题逻辑中的文字? 答:检测和消除命题逻辑公式中的冗余文字,是人工智能领域广泛研究的基本问题。针对命题逻辑的子句集中子句的划分,结合冗余子句和冗余文字的概念,将命题逻辑的子句集中的文字分为必需文字、有用文字和无用文字3类。 5、什么是析取范式?请给出一例。 答:在离散数学中,仅由有限个文字构成的合取式称为简单合取式,而由有限个简单合取式构成的析取式称为析取范式。范式存在定理说明了它的存在性:任一命题公式都存在着与之等值的析取范式与合取范式。但它并不是惟一的。主析取范式是惟一的。
离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word 文档 3. 自备答题纸张,将答题过程手工书写,并拍照上传. 一、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数是 15 . 2.设给定图G (如右由图所示),则图G 的点割集是 {f,c} . 3.设G 是一个图,结点集合为V ,边集合为E ,则 G 的结点 度数之和 等于边数的两倍. 4.无向图G 存在欧拉回路,当且仅当G 连通且所有结点的度数全为偶 数 . 5.设G=
2020年电大离散数学(本)期末考试题库及答案 一、单项选择题 1.设P:a是偶数,Q:b是偶数。R:a + b是偶数,则命题“若a是偶数,b是偶数,则a + b 也是偶数”符号化为(D.P Q→R)。2.表达式?x(P(x,y)∨Q(z))∧?y(Q(x,y)→?zQ(z))中?x的辖域是(P(x,y)Q(z))。 3.设) ( }), ({ }, { , 4 3 2 1 ? = ? = ? = ? =P S P S S S则命题为假的是( 4 2 S S∈)。 4.设G是有n个结点的无向完全图,则G的边数(1/2 n(n-1))。 5.设G是连通平面图,有v个结点,e条边,r个面,则r=(e-v+2)。 6.若集合A={1,{2},{1,2}},则下列表述正确的是( {1}?A ). 7.已知一棵无向树T中有8个顶点,4度、3度、2度的分支点各一个,T的树叶数为( 5 ). 8.设无向图G的邻接矩阵为 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 则G的边数为( 7 ). 9.设集合A={a},则A的幂集为({?,{a}} ). 10.下列公式中(?A∧?B ??(A∨B) )为永真式. 11.若G是一个汉密尔顿图,则G一定是( 连通图). 12.集合A={1, 2, 3, 4}上的关系R={
离散数学作业答案 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={, , ,
电大离散数学本形考任 务 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】
离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第一次作业,大家要认真及时地完成集合论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档 3. 自备答题纸张,将答题过程手工书写,并拍照上传. 一、填空题 1.设集合{1,2,3},{1,2} A B ==,P(A)-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=} x∈ y y > <那么R-1={<6,3>,<8,4>}. x = ∈ 2 , , x , {B A y 5.设集合A={a, b, c, d},A上的二元关系R={, , ,
第一章 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规则 第五章
五、证明题 1.设G 是一个n 阶无向简单图,n 是大于等于3的奇数.证明图G 与它的补图G 中的奇数度顶点个数相等. 证明:设,G V E =<>,,G V E '=<>.则E '是由n 阶无向完全图n K 的边删去E 所得到的.所以对于任意结 点u V ∈,u 在G 和G 中的度数之和等于u 在n K 中的度数.由于n 是大于等于3的奇数,从而n K 的每个结点都是偶数度的( 1 (2)n -≥度),于是若u V ∈在G 中是奇数度结点,则它在G 中也是奇数度结点.故图G 与它的补图G 中的奇数度结点个数相等. 2.设连通图G 有k 个奇数度的结点,证明在图G 中至少要添加 2 k 条边才能使其成为欧拉图. 证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k 是偶数. 又根据定理4.1.1的推论,图G 是欧拉图的充分必要条件是图G 不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G 的所有结点的度数变为偶数,成为欧拉图. 故最少要加2 k 条边到图G 才能使其成为欧拉图. 五、证明题 1.试证明集合等式:A ? (B ?C )=(A ?B ) ? (A ?C ). 证:若x ∈A ? (B ?C ),则x ∈A 或x ∈B ?C , 即x ∈A 或x ∈B 且x ∈A 或x ∈C . 即x ∈A ?B 且x ∈A ?C , 即x ∈T =(A ?B ) ? (A ?C ), 所以A ? (B ?C )? (A ?B ) ? (A ?C ). 反之,若x ∈(A ?B ) ? (A ?C ),则x ∈A ?B 且x ∈A ?C , 即x ∈A 或x ∈B 且x ∈A 或x ∈C , 即x ∈A 或x ∈B ?C , 即x ∈A ? (B ?C ), 所以(A ?B ) ? (A ?C )? A ? (B ?C ). 因此.A ? (B ?C )=(A ?B ) ? (A ?C ). 2.对任意三个集合A , B 和C ,试证明:若A ?B = A ?C ,且A ≠?,则B = C . 证明:设x ∈A ,y ∈B ,则
华南理工大学网络教育学院 2018–2019学年度第一学期 《离散数学》作业 1、用推理规则证明?(P∧?Q),?Q∨R,? R??P 证(1)?Q∨R P (2)? R P (3)?Q(1)(2)析取三段论 (4)?(P∧?Q)P (5)?P ∨ Q (4)等价转换 (6)?P (3)(5)析取三段论 2、用推理规则证明Q,?P → R,P → S,? S?Q∧R 证(1)P → S P (2)? S P (3)?P(1)(2)拒取式 (4)?P → R P (5)R (3)(4)假言推理 (6)Q P (7)Q∧R(5)(6)合取 3.设命题公式为?Q∧(P→Q)→?P。 (1)求此命题公式的真值表; (2)求此命题公式的析取范式; (3)判断该命题公式的类型。 解(1)真值表如下 P Q ?Q P→Q ?Q∧(P→Q)?P?Q∧(P→Q)→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 (2)?Q∧(P→Q)→?P??(?Q∧(?P∨Q))∨?P ?(Q∨?(?P∨Q))∨?P??(?P∨Q)∨(Q∨?P)?1(析取范式)?(?P∧?Q)∨(?P∧Q)∨(P∧?Q)∨(P∧Q)(主析取范式) (3)该公式为重言式 4.在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。
令F(x):x喜欢步行。G(x):x喜欢坐汽车。H(x):x喜欢骑自行车。 解前提:?x(F(x)→? G(x)),?x(G(x)∨H(x)), ? x? H(x)。 结论:? x ?F(x)。 证(1)? x ?H(x)P (2)?H(c)ES(1) (3)?x(G(x)∨H(x))P (4) G(c)∨H(c)US(3) (5) G(c)T(2,4)I (6)?x(F(x)→? G(x))P (7)F(c)→? G(c)US(6) (8)? F(c)T(5,7)I (9)(?x)? F(x)EG(8) 5.用直接证法证明: 前提:(?x)(C(x)→W(x)∧R(x)),(?x)(C(x)∧Q(x)) 结论:(?x)(Q(x)∧R(x))。 证(1)(?x)(C(x)∧Q(x))P (2)C(c)∧Q(c)ES(1) (3)(?x)(C(x)→W(x)∧R(x))P (4) C(c)→W(c)∧R(c)US(3) (5) C(c)T(2)I (6)W(c)∧R(c)T(4,5)I (7)R(c)T(6)I (8)Q(c)T(2)I (9)Q(c)∧R(c)T(7,8)I (10) (?x)(Q(x)∧R(x))EG(9) 6.设R是集合A = {1, 2, 3, 4, 5, 6, 7, 8, 9}上的整除关系。 (1)给出关系R;(2)画出关系R的哈斯图; (3)指出关系R的最大、最小元,极大、极小元。 解R={<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<1,9>,<2,4>,<2,6>,<2,8>,<3,6>,<3,9>,<4,8>}∪I A COV A={<1,2>,<1,3>,<1,5>,<1,7>,<2,4>,<2,6>,<3,6>,<3,9>,<4,8>} 作哈斯图如右: 极小元和最小元为1; 极大元为5,6,7,8,9, 无最大元 8