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