离散数学综合练习
- 格式：doc
- 大小：2.72 MB
- 文档页数：12
北京科技大学远程教育学院 《离散数学》综合练习一参考答案 数理逻辑 一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。 1、今天天气真好！ 解：不是命题。 2、王华和张民是同学。 解：是命题。真值视实际情况而定。p：王华和张民是同学。 3、我一边吃饭，一边看电视。 解：是命题。真值视实际情况而定。p：我吃饭。q：我看电视。pq 4、没有不呼吸的人。 解：是命题。真值为1。Mx：x是人。Fx：x呼吸。xMxFx 二、求命题公式的真值表和成真赋值、成假赋值。
)(])[(rprqp 解： p q r pq rqp)( rp )(])[(rprqp
0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 成真赋值：000，001，010，011，101，111；成假赋值100，110 三、用真值表、等值演算两种方法判别公式类型。
1、rqqp])[( 解： p q
r
pq qqp)( rqqp])[(
0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1
rqqprqqqprqqprqqprqqprqqp])[()]()[()()(])[(])[( 可满足式 2、))((pqpq
解：))((pqpqA p q qp pqp)( ))((pqp A
0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 0 1
1)()()())((qpqppqpqpqpq 永真式 四、求命题公式的主析取范式和成真赋值、成假赋值。
)(rqp 解： p q
r
)(rqp
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1
），，，，，，7543210()(rqp
成真赋值：000，001，010，011，100，101，111；成假赋值110 五、解释I如下：D是实数集，特定元素a=0；特定函数fx，y=xy； 特定谓词Fx，y：x
1、)])(([xyxfFyx，， 解：
)])[()])(([)]([)])(([xyxyxxyxyxxyxFyxxyxfFyx，，，
真值为假 2、)]()([)({zyfzxfFyxFzyx，，，， 解： )]()()[()]}()([)({zyzxyxzyxzyfzxfFyxFzyx，，，， 真值为真 六、 1、求前束范式)()(yxyGxxF， 解：
)]()([)()()()()()(ytGxFyxytyGxxFyxyGxxFyxyGxxF，，，，
2、证明：BxxABxAx)())(( 证明：
BxxABxxABxAxBxAxBxAx)()()())(())((
七、写出下面推理的证明，要求写出前提、结论，并注明 推理规则。 （1）如果乙不参加篮球赛，那么甲就不参加篮球赛。若乙参加篮球赛，那么甲和丙就参加篮球赛。因此，如果甲参加篮球赛，则丙就参加篮球赛。 解： p：甲参加篮球赛。q：乙参加篮球赛。r：丙参加篮球赛。 前提： q p ，q pr ， 结论：p r 证明：① q p 前提引入 ② pq ①置换 ③ q pr 前提引入 ④ q pr ③置换 ⑤ q p q r ④置换 ⑥ q r ⑤化简 ⑦ q r ⑥置换 ⑧ p r ②⑦假言三段论 推理正确 （2）学会的成员都是专家。有些成员是青年人。所以，有些成员是青年专家。个体域是人的集合 Fx：x 是学会成员。Gx：x 是专家。Hx：x 是青年人。 前提：x Fx Gx，x Fx Hx 结论：x Fx Hx Gx 证明：① x Fx Hx 前提引入 ② Fc Hc ①EI ③ x Fx Gx 前提引入 ④ Fc Gc ③UI ⑤ Fc ②化简 ⑥ Gc ⑤④假言推理 ⑦ Fc Hc Gc ②⑥ 合取 ⑧ x Fx Hx Gx ⑦EG 推理正确 《离散数学》综合练习二参考答案 集合、关系、函数 一、判断题 1、对任意集合A，都有AA和A A，不能同时成立。 （ F ） 2、R1、R2是A上的具有自反性的二元关系，R1－R2也具有自反性。 （ F ） 3、A上恒等关系IA具有自反性、对称性、反对称性、传递性。 （ T ） 4、f：AB，g：BC，若fog是AC的满射，则f、g都是满射。 （ F ） 5、A =｛1，2，3，4｝，f是从A到A的满射，则也是从A到A的单射。 （ T ） 二、填空题 1、A－B∪AB = A 。 2、A有2个元素，B有3个元素，从A到B的二元关系有 26 个。 3、R是A上的二元关系，RoR－1一定具有的性质是 对称性 。 4、fx= lnx 是从 R+ 到 R 的函数。 5、f、g都是从A到A的双射，(fog)－1 = g－1of－1 。 三、集合 1、A={{a，{b}}，c，{c}，{a，b}}、B={{a，b}，c，{b}} 求A∪B、A∩B、A－B、AB 解：
}}{},{}},{,{{}{}}{}},{,{{)()(}}{}},{,{{}},{,{}}{,},,{},,{},{,}},{,{{bcbabcbaABBABAcbaBAbacBAbcbabaccbaBA
2、A={{a，{b}}，c，Ø} 求A的幂集。 解：PA={Ø，｛Ø｝，{{a，{b}}}，｛c｝，｛{a，{b}}，c｝，｛{a，{b}}，Ø｝，｛c，Ø｝}，A} 3、证明：A－B∪C = A－B∩A－C
解：)()()()(CABACABACBACBACBA 四、二元关系（共30分）
1、A＝{a，b，c，b}，R＝{，，，} 用关系矩阵求R4，写出R4的集合表示。 2、指出二元关系满足哪种性质，不满足哪种性质，说明理由。
解：满足反对称性；不满足自反性，反自反性，对称性，传递性 3、A =｛1，2，3，4，5，6｝，S =｛｛1，2｝，｛3｝，｛4，5，6｝｝ 画出由S产生的等价关系的关系图。 解： 4、画出偏序集的哈斯图，并指出最大元、最小元、极大元、极小元。 ｛1，2，3，…，12｝整除关系 解：
最大元：无；最小元、极小元：1；极大元：7，8，9，10，11，12 五、函数 1、确定以下各题中f是否是从AB的函数，若是指出是否是单射、满射、双射， 如果不是说明理由。 （1）A=｛1，2，3，4，5｝、B=｛5，6，7，8，9｝ f=｛1，8，3，9，4，10，2，6，5，9｝ 解：f 是函数，由3，9，5，9 f 不是单射，也不是满射。
（2）A=｛1，2，3，4，5｝、B=｛5，6，7，8，9｝ f=｛1，7，2，6，4，8，1，9，5，10｝ 解：由1，7，1，9，f 不是函数。 （3）A、B都是实数集，fx = x3。 解：f 是函数， f 是单射，也是满射，f 是双射。
（4）A、B都是正整数集，1111)(xxxxf 解：f 是函数， f 是单射，不是满射。 2、aA，b，c，d，g、h都是AA的函数。 g：ba，ab，dc，cd
h：ba，cb，bc，cd
g、h中哪个有反函数？若有则求出反函数。求出复合函数)(xgg、)(xgh。 解：g 是双射，有反函数，就是 g 自己。1g：ba，ab，dc，cd )(xgg：aa，bb，cc，dd
)(xgh：aa，db，ac，dd
3、A、B都是有n个元素的集合，f：AB的函数。 证明：f是单射 f是满射。
证明：设f是单射，由于Axx21，)()(21xfxf，所以ranf 有n 个元素，
又 Branf，而 B 也只有 n 个元素，所以 Branf 设f是满射，若 f 不是单射，则 Axx21，)()(21xfxf， 由于 A 中只有 n 个元素，所以 Branf，与 Branf 矛盾。
《离散数学》综合练习三参考答案 代数系统 一、判断题 1、｛0，1，2，…，n｝对普通加法封闭。 （F） 2、在非负整数集Z+上定义运算·，x·y = min｛x，y｝，1是运算的幺元。（T） 3、实数集与普通乘法构成的代数系统中每个元素都有逆元素。 （F） 4、在代数系统Z，+，0中，0是零元。 （F） 5、非负整数集Z+与普通加法构成的代数系统是群。 （F） 6、M是n阶可逆矩阵的集合，×是矩阵乘法，M，×是群。 （T） 7、循环群的子群是循环群。 （T） 8、代数系统Z，+是代数系统R*，+的子代数。 （F） 二、填空题 1、A =｛x | x = 3n ，nN｝，对 乘法 运算封闭。 2、R*，+构成的代数系统是 半群 。 3、在代数系统Z，+，0中，0是 单位 元。 4、F =｛f | f：AA｝，o为函数的复合运算，F，o的单位元是 恒等函数 。 5、f、g都是从A到A的双射，(fog)－1 = g－1of－1 。 6、在代数系统S，*中，元素a、b都有逆元，则a－1－1= a ，a*b－1=b－1*a－1 。 7、循环群有 生成 元，使循环群中元素都是该元素的方幂。 8、V1=S1，o，V2=S2，*都有幺元，是V1到V2的同态，则把V1中的单 位元映射到 V2中的单位元 。 三、解答题 1、Q＋是正有理数集，×是普通乘法，Q+，×是否是半群、独异点、群？ 解：普通乘法有结合律，单位元是 1 ，但 0 没有逆元，Q+，×是独异点。
