离散数学习题解答.docx

资源描述

离散数学习题解答.docx

《离散数学习题解答.docx》由会员分享，可在线阅读，更多相关《离散数学习题解答.docx（60页珍藏版）》请在冰点文库上搜索。

离散数学习题解答.docx

离散数学习题解答

离散数学习题答案

习题一

1.判断下列句子是否为命题？

若是命题说明是真命题还是假命题。

（1）3是正数吗？

（2）x＋1=0。

（3）请穿上外衣。

（4）2＋1＝0。

（5）任一个实数的平方都是正实数。

（6）不存在最大素数。

（7）明天我去看电影。

（8）9＋5≤12。

（9）实践出真知。

（10）如果我掌握了英语、法语，那么学习其他欧洲语言就容易多了。

解：

（1）、

（2）、（3）不是命题。

（4）、（8）是假命题。

（5）、（6）、（9）、（10）是真命题。

（7）是命题，只是现在无法确定真值。

2.设P表示命题“天下雪”，Q表示命题“我将去书店”，R表示命题“我有时间”，以符号形式写出下列命题。

（1）如果天不下雪并且我有时间，那么我将去书店。

（2）我将去书店，仅当我有时间。

（3）天不下雪。

（4）天下雪，我将不去书店。

解：

（1）（┐P∧R）→Q。

（2）Q→R。

（3）┐P。

（4）P→┐Q。

3.将下列命题符号化。

（1）王皓球打得好，歌也唱得好。

（2）我一边看书，一边听音乐。

（3）老张和老李都是球迷。

（4）只要努力学习，成绩会好的。

（5）只有休息好，才能工作好。

（6）如果a和b是偶数，那么a+b也是偶数。

（7）我们不能既游泳又跑步。

（8）我反悔，仅当太阳从西边出来。

（9）如果f（x）在点x0处可导，则f（x）在点x0处可微。

反之亦然。

（10）如果张老师和李老师都不讲这门课，那么王老师就讲这门课。

（11）四边形ABCD是平行四边形，当且仅当ABCD的对边平行。

（12）或者你没有给我写信，或者信在途中丢失了。

解：

（1）P：

王皓球打得好，Q：

王皓歌唱得好。

原命题可符号化：

P∧Q。

（2）P：

我看书，Q：

我听音乐。

原命题可符号化：

P∧Q。

（3）P：

老张是球迷，Q：

老李是球迷。

原命题可符号化：

P∧Q。

（4）P：

努力学习，Q：

成绩会好。

原命题可符号化：

P→Q。

（5）P：

休息好，Q：

工作好。

原命题可符号化：

Q→P。

（6）P：

a是偶数，Q：

b是偶数，R：

a+b是偶数。

原命题可符号化：

（P∧Q）→R。

（7）P：

我们游泳，Q：

我们跑步。

原命题可符号化：

┐（P∧Q）。

（8）P：

我反悔，Q：

太阳从西边出来。

原命题可符号化：

P→Q。

（9）P：

f（x）在点x0处可导，Q：

f（x）在点x0处可微。

原命题可符号化：

P→←Q。

（10）P：

张老师讲这门课，Q：

李老师讲这门课，R：

王老师讲这门课。

原命题可符号化：

（┐P∧┐Q）→R。

（11）P：

四边形ABCD是平行四边形，Q：

四边形ABCD的对边平行。

原命题可符号化：

P→←Q。

（12）P：

你给我写信，Q：

信在途中丢失了。

原命题可符号化：

┐P←∣→（P∧Q）。

4.判断下列公式哪些是合式公式，哪些不是合式公式。

（1）（Q→R∧S）

（2）（P→←（R→S））

（3）（（┐P→Q）→（Q→P）））

（4）（RS→F）

（5）（（P→（Q→R））→（（P→Q）→（P→R）））

解：

（1）、

（2）、（5）是合式公式，（3）、（4）不是合式公式。

5.否定下列命题：

（1）桂林处处山清水秀。

（2）每一个自然数都是偶数。

解：

（1）桂林并非处处山清水秀。

（2）并不是每一个自然数都是偶数。

或：

有些自然数不是偶数。

6.给出下述每一个命题的逆命题、否命题和逆否命题。

（1）如果天下雨，我将不去。

（2）仅当你去我才不去。

（3）如果Δ=b2−4ac<0，则方程ax2+bx+c=0无实数解。

（4）如果我不获得奖学金，我就不能完成学业。

解：

（1）逆命题：

如果我不去，那么天下雨。

否命题：

如果天不下雨，我就去。

逆否命题：

如果我去，那么天不下雨。

