离散数学第五章答案.docx
《离散数学第五章答案.docx》由会员分享，可在线阅读，更多相关《离散数学第五章答案.docx（18页珍藏版）》请在冰点文库上搜索。
离散数学第五章答案
离散数学第五章答案
【篇一：
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}不存在。
126
31
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}不存在。
126
31
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
升级会员 