第一篇:离散数学练习题1
1、下列句子是简单命题的是()
A)3是素数。B)2x+3<
5C)张三跟李四是同学吗?D)我在说谎。
2、下列公式不是永真式的是()..
A)((p∧q))→p)∨rB)p→(p∨q∨r)
C)┓(q→r)∧rD)(p→q)→(┓q→┓p)
3、设命题公式G<=>┓(p→q),H<=>p→(q →┓p),则G与H的关系是()。
A)G<=>HB)H→GC)H => GD)G => H4、下列命题不为真的是().
A)Φ ΦB)Φ∈Φ
C){a,b}∈{a,b,c,{a,b}}}D){a,b}{a,b,c,{a,b}}
5、1到300之间(包含1 和1000)不能被3、5和7整除的数有()个。
13、下列运算在指定集合上不符合交换律的是()。
A)复数C集合上的普通加法B)n阶实矩阵上的乘法 C)集合S的幂集上的∪D)集合S的幂集上的
14、下列集合对所给的二元运算封闭的是()
A)正实数集合R+和。运算,其中。运算定义如下:a,b∈R+,a。b=ab-a-b B)n∈Z+,nZ={nZ|z∈Z},nZ关于普通的加法运算 C)S={2x-1|x∈Z+}关于普通的加法运算
D)S={x|x=2n, n∈Z+},S关于普通的加法运算
15、设V=能构成的代数系统是()。
A)半群、独异点、群B)半群、独异点C)半群D)二元运算
上有○
A)138B)120C)68D)1246、设A, C, B, D为任意集合,以下命题一定为真的是()
A)A∪B= A∪C =>B=C B)A×C= A×B =>B= C
C)A∪(B×C)=(A∪B)×(A∪C)D)存在集合A,使得A A ×A7、设A={1,2,3,4},R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>} 是A上的关系,则R的性质是()
A)既是对称的也是反对称的 B)既不是对称的也不是反对称的 C)是对称的但不是反对称的D)不是对称的但是反对称的8、设R是A上的关系,则R在A上是传递的当且仅当()
则这4个运算中满足幂等律的是()
17、在上述四个运算中有单位元的是()
18、在上述四个运算中有零元的是()
19、与命题公式P(QR)等值的公式是()
A)(PQ)RB)(PQ)RC)(PQ)RD)P(QR)
20、下列集合都是N的子集,能够构成代数系统V=
A){x| x∈N∧x与5互为素数}B){x| x∈N∧x是30的因子} C){x| x∈N∧x是30的倍数}D){x|x=2k+1, k∈N }
二、填空题(1分/空,共20分。请将正确答案填在相应的横线上。)
1、公式┓(p∨q)→p的成假赋值为00__,公式┓(q→p)∧p的成真赋值为。
2、设A,B为任意命题公式,C为重言式,若A∧C<=>B∧C,那么A<->B是重言式(重言式、矛盾式或可满足式)。
3、f:N->N×N,f(x)=
其中,x=y(mod 3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等。则1的等价类,即[1],为()
A){1,4,7}B){2,5,8}C){3,6}D){1,2,3,4,5,6,7,8}
10、当集合A=Φ且B≠Φ时,则BA结果为()
A)ΦB){Φ} C){Φ, {Φ}}D)错误运算
11、函数f:R→R,f(x)= x2-2x+1,则f(x)是()函数。
A)单射B)满射C)双射D)不是单射,也不是满射
12、设X={a,b,c,d},Y={1,2,3},f={,,
A)f是从X到Y的二元关系,但不是从X到Y的函数 B)f是从X到Y的函数,但不是满射的,也不是单射的 C)f是从X到Y的满射,但不是单射 D)f是从X到Y的双射
双射)函数,A在f下的像f(A)=_{<5,6>}_,B在f下的完全原像f-1(B)=____。
4、已知公式A中含有3个命题变项p,q,r,并且它的成真赋值为000,011,110,则A的主合取范式为(用极大项表示)__M∧_M∧_M∧_M∧_M,主析取范式为(用极小项表示)
5、公式x(F(x,y)→yG(x,y,z))的前束范式为_
6、列出从集合A={1,2}到B={1}的所有二元关系。
7、设A为集合且∣A∣=n,则A共有nP(A)有n
8、设 f,g,h ∈RR 且f(x)=x+3, g(x)=2x+1, h(x)=x/2, 则复合函数
⑦ x(F(x)∧G(x)→H(x))前提引入 ⑧ F(a)∧G(a)→H(a)T ⑦UI⑨ F(a)∧G(a)T ③ ⑥合取(10)H(a)T ⑧ ⑨ 假言推理
f。g。h(x)=__,f。g。h(x)=_____。
9、含有n个命题变项的公式共有_____个不同的赋值,最多可以生成___个不同的真值表;n个命题变项共可产生___n_____个极小项(极大项);含n个命题变项的所有有穷多个合式公式中,与它们等值的主析取范式(主合取范式)共有___2^2___种不同的情况。
10、已知集合A={,{}},则A的幂集P(A)=_____。
n
n
n
五、设A={1,2,3,4},在A×A上定义二元关系R,,
(1)证明R是A×A上的等价关系
(2)确定由R引起的对A×A的划分。(5分)
三、利用公式的主合取范式判断下列公式是否等值。(5分)
p→(q→r)与(p∧q)∨r p→(q→r)
<=>p∨(q∨r)<=>p∨q∨r <=>M6
(p∧q)∨r
<=>(p∨q)∨r <=>p∨q)∨r <=>M6
(1)证明:
=> x+v+u+n=y+u+v+m => x+n=y+m =>
解:{{<1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>,<4,1>},{<3,1>,<4,2>},{<2,1>,<3,2>,<4,3>}}
四、符号化命题,并推理证明(给出每个符号的准确含义,及每一步推理的根据)。(5分)
每个科学工作者都是刻苦钻研的。每个刻苦钻研而又聪明的人在他的事业中都将获得成功。华有为是科学工作者并且是聪明的,所以华有为在他的事业中将获得成功。
六、A= {1,2,3,4,6,8,12},R是A上的整除关系,请作出偏序集的哈斯图,给出关系矩阵,并
求出A的极大元、极小元、最大元和最小元。若B={2,3,4},求出B的上界,下界,最小上界,最大下界。(5分)
解:
首先符号化:M(x):x是科学工作者;F(x):x是刻苦钻研的;G(x):x是聪明的;H(x):x
在事业中获得成功;a:华有为。
前提: x(M(x)→F(x)),x(F(x)∧G(x)→H(x)),M(a)∧ G(a)
结论:H(a)
证明:① M(a)∧ G(a)前提引入 ② M(a)T ①化简规则 ③ G(a)T ①化简规则 ④ x(M(x)→F(x))前提引入 ⑤ M(a)→F(a)T ④
⑥ F(a)T ② ⑤ 假言推理
解:A的极大元为8、12,极小元为1,无最大元,最小元为1。
B的上界为12,下界为1,最小上界为12,最大下界为1。
七、在自然推理系统P中构造下面推理的证明。(5分)(1)前提:(p∨q)→(r∧s),(s∨t)→u
结论:p→u(2)前提:x(F(x)→(G(a)∧ R(x))),x F(x).九、证明下列恒等式 A-(B∪C)=(A-B)∩(A-C)。(5分)证明:A-(B∪C)
结论: x(F(x)∧ R(x)).(1)证明:① p附加前提引入规则② p ∨ q①附加规则③(p ∨ q)→(r ∧ s)前提引入
④ r ∧ s②③ 假言推理⑤ s④化简规则⑥ s ∨ t⑤附加规则⑦(s ∨ t)→ u前提引入
⑧ u⑥ ⑦假言推理
(2)证明:① x F(x)前提引入② F(b)① EI③ x(F(x)→(G(a)∧ R(x)))前提引入④ F(b)→(G(a)∧ R(b))③ UI
⑤ G(a)∧ R(b)② ④假言推理⑥ R(b)⑤化简⑦ F(b)∧ R(b)②⑥合取⑧x(F(x)∧ R(x))⑦EG
八、设有理数集合Q上的 * 运算定义如下:a,b∈Q, a*b=a+b-ab。请指出该运算的性质,并求出其单位元、零元及所有可能的逆元。(5分)
解:(1)因为a*b=a+b-ab =b+a-ba=b*a,所以运算满足交换律。
(2)因为(a*b)*c=(a+b-ab)*c= a+b-ab+c-(a+b-ab)c=a+b+c-ab-bc-ac+abca*(b*c)=a*(b+c-bc)=a+b+c-bc-a(b+c-bc)= a+b+c-ab-bc-ac+abc故运算满足结合律。
(3)任意x∈Q,因为x*x=x+x-xx=2x+x2≠x,故不满足幂等律(4)因为对a∈Q,有a*0=a+0-a0=a,所以0是单位元。(5)因为对a∈Q,有a*1=a+1-a=1,所以1是零元。
(6)对a∈Q,令a*x=a+x-ax=0,则有x=a/(a-1)。所以当a≠1时,其逆元为a=a/(a-1),1没有逆元。
1=A∩~(B∪C)=A∩~B∩~C = A∩A∩~B∩~C =(A∩~B)∩(A∩~C)=(A-B)∩(A-C)
十、设A,B为任意集合,证明:AB<=>P(A)P(B)。(5分)证明:先证明充分性(=>)
X∈P(A)=> XA=> XB=> X∈P(B)再证明必要性(<=)
x∈A=> {x}A=> {x}∈P(A)=> {x}∈P(B)=> {x}B=>x∈B 综上所述,AB<=>P(A)P(B)
第二篇:离散数学复习题1
逻辑
1、给出的真值表
2、证明为永真式 谓词量词和推理
1、使用量词和谓词表达不存在这一事实
2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门考试蕴含结论“通过考试的某个人没有读过书” 集合、函数、数列与求和
1、全集为,求集合A=的位串?它的补集的位串是什么?写出集合A=的所有子集,写出集合
2、从集合到集合能定义多少个函数?下面给出的函数其定义为:该函数是双射吗?是满射吗?该函数是否存在逆函数?如果存在请给出其逆函数。计数
1、计算机系统的美国用户有一个6~8个字符构成的密码,其中每个字符是一个大写字母或数字,且每个密码必须至少包含一个数字,问总共有多少个合适的密码?
2、在30天的一个月里,某棒球队一天至少打一场比赛,但最多打45场。证明一定有连续的若干天内这个球队恰好打了14场比赛
3、证明n个元素的集合中允许重复的r组合数等于
4、按照字典顺序生成整数1,2,3的所有排列(不允许重复),在362541后面按照字典顺序的下一个最大排列是什么?找出在1000100111后面的下一个最大的二进制串。关系
1、求下面给出关系R的自反闭包、对称闭包和传递闭包的0-1关系矩阵,其中
2、S是所有比特串的集合,关系定义为当s=t或者s和t的长度至少是3,且前3个比特相同时具有关系,例如0101,0011100101,但01010,0101101110。证明是S上的等价关系,由产生的S的等价类是那些集合?
3、偏序集({2,4,5,10,12,20,25},|)的那些元素是极大的,那些元素是极小的? 图与树
1、在下图所示的图中,从a 到d的长度为4的通路有几条?该图是否是Euler图,是否是Hamilton图,该图的度序列是什么?该图是否可平面,如果是请给出平面画图,该图的点色数和边色数等于多少?给出该图的一个生成树,2、求下面赋权图从a到z的最短距离是多少?最短路径是什么?(画图给出标号过程)
3、用哈夫曼编码方法来编码下列符号,这些符号具有下列频率:A:0.08,B:0.10,C:0.12,D:0.15,E:0.20,F:0.35,该编码方法编码一个字符的平均位数是多少?
4、下面树的高度是多少?那些节点是内部节点,那些节点是叶子节点,该树是否是3元正则树?分别给出该树节点的前序、中序、后序遍历的节点访问次序
第三篇:离散数学练习题及答案
离散数学试题
一、单项选择题
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.设P:天下大雨,Q:他在室内运动,命题“如果天下大雨,他就在室内运动”可符合化为.(B)A.P∧Q C.Q→P
B.P→Q D.P∨Q
2.设G=(V , E)为任意一图(无向或有向的),顶点个数为n,边的条数为m,则各顶点的度数之和等于(D)。
A.nB.mC.2nD.2m
3.下列命题为假命题的是(A).
A.如果2是偶数,那么一个公式的析取范式惟一 B.如果2是偶数,那么一个公式的析取范式不惟一 C.如果2是奇数,那么一个公式的析取范式惟一 D.如果2是奇数,那么一个公式的析取范式不惟一
4.谓词公式x(P(x)∨yR(y))→Q(x)中变元x是(D)A.自由变元
C.既不是自由变元也不是约束变元
B.约束变元
D.既是自由变元也是约束变元
5.若个体域为整数域,下列公式中值为真的是(A)A.xy(x+y=0)C.xy(x+y=0)
6.下列命题中不正确的是(D).A.x∈{x}-{{x}}
C.A={x}∪x,则x∈A且xA
B.{x}{x}-{{x}}D.A-B=A=B B.yx(x+y=0)D.xy(x+y=0)
7.设P={x|(x+1)2≤4},Q={x|x2+16≥5x},则下列选项正确的是(C)A.PQ C.QP
8.下列表达式中不成立的是(A).A.A∪(BC)=(A∪B)(A∪C)C.(AB)×C=(A×C)(B×C)
9.半群、群及独异点的关系是(A)A.{群}{独异点}{半群}
B.{独异点}{半群}{群} B.A∩(BC)=(A∩B)(A∩C)D.(A-B)×C=(A×C)-(B×C)B.PQ D.Q=P
C.{独异点}{群}{半群} D.{半群}{群}{独异点}
10.下列集合对所给的二元运算封闭的是(C)A.正整数集上的减法运算
B.在正实数的集R+上规定为ab=ab-a-b
+
a,b∈R
C.正整数集Z+上的二元运算为xy=min(x,y)x,y∈Z+ D.全体n×n实可逆矩阵集合Rn
×n
上的矩阵加法
11.设集合A={1,2,3},下列关系R中不是等价关系的是(C).A.R={<1,1>,<2,2>,<3,3>}
B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>} C.R={<1,1>,<2,2>,<3,3>,<1,2>}
D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 12.下列函数中为双射的是(D)A.f:Z→Z,f(j)=j(mod)3C.f:Z→N,f(j)=|2j|+
11,j是奇数
B.f:N→N,f(j)=
0,j是偶数
D.f:R→R,f(r)=2r-1
513.设集合A={a,b, c}上的关系如下,具有传递性的是(D)A.R={,
14.设有限集合A的元素个数为n个,则A上共有(C)个不同的二元关系。
A. nB.C.D.以上都不对
15.设D的结点数大于1,D=
C.D中有通过每个结点至少一次的通路
B.D中至少有一条回路
D.D中有通过每个结点至少一次的回路
15-1.下列公式中,(C)是含有3个命题变项p,q,r的极小项。
A.pqB.(pqr)C.pqrD.pq r
二、填空题
请在每小题的空格中填上正确答案。错填、不填均无分。
16.设A={1,2,3},B={3,4,5},则AA=___________,AB=___________。
17.设A={1,2,3,4,5},RA×A,R={<1,2>,<3,4>,<2,2>},则R的自反闭包r(R)=__________。
对称闭包t(R)=__________。
18.设P、Q为两个命题,德摩根律可表示为_____________,吸收律可表示为____________。
19.对于公式x(P(x)∨Q(x)),其中P(x)∶x=1,Q(x)∶x=2,当个体域为{1,2}时,其真值为
_____________ ,当个体域为{0,1,2}时,其真值为_____________。
__, 20.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数(fg)(x)__________
(gf)(x)__________________。(此题两个答案颠倒一下)
22.无向图G=
Δ(G)=_____________,G的最小度δ(G)=_____________。0
123.设图G
11
10100100
11,则deg-(v1)=_ ________, 00
deg+(v4)=____________。
25.给定集合A={1,2,3,4,5},在集合A上定义两种关系:R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>},则RS__________答案:
三、计算题
26.设A={a,b,c,d},A上的等价关系R={,,
_____,SR_______________。
28.求下列公式的主析取范式:P→((Q→P)∧(P∧Q))解:
原式P ∨((Q∨P)∧(P∧Q))
P ∨((Q∧P∧Q)∨(P∧P∧Q)) P∨(0∨0)P
(P∧Q)∨(P∧Q)m0∨m
129.设A={a, b, c, d, e},R为A上的关系,R={,,, , ,
解:
四、证明题
32.设R是A上的自反和传递关系,如下定义A上的关系T,使得x, y∈A,
第四篇:离散数学练习题B
离散数学练习题B
一、简要回答下列问题:
1.什么是消去环?请举一例。
2.请给出公式R→P的真值表。
3.什么是恒真公式?举一例。
4.什么是子句?什么是短语?
5.请给出命题xG(x)的真值规定
6.什么是最优树?
7.什么是群?举一例。
8.给出环的定义。举一例。
9.什么是整区?举一例。
10.什么是半序格?请举一例。
二、对任意集合A,B,证明:
(1)AB当且仅当(A) (B);
(2)(A)(B)(AB);
(3)(A)(B)=(AB);
举例说明:(A)∪(B)≠(A∪B)
三、证明:映射的乘法满足结合律,举例说明:映射的乘法不满足交换律。
四、判断下列公式是恒真?恒假?可满足?
a)(P(QR))(P(QR));
b)P(P(QP));
c)(QP)(PQ);
d)(PQ)(PQ)。
五、证明:连通图中任意两条最长的简单路必有公共点。
第五篇:离散数学单元测试试题1
临沂大学2015—2016学第1学期
离散数学单元测试试题一
(适用于2014级计算机科学与技术、软件工程、网络工程专业本科学生)
一、选择题(共10题,每题3分,共30分)1.下列语句中为命题的是(D)。A.这朵花是谁的? B.这朵花真美丽啊!C.这朵花是你的吗? D.这朵花是他的。
2.若p:他聪明;q:他用功;则“他虽聪明,但不用功”,可符号化为(B)。A.p∨q
B.p∧┐q
C.p→┐q
D.p∨┐q 3.命题公式p∨q→q的公式类型为(D)。A.矛盾式 B.非重言可满足式 C.重言式
D.条件式
4.若F(x):x是有理数,G(x):x能被2整除,则“有的有理数能被2整除”,可符号化为(A)。
A.x(F(x)∧G(x))
B.F(x)∧G(x)
C.xF(x)
D.xG(x)5.设F(x)表示x是火车,G(x)表示y是汽车,H(x,y)表示x比y快,命题“某些汽车比所有火车慢”的符号化公式是(B)。
A.y(G(y)→x(F(x)∧H(x,y)))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)))6.设集合A={1,2,3},A上的关系R={<1,2>,<1,3>,<3,3>},则R具有(D)。A.自反性 B.传递性 C.对称性 D.以上答案都不对
######7.谓词公式x(P(x)∨yR(y))→Q(x)中的 x是(C)。A.自由变元 B.约束变元
C.既是自由变元又是约束变元 D.既不是自由变元又不是约束变元
8.设X、Y是两个集合且|X|=n,|Y|=m,则从X到Y可产生(A)个二元关系。A.n m B.mn
C.2n m D.nm 9.下列关于集合的表示中正确的为(C)。A.{a}{a,b,c} B.{a}{a,b,c}
C.{a,b,c} D.{a,b}{a,b,c} 10.设集合A={1,2,3,4,5},下列哪些是集合A的划分(D)。A.{{1,2},{3,5}}
B.{{1,2,3,4},5} C.{ ,{1,2},{3},{4,5}} D.{{1},{2},{3},{4},{5}}
二、填空题(共10空,每空3分,共30分)1.设p:2+2=5,q:明天是阴天,则命题“只要2+2=5,那么明天是阴天”可符号化为 p->q,其真值是 1。
2.设p:你陪伴我,q:你代我叫车子,r:我出去,则“如果你不陪伴我或不代我叫车子,我就不出去。”的符号化形式为 ¬p/¬q->r。
3.设p: 天下雨,q: 天刮风,r: 我去书店,则“如果天不下雨并且不刮风,我就去书店”的符号化形式为。
4.设S(x)∶x是大学生;K(x)∶x是运动员。则“有些运动员不是大学生”的符号化为。
5.设P(x):x非常聪明;Q(x):x非常能干;a:小李;则“小李非常聪明且能干”的符号化形式为。
6.设F(x): x是人,G(x): x用右手写字,则“有的人并不用右手写字”的符号化形式为。
7.设S(x):x是学生;L(x):x喜欢英语。则“有些学生喜欢英语”的符号化为:。8.在公式x(P(z)→Q(x,z))∧zR(x,z)中,x的辖域是
,z的辖域是。
三、计算与证明(共2题,每题20分,共40分)1.用等值演算求下公式的主析取范式(p→q)∧r。
2.在命题逻辑自然推理系统中,构造下面推理的证明。前提: p∨q, q→r, p→s, ┐s,结论:r ∧
(p∨q)。