（2）逆命题：

如果你去，我将不去。

否命题：

如果我去，你将不去。

逆否命题：

如果你不去，我就去。

（3）逆命题：

如果方程ax2+bx+c=0无实数解，则Δ=b2−4ac<0。

否命题：

如果Δ=b2−4ac≥0，则方程ax2+bx+c=0有实数解。

逆否命题：

如果方程ax2+bx+c=0有实数解，则Δ=b2−4ac≥0。

（4）逆命题：

如果我不能完成学业，那么我没有获得奖学金。

否命题：

如果我获得奖学金，我就能完成学业。

逆否命题：

如果我就能完成学业，那么我就获得奖学金。

7.求下列各式的真值表。

（1）P→（R∨S）

（2）（P∧R）∨（P→Q）

（3）（P∨Q）→←（Q∨P）

（4）（P∨┐Q）∧R

（5）（P→（Q→R））→（（P→Q）→（P→R））

解：

（1）P→（R∨S）

R∨S

P→（R∨S）

（2）（P∧R）∨（P→Q）

P∧R

P→Q

（P∧R）∨（P→Q）

（3）（P∨Q）→←（Q∨P）

P∨Q

Q∨P

（P∨Q）→←（Q∨P）

（4）（P∨┐Q）∧R

┐Q

P∨┐Q

（P∨┐Q）∧R

（5）（P→（Q→R））→（（P→Q）→（P→R））

Q→R

P→（Q→R）

P→Q

P→R

（P→Q）→（P→R）

原公式

8.用真值表判断下列公式的类型：

（1）P∨┐Q→Q

（2）（（P→Q）∨（R→S））→（（P∨R）→（Q∨S））

解：

（1）P∨┐Q→Q

┐Q

P∨┐Q

P∨┐Q→Q

（1）为可满足式。

（2）（（P→Q）∨（R→S））→（（P∨R）→（Q∨S））

P→Q

R→S

（P→Q）∨（R→S）

P∨R

Q∨S

（P∨R）→（Q∨S）

原公式

（2）为可满足式。

9.证明下列等价式。

（1）P→（Q→P）⇔┐P→（P→┐Q）

（2）┐（P→←Q）⇔（P∨Q）∧┐（P∧Q）

（3）┐（P→Q）⇔P∧┐Q

（4）┐（P→←Q）⇔（P∧┐Q）∨（┐P∧Q）

（5）P→（Q∨R）⇔（P∧┐Q）→R

（6）（P→R）∧（Q→R）⇔（P∨Q）→R

（7）（（P∧Q）→R）∧（Q→（S∨R））⇔（Q∧（S→P））→R

证明：

（1）P→（Q→P）⇔┐P∨（┐Q∨P）⇔P∨（┐P∨┐Q）⇔┐P→（P→┐Q）

（2）┐（P→←Q）⇔┐（（P∧Q）∨（┐P∧┐Q））⇔┐（P∧Q）∧┐（┐P∧┐Q））⇔（P∨Q）∧┐（P∧Q）

（3）┐（P→Q）⇔┐（┐P∨Q）⇔P∧┐Q

（4）┐（P→←Q）⇔┐（（P→Q）∧（Q→P））⇔┐（┐P∨Q）∨┐（┐Q∨P）⇔（P∧┐Q）∨（┐P∧Q）

（5）P→（Q∨R）⇔┐P∨（Q∨R）⇔┐（P∧┐Q）∨R⇔（P∧┐Q）→R

（6）（P→R）∧（Q→R）⇔（┐P∨R）∧（┐Q∨R）⇔（┐P∧┐Q）∨R⇔┐（P∨Q）∨R⇔（P∨Q）→R

（7）（（P∧Q）→R）∧（Q→（S∨R））⇔（┐（P∧Q）∨R）∧（┐Q∨（S∨R））⇔┐Q∨（┐P∧S）∨R

⇔┐（Q∧（┐S∨P））∨R⇔┐（Q∧（S→P））∨R⇔（Q∧（S→P））→R

10.使用恒等式证明下列各式，并写出它们对偶的公式。

（1）（┐（┐P∨┐Q）∨┐（┐P∨Q））⇔P

（2）（P∨┐Q）∧（P∨Q）∧（┐P∨┐Q）⇔┐（┐P∨Q）

（3）Q∨┐（（┐P∨Q）∧P）⇔T

证明：

（1）（┐（┐P∨┐Q）∨┐（┐P∨Q））⇔（P∧Q）∨（P∧┐Q）⇔P∧（Q∨┐Q）⇔P∧T⇔P

