离散数学第五章答案
离散数学第五章答案
【篇一：3~离散数学习题解答(第五章)格与布尔代数5】
题五（第五章格与布尔代数）
1．设〈l，?〉是半序集，?是l上的整除关系。问当l取下列集合时，〈l，?〉是否是格。 a) l={1，2，3，4，6，12}
b) l={1，2，3，4，6，8，12}
c) l={1，2，3，4，5，6，8，9，10}
[解] a) 〈l，?〉是格，因为l中任两个元素都有上、下确界。
6
3
1
b) 〈l，?〉不是格。因为l中存在着两个元素没有上确界。
例如：8?12=lub{8，12}不存在。
12 6
3 1
c) 〈l，?〉不是格。因为l中存在着两个元素没有上确界。
倒例如：4?6=lub{4，6}不存在。
7
1
2．设a，b是两个集合，f是从a到b的映射。证明：〈s，?〉是〈2b，?〉的子格。其中
s={y|y=f (x)，x∈2a}
[证] 对于任何b1∈s，存在着a1∈2a，使b1=f（a1），由于
f(a1)={y|y∈b∧(?x)(x∈a1∧f (x)=y)}
?b 所以b1∈2b，故此s?2b；又b0=f (a)∈s (因为a∈2a)，所以s
非空；
对于任何b1，b2∈s，存在着a1，a2∈2a，使得b1=f (a1)，b2=f (a2)，从而
l∪b{b1，b2}=b1∪b2=f (a1)f (a2)
=f (a1∪a2) （习题三的8的1））
由于a1∪a2?a，即a1∪a2∈2a，因此f (a1∪a2)∈s，即上确界
l∪b{b1，b2}存在。
对于任何b1，b2∈s，定义a1=f –1(b1)={x|x∈a∧f (x)∈b1}，
a2=f-1(b2)={x|x∈a∧f (x)∈b2}，则a1，a2∈2a，且显然b1=f (a1)，b2=f (a2)，于是
glb{b1，b2}=b1∩b2=f (a1)∩f (a2)
?f (a1∩a2) （习题三的8的2））
又若y∈b1∩b2，则y∈b，且y∈b2。由于y∈b1=f
(a1)={y|y∈b∧(?x)(x∈a1∧f (x)=y)}，于是存在着x∈a1，使f
(x)=y，但是f (x)=y∈b2。故此x∈a2=f-1(b2)={x|x∈a∧f(x)∈b2}，因此x∈a1∩a2，从而y=f (x)∈f (a1∩a2)，所以
glb{b1，b2}=b1∩b2=f (a1)∩f (a2) ?f (a1∩a2)
这说明 glb{b1，b2}=b1∩b2=f (a1)∩f (a2)=f (a1∩a2)于是从
a1∩a2∈2a可知f (a1∩a2)∈s，即下确界glb{b1，b2}存在。
因此，〈s，?〉是〈2b，?〉的子格。
3．设〈l，?〉是格，任取a，b∈l且a?b。证明〈b，?〉是格。其中
b={x|x∈l 且 a?x?b}
[证] 显然b?l；根据自反性及a?b?b
所以a，b∈b，故此b非空；
对于任何x，y∈b，则有a?x?b及a?y?b，由于x，y∈l，故有
z1=x?y为下确界∈l存在。我们只需证明z1，z2∈b即可，证明方
法有二，方法一为：
由于
a?x，所以a?x=x，于是
z1=x?y
=(a?x) ?y （利用a?x=x）
=a? (x?y) （由?运算结合律）
因此a?z1；另一方面，由y?b可知y?b=b，由x?b可知x?b=b，
于是
z1?b=(x?y) ?b
=x?(y?b)（由?运算结合律）
=x?b （利用y?b=b）
=b （利用x?b=b）
因此 z1?b，即 a?z1?b所以z1∈b
由于a?x及a?y，所以a*x=a，a*y=a，因而
a*z2=a* (x*y)
=(a*x) *y （由*运算结合律）
=a*y（利用a*x=a）
=a （利用a*y=a）
因而a?z2；又由于y?b，所以y*b=y 于是
z2=x*y
=x* (y*b)
=(x*y) *b （利用*运算结合律）
=z2*b
从而z2?b，即a?z2?b所以z2∈b
因此〈b，?〉是格（是格〈l，?〉的子格）。
方法二：根据上、下确界性质，由a?x，a?y，可得a?x*y，（见附页数）
4．设〈l，?，*，?〉是格。?a，b∈l，证明：（附页）
a?x??y，即a?z2，a?
又由x?b，y?b，可得x?y?b，x*y?y?b，即z1?b，z2?b
所以a?z1?b，a?z2?b，故此z1，z2∈b
a*b?a且a*b?b?a与b是不可比较的。
[证] 先证?
用反证法，假设a与b是可比较的，于是有a?b或者b?a。
当a?b时，a*b=a与a*b?a（得a*b≠a）矛盾；
当b?a时，a*b=b与a*b?b（得a*b≠b）矛盾；
因此假设错误，a与b是不可比较的。
次证?
由于a*b?a，a*b?b。如果a*b?a，则a?b，与a和b不可比较的
已知条件矛盾，所以a*b≠a，故此a*b?a；如果a*b=b，则b?a，也与a和b不可比较的已知条件矛盾，所以a*b≠b，故此可得a*b?b。 5．设〈l，?，*，?〉是格。证明：
a) (a*b) ? (c*d)?(a? c) * (b? d)
b) (a*b) ? (b*c)?(c ? a)?(a?b) * (b?c) * (c?a)
[证] a) 方法一，根据上、下确界的性质，由
a*b?a?a?c及a*b?b?b?d 所以得到
a*b?(a?c) * (b?d)
又由 c*d?c?a?c及c*d?d?b?d，所以得到
c*d?(a?c) * (b?d)
因此(a*b) ? (c*d) ? (a?c) * (b?d)
方法二 (a*b) ? (c*d)
?[(a?c) * (a?d)] * [(a?c) * (b?d)]
（分配不等式，交换律，结合律，保序性）
?(a?c) * (b?d)（保序性）
b) 方法一，根据上、下确界的性质
由a*b?a?a?b，a*b?b?b?c，a*b?a?c?a可得
a*b?(a?b) * (b?c) * (c?a)
同理可得
b*c?(a?b) * (b?c) * (c?a)
及 c*a?(a?b) * (b?c) * (c?a)
所以
(a?b) ? (b?c) ? (c?a)?(a?b) * (b?c) * (c?a)
方法二：(a?b) ? (b?c) ? (c?a)
?[b* (a?c)] ? (c*a) （交换律，结合律，分配不等式，保序性） ?[b? (c*a)] * [(a?c) ? (c*a)]（分配不等式，交换律，）
?[(a?b) * (b?c)] * (a?c)（分配不等式，结合律，交换律，吸收律，保序性）
?(a?b) * (b?c) * (c?a) （结合律）
6．设i是整数集合。证明：〈i，min，max〉是分配格。
[证] 由于整数集合i是全序集，所以任何两个整数的最小者和最大者是存在的，因此〈i，min，max〉
是格是显然的。
下面我们来证〈i，min，max〉满足分配律
对于任何a，b，c∈i 有
a* (b?c)=min{a，max{b，c}}
(a*b) ? (a*c)=min{min{a，b}，min{a，c}}
（1）若b≤c时，当
（a）a≤b，则a≤c ，故此
min{a，max{b，c}}=min{a，c}=a
max{min{a，b}，min{a，c}}=max{a，a}=a
（b）b≤a≤c ，则
min{a，max{b，c}}=min{a，c}=a
max{min{a，b}，min{a，c}}=max{b，a}=a
（c）c≤a，则b≤a，因此
min{a，max{b，c}}=min{a，c}=c
max{min{a，b}，min{a，c}}=max{b，a}=c
（2）若c≤b时，当
（a）a≤c，则a≤b，故此
min{a，max{b，c}}=min{a，b}
max{min{a，b}，min{a，c}}=min{a，a}=a
（b）c≤a≤b，则
min{a，max{b，c}}=min{a，b}=a
max{min{a，b}，min{a，c}}=max{a，c}=a
（c）b≤a，则c≤a，因此
min{a，max{b，c}}=min{a，b}=b
max{min{a，b}}，min{a，c}}=max{b，c}=b
综合（1）（2）总有
a* (b?c)=(a?b) * (a? c)
【篇二：离散数学习题解答(第五章)格与布尔代数】
题五（第五章格与布尔代数）
1．设〈l，?〉是半序集，?是l上的整除关系。问当l取下列集合时，〈l，?〉是否是格。
a) l={1，2，3，4，6，12}
b) l={1，2，3，4，6，8，12}
c) l={1，2，3，4，5，6，8，9，10}
[解] a) 〈l，?〉是格，因为l中任两个元素都有上、下确界。
6
3
1
b) 〈l，?〉不是格。因为l中存在着两个元素没有上确界。
例如：8?12=lub{8，12}不存在。
12 6
3 1
c) 〈l，?〉不是格。因为l中存在着两个元素没有上确界。
倒例如：4?6=lub{4，6}不存在。
7
1
2．设a，b是两个集合，f是从a到b的映射。证明：〈s，?〉是〈2b，?〉的子
格。其中
s={y|y=f (x)，x∈2a}
[证] 对于任何b1∈s，存在着a1∈2a，使b1=f（a1），由于
f(a1)={y|y∈b∧(?x)(x∈
a1∧f (x)=y)}?b 所以b1∈2b，故此s?2b；又b0=f (a)∈s (因为
a∈2a)，所以s非空；
对于任何b1，b2∈s，存在着a1，a2∈2a，使得b1=f (a1)，b2=f (a2)，从而
l∪b{b1，b2}=b1∪b2=f (a1)f (a2)
=f (a1∪a2) （习题三的8的1））
由于a1∪a2?a，即a1∪a2∈2a，因此f (a1∪a2)∈s，即上确界
l∪b{b1，b2}存在。
对于任何b1，b2∈s，定义a1=f –1(b1)={x|x∈a∧f (x)∈b1}，
a2=f-1(b2)={x|x∈a∧f (x)∈b2}，则a1，a2∈2a，且显然b1=f (a1)，b2=f (a2)，于是
glb{b1，b2}=b1∩b2=f (a1)∩f (a2)
?f (a1∩a2) （习题三的8的2））
又若y∈b1∩b2，则y∈b，且y∈b2。由于y∈b1=f
(a1)={y|y∈b∧(?x)(x∈a1∧f (x)=y)}，于是存在着x∈a1，使f
(x)=y，但是f (x)=y∈b2。故此x∈a2=f-1(b2)={x|x∈a∧f(x)∈b2}，因此x∈a1∩a2，从而y=f (x)∈f (a1∩a2)，所以
glb{b1，b2}=b1∩b2=f (a1)∩f (a2) ?f (a1∩a2)
这说明 glb{b1，b2}=b1∩b2=f (a1)∩f (a2)=f (a1∩a2)于是从
a1∩a2∈2a可知f (a1∩a2)∈s，即下确界glb{b1，b2}存在。
因此，〈s，?〉是〈2b，?〉的子格。
3．设〈l，?〉是格，任取a，b∈l且a?b。证明〈b，?〉是格。其中
b={x|x∈l 且 a?x?b}
[证] 显然b?l；根据自反性及a?b?b
所以a，b∈b，故此b非空；
对于任何x，y∈b，则有a?x?b及a?y?b，由于x，y∈l，故有
z1=x?y为下确界∈l存在。我们只需证明z1，z2∈b即可，证明方
法有二，方法一为：由于
a?x，所以a?x=x，于是
z1=x?y
=(a?x) ?y （利用a?x=x）
=a? (x?y) （由?运算结合律）
因此a?z1；另一方面，由y?b可知y?b=b，由x?b可知x?b=b，
于是
z1?b=(x?y) ?b
=x?(y?b)（由?运算结合律）
=x?b （利用y?b=b）
=b （利用x?b=b）
因此 z1?b，即 a?z1?b所以z1∈b
由于a?x及a?y，所以a*x=a，a*y=a，因而
a*z2=a* (x*y)
=(a*x) *y （由*运算结合律）
=a*y（利用a*x=a）
=a （利用a*y=a）
因而a?z2；又由于y?b，所以y
*b=y 于是
z2=x*y
=x* (y*b)
=(x*y) *b （利用*运算结合律）
=z2*b
从而z2?b，即a?z2?b所以z2∈b
因此〈b，?〉是格（是格〈l，?〉的子格）。
方法二：根据上、下确界性质，由a?x，a?y，可得a?x*y，（见附
页数）
4．设〈l，?，*，?〉是格。?a，b∈l，证明：（附页）
a?x??y，即a?z2，a?
又由x?b，y?b，可得x?y?b，x*y?y?b，即z1?b，z2?b
所以a?z1?b，a?z2?b，故此z1，z2∈b
a*b?a且a*b?b?a与b是不可比较的。
[证] 先证?
用反证法，假设a与b是可比较的，于是有a?b或者b?a。
当a?b时，a*b=a与a*b?a（得a*b≠a）矛盾；
当b?a时，a*b=b与a*b?b（得a*b≠b）矛盾；
因此假设错误，a与b是不可比较的。
次证?
由于a*b?a，a*b?b。如果a*b?a，则a?b，与a和b不可比较的
已知条件矛盾，所以a*b≠a，故此a*b?a；如果a*b=b，则b?a，也与a和b不可比较的已知条件矛盾，所以a*b≠b，故此可得a*b?b。 5．设〈l，?，*，?〉是格。证明：
a) (a*b) ? (c*d)?(a? c) * (b? d)
b) (a*b) ? (b*c)?(c ? a)?(a?b) * (b?c) * (c?a)
[证] a) 方法一，根据上、下确界的性质，由
a*b?a?a?c及a*b?b?b?d 所以得到
a*b?(a?c) * (b?d)
又由 c*d?c?a?c及c*d?d?b?d，所以得到
c*d?(a?c) * (b?d)
因此(a*b) ? (c*d) ? (a?c) * (b?d)
方法二 (a*b) ? (c*d)
?[(a?c) * (a?d)] * [(a?c) * (b?d)]
（分配不等式，交换律，结合律，保序性）
?(a?c) * (b?d)（保序性）
b) 方法一，根据上、下确界的性质
由a*b?a?a?b，a*b?b?b?c，a*b?a?c?a可得
a*b?(a?b) * (b?c) * (c?a)
同理可得
b*c?(a?b) * (b?c) * (c?a)
及 c*a?(a?b) * (b?c) * (c?a)
所以
(a?b) ? (b?c) ? (c?a)?(a?b) * (b?c) * (c?a)
方法二：(a?b) ? (b?c) ? (c?a)
?[b* (a?c)] ? (c*a) （交换律，结合律，分配不等式，保序
性） ?[b? (c*a)] * [(a?c) ? (c*a)]（分配不等式，交换律，）
?[(a?b) * (b?c)] * (a?c)（分配不等式，结合律，交换律，吸收律，保序性）
?(a?b) * (b?c) * (c?a) （结合律）
6．设i是整数集合。证明：〈i，min，max〉是分配格。
[证] 由于整数集合i是全序集，所以任何两个整数的最小者和最大者是存在的，因此
〈i，min，max〉是格是格是显然的。
下面我们来证〈i，min，max〉满足分配律
对于任何a，b，c∈i 有
a* (b?c)=min{a，max{b，c}}
(a*b) ? (a*c)=min{min{a，b}，min{a，c}}
（1）若b≤c时，当
（a）a≤b，则a≤c ，故此
min{a，max{b，c}}=min{a，c}=a
max{min{a，b}，min{a，c}}=max{a，a}=a
（b）b≤a≤c ，则
min{a，max{b，c}}=min{a，c}=a
max{min{a，b}，min{a，c}}=max{b，a}=a
（c）c≤a，则b≤a，因此
min{a，max{b，c}}=min{a，c}=c
max{min{a，b}，min{a，c}}=max{b，a}=c
（2）若c≤b时，当
（a）a≤c，则a≤b，故此
min{a，max{b，c}}=min{a，b}
max{min{a，b}，min{a，c}}=min{a，a}=a
（b）c≤a≤b，则
min{a，max{b，c}}=min{a，b}=a
【篇三：离散数学最全课后答案(屈婉玲版)】
略
1.3．略
1.4．略
1.5．略
1.6．略
1.7．略
1.8．略
1.9．略
1.10．略
1.11．略
1.12．将下列命题符号化, 并给出各命题的真值:
(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, 反之亦然.
(1)p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 1.
(2)p??q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 0.
(3) ?p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 0.
(4) ?p??q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 1.
1.13．将下列命题符号化, 并给出各命题的真值:
(1)若今天是星期一, 则明天是星期二. (2)只有今
天是星期一, 明天才是星期二. (3)今天是星期一
当且仅当明天是星期二. (4)若今天是星期一, 则
明天是星期三.
令 p: 今天是星期一; q: 明天是星期二; r: 明天是星期三.
(1) p?q ??1.
(2) q?p ??1.
(3) p?q ??1.
(4) p?r 当 p ??0 时为真; p ??1 时为假.
1.14．将下列命题符号化.
(1) 刘晓月跑得快, 跳得高.
(2)老王是山东人或河北人.
(3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组.
(5)李辛与李末是兄弟.
(6)王强与刘威都学过法语. (7)他一面吃
饭, 一面听音乐. (8)如果天下大雨, 他就乘
班车上班. (9)只有天下大雨, 他才乘班车
上班. (10)除非天下大雨, 他才乘班车上
班. (11)下雪路滑, 他迟到了.
(12)2 与 4 都是素数, 这是不对的.
(13)“2 或 4 是素数, 这是不对的”是不对的.
(1)p?q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高.
(2)p?q, 其中, p: 老王是山东人, q: 老王是河北人.
(3)p?q, 其中, p: 天气冷, q: 我穿了羽绒服.
(4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题.
(5)p, 其中, p: 李辛与李末是兄弟.
(6)p?q, 其中, p: 王强学过法语, q: 刘威学过法语.
(7)p?q, 其中, p: 他吃饭, q: 他听音乐.
(8)p?q, 其中, p: 天下大雨, q: 他乘班车上班.
(9)p?q, 其中, p: 他乘班车上班, q: 天下大雨.
(10)p?q, 其中, p: 他乘班车上班, q: 天下大雨.
(11)p?q, 其中, p: 下雪路滑, q: 他迟到了.
12) ??(p?q)或?p??q, 其中, p: 2 是素数, q: 4 是素数. (13) ???(p?q)或 p?q, 其中, p: 2 是素数, q: 4 是素数.
1.15．设 p: 2+3=5.
q: 大熊猫产在中国.
r: 复旦大学在广州. 求
下列复合命题的真值:
(1)(p?q) ?r
(2)(r??(p?q)) ???p
(3) ?r??(?p??q?r)
(4)(p?q??r) ??(( ?p??q) ?r)
(1)真值为 0.
(2)真值为 0.
(3)真值为 0.
(4)真值为 1.
注意: p, q 是真命题, r 是假命题.
1.16．
1.17．
1.18．
1.19．略略略用真值表判断下列公式的类型:
(1)p??(p?q?r)
(2)(p??q) ??q
(3) ??(q?r) ?r
(4)(p?q) ??(?q??p)
(5)(p?r) ??( ?p??q)
(6)((p?q) ??(q?r)) ??(p?r)
(7)(p?q) ??(r?s)
(1), (4), (6)为重言式.
(3)为矛盾式.
(2), (5), (7)为可满足式.
1.20．
1.21．
1.22．
1.23．
1.24．
1.25．
1.26．
1.27．
1.28．
1.29．
1.30．
1.31．略略略略略略略略略略略将下列命题符号化, 并给出各命题的真值:
(1)若 3+＝4, 则地球是静止不动的.
(2)若 3+2＝4, 则地球是运动不止的. (3)若地球
上没有树木, 则人类不能生存.
(4)若地球上没有水, 则 3 是无理数.
(1)p?q, 其中, p: 2+2＝4, q: 地球静止不动, 真值为 0.
(2)p?q, 其中, p: 2+2＝4, q: 地球运动不止, 真值为 1.
(3) ?p??q, 其中, p: 地球上有树木, q: 人类能生存, 真值为 1.
(4) ?p?q, 其中, p: 地球上有水, q:3 是无理数, 真值为 1.
2.1. 设公式 a = p?q, b = p??q, 用真值表验证公式 a 和 b 适合德摩根律:
?(a?b) ???a??b.
因为 ?(a?b)和 ?a??b 的真值表相同, 所以它们等值.
2.2. 略
2.3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值.
(1) ??(p?q?q)
(2)(p??(p?q)) ??(p?r)
(3)(p?q) ??(p?r)
(1) ??(p?q?q)????(?(p?q) ??q) ????(?p ???q ??q) ??p?q??q ??p?0 ??0 ??0. 矛盾式. (2)
重言式.
(3) (p?q) ??(p?r) ???(p?q) ??(p?r) ???p??q ??p?r 易见, 是可满足式, 但不是重言式. 成真赋值为: 000, 001, 101, 111
2.4. 用等值演算法证明下面等值式:
(1) p??(p?q) ??(p??q)
(3) ??(p?q) ??(p?q) ???(p?q)
(4) (p??q) ??(?p?q) ??(p?q) ???(p?q)
(1) (p?q) ??(p??q) ??p ??(q??q) ??p ??1 ??p.
(3) ??(p?q)
???((p?q) ??(q?p))
???((?p?q) ??(?q?p))
??(p??q) ??(q??p)
??(p?q) ??(p??p) ??(?q?q) ??(?p??q)
??(p?q) ???(p?q)
(4) (p??q) ??(?p?q)
??(p??p) ??(p?q) ??(?q??p) ??(?q?q)
??(p?q) ???(p?q)
2.5. 求下列公式的主析取范式, 并求成真赋值:
(1)( ?p?q) ??(?q?p)
(2) ??(p?q) ?q?r
(3)(p??(q?r)) ??(p?q?r)
(1)(?p?q) ??(?q?p)
???(p?q) ??(?q?p)
???p??q ???q ??p???p??q ???q ??p(吸收
律)??(p??p)??q ??p?(q??q) ??p??q ??p??q ??p?q ??p??q ??m10 ??m00 ??m11 ??m10
??m0 ??m2 ??m3
???(0, 2, 3).
成真赋值为 00, 10, 11.
(2)主析取范式为 0, 无成真赋值, 为矛盾式.
(3)m0?m1?m2?m3?m4?m5?m6?m7, 为重言式.
2.6. 求下列公式的主合取范式, 并求成假赋值:
(1) ??(q??p) ??p
(2)(p?q) ??(?p?r)
(3)(p??(p?q)) ?r
(1)??(q??p) ???p
???(?q??p) ???p
??q?p ???p
??q?0
??0
??m0?m1?m2?m3
这是矛盾式. 成假赋值为 00, 01, 10, 11.
(2)m4, 成假赋值为 100.
(3)主合取范式为 1, 为重言式.
离散数学答案屈婉玲版第二版高等教育出版社课后答案
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数1 q: 3是无理数0 r: 2是无理数 1 s: 6能被2整除1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式
（5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ?(?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q)
(完整版)离散数学试卷及答案
离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：
((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
离散数学第1章习题答案
#include
N=N/2; } while(!Empty(S)) { Pop(S,&e); printf("%d ",e); } } void main() { int n; printf("请输入待转换的值n：\n"); scanf ("%d",&n); conversion(n); }习题 1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？ (1)离散数学是计算机专业的一门必修课。 (2)李梅能歌善舞。 (3)这朵花真美丽！ (4)３＋２＞６。 (5)只要我有时间，我就来看你。 (6)x＝５。 (7)尽管他有病，但他仍坚持工作。 (8)太阳系外有宇宙人。 (9)小王和小张是同桌。 (10)不存在最大的素数。 解在上述10个句子中，(3)是感叹句，因此它不是命题。(6)虽然是陈述句，但它没有确定的值，因此它也不是命题。其余语句都是可判断真假的陈述句，所以都是命题。其中：(1)、(4) 、(8) 、(9) 、是简单命题，、(2) 、(5) 、(7)、(10) 是复合命题。 2.判断下列各式是否是命题公式，为什么？ (1)(P→(P∨Q))。 (2)(?P→Q)→(Q→P)))。 (3)((?P→Q)→(Q→P))。 (4)(Q→R∧S)。 (5)(P∨QR)→S。 (6)((R→(Q→R)→(P→Q))。 解 (1)是命题公式。 (2)不是命题公式，因为括号不配对。 (3)是命题公式。 (4)是命题公式。
屈婉玲版离散数学课后习题答案【2】
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). G(x): x+5=9. (1)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快
命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误！未找到引用源。=0. (c) 特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y D ∈错误！未找到引用源。. (d) 特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x 试卷二试题与参考答案 一、填空 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、设代数系统 二、选择 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、下面偏序集( )能构成格。 第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p?q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p?q真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q 真值:1 (13) 4是偶数且是奇数. 是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 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. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p?q,真值为1. (6)p?┐q,真值为0. (7)┐p?q,真值为0. (8)┐p?┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 p:今天是1号。 q:明天是2号。 符号化为：p→q 真值为：1 （2）如果今天是1号，则明天是3号。 p:今天是1号。 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)0∨(0∧1) 0 （2）（p?r）∧(﹁q∨s) （0?1）∧(1∨1) 0∧10. （3）（p∧q∧r）?(p∧q∧﹁r) （1∧1∧1）? (0∧0∧0)0 (4)（r∧s）→(p∧q) （0∧1）→(1∧0) 0→0 1 17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则也是无理数。另外6能被2整除，6才能被4整除。” 答：p: 是无理数 1 q: 3是无理数0 r: 是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 19．用真值表判断下列公式的类型： （4）(p→q) →(q→p) （5）(p∧r) (p∧q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q q p q→p (p→q)→(q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) (p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1 所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)(p→(q∧r)) (4)(p∧q)∨(p∧q)(p∨q) ∧(p∧q) 证明（2）(p→q)∧(p→r) (p∨q)∧(p∨r) p∨(q∧r)) p→(q∧r) （4）(p∧q)∨(p∧q)(p∨(p∧q)) ∧(q∨(p∧q) (p∨p)∧(p∨q)∧(q∨p) ∧(q∨q) 1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(p→q)→(q∨p) (2)(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (p→q)→(q p) (p q)(q p) (p q)(q p) (p q)(q p)(q p)(p q)(p q) (p q)(p q)(p q) ∑(0,2,3) 主合取范式： (p→q)→(q p) (p q)(q p) 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ P10 1对下面每个集合，判断2和{2}是否它的一个元素。 (1){x∈R | x是大于1的整数} (2){x∈R | x是某些整数的平方} (3){2, {2}} (4){{2},{{2}}} (5){{2}, {2,{2}}} (6){{{2}}} 解： {2}是(3)，(4)，(5)的元素。2是(1)，(3)的元素。 3 下列哪些命题成立？哪些不成立？为什么？ （1）φ∈{φ,{φ}} （2）φ?{φ,{φ}} （3）{φ}?{φ,{φ}} （4）{{φ}}?{φ,{φ}} 解： （1）成立 （2）成立 （3）成立 （4）成立 5 设A集合={a,b,{a,b},φ}。下列集合由哪些元素组成？ (1)A-{a,b}; (2){{a.b}}-A; (3){a,b}-A; (4)A--φ; (5)φ-A; (6)A-{φ}. 解： (1){{a,b},φ} (2)φ (3)φ (4) A (5)φ (6){a,b,{a,b}} 6 假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 解：A∩B 7 设A,B和C是任意集合，判断下列命题是否成立，并说明理由。 (1)若A?B,C?D，则A∪C?B∪D,A∩C?B∩D； (2)若ADB,CDD，则A∪CDB∪D,A∩CDB∩D； (3)若A∪B=A∪C，则B=C； (4)若A∩B=A∩C，则B=C； 解： (1)成立 (2)不一定成立 (3)不一定成立 (4)不一定成立 11（5）设A、B和C是集合，请给出(A-B)?(A-C)=φ成立的充要条件。解：错误！未找到引用源。A?B∪C 13试求： (1)P(φ); (2)P(P(φ)); (3)P({φ,a,{a}}) 解： (1){φ} (2){φ，{φ}} (3){φ，{φ}，{a}，{{a}}} 15 设A是集合，下列命题是否必定成立? （1）A∈P(A) （2）A?P(A) （3）{A}∈P(A) （4）{A}?P(A) 解： (1)成立 (2)不一定成立 (3)不一定成立 (4)成立 18设A＝{a,b}，B={b,c},下列集合由哪些元素组成？ (1)A×{a}×B; (2)P(A)×B; (3)(B×B) ×B; 解： (1){(a,a,b),(a,a,c),(b,a,b),(b,a,c)} (2){(φ,c),(φ,b),({a},c),({a},b),({b},c),({b},b),({a,b},c),({a,b},b)} (3){((b,b),c),((b,b),b),((b,c),c),((b,c),b),((c,b),c),((c,b),b),((c,c),c),((c,c),b)} 19 设A是任意集合，A3=(A×A)×A=A×(A×A)是否成立？为什么？ 解：不成立。 填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论 C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、 x(P(x) Q(x)) xP(x) xQ(x)； B 、 x(P(x) Q(x)) xP(x) xQ(x)； C 、 x(P(x) Q) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x) 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝_____{3}______________; ρ(A) - ρ(B)＝ ____{{3}，{1，3}，{2,3},{1,2,3}}__________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = ___2^(n^2)________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是____A1 = {(a,1), (b,1)}, A2 = {(a,2), (b,2)}, A3 = {(a,1), (b,2)}, A4 = {(a,2), (b,1)},_________ _____________, 其中双射的是______A3, A4__________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取式是____P∧?Q∧R (m5)____. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为___12______，分枝点数为_______3_________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝______{4}______; A?B＝____{1,2,3,4}_________;A－B＝______{1,2}_______ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______自反性____________, _________对称性_________, _________传递性_____________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有_____（1,0,0）__________， ______(1,0,1)________, ________(1,1,0)________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则R1?R2= ___{(1,3),(2,2),(3,1)}____,R2?R1 =_____{(2,4), (3,3), (4,2)}_____, R12=_______{(2,2), (3,3)}_________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = ______2^(m*n)___________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = _____{x | -1 ≤x < 0, x ∈R}_______ , B-A = ______{x | 1 < x < 2, x ∈R}_____ , A∩B = ______{x | 0 ≤x ≤1, x ∈R}__________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ ________{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}_________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束式是_____?y?x(P(y)→Q(x))________ _____. 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： 一、 填空 1. 任何(n,m) 图G = (V,E) , 边数与顶点度数的关系是 。 2. 当n 为 时,非平凡无向完全图K n 是欧拉图。 3. 已知一棵无向树T 有三个3顶点,一个2度顶点,其余的都是1度顶点, 则T 中有 个1度顶点。 4．设}3,34,2,2,1{, } 4,3,2,1{><><><==，R X ，则 r (R) = ； s (R) = ； t (R) = 。 5．设R 为集合A 上的等价关系，对A a ∈?，集合R a ][= ，称为元素a 形成的R 等价类，Φ≠R a ][，因为 。 6．任意两个不同小项的合取为 ，全体小项的析取式为 。 7．设为偶数 x x Q :)(，为素数 x x P :)(，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化： （1） ； （2） 。 8．含5个结点，4条边的无向连通图（不同构）有 个， 它们是 。 9. 设T 为根树，若 ，则称T 为m 元树； 若 则称T 为完全m 叉树。 二、 选择 1、下面四组数能构成无向图的度数列的有( )。 A 、 2,3,4,5,6,7； B 、 1,2,2,3,4； C 、 2,1,1,1,2； D 、 3,3,5,6,0。 2、图 的邻接矩阵为( )。 A 、??? ???? ??00 1 101110100001 ；B 、??? ???? ??111111111111 1111；C 、??? ???? ??00 1 10111100 0010 ；D 、??????? ??00 1 10111010 0010 。 3、下列几个图是简单图的有( )。 A. G 1=(V 1,E 1), 其中 V 1={a,b,c,d,e},E 1={ab,be,eb,ae,de}； B. G 2=(V 2,E 2)其中V 2=V 1,E 2={ 离散数学 10.设有JR 集 |A| =m, |B| = n, Ml|| |p(AxB)| = J 2A m*n 带伞”可符号化为( ) 2 ?下列命题公式为永真蕴含式的是( ) (A ) Q —( P A Q ) ( B ) P -( P A Q ) (C ) (P A Q )-P ( D ) (P V Q )- Q 3、 命题“存在一些人是大学生”的否定是(A),而命题“所有的人都是要死 的”的否定是( )。 (A) 所有人都不是大学生，有些人不会死 (B) 所有人不都是大学生，所有人都不会死 (C) 存在一些人不是大学生，有些人不会死 (D) 所有人都不是大学生，所有人都不会死 4、 永真式的否定是()。 (A )永真式 (B )永假式 (C )可满足式 (D )以上均有可能 5、以下选项中正确的是()。 (A ) 0= ? (B ) 0 ? (C 0€ ? (D ) 0?? 6、以下哪个不是集合A 上的等价关系的性质？( ) (A )自反性 (B )有限性 (C )对称性 (D ) 传递性 7、集合 A={1,2；?；10}上的关系 R={vx,y>|x+y=10,x,y€ A}，贝U R 的性质为()。 (A )自反的 (B )对称的 (C )传递的，对称的 (D )传递的 8 .设 D=离散数学试题与答案
离散数学(屈婉玲版)第一章部分习题分解
离散数学期末试题及答案完整版
离散数学第一章部分课后习题参考答案
离散数学期末试卷及答案
华东师范大学离散数学章炯民课后习题第1章答案
离散数学试卷及答案
离散数学试卷及答案(1)
离散数学试题及答案
离散数学课后习题答案(左孝凌版)
离散数学试卷六试题与答案
(完整word版)离散数学试题及解答
- 离散数学(胡海涛)第1章答案
- 离散数学自考第一章(课后习题和答案)
- 离散数学课后习题答案第一章
- 离散数学(屈婉玲版)第一章部分习题分解
- 离散数学 第1章 习题解答
- 离散数学(屈婉玲)答案-1-5章
- 离散数学(屈婉玲)答案_1-5章
- 离散数学课后习题答案
- 离散数学课后习题答案(第一章)
- (完整版)离散数学答案(尹宝林版)第一章习题解答
- 离散数学第1章答案
- 离散数学课后习题答案
- 离散数学第1章习题答案
- 离散数学第1章答案
- 离散数学答案第一章习题解答
- 离散数学第1章习题答案
- 最新离散数学第1章习题答案
- 华东师范大学离散数学章炯民课后习题第1章答案
- 《离散数学》全程练习册(2011)答案(讲解用)
- 离散数学(屈婉玲)答案_1-5章