离散数学 集合、数理逻辑、图部分的综合练习题

《离散数学》题库及标准答案《离散数学》题库及答案————————————————————————————————作者：————————————————————————————————日期：《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。

在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。

于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

离散数学集合论部分测试题离散数学集合论部分综合练习本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次是集合论部分的综合练习。

一、单项选择题1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）．A．A⊂B，且A∈B B．A∈B，但A⊄BC．A⊂B，但A∉B D．A⊄B，且A∉B2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．A．{a，{ a }}∈A B．{ a }⊆AC．{2}∈A D．∅∈A3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )．A．{a，{a}}∈A B．{2}⊆AC．{a}⊆A D．∅∈A4．若集合A={a，b，{1，2 }}，B={1，2}，则（）．A．B⊂ A，且B∈A B．B∈ A，但B⊄AC．B ⊂ A，但B∉A D．B⊄ A，且B∉A5．设集合A = {1, a }，则P(A) = ( )．A．{{1}, {a}} B．{∅,{1}, {a}}C．{∅,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}6．若集合A的元素个数为10，则其幂集的元素个数为（）．A．1024 B．10 C．100 D．17．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, y∈A}，则R 的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={<a , b>⎢a , b∈A , 且a +b = 8}，则R具有的性质为（）．A．自反的B．对称的C．对称和传递的D．反自反和传递的9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A．0 B．2 C．1 D．310．设集合A={1 , 2 , 3 , 4}上的二元关系R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，S = {<1 , 1>，<2 , 2>，<2 , 3>，<3 , 2>，<4 , 4>}，则S 是R 的（ ）闭包．A ．自反B ．传递C ．对称D ．以上都不对11．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系的哈斯图如图一所示，若A 的子集B = {3 , 4 , 5}，则元素3为B 的（ ）．A ．下界B ．最大下界C ．最小上界D ．以上答案都不对 12．设A ={1, 2, 3, 4, 5, 6, 7, 8}，R 是A 上的整除关系，B ={2, 4, 6}，则集合B 的最大元、最小元、上界、下界依次为 ( )．A ．8、2、8、2B ．无、2、无、2C ．6、2、6、2D ．8、1、6、113．设A ={a , b }，B ={1, 2}，R 1，R 2，R 3是A 到B 的二元关系，且R 1={<a ，2>, <b ，2>}，R 2={<a ，1>, <a ，2>, <b ，1>}，R 3={<a ，1>, <b ，2>}，则（ ）不是从A 到B 的函数．A ．R 1和R 2B ．R 2C ．R 3D ．R 1和R 3二、填空题1．设集合A 有n 个元素，那么A 的幂集合P (A )的元素个数为 ．2．设集合A ＝{a ，b }，那么集合A 的幂集是 ． 应该填写：{∅,{a ,b },{a },{b }}3．设集合A ={0, 1, 2, 3}，B ={2, 3, 4, 5}，R 是A 到B 的二元关系， },,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的有序对集合为 ．4．设集合A ={0, 1, 2}，B ={0, 2, 4},R 是A 到B 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的关系矩阵M R ＝．5．设集合A ={a ,b ,c }，A 上的二元关系R ={<a , b >,<c . a >}，S ={<a , a >,<a , b >,<c , c >}则(R ∙S )－1= ．6．设集合A =｛a ,b ,c ｝，A 上的二元关系R ={<a , b >, <b , a >, <b , c >, <c , d >}，则二元关系R 具有的性质是 ．7．若A ={1,2}，R ={<x , y >|x ∈A , y ∈A , x +y =10}，则R 的自反闭包为 ．8．设集合A ={1, 2}，B ={a , b }，那么集合A 到B 的双射函数是 ． 2 4 1 3 5图一9．设A ={a ，b ，c }，B ={1，2}，作f ：A →B ，则不同的函数个数为 ．三、判断说明题（判断下列各题，并说明理由．）1．设A 、B 、C 为任意的三个集合，如果A ∪B =A ∪C ，判断结论B =C 是否成立？并说明理由．2．如果R 1和R 2是A 上的自反关系，判断结论：“R -11、R 1∪R 2、R 1⋂R 2是自反的” 是否成立？并说明理由．3． 若偏序集<A ，R >的哈斯图如图一所示，则集合A 的最大元为a ，最小元不存在． 4．若偏序集<A ，R >的哈斯图如图二所示，则集合A 的最大元为a ，最小元不存在．5．设N 、R 分别为自然数集与实数集，f ：N→R ，f (x )=x +6，则f 是单射．四、计算题 1．设集合A ＝{a , b , c }，B ={b , d , e }，求（1）B ⋂A ； （2）A ⋃B ； （3）A －B ； （4）B ⊕A ．2．设A ={{a , b }, 1, 2}，B ={ a , b , {1}, 1}，试计算（1）（A -B ） （2）（A ∪B ） （3）（A ∪B ）-（A ∩B ）．3．设集合A ={{1},{2},1,2}，B ={1,2,{1,2}}，试计算（1）（A -B ）； （2）（A ∩B ）； （3）A ×B ．4．设A ={0，1，2，3，4}，R ={<x ，y >|x ∈A ，y ∈A 且x +y <0}，S ={<x ，y >|x ∈A ，y ∈A 且x +y ≤3}，试求R ，S ，R ∙S ，R -1，S -1，r (R )．5．设A ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R 是A 上的整除关系，B ={2, 4, 6}．（1）写出关系R 的表示式； （2）画出关系R 的哈斯图；（3）求出集合B 的最大元、最小元．6．设集合A ＝{a , b , c , d }上的二元关系R 的关系图 如图三所示．（1）写出R 的表达式；（2）写出R 的关系矩阵；（3）求出R 2． 7．设集合A ={1，2，3，4}，R ={<x , y >|x , y ∈A ；|x -y |=1或x -y =0}，试（1）写出R 的有序对表示； （2）画出R 的关系图；（3）说明R 满足自反性，不满足传递性．五、证明题1．试证明集合等式：A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C )．2．试证明集合等式A ⋂ (B ⋃C )=(A ⋂B ) ⋃ (A ⋂C )．图一图二a dbc 图三3．设R 是集合A 上的对称关系和传递关系，试证明：若对任意a ∈A ，存在b ∈A ，使得<a , b >∈R ，则R 是等价关系．4．若非空集合A 上的二元关系R 和S 是偏序关系，试证明：S R ⋂也是A 上的偏序关系．参考解答一、单项选择题1．A 2．B 3．C 4．B 5．C 6．A 7．B 8．B 9．B 10．C 11．C 12．B 13．B二、填空题1．2n2．{∅,{a ,b },{a },{b }}3．{<2, 2>，<2, 3>，<3, 2>}，<3, 3>4．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡011000011 5．{<a . c >, <b , c >}6．反自反的7．{<1, 1>, <2, 2>}8．{<1, a >, <2, b >}，{<1, b >, <2, a >}9．8三、判断说明题（判断下列各题，并说明理由．）1．解：错．设A ={1, 2}，B ={1}，C ={2}，则A ∪B =A ∪C ，但B ≠C ．2．解：成立．因为R 1和R 2是A 上的自反关系，即I A ⊆R 1，I A ⊆R 2。

