离散数学(第5讲)省名师优质课赛课获奖课件市赛课一等奖课件

冯伟森Email：fws365@16九月2023离散数学计算机学院1/312023/9/16计算机学院2主要内容1、命题公式蕴涵

1）九类蕴涵关系

2）蕴涵关系基本性质2、推理基本概念和推理形式3、推理规则

1）P规则

2）T规则

3）CP规则2/312023/9/16计算机学院3§1．6

命题公式蕴涵定义1.18设A和B是两个适当公式，假如在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A

B。定理1.11

A

BiffA→B为永真式。注意：蕴涵和条件联结词→是完全不一样。→是命题联结词，A→B是一个命题公式；

是公式间关系符，A

B不是一个命题公式，仅表示A，B间蕴涵关系。3/312023/9/16计算机学院4基本蕴涵（关系）式（蕴涵定律）I1：P∧Q

P，P∧Q

Q

I2:～（P→Q）

P，～（P→Q）

～Q解释：利用P→Q真值表，P→Q不成立只有一个情况，前件即P成立；一样，P→Q不成立只有一个情况，后件即Q不成立。

I3：P

P∨Q，Q

P∨Q

I4：～P

P→Q，Q

P→Q解释：类似I1，I2，自己思索。扩充法则简化法则4/312023/9/16计算机学院5√I5：P∧（P→Q）

Q

假言推论√I6：～Q∧（P→Q）

～P拒取式（否定式假言推论）解释：类似I1，I2，自己思索。√I7：～P∧（P∨Q）

Q析取三段论√I8：（P→Q）∧（Q→R）

P→R

假言三段论解释：假如我是川大学生，则我拥有川大学籍；假如我拥有川大学籍，则我有川大学生证。所以，假如我是川大学生，则我有川大学生证。5/312023/9/16计算机学院6基本蕴涵（关系）式（续）√I9：（P∨Q）∧（P→R）∧（Q→R）

R

二难推论解释：和假言推论联络起来思索I10：（P→Q）∧（R→S）

（P∧R）→（Q∧S）√I11：（P

Q）∧（Q

R）

P

R

等价三段论√I12：（P∨Q）∧（～P∨R）

Q∨R

归结原理

[解释：（～P→Q）∧（P→R）

Q∨R]6/312023/9/16计算机学院7蕴涵关系性质①自反性A

A②反对称性:

假如A

B，B

A，

iffA

B③A

B且A为永真式，则B必为永真式7/312023/9/16计算机学院8④传递性，假如A

B，B

C，则A

C【证实】由已知条件A

B，且B

C，依据定理1.11

(A→B）∧（B→C）是永真式；再由假言三段论，应有（A→B）∧（B→C）

A→C；再依据性质3，A→C也必是永真式，即A

C。■8/312023/9/16计算机学院9⑤

如A

B，A

C，iffA

B∧C【证实】“

”由

AB

且

AC得到A

B和AC都是永真式，于是（AB）∧（AC）也是永真式；不过，（AB）∧（AC）

（～A∨B）∧(～A∨C)

～A∨(B∧C)A→(B∧C)，所以A(B∧C)是永真式，即AB∧C。9/312023/9/16计算机学院10“”从证实过程看，性质5反过来也对，即由

AB∧C能够得到AB

且

AC。

⑥如A

B，C

B，则A∨C

B⑦A∧B

CiffA

B→C

该性质是推理演绎中CP规则基础⑧

A

BiffA∧～B是矛盾式

该性质是反证法基础10/312023/9/16计算机学院11定理1.12

A

Biff

～B

～A

该定理提供了逆向思维基础11/312023/9/16计算机学院12例1-6.1考虑以下语句，并将其前提和结论符号化。1)、前提：

1.假如明天天晴，我们准备外出旅游。P→Q

2．明天确实天晴。 P结论：我们外出旅游。 Q上述例子可描述为：P→Q，P

Q(假言推论)2)、前提：1.假如一个人是单身汉，则他不幸福。P→Q2.假如一个人不幸福，则他死得早。

Q→R结论：单身汉死得早。

P→R上述例子可描述为：

P→Q，Q→R

P→R(假言三段论)12/312023/9/16计算机学院13例1-6.1(续1)3)、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，依据上述案情可得前提以下：

前提：

1.凶手为王某或陈某。

P∨Q 2.假如王某是凶手，则他在作案当晚必外出。

P→R 3.王某案发之晚并未外出。

～R结论：陈某是凶手。

Q则上述例子可描述为：

P→R，～R

～P

(拒取式)

P∨Q，～P

Q

(析取三段论)13/312023/9/16计算机学院14例1-6.1(续2)4)、前提：

1.假如某同学为省二级以上运动员，则他将被大学录用。

P→R 2.假如某同学高考总分在560分以上，则将被大学录用。

Q→R 3.某同学高考总分在560分以上或者是省二级运动员。

P∨Q 结论：该同学被大学录用。

R 则上述例子可描述为：

P∨Q，P→R，Q→R