（2）（P∨┐Q）∧（P∨Q）∧（┐P∨┐Q）⇔P∨（┐Q∧Q）∧（┐P∨┐Q）⇔P∨F∧（┐P∨┐Q）⇔P∧（┐P∨┐Q）⇔（P∧┐P）∨（P∧┐Q）⇔F∨（P∧┐Q）⇔（P∧┐Q）⇔┐（┐P∨Q）

（3）Q∨┐（（┐P∨Q）∧P）⇔Q∨（┐（┐P∨Q）∨┐P）⇔Q∨（P∧┐Q）∨┐P

⇔（Q∨┐P∨P）∧（Q∨┐P∨┐Q）⇔T∨T⇔T

11.试证明{∨}，{→}不是全功能联结词集合。

证明：

若{∨}是最小联结词组，则┐P⇔（P∨...）

对所有命题变元指派T，则等价式左边为F，右边为T，等价式矛盾。

若{→}是最小联结词组，则┐P⇔P→（P→（P→...）...）

对所有命题变元指派T，则等价式左边为F，右边为T，等价式矛盾。

12.证明下列蕴涵式：

（1）P∧Q⇒（P→Q）

（2）P⇒（Q→P）

（3）（P→（Q→R））⇒（P→Q）→（P→R）

证明：

（1）P∧Q→（P→Q）⇔┐（P∧Q）∨（P→Q）⇔（┐P∨┐Q）∨（┐P∨Q）⇔┐P∨（┐Q∨Q）⇔T

因为P∧Q→（P→Q）为永真式，所以P∧Q⇒（P→Q）。

（2）P→（Q→P）⇔┐P∨（┐Q∨P）⇔┐Q∨（┐P∨P）⇔T

因为P→（Q→P）为永真式，所以P⇒（Q→P）。

（3）（P→（Q→R））→（（P→Q）→（P→R））

⇔┐（┐P∨（┐Q∨R））∨（┐（┐P∨Q）∨（┐P∨R））

⇔（P∧（Q∧┐R））∨（（P∧┐Q）∨（┐P∨R））

⇔（P∧Q∧┐R）∨（（P∨┐P∨R）∧（┐Q∨┐P∨R））

⇔（P∧Q∧┐R）∨（┐P∨┐Q∨R）

⇔（（P∨（┐P∨┐Q∨R））∧（Q∨（┐P∨┐Q∨R））∧（┐R∨（┐P∨┐Q∨R））⇔T

因为（P→（Q→R））→（（P→Q）→（P→R））为永真式，所以（P→（Q→R））⇒（P→Q）→（P→R）。

13.对下列各公式，试仅用↑或↓表示。

（1）┐P

（2）P∧Q

（3）P∨Q

（4）P→Q

解：

（1）┐P⇔┐（P∧P）⇔P↑P

（2）P∧Q⇔（P↑Q）↑（P↑Q）

（3）P∨Q⇔┐（┐P∧┐Q）⇔（┐P↑┐Q）⇔（P↑P）↑（Q↑Q）

（4）P→Q⇔┐P∨Q⇔（P↑P）∨Q⇔（（P↑P）↑（P↑P））↑（Q↑Q）

14.将下列公式化成与之等值且仅含{┐，→}中联结词的公式。

（1）（P→┐Q）∧R

（2）P→←（Q∧R）∨P

解：

（1）（P→┐Q）∧R⇔（┐P∨┐Q）∧R⇔（┐P∧R）∨（┐Q∧R）⇔┐（P∨┐R）∨┐（Q∨┐R）

⇔┐（R→P）∨┐（R→Q）⇔（R→P）→┐（R→Q）

（2）P→←（Q∧R）∨P⇔（P→（（Q∧R）∨P））∧（（（Q∧R）∨P）→P）⇔（┐P∨（（Q∧R）∨P））∧（┐（（Q∧R）∨P）∨P）⇔T∧（（（┐Q∨┐R）∧┐P）∨P）⇔（（┐Q∨┐R）∨P）⇔P∨（┐Q∨┐R）⇔P∨（Q→┐R）⇔┐P→（Q→┐R）

15.如果A（P，Q，R）由R↑（Q∧┐（R↓P））给出，求它的对偶A*（P，Q，R），并求出与A及A*等价且仅包含联接词“∧”，“∨”及“┐”的公式。

解：

A*（P，Q，R）：

R↓（Q∨┐（R↑P））

R↑（Q∧┐（R↓P））⇔┐（R∧（Q∧（R∨P）））⇔┐R∨┐Q∨（┐R∧┐P）

R↓（Q∨┐（R↑P））⇔┐R∧┐Q∧（┐R∨┐P）

