2017离散数学复习题
题型
一、填空题
1、设集合A有n个元素，那么A的幂集P(A)的元素个数为____________。
2、谓词公式?xF(x)→Q(x,y)中的前束范式为______________。
3、设集合A＝{a,b,{a,b}}，B＝{{a,b}},则B-A=_____________。
4、设集合A＝{0,1}，B＝{1,2},则A×B=_____________________________________。5．已知图G中有1个1度结点，2个2度结点，3个3度结点，则G的边数是。
二、单项选择题
1、下列各命题中真值为真的命题有（）。
A. 2+2=4当且仅当3是奇数
B. 2+2=4当且仅当3不是奇数
C. 2+2≠4当且仅当3是奇数
D. 2+2=4仅当3不是奇数
2、设个体域D={a,b}，与公式)
?等价的公式是( )。
xA
(x
A. )
a
A
A∨ D. )
)
(
(b
(a
A→
b
A
(
)
(b
A
a
(b
A→ C. )
(
A∧ B. )
)
A
a
)
(
3、令F(x):x是人，G(x):x是犯错误，则命题“没有不犯错误的人”可符号化为（）。
A.))
G
)
x
(
→
(
??
x?
F
(x
(
)
(
(x
G
x∧
F
x
? B.))
C.))
(x
(
)
G
x
∧
x?
F
(
??
(
)
(
(x
G
x∧
F
x
?? D.))
4、下列命题公式不是永真式的是( )。
A. p
∨
p→
q
? D. p
q
(
→)
p∨
→ C. )
→)
p→
q
( B . )
(p
p→
q
(p
5、设X={1,2,3},Y={a,b,c},f={<1,b>,<2,a>,<3,a>},则以下命题正确的是( )。
A．f是从X到Y的二元关系，但不是从X到Y的函数
B．f是从X到Y的函数，但不是满射的，也不是单射的
C．f是从X到Y的满射，但不是单射D．f是从X到Y的双射
6、设集合A={a, b, c}，A上的二元关系R={
A.自反的
B.对称的
C. 传递的
D.反对称的
7、设集合A={1,2,3,4}，A上的等价关系R={ <3,2>, <2,3>}Y I A，则对应于R的划分是（）。
A. {{1},{2,3},{4}}
B. {{1,3},{2,4}}
C. {{1,3},{2},{4}}
D. {{1},{2},{3},{4}}
8、图G 1如图1所示，以下说法正确的是( )。 A. a 是割点 B. {b,c }是点割集 C. {b,d }是点割集 D. c 是割点
9、设集合S ={1,-1}，下面定义的哪种运算关于集合S 是封闭的( )。 A. 普通的减法运算 B. 普通的加法运算 C. 普通的乘法运算 D. 以上均不是
10、集合A={2,3,6,12,24,36}上的偏序关系R 的哈斯图G 2如图2所 示，则集合B={2,3,6}的最小元为（ ）。 A. 2 B. 3 C. 2和3 D. 不存在
三、推理及证明题
1、已知A ，B ，C 是三个集合，证明：A-(B Y C)=(A-B)-C.
2、构造下面推理的证明。
前提：A ，A→B ，A→C ，B→(D→?C) 结论：?D
四、综合应用题
1、利用等值演算法求命题公式（P ∨Q ）→R 的主合取范式并给出其成真赋值和成假赋值。
2、设集合Ａ={a ，b ，c }上的二元关系R={?a ，b ?，?b ，a ?，?b ，c ?}，求R 的自反闭包r (R )，对称闭包s (R )及传递闭包t (R )。
3、设有向图D 如图G 3所示,回答下列问题： （1）求图D 的邻接矩阵；
（2）求图D 中长度为2的通路数； （3）求图D 中长度为2的回路数； （4）求图D 的可达矩阵。
图2 G 2
24
36
12 6 2
3 图1 G 1
d
c a
b
4、如图4-1和图4-2所示的两个图G 4，G 5： （1）试判断它们是否为欧拉图？并说明理由； （2）若是欧拉图，请写出一条欧拉回路；
（3
图4-1 G 4
图4-2 G 5
5、设R 为实数集合，在R 上定义二元运算*，R y x ∈?,，有
xy y x y x ++=*
（1）验证二元运算*是否满足结合律； （2）求二元运算*的单位元； （3）对实数x ，求其逆元。
离散数学期末考试复习题
一、填空题
1、谓词公式((,)(,))(,)
??∧→?中x?的辖域是。
x y P x y Q y z xR x y
2、将以下命题进行命题符号化为______________________。
(1) 李平不但聪明又用功。
(2) 李平虽然聪明，但不用功。
(3) 李平不但聪明，而且用功。
(4) 李平不是不聪明，而是不用功。
3、将以下命题进行命题符号化为______________________。
(1) 人不犯我，我不犯人；人若犯我，我必犯人。
(2) 不经一事，不长一智。
4、命题公式p q
( )的成真赋值为_______________________。
∨?
5、命题公式()()
∧?∨?∧?的成真赋值为___________________。
p q p q
6、将命题“没有一个运动员不是强壮的”谓词符号化为___________________。
7、给定简单命题函数：
A(x)：x身体好，B(x)：x学习好，C(x)：x工作好，
复合命题函数?A(x)→(?B(x)∧?C(x))表示的含义是：________________。
8、将下列命题符号化：________________。
(1)偶数均能被2整除. (2)存在着偶素数. (3)没有不吃饭的人.(4)素数不全是奇数.
9、公式()()
?→?的前束范式为_____________________________。
xP x xQ x
10、谓词公式?(?xF(x，y)∨?yG(x，y))的前束范式为。
11、在1和1000之间（包括1和1000在内）不能被4和5整除的数有个。
12、若集合A＝{a,b},B＝{0,1,2},则A×B为______________________；B×A为
______________________。
13、设集合A = {1, 2}，则P(A)为________________；P(A)×A为
_______________________。
14、设集合A={0, 1}, B={1, 2}, C={0, 1, 2} ，则A, B和C的笛卡尔积A×B×C为：
________________________。
15、请用谓词表达式（或枚举方式）描述实数集上子集A上的小于等于关系
__________________；正整数集合的子集B上的整除关系
____________________；集合C的幂集上的包含关系_________________；集合D={1,2,3,4,5,6,7}上的模3同余关系__________________________。
A=上的二元关系
16．设R是定义在集合{1,2,3,4}
s R=_______________。
R=<><><><>，则R的对称闭包()
{1,1,1,2,2,3,1,4}
17、命题“所有的人都是要死的”的否定的含义是___________。
18、设集合A中有m个元素，集合B中有n个元素，则集合A和集合B的笛卡尔积
A×B中含有___________个元素，定义在集合A和集合B上不同的二元关系有___________个，从集合A到集合B不同的函数有___________个。
19．无向连通图是欧拉图的充分必要条件是____________________。
20．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则
G 的边数是 ．
21．设给定图G (如下图所示)，则图G 的点割集是 ．
22．设无向图G ＝
24．设完全图K n 有n 个结点(n ≥2)，m 条边，当 时，K n 中存在欧拉回路．
n n 乘法，则n Z 对⊕运算的单位元是______， n Z 对?的单位元是_______。
28．设G={1 , 2 , 3 , 4 , 5, 6}，G 关于模7乘法构成代数系统，群G 的幺元是_________，元素3与______互为逆元。
二、单项选择题
1、下列句子中有（ ）个是命题。 (1) 我是老师。(2) 禁止吸烟! (3) 蚊子是鸟类动物。(4) 月亮比地球大。A. 1 B . 2 C. 3 D. 4
2、下列公式中，哪个是永真式（ ）
A. ()q p q →∧
B. ()p q p ∧→
C. ()p p q →∧
D. ()p q q ∨→
3、 设()F x : x 是有理数，()G x ：x 能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为( )。
A. (()())x F x G x ??∧?
B. (()())x F x G x ??→?
C. (()())x F x G x ??∧?
D. (()())x F x G x ??→?
4、 设个体域是整数集，则下列命题的真值为真的是( )。 A ．(1)y x x y ???= B ．(0)x y x y ???≠ C ．2()x y x y y ???= D ．2()y x x y x ???=
5、下列命题中为假命题的是( )（其中P （A ）为A 的幂集）
A ．{}()P ?∈? B. ({})P ??? C. (){}P ??? D.()({})P P ?∈?
6、 集合{1,2,,10}A =L 上的关系{,|10,,}R x y x y x y A =<>+=?∈，则R 的性质为( )。
A 、自反的
B 、传递的、对称的
C 、对称的
D 、反自反的、传递的 7、设,,R Z N 分别表示实数、整数和自然数集， 设函数1:{0,1,2}f N →，()mod3f x x =，（x 除以3所得的余数），
2:,()2x f R R f x →=，3:,()||f Z N f x x →=，4:f N N N →?，(),1f x x x =<+>
ο ο ο ο ο c a
b e d
ο f
则上述函数中满射的个数为（ ）。
A ．1 B. 2 C. 3 D. 4
8、设R 和S 定义在P 上，P 是所有人的集合。{}的父亲是y ,|,x P y x y x R ∧∈><=，{}的母亲是y ,|,x P y x y x S ∧∈><= ，则对于R S y x ο1,->∈<表示( ) A.x 是y 的丈夫 B .x 是y 的妻子 C. x 是y 的孙子 D.x 是y 的祖母
9、设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}，则h =（ ）． A. f?g B. g?f C. f?f D. g?g 10．设图G 的邻接矩阵为
则G 的边数为( )．
A ．5
B ．6
C ．3
D ．4 11．图G 如右图所示，以下说法正确的是 ( ) ．
A ．{(a , d )}是割边
B ．{(a , d )}是边割集
C ．{(d , e )}是边割集
D ．{(a, d ) ,(a, c )}是边割集
12．无向图G 存在欧拉通路，当且仅当( )．
A ．G 中所有结点的度数全为偶数
B ．G 中仅有有两个奇数度结点
C ．G 连通且所有结点的度数全为偶数
D ．G 连通且仅有两个奇数度结点
13．设S={a,b}，则S 上总共可定义的二元运算的个数是（ ） A.4 B.8 C.16 D.32
14．设集合{1,2,3,...,10}A =，下面定义的哪种运算关于集合A 是不封闭的（ ）。 A ．*max{,}x y x y = B ．*min{,}x y x y = C ．*(,)x y GCD x y = 即,x y 的最大公约数 D ．*{,}x y LCM x y = 即,x y 的最小公倍数
15．在自然数集N 上，下列哪种运算是可结合的？（ ） A.a *b =a -b B.a *b =max{a ,b } C.a *b =a +2b D.a*b =|a-b |
16．设ο是正整数集+
Z 上的二元运算，其中{}b a b a ,m ax =ο（即取a 与b 中的最大者），那么ο在+
Z 中（ ）
A ．不适合交换律；
B ．不适合结合律；
C ．存在单位元；
D ．每个元都有逆元。 三、计算题
1、 求命题公式()()p q p r →∧→的主析取范式，主合取范式及其成真成假赋值。
2、 求命题公式p r q p →→∨))((的主析取范式，主合取范式及其成真成假赋值。
3、 求命题公式R )Q P (→?主析取范式，主合取范式及其成真成假赋值。
4、 求命题公式p → (q → r)主析取范式，主合取范式及其成真成假赋值。
5、给定集合A={a,b,c,d}，给出A 上的所有等价关系。
6、给定集合A={a,b,c}，给出A 上的所有等价关系。
7、设A={a,b,c,d}。下列哪个是A 的划分,请说明原因？若是划分，则求其诱导的等价关系？
（1）B={{a},{b,c},{d}}; （2）C={{a,b},{c},{a,d}}; （3）D={{a},{b,c}}
8、设,A R <>为偏序集，其中{1,2,3,4,6,9,24,54}A =，R 是A 上的整除关系。（1）画出,A R <>的哈斯图；（2）求A 中的极大元最大元、最小元、极大元、极小元。 9、设集合}36,18,12,9,6,4,3,2,1{A =，R 为A 上的整除关系，则R 为偏序关系。 1) 求该关系的哈斯图； 2) 令{2,3,6}B =，求B 的最大元、最小元、极大元、极小元、上界，上确界，，下界和下确界。
10、 设集合{,,,}A a b c d =，R 为A 上的二元关系，且{(,),(,),(,),(,)}R a b b c c a d d =， 1) 求R 的关系矩阵； 2) 求R 的性质；
3) 求R 的自反闭包，对称闭包以及传递闭包t(R)； 11、 给定解释I 如下：
(1) D1={2,3}； (2) D1中特定元素a=2； (3) 函数f(x)为f(2)=3,f(3)=2；
(4)谓词F(x)为F(2)=0;F(3)=1;G(x,y)为G(i,j)=1,i,j=2,3;
L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0;
在解释I 下，求下列各式的真值。
1))),()((x a x G x F ∧?
2))));(,())(((x f x G x f F x ∧? 3)),(y x yL x ??
12、求出下列公式的前束范式
1) )()(x xG x xF ??∧? 2))()(x xG x xF ??∨?
3))()(x xG x xF ?→? 4)),()(y x yG x xF ?→??
5)),,()),,()((z y x zH z y x yG x F x ?→?∧?
13、求1到1000之间不能被5、6、8整除的数的个数。
14、设A ＝{a,b,c,d},R ＝{
的关系图。
15、设图G =
（1）试给出G 的图形表示；
（2）求G 的邻接矩阵，关联矩阵；
（3）判断图G 是强连通图、单侧连通图还是弱连通图？
16、设有向图D 如右图所示，求图D 中长度为3的通路数， 并指出其中的回路数．
17、在实数集合R 上定义二元运算*226X Y XY X Y =--+ （1） 验证*是否满足交换律和结合律。 （2） 求*的单位元。
（3） 对任何实数X ，求其逆元。
18、设代数系统,*A <>，其中{,,,}A a b c d =，*运算定义如下表，请指出*运算是否是可交换的；是否有单位元；如果有单位元，指出哪些元素是可逆的，并给出它们的逆元。
*a b a b c d
a b c d
b c d c d a
c d a b
d a b c
19、设V=
（2）*是否有零元和幺元？若有幺元，请求出所有可逆元素的逆元。 20、设Z 为整数集合，在Z 上定义二元运算*，，Z y x ∈?,，有
2*-+=y x y x ，
（1）二元运算*满足结合律吗？
（2）二元运算*是否有零元和幺元？若有幺元，请求出所有可逆元素的逆元。 （3）Z 与二元运算*是否构成群，为什么。 22、学生会下设6个委员会, 第一委员会={张, 李, 王}, 第二委员会={李, 赵, 刘}, 第三委员会={张, 刘, 王}, 第四委员会={赵, 刘, 孙}, 第五委员会={张, 王}, 第六委员会={李, 刘, 王}. 每个月每个委员会都要开一次会, 为了确保每个人都能参加他所在的委员会会议, 这6
个会议至少要安排在几个不同时间段?
23、某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、香港去开会，每个地方只能去一人. 已知a只想去上海，b只想去广州，c, d, e都表示想去广州或香港. 问该课题组在满足个人要求的条件下，给出一种派遣方案？
24、有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日语和俄语, G会讲法语和德语. 问能否将他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人交谈?
25、画出下面平面图的对偶图
四、推理及证明。
1、如果我上街,我一定去新华书店.我没上街,所以我没去新华书店.
2、若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。
3、如果今天是星期一,则要进行英语或离散数学的考试.如果英语老师有会,则不考英语.今天是星期一,英语老师有会,所以进行离散数学的考试.
4、构造下面推理的证明
前提：q→p，q ? s，s ? t, t ∧ r
结论：p ∧ q ∧ s ∧ r
5、判断下列推理是否正确。先将命题符号化，再写出前提和结论，然后进行判断。
a)如果今天是1号，则明天是5号，今天是1号，所以明天是5号。
b)如果今天是1号，则明天是5号，明天是5号，所以今天是1号。
c)如果今天是1号，则明天是5号，今天不是1号，所以明天不是5号。
d)如果今天是1号，则明天是5号，明天不是5号，所以今天不是1号。
6、构造下面推理的证明
前提：P→Q，?(Q∨R)
结论：?P
7、构造下面推理的证明
前提：(P∧Q)→R，?R∨S，?S，P
结论：?Q
8、构造下面推理的证明
前提：A→B∧C, ?B∨D , (E→?P)→?D, B→A∧?E
结论：B→E
9、给定集合A，证明P(A)上的包含关系为偏序关系。
10、给定有限集合A，证明A上的小于等于关系≤为偏序关系。
11、设,A R
<>为偏序集，其中}9,8,7,6,5,4,3,2,1{
A，R是A上的整除关系，试证明
=
R为偏序关系。
12、令I是整数集合，I上关系R定义为：R={
13、已知A 、B 、C 是三个集合，证明以下集合恒等式。 A ∩(B ∪C)=(A ∩B)∪(A ∩C) A ∪(B ∩C)=(A ∪B)∩(A ∪C) A-(B ∪C)=(A-B)∩(A-C) A-(B ∩C)=(A-B)∪(A-C)
14、若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的．
15、设G 是一个n 阶无向简单图，n 是大于等于2的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．
16、设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2
k
条边才能使其成为
欧拉图．
17、设G 为n 阶无向连通简单图, 若G 中有割点或桥, 则G 不是哈密顿图. 18、证明K 5 和 K 3,3不是平面图. 五、判断题
1、下列命题公式的类型，若为可满足式，给出成真赋值
1) ;q q)(p ∧→? 2) ;))((q p q p →∧→
3) ;)(q q p ∧→
4) ));(),(()(x xF y x yG x x xF ?→??→? 5) );,()),(),((y x R y x R y x F ∧→? 6) );()(x xF x xF ?→? 7) );()(y F x xF →? 8) );()(y F x xF →? 9) )(r q p →→
10) )()(r p q p →∧→
11) );()(p q q p ∨?→→?
2、如何判断一个二元关系是否具有自反性、反自反性、对称性、反对称性以及传递性（给出一种方法即可）。
3、设集合A={1,2,3},A 上关系R 1，R 2,R 3，R 4，....判断其各有哪些性质(用二进制码依次对是否具有自反、反自反、对称、反对称、传递性质进行标示)：
R 1={<1,1>, <1,2>, <2,1>}; R 2={<1,2>, <2,3>, <1,3>}; R 3={<1,1>, <3,3>};
R 4={<1,1>, <2,2>, <3,3>, <1,2>, <1,3>, <2,1>}; R 5={<1,2>, <2,1>,<2,3>, <1,3>};
R 6={<1,1>, <2,2>, <3,3>, <1,2>, <1,3>}; ......
4、判断以下f 、g 、h 是否为从A 到B 的函数，若是，再判断是否是单射、满射或双射；若不是，请说明理由。 1) A={1,2,3,4,5}，B={6,7,8,9,10}，f={<1,8>, <3,9>, <4,10>, <2,6>, <5,9>}。
2) A={1,2,3,4,5}，B={6,7,8,9,10}，g={<1,8>, <3,10>, <2,6>, <4,9>}。
3) A={1,2,3,4,5}，B={6,7,8,9,10}，h={<1,7>, <2,6>, <3,8>, <4,5>, <1,9>, <5,10>}。
4) A=B=R(实数集)， f(x)=x2-x。
5) A=B=R(实数集)， f(x)=x3。
6) A=B=R(实数集)， f(x)=x。
5．给定两个图G1，G2（如下图所示）：
（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由．
（2）若是欧拉图，请写出一条欧拉回路．
离散数学试卷答案2017.6月
浙江农林大学暨阳学院 2016 - 2017 学年第 二 学期考试卷答案 课程名称： 离散数学 课程类别： 必修 考试方式： 闭卷 适用专业： 计算机151-152 注意事项：1、本试卷满分100分。 2、考试时间 120分钟。 一、单项选择题（在每小题的四个备选答案中，选出一个正确答案， 并将正确答案的选项填在题后的括号内。每小题2分，共8分） 1. 公式q p p ?→?→)(的类型是 ( C ) A. 重言式 B. 矛盾式 C. 非重言式的可满足式 D. 以上均不对 2. |A |=n , |B |=m , 且m , n >0, 则|B A |= ( D ) A.m 2 B. 2n C. n m D. m n 3. 集合的广义并}},{},,,{},,,{{d a d c a c b a ?= ( B ) A.},,{c b a B.},,,{d c b a C.},,{d c a D.}{a 4. f ：R→R, f (x )=-x 2+2x -1，则f 是 ( D ) A. 单射 B. 满射 C. 双射 D. 以上均不对 系（部） ： 专业班级： 姓名： 学号： 装 订 线 内 不 要 答 题
二、填空题（每小题3分，共36分） 1. 令p:吴颖用功, q:吴颖聪明，吴颖既用功又聪明符号化为__q p ∧_____ 2. 如果2 <1,则23≥的真值为___1___ 3. (q →p ) ∧q →p 的成真赋值为 ___00,01,10,11_ __ 4. (p →?q)→r ? 13567m m m m m ∨∨∨∨的成假赋值为__000,010,100_ 5. 设A 有3个命题变项, 且已知A= m 2∨m 4∨m 5∨m 6，A 的主合取范式为 ___7310M M M M A ∧∧∧= 6. 设D 为人类集合，G(x)：x 用左手写字，则一阶逻辑中命题有人用左手写字符号 化为__)(x xG ?__ _ 7. 给定解释 I 如下： (a) 个体域 D=R (b) 0a = (c) (,),(,)f x y x y g x y x y =+=? (d) (,):F x y x y = 则公式?xF (g (x ,y ),a ) 在I 下的解释为__)0(=??y x x _____ 8. R = {<1,2>, <2,3>, <1,4>, <2,2>}，S = {<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}， 则S ?R = __{1,2,1,4,3,3,3,2}<><><><>__ 9. 设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}, 则R ?{2} = ___}4,2,2,2{><><___ 10. 设R 为A 上的关系, 则有R 的对称闭包s(R)=__ 1-?R R ____ 11. 设G=
离散数学期末试题
离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。
离散数学模拟题一套及答案
离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())
下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<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>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
2017离散数学答案(6--10)
04任务_0006 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )． A. （a）只是弱连通的 B. （b）只是弱连通的 C. （c）只是弱连通的 D. （d）只是弱连通的 2. 设无向图G的邻接矩阵为 ， 则G的边数为( )． A. 1 B. 6 C. 7 D. 14
3. 设无向图G的邻接矩阵为，则G的边数为( )． A. 6 B. 5 C. 4 D. 3 4. 无向简单图G是棵树，当且仅当( )． A. G连通且边数比结点数少1 B. G连通且结点数比边数少1 C. G的边数比结点数少1 D. G中没有回路． 5. 图G如图三所示，以下说法正确的是 ( ) ． A. {(a, d)}是割边 B. {(a, d)}是边割集 C. {(a, d) ,(b, d)}是边割集 D. {(b, d)}是边割集 6. 若G是一个汉密尔顿图，则G一定是( )． A. 平面图
B. 对偶图 C. 欧拉图 D. 连通图 7. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )． A. e－v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2 8. 无向完全图K4是（）． A. 欧拉图 B. 汉密尔顿图 C. 非平面图 D. 树 9. 设图G＝
自考离散数学试题及答案
一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．． 命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．． 谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ??????001110101 B ．??????????101110001 C ．??????????001100100 D ．???? ??????001010101 9．设R 1和R 2是集合A 上的相容关系，下列关于复合关系R 1?R 2的说法正确的是（ ） A ．一定是等价关系 B ．一定是相容关系
离散数学模拟试题讲解
1 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f
2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 02任务_0001 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={ 5. 设集合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. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 06任务_0001 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 命题公式的析取范式是( )． A. B. C. D. 2. 设个体域为整数集，则公式"x$y(x+y=0)的解释可为( )． A. 存在一整数x有整数y满足x+y=0 B. 任一整数x对任意整数y满足x+y=0 C. 对任一整数x存在整数y满足x+y=0 D. 存在一整数x对任意整数y满足x+y=0 3. 下列公式成立的为( )． A. ?P∧?Q ?P∨Q B. P→?Q??P→Q C. Q→P? P D. ?P∧(P∨Q)?Q 4. 下列公式中( )为永真式． A. ?A∧?B ??A∨?B B. ?A∧?B ??(A∨B) C. ?A∧?B ?A∨B D. ?A∧?B ??(A∧B) 5. 设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符 号化为( )． A. B. C. D. 6. 命题公式(P∨Q)→R的析取范式是( ) A. ?(P∨Q)∨R B. (P∧Q)∨R C. (P∨Q)∨R D. (?P∧?Q)∨R 7. 命题公式（P∨Q）的合取范式是( )． A. （P∧Q） B. （P∧Q）∨（P∨Q） C. （P∨Q） D. ?（?P∧?Q） 8. 设命题公式G：，则使公式G取真值为1的P，Q，R赋值分别 是( )． A. 0, 0, 0 B. 0, 0, 1 C. 0, 1, 0 D. 1, 0, 0 9. 命题公式P→Q的主合取范式是( )． A. (P∨Q)∧(∏∨?Θ)∧(?∏∨?Θ) B. ?P∧Q C. ?P∨Q D. P∨?Q 10. 下列等价公式成立的为( )． A. ?P∧P??Q∧Q B. ?Q→P?P→Q C. P∧Q?P∨Q D. ?P∨P?Q 全国2009年4月自学考试离散数学试题（附答案） 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 2．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟 C．如果1+2=3，那么雪是黑的D．如果1+2=5，那么雪是黑的 3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q）D．?（? P∨? Q） 4．命题公式（P∧（P→Q））→Q是（） A．矛盾式B．蕴含式 C．重言式D．等价式 5．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 6．在公式（x ?）F（x，y）→（?y）G（x，y）中变元x是（） A．自由变元B．约束变元 C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元 7．集合A={1，2，…，10}上的关系R={ 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)( 全国2018年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是 ．．命题的是（） A．中华人民共和国的首都是北京B．张三是学生 C．雪是黑色的D．太好了！ 2．下列式子不是 ．．谓词合式公式的是（） A．（?x）P(x)→R(y) B．(?x) ┐P（x）?(?x)(P(x)→Q(x)) C．(?x)(?y)(P(x)∧Q(y))→(?x)R(x) D．(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z) 3．下列式子为重言式的是（） A．(┐P∧R)→Q B．P∨Q∧R→┐R C．P∨(P∧Q) D．(┐P∨Q)?(P→Q) 4．在指定的解释下，下列公式为真的是（） A．(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2} B．(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2} C．(?x)(P(x) →Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} D．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} 5．对于公式(?x) (?y)(P(x)∧Q(y))→(?x)R(x,y)，下列说法正确的是（） A．y是自由变元B．y是约束变元 C．(?x)的辖域是R(x, y) D．(?x)的辖域是(?y)(P(x)∧Q(y))→(?x)R(x,y) 6．设论域为{1,2}，与公式(?x)A(x)等价的是（） A．A(1)∨A(2) B．A(1)→A(2) C．A(1)∧A(2) D．A(2)→A(1) 7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（） 1 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF 离散数学综合练习题 一、判断下列命题是否正确．如果正确，在题后括号内填“\/”； 否则，填“?” （1）空集是任何集合的真子集． （ ） （2）{ }φ是空集． （ ） （3）{}{ }a a a },{∈ （ ） （4）如果B A a ??，则A a ?或B a ?． （ ） （5）设集合},,{321a a a A =，},,{321b b b B =，则 },,,,,{332211><><><=?b a b a b a B A （ ） （6）设集合}1,0{=A ，则 }1},0{,0},0{,1,,0,{><><><><=φφρ 是A 2到A 的关系． （ ） （7）关系的复合运算满足交换律． （ ） （8）设21,ρρ为集合 A 上的等价关系, 则21ρρ?也是集合 A 上的等价关系 ( ) （9）设ρ是集合A 上的等价关系, 则当ρ>∈?<,G 是群．如果对于任意G b a ∈,，有 222)(b a b a ?=? 则>?<,G 是阿贝尔群． （ ） （14）设a 是群>?<,G 的元素，记 }|{y a a y G y y H ?=?∈=且 则>?<,H 是>?<,G 的子群． （ ） （15）<{0，1，2，3，4}，max ，min>是格． （ ） （16）设a ，b 是格>∧∨<,,L 的任意两个元素，则 a b a b b a =∧?=∨． （ ） （17）设>∧∨<,,,B 是布尔代数，则>∧∨<,,B 是格． （ ） （18）设集合},{b a A =，则>??<,},},{},{,{A b a φ是格． （ ） （19）设>∧∨<,,,B 是布尔代数，则对任意B b a ∈,，有 b a b a ∨=∧． （ ） （20）设>∧∨<,,,B 是布尔代数，则对任意B a ∈，都有B b ∈，使得 0,1=∧=∨b a b a ． （ ） （21）n 阶完全图的任意两个不同结点的距离都为1. （ ） （22）在有向图中，结点i v 到结点j v 的有向短程即为j v 到i v 全国2010年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ? ?????001110101 B ．???? ? ?????101110001 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={2017离散数学答案(1--5)
离散数学期末试题及答案完整版
离散数学模拟试卷和答案
2017离散数学答案1--5)(2)
自考离散数学02324真题含答案(2009.4-2016.4年整理版)
离散数学期末试卷A卷及答案
离散数学模拟试题及答案
7月全国自考离散数学试题及答案解析
离散数学期末试卷及答案
离散数学考试试题(A、B卷及答案)
离散数学2017秋综合练习题
离散数学及答案
离散数学期末考试试题及答案