当前位置:
文档之家› 西工大明德学院离散数学试卷A
西工大明德学院离散数学试卷A
A.p∧┐p∧q B.┐p∨qC.┐p∧q D.┐p∨p∨q
2.设P:我将去镇上,Q:我有时间。命题“我将去镇上,仅当我有时间时”符号化为()
A.PQB.QPC.PQD.QP
3.谓词公式(x)(y)(A(x,y)B(y,z))(x)A(x,y)中量词(x)的辖域是()
A.(y)(A(x,y)B(y,z)) B.(y)(A(x,y) C.A(x,y)B(y,z)
设集合A={a,b,c},R是A上的二元关系,R={<a,a>,<a,b>,<a,c>,<c,a>},那么R是()
A.反自反的B.反对称的C.可传递的D.不可传递的
5.下列句子中,是命题的有
(1).我是教师。
(2).禁止吸烟!
(3).蚊子是鸟类动物。
(4).上课去!
(5).月亮比地球大。
6.设P:我生病,Q:我去学校
A.完全图B.零图C.简单图D.多重图
3.含5个结点、3条边的不同构的简单图有()
A.2个B.3个C.4个D.5个
4.任何无向图中结点间的连通关系是()
A.偏序关系B.等价关系C.相容关系D.拟序关系
2.
设A={1,2,3,4,5},ρ={<i,j>|i<j,i,jA},则的性质是()
A.对称的B.自反的C.反对称的D.反自反、反对称、传递的
由n个命题变元组成不等值的命题公式的个数为()
A.2nB.2nC.n2D.
1.设P:我将去镇上,Q:我有时间。命题“我将去镇上,仅当我有时间时”符号化为()
A.PQB.QPC.PQD.QP
2.设P:我们划船,Q:我们跑步。命题“我们不能即划船又跑步”符号化为()
A.pQB.PQC.(PQ)D.PQ
3.设P:张三可以作这件事,Q:李四可以作这件事。命题“张三或李四可以做这件事”符号化为()
14.设|V|>1,D=<V,E>是强连通图,当且仅当()
A.D中至少有一条通路
B.D中至少有一条回路
C.D中有通过每个结点至少一次的通路
D.D中有通过每个结点至少一次的回路
二、填空题(每空3分,共30分)
1.设F(x): x是人,G(x): x用右手写字,命题“有的人并不用右手写字”在一阶逻辑中符号化的形式为_______________。
A.x*y=max{x,y}
B.x*y=min{x,y}
C.x*y=GCD(x,y),即x,y的最大公约数
D.x*y=LCM(x,y),即x,y的最小公倍数
7.Q是有理数,(Q,*)(其中*为普通乘法)不能构成()
A.群B.独异点C.半群D.交换半群
8.R为实数集,运算*定义为:a,bR,a*b=a|b|,则代数系统(R,*)是()
C.如果2是奇数,那么一个公式的析取范式惟一
D.如果2是奇数,那么一个公式的析取范式不惟一
10.下列运算中,哪种运算关于整数集不能构成半群?()
A.aοb=max{a,b}B.aοb=b
C.aοb=2abD.aοb=|a-b|
11.设A={a,b,c}上的关系如下,有传递性的有()
A.ρ1={<a,c>,<c,a>,<a,b>,<b,a>}
A.半群B.独异点C.群D.阿贝尔群
下列代数系统(S,*)中,哪个是群?()
A.S={0,1,3,5},*是模7的加法
B.S=Q(有理数集合),*是一般乘法
C.S=Z(整数集合),*是一般乘法
D.S={1,3,4,5,9},*是模11的乘法
10.具有如下定义的代数系统(G,*),哪个不够成群?()
A.G={1,10},*是模11的乘法
2.设A={1,2,3},f,g,h是A到A的函数,其中f(1)=f(2)=f(3)=1;g(1)=1,g(2)=3,g(3)=2;h(1)=3,h(2)=h(3)=1,则①是单射;②是满射;③是双射。
3.设图D=<V,E>;V={v1,v2,v3,v4},若D的邻接矩阵 ,则deg-(v1)=①,deg+(v4)=②,从v2到v4长度为2的通路有③条。
(5).(PQ)(PQ)(PQ)
3.设(A,≤)是格,其中A={1,2,3,4,6,8,12,24},≤为整除关系,则3的补元是
28.用CP规则证明A(BC),(EF)C,B(AS)BE。
(P∧┐P)∨(P∧Q)
P∧(P→Q)
(P∨(┐Q∧Q))∧(┐P∨Q)
(P∨┐Q)∧(P∨Q)∧(┐P∨Q)
a)
其中|为整除关系,A={a,b,c}。
7.用谓词和量词将下列命题符号化:
(1).没有不犯错误的人;
(2).尽管有人聪明,但未必一切人都很聪明;
(3).每个计算机系的学生都学离散数学;
(4).所有的人都学习和工作;
(5).并非一切推理都能用计算机完成;
(6).任何自然数都有惟一的一个后继数。
2.设G=<V,E>为无环的无向图,|V|=6,|E|=16,则G是()
7.设A={a,b},则A上共有__________个不同的偏序关系。
8.设A={a,b,c},B={1,2,3},则A到B共可产生_____________个不同的双射函数。
9.设A是n(n≥1)元集,则A上共有22n个二元运算,其中有______________个是A到A的函数。
10.设A={1, 2, 3},在A上定义二元运算如下:" x,y ? A, x*y=min{x,y}则*的运算表为___________。
A.{R+中的有理数} B.{R+中的无理数}
C.{R+中的自然数} D.{1,2,3}
8.下列哪一组命题公式是等值的?()
A.PQ,PQB.A(BA),A(AB)
C.Q(PQ),Q(PQ)D.A(AB),B
9.下面哪一个命题是假命题?()
A.如果2是偶数,那么一个公式的析取范式惟一
B.如果2是偶数,那么一个公式的析取范式不惟一
B.y(G(y)x(F(x)H(x,y)))
C.xy(G(y)(F(x)H(x,y)))
D.y(G(y)x(F(x)H(x,y)))
2.f:ZZ,对任意的iZ,有f(i)=i(mod 8),则f是()
A.不是双射B.单射C.满射D.双射
2.设集合A={1,2,3,…,10},下面定义的哪种运算关于集合A是不封闭的?()
4.设G是n阶m条边的无向简单边通图,则G的任何生成树对应的G的基本割集系统中均有________________个元素。
5.完全Байду номын сангаас部图Kr,s的边连通度λ等于_________________。
6.以1,1,1,1,2,2,4为无向树的度数列,可以生成_________________棵非同构的无向树。
4.设A={1,2,3}上的关系R={<1,1>,<1,2>,<1,3>,<3,3>},则关系R具备①性,不具备②性。
5.设A={1,2,3,4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>},则r(R)=①,s(R)=
②。
6.令R(x):x是实数,Q(x):x是有理数。
(1)命题“并非每个实数都是有理数”。其符号化为①。
3.谓词公式x(P(x)yR(y))Q(x)中变元x是()
A.自由变量B.约束变量
C.既不是自由变量也不是约束变量
D.既是自由变量也是约束变量
4.设C(x):x是运动员,G(x):x是强壮的。命题“没有一个运动员不是强壮的”可符号化为()
A.x(C(x)G(x))B.x(C(x)G(x))
C.x(C(x)G(x))D.x(C(x)G(x))
B.G={1,3,4,5,9},*是模11的乘法
C.G=Q,*是普通加法
D.G=Q,*是普通乘法
2.下面哪一个偏序集(其中均略去了反映自反关系的序对)能构成格?()
A.A={a,b,c,d},≤={<d,c>,<c,b>,<b,a>,<d,b>,<d,a>}
B.A={a,b,c,d,e},≤={<b,a>,<c,b>,<d,b>,<e,c>,<e,d>,<e,b>}
C.A={a,b,c,d,e,f,g},≤={<b,a>,<d,a>,<c,b>,<c,d>,<f,e>,<g,f>}
D.A={1,2,3,4},≤={<1,2>,<1,3>,<2,4>,<3,4>}
3.下面哪个偏序集构成有界格?()
A.(N,≤)B.(Z,≥)
C.({2,3,4,6,12},|)D.(P(A),)
(1).命题“我虽然生病但我仍去学校”符号化为。
(2).命题“只有在生病的时候,我才不去学校”符号化为。
(3).命题“如果我生病,那么我不去学校”符号化为。
7.证明下列命题的等值关系:
(1).(PQ)(RQ)(PR)Q
(2).(PQAC)(APQC)(A(PQ))C
(3).P(QP)Q(PR)
(4).(PQ)(PR)P(QR)
三、计算题(共43分)
1.求P→(P∧(Q→P))的主析取范式(写出过程)。(6分)
2.求公式的前束范式。(6分)
3 证明:
(1)A→(B→A)┐A→(A→┐B)
A→(B→A)┐A∨(┐B∨A)A∨(┐A∨┐B)A∨(A→┐B)┐A→(A→┐B)