16.把P↑Q表示为只含有“↓”的等价公式。

解：

P↑Q⇔┐（P∧Q）⇔┐（（P↓P）↓（Q↓Q））⇔（（P↓P）↓（Q↓Q））↓（（P↓P）↓（Q↓Q））

17.证明：

（1）┐（P↑Q）⇔┐P↓┐Q

（2）┐（P↓Q）⇔┐P↑┐Q

证明：

（1）┐（P↑Q）⇔┐（┐（P∧Q））⇔（P∧Q）⇔┐（┐P∨┐Q）⇔┐P↓┐Q

（2）┐（P↓Q）⇔┐（┐（P∨Q））⇔（P∨Q）⇔┐（┐P∧┐Q）⇔┐P↑┐Q

18.求公式P∧（P→Q）的析取范式和合取范式。

解：

P∧（P→Q）⇔P∧（┐P∨Q）合取范式

⇔（P∧┐P）∨（P∧Q）析取范式

19.求下列公式的主析取范式和主合取范式。

（1）（┐P→Q）→（┐Q∨P）

（2）（P→（P∨Q））∨R

（3）（P→Q∧R）∧（（┐P→（┐Q∧┐R））

解：

（1）真值表法

┐P→Q

┐Q∨P

（┐P→Q）→（┐Q∨P）

主析取范式为：

（P∧Q）∨（P∧┐Q）∨（┐P∧┐Q）

主合取范式为：

P∨┐Q

公式化归法

（┐P→Q）→（┐Q∨P）⇔┐（P∨Q）∨（┐Q∨P）⇔（┐P∧┐Q）∨（┐Q∨P）

⇔（┐P∨┐Q∨P）∧（┐Q∨┐Q∨P）⇔P∨┐Q主合取范式

⇔（P∧Q）∨（P∧┐Q）∨（┐P∧┐Q）主析取范式

（2）真值表法（P→（P∨Q））∨R

P∨Q

P→（P∨Q）

（P→（P∨Q））∨R

原式为永真式，其主析取范式为所有小项的析取，即：

m000∨m001∨m010∨m011∨m100∨m101∨m110∨m111

不能表示为主合取范式。

公式化归法

（P→（P∨Q））∨R⇔（┐P∨（P∨Q））∨R⇔T∨R⇔T

（3）真值表法（P→Q∧R）∧（（┐P→（┐Q∧┐R））

Q∧R

P→Q∧R

┐Q∧┐R

┐P→（┐Q∧┐R）

原公式

主析取范式为：

（P∧Q∧R）∨（┐P∧┐Q∧┐R）⇔m111∨m000⇔m7∨m0

主合取范式为：

M1∧M2∧M3∧M4∧M5∧M6⇔M001∧M010∧M011∧M100∧M101∧M110⇔（P∨Q∨┐R）∧（P∨┐Q∨R）∧（P∨┐Q∨┐R）∧（┐P∨Q∨R）∧（┐P∨Q∨┐R）∧（┐P∨┐Q∨R）

20.求下列公式的主析取范式和主合取范式，并指出该公式的类型。

（1）（┐P∨┐Q）→（P→←┐Q）

（2）Q∧（P∨┐Q）

（3）P∨（┐P→（Q∨（┐Q→R）））

（4）（P→（Q∧R））∧（┐P→（┐Q∧┐R））

（5）P→（P∧（Q→P））

（6）（Q→P）∧（┐P∧Q）

解：

（1）

┐P∨┐Q

P→←┐Q

（┐P∨┐Q）→（P→←┐Q）

主析取范式为：

（P∧Q）∨（P∧┐Q）∨（┐P∧Q）

主合取范式为：

P∨Q

公式为可满足式。

（2）

P∨┐Q

Q∧（P∨┐Q）

主析取范式为：

P∧Q

主合取范式为：

（┐P∨Q）∧（P∨┐Q）∧（P∨Q）

公式为可满足式。

（3）P∨（┐P→（Q∨（┐Q→R）））⇔P∨（P∨（Q∨（Q∨R）））

⇔P∨Q∨R主合取范式

⇔M000⇔M0⇔m1∨m2∨m3∨m4∨m5∨m6∨m7主析取范式

公式为可满足式。

（4）（P→（Q∧R））∧（┐P→（┐Q∧┐R））⇔（┐P∨（Q∧R））∧（P∨（┐Q∧┐R））⇔（┐P∨Q）∧（┐P∨R）∧（P∨┐Q）∧（P∨┐R）⇔（┐P∨Q∨R）∧（┐P∨Q∨┐R）∧（┐P∨┐Q∨┐R）∧（P∨┐Q∨R）∧（P∨┐Q∨┐R）∧（P∨Q∨┐R）⇔M100∧M101∧M111∧M010∧M011∧M001⇔M4∧M5∧M7∧M2∧M3∧M1主合取范式