北京科技大学远程教育学院《离散数学》综合练习(一)参考答案数理逻辑一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。

1、今天天气真好！解：不是命题。

2、王华和张民是同学。

解：是命题。

真值视实际情况而定。

p：王华和张民是同学。

3、我一边吃饭，一边看电视。

解：是命题。

真值视实际情况而定。

p：我吃饭。

q：我看电视。

p∧q 4、没有不呼吸的人。

解：是命题。

真值为1。

M(x)：x是人。

F(x)：x呼吸。

∀x(M(x)→F(x))二、求命题公式的真值表和成真赋值、成假赋值。

p→∧qr∧→(p])[(r)解：成真赋值：000，001，010，011，101，111；成假赋值100，110三、用真值表、等值演算两种方法判别公式类型。

1、r q q p →∧→])[( 解：rq q p r q q q p r q q p rq q p r q q p r q q p ∨⌝∧⌝∨⇔∨⌝∨⌝∧⌝∨⇔∨⌝∨⌝∧⇔∨⌝∨∨⌝⌝⇔∨∧∨⌝⌝⇔→∧→])[()]()[()()(])[(])[(可满足式2、))((p q p q ∧∨⌝⌝∨ 解：))((p q p q A ∧∨⌝⌝∨=1)()()())((⇔∨⌝∨∨⌝⌝⇔⌝∨∨⌝⌝∨⇔∧∨⌝⌝∨q p q p p q p q p q p q永真式四、求命题公式的主析取范式和成真赋值、成假赋值。

)(r q p →→ 解：∑=→→），，，，，，7543210()(r q p 成真赋值：000，001，010，011，100，101，111；成假赋值110 五、解释I 如下：D 是实数集，特定元素a =0；特定函数f (x ，y )=x -y ；特定谓词F (x ，y )：x<y 。

在解释I 下判别公式真、假。

1、)])(([x y x f F y x ，，⌝∀∀ 解：)])[()])(([)]([)])(([x y x y x x y x y x x y x F y x x y x f F y x ≥-∀∀⇔<-⌝∀∀⇔-⌝∀∀⇔⌝∀∀，，，真值为假2、)]()([)({z y f z x f F y x F z y x ，，，，→∀∀∀ 解：)]()()[()]}()([)({z y z x y x z y x z y f z x f F y x F z y x -<-→<∀∀∀⇔→∀∀∀，，，，真值为真 六、1、求前束范式)()(y x yG x xF ，∀→⌝∃ 解：)]()([)()()()()()(y t G x F y x y t yG x xF y x yG x xF y x yG x xF ，，，，∨∀∃⇔∀∨∃⇔∀∨∃⇔∀→⌝∃2、证明：B x xA B x A x →∀⇔→∃)())(( 证明：Bx xA Bx xA B x A x B x A x B x A x →∀⇔∨⌝∀⇔∨⌝∃⇔∨⌝∃⇔→∃)()()())(())((七、写出下面推理的证明，要求写出前提、结论，并注明推理规则。

离散数学集合论部分综合练习本课程综合练习共分3次, 分别是集合论部分、图论部分、数理逻辑部分的综合练习, 这3次综合练习基本上是按照考试的题型安排练习题目, 目的是经过综合练习, 使同学自己检验学习成果, 找出掌握的薄弱知识点, 重点复习, 争取尽快掌握。

本次是集合论部分的综合练习。

一、单项选择题1．若集合A={a, b}, B={ a, b, { a, b }}, 则( ) ． A．A B, 且A B B．A B, 但A BC．A B, 但A B D．A B, 且A B 2．若集合A＝{2, a, { a }, 4}, 则下列表述正确的是( )．A．{a, { a }}A B．{ a }AC．{2}A D． A3．若集合A＝{a, {a}, {1, 2}}, 则下列表述正确的是( )． A．{a, {a}}A B．{2}AC．{a}A D．A4．若集合A={a, b, {1, 2 }}, B={1, 2}, 则( ) ．A．B A, 且B A B．B A, 但B AC．B A, 但B A D．B A, 且B A5．设集合A = {1, a }, 则P(A) = ( )．A．{{1}, {a}} B．{∅,{1}, {a}} C．{∅,{1}, {a}, {1, a}} D．{{1}, {a}, {1, a}} 6．若集合A的元素个数为10, 则其幂集的元素个数为( ) ．A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x, y>|x+y=10且x, y∈A}, 则R的性质为( ) ．A．自反的 B．对称的C．传递且对称的 D．反自反且传递的8．设集合A = {1, 2, 3, 4, 5, 6 }上的二元关系R ={<a , b>a , b∈A , 且a +b = 8}, 则R具有的性质为( ) ．A．自反的 B．对称的C．对称和传递的 D．反自反和传递的9．如果R1和R2是A上的自反关系, 则R1∪R2, R1∩R2, R1-R2中自反关系有( ) 个．A ．0B ．2C ．1D ．310．设集合A ={1 , 2 , 3 , 4}上的二元关系R = {<1 , 1>, <2 , 2>, <2 , 3>, <4 , 4>},S = {<1 , 1>, <2 , 2>, <2 , 3>, <3 , 2>, <4 , 4>}, 则S 是R 的( ) 闭包．A ．自反B ．传递C ．对称D ．以上都不对11．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系 的哈斯图如图一所示, 若A 的子集B则元素3为B 的( ) ．A ．下界B ．最大下界C ．最小上界D ．以上答案都不对12．设A ={1, 2, 3, 4, 5, 6, 7, 8}, R 是A 上的整除关系, B ={2, 4, 6}, 则集合B 的最大元、 最小元、 上界、 下界依次为 ( )．A ．8、 2、 8、 2B ．无、 2、 无、 2C ．6、 2、 6、 2D ．8、 1、 6、 113．设A ={a , b }, B ={1, 2}, R 1, R 2, R 3是A 到B 的二元关系, 5图且R1={<a, 2>, <b, 2>}, R2={<a, 1>, <a, 2>, <b, 1>}, R3={<a, 1>, <b, 2>}, 则( ) 不是从A到B的函数．A．R1和R2 B．R2 C．R3 D．R1和R3二、填空题1．设集合A有n个元素, 那么A的幂集合P(A)的元素个数为．2．设集合A＝{a, b}, 那么集合A的幂集是．应该填写: {,{a,b},{a},{b }}3．设集合A={0, 1, 2, 3}, B={2, 3, 4, 5}, R是A到B的二元关系,∈R⋂xy∈x且=且<>∈{B,,}AyyBxA则R的有序对集合为．4．设集合A={0, 1, 2}, B={0, 2, 4},R是A到B的二元关系,∈∈R⋂x∈y且=且<>A{B,,}xyAxyB则R的关系矩阵M R＝．5．设集合A={a,b,c}, A上的二元关系R={<a, b>,<c. a>}, S={<a, a>,<a, b>,<c, c>}则(R S)－1= ．6．设集合A=｛a,b,c｝, A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}, 则二元关系R具有的性质是．7．若A={1,2}, R={<x, y>|x A, y A, x+y=10}, 则R的自反闭包为．8．设集合A={1, 2}, B={a, b}, 那么集合A到B的双射函数是．9．设A={a, b, c}, B={1, 2}, 作f: A→B, 则不同的函数个数为．三、判断说明题( 判断下列各题, 并说明理由．)1．设A、B、C为任意的三个集合, 如果A∪B=A∪C, 判断结论B=C是否成立? 并说明理由．图一。

《离散数学》课程作业（2）-------数理逻辑部分一、 填空题1. 将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、 、 、 和等值。

2、命题公式G=（P ∧Q ）→R ，则G 共有 个不同的解释；把G 在其所有解释下所取真值列成一个表，称为G 的 ；解释（⌝P ，Q ，⌝R ）或（0，1，0）使G 的真值为 。

3、 已知命题公式R Q P G →∧⌝=)(，则G 的析取范式是 。

4、 求公式)()(R P Q P ∧⌝∨∧的主析取范式 。

5、 设命题公式)(R Q P G →⌝→=，则使公式G 为假的解释是 、 和 。

6、在谓次词逻辑中将下面命题符号化：在北京工作的人未必都是北京人（提示：设F （x ）：x 在北京工作。

G （x ）：x 是北京人。

） 。

7、将公式化成等价的前束范式，=→∃→⌝∃∃)))()((),((x R z zQ y x yP x 。

8、设谓词的定义域为},,{c b a ，将表达式)()(x xS x xR ∃∧∀中的量词消除，写成与之等价的命题公式是 。

二、 单项选择题1、下列语句中，（ ）是命题。

A ．下午有会吗？B ．这朵花多好看呀！C ．2是常数。

D ．请把门关上。

2、一个公式在等价意义下，下面哪个写法是唯一的（ ）。

A ．析取范式B ．合取范式C ．主析取范式D ．以上答案都不对3、设命题公式P Q P G →∧=)(，则G 是（ ）。

A. 恒假的B. 恒真的C. 可满足的D. 析取范式4、设命题公式)(),(P Q P H Q P G ⌝→→=→⌝=，则G 与H 的关系是（ ）。

以上都不是。

.;.;.;.D H G C G H B H G A =⇒⇒ 5、已知命题))((R Q P G ∧→⌝=，则所有使G 取真值1的解释是（ ）。

A （0，0，0），（0，0，1），（1，0，0）B （1，0，0），（1，0，1），（1，1，0）C （0，1，0），（1，0，1），（0，0，1）D （0，0，1），（1，0，1），（1，1，1）6、设I 是如下一个解释，0101),(),(),(),(},,{b b P a b P b a P a a P b a D =， 则在解释I 下取真值为1的公式是（ ）。

《离散数学》题库一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

5、判断下列语句是不是命题。

若是，给出命题的真值。

( ) (1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？(4) 若7+8＞18，则三角形有4条边。

(5) 前进！(6) 给我一杯水吧！6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校(2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)9、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数(3) 复数(4) (1)--(3)均成立11、命题“2是偶数或-3是负数”的否定是（）。

离散数学试题及答案一、选择题1. 下列哪个是由离散数学的基本概念组成的？A. 集合论和函数论B. 图论和逻辑C. 运算符和关系D. 全数论和数论答案：B2. 下列哪个是离散数学的一个应用领域？A. 数据结构和算法分析B. 微积分和线性代数C. 概率论和统计学D. 数值分析和微分方程答案：A3. 集合A={1, 2, 3}，集合B={2, 3, 4}，则A交B的结果是：A. {1, 2, 3, 4}B. {2, 3}C. {2}D. {1}答案：B4. 下列哪个是对于集合的补集运算的正确描述？A. A∪A' = ∅B. A∩A' = ∅C. A - A' = AD. A'∩B' = (A∪B)'答案：B5. 若命题p为真，命题q为假，则命题p→q的真值为：A. 真B. 假C. 不确定D. 无法确定答案：B二、填空题1. 对于命题“如果x是偶数，则x能被2整除”，其逆命题为________________。

答案：如果x不能被2整除，则x不是偶数。

2. 在一个完全图中，如果有12条边，则这个图有__________个顶点。

答案：6个顶点。

3. 设集合A={1, 2, 3, 4}，则A的幂集的元素个数是__________。

答案：2^4=16个元素。

4. 设关系R={(-1, 0), (0, 1), (1, 0)}，则R的逆关系是__________。

答案：R^(-1)={(0, -1), (1, 0), (0, 1)}。

5. 若集合A={1, 2, 3}，集合B={2, 3, 4}，则A的笛卡尔积B是__________。

答案：A×B={(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}。

三、计算题1. 求集合A={1, 2, 3}和集合B={2, 3, 4}的并集。

离散数学作业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 ：今天是晴天。

姓 名： 学 号： 得 分： 教师签名：则P2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．设P：小王去旅游。

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

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

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年11月7日前完成并上交任课教师（不收电子稿）。

并在03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。

一、填空题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 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的有序对集合为 {<2,2>,<2,3>,<3,2>,<3,3>} ． 姓 名： 学 号： 得 分： 教师签名：4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系R＝}yyx∈=<>∈xx,,,2{BAy那么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，R-R2中自反关系有2个．18．设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．由逆关系定义和I A R 1，得I A R 1-1；由I A R 1，I A R 2，得I A R 1∪R 2，I A R 1R 2．所以，R 1-1、R 1∪R 2、R 1R 2是自反的．3．若偏序集<A ，R >的哈斯图如图一所示， 则集合A 的最大元为a ，最小元不存在．错误，按照定义，图中不存在最大元和最小元。

一-单项选择题B ・(P/\0) V/? D ・\!R G(x):兀是健壮的，则命题“没有一个国家级 )・ B ・「\/x(C(x) t 「G(x)) D ・—«3%(C(x) A —iG(x)) 兀是学生，则命题“不是所有人都是学生” A. (X/x)(A(x)/\B ⑴) B ・-](m*)(A ⑴AB(X))C. n (Vx)(/4(x) -*B(X )) D ・ ~I (m^)(A ⑴A~i B(x)) 9.表达式 Vx(P(x,y) 7 Q(z)) A 3y(R(x, y) T X/Z Q(Z ))中 Vx 的辖域是(). A. P(x, y)B ・ P(x,y)\/Q(z)C ・ R(x, >)D ・ P(x, ^)A /?(X , y)二、填空题 1・命题公式P T (Q V P)的真值是 ________________ ・2. 设戸 他生病了，Q ：他出差了. R ：我同意他不参加学习.则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为(PS'T R •3•含有三个命题变项P,Q,R 的命题公式的主析取范式是_(P A 2A /?)V (P A ，O/\—\R) •4. 设F(x)：兀是鸟，G(x)：兀会飞翔.则命题“鸟会飞”符号化为(\7X )(F(X )T G(x)) 符号化为( )? ?A. Q T P B ・ P T Q C ・ P > Q D. ―P v ―Q 2. 设命题公式G ： 「P T (Q A R),则使公式G 取真值为1的P, Q,尺赋值分别是( )A. 0,0,0B. 0, 0, 1C. 0, 1,0D. 1,0,0 3・ 卜'列公式(] )为重言式. A. -iP/\-QB. (Q T (/VQ)) *0如0)C.D. (-1Pv(PAe )) 4. 下列等价公式成立的为(). A. -I P A -I Q O P V 0 B. P T (-I Q T P) O 「P T (P T Q)1-设P ：我将去市里，Q ：我有时间・命题“我将去市里，仅当我有时间时” C. Q T (P V Q) o-iQMPvQ) D. ^P V (P A 2)5. 命题公式TPT 2)的主析取范式是().A. P A -QB. -P N QC. -F 、Q 6. 命题公式(PVQ) -/?的析取范式是( )D. Pv-.O A.「(PVQ) V/? C ・(PVQ) V/? 7. 设C(%): x 是国家级运动员, 运动员不是健壮的”可符号化为( A. ―Vx(C(x) A ―G(x)) C. ―3x(C(x) —> ―G (兀)) 8. 设A (x):兀是人，B (x)5.设个体域D={\, 2},那么谓词公式v \fyB(y)消去量词后的等值式为⑵)\/(B⑴人B(2)) •6.设个体域D={a, b, c},则谓词公式(X/x)Ad)消去量词后的等值式为A(d)人A (Z?)心(c ) ・7.设个体域D={a, b},则谓词公式(Vx)A(x) A ( 3% ) B ( % )消去量词后的等值式为.8.设个体域D={1,2},则谓词公式BxA(x)消去量词后的等值式为—A 仃)\/A(2)・9•谓词命题公xl：(Vx)(P(x)->2(x)V/?(x, y))中的约束变元为兀•10. (Vx)(P(x)^e(x)V/?(x, y))中的自由变元为 /?% y )中的y ・三、公式翻译题1 •请将语句“今天不是天晴”翻译成命题公式・1・解：设P:今天是天晴；则-iP・2.将语句“今天没有下南・”翻译成命题公式.2.解：设P：今天下雨，则「P・3.将语句“今天没有人來・”翻译成命题公式.3.解：设P：今天有人來，则-iP・4.将语句“他不去学校・”翻译成命题公式.4.解：设P：他去学校，则"5.将语句“尽管他接受了这个任务，但他没有完成好・”翻译成命题公式.5.解：设戸他接受了这个任务，Q：他完成好了这个任务，则P^Q.6.将语句“小王去旅游，小李也去旅游・”翻译成命题公式.6.解：设小王去旅游，Q：小李去旅游，则P A Q.7.将语句“他去旅游，仅当他有时间・”翻译成命题公式.7.解：设P：他去旅游，Q：他有时间，则P—Q・8.请将语句“我去书店，仅当天不下雨”翻译成命题公式・8.解：设P：我去书店，Q：天不下雨，则P T Q.9.将语句“如果所有人今天都去参加活动，则明天的会议取消•”翻译成命题公式.9.解：设所有人今天都去参加活动，Q：明犬的会议取消,则P T Q・10.将语句“如果你去了，那么他就不去•”翻译成命题公式.10.解：设P：你去，Qz他去，则P T「Q.11•请将语句“有人不去工作”翻译成谓词公式.11•解：设P(x)： x是人，Q(x)：无去工作，贝I」(3x)(P(x) AH Q(x)).12.将语句“有人去上课・”翻译成谓词公式.12.解：设P(x)：兀是人，Q(x)： x去上课，则0x)(P(x) A2(X)). 13•请将语句“所有人都努力工作・”翻译成谓词公式・13.解：设P(x)：兀是人，Q(x)： x努力工作.则(Vx)(P(X)T 2(%)).14.将语句“所有人都去工作•”翻译成谓词公式.14.解：设兀是人，Q(x)：无去工作，则(vx)(p(x)^e(%)).15.将语句“所有的人都学习努力・”翻译成命题公式.15.解：设P⑴：兀是人，Q(x):兀学习努力，贝I」(Vx) (P9)T Q(X))・四、判断说明题(判断下列各题，并说明理由・)1.命题公式7Q T P)A P为永假式.1.解：正确因为，由真值表P Q Q T P「（Q T P）「( Q T P)人P0 0 1 0 00 1 0 1 01 0 1 0 01 1 1 0 0可知，该命题公式为永假式.2.命题公式P/\ Q) \/P为永真式.2.解：正确.-1 PA (P—| 2)VF 是dhi PA (P—-I 2)与P 组成的析取式，如果P的值为真，则1 PA (P-i Q) VP为真，如果P的值为假，贝归P与P—1 Q为真,即1 PA (P-1 0)为真,也即i PA (P-n 2)VP为真，所以i PA (P-n 2)VP是永真式.另种说明：-i PA (P-n 2)VP是由1 PA (P—i 0)与P组成的析取式，只耍其中一项为真，则整个公式为真.可以看到，不论P的值为真或为假，(P—1 2)与P总有一个为真, 所以1 PA (P-n 2)VP是永真式.或用等价演算-1 PA (P-n 2)VP«T3•下而的推理是否正确，试予以说明.(1)(Vx) F -G (x) 前捉引入(2) F (y) -G (y) US (1).3.解：错误.(2)应为F (y丿->G (x),换名时，约束变元与自由变元不能混淆.五•计算题1.(1)求命题公式TP T Q)人(P TF2)的主析取范式、主合取范式；(2)求该命题公式的成假赋值.1・解：(1) 0 A (P V 2) A (-.P V -.Q)O (P A-)Q)/\(-I P\/-I Q) O (P A -yQ A -I P) v (P A -ig A -\Q) O(P A「Q)(主析取范式)o (P V (Q 人「Q))人((P 人「P) V「Q)« (Pvg) A(Pv -10 A(P V iQ) A(-|P V iQ) o (P V Q)人(P V「Q) A (「P V「Q) (主合取范式)(2)因为命题公式的成真赋值是(1,0), 所以它的成假赋值是(0, 0), (0, 1), (1, 1).2.求公式(P A Q)T R的析取、合取、主析取、主合取范式.2.解：(Pg T R o十八①^ Ro (―iPv-i0 v R O rPv -yQ\/ R (析取、合取、主合取范式) O鬥P/M-1 eve)A(-i /?V/?))V((-1 PVP)An 2A(n /?V/?))V((n PVP) Ah eve)A/?) PN-\ eAn /?)V(-1 PA-] 2A/?)V(-| PAgAq /?)V(n P/\Q/\R) V(PA-1 2A-I /?)V(PA-1 eA7?)V(PAeA7?) (主析取范式)3.求P T Q P R的析取范式，合取范式、主析取范式，主合取范式.3.解：p-(/?ve)pv(/?ve)O -1 PVgV/? (析取、合取、主合取范式)o(i PAn 2A-i /?)V(-i PA-i Q^R) V(n PAgA/?) V (-1 PAgA-i /?)V(PA-i 2A/?)V(PAeA-i R) V(PAQA/?)(主析取范式)4•试求出(PVQ) -/?的析取范式，合取范式，主合取范式.4.解：(PVQ) (PV0V/?« (n PAn Q)V/?(析取范式)o 鬥PV/?)A (n SV/?)(合取范式)o(鬥PV/?)V(2A-i 2))A ((-i eV7?)V(PA-i P)) o(「PV/?Ve)A(-i PV/?Vn e)A (n 2V/?VP) A(-1 ev/?v-i P)0(-1 pvev/?)A(-i pvn ev/?)A(pv-i ev/?) (主合取范式)5.求(PVQ) f (/?ve)的合取范式.5.解：(PV2)f(/?ve) o-i (pve) v(/?ve)O(「P/\「Q)V(/?ve) «(^pv/?ve)A(-ievRve)«(-^v/?ve)合取范式6・设谓词公式3x(P(%, y) t X/zQ(y,兀,z)) A V.y/?(y, z)导F(y)・试(1)写出量词的辖域；(2)指出该公式的自由变元和约束变元.6.解：(1) 3x量词的辖域为(P(x,y)T VzQ(y,兀,z)),Vz量词的辖域为Q(y,x,z), 量词的辖域为R(”z)・(2)自由变元为(P(x,y) T VzQ(y,x,z))与F(y)中的y,以及R(y,z)中的z 约束变元为(P(x, y) -> VzQ(y,x,z))中的兀与Q(y,x, z)中的z,以及R(y,z)中的y・六、证明题1.试证明命题公式(P T(Q—R))人与「(P—Q)等价.1.证明：(P T(Q—R)”「P八Qo(「Pp(QgR)2P八Q Qv—iR) A-I P A Q«(—)P A-I P A0V(2A-I P A0V(-I/?A—)P A0<=>(-I P A0V(-I P A0V(-I P A Q A-I7?)(吸收律) ofPviQ) (摩根律)2.试证明Ox) (P (x) A/? (x) ) => (3x) P (x) A (3x) R (兀) 2.证明：'〔1) (3x) (P (x) /\R (x)) P(2) P (a) A/? (a) ES(1)(3) P (a) T(2)I(4) (3x) P(x) EG(3)(5) R (a) T(2)I(6) Ox) R(x) EG(5)P(x) A (3x) R (%)T(5)(6)I(7) （玉）。

