《离散数学》题库答案
一、选择或填空
(数理逻辑部分)
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),(5),(6)
4、公式?x((A(x)→B(y,x))∧?z C(y,z))→D(x)中,自由变元是( ),约束变元是( )。
答:x,y, x,z
5、判断下列语句是不是命题。若是,给出命题的真值。( ) (1)北京是中华人民共和国的首都。(2) 陕西师大是一座工厂。
(3) 你喜欢唱歌吗?(4) 若7+8>18,则三角形有4条边。
(5) 前进!(6) 给我一杯水吧!
答:(1)是,T (2)是,F (3)不是
(4)是,T (5)不是(6)不是
6、命题“存在一些人是大学生”的否定是( ),而命题“所有的人都是要死的”的否定是( )。
答:所有人都不是大学生,有些人不会死
7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。
(1) 只有在生病时,我才不去学校(2) 若我生病,则我不去学校
(3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校答:(1)P
?(4)Q
P?
?
P→
P?
→(3)Q
Q→
?(2)Q
8、设个体域为整数集,则下列公式的意义是( )。
(1) ?x?y(x+y=0) (2) ?y?x(x+y=0)
答:(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) ( )
答:(1)F (2)F (3)F (4)T
10、设谓词P(x):x是奇数,Q(x):x是偶数,谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( )
(1) 自然数(2) 实数(3) 复数(4) (1)--(3)均成立
答:(1)
11、命题“2是偶数或-3是负数”的否定是()。
答:2不是偶数且-3不是负数。
12、永真式的否定是()
(1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能
答:(2)
13、公式(?P∧Q)∨(?P∧?Q)化简为(),公式Q→(P∨(P∧Q))可化简为()。
答:?P ,Q→P
14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是()。
答:P(x)∨?yR(y)
15、令R(x):x是实数,Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为()。
答:??x(R(x)→Q(x))
(集合论部分)
16、设A={a,{a}},下列命题错误的是()。
(1) {a}∈P(A) (2) {a}?P(A) (3) {{a}}∈P(A) (4) {{a}}?P(A)
答:(2)
17、在0()Φ之间写上正确的符号。
(1) = (2) ?(3) ∈(4) ?
答:(4)
18、若集合S的基数|S|=5,则S的幂集的基数|P(S)|=()。
答:32
19、设P={x|(x+1)2≤4且x∈R},Q={x|5≤x2+16且x∈R},则下列命题哪个正确()
(1) Q?P (2) Q?P (3) P?Q (4) P=Q
答:(3)
20、下列各集合中,哪几个分别相等( )。
(1) A1={a,b} (2) A2={b,a} (3) A3={a,b,a} (4) A4={a,b,c}
(5) A5={x|(x-a)(x-b)(x-c)=0} (6) A6={x|x2-(a+b)x+ab=0}
答:A1=A2=A3=A6,A4=A5
21、若A-B=Ф,则下列哪个结论不可能正确?( )
(1) A=Ф(2) B=Ф(3) A?B (4) B?A
答:(4)
22、判断下列命题哪个为真?( )
(1) A-B=B-A => A=B (2) 空集是任何集合的真子集
(3) 空集只是非空集合的子集(4) 若A的一个元素属于B,则A=B
答:(1)
23、判断下列命题哪几个为正确?( )
(1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}?{Ф,{{Ф}}} (3) Ф∈{{Ф}}
(4) Ф?{Ф} (5) {a,b}∈{a,b,{a},{b}}
答:(2),(4)
24、判断下列命题哪几个正确?( )
(1) 所有空集都不相等(2) {Ф}≠Ф(4) 若A为非空集,则A?A成立。答:(2)
25、设A∩B=A∩C,A∩B=A∩C,则B( )C。
答:=(等于)
26、判断下列命题哪几个正确?( )
(1) 若A∪B=A∪C,则B=C (2) {a,b}={b,a}
(3) P(A∩B)≠P(A)∩P(B) (P(S)表示S的幂集)
(4) 若A为非空集,则A≠A∪A成立。
答:(2)
27、A,B,C是三个集合,则下列哪几个推理正确:
(1) A?B,B?C=> A?C (2) A?B,B?C=> A∈B (3) A∈B,B∈C=> A∈C 答:(1)
(二元关系部分)
28、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=y2},
求(1)R (2) R-1 。
答:(1)R={<1,1>,<4,2>} (2) R1-={<1,1>,<2,4>}
29、举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 答:A上的恒等关系
30、集合A上的等价关系的三个性质是什么?( )
答:自反性、对称性和传递性
31、集合A上的偏序关系的三个性质是什么?( )
答:自反性、反对称性和传递性
32、设S={1,2,3,4},A上的关系R={〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉}求(1)R R (2) R-1。
答:R R ={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉}
R-1 ={〈2,1〉,〈1,2〉,〈3,2〉,〈4,3〉}
33、设A={1,2,3,4,5,6},R是A上的整除关系,求R= {( )}。答:R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,
<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}
34、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=2y},求(1)R (2) R-1 。
答:(1)R={<1,1>,<4,2>,<6,3>} (2) R1-={<1,1>,<2,4>,(36>}
35、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=y2},
求R和R-1的关系矩阵。
答:R 的关系矩阵=????
??
?
?
?
?????
????0000000010000000
01 R 1-的关系矩阵=????
??????000000010000000001 36、集合A={1,2,…,10}上的关系R={
(1) 自反的 (2) 对称的 (3) 传递的,对称的 (4) 传递的
答:(2)
(代数结构部分)
37、设A={2,4,6},A 上的二元运算*定义为:a*b=max{a,b},则在独异点中,单位元是( ),零元是( )。
答:2,6
38、设A={3,6,9},A 上的二元运算*定义为:a*b=min{a,b},则在独异点中,单位元是( ),零元是( );
答:9,3
(半群与群部分)
39、设〈G,*〉是一个群,则
(1) 若a,b,x ∈G ,a *x=b ,则x=( );
(2) 若a,b,x∈G,a*x=a*b,则x=( )。
-1 b (2)b
答:(1)a*
40、设a是12阶群的生成元,则a2是( )阶元素,a3是( )阶元素。答:6,4
41、代数系统
答:单位元
42、设a是10阶群的生成元,则a4是( )阶元素,a3是( )阶元素。答:5,10
43、群
答:单位元,1
44、素数阶群一定是( )群, 它的生成元是( )。
答:循环群,任一非单位元
45、设〈G,*〉是一个群,a,b,c∈G,则
(1) 若c*a=b,则c=( );(2) 若c*a=b*a,则c=( )。
*a(2) b
答:(1)b1-
46、
答:
47、群<A,*>的等幂元有( )个,是( ),零元有( )个。答:1,单位元,0
48、在一个群〈G,*〉中,若G中的元素a的阶是k,则a-1的阶是( )。
答:k
49、在自然数集N上,下列哪种运算是可结合的?()(1) a*b=a-b (2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|a-b| 答:(2)
50、任意一个具有2个或以上元的半群,它()。
(1) 不可能是群(2) 不一定是群
(3) 一定是群(4) 是交换群
答:(1)
51、6阶有限群的任何子群一定不是()。
(1) 2阶(2) 3 阶(3) 4 阶(4) 6 阶
答:(3)
(格与布尔代数部分)
52、下列哪个偏序集构成有界格()
(1) (N,≤)(2) (Z,≥)
(3) ({2,3,4,6,12},|(整除关系))(4) (P(A),?)
答:(4)
53、有限布尔代数的元素的个数一定等于()。
(1) 偶数(2) 奇数(3) 4的倍数(4) 2的正整数次幂答:(4)
(图论部分)
54、设G是一个哈密尔顿图,则G一定是( )。
(1) 欧拉图(2) 树(3) 平面图(4) 连通图
答:(4)
55、下面给出的集合中,哪一个是前缀码?( )
(1) {0,10,110,101111} (2) {01,001,000,1}
(3) {b,c,aa,ab,aba} (4) {1,11,101,001,0011}
答:(2)
56、一个图的哈密尔顿路是一条通过图中( )的路。
答:所有结点一次且恰好一次
57、在有向图中,结点v的出度deg+(v)表示( ),入度deg-(v)表示( )。答:以v为起点的边的条数,以v为终点的边的条数
58、设G是一棵树,则G 的生成树有( )棵。
(1) 0 (2) 1 (3) 2 (4) 不能确定
答:1
59、n阶无向完全图K n 的边数是( ),每个结点的度数是( )。
答:
2)1
(
n
n
, n-1
60、一棵无向树的顶点数n与边数m关系是( )。答:m=n-1
61、一个图的欧拉回路是一条通过图中( )的回路。
答:所有边一次且恰好一次
62、有n个结点的树,其结点度数之和是( )。
答:2n-2
63、下面给出的集合中,哪一个不是前缀码( )。
(1) {a,ab,110,a1b11} (2) {01,001,000,1}
(3) {1,2,00,01,0210} (4) {12,11,101,002,0011}
答:(1)
64、n个结点的有向完全图边数是( ),每个结点的度数是( )。答:n(n-1),2n-2
65、一个无向图有生成树的充分必要条件是( )。
答:它是连通图
66、设G是一棵树,n,m分别表示顶点数和边数,则
(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。
答:(3)
67、设T=〈V,E〉是一棵树,若|V|>1,则T中至少存在( )片树叶。答:2
68、任何连通无向图G至少有( )棵生成树,当且仅当G 是( ),G的生成树只有一棵。
答:1,树
69、设G是有n个结点m条边的连通平面图,且有k个面,则k等于:
(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。
答:(1)
70、设T是一棵树,则T是一个连通且( )图。
答:无简单回路
71、设无向图G有16条边且每个顶点的度数都是2,则图G有( )个顶点。
(1) 10 (2) 4 (3) 8 (4) 16
答:(4)
72、设无向图G有18条边且每个顶点的度数都是3,则图G有( )个顶点。
(1) 10 (2) 4 (3) 8 (4) 12
答:(4)
73、设图G=
答:有向图
74、任一有向图中,度数为奇数的结点有( )个。
答:偶数
75、具有6 个顶点,12条边的连通简单平面图中,每个面都是由( )条边围成?
(1) 2 (2) 4 (3) 3 (4) 5
答:(3)
76、在有n个顶点的连通图中,其边数()。
(1) 最多有n-1条(2) 至少有n-1 条
(3) 最多有n条(4) 至少有n 条
答:(2)
77、一棵树有2个2度顶点,1 个3度顶点,3个4度顶点,则其1度顶点为()。
(1) 5 (2) 7 (3) 8 (4) 9
答:(4)
78、若一棵完全二元(叉)树有2n-1个顶点,则它()片树叶。
(1) n (2) 2n (3) n-1 (4) 2
答:(1)
79、下列哪一种图不一定是树()。
(1) 无简单回路的连通图(2) 有n个顶点n-1条边的连通图
(3) 每对顶点间都有通路的图(4) 连通但删去一条边便不连通的图答:(3)
80、连通图G是一棵树当且仅当G中()。
(1) 有些边是割边(2) 每条边都是割边
(3) 所有边都不是割边(4) 图中存在一条欧拉路径
答:(2)
(数理逻辑部分)
二、求下列各公式的主析取范式和主合取范式:
1、(P→Q)∧R
解:(P→Q)∧R?(?P∨Q )∧R
?(?P∧R)∨(Q∧R) (析取范式)
?(?P∧(Q∨?Q)∧R)∨((?P∨P)∧Q∧R)
?(?P∧Q∧R)∨(?P∧?Q∧R)∨(?P∧Q∧R)∨(P∧Q∧R)
?(?P∧Q∧R)∨(?P∧?Q∧R)∨(P∧Q∧R)(主析取范式)
?((P→Q)∧R)?(?P∧?Q∧?R)∨(?P∧Q∧?R)∨(P∧?Q∧R)
∨(P∧Q∧?R)∨( P∧?Q∧?R)(原公式否定的主析取范式)(P→Q)∧R?(P∨Q∨R)∧(P∨?Q∨R)∧(?P∨Q∨?R)
∧(?P∨?Q∨R)∧(?P∨Q∨R)(主合取范式)
2、(P∧R)∨(Q∧R)∨?P
解:(P∧R)∨(Q∧R)∨?P(析取范式)
?(P∧(Q∨?Q)∧R)∨((P∨?P)∧Q∧R)∨(?P∧(Q∨?Q)∧(R∨?R))
?(P∧Q∧R)∨(P∧?Q∧R)∨(P∧Q∧R)∨(?P∧Q∧R)
∨( ?P∧Q∧R)∨( ?P∧Q∧?R)∨(?P∧?Q∧R)∨(?P∧?Q∧?R)
?(P∧Q∧R)∨(P∧?Q∧R)∨(?P∧Q∧R)∨(?P∧Q∧?R) ∨(?P∧?Q∧R)∨(?P∧?Q∧?R) (主析取范式)
?((P∧R)∨(Q∧R)∨?P)
?(P∧?Q∧?R)∨(P∧Q∧?R)(原公式否定的主析取范式)
(P∧R)∨(Q∧R)∨?P ?(?P∨Q∨R)∧(?P∨?Q∨R)(主合取范式)3、(?P→Q)∧(R∨P)
解:(?P→Q)∧(R∨P)
?(P∨Q)∧(R∨P)(合取范式)
?(P∨Q∨(R∧?R))∧(P∨(Q∧?Q))∨R)
?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)∧(P∨?Q∨R)
?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨?Q∨R)(主合取范式)
?((?P→Q)∧(R∨P))
?(P∨?Q∨?R)∧(?P∨Q∨R)∧(?P∨?Q∨R)∧(?P∨Q∨?R) ∧(?P∨?Q∨?R)(原公式否定的主合取范式)
(?P→Q)∧(R∨P)
?(?P∧Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R) (主析取范式)
4、Q→(P∨?R)
解:Q→(P∨?R)
??Q∨P∨?R(主合取范式)
?(Q→(P∨?R))
?(?P∨?Q∨?R)∧(?P∨?Q∨R)∧(?P∨Q∨?R)∧(?P∨Q∨R)
∧(P∨?Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)(原公式否定的主合取范式)Q→(P∨?R)
?(P∧Q∧R)∨(P∧Q∧?R)∨(P∧?Q∧R)∨(P∧?Q∧?R)∨(?P∧Q∧?R) ∨(?P∧?Q∧R)∨(?P∧?Q∧?R)(主析取范式)
5、P→(P∧(Q→P))
解:P→(P∧(Q→P))
??P∨(P∧(?Q∨P))
??P∨P
?T (主合取范式)
?(?P∧?Q)∨(?P∧Q)∨(P∧?Q)∨(P∧Q)(主析取范式)
6、?(P→Q)∨(R∧P)
解:?(P→Q)∨(R∧P)??(?P∨Q)∨(R∧P)
?(P∧?Q)∨(R∧P)(析取范式)
?(P∧?Q∧(R∨?R))∨(P∧(?Q∨Q)∧R)
?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R)
?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)(主析取范式)?(?(P→Q)∨(R∧P))?(P∧Q∧?R)∨(?P∧Q∧R)∨(?P∧?Q∧R)
∨(?P∧?Q∧?R)∨(?P∧Q∧?R)(原公式否定的主析取范式)?(P→Q)∨(R∧P)?(?P∨?Q∨R)∧(P∨?Q∨?R)∧(P∨Q∨?R)
∧(P∨Q∨R)∧(P∨?Q∨R)(主合取范式)
7、P∨(P→Q)
解:P∨(P→Q)?P∨(?P∨Q)?(P∨?P)∨Q
?T(主合取范式)
?(?P∧?Q)∨(?P∧Q)∨(P∧?Q)∨(P∧Q)(主析取范式)
8、(R→Q)∧P
解:(R→Q)∧P?(?R∨Q )∧P
?(?R∧P)∨(Q∧P) (析取范式)
?(?R∧(Q∨?Q)∧P)∨((?R∨R)∧Q∧P)
?(?R∧Q∧P)∨(?R∧?Q∧P)∨(?R∧Q∧P)∨(R∧Q∧P)
?(P∧Q∧?R)∨(P∧?Q∧?R)∨(P∧Q∧R)(主析取范式)
?((R→Q)∧P)?(?P∧?Q∧?R)∨(?P∧Q∧?R)∨(P∧?Q∧R) ∨(?P∧Q∧R)∨(?P∧?Q∧R)(原公式否定的主析取范式)
(R→Q)∧P?(P∨Q∨R)∧(P∨?Q∨R)∧(?P∨Q∨?R)
∧(P∨?Q∨?R)∧(P∨Q∨?R)(主合取范式)
9、P→Q
解:P→Q??P∨Q(主合取范式)
?(?P∧(Q∨?Q))∨((?P∨P)∧Q)
?(?P∧Q)∨(?P∧?Q)∨(?P∧Q)∨(P∧Q)
?(?P∧Q)∨(?P∧?Q)∨(P∧Q)(主析取范式)
10、P∨?Q
解:P∨?Q (主合取范式)
?(P∧(?Q∨Q))∨((?P∨P)∧?Q)
?(P∧?Q)∨(P∧Q)∨(?P∧?Q)∨(P∧?Q)
?(P∧?Q)∨(P∧Q)∨(?P∧?Q)(主析取范式)
11、P∧Q
解:P∧Q(主析取范式)?(P∨(Q∧?Q))∧((P∧?P)∨Q)
?(P∨?Q)∧(P∨Q)∧(P∨Q)∧(?P∨Q)
?(P∨?Q)∧(P∨Q)∧(?P∨Q)(主合取范式)
12、(P∨R)→Q
解:(P∨R)→Q
??(P∨R)∨Q
?(?P∧?R)∨Q
?(?P∨Q)∧(?R∨Q)(合取范式)
?(?P∨Q∨(R∧?R))∧((?P∧P)∨Q∨?R)
?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨Q∨?R)∧(P∨Q∨?R)
?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨Q∨?R)∧(P∨Q∨?R)
?(?P∨Q∨R)∧(?P∨Q∨?R)∧(P∨Q∨?R)(主合取范式)
?(P∨R)→Q
?(?P∨?Q∨R)∧(?P∨?Q∨?R)∧(P∨Q∨R)∧(P∨?Q∨R)∧(P∨
?Q∨?R) (原公式否定的主析取范式)
(P∨R)→Q
?(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R)
∨(?P∧Q∧R)(主析取范式)
13、(P→Q)→R
解:(P→Q)→R
??(?P∨Q)∨R
?(P∧?Q)∨R(析取范式)
?(P∧?Q∧(R?
∨Q)∧R)
∨R))∨((P?
∨P)∧(Q?
?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧?Q∧R)∨(?P∧Q∧R) ∨(?P∧?Q∧R)
?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)
∨(?P∧?Q∧R)(主析取范式)
(P→Q)→R
??(?P∨Q)∨R
?(P∧?Q)∨R(析取范式)
?(P∨R)∧(?Q∨R)(合取范式)
?(P∨(Q∧?Q)∨R)∧((P∧?P)∨?Q∨R)
?(P∨Q∨R)∧(P∨?Q∨R)∧(P∨?Q∨R)∧(?P∨?Q∨R)
?(P∨Q∨R)∧(P∨?Q∨R)∧(?P∨?Q∨R)(主合取范式)
14、(P→(Q∧R))∧(?P→(?Q∧?R))
解:(P→(Q∧R))∧(?P→(?Q∧?R))
?(?P∨(Q∧R))∧(P∨(?Q∧?R))
?(?P∨Q)∧(?P∨R)∧(P∨?Q)∧(P∨?R)(合取范式)
?(?P∨Q∨(R∧?R))∧(?P∨(Q∧?Q)∨R)∧(P∨?Q∨(R∧?R)) ∧(P∨(Q∧?Q)∨?R)
?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨Q∨R)∧(?P∨?Q∨R) ∧(P∨?Q∨R)∧(P∨?Q∨?R)∧(P∨Q∨?R)∧(P∨?Q∨?R) ?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R)∧(P∨?Q∨R)
∧(P∨Q∨?R)∧(P∨?Q∨?R)(主合取范式)
?(P→(Q∧R))∧(?P→(?Q∧?R))
?(?P∨?Q∨?R)∧(P∨Q∨R)(原公式否定的主合取范式)
(P→(Q∧R))∧(?P→(?Q∧?R))
?(P∧Q∧R)∨(?P∧?Q∧?R)(主析取范式)
15、P∨(?P→(Q∨(?Q→R)))
解:P∨(?P→(Q∨(?Q→R)))
?P∨(P∨(Q∨(Q∨R)))
?P∨Q∨R(主合取范式)
?(P∨Q∨R)
?(P∨?Q∨R)∧(P∨?Q∨?R)∧(P∨Q∨?R)∧(?P∨Q∨R)
∧(?P∨Q∨?R)∧(?P∨?Q∨R)∧(?P∨?Q∨?R)
(原公式否定的主合取范式)
(P∨Q∨R)
?(?P∧Q∧?R)∨(?P∧Q∧R)∨(?P∧?Q∧R)∨(P∧?Q∧?R) ∨(P∧?Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)(主析取范式)
16、(P→Q)∧(P→R)
解、(P→Q)∧(P→R)
?(?P∨Q)∧(?P∨R) (合取范式)
?(?P∨Q∨(R∧?R)∧(?P∨(?Q∧Q)∨R)
?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R)∧(?P∨Q∨R) ?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R)(主合取范式)
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 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),(5),(6) 4、公式?x((A(x)→B(y,x))∧ ?z C(y,z))→D(x)中,自由变元就是( ),约束变元就是( )。 答:x,y, x,z 5、判断下列语句就是不就是命题。若就是,给出命题的真值。( ) (1) 北京就是中华人民共与国的首都。 (2) 陕西师大就是一座工厂。 (3) 您喜欢唱歌不? (4) 若7+8>18,则三角形有4条边。 (5) 前进! (6) 给我一杯水吧! 答:(1) 就是,T (2) 就是,F (3) 不就是 (4) 就是,T (5) 不就是 (6) 不就是 6、命题“存在一些人就是大学生”的否定就是( ),而命题“所有的人都就是要死的”的否定就是( )。 答:所有人都不就是大学生,有些人不会死 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义就是( )。 (1) ?x ?y(x+y=0) (2) ?y ?x(x+y=0) 答:(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) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x 就是奇数,Q(x):x 就是偶数,谓词公式 ?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2就是偶数或-3就是负数”的否定就是( )。 答:2不就是偶数且-3不就是负数。 12、永真式的否定就是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不? (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不? B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。
《离散数学》考试题库及答案 一、 填空 10% (每小题 2分) 1、 若P ,Q 为二命题,Q P ?真值为1,当且仅当 。 2、 对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的 公 式 为 。 3、 )) (()(x xG x xF ??∧?的 前 束 范 式为 。 4、 设x 是谓词合式公式A 的一个客体变元,A 的论域为D ,A (x )关于y 的自由的, 则 被称为全称量词消去规则,记为US 。 5、 与非门的逻辑网络为 。 二、 选择 30% (每小题 3分) 1、 下列各符号串,不是合式公式的有( )。 A 、R Q P ?∧∧)(; B 、)()((S R Q P ∧→→; C 、R Q P ∧∨∨; D 、S R Q P ∨∧∨?))((。 2、 下列语句是命题的有( )。 A 、2是素数; B 、x+5 > 6; C 、地球外的星球上也有人; D 、这朵花多好看呀!。 3、 下列公式是重言式的有( )。 A 、)(Q P ??; B 、Q Q P →∧)(; C 、P P Q ∧→?)(; D 、P Q P ?→)( 4、 下列问题成立的有( )。 A 、 若C B C A ∨?∨,则B A ?; B 、若C B C A ∧?∧,则B A ?; C 、若B A ???,则B A ?; D 、若B A ?,则B A ???。 5、 命题逻辑演绎的CP 规则为( )。 A 、 在推演过程中可随便使用前提; B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果; C 、如果要演绎出的公式为C B →形式,那么将B 作为前提,设法演绎出C ;
《离散数学》题库与答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式?( A ) (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、命题“存在一些人是大学生”的否定是( ),而命题“所有的人都是要死的”的否定是( )。 答:所有人都不是大学生,有些人不会死(命题的否定就是把命题前提中的量词“换成存在,换成”,然后将命题的结论否定,“且变或或变且”) 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校(2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校答:(1)P ?(注意“只有……才……”和“除非……就……”两者都是一个 Q→ 形式的)(2)Q P→ ? P? ?(4)Q P? →(3)Q 8、设个体域为整数集,则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答:(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) ( ) 答:(1)F (反证法:假若存在,则(x- 1)*y=0 对所有的x都成立,显然这个与前提条件相矛盾) (2)F (同理)(3)F (同理)(4)T(对任一整数x存在整数y满足条件y=2x 很明显是正确的)
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等 性 ;就是否有对称性 。 6、4阶群必就是 群或 群。 7、下面偏序格就是分配格的就是 。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是 。 * a b c a b c a b c b b c c c b
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈>∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】
一、填空题 1设集合A,B,其中A={1,2,3},B={1,2},则A-B=____________________; (A)-(B)=__________________________. 2.设有限集合A,|A|=n,则|(A×A)|=__________________________. 3.设集合A={a,b},B={1,2},则从A到B的所有映射是 _______________________________________,其中双射的是 __________________________. 4.已知命题公式G=(PQ)∧R,则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB= _________________________;AB=_________________________;A-B=_____________________. 7.设R是集合A上的等价关系,则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G=(P(QR)),则使公式G为真的解释有 __________________________, _____________________________,__________________________. 9.设集合A={1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则
第一章习题 1.1判断下列语句是否为命题,若是命题请指出是简单命题还是复合命题。(1)2是无理数。 (2)5能被2整除。 (3)现在开会吗? (4)x+5>0 (5)这朵花真是好看! (6)2是素数当且仅当三角形有三条边。 (7)雪是黑色的当且仅当太阳是从东方升起。 (8)2000年10月1日天气晴好。 (9)太阳系以外的星球上有生物。 (10)小李在宿舍里。 (11)全体起立。 (12)4是2的倍数或是3的倍数。 (13)4是偶数且是奇数。 (14)李明和王华是同学。 (15)蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化,并讨论他们的真值。 1.3判断下列各命题的真值。 (1)若2+2=4,则3+3=6; (2)若2+2=4,则3+3≠6; (3)若2+2≠=4,则3+3=6; (4)若2+2≠=4,则3+3≠=6; (5)2+2=4,当且仅当3+3=6; (6)2+2=4,当且仅当3+3≠6; (7)2+2≠4,当且仅当3+3=6; (8)2+2≠4,当且仅当3+3≠6; 1.4将下列命题符号化,并讨论其真值。 (1)如果今天是1号,则明天是2号; (2)如果今天是1号,则明天是3号; 1.5将下列命题符号化。 (1)2是偶数不是素数; (2)小王不但聪明而且用功; (3)虽然天气冷。老王还是来了; (4)他一边吃饭,一边看电视; (5)如果天下大雨,他就乘公交汽车来; (6)只有天下大雨,他才乘公交汽车来; (7)除非天下大雨,否则他不乘公交汽车来; (8)不经一事,不长一智; 1.5设p,q的真值为0 ,r,s的真值为1,求下列命题公式的真值。(1)p∨(q∧r);
本科高等数学离散数学试题及答案 一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=____________________; ρ(A) - ρ(B)=__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G=?(P→Q)∧R,则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为__________,分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B=_________________________; A?B=_________________________;A-B=_____________________ . 7. 设R是集合A上的等价关系,则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G=?(P→(Q∧R)),则使公式G为真的解释有__________________________,_____________________________, __________________________. 9. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B,|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A={2, 3, 4, 5, 6},R是A上的整除,则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x),则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树,则G中增加_________条边才能把G变成完全图。
常熟理工学院20 ~20 学年第学期 《离散数学》考试试卷(试卷库01卷) 试题总分: 100 分考试时限:120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题(每题2分,共20分) 1.下列表达式正确的有( ) (A)(B)(C)(D) 2.设P:2×2=5,Q:雪是黑的,R:2×4=8,S:太阳从东方升起,下列( )命题的真值为 真。 (A)(B)(C)(D) 3.集合A={1,2,…,10}上的关系R={
1.n个命题变元组成的命题公式共有种不同的等价公式。 2.设〈L,≤〉为有界格,a为L中任意元素,如果存在元素b∈L,使,则称b是a 的补元。 3.设*,Δ是定义在集合A上的两个可交换二元运算,如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4.设T是一棵树,则T是一个连通且的图。 5.一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6.量词否定等价式? ("x)P(x) ?,? ($x)P(x) ?。 7.二叉树有5个度为2的结点,则它的叶子结点数为。 8.设中的幺元是,α的逆元是。 10.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>} = 。 = 。 三、判断题(每题1分,共10分) 1.命题公式是一个矛盾式。() 2.,若,则必有。() 3.设S为集合X上的二元关系,则S是传递的当且仅当(S S)S。() 4.任何一棵二叉树的结点可对应一个前缀码。() 5.代数系统中一个元素的左逆元一定等于该元素的右逆元。() 6.一个有限平面图,面的次数之和等于该图的边数。() 7.A′B = B′A () 8.设*定义在集合A上的一个二元运算,如果A中有关于运算*的左零元θl和右零θr,则A中 有零元。() 9.一个循环群的生成元不是唯一的。() 10.任何一个前缀码都对应一棵二叉树。() 四、解答题(5小题,共30分) 1.(5分)什么是欧拉路?如何用欧拉路判定一个图G是否可一笔画出? 2.(8分)求公式 (P∨Q)R 的主析取范式和主合取范式。
第一章 定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A(吸收律) 证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)
《离散数学》期末复习题 一、填空题(每空2分,共20分) 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c},B={a,b,c,d,e},则A?B= 。 4、集合A={1,2,3,4},B={1,3,5,7,9},则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3},A上的二元运算定义为:a* b = a和b两者的最大值,则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法,是加法的幂等元, 是乘法的幂等元。 9、设a,b,c是阿贝尔群
19、代数系统是指由及其上的或 组成的系统。 20、设
离散数学试题及答案 一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=____________________; ρ(A) - ρ(B)=__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G=?(P→Q)∧R,则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为__________,分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B=_________________________; A?B =_________________________;A-B=_____________________ . 7. 设R是集合A上的等价关系,则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G=?(P→(Q∧R)),则使公式G为真的解释有__________________________, _____________________________, __________________________. 9. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B,|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A={2, 3, 4, 5, 6},R是A上的整除,则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x),则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树,则G中增加_________条边才能把G变成完全图。
离散数学试题一(A 卷答案) 一、(10分)证明(A ∨B )(P ∨Q ),P ,(B A )∨P A 。 二、(10分)甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛,下列4 种判断都是正确的: (1)甲和乙只有一人参加; (2)丙参加,丁必参加; (3)乙或丁至多参加一人; (4)丁不参加,甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、(10分)指出下列推理中,在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1),US (3)xP (x ) P (4)P (y ) T (3),ES (5)Q (y ) T (2)(4),I (6)xQ (x ) T (5),EG 四、(10分)设A ={a ,b ,c},试给出A 上的一个二元关系R ,使其同时不满足自反性、反自反性、 五、(15分)设函数g :A →B ,f :B →C , (1)若f o g 是满射,则f 是满射。 (2)若f o g 是单射,则g 是单射。 六、(15分)设R 是集合A 上的一个具有传递和自反性质的关系,T 是A 上的关系,使得T R 且R ,证明T 是一个等价关系。 七、(15分)若
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 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),(5),(6) 4、公式 x((A(x) B(y ,x)) z C(y ,z))D(x)中,自由变元是( ),约束变元是( )。 答:x,y, x,z 5、判断下列语句是不是命题。若是,给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗? (4) 若7+8>18,则三角形有4条边。 (5) 前进! (6) 给我一杯水吧! 答:(1) 是,T (2) 是,F (3) 不是 (4) 是,T (5) 不是 (6) 不是 6、命题“存在一些人是大学生”的否定是( ),而命题“所有的人都是要死的”的否定是( )。 答:所有人都不是大学生,有些人不会死 7、设P :我生病,Q :我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答:(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) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x 是奇数,Q(x):x 是偶数,谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2是偶数或-3是负数”的否定是( )。 答:2不是偶数且-3不是负数。 12、永真式的否定是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答:(2) 13、公式(?P ∧Q)∨(?P ∧?Q)化简为( ),公式 Q →(P ∨(P ∧Q))可化简为( )。 答:?P ,Q →P
离散数学练习题 第一章 一.填空 1.公式) ∨ ? ∧的成真赋值为 01;10 ? p∧ ( (q ) p q 2.设p, r为真命题,q, s 为假命题,则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01;10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式,B为重言式,则B A∨的类型为重言式 5.设p, q均为命题,在不能同时为真条件下,p与q的排斥也可以写成p与q的相容或。 二.将下列命题符合化 1. 7不是无理数是不对的。 解:) ? ?,其中p: 7是无理数;或p,其中p: 7是无理数。 (p 2.小刘既不怕吃苦,又很爱钻研。 解:其中 ?p: 小刘怕吃苦,q:小刘很爱钻研 p∧ ,q 3.只有不怕困难,才能战胜困难。 解:p →,其中p: 怕困难,q: 战胜困难 q? 或q →,其中p: 怕困难, q: 战胜困难 p? 4.只要别人有困难,老王就帮助别人,除非困难解决了。 解:) → ?,其中p: 别人有困难,q:老王帮助别人,r: 困难解决了 p (q r→ 或:q ?) (,其中p:别人有困难,q: 老王帮助别人,r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解:q p?,其中p: 整数n是偶数,q: 整数n能被2整除 三、求复合命题的真值 P:2能整除5, q:旧金山是美国的首都, r:在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解:p, q 为假命题,r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r
离散数学 1.在自然推理系统P 中构造下面推理的证明: 前提:,,p q r q r s ?∨∨?→ 结论:p s →. 3设一阶逻辑公式 ((,)(()()))G x yP x y zQ z R x =???→?→ 试将G 化成与其等价的前束范式。 4.判断下面推理是否正确,并证明你的结论。 如果小王今天家里有事,则他不会来开会。 如果小张今天看到小王,则小王今天来开会了。 小张今天看到小王。所以小王今天家里没事。 5、构造下面推理的证明 前提: ))()(()),()()((x R x F x x H x G x F x ∧?∧→? 结论: ))()()((x G x R x F x ∧∧? 6用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ??→∧→=的类型。 7分别用真值表法和公式法求(P →(Q ∨R ))∧(?P ∨(Q ?R ))的主析取范式 ,并写出其相应的成真赋值和成假赋值。 8用逻辑推理证明: 所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。 9、设A ={?,1,{1}},B ={0,{0}},求P (A )、P (B )-{0}、P (B )⊕B 。 10、设X ={1,2,3,4},R 是X 上的二元关系,R ={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>} (1)画出R 的关系图。 (2)写出R 的关系矩阵。 (3)说明R 是否是自反、反自反、对称、传递的。 11、集合X={<1,2>, <3,4>, <5,6>,… },R={<
1 / 15 离散数学(2)复习题 一、单项选择题 1、由集合运算定义,下列各式正确的有( A )。 A.X ?X ?Y B.X ?X ?Y C.X ?X ?Y D.Y ?X ?Y 2、设A B -=?,则有( C )。 A.B =? B.B ≠? C.A B ? D.A B ? 3、对任意的集合A 、全集U ,下列命题为假的是( D )。 A.A ?? =A , B.A ?U = U C.A ?? = ?, D.A ?U = U 4、集合A={1,2,…,10}上的关系R={