离散数学 第四讲

北京邮电大学版权所有

1.6 推理理论

1.6.1 推理的基本概念

推理——从前提推出结论的思维过程。

前提——已知的命题公式。

结论——从前提出发运用推理规则推出的命题公式。定义1.24若A和B是两个命题公式，当且仅当A →B为永真式，即A B，称B为A的有效结论，或称B可由A逻辑地推出。

上述定义可以推广到n个前提的情形：

当且仅当(A1 ∧A2, ∧…∧An) →B为永真式，则称B是一组前提A1 ,A2, ,…,An的有效结论。

北京邮电大学版权所有

1.6 推理理论

例有一逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可以任意开启一门。为协助脱险，今加派两名战士负责解答你所提的任何问题。惟可虑者，此两名战士一名天性诚实，一名说谎成性，今后生死由你自己选择。”逻辑学家沉思片刻，即向一战士发问，然后开门从容离去。请问，该逻辑学家应如何发问？

设计问题：“这扇门是死亡门，他（意指另一名战士）将回答‘是’，对吗？”

北京邮电大学版权所有

1.6 推理理论

（1）分析：

若被问者回答“对”，且若他是诚实的，则说明“这扇门是死亡门，那个不诚实的战士将回答‘是’”这个命题为真，因此这扇门是自由门；若他是不诚实的，则说明“这扇门是死亡门，那个诚实的战士将回答‘是’”这个命题为假，因此这扇门仍然是自由门。

若被问者回答“不对”，且若他是诚实的，则说明“这扇门是死亡门，那个不诚实的战士将回答‘是’”这个命题为假，因此这扇门是死亡门；且若他是不诚实的，则说明“这扇门是死亡门，那个诚实的战士将回答‘是’”这个命题为真，因此这扇门仍然是死亡门。

北京邮电大学版权所有

1.6推理理论

设： p:被问战士回答“是”; q:被问战士是诚实的； r:另一战士回答“是”; s:这扇门是死亡门。 (2)真值表法：见右表

p 0 0 1 1

q 0 1 0 1

r 1 0 0 1

s 1 1 0 0

(3)等值演算法 r p q s (¬p∧ q)∨ (¬p∧¬q) ¬p∧ (q∨¬q) ¬p2006-3-9电子工程学院，离散数学 4

北京邮电大学版权所有

1.6 推理理论

例1.19判断下列各推理是否正确：

（1）如果天气凉快，小王就不去游泳。天气凉快，所以小王就没去游泳。

解：符号化，设：

p：天气凉快；q：小王就不去游泳

前提：p →¬q，p 结论：¬q

形式结构：((p →¬q)∧p) →¬q是否为永真式?

9真值表法

9等值演算法

9主析取范式法

北京邮电大学版权所有

1.6 推理理论

1.6.2构造证明法

人们在研究推理过程中，发现一些重要的永真蕴涵式，我们把这些永真蕴涵式称为推理定律，下面我们给出这些推理定律。

北京邮电大学版权所有

1.6 推理理论

附加：A A ∨B

化简：A ∧B A

假言推理：(A →B) ∧A B

拒取式：(A →B) ∧¬B ¬A

析取三段论：(A ∨B) ∧¬B A

假言三段论：(A →B) ∧(B →C) A →C

等价三段论：(A B) ∧(B C) A C

构造性二难：(A →B) ∧(C→D) ∧(A ∨C)

∨DB

北京邮电大学版权所有

1.6 推理理论

常用的推理规则：

前提引入：任何步骤，均可以引入前提。

结论引入：任何步骤，所证明的结论都可作为后续证明的前提。置换：在任何步骤，命题公式中的任何子命题公式都可以用与之等值的命题公式置换。如：可用¬p∨q置换p →q

假言推理：A →B，A B

附加：A A ∨B

化简：A ∧B A

拒取式：A →B，¬B ¬A

析取三段论：A ∨B，¬B A

假言三段论：A →B，B →C A →C

构造性二难：A →B，C→D，A ∨C B ∨D

合取引入：A，B A ∧B

北京邮电大学版权所有

1.6 推理理论

举例说明构造证明法的运用

例1.20若数a是实数，则它不是有理数就是无理数。若a不能表示成分数，则它不是有理数。a是实数且它不能表示成分数，所以a是无理数。

解：首先将简单命题符号化：

p：a是实数；q：a是有理数；

r：a是无理数；

结论：r

s：a能表示成分数。前提：p →q ∨r，¬s→¬q，p ∧¬s

北京邮电大学版权所有

1.6 推理理论

前提：p →q ∨r，¬s→¬q，p ∧¬s

结论：r

证明：①p∧¬s前提引入

②p①化简

③¬s①化简

④p→q∨r前提引入

⑤q ∨r②④假言推理

⑥¬s→¬q前提引入

⑦¬q③⑥假言推理

⑧r⑤⑦析取三段论

北京邮电大学版权所有

1.6 推理理论

在构造证明时，采用一些技巧会带来许多方便，通常的技巧是：9附加前提证明法

若推理结构具有形式：

(A1 ∧A2, ∧…∧An) →(A →B) （*）

（*）中的结论也为蕴涵式，则可加工结论中的前件作为推理的前提，即：

(A1 ∧A2, ∧…∧An) →(A →B)

¬(A1 ∧A2, ∧…∧An) ∨(¬A ∨B)

(¬(A1 ∧A2, ∧…∧An) ∨¬A) ∨B

¬(A1 ∧A2, ∧…∧An ∧A) ∨B

(A1 ∧A2, ∧…∧An ∧A) →B

称A为附加前提，称此证明方法为附加前提证明法。

北京邮电大学版权所有

1.6 推理理论

例1.21用附加前提法证明下列推理：

前提：(p∧q) →r，¬s∨p，q

结论：

证明：

s →r①s附加前提引入②¬s∨p前提引入③p①②析取三段论④q前提引入⑤p∧q③④合取⑥(p∧q) →r前提引入⑦r⑤⑥假言推理

北京邮电大学版权所有

1.6 推理理论

9归谬法

若推理结构具有形式：(A1 ∧A2, ∧…∧An) →B（ ）若将¬B也作为前提能推出矛盾，比如说得出A ∧¬A，则说明（**）中的蕴涵式为永真式。即：

(A1 ∧A2, ∧…∧An) →B

¬(A1 ∧A2, ∧…∧An) ∨B

¬(A1 ∧A2, ∧…∧An∧¬B)

即：(A1 ∧A2, ∧…∧An∧¬B)为永假式正好与（**）为永真式等价，即：(A1 ∧A2, ∧…∧An) B

称此证明方法为归谬法。

北京邮电大学版权所有

例1.22 用归谬法证明下列推理：

前提：(p ∧q) →r，¬r∨s，p，¬s

结论：¬q

证明：

①q 结论的否定引入②¬r∨s前提引入③¬s前提引入④¬r②③析取三段论⑤(p∧q) →r前提引入⑥¬(p∧q)④⑤拒取式⑦¬p∨¬q⑥置换⑧p前提引入⑨¬q⑦⑧析取三段论⑩q∧¬q①⑨合取

北京邮电大学版权所有

题例分析（自学）1.7

北京邮电大学版权所有

第一章命题逻辑（小结）

¾了解命题和9个连结词的概念，深刻理解其中5个连结词，熟练掌握将复合命题符号化的方法。

¾理解公式，成真、成假赋值，及公式的类型等概念，熟练掌握利用真值表判断公式类型的方法。

¾理解等值式的概念，掌握置换定理和全功能集、极小全功能集的概念 …… 此处隐藏：1497字，全部文档内容请下载后查看。喜欢就下载吧 ……