离散数学答案屈婉玲版第二版高等教育出版社课后答案Word文件下载.docx
《离散数学答案屈婉玲版第二版高等教育出版社课后答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《离散数学答案屈婉玲版第二版高等教育出版社课后答案Word文件下载.docx（48页珍藏版）》请在冰点文库上搜索。
q
pq→p（p→q）→（q→p）
所以公式类型为永真式
（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
r
p
∨q
∧r
（p∨q）→（p∧r）
所以公式类型为可满足式
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）→（qp）
（pq）（qp）
（pq）（qp）
（pq）（qp）（qp）（pq）（pq）
（pq）（pq）（pq）
m0m2m3
∑（0,2,3）
主合取范式：
（p→q）→（qp）
（p（qp））（q（qp））
1（pq）
（pq）M1
∏
（1）
（1）主合取范式为：
（p→q）qr（pq）qr
（pq）qr0
所以该式为矛盾式.
主合取范式为∏（0,1,2,3,4,5,6,7）
矛盾式的主析取范式为0
（3）主合取范式为：
（p（qr））→（pqr）
（p（qr））→（pqr）
（p（qr））（pqr）
（p（pqr））（（qr））（pqr））
11
1
所以该式为永真式.
永真式的主合取范式为1
主析取范式为∑（0,1,2,3,4,5,6,7）
第三章部分课后习题参考答案
14.在自然推理系统P中构造下面推理的证明：
（2）前提：
pq,（qr）,r
结论：
p
（4）前提：
qp,qs,st,tr
pq
证明：
（2）
①
（q
r）
前提引入
②
①置换
③q
②蕴含等值式
④r
⑤
③④拒取式
⑥p
⑦￢p（3）
⑤⑥拒取式
证明（4）：
①tr
②t
①化简律
③q
s
④s
t
⑤q
③④等价三段论
⑥（q
t）（t
q）⑤置换
⑦（q
t）
⑥化简
⑧q
②⑥假言推理
⑨q
⑩p⑧⑨假言推理
（11）pq⑧⑩合取
15在自然推理系统P中用附加前提法证明下面各推理：
（1）前提：
p（qr）,sp,q
sr
证明
①s
附加前提引入
②s
③p
①②假言推理
④p
r）前提引入
③④假言推理
⑥q
⑦r
⑤⑥假言推理
16在自然推理系统P中用归谬法证明下面各推理：
pq,rq,rs
①p
结论的否定引入
②p
﹁q
③﹁q
④￢r
⑤￢r
④化简律
⑥r
￢s
⑥化简律
⑧r
﹁r
⑤⑦合取
由于最后一步r
﹁r是矛盾式,所以推理正确.
第四章部分课后习题参考答案
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）在两个个体域中都解释为xF（x），在（a）中为假命题，在（b）中为真命题。
（2）在两个个体域中都解释为xG（x），在（a）（b）中均为真命题。
4.在一阶逻辑中将下列命题符号化:
（1）没有不能表示成分数的有理数.
（2）在北京卖菜的人不全是外地人.
解:
（1）F（x）:
x能表示成分数
H（x）:
x是有理数
命题符号化为:
x（F（x）H（x））
（2）F（x）:
x是北京卖菜的人
x是外地人
x（F（x）H（x））
5.在一阶逻辑将下列命题符号化:
（1）火车都比轮船快.
（3）不存在比所有火车都快的汽车.
x是火车;
G（x）:
x是轮船;
H（x,y）:
x比y快
xy（（F（x）G（y））H（x,y））
（2）
（1）F（x）:
x是汽车;
y（G（y）x（F（x）H（x,y）））
9.给定解释I如下:
（a）个体域D为实数集合R.
（b）D中特定元素=0.
（c）特定函数（x,y）=xy,x,yD.
（d）特定谓词（x,y）:
x=y,（x,y）:
x<
y,x,yD.
说明下列公式在I下的含义,并指出各公式的真值:
（1）
x
y（G（x,y）
F（x,y））
（2）
y（F（f（x,y）,a）G（x,y））
答:
（1）对于任意两个实数x,y,如果x<
y,那么xy.真值1.
（2）对于任意两个实数x,y,如果x-y=0,那么x<
y.真值0.
10.给定解释I如下：
（a）个体域D=N（N为自然数集合）.
（b）D中特定元素=2.
（c）D上函数=x+y,（x,y）=xy.
（d）D上谓词（x,y）:
x=y.
说明下列各式在I下的含义，并讨论其真值.
（1）xF（g（x,a）,x）
（2）xy（F（f（x,a）,y）→F（f（y,a）,x）
（1）对于任意自然数x,都有2x=x,真值0.
（2）对于任意两个自然数x,y,使得如果x+2=y,那么y+2=x.真值0.
11.判断下列各式的类型:
（3）yF（x,y）.
解:
（1）因为p（qp）p（qp）1为永真式；
所以为永真式；
（3）取解释I个体域为全体实数
F（x,y）：
x+y=5
所以,前件为任意实数x存在实数y使x+y=5，前件真；
后件为存在实数x对任意实数y都有x+y=5，后件假，]
此时为假命题
再取解释I个体域为自然数N，
:
所以,前件为任意自然数x存在自然数y使x+y=5，前件假。
此时为假命题。
此公式为非永真式的可满足式。
13.给定下列各公式一个成真的解释，一个成假的解释。
（1）（F（x）
（2）x（F（x）G（x）H（x））
（1）个体域:
本班同学
F（x）：
x会吃饭,G（x）：
x会睡觉.成真解释
x是泰安人,G（x）：
x是济南人.
（2）成假解释
（2）个体域:
泰山学院的学生
x出生在山东,G（x）:
x出生在北京,H（x）:
x出生在江苏,成假解释.
x会吃饭,G（x）：
x会睡觉,H（x）：
x会呼吸.成真解释.
第五章部分课后习题参考答案
5.给定解释Ｉ如下:
（a）个体域D={3,4};
（b）
f（x）为f（3）
4,f（4）
3
（c）
F（x,y）为F（3,3）
F（4,4）
0,F（3,4）F（4,3）1.
试求下列公式在Ｉ下的真值.
（1）xyF（x,y）
（3）
xy（F（x,y）
F（f（x）,
f（y）））
yF（x,y）
x（F（x,3）
F（x,4））
（F（3,3）
F（3,4））
（F（4,3）
F（4,4））
（0
1）
（1
0）
y（F（x,y）
F（f（x）,f（y）））
x（（F（x,3）
f（3）））
（F（x,4）
F（f（x）,f（4））））
x（（F（x,3）
F（f（x）,4））（F（x,4）
F（f（x）,3）））
（（F（3,3）
F（f（3）,4））
（F（3,4）
F（f（3）,3）））
（（F（4,3）
F（f（4）,4））
（F（4,4）
F（f（4）,3）））
（（0
F（4,4））
（F（3,4）
F（4,3）））
（（1F（3,4））（0F（3,3）））
12.求下列各式的前束范式。
xF（x）
yG（x,y）
（5）
x1F（x1,x2）
（H（x1）
x2G（x1,x2））（本题课本上有错误）
yG（x,y）
yG（t,y）
xy（F（x）G（t,y））
x1F（x1,x2）
（H（x1）
x2G（x1,x2））
x1F（x1,x2）（H（x3）
x2G（x3,x2））
x1F（x1,x4）x2（H（x3）G（x3,x2））
x1x2（F（x1,x4）（H（x3）G（x3,x2）））
15.在自然数推理系统F中,构造下面推理的证明:
（1）前提:
xF（x）y（（F（y）G（y））R（y））,xF（x）
结论:
xR（x）
（2）前提:
x（F（x）→（G（a）∧R（x）））,xF（x）
x（F（x）∧R（x））
证明
（1）
xF（x）
②F（c）
①EI
③
y（（F（y）G（y））
R（y））前提引入
④
y（（F（y）
G（y））R（y））
①③假言推理
⑤（F（c）∨G（c））→R（c））④UI
⑥F（c）∨G（c）②附加
⑦R（c）⑤⑥假言推理
⑧xR（x）⑦EG
①xF（x）前提引入
②F（c）①EI
③x（F（x）→（G（a）∧R（x）））前提引入
④F（c）→（G（a）∧R（c））③UI
⑤G（a）∧R（c）②④假言推理
⑥R（c）⑤化简
⑦F（c）∧R（c）②⑥合取引入
⑧x（F（x）∧R（x））⑦EG
第六章部分课后习题参考答案
5.确定下列命题是否为真：
（1）
真
假
（3）
{
}
（5）｛a,b｝
｛a,b,c,
｛a,b,c｝｝
（6）｛a,b｝
｛a,b｝｝
（7）｛a,b｝
｛a,b,｛｛a,b｝｝｝
（8）｛a,b｝
｛a,b,｛｛a,b｝｝｝
6．设a,b,c各不相同，判断下述等式中哪个等式为真:
（1）｛｛a,b｝，c,｝=｛｛a,b｝,c｝假
（2）｛a,b,a｝=｛a,b｝真
（3）｛｛a｝，{b}｝=｛｛a,b｝｝假
（4）｛
，｛
｝，a,b｝=｛｛
｛
｝｝,a,b｝
8．求下列集合的幂集：
（1）｛a,b,c｝
P（A）={
{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
（2）｛1，｛2，3｝｝P（A）={
{1},
{{2,3}},
{1
，{2，3}}}
（3）｛
｝
｝}
｝｝P（A）={
14．化简下列集合表达式：
（1）（AB）B）-（AB）
（2）（（ABC）-（BC））A
（1）（AB）B）-（AB）=（AB）B）～（AB）
=（AB）～（AB））B=B=
（2）（（ABC）-（BC））A=（（ABC）～（BC））A
=（A～（BC））（（BC）～（BC））A
=（A～（BC））A=（A～（BC））A=A
18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。
已知6个会打网球的人都会打篮球或排球。
求不会打球的人数。
阿A={会打篮球的人}，B={会打排球的人}，C={会打网球
的人}
|A|=14,|B|=12,|AB|=6,|AC|=5,|ABC|=2,
|C|=6,CAB
如图所示。
25-（5+4+2+3）-5-1=25-14-5-1=5
不会打球的人共5人
21.设集合A＝{{1，2}，{2，3}，{1，3},{}},计算下列表达式：
（1）A
（2）A
（3）A
（4）A
A={1，2}
{2，3}
{1，3}
}={1，2，3,}
}=
A=123
=
（4）
A=
27、设A,B,C是任意集合，证明
（1）（A-B）-C=A-BC
（2）（A-B）-C=（A-C）-（B-C）
（A-B）-C=（A
～B）
～C=A
（～B～C）=A～（B
C）=A-BC
（A-C）-（B-C）=（A
～C）
～（B
～C）=（A
～C）
（～BC）
=（A
～C
～B）
（A
～C
C）=（A～C
=A
C）=A-B
C由
（1）得证。
第七章部分课后习题参考答案
7.列出集合A={2,3,4}上的恒等关系IA,全域关系EA,小于或等于关系LA,整除关系DA.
IA={<
2，2>
<
3,3>
4,4>
EA={<
2,2>
2,3>
2,4>
3,4>
3,2>
4,2>
4,3>
LA={<
DA={<
13.设A={<
1,2>
}B={<
1,3>
求AB,AB,domA,domB,dom（AB）,ranA,ranB,ran（AB）,fld（A-B）.
AB={<
AB={<
domA={1,2,3}
domB={1,2,4}
dom（A∨B）={1,2,3,4}
ranA={2,3,4}
ranB={2,3,4}
ran（AB）={4}
A-B={<
}，fld（A-B）={1,2,3}
14.设R={<
0,1>
<
0,2>
0,3>
求RR,R-1,R{0,1,},R[{1,2}]
RR={<
R-1,={<
1,0>
2,0>
3,0>
2,1>
3,1>
R{0,1}={<
R[{1,2}]=ran（R|{1,2}）={2,3}
16．设A={a,b,c,d}，R
R2为A上的关系，其中
1，
R1=
a,a,a,b,b,d
R2
a,d,b,c,b,d
c,b
求R1R2,R2R1,R12,R23。
R1R2={<
a,d>
a,c>
}R2R1={<
c,d>
R12=R1R1={<
a,a>
a,b>
}R22=R2R2={<
b,b>
c,c>
}R23=R2R22={<
b,c>
c,b>
b,d>
36．设A={1，2，3，4}，在AA上定义二元关系R，
u,v>
x,y>
AA，〈u,v>
R<
u+y=x+v.
（1）证明R是AA上的等价关系.
（2）确定由R引起的对AA的划分.
（1）证明：
∵<
R<
u+y=x-y
∴<
u-v=x-y
AA
∵u-v=u-v
∴<
∴R是自反的
任意的<
∈A×
A
如果<
，那么u-v=x-y
∴x-y=
升级会员 