离散数学屈婉玲版课后答案.docx
《离散数学屈婉玲版课后答案.docx》由会员分享，可在线阅读，更多相关《离散数学屈婉玲版课后答案.docx（150页珍藏版）》请在冰点文库上搜索。
离散数学屈婉玲版课后答案
3®-
习题一
1.1.略
1.2.略
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飞.
（3）2+24与3+3=6互为充要条件.
（4）若2+22,则3+3一6,反之亦然.
⑴pp,其中,p:
2+2=4,q:
3+3=6,真值为1.
（2）p：
l_q,其中,p:
2+2=4,q:
3+3=6,真值为0.
⑶*pp,其中,p:
2+2=4,q:
3+3=6,真值为0.⑷一p—q,其中,p:
2+2=4,q:
3+3=6,真值为1.
将下列命题符号化，并给岀各命题的真值：
（1）若今天是星期一，则明天是星期二.一一
——
（2）只有今天是星期一，明天才是星期二.
（3）今天是星期一当且仅当明天是星期二.
（4）若今天是星期一，则明天是星期三.
令p:
今天是星期一；q:
明天是星期二；r:
明天是星期三
（1）pq'''1.
⑵q'p「4
⑶pq'''1.
（4）p"r当p'''0时为真;p'1时为假.
将下列命题符号化.
（1）刘晓月跑得快，跳得高.
（2）老王是山东人或河北人.
（3）因为天气冷，所以我穿了羽绒服.
（4）王欢与李乐组成一个小组.
（5）李辛与李末是兄弟.
——（6）王强与刘威都学过法语—.
（7）他一面吃饭，一面听音乐.
（8）如果天下大雨，他就乘班车上班.
（9）只有天下大雨，他才乘班车上班.
（10）除非天下大雨，他才乘班车上班.
（11）下雪路滑,他迟到了.
（12）2与4都是素数，这是不对的.
（13）或4是素数，这是不对的”是不对的.
（1）pq,其中，p:
刘晓月跑得快，q:
刘晓月跳得高.
（2）pq,其中,p:
老王是山东人，q:
老王是河北人.
⑶p'q,其中，p:
天气冷，q:
我穿了羽绒服.
（4）p,其中，p:
王欢与李乐组成一个小组，是简单命题
（5）p,其中，p:
李辛与李末是兄弟.
（6）pq,其中，p:
王强学过法语，q:
刘威学过法语.
（7）pq,其中，p:
他吃饭，q:
他听音乐.
（8）p"q,其中，p:
天下大雨，q:
他乘班车上班.
（9）p'q,其中，p:
他乘班车上班，q:
天下大雨.
（10）pp,其中，p:
他乘班车上班，q:
天下大雨.
（11）p-q,其中，p:
下雪路滑,q:
他迟到了.
（12）—（pq）或一pjiq,其中，p:
2是素数，q:
4是素数.
（13）/i（pq）或pq,其中,p:
2是素数,q:
4是素数.
（1）真值为0.
（2）真值为0.
（3）真值为0.
（4）真值为1.
注意：
p,q是真命题,r是假命题.
1.16.略
1.17.略
1.18.略
1.19.用真值表判断下列公式的类型
（1）<（pqr）
（2）（P_q厂-q
⑶"（q'r）r
⑷（p-q）,qJp）
（5）（pr）"（『p『q）
（6）（（p'q）（（7）（^q）"（r's）
⑴,（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,则地球是静止不动的.
⑵若3+2=4,则地球是运动不止的.—
（3）若地球上没有树木，则人类不能生存.
（4）若地球上没有水，则3是无理数.
⑴pp,其中，p:
2+2=4,q:
地球静止不动］真值为0.
⑵p-q,其中，p:
2+2=4,q:
地球运动不止，真值为1.
（3）:
―p：
l-q,其中，p:
地球上有树木，q:
人类能生存，真值为1.
⑷:
一p'q,其中，p:
地球上有水，q:
3是无理数，真值为1.
习题二
2.1.设公式A=p■q,B=p—.：
.q,用真值表验证公式A和B适合德摩根律
（AB）〉：
_AjB.
A=pqB=piq
10
l（A（B）『AeB
110
001
11
1
因为1（AB）和：
—Ai,.B的真值表相同，所以它们等值
Pqr
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
（1）—（pqp）w—（―（Pq）q）心—（—p「qq）'pq：
：
：
—q■p00；0.矛盾式.
（2）重言式.
⑶（pq）"（pr）（pq）（pr），piqpr易见，是可满足式，但不是重言式.成真赋值为：
000,
001,101,111
-p厂—qpr
11101
11110
10000
10000
1010000111
00000
00011
0
2.4.用等值演算法证明下面等值式
（1）P：
（Pq）（P『q）
（3）J（p"q）"（P（q）A（PR）
（4）（P•q）（Pq）■■■（pq）-（pq）
（1）（pq）（p：
：
：
—q）"'p（qq）"'p1'p.⑶『（p'q）
（（pP）（q"p））
一（（一pq）（-qp））
；（p.」q）（q.—p）
■■■（pq）（p-p）（-qq）（—p：
.—q）
■■■（pq）（pq）
⑷（p：
：
t）（:
—pq）
■■■（^：
-p）（pq）（up）dq）
■■■（pq）*（pq）
2.5.求下列公式的主析取范式，并求成真赋值
（1）（Wq）"（・q（p）
（2）Rp冷）田于
（3）（P（（qD?
s（Pp（r）
（1）（「pF）"qP）
■"：
-（pq）（:
—qp）
z-pj—qpp、一q:
-qp（吸收律f'（PP）—：
qP（qq）
伽p〜q科peq（p可（冲鼻q
mio
成真赋值为00,10,11.
（2）主析取范式为0,无成真赋值，为矛盾式.
（3）m0m1m2m3m4m5m6m7,为重言式.
（1）：
-（q：
-p）；：
-p
用H—qip）■--p
qP:
--p
q0
■■0
■■M0M1M2M3
这是矛盾式.成假赋值为00,01,10,11.
（2）M4,成假赋值为100.
（3）主合取范式为1,为重言式.
2.7.求下列公式的主析取范式，再用主析取范式求合取范式
^=
（1）（pq）r
（2）（pP）.gr）
（1）mim3m5m6m^'MoM2M4
（2）momim3mF'-M2M4M5M6
2.8.略
2.9.用真值表求下面公式的主析取范式
（2）（p-q）"（p：
_q）
pq
（pq）"（piq）
00
i00i
0i
iii0
i0
0iii
ii
i000
（2）从真值表可见成真赋值为01,10.于是（p"q）i（p—'q）；mim2.
（2）（pp）冲
■":
-epq）r
E-（—pq）r
Tp：
—hqr
pqLr）（pp）（q^q）r
Tpi.：
，qrpi.：
，q：
Ar
pqrpQqr「pqr「p『qr
=mioimioommmioimoiimooi
'mim3m4m5m7
='（i,3,4,5,7）.
而q"（pr）
':
一q（ipr）
[pr
■■'Cpp）qCrr）-p（qq）（-rr）
（pp）eqq）r
■■'eP—q—r）（，Prqr）（prq=—r）（prqr）
C^-^-r）CP「qr）Cpqi—r）（pqr）
（P「qr）（pqr）（p「qr）（pqr）
=momim4m5
m°m1m2m3
mim3m5m7!
；“m°mim2m3m4m5m7
■■■■■（0,1,2,3,4,5,7）.
2.16.用主析取范式判断下列公式是否等值
（1）（p「q）'T与q,p”r）
（2）*-（P国）与*（P（q）
（i）
（pp）'r）'-mim3m4m5m7
（p'r）'-momim2m3m4m5m7所以（p-q）-r）q-（p-Q
⑵
—（pq）■'"momim2
:
一（pq）■■m0
所以i（pq）:
一（pq）
2.18.略
2.19.略
2.20.将下列公式化成与之等值且仅含｛「,'｝中联结词的公式
⑶（pq）'r.
注意到A'B'^（AB）（BA）和AB「：
一（lA：
_dB）1（A：
-B）以及AB「：
一A“B.
（pq）r
■■■（pq"r）（r"pq）
…「（一（P-W）“--（p-q））
心-（（「（P"q）"r）（r二（p'q）））注联结词越少，公式越长.
2.21.证明：
（1）（p©■■■（（p-q）2「（pq）用-（qp）：
（q-p）.（p-q）w-（pq）w-（qp）'■■（q'p）.
（1）取A=p,B=q,C=1（重言式）,有
AC■■■BC,但AB.
⑵取A=p,B=q,C=0（矛盾式）,有
AC'BC,但AB.
好的例子是简单，具体，而又说明问题的
⑶一定.
2.26.略
2.27.某电路中有一个灯泡和三个开关A,B,C.已知在且仅在下述四种情况下灯亮
（1）C的扳键向上，A,B的扳键向下.
（2）A的扳键向上，B,C的扳键向下.
（3）B,C的扳键向上，A的扳键向下.
（4）A,B的扳键向上，C的扳键向下.
设F为1表示灯亮，p,q,r分别表示A,B,C的扳键向上.
（a）求F的主析取范式.
（b）在联结词完备集｛1,耳上构造F.
（c）在联结词完备集｛1上构造F.
（a）由条件
（1）-（4）可知,F的主析取范式为
^-qr）（p「r）（pqr）（pq.—r）
m1m4m3m6
m1m3m4m6
（b）先化简公式
F「（一P.」qr）（p、_q._r）（-pqr）（pq二一r）用T（（—Pr）（Pj—r））q（（—pr）（p—））
■\-qq）（（—pr）（Pj—r））
：
（—Pr）（p：
：
:
—r）
■'（:
—（:
—Pr）（p：
：
:
—r））（已为｛i,｝中公式）
（c）
F：
（—pr）（p,：
_r）
■l;'——&Pr）（p「r）
:
（Pr厂（p•r）
■■■（P^r）1_（：
_pr）
■■■（r'p）—（^r）（已为｛—「「｝中公式）
2.28.—个排队线路，输入为A,B,C,其输出分别为Fa,Fb,Fc.本线路中，在同一时间内只能有一个信号通过，
若同时有两个和两个以上信号申请输出时，则按A,B,C的顺序输出.写出Fa,Fb,Fc在联结词完备集｛一，｝
中的表达式.——
根据题目中的要求，先写岀Fa,Fb,Fc的真值表（自己写）
由真值表可先求岀他们的主析取范式，然后化成｛：
_,｝中的公式
Fa'-'m4m5m6m7
Fb-m2m3
Fc'-'mi
2—prqr（已为｛：
—,｝中公式）
2.29.略
2.30.略
3.1.略
3.2.略
3.3.略
3.4.略
3.5.略
3.6.判断下面推理是否正确.先将简单命题符号化，再写出前提，结论，推理的形式结构（以蕴涵式的形式给出）和判断过程（至少给出两种判断方法一）：
（1）若今天是星期一=,则明天是星期三；今天是星期一所以明天是星期三==
（2）若今天是星期一，则明天是星期二；明天是星期二—.所以今天是星期一.
（3）若今天是星期一，则明天是星期三；明天不是星期三=.所以今天不是星期一.
（4）若今天是星期一，则明天是星期二；今天不是星期一一.所以明天不是星期二.
（5）若今天是星期一=,则明天是星期二或星期三.
（6）今天是星期一当且仅当明天是星期三；今天不是星期一.所以明天不是星期三.
设p:
今天是星期一，q:
明天是星期二，r:
明天是星期三.
（1）推理的形式结构为
（Pr）pr
此形式结构为重言式，即
（p「）p：
$r
所以推理正确.
（2）推理的形式结构为
（p-q）q'p
此形式结构不是重言式，故推理不正确.
（3）推理形式结构为
（pi）—r-p
此形式结构为重言式，即
（p"r）：
Ar：
；p
故推理正确.
（4）推理形式结构为
0q）•p-q
此形式结构不是重言式，故推理不正确.
（5）推理形式结构为
叭*
p（qr）
它不是重言式，故推理不正确.
（6）推理形式结构为
（p吃r）：
：
:
—p；r
此形式结构为重言式，即
（p：
r）._p：
;r
故推理正确.
推理是否正确，可用多种方法证明.证明的方法有真值表法，等式演算法.证明推理正确还可用构造证明法下面用构造证明法证明（6）推理正确.
前提:
p逹r,ip
前提引入
①置换
②化简律
前提引入
③④拒取式
结论:
—r
证明:
①p：
$r
2（p'r）（r'p）
3r"p
41p
5『r
所以，推理正确.
3.7.略
3.8.略
3.9.用三种方法（真值表法，等值演算法，主析取范式法）证明下面推理是正确的：
不是奇数.
若a是奇数，则a不能被2整除.若a是偶数，则a能被2整除.因此，如果a是偶数，则a
令p:
a是奇数；q:
a能被2整除；r:
a是偶数.
前提：
p"q，r'q.
结论：
r"■■p.
形式结构：
（p:
—q）（r"q）"（r:
-p）.
3.10.略
3.11.略
3.12.略
3.13.略
3.14.在自然推理系统P中构造下面推理的证明
（1）前提：
P,q】），p，q结论:
r（s
（2）前提：
pp,J（q“r结论:
*-p
（3）前提：
p飞
结论:
p,p可）
（4）前提：
q'p，q還s,s®,tsr
结论：
p可
（5）前提：
p】,
⑴证明:
P（qr）
②
p
q十③
④
q
⑤
r
rs⑥
前提引入
①②假言推理
前提引入
③④假言推理
⑤附加律
（2）证明:
前提引入
-（qr）①①置换
「q-r②前提引入
②③析取三段论
T④
pp⑤
’p⑥
前提引入
④⑤拒取式
（3）
前提引入
①置换
证明：
pq①
:
-pq②
（—pq）（—pp）
-p（pq）p"（pq）
也可以用附加前提证明法，更简单些.
（4）证明:
s3t
（st）（ts）
ts
④化简
③⑤假言推理前提引入
7置换
8化简
⑥⑥假言推理
tr
5t
6s
qWs⑦
（sq）（qs）⑧
sq⑨
o
12p
13
⑩o假言推理
11
⑩o合取
12
（5）证明:
p"r①前提引入
q"s②前提引入
pq③前提引入
说明：
证明中，附加提前t,前提「qs没用上.这仍是正确的推理
3.15.在自然推理系统P中用附加前提法证明下面各推理——:
（1）前提:
P,q「）,sp,q—
结论:
s'r
——
（2）前提：
（pq）"（rs）,（st）"u
结论:
p-u
（1）
证明:
①s
sp②
③p
p（qr）④q"r⑤
6q
7r
（2）证明:
pq②
（pq）"（rs）③
rs④
附加前提引入
1附加
前提引入
②③假言推理
4化简
st⑥
（st）'u⑦
⑤附加
前提引入
⑥⑦假言推理
3.16.在自然推理系统P中用归谬法证明下面推理
（1）前提：
p'Jq,*-r（q,^-s
/,I.、A
结论：
—p
⑵前提:
pq,结论：
rs
（1）证明:
①P
p—q②
q③
—rq④
—r⑤
rt-s⑥
7r
rr⑧结论否定引入前提引入
①②假言推理
前提引入
③④析取三段论
前提引入
⑥化简
⑤⑦合取
8为矛盾式，由归谬法可知，推理正确.
（2）证明:
一（rs）
pq
pr
qs
rs
is）（rs）
⑥为矛盾式，所以推理正确
3.仃.P5317.在自然推理系统P中构造下面推理的证明：
只要A曾到过受害者房间并且一11点以前没用离开，A就犯了谋杀罪.A曾到过受害者房间一.如果A在
11点以前离开，看门人会看到他=看门人没有看到他=.所以=A犯了谋杀罪.
令p:
A曾到过受害者房间；q:
A在11点以前离开了；r:
A就犯了谋杀罪；s:
看门人看到A.
前提：
r,p,qJSs,^-s.
结论：
r.
结论：
r.
前提：
心夕q计，p,q?
ss,.s;
证明：
1-s前提引入
2q's前提引入
3：
_q①②拒取
前提引入④p
5p_.：
.q③④合取
6p_：
q"r前提引入
7r⑤⑥假言推理
3.佃.在自然推理系统P中构造下面推理的证明.
（1）如果今天是星期六，我们就要到颐和园或圆明园去玩.如果颐和园游人太多，我们就不去颐和园玩.
今天是星期六.颐和园游人太多.所以我们去圆明园玩.
（2）如果小王是理科学生，他的数学成绩一定很好.如果小王不是文科生，他必是理科生.小王的数学成绩不好.所以小王是文科学生.
（3）明天是晴天，或是雨天；若明天是晴天，我就去看电影；若我看电影，我就不看书.所以，如果我看书,则明天是雨天.
（1）令p:
今天是星期六；q:
我们要到颐和园玩；r:
我们要到圆明园玩；s:
颐和园游人太多前提：
p"（qr）,s-q,p,s.
结论：
r.
④
前提引入
前提引入
③⑥析取三段论
（1）的证明树④⑤假言推理
（2）令p:
小王是理科生，q:
小王是文科生，r:
小王的数学成绩很好
前提：
p计,iq讳,«r
结论：
q
证明：
:
_r②前提引入ip③①②拒取式
<-q'p④前提引入
⑤③④拒取式q
⑶令p:
明天是晴天，q:
明天是雨天，r:
我看电影，s:
我看书.
前提：
pq，卩十,r二s
结论:
sq
证明：
①附加前提引入s
L-s②前提引入
-r③①②拒取式
4前提引入
ip⑤③④拒取式
pq⑥前提引入
⑦⑤⑥析取三段论q
习题四
4.1.将下面命题用0元谓词符号化：
（1）小王学过英语和法语==
（2）除非李建是东北人，否则他一定怕冷.
⑴令F（x）:
x学过英语；F（x）:
x学过法语；a:
小王.符号化为
F（a）F（b）.
或进一步细分，令L（x,y）:
x学过y;a:
小王；bi:
英语；b2:
法语.则符号化为
L（a,bi）L（a,b2）.
⑵令F（x）:
x是东北人；G（x）:
x怕冷；a:
李建.符号化为
:
_F（a）"G（a）或iG（a厂F（a）.
或进一步细分，令H（x,y）:
x是y地方人；G（x）:
x怕冷；a:
小王；b:
东北.则符号化为
:
_H（a,b「G（a）或：
一G（a厂H（a,b）.
（b）中，x（G（x）F（x））,其中，G（x）:
x为有理数，F（x）同（a）中，真值为0.
⑵（a）中「xF（x）,其中，F（x）:
x能被2整除，真值为1.
（b）中，k（G（x）F（x））,其中，F（x）同（a）中，G（x）:
x为有理数，真值为1.
4.3.在一阶逻辑中将下面命题符号化，并分别讨论个体域限制为（a）,（b）时命题的真值
（1）对于任意的x,均有x2“2=（x+2）（^2）.
⑵存在x,使得x+5=9.
其中（a）个体域为自然数集合，（b）个体域为实数集合.
（1）（a）中,x（x2“2=（x+2）（^2））,真值为1.
（b）中，x（F（x）"（x^"2=（x+2）（/2））））,其中,F（x）:
x为实数,真值为1.⑵（a）中,"x（x+5=9）,真值为1.
（b）中，"x（F（x）（x+5=9））,其中，F（x）:
x为实数，真值为1.
4.4.在一阶逻辑中将下列命题符号化：
（1）没有不能表示成分数的有理数.
（2）在北京卖菜的人不全是外地人.
（3）乌鸦都是黑色的.
（4）有的人天天锻炼身体没指定个体域，因而使用全总个体域.
（1）：
—，x（F（x）：
：
：
_G（x））或x（F（x）"G（x））,其中，F（x）:
x为有理数，G（x）:
贿总表示成分数
⑵:
—x（F（x）'G（x））或'x（F（x）■.：
：
—G（x））,其中，F（x）:
x在北京卖菜，G（x）:
x是外地人.
（3）x（F（x）'G（x）），其中，F（x）:
x是乌鸦，G（x）:
x是黑色的.
⑷'x（F（x）G（x）），其中，F（x）:
x是人，G（x）:
x天天锻炼身体.
因为没指明个体域，因而使用全总个体域
（1）xy（F（x）G（y厂H（x,y））,其中，F（x）:
x是火车，G（y）:
y是轮船，H（x,y）:
x比y快.
（2）'^y（F（x）G（y）H（x,y））,其中,F（x）:
x是火车,G（y）:
y是汽车,H（x,y）:
x比y快.
⑶・=（F（x）y（G（y厂H（x,y）））
或x（F（x）■"y（G（y）j-H（x,y）））,其中,F（x）:
x是汽车,G（y）:
y是火车,H（x,y）:
x比y快.
⑷•xy（F（x）G（y）"H（x,y））
或'x'y（F（x）G（y）■-H（x,y））,其中,F（x）:
x是汽车,G（y）:
y是火车,H（x,y）:
x比y慢.
4.
升级会员 