⇔m0∨m6⇔m000∨m110主析取范式

公式为可满足式。

（5）P→（P∧（Q→P））⇔┐P∨（P∧（┐Q∨P））⇔（┐P∨P）∧（┐P∨（┐Q∨P））⇔T

主析取范式为：

m0∨m1∨m2∨m3

公式为永真式。

（6）（Q→P）∧（┐P∧Q）⇔（┐Q∨P）∧（┐P∧Q）⇔（┐Q∧┐P∧Q）∨（P∧┐P∧Q）⇔F

主合取范式为：

M0∧M1∧M2∧M3

公式为永假式。

21.用将合式公式化为范式的方法证明下列各题中两式是等价的。

（1）（P→Q）∧（P→R），P→（Q∧R）

（2）（P→Q）→（P∧Q），（┐P→Q）∧（Q→P）

（3）P∧Q∧（┐P∨┐Q），┐P∧┐Q∧（P∨Q）

（4）P∨（P→（P∧Q）），┐P∨┐Q∨（P∧Q）

证明：

（1）（P→Q）∧（P→R）⇔（┐P∨Q）∧（┐P∨R）

P→（Q∧R）⇔┐P∨（Q∧R）⇔（┐P∨Q）∧（┐P∨R）

（2）（P→Q）→（P∧Q）⇔┐（┐P∨Q）∨（P∧Q）⇔（P∧┐Q）∨（P∧Q）⇔P∧（┐Q∨Q）⇔P

（┐P→Q）∧（Q→P）⇔（P∨Q）∧（┐Q∨P）⇔P∨（Q∧┐Q）⇔P

（3）P∧Q∧（┐P∨┐Q）⇔（P∧Q∧┐P）∨（P∧Q∧┐Q）⇔F

┐P∧┐Q∧（P∨Q）⇔（┐P∧┐Q∧P）∨（┐P∧┐Q∧Q）⇔F

（4）P∨（P→（P∧Q））⇔P∨（┐P∨（P∧Q））⇔T∨（P∧Q）⇔T

┐P∨┐Q∨（P∧Q）⇔（┐P∨┐Q∨P）∧（┐P∨┐Q∨Q）⇔T

22.用推理规则证明以下各式。

（1）┐（P∧┐Q），┐Q∨R，┐R⇒┐P

（2）A→（B∨C），（D∨E）→A，D∨E⇒B∨C

（3）B∧C，（B→←C）→（D∨E）⇒D∨E

（4）P→Q，（┐Q∨R）∧┐R，┐（┐P∧S）⇒┐S

证明：

（1）┐（P∧┐Q），┐Q∨R，┐R⇒┐P

证明：

（1）┐RP

（2）┐Q∨RP

（3）┐QT

（1）

（2）I

（4）┐（P∧┐Q）P

（5）┐P∨QT（4）E

（6）┐PT（3）（5）I

（2）A→（B∨C），（D∨E）→A，D∨E⇒B∨C

证明：

（1）D∨EP

（2）（D∨E）→AP

（3）AT

（1）

（2）I

（4）A→（B∨C）P

（5）B∨CT（3）（4）I

（3）B∧C，（B→←C）→（D∨E）⇒D∨E

证明：

（1）B∧CP

（2）B→←CT

（1）I

（3）（B→←C）→（D∨E）P

（4）D∨ET

（2）（3）I

（4）P→Q，（┐Q∨R）∧┐R，┐（┐P∧S）⇒┐S

证明：

（1）（┐Q∨R）∧┐RP

（2）┐Q∨RT

（1）I

（3）┐RT

（1）I

（4）┐QT

（2）（3）I

（5）┐（┐P∧S）P

（6）S→PT（5）E

（7）P→QP

（8）S→QT（6）（7）I

（9）┐Q→┐ST（8）E

（10）┐ST（4）（8）I

23.仅用规则P和T，推证以下公式。

（1）┐A∨B，C→┐B⇒A→┐C

（2）A→（B→C），（C∧D）→E，┐F→（D∧┐E）⇒A→（B→F）

（3）A∨B→C∧D，D∨E→F，⇒A→F

（4）A→（B∧C），┐B∨D，（E→┐F）→┐D，B→（A∧┐E）⇒B→E

（5）（A→B）∧（C→D），（B→E）∧（D→F），

展开阅读全文