R(二难推论)14/312023/9/16计算机学院15§1．7命题逻辑推理方法

命题演算一个主要任务在于提供一个正确思维规律，即推理规则，应用此规则从一些前提中推导出一个结论来，这种推导过程称为演绎或形式证实。定义1.19

设A1,A2,…,An,B是公式,假如

A1,A2,…,An

B则称B是A1,A2,…,An

逻辑结果（有效结论）。也能够说由A1,A2,…,An推出结论B。15/312023/9/16计算机学院16

在更普通意义上，我们有下述定义定义1.20设G是由一组命题公式组成集合，假如存在命题公式有限序列：

A1，A2，……，An（=B）其中，Ai（i<n-1）或者是G中某个公式，或者是前面一些Aj（j<i）有效结论，而且An就是B，则称公式B是G逻辑结果（有效结论），或者称由G演绎出结论B来。16/312023/9/16计算机学院17我们有下述结论：

公式B是公式集合G＝{A1,A2,…,An}逻辑结果当且仅当A1∧A2∧…∧An→B为永真公式。17/312023/9/16计算机学院18解释

1)这里需要尤其注意是：推理有效性和结论真实性是不一样，有效推理不一定产生真实结论；而产生真实结论推理过程未必是有效，因为有效推理中可能包含为“假”前提，而无效推理却可能包含为“真”前提。18/31解释2)由此可见，推理有效性是一回事，前提与结论真实是否是另一回事。所谓推理有效，指是它结论是在它前提下合乎逻辑结果。也即，假如它前提都为真，那么所得结论也必定为真，而并不是要求前提或结论一定为真或为假，假如推理是有效话，那么不可能它前提都为真时，而它结论为假。2023/9/16计算机学院1919/312023/9/16计算机学院20推理规则

在数理逻辑中，主要推理规则有：①P规则（称为前提引用规则）：在推导过程中，可随时引入前提集合中任意一个前提；②Ｔ规则（逻辑结果引用规则）：在推导过程中，利用基本等价式和蕴涵式，由证实过程中一些中间公式变换出新公式，若依据是等价式，规则标明为TE，若依据是蕴涵式，规则标明为TI。20/31推理规则③ＣＰ规则（附加前提规则）：假如能从给定前提集合G与公式P推导出S，则能从以前提集合G推导出P→S。即G1,G2,…,Gn

P→S当且仅当

G1,G2,…,Gn，P

S

2023/9/16计算机学院2121/312023/9/16计算机学院22推理方法1.真值表法

依据前提A1,A2,…,An和结论B,结构条件式（A1∧A2∧…∧An）→B真值表,若它为永真式，则结论B是有效。真值表法标准上能够处理推理有效性问题，但当出现在公式中命题变元数目很大时，此法显得不切实用，且烦琐乏味，对培养逻辑推理能力及训练推理技巧毫无帮助。22/312023/9/16计算机学院232、演绎法演绎法是从前提（假设）出发，依据公认推理规则，推导出一个结论来。

1）直接法

2）利用CP规则3、间接证实法（反证法）23/312023/9/16计算机学院24直接证实法例1-7．1

求证S∨R是前提{P∨Q，P→R，Q→S}有效结论。(结构性二难推论)证：步骤公式依据（注释）①P∨QP②～P→QT，①，E1，E2

③Q→SP④～P→ST,②,③,I9⑤～S→PT，④，E14，E23⑥P→RP⑦～S→RT，⑤，⑥，I9⑧S∨RT，⑦，E2，E1

故{P∨Q，P→R，Q→S}

S∨R24/312023/9/16计算机学院25利用CP规则例1-7．2

证实R→S能够从前提

{P→（Q→S），～R∨P，Q}推出证：①RP（附加前提）②～R∨PP③PT，①，②，I8④P→（Q→S）P⑤Q→ST，③，④，I5⑥QP⑦ST，⑥，⑤，I5

⑧R→SCP，①，⑦25/312023/9/16计算机学院26依据蕴涵关系性质8，

A

BiffA∧～B是矛盾式

将结论否定加入到前提集合中组成一组新前提，然后证实这组新前提集合是不相容，即蕴涵一个矛盾式。

即，若

A1,A2,…,An,～B

R∧～R则

A1,A2,…,An

B间接证实法（反证法）26/312023/9/16计算机学院27例1-7．3证实：{R→～Q，R∨S，S→～Q，P→Q}

～P

证：①～（～P）P（假设前提）②PT，①，E1③P→QP④QT,②,③,I5

⑤S→～QP⑥～ST，④，⑤，I23，E1，I5⑦R∨SP⑧RT，⑥，⑦，I7⑨R→～QP⑩～QT，⑧，⑨，I5

⑾Q∧～QF，④，⑩Ｅ19∴{R→～Q，R∨S，S→～Q，P→Q}

～P27/31例1-7．4把命题“假如小王不去，小张或小李就要去；假如小李去，小王就一定要去；另外，假如小林也去，小张就不愿去；所以，假如小王不去，小林也不会去”翻译成命题逻辑形式并证实命题是真。解：

令