离散数学考试试题及答案离散数学是一门涉及离散结构和逻辑推理的数学学科。

它在计算机科学、信息技术和其他领域中具有重要的应用价值。

离散数学考试试题涵盖了离散数学的各个方面，包括集合论、图论、逻辑、代数结构等。

本文将为大家提供一些离散数学考试试题及答案，希望能帮助大家更好地理解和掌握这门学科。

一、集合论1. 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A与B的交集、并集和差集。

答案：A与B的交集为{3,4,5}，并集为{1,2,3,4,5,6,7}，A与B的差集为{1,2}。

2. 设集合A={x|x是正整数，1≤x≤10}，B={x|x是偶数，2≤x≤8}，求A与B的笛卡尔积。

答案：A与B的笛卡尔积为{(1,2),(1,4),(1,6),(1,8),(2,2),(2,4),(2,6),(2,8),...,(10,2),(10,4),(10,6),(10,8)}。

二、图论1. 给定图G，其邻接矩阵如下：| 0 1 1 0 || 1 0 0 1 || 1 0 0 1 || 0 1 1 0 |判断图G是否是连通图，并给出其连通分量。

答案：图G是连通图，其连通分量为{1,2,3,4}。

2. 给定图G，其邻接表如下：| 1 | 2 || 3 | 2 4 || 4 | 3 |判断图G是否是树，并给出其生成树。

