2004～2005 学年第 二 学期科目,离散数学 考试试题A卷答案命题教师,李伟勋 使用班级：计科04-1班
一、1．A 2．C 3．C 4．D 5．A 6．B 7．B 8．A 9．C 10．C
二、11． 12． 13．{a，b，c}，{b，c，d}
14．反对称性，
15．
；；
16．； 17．； 8．1，1； 19．4，18；20．
三、21．解：（1）令P：天下雨，Q：我们去郊游。 1分该命题可符号化为。 1分天不下雨是去郊游的充分条件 1分
（2）令P：天下雨，Q：我们去郊游。
该命题可符号化为或。 1分天不下雨是去郊游的必要条件 1分
22．解：设题中的公式为A，则
A
1分
2分
4分
,此即该公式的主析取范式.由此即推得它的主合取范式为
= 5分
23．解,⑴ 1分
⑵ 1分
⑶ 2分
⑷
24．解：从Ｒ的表达式可知，x∈A，（x，x）∈R，即Ｒ具有自反性,1分由Ｒ的表达式，x，y∈A,(x,y)∈R,则(y,x)∈Ｒ，Ｒ具有对称性。 3分又有x，y，z∈Ａ，(x，y)∈R且（y，ｚ）∈Ｒ，则（x，ｚ）∈Ｒ,
于是Ｒ具有传递性。故Ｒ是Ａ上的等价关系。 5分
6．解：强分图为 2分。单向分图为,3分
25．解：易知，二元运算满足交换律
. 对 即是单位元.
,的逆元记作，有 （单位元）
．
三．计算题（二）
27．解：
1分
2分
（加法对乘法的分配律） 4分
5分
28．解：
四．29．证明：（参考答案）
用反证法，假设((xQ(x)成立。
（1）(x(P(x) 前提
（2）(P(y) （1）；US
（3）((xQ(x) 假设
（4）(x(Q(x) （3）
（5）(Q(y) （4）；US
（6）(P(y)((Q(y) （2），（5）
（7）((P(y) (Q(y)) （6）
（8）(x(P(x)(Q(x)) 前提
（9）P(y) (Q(y) （8），US
（10）(P(y) (Q(y)) (((P(y) (Q(y)) （7），（9）
因为(P(y) (Q(y)) (((P(y) (Q(y))是恒假公式，所以(x(P(x)(Q(x))，(x(P(x)((xQ(x)。
30．证明 ，存在使。由于，得知，即在G上是封闭的。
由整数运算的性质可知，是可结合的。
，对，有，故0是G的单位元。
，存在使，由于，，且。故是a的逆元。
综上所述，是一个群。
2004～2005 学年第 二 学期
科目,离散数学 考试试题B卷答案
命题教师,李伟勋 使用班级：计科04－1班一、选择题
1．A 2．B 3．C 4．C 5．A 6．C 7．B 8．A 9．C 10．C
二、11．矛盾式；重言式；
12．设R(x)：x为实数，则命题可符号化为；
13．B；A；14．{<a,c>,<a,d>}，{<a,a>,<a,b>,<a,d>}；15．{a，b，c}，{b，c，d}；16．反对称性；17．；18．1，1；19．4，18；20．偶数三、21．解：（1）令P：天下雨，Q：我们去郊游。
该命题可符号化为。（天不下雨是去郊游的充分条件） 3分
（2）令P：天下雨，Q：我们去郊游。
该命题可符号化为或。（天不下雨是去郊游的必要条件） 5分
22．解：
4分
∴命题公式的主析取范式为
。
②求主合取范式由①知命题公式的主合取范式为
5分
23．解：
24．解
∴
25．解：i)
（1）因为，
所以R是自反的；
（2）因为
而，所以R是对称的；
（3）因为，所以具有传递性．由（1）(2)(3)可知R在A上式等价关系。
26．解：任意两个正整数的最小公倍数仍是一个正整数，即在Z+上是封闭的，故是Z+上的二元运算。
，设，，则有
即
同理可证。故有，即。所以是可结合的。从而是一个半群。
因为，有，故1是单位元，即是含单位元的半群。
四．计算题（二）
27．解：
（结合律，分配律）
（）
（交换律，分配律，结合律）
（）
8．解：解
从到长度为2的通路有1条：。
从到长度为3的通路有2条：，。
四．1．证明 （1） P
（2） T（1）（换名规则）
（3） T（2）（前束范式性质2）
（4） T（3）（US规则）
（5） T（4）（US规则）
（6） T（5）（UG规则）
证二 （1） P（附加）
（2） T（1）（等值置换）
（3） T（2）（ES规则）
（4） T（3）（化简规则）
（5） T（4）（EG规则）
（6） P
（7） T（6）（等值置换）
（8） T（5），（7）（假言推理）
（9） T（8）（US规则）
（10） T（3）（化简规则）
（11） T（9），（10）（合取引入）
2．证明,
所以运算在Z上是封闭的，可结合的。
又，有，使，所以运算有单位元2。
，有，使
，
所以Z中每一元素均有逆元。
综上所述，是群。
一、1．A 2．C 3．C 4．D 5．A 6．B 7．B 8．A 9．C 10．C
二、11． 12． 13．{a，b，c}，{b，c，d}
14．反对称性，
15．
；；
16．； 17．； 8．1，1； 19．4，18；20．
三、21．解：（1）令P：天下雨，Q：我们去郊游。 1分该命题可符号化为。 1分天不下雨是去郊游的充分条件 1分
（2）令P：天下雨，Q：我们去郊游。
该命题可符号化为或。 1分天不下雨是去郊游的必要条件 1分
22．解：设题中的公式为A，则
A
1分
2分
4分
,此即该公式的主析取范式.由此即推得它的主合取范式为
= 5分
23．解,⑴ 1分
⑵ 1分
⑶ 2分
⑷
24．解：从Ｒ的表达式可知，x∈A，（x，x）∈R，即Ｒ具有自反性,1分由Ｒ的表达式，x，y∈A,(x,y)∈R,则(y,x)∈Ｒ，Ｒ具有对称性。 3分又有x，y，z∈Ａ，(x，y)∈R且（y，ｚ）∈Ｒ，则（x，ｚ）∈Ｒ,
于是Ｒ具有传递性。故Ｒ是Ａ上的等价关系。 5分
6．解：强分图为 2分。单向分图为,3分
25．解：易知，二元运算满足交换律
. 对 即是单位元.
,的逆元记作，有 （单位元）
．
三．计算题（二）
27．解：
1分
2分
（加法对乘法的分配律） 4分
5分
28．解：
四．29．证明：（参考答案）
用反证法，假设((xQ(x)成立。
（1）(x(P(x) 前提
（2）(P(y) （1）；US
（3）((xQ(x) 假设
（4）(x(Q(x) （3）
（5）(Q(y) （4）；US
（6）(P(y)((Q(y) （2），（5）
（7）((P(y) (Q(y)) （6）
（8）(x(P(x)(Q(x)) 前提
（9）P(y) (Q(y) （8），US
（10）(P(y) (Q(y)) (((P(y) (Q(y)) （7），（9）
因为(P(y) (Q(y)) (((P(y) (Q(y))是恒假公式，所以(x(P(x)(Q(x))，(x(P(x)((xQ(x)。
30．证明 ，存在使。由于，得知，即在G上是封闭的。
由整数运算的性质可知，是可结合的。
，对，有，故0是G的单位元。
，存在使，由于，，且。故是a的逆元。
综上所述，是一个群。
2004～2005 学年第 二 学期
科目,离散数学 考试试题B卷答案
命题教师,李伟勋 使用班级：计科04－1班一、选择题
1．A 2．B 3．C 4．C 5．A 6．C 7．B 8．A 9．C 10．C
二、11．矛盾式；重言式；
12．设R(x)：x为实数，则命题可符号化为；
13．B；A；14．{<a,c>,<a,d>}，{<a,a>,<a,b>,<a,d>}；15．{a，b，c}，{b，c，d}；16．反对称性；17．；18．1，1；19．4，18；20．偶数三、21．解：（1）令P：天下雨，Q：我们去郊游。
该命题可符号化为。（天不下雨是去郊游的充分条件） 3分
（2）令P：天下雨，Q：我们去郊游。
该命题可符号化为或。（天不下雨是去郊游的必要条件） 5分
22．解：
4分
∴命题公式的主析取范式为
。
②求主合取范式由①知命题公式的主合取范式为
5分
23．解：
24．解
∴
25．解：i)
（1）因为，
所以R是自反的；
（2）因为
而，所以R是对称的；
（3）因为，所以具有传递性．由（1）(2)(3)可知R在A上式等价关系。
26．解：任意两个正整数的最小公倍数仍是一个正整数，即在Z+上是封闭的，故是Z+上的二元运算。
，设，，则有
即
同理可证。故有，即。所以是可结合的。从而是一个半群。
因为，有，故1是单位元，即是含单位元的半群。
四．计算题（二）
27．解：
（结合律，分配律）
（）
（交换律，分配律，结合律）
（）
8．解：解
从到长度为2的通路有1条：。
从到长度为3的通路有2条：，。
四．1．证明 （1） P
（2） T（1）（换名规则）
（3） T（2）（前束范式性质2）
（4） T（3）（US规则）
（5） T（4）（US规则）
（6） T（5）（UG规则）
证二 （1） P（附加）
（2） T（1）（等值置换）
（3） T（2）（ES规则）
（4） T（3）（化简规则）
（5） T（4）（EG规则）
（6） P
（7） T（6）（等值置换）
（8） T（5），（7）（假言推理）
（9） T（8）（US规则）
（10） T（3）（化简规则）
（11） T（9），（10）（合取引入）
2．证明,
所以运算在Z上是封闭的，可结合的。
又，有，使，所以运算有单位元2。
，有，使
，
所以Z中每一元素均有逆元。
综上所述，是群。
