离散数学试题(A) (2001计算机) 2002.7
班级,学号,姓名:
总分
1
2
3
4
5
6
7
一,填空(共计26分)
1,(每空1分) 令P,天气好,Q,我有时间,R,我在家,S,我上街,
将下面各个命题的符号表达式填在各个命题后面的括号内..
⑴,或者我上街,或者我在家,( )
⑵ 仅当天气好,我才上街,( )
⑶ 如果天气好,我就上街,否则在家.( )
2.(每个空2分) 用给定谓词将命题符号化（论域都是“全总个体域” ）
⑴．（令(A(x):x是人,B(x,y):y是x说的话,C(x):x是谎话,D(x):x是可信的)命题“如果一个人只说谎话,那么他说的话没有一句是可信的.”的符号表达式为：
（ ）
⑵．(A(x):x属于A,B(x):x属于B).A、B是集合,命题“A(B” 的符号表达式 为：
（ ）
⑶．( Y(x):x是年号; D(x,y):x可整除y; R(x):x是闰年 )
下面是判定一个年号是否为闰年的命题:,年号能被4整除并且不能被100整除
的为闰年,或者年号能被400整除的也是闰年.” 该命题的符号表达式为：
（ ）
3.(每空1分)A,B是有限集合,P(A)表示A的幂集,已知|A|=3,|P(B)|=64,
|P(A∪B)|=256,则|B|=( ),|A∩B|=( ),|A-B|=( ),|A(B|=( )
4.(每空2分)设F表示一年级大学生的集合,M表示数学专业学生的集合,C表示计算机专业学生的集合,D表示学离散数学课学生的集合,G表示星期六晚上参加音乐会的学生的集合,H表示星期六晚上很迟才睡觉的学生集合。将下面各个句子所对应的集合表达式分别写在句子后面的括号内:
(1)这些且只有这些学离散数学课的学生或者星期六晚上去听音乐会的学生在星期六晚上很晚才睡觉,( )
(2)除去数学专业和计算机专业以外的一年级的学生都去参加星期六晚上的音乐会,( )
5.（3分）A与B是全集E的子集,给定集合X={P,Q,R,S,T,U,V,W,Y,Z},其中的元素都表示命题，如下所示,
P:A－B=A Q:A(B=B R:A(B S,A((B T,B(A
U,(B((A V:A(B=Φ W:A(B=B Y,(A((B Z,B((A
又令R是X上的命题等价关系,则商集X/R=( )
6.(每空1分)令R和S都是人类上的关系，且
R={<x,y>|x是y的父亲} S={<x,y>|x是y的母亲} 则
S(R表示( )关系； R(SC表示( )关系。
7.(每空1分) 令<G,*>是群,其中G={a,b,c},设a是幺元,则b2=( ),b*c=( )
b和c的阶分别是( )，（ )。
二．（9分）判断下面题各个命题的真值，并给予证明或举反例。
已知R是A上的反自反的、传递的二元关系，则Ｒ也是反对称的.
2．<G,(>是个群,且|G|=11,任取a,b∈G,且a,b不是幺元,设a,b的阶分别是m和ｎ，令A={a1,a2,a3,…,am},B={b1,b2,b3,…,bn},则A(G 且 B(G。
令E是非空集合,<P(E),∪,∩>是环。 (其中P(E)是E的幂集。)
三．（20分）有四个小题写出命题公式(P→Q)→?(Q(R) 的主合取范式。(符号?表示否定)
2．设Ｐ表示"今天天气好"，Ｑ表示"我们去旅游"，用最简单明了的汉语描述下面命题公式所表达的含义。
(((P∨Q)→(P∧(Q))∨((P→Q))∧Q
3．令Ａ={0,1,2,3,4,....} B={1,2,4,8,16,..,}
＋表示加法，(表示乘法。问：<Ａ，＋>与<Ｂ，(>是否同构？为什么？
4,集合Ａ＝{a,b,c,d,e,f,g}，R1、R2是A上的等价关系,且已知商集:
A/R1={{a,b,c},{d,e,g,f}}
A/R2={{a,c},{b,d},{e,f,g}}
显然R1∩R2是A上的等价关系 试求商集A/R1∩R2.
任取x∈A，试给出等价类[x]R1∩R2、[x]R1以及[x]R2之间的关系，并证明之。
5.设S={0,1},F是S中的符号构成的长度（即所含符号个数）不超过3的符号串
的集合,即
F={λ,0,1,00,01,10,11,000,001,010,011,100,101,110,111}
其中λ表示空符号串(即没有字符的符号串,λ的长度为0),在F上定义关系
R如下,对于任何x,y∈F
<x,y>∈R ( x是y的前缀.
例如0是00,01的前缀,但是01不是001的前缀,显然R是F上的偏序关系.
画出R的哈斯图.
2．求F的极小元和最大元.
四．(12分)用谓词逻辑推理方法,证明下面推理的有效性,
(要求按照教材规定的格式,书写推理过程)
(xP(x)((x((P(x)(Q(x))(R(x)),(xP(x),(xQ(x) ((x(y(R(x)(R(y))
五．(6分)证明由格<A,≤>诱导的代数系统<A,∧,∨>中满足吸收律。
六．.(15分)设<G,(>是群,a∈G,定义函数fa:G(G为,
任何x∈G 有 fa(x)=a(x
1.求证fa:G(G是入射的.
2,设F={ fa:G(G | a∈G},即F是G中所有元素a 定义的函数构成的集合,
令“(” 是函数的左复合运算,求证<F,(> 是个群.
七（12分）有四个小题
G是个有n个结点的简单图，n是个大于2的奇数，如果G中有k个奇数度的结点，那么G的补图中有奇数度的结点也是k个。
请画出有４个结点的无向完全图K4的所有不同构的生成子图。
乒乓球单打比赛采用淘汰制，即一名选手在一次比赛中失败就被淘汰。用结点表示选手，如果两个选手进行过比赛，这两个结点之间就连一条边。如果有n个选手参赛，共需要多少场比赛？为什么？（用图论的知识解答）
4.根据给定一组权值:1,2,1,3,2,4,3,5,6,5,8,7 画出一棵最优完全二叉树.
班级,学号,姓名:
总分
1
2
3
4
5
6
7
一,填空(共计26分)
1,(每空1分) 令P,天气好,Q,我有时间,R,我在家,S,我上街,
将下面各个命题的符号表达式填在各个命题后面的括号内..
⑴,或者我上街,或者我在家,( )
⑵ 仅当天气好,我才上街,( )
⑶ 如果天气好,我就上街,否则在家.( )
2.(每个空2分) 用给定谓词将命题符号化（论域都是“全总个体域” ）
⑴．（令(A(x):x是人,B(x,y):y是x说的话,C(x):x是谎话,D(x):x是可信的)命题“如果一个人只说谎话,那么他说的话没有一句是可信的.”的符号表达式为：
（ ）
⑵．(A(x):x属于A,B(x):x属于B).A、B是集合,命题“A(B” 的符号表达式 为：
（ ）
⑶．( Y(x):x是年号; D(x,y):x可整除y; R(x):x是闰年 )
下面是判定一个年号是否为闰年的命题:,年号能被4整除并且不能被100整除
的为闰年,或者年号能被400整除的也是闰年.” 该命题的符号表达式为：
（ ）
3.(每空1分)A,B是有限集合,P(A)表示A的幂集,已知|A|=3,|P(B)|=64,
|P(A∪B)|=256,则|B|=( ),|A∩B|=( ),|A-B|=( ),|A(B|=( )
4.(每空2分)设F表示一年级大学生的集合,M表示数学专业学生的集合,C表示计算机专业学生的集合,D表示学离散数学课学生的集合,G表示星期六晚上参加音乐会的学生的集合,H表示星期六晚上很迟才睡觉的学生集合。将下面各个句子所对应的集合表达式分别写在句子后面的括号内:
(1)这些且只有这些学离散数学课的学生或者星期六晚上去听音乐会的学生在星期六晚上很晚才睡觉,( )
(2)除去数学专业和计算机专业以外的一年级的学生都去参加星期六晚上的音乐会,( )
5.（3分）A与B是全集E的子集,给定集合X={P,Q,R,S,T,U,V,W,Y,Z},其中的元素都表示命题，如下所示,
P:A－B=A Q:A(B=B R:A(B S,A((B T,B(A
U,(B((A V:A(B=Φ W:A(B=B Y,(A((B Z,B((A
又令R是X上的命题等价关系,则商集X/R=( )
6.(每空1分)令R和S都是人类上的关系，且
R={<x,y>|x是y的父亲} S={<x,y>|x是y的母亲} 则
S(R表示( )关系； R(SC表示( )关系。
7.(每空1分) 令<G,*>是群,其中G={a,b,c},设a是幺元,则b2=( ),b*c=( )
b和c的阶分别是( )，（ )。
二．（9分）判断下面题各个命题的真值，并给予证明或举反例。
已知R是A上的反自反的、传递的二元关系，则Ｒ也是反对称的.
2．<G,(>是个群,且|G|=11,任取a,b∈G,且a,b不是幺元,设a,b的阶分别是m和ｎ，令A={a1,a2,a3,…,am},B={b1,b2,b3,…,bn},则A(G 且 B(G。
令E是非空集合,<P(E),∪,∩>是环。 (其中P(E)是E的幂集。)
三．（20分）有四个小题写出命题公式(P→Q)→?(Q(R) 的主合取范式。(符号?表示否定)
2．设Ｐ表示"今天天气好"，Ｑ表示"我们去旅游"，用最简单明了的汉语描述下面命题公式所表达的含义。
(((P∨Q)→(P∧(Q))∨((P→Q))∧Q
3．令Ａ={0,1,2,3,4,....} B={1,2,4,8,16,..,}
＋表示加法，(表示乘法。问：<Ａ，＋>与<Ｂ，(>是否同构？为什么？
4,集合Ａ＝{a,b,c,d,e,f,g}，R1、R2是A上的等价关系,且已知商集:
A/R1={{a,b,c},{d,e,g,f}}
A/R2={{a,c},{b,d},{e,f,g}}
显然R1∩R2是A上的等价关系 试求商集A/R1∩R2.
任取x∈A，试给出等价类[x]R1∩R2、[x]R1以及[x]R2之间的关系，并证明之。
5.设S={0,1},F是S中的符号构成的长度（即所含符号个数）不超过3的符号串
的集合,即
F={λ,0,1,00,01,10,11,000,001,010,011,100,101,110,111}
其中λ表示空符号串(即没有字符的符号串,λ的长度为0),在F上定义关系
R如下,对于任何x,y∈F
<x,y>∈R ( x是y的前缀.
例如0是00,01的前缀,但是01不是001的前缀,显然R是F上的偏序关系.
画出R的哈斯图.
2．求F的极小元和最大元.
四．(12分)用谓词逻辑推理方法,证明下面推理的有效性,
(要求按照教材规定的格式,书写推理过程)
(xP(x)((x((P(x)(Q(x))(R(x)),(xP(x),(xQ(x) ((x(y(R(x)(R(y))
五．(6分)证明由格<A,≤>诱导的代数系统<A,∧,∨>中满足吸收律。
六．.(15分)设<G,(>是群,a∈G,定义函数fa:G(G为,
任何x∈G 有 fa(x)=a(x
1.求证fa:G(G是入射的.
2,设F={ fa:G(G | a∈G},即F是G中所有元素a 定义的函数构成的集合,
令“(” 是函数的左复合运算,求证<F,(> 是个群.
七（12分）有四个小题
G是个有n个结点的简单图，n是个大于2的奇数，如果G中有k个奇数度的结点，那么G的补图中有奇数度的结点也是k个。
请画出有４个结点的无向完全图K4的所有不同构的生成子图。
乒乓球单打比赛采用淘汰制，即一名选手在一次比赛中失败就被淘汰。用结点表示选手，如果两个选手进行过比赛，这两个结点之间就连一条边。如果有n个选手参赛，共需要多少场比赛？为什么？（用图论的知识解答）
4.根据给定一组权值:1,2,1,3,2,4,3,5,6,5,8,7 画出一棵最优完全二叉树.
