离散数学习题解答
习题五（第五章 格与布尔代数）
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 中任两个元素都有上、下确界。
b) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。
例如：8 12=LUB{8，12}不存在。
6
3
1
6
3 1
12
c) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。
倒例如：4⊕6=LUB{4，6}不存在。
2．设A ，B 是两个集合，f 是从A 到B 的映射。证明：〈S ，?〉是〈2B ，?〉的子
格。其中
S={y|y=f (x)，x ∈2A }
[证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈B ∧(?x)(x ∈
A 1∧f (x)=y)}?
B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空；
对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而
L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2)
=f (A 1∪A 2) （习题三的8的1））
由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。
对于任何B 1，B 2∈S ，定义A 1=f –1(B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1(B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是
GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2)
?f (A 1∩A 2) （习题三的8的2））
又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(?x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f (x)=y ∈B 2。故此x ∈A 2=f -1(B 2)={x|x ∈A ∧f(x)∈B 2}，因此x ∈A 1∩A 2，从而y=f (x)∈f (A 1∩A 2)，所以
7
1
GLB{B1，B2}=B1∩B2=f (A1)∩f (A2)?f (A1∩A2)
这说明G L B{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)
根据对偶原理，就还有
a⊕ (b*c)=(a⊕b) * (a⊕c)
因此〈I，min，max〉是分配格。
7．设〈A，*，⊕，max〉是分配格，a，b∈A且a?b。证明：
f (x)=(x⊕a) *b
是从A到B的同态函数。其它
B={x|x∈A且a?x?b}
[证] 由于a?x⊕a，及已知a?b，所以a?(x⊕a)*b；其次(x⊕a)*b?b，所以a?f (x)?b，因而f (x)是从A到B的函数。
对于任何x，y∈A，
f(x⊕y)=((x⊕y)⊕a)*b
=((x⊕a) ⊕ (y⊕a)) *b（幂等律，交换律，结合律）
=((x⊕*a)b)((y⊕a) *b)（分配律）
=f (x) ⊕f (y)
f (x*y) =((x*y) ⊕a) *b
=((x⊕a) * (ya⊕))*b （分配律）
=((x⊕a) *b)((y⊕a) *b) （幂等律，交换律，结合律）
=f (x) *f (y)
所以，f满足同态公式，因而f 是从A到B的同态函数。
8．证明：一个格是分配格的充分必要条件是?a，b，c∈L，有(a*b) ⊕ (b*c) ⊕ (c*a)=(a⊕b) * (b⊕c) * (c⊕a)
[证] 必要性。对于任何a，b，c∈L，
(a*b) ⊕ (b*c) ⊕ (c*a)
=(b* (a⊕c)) ⊕ (c*a) （交换律，分配律）
=(b⊕ (c*a)) * ((a⊕c) ⊕ (c*a)) （分配律）
=(b⊕c) * (b⊕a) * (a⊕c) （分配律，吸收律）
=(a⊕b) * (b⊕c) * (c⊕a) （交换律）
充分性，f满足同态公式，因而f是从A到B的同态函数。
8．证明：一个格是分配格的充分必要条件是?a，b，c∈L，有
(a*b) ⊕ (b*c) ⊕ (c*a)=(a⊕b) * (b⊕c) * (c⊕a)
[证] 必要性。对于任何a，b，c∈L，
(a*b) ⊕ (b*c) ⊕ (c*a)
=(b* (a⊕c)) ⊕ (c*a) （交换，分配律）
=(b⊕ (c*a))(( a⊕ c) ⊕ (c*a)) （分配律）
=(b⊕c) * (b⊕a) * (a⊕c) （分配律，吸收律）
=(a⊕b) * (b⊕c) * (c⊕a) （交换律）
充分性，对于任何a，b，c∈L
a⊕ (b*c)
=(a⊕ (a*c)) ⊕ (b*c) （吸收律）
=((a⊕ (a*b)) ⊕ (a*c)) ⊕ (b*c) （吸收律）
=(a*b) ⊕ (b*c) ⊕ (c*a) ⊕ a （交换律，结合律）
=((a⊕b) * (b⊕c) * (c⊕a)) ⊕a （已知条件）
=((a⊕b) * (a⊕c) * (b⊕c)) ⊕ ((b⊕c) *a) ⊕a （交换律，吸收律）
=((a⊕b) * (a⊕c) * (b⊕c)) ⊕ ((b⊕c) *a) ⊕ (a* (a⊕ b) * (a⊕ c)) （吸收律）
=(((a⊕b) * (a⊕c))⊕ (b⊕c)) * ((b⊕c) ⊕a) * (a⊕ ((a⊕ b)) * (a⊕c)))
（已知条件）=(((a⊕b)*(a⊕c))⊕(b⊕c)) * (a⊕b⊕c)*((a⊕b)*(a⊕c))（因为a⊕((a⊕b)* (a⊕c))= (a⊕b) * (a⊕c)
=(((a⊕b) * (a⊕c)) ⊕(b⊕c)) * (((a⊕b)⊕c) *(a⊕ b)* (a⊕c) （结合律）
=(((a⊕b) * (a⊕c)) ⊕(b⊕c)) *((a⊕ b)* (a⊕c)) （吸收律，结合律）
=(a⊕ b)* (a⊕c) （吸收律）
根据对偶原理还有a* (b⊕c)= (a⊕b) * (a⊕c)
所以格L是分配格。
9．设〈L，?〉是格。其Hasse图如右
a) 找出格中每个元素的补元；
b) 此格是有补格吗？
c) 此格是分配格吗？
[解] a)最小元0=i；最大元1=a；
故此格为有界格。
a b
d
f
i
a 和i 互为补元；f 和C 互为补元；其余
b ，d ，e ，g ，h 等都没有补元。
b) 根据a) 可知，此格不是有补格。
c) 此格不是分配格，因为f ⊕ (g * h)=f ⊕ i=f
(f ⊕g) * (f ⊕h)=b * d=d
因为去掉g 结点后所形成的子格与分配格〈S 24，I ，GCD ，LCM ，1，24〉同构，因此若此格不是分配格，则必有子格
h * (f ⊕g)=h *b=h
(h *f) ⊕ (h *g)=i ⊕i=I
〈S 24，I ，GCD ，LCM ，1，24〉 两个不是分配格的特殊格
与两个不是分配格的特殊格同构，并且此子格必含有g 点。而特殊不分配格之图或是含有五个结点的圈，或是有六个结点：gebdfi ；gebdhi ；gehdfi ；或是有八个结：gecabdfi ；gecabdhi ；或是只有一个四结点的圈：gehi 。因此此格绝不会有含g 点的子格与两个不是分配格的特殊格同构。
10．设〈L ，?，*，⊕〉是有界格。x ，y ∈L ，证明：
a) 若x ⊕y=0，则x=0且y=0。
b) 若x *y=1，则x=1且y=1。
[证] a) 对任何x ，y ∈L ，若x ⊕y=0，则
x=x * (x ⊕y) （吸收律）
=x *0 （x ⊕y=0）
=0 （0—1律）
y=y * (y ⊕x) （吸收律）
=y * (x ⊕y) （交换律）
=y *0 （x ⊕y=0）
8 4 2 1 3 6 12
a
1
a 2 a 4 a 5
b 5
=0 （0—1律）
b) 对任何x，y∈L，若x*y=1，则
x=x⊕ (x*y) （吸收律）
=x⊕1 （x*y=1）
=1 （0—1律）
y=y⊕ (y*x) （吸收律）
=y⊕ (x*y) （交换律）
=y⊕1 （x*y=1）
=1 （0—1律）
11．在有界格中，0是1的唯一补元，1是0的唯一补元。
[证] 由于1⊕0=1，1*0=0，所以0与1互为补元。
下面我们先来证0是1的唯一补元：
对于任何元素a属于有界格，若a是1的补元，则必有1⊕a=1，及1*a=0，于是必有
a=a* (a⊕1) （吸收律）
=a* (1⊕a) （交换律）
=a*1 （由1⊕a=1）
=1*a （交换律）
=0 （由1*a=0）
从而0是1的唯一补元。
次证1是0的唯一补元。
对于任何元素a属于有界格，若a是0的补元，则必有0⊕a=1，0*a=0。于是必有
a=a(a*0) （吸收律）
=a(0⊕a) （交换律）
=a⊕0 （由0*a=0）
=0⊕a （交换律）
=1 （由0⊕a=1）
12．设〈L，?〉是格，|L|≥2。证明：L中不存在以自己为补元的元素。
[证] 用反证法，假设L中存在着以自己为补元的元素，不妨是b∈L，那么b⊕b=1，b*b=0，于是由幂等律，可得
b=b*b=0，b⊕b=1，
从而有0=b=1，即0=1
因此，对于任何元素a?L，都有a=0=1（因为0?a?1），从而|L|=1，这与已知|L，|≥2矛盾。
13．设〈L，?〉是全序集，|L|≥3。证明：〈L，?〉是格，但不是有补格。
[证] 由于〈L，?〉是全序集，那么L中任意两个元素都可比较，于是L中任意两个元素都有上确界和下确界，因此〈L，?〉是格。
下面我们来证〈L，?〉不是有补格，用反证法：
否则〈L，?〉是有补格，则对任何a∈L，都存在着一个元素b∈L，使a⊕b=1及a*b=0。由于〈L，?〉是全序集，所以任二元素可比较，从而
①若a?b，则a=a*b=0
②若b?a，则a=a⊕b=1
因此|L|=2，与已知|L|≥3矛盾。
14．在有界的分配格中，证明：具有补元的那些元素组成一个子格。
[证] 设〈L，*，⊕，0，1〉是有界分配格，令
L′={x|x∈L∧(?y∈L)(x*y=0∧x⊕y=1)}
我们来证〈L′，*，⊕，0，1〉是〈L，*，⊕，0，1〉的子格：
显然L′?L；其次易证0，1∈L′，故此L′非空；对于任何a1，a2∈L′，我们来证a1*a2，a1⊕a2∈L′
为证a1*a2∈L′，只需找出a1*a2的补元即可。由于a1，a2∈L′，故此存在着b1，b2∈L，使a1*b1=0，a1⊕b1=1以及a2*b2=0，a2⊕b2=1，于是构造出a1*a2补元为b1b2∈L。这是因为
(a1*a2) * (b1⊕b2)=((a1*a2) * b1) ⊕((a1*a2) * b2) （分配律）
=((a1*b1) *a2) ⊕(a1*(a2 * b2) （交换律）
=(0*a2) ⊕(a1*0)（由a1*b1=0，a2b2=0）
=0⊕0 （由0—1律）
=0
(a1*a2) ⊕ (b1⊕b2)=(a1⊕ (b1⊕ b2)) * (a2⊕ (b1⊕ b2))（分配律）
=((a1⊕b2) ⊕b2) * ((a2⊕b2) ⊕b1)（交换律，结合律）
=(1⊕b2)* (1⊕b1)（由a1⊕b1=1及a2⊕b2=1）
=1*1（由0—1律）
=1
为证a1⊕a2∈L′只需找出a1⊕a2的补元即可。由于a1，a2的补元是b1，b2，故构造出a1⊕a2的补元为b1*b2∈L。这是因为
(a1⊕a2) * (b1*b2)=(a1* (b1* b2))⊕(a2* (b1* b2))（分配律）
第七章 格与布尔代数 1. 说明什么叫格？ 2. 给定偏序集
a ∧ b 表示（ ）。 7. 说明什么叫子格？ 8. 给定偏序集
14. 请说出什么叫分配格？ 15. 指出判定一个格是分配格的充分且必要条件是在该格中没有任何子格与两个五元素非分配格之一同构。请画出这两个五元素非分配格。 16. 下面具有五个元素的格中，哪些是分配格？ 17.具有五个元素的格中，有几个不是分配格？请画出这些非分配格的图。 18. 验证下面格不是分配格。 19. 验证下面格不是分配格。 a b c d e
离散数学习题答案 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 解：公式的真值表如下：
由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理 15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论： p u → 证明：用附加前提证明法。 ① p 附加前提引入 ② p q ∨ ①附加 ③ ()()p q r s ∨→∧ 前提引入 ④ r s ∧ ②③假言推理 ⑤ s ④化简 ⑥ s t ∨ ⑤附加 ⑦ ()s t u ∨→ 前提引入 ⑧ u ⑥⑦假言推理 故推理正确。 16、在自然推理系统P 中用归谬法证明下面推理： （1）前提： p q →?，r q ?∨，r s ∧? 结论：p ?
第五章函数Function 函数在数学、应用数学等许多领域，尤其计算机科学领域有着极其重要的作用。函数的思想、概念和应用无处不在，无时不在。 它主要是研究变量之间的关系和规律。函数的划分有很多种。有线性与非线性之分、连续与离散之分。例
如， x12345… y357911… 5.1 函数 假定A，B是两个非空集合，f : A→B，称f为A到B上的函数，对每个a∈A, 有唯一的f(a)∈B, 记做b = f(a)。 函数也叫映射mappings或变换transformations（错误） a叫做函数f的自变量argument，b被称为因变量，b=f(a)叫做函数的值value，也叫a的像。 例1. A＝{1,2,3,4}, B={a,b,c,d}, ，
则f是一个函数。 也可以简单记为， f={(1,a), (2,a), (3,d), (4,c)} 另外, g={(1,a), (1,b), (2,a), (4,c)} 因为对于1来说，1∈A, 不是唯一的f(1)∈B与之相对应,f(1)=a,并且f(1)=b, 因此g就不是一个函数。 例2． f：Z→Z， f(a)= f是函数。 例3．恒等函数1A(a)=a是函数。 正如，我们在第四章里表述的，函数f : A→B，b=f(a), 是一个特殊的二元关系，我们知道，由函数f可以确定一个关系，简单地，可以表示为(a,b)∈，或 ab。关系的特征函数为 或者简记为 因此，这样一来，我们以前所讨论的有关集合或关系的运算和性质对于函数来说，就可以完全适用。 例如，f：A→B, g：A→B, 函数的复合 设f：A→B，g：B→C，是函数，则g?f：A→C，是函数。 g?f（a）＝g(f(a))
离散数学习题解答(第五章)格与布尔代数
仅供学习与交流，如有侵权请联系网站删除 谢谢2 离散数学习题解答 习题五（第五章 格与布尔代数） 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 中任两个元素都有上、下确界。 b) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 例如：8 12=LUB{8，12}不存在。 6 3 1 6 3 1 1
仅供学习与交流，如有侵权请联系网站删除 谢谢3 c) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 倒例如：4⊕6=LUB{4，6}不存在。 2．设A ，B 是两个集合，f 是从A 到B 的映射。证明：〈S ，?〉是 〈2B ，?〉的子格。其中 S={y|y=f (x)，x ∈2A } [证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈ B ∧(?x)(x ∈A 1∧f (x)=y)}?B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空； 对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2) =f (A 1∪A 2) （习题三的8的1）） 由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。 对于任何B 1，B 2∈S ，定义A 1=f –1(B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1 (B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) （习题三的8的2）） 又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(?x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f 7 1
《离散数学》考试题库及答案 一、 填空 10% （每小题 2分） 1、 若P ，Q 为二命题，Q P ?真值为1，当且仅当 。 2、 对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的 公 式 为 。 3、 )) (()(x xG x xF ??∧?的 前 束 范 式为 。 4、 设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的， 则 被称为全称量词消去规则，记为US 。 5、 与非门的逻辑网络为 。 二、 选择 30% （每小题 3分） 1、 下列各符号串，不是合式公式的有（ ）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、 下列语句是命题的有（ ）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、 下列公式是重言式的有（ ）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、 下列问题成立的有（ ）。 A 、 若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、 命题逻辑演绎的CP 规则为（ ）。 A 、 在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出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 中任两个元素都有上、下确界。 b) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 例如：8 12=LUB{8，12}不存在。 c) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 1 6 3 1 2 4 8 63 1 2 4 1 1
倒例如：46=LUB{4，6}不存在。 2．设A ，B 是两个集合，f 是从A 到B 的映射。证明：〈S ，?〉是〈2B ，?〉的子格。其中 S={y|y=f (x)，x ∈2A } [证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}?B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空； 对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2) =f (A 1∪A 2) （习题三的8的1）） 由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。 对于任何B 1，B 2∈S ，定义A 1=f –1 (B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1 (B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) （习题三的8的2）） 又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f (x)=y ∈B 2。故此x ∈A 2=f -1 (B 2)={x|x ∈A ∧f(x)∈B 2}，因此x ∈A 1∩A 2，从而y=f (x)∈f (A 1∩A 2)，所以 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) 9 7 31
第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。 （2）5能被2整除。 （3）现在开会吗？ （4）x+5>0 （5）这朵花真是好看！ （6）2是素数当且仅当三角形有三条边。 （7）雪是黑色的当且仅当太阳是从东方升起。 （8）2000年10月1日天气晴好。 （9）太阳系以外的星球上有生物。 （10）小李在宿舍里。 （11）全体起立。 （12）4是2的倍数或是3的倍数。 （13）4是偶数且是奇数。 （14）李明和王华是同学。 （15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 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； 1.4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号； （2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。 （1）2是偶数不是素数； （2）小王不但聪明而且用功； （3）虽然天气冷。老王还是来了； （4）他一边吃饭，一边看电视； （5）如果天下大雨，他就乘公交汽车来； （6）只有天下大雨，他才乘公交汽车来； （7）除非天下大雨，否则他不乘公交汽车来； （8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r);
一、格的引入 在上一章中讨论过偏序集与偏序关系时,已经把格定义为一种特殊的偏序集。下面, 先 回顾一下几个有关概念。 设
第5章作业答案 1. 用枚举法给出下列集合 解(2) {-3，2} (4) {5，6，7，8，9，10，11，12，13，14，15} 2. 用抽象法说明下列集合 解(6) {x|?k (k∈I∧x = 2k + 1)} 6．写出下列集合的幂集 解(2) ρ({1, ?}) = {?, {1}, {?}, {1, ?}} (4) ρ({?, {a}, {?}}) = {?, {?}, {{a}}, {{?}}, {?, {a}}, {?, {?}}, {{a}, {?}}, {?, {a}, {?}}} 9. 证明：如果B?C，则ρ(B) ?ρ(C)。 证明任取x∈ρ(B)，则x?B，又因为B?C，所以x?C，x∈ρ(C)。 10．设U = {1, 2, 3, 4, 5}，A = {1, 4}，B = {1, 2, 5}和C = {2, 4}，试写出下列集合。解(8) ρ(A) -ρ(C) = {?, {1}, {4}, {1, 4}} - {?, {2}, {4}, {2, 4}} = {{1}, {1, 4}} 11．证明下列恒等式 (7) (A-B) -C = (A-C) - (B-C) 证法1 对于任意x， x∈ (A-C) - (B-C) ?x∈A-C ∧x? B-C ?x∈A∧x?C ∧?(x∈ B∧x?C) ? x∈A∧x?C ∧ ( x?B ∨ x∈C) ?( x∈A∧x?C ∧ x?B)∨( x∈A∧x?C ∧ x∈C) ? x∈A∧x?C ∧ x?B ? x∈A∧ x?B∧x?C ? x∈A-B ∧ x?C ? x∈(A-B) -C 证法2 (A-C) - (B-C) = A?~C?~( B?~C) = A?~C? (~ B? C) = ( A?~C?~ B) ?( A?~C? C) =(A?~C?~ B) ?? = A?~B?~ C = (A-B) ?~ C = (A-B) -C 12．设A, B, C是集合，下列等式成立的条件是什么？ (3) (A-B ) ? (A-C) = ? 解因为(A- B) ?( A-C) = (A?~B) ? ( A?~C) = A? (~B?~C) = A?~(B ?C) = A- (B ?C) 所以(A-B)?(A-C) = ?iff A- (B?C) = ?iff A? (B?C)
、选择题(每小题2分，共30分) 1、N 是自然数集， 是小于等于关系, 则 N, 是(C )。 (A)有界格 (B) 有补格 (C)分配格 (D) 2、在有界格中，若只有一个元素有补元, 有补分配格 则补元( C ) (A)必唯 (B) 不唯 (C)不一定唯 (D) 可能唯 3、 F 面是一些偏序集的哈斯图，判断哪一个为格( C ) d c e e e c D A C B D ) (A)分配格 (B)有补格 (C)布尔格 (D) 有界格 6设L,是一条链，其中L -3，贝U L, ( C ) (A)不是格 (B) 是有补格 5、只含有有限个元素的格称为有限格, 有限格必是(
(C)是分配格 (D) 是布尔格 7、 设A 为一个集合， P(A), 为有补格，P(A)中每个元素的补元(A ) (A) 存在且唯一 (B) 不存在 (C)存在但不唯一 (D)可能存在 8、 设 代 是一个有界格，若它也是有补格，只要满足( B ) (A)每个元素都有一个补元 (B)每个元素都至少有一个补元 9、如下哈斯图(C )表示的关系构成有补格。 (C)每个元素都无补元 (D)每个元素都有多个补元 10、如图给出的哈斯图表示的格中( (A)a (C)e (D) f 11、设格 B, 2如图所示，它们的运算分别为 和，。令 f(a) X !, f(b) X 2, f (c) X 4, f (d) X 8，则 f ( B ) B )元素无补元。 d g c
(A)是格同态映射 (B)不是格同态映射 系。贝U 30的补元为 (B) 30 (D) 70 f (a) 2 f(b)是格同构的( (B)充分条件 ,其中定义为：对于n 1 , n 2 L, n 1 n 2 当且仅当n 1是n 2的因子。问其中哪几个偏序集是格(说明理由)。(共6 分) a)、L {1,2,3,4,6,12} b)、L {1,2,3,4,6,8,12,14} C)、L {1,2,3,4,5,6,7,8,9,10,11,12} 、图中为格L 所对应的哈斯图。(共10分) (C) 是格同构映射 (D) 是自同态映射 (A) 2n (B) (C) 2n (D) 4n 13、在布尔格 A, 中有3个原子a 1,a 2,a 3则6 ( B ) (A) a 2 a 3 (B) a 2 a 3 (C) a 2 a 3 (D) a 2 a 3 14、在布尔格 代 中, A {X | X 是5的整数倍且是210的正因子} , |为整除关 (A)15 (C)35 15、设A, 1和 B, 2 是两个格, f 是A 到B 的双射，则对任意的a,b A ，有 (A)必要条件 (C)充要条件 (D)既不充分也不必要 、由下列集合L 构成的偏序集 L,
第一章 定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律） 证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)
第5章 习题解答 5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨ 分析 S 为n 元集,那么有个元素.S 上的一个二元运算就是函数 S S ?2n .这样的函数有个.因此上的二元运算有个. S S S f →?:2n n },{b a 162 =n n 下面说明通过运算表判别二元运算性质及求特导元素的方法. 1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换律. 2 °幂等律 设运算表表头元素的排列顺序为如果主对角线元,,,21n x x x 素的排列也为 则该运算满足幂等律. ,,,21n x x x 其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特征,只能针对所有可能的元素等来验证相关的算律是否成立. z y x ,,3 ° 幺元设运算表表头元素的排列顺序为如果元素所在的.e ,,,21n x x x i x 行和列的元素排列顺序也是则为幺元. ,,,21n x x x i x 4 ° 零元如果元素所在的行和列的元素都是,则是零元. .θi x i x i x 5 ° 幂等元.设运算表表头元素的排列顺序为如果主对角线上,,,21n x x x 第个元素恰 为那么是幂等元.易见幺元和零元都是幂等元. i },,2,1{n i x i ∈i x 6 ° 可逆元素及其逆元.设为任意元素,如果所在的行和列都有幺元,并i x i x 且这两个幺元关于主对角线成对称分布,比如说第行第列和第行第列的两i j j i 个位置,那么与互为逆元.如果所在的行和列具有共同的幺元,则幺元一j x i x i x 定在主对角线上,那么的逆元就是自己.如果所在的和地或者所在的列没i x i x i x 有幺元,那么不是可逆元素.不难看出幺元一定是可逆元素,且;而零i x e e e =-1元不是可逆元素. θ以本题为例,的运算表是对称分布的,因此,这三个运算是可交换的, 321,,f f f
离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若
第一章部分课后习题参考答案 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)
第十二章 格和布尔代数 12.1 设c b a ,,是格),( A 中的元素，求证：如果b a ，则)()(c a b c b a ∨∧∧∨ 证明 因为b a ，且)(c a a ∨ ，所以)(c a b a ∨∧ 。 又因为b c b ∧，且c a c c b ∨∧ ，所以)(c a b c b ∨∧∧ 。 即)(c a b ∨∧是a 和c b ∧的上界，从而有： )()(c a b c b a ∨∧∧∨ 。 12.2 设c b a ,,是格),( A 中的元素，求证： （1）)()()(c a b a c b a ∨∧∨∧∨ （2）)( )()(c b a c a b a ∨∧∧∨∧ (1)证明 因为c a a b a a ∨∨ ,，所以)()(c a b a a ∨∧∨ 。 又因为b a b c b ∨∧ ，且c a c c b ∨∧ ，所以)()(c a b a c b ∨∧∨∧ 。 即)()(c a b a ∨∧∨是a 和c b ∧的上界。 所以，)()()(c a b a c b a ∨∧∨∧∨ 。 （2）证明 因为a b a ∧，a c a ∧，则有a c a b a )()(∧∨∧。 又因为b b a ∧，有c b b b a ∨∧ ，同理c b c a ∨∧ 。从而有c b c a b a ∨∧∨∧ )()(。 即)()(c a b a ∧∨∧是a 和c b ∨的下界。 因此，)( )()(c b a c a b a ∨∧∧∨∧ 。 10.3 设),,(∧∨A 是一个代数系统，其中∨和∧是满足吸收律的二元运算，证明：∨和∧也满足等幂律。 证明
因为∨和∧是满足吸收律，所以a b a a =∨∧)(，a b a a =∧∨)(。于是有： )((b a a a a a ∧∨∧=∧ )(c a a ∨∧= （其中b a c ∧=） a = 同理可证，a a a =∨。 故∨和∧也满足等幂律。 10.4 证明：一个格是可分配的，当且仅当对于这个格中的任意元素a ，b 和c ，有 )()(c b a c b a ∧∨∧∨ 证明 （1）必要性 因为a c a ∧和c b c b ∧∧ ，所以)()()(c b a c b c a ∧∨∧∨∧ 。 又因为格为分配格，所以)()()(c b c a c b a ∧∨∧=∧∨。 因此，)()(c b a c b a ∧∨∧∨ 。 （2）充分性 因为对于c b a ,,?，有)()(c b a c b a ∧∨∧∨ ，则 )()()(c c b a c b a ∧∧∨=∧∨ （等幂律） c c b a ∧∧∨=))(( （结合律） c c b a ∧∧∨))(( （假设） c a c b ∧∨∧=))(( （交换律） )()(c a c b ∧∨∧ （假设） 又因为b a a ∨ ，c c ，所以c b a c a ∧∨∧)( ；同理，c b a c b ∧∨∧)( 因此，c b a c b c a ∧∨∧∨∧)()()( 综上所述，)()()(c b c a c b a ∧∨∧=∧∨ 故该格是可分配的。 10.5 证明一个格),( A 是分配的，当且仅当对A 中的任意元素a ，b 和c ，有 )()()()()()(a c c b b a a c c b b a ∨∧∨∧∨=∧∨∧∨∧
试卷二试题与参考答案 一、填空 1、 P ：你努力，Q ：你失败。 2、 “除非你努力，否则你将失败”符号化为 ； “虽然你努力了，但还是失败了”符号化为 。 2、论域D={1，2}，指定谓词P 则公式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、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 6、4阶群必是 群或 群。 7、下面偏序格是分配格的是 。
8、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 二、选择 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 ．自反性 。
第五章习题 7年昆明理工 1、在自然数集合 N上，下列哪种运算是可结合的。（） A. a*b=a-b B.a*b=max(a,b) C. a*b=a+2b D.a*b=|a-b| 2、设 Z 为整数集合， +为普通加法，则代数系统
其他习题 1、已知集合 A={1 ，2，?,10}, 下面定的哪些运算关于集合 A 是不封的 .() A. x*y=max(x,y) B.x*y=min(x,y) C.x*y=GCD(x,y) , 即 x,y 的最大公数 D.x*y=LCM(x,y), 即 x,y 的最小公倍数 2、 Z* 是正整数集合， +，—， * ，△分是数的普通加法、减法， 乘法和平方运算，下列（）不能构成代数系。 A.
数理逻辑部分 选择、填空及判断 ?下列语句不是命题的（ A ）。 (A) 你打算考硕士研究生吗？(B) 太阳系以外的星球上有生物。 (C) 离散数学是计算机系的一门必修课。(D) 雪是黑色的。 ?命题公式P(P P)的类型是（ A ） (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A是重言式，那么A的否定式是( A ) A. 矛盾式 B. 重言式 C. 可满足式 D.不能确定 ?以下命题公式中，为永假式的是( C ) A. p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值是( D ) A. 00,11 B. 00,01,11 C.10,11 D. 10 ?谓词公式) x R xP∧ ?中，变元x是( B ) ) x ( , (y A. 自由变元 B. 既是自由变元也是约束变元 C. 约束变元 D. 既不是自由变元也不是约束变元 ?命题公式P(Q Q)的类型是( A )。 (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?设B不含变元x，) x→ ?等值于( A ) A (B ) ( x
A. B x xA →?)( B. ))((B x A x ∨? C. B x xA →?)( D. B x A x ∧?)(( ? 下列语句中是真命题的是( D )。 A ．你是杰克吗？ B ．凡石头都可练成金。 C ．如果2+2=4，那么雪是黑的。 D ．如果1+2=4，那么雪是黑的。 ? 从集合分类的角度看，命题公式可分为( B ) A. 永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 ? 命题公式﹁p ∨﹁q 等价于( D )。 A. ﹁p ∨q B. ﹁(p ∨q) C. ﹁p ∧q D. p →﹁q ? 一个公式在等价意义下，下面写法唯一的是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ? 下列含有命题p ，q ，r 的公式中，是主析取范式的是 ( D )。 (A) (p q r) (p q) (B) (p q r) (p q) (C) (p q r) (p q r) (D) (p q r) (p q r) ? 设个体域是整数集合，P 代表x y ((x y )(x y x ))，下面描述正确的是 （ C ）。 (A) P 是真命题 (B) P 是假命题 (C) P 是一阶逻辑公式，但不是命题 (D) P 不是一阶逻辑公式 ? 对一阶逻辑公式((,)(,))(,)x y P x y Q y z xP x y ??∧∧?的说法正确的是( B ). (A) x 是约束的，y 是约束的，z 是自由的； (B) x 是约束的，y 既是约束的又是自由的，z 是自由的； (C) x 是约束的，y 既是约束的又是自由的，z 是约束的；
离散数学课后习题答案(左孝凌版) 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）解：