答案：图G是树，其生成树为{1-2, 2-3, 3-4}。

三、逻辑1. 判断命题逻辑公式((p∨q)→r)∧(¬p∨¬q)的真值。

答案：命题逻辑公式((p∨q)→r)∧(¬p∨¬q)的真值为真。

2. 判断命题逻辑公式∀x(P(x)∧Q(x))→(∀xP(x)∧∀xQ(x))的真值。

答案：命题逻辑公式∀x(P(x)∧Q(x))→(∀xP(x)∧∀xQ(x))的真值为假。

四、代数结构1. 设集合S={0,1,2,3,4}，定义运算*如下：a*b = (a+b)%5其中%表示取余运算。

《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式?x((A(x)?B(y，x))??z C(y，z))?D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。

在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。

于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。

）6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

离散数学复习题含答案1. 集合论基础集合A和集合B的交集表示为A∩B，它包含所有既属于A又属于B的元素。

请写出集合{1, 2, 3}和{2, 3, 4}的交集。

答案：{2, 3}2. 逻辑运算设命题p为“今天是周一”，命题q为“明天是周三”。

请判断复合命题“p且q”的真值。

答案：假3. 图论初步在无向图中，若存在一条路径使得起点和终点相同，则称该图为欧拉图。

请判断一个有5个顶点且每个顶点的度均为2的无向图是否一定是欧拉图。

答案：是4. 组合数学从5个不同的球中选取3个，有多少种不同的选取方法？答案：10种5. 布尔代数在布尔代数中，逻辑或运算符表示为∨，逻辑与运算符表示为∧。

请计算表达式(A∨B)∧(¬A∨¬B)的值。

答案：¬(A∧B)6. 归纳与递归给定递归关系式T(n) = 2T(n-1) + 1，初始条件为T(1) = 1，求T(3)的值。

答案：T(3) = 2T(2) + 1 = 2(2T(1) + 1) + 1 = 2(2*1 + 1) + 1 =2(3) + 1 = 77. 有限状态机在有限状态机中，状态转移可以通过一个转移函数来描述。

若状态转移函数定义为δ(q, a) = q'，其中q和q'是状态，a是输入符号，请说明该函数的作用。

答案：该函数定义了在给定当前状态q和输入符号a的情况下，有限状态机将转移到新的状态q'。

8. 正则表达式正则表达式用于描述字符串的模式。

请写出匹配任意长度的数字串的正则表达式。

答案：\d*9. 命题逻辑命题逻辑中的等价关系是指两个命题逻辑表达式在所有可能的真值赋值下具有相同的真值。

请判断命题p∨¬p和命题¬(p∧¬p)是否等价。

答案：是10. 树的遍历在计算机科学中，树的遍历有前序、中序和后序三种方式。

请简述后序遍历的步骤。

答案：后序遍历的步骤是先访问左子树，然后访问右子树，最后访问根节点。