第二章命题推理(离散数学)

1/66上堂课的内容、重点与难点合(析)取式与成真(假)解释求解范式、主范式等价公式的熟练运用等价变换法、解释法、真值表法的灵活运用联结词的完备集合合取式、析取式合取范式、析取范式极小项、极大项主合取范式、主析取范式2/66逻辑推理

演绎推理（数学家使用）归纳推理（科学家使用）溯因推理（侦探使用）从真的前提出发，得到的结论只能够要求它与前提是协调的，但不一定是真的。从前提出发，通过推导即“演绎”，得出结论的过程。前提和结论之间有可推导性关系：前提的真蕴涵结论的真。生成假设来解释观察或结论。3/66例判断下面两个推理是否正确:(1)

如果今天是星期二,今天有数学课。

今天是星期二，

所以今天有数学课。

(2)如果今天是星期二,今天有数学课。今天不是星期二，

所以今天没有数学课。第二章命题演算的推理理论4/66推理是否正确？记：P表示今天是星期二，

Q表示今天有数学课。(1)

如果今天是星期二,今天有数学课。今天是星期二，所以今天有数学课。((PQ)P)Q(2)如果今天是星期二,今天有数学课。今天不是星期二，所以今天没有数学课。

((PQ)P)Q5/66从真值表看推理是否正确：PQ((PQ)P)Q

((PQ)P)QTT

TTTF

TTFT

TFFF

TT永真公式三段论非永真6/66有效推理若有重言式则称由前提A1，…，

An

推出结论B的

推理有效，并称B是A1，A2，

…，

An

的逻辑结论，记为：A1，A2，

…，

An┣B或

A1，A2，

…，

An

B重言式——推理规则(A1A2…An)B7/66三段论

PQ大前提

P小前提

Q结论三段论推理的有效性由永真公式：((PQ)P)Q所保证。已知的一般原理对特殊情况作出判断所研究的特殊情况

8/66前提和结论间具有可推导性的形式关系大前提：如果1+1=3，则雪是黑的。小前提：1+1=3。结论：雪是黑的。该推理过程正确,但不意味着前提与结论正确9/669/70莫绍揆教授（1917.8-2011.4）1939年毕业于中央大学教学系1948年，瑞士苏黎世高级工业大学留学，师从希尔伯特的继承人贝尔奈斯1950年4月回国，任职南京大学，创建数理逻辑专业数理逻辑教育和研究的开拓者之一。编著有：《数理逻辑导论》《递归数论》《递归论》《算法论》10/6610/70公理化演绎推理归结推理离散数学北京大学耿素云前提引入规则结论引入规则置换规则8条推理定律离散数学及其应用北京大学屈婉玲前提引入规则结论引入规则置换规则

9条推理定律,24个等值式离散数学解放军通信工程学院方世昌9条推理规则离散数学朱怀宏，南京大学出版社前提引入规则（P规则）结论引入规则（T规则）置换规则,11个重言式,22个等价公式关于推理理论的学习11/6611/70公理化演绎推理归结推理离散数学导论南京大学徐洁磐✔应用公理系统✔自动定理证明✔离散数学基础教程南京大学徐洁磐等式推理蕴涵推理离散数学及其在计算机中的应用南京大学徐洁磐✔推理定理✔离散数学导论解放军理工大学王元元3条公理模式分离规则自然推理系统✔消解原理✔离散数学南京理工大学朱保平15条公理代入规则,分离规则✔✔关于推理理论的学习12/662.1命题演算的公理系统给出若干条永真公式(称为公理)，再给出若干条由永真公式推出永真公式的推理规则，由它们出发推出一切永真公式。要求：了解公理系统的构成规则和推理形式。13/66

公理系统的组成部分一、语法部分

㈠基本符号

公理系统所允许出现的全体符号的集合

㈡

公理

㈢

规则

二、语义部分14/66㈠基本符号

命题变元P，Q，R，……

联结词,,,,

括号(，)

合式公式

推出符┣

15/66㈡公理公理1PP公理2(P(QR))(Q(PR))公理3(PQ)((QR)(PR))公理4(P(PQ))(PQ)公理5(PQ)(PQ)公理6(PQ)(QP)公理7(PQ)((QP)(PQ))调头传递凝缩与有关16/66㈡公理公理8(PQ)P公理9(PQ)Q公理10P(Q(PQ))公理11P(PQ)公理12Q(PQ)公理13(PR)((QR)((PQ)R))公理14(PQ)(QP)公理15PP与∧有关与∨有关与有关17/66㈢规则(1)代入规则：将公式中出现的某一符号B每处均代以某一公式C，所到的公式D称为C对的代入。(2)分离规则：如果AB，且A，则B。MP规则18/66二、语义部分(1)公理是永真公式。规则规定如何从永真公式推出永真公式。分离规则指明:如果AB永真且A永真，则B也为永真公式。(3)代入规则指明如果为永真公式，则某一个公式正确代入公式后所得的公式也为永真公式。(4)定理为永真公式。19/66公理系统的推理过程定义如果能够作出一系列合式公式序列

A1，A2,A3,…，An，它们满足下列性质：诸Ai或为公理/定理之一(可以使用代入规则)；或由前面的Ag、Ah利用分离规则而得；(3)An=B。称序列A1，A2,…，An为B的永真证明过程。├B20/66公理推理证明的方法构造合式公式序列

A1，A2,A3,…，An=B，把待证明的公式结论变成永真蕴涵式的后件，再证明前件永真，最后利用分离规则得到结论。├B21/66定理1(p20)

├

PP证明：(1)(PQ)(QP)公理14(2)(PP)(PP)P用P，Q用P代入(3)PP

公理1(4)PP

P用P代入(5)PP

(2)(4)分离P=P✘22/66定理1的推论├

PP证明：(1)PP公理15(2)PP定理1(3)(PQ)((QP)(PQ))公理7

(4)(PP)((PP)(PP))

代入(3)

(5)(PP)(PP)(2)(4)分离(6)PP(1)(5)分离23/66定理2(p18)

├

(PQ)((RP)(RQ))

分析：由传递公理3知道(RP)((PQ)(RQ))与要求证的公式的联系是两个前件次序换一换，就可以用调头公理2：(P(QR))(Q(PR))

加头公式24/66定理3(p18,拒取式)

├(PQ)(QP)

分析：由公理14，(PQ)(QP)，可以得到(PQ)(QP)

如果(PQ)(PQ)，则由传递性知道结论成立。

25/66例：

├(PQ)(PQ)证明：

(PQ)((RP)(RQ))加头定理2(2)(QQ)((PQ)(PQ))

P用Q代入，Q用Q代入，R用P代入(3)PP

定理1(4)QQ

P用Q代入(5)(PQ)(PQ)

(6)(2)分离26/66

定理4

├

P((PQ)Q)

证明：(1)(P(QR))(Q(PR))公理2(2)((PQ)(PQ))(P((PQ)Q))

Q用P代入，R用Q代入，P用PQ代入

(3)PP公理1(4)

(PQ)(PQ)代入(5)P((PQ)Q)分离(2)(4)27/66例1已知公理：A:(Q

R)((PQ)(PR))B:(PP)PC:Q(PQ)及分离规则和代入规则试证明PP

为定理28/66例1的证明(1)(Q

R)((PQ)(PR))公理A(2)(P∨P)P公理B(3)Q(PQ)公理C(4)(QP)((PQ)(PP))R用P代入(5)((P∨P)P)((P(P∨P))(PP))

(4)式中Q用P∨P(6)(P(P∨P))(PP)(2)(5)分离(7)P(P∨P)(3)式中Q用P代入(8)PP(6)(7)分离29/66例2已知公理A:(P(QR))((PQ)(PR))B:P(QP)C:(PQ)(QP)及分离规则和代入规则，试证明PP

为定理。30/66(1)(P(QR))((PQ)(PR))(2)P(QP)(3)(PQ)(QP)(4)(P(QP))((PQ)(PP))代入(1)(5)(PQ)(PP)(2)(4)分离(6)(P(QP))(PP)代入(5)(7)PP(2)(5)分离(8)PP代入(8)(9)(PP)(PP)代入(3)(10)

PP

(8)(9)分离例2的证明:31/662.2若干重要的导出规则2.2.1关于分离规则的讨论从分离规则出发，由永真公式(a)，导出分(a)规则。永真公式(a)分(a)分分(a)分分分(a)├()├,├

(())├

(),├

,,├32/66

2.2.2关于公理和定理的导出规则每一个永真公式(公理与定理)都可以导出一条推理规则。公理2P(QR)├

Q(PR)调头规则公理3PQ，QR├

PR传递规则公理7PQ，QP├PQ充要规则公理8PQ├P化简规则公理10P，Q├PQ合取规则33/66重要的导出规则公理13PR，QR├(PQ)R析取规则定理2PQ

├

(RP)(RQ)加头规则公理14PQ├QP逆否规则拒取规则PQ，Q├

P定理3PQ├

QPPQ，Q├P34/66假言三段论（传递三段论）

P

Q

前提

Q

R

前提

PR

结论推理的有效性由公理3所保证。35/66化简

P∧Q

前提

P

结论推理的有效性由公理8所保证。36/66合取

P

前提

Q前提

P∧Q

结论推理的有效性由公理10所保证。37/66拒取

P

Q

大前提

Q

小前提

P

结论推理的有效性由定理3所保证。38/66定理3├(PQ)(QP)

运用导出规则的新证明：

(PQ)(QP)公理14(2)(PQ)(QP)Q用Q代入(3)P

P定理1(4)Q

Q代入(3)(5)

(PQ)(PQ)

(4)加头(6)

(PQ)(QP)

(5)(2)传递39/66替换定理40/66定理3├(PQ)(QP)

运用替换规则的新证明：(PQ)(QP)公理14(2)(PQ)(QP)

Q用Q代入(3)P

P定理1的推论(4)Q

Q代入(3)(5)(PQ)(QP)

(4)替换(2)41/66例(p22)├(PQ)(QP)利用替换规则的新证明：(1)(PQ)(QP)公理14

(2)(PQ)(QP)代入(1)(3)P

P

定理1的推论(4)QQ

代入(3)(5)(PQ)(QP)(3)替换(2)(6)(PQ)(QP)(4)替换(5)42/662.3

假设推理系统

——自然推理系统一、扩充的推理规则二、假设推理过程三、推理定理四、假设推理证明定理的方法2.3.1假设推理系统的组成43/66一、扩充的推理规则记R：A1，A2，…，An

├B称B是由A1，A2，…，An实施规则R而得。设有重言式：(A1

A2

…

An)B

A1

前提

A2

前提……

An

前提

B

结论规则R：在假设推理系统中的重言式既可以是公理系统中的公理及定理，也可以是利用真值表法验证的等值公式。44/66肯定前提律（化简）

P∧Q

前提

P

结论推理的有效性由公理(8)所保证。一般地，

A1，A2，…，An├Ai

(i=1，2，…，n)即前提中的任何命题均可作为结论。45/66置换(替换)任何命题公式都可以用与之等值的命题公式置换。如果A=B，则A┣B例P┣

PP┣PPQ┣

P∨QP∨Q┣

PQ

在公理系统中，导出规则(包括：替换)在初学时一般不允许使用。46/66析取三段论

P∨Q

大前提

P

小前提

Q

结论推理的有效性由永真公式：((P∨Q)P)Q所保证。47/66拒取

P

Q

大前提

Q

小前提

P

结论推理的有效性由定理3所保证。48/66二、假设推理过程定义:

如果能够作出一系列合式公式序列A1，A2,A3,…，An，它们满足下列性质：(1)诸Ai或为公理/定理之一(可以使用代入规则)；(2)或为公式1,

2,

…,k之一(对假设i不能代入)；(3)或由前面的Ag、Ah利用分离规则而得；(4)An=B。称这个公式序列A1，A2,…，An为由公式1，2，…，k证明B的证明过程。1，2，…，k├B49/66三、推理定理附加前提推理定理(CP规则)

如果Γ，A├B，则Γ├AB

Γ

(AB)与(Γ∧A)

B同真假50/66附加前提推理定理如果A1，A2，…，An-1

，An，A├B，则

A1，A2，…，An-1

，An├AB进而，有下面定理：

A1，A2…，An-1├An

(AB)A1，A2，…，An-2├An-1

(An

(AB))依次类推可得定理：

├A1(A2(…(An(AB))…))51/66四、反证律如果Γ，A├B

且Γ，A├B这里B是一个公式。则有:

Γ├A。52/66五、假设推理证明定理的方法

把待证公式的前件一一列出，注明为假设或前提。按推理规则进行推理，但此时不能对假设以及演绎公式实施代入规则。(3)当推导出待证公式的后件时，就完成了该定理的证明。附加前提推理证明方法53/66反证法(1)把待证公式的前件一一列出，把待证公式的后件的否定列出，注明为假设或前提。(2)按推理规则进行推理，但此时不能对假设以及演绎公式实施代入规则。(3)当推导出两个矛盾的结论时，就完成了该定理的证明。54/66例1：求证├

(P(QR))((PQ)R)证明(1)P(QR)假设

(2)PQ假设

(3)(PQ)P公理8(4)(PQ)Q公理9(5)P(3)(2)分离

(6)Q(4)(2)分离

(7)QR(1)(5)分离

(8)R(6)(7)分离55/66例1：求证├

(P(QR))((PQ)R)证明:(1)P(QR)假设

(2)PQ假设

(3)P(2)化简

(4)Q(2)化简

(5)QR(1)(3)分离

(6)R(4)(5)分离(4)R

在(3)中用R代入P有错吗?不能对(3)实施代入规则!!!56/66例3(p25)求证：├

(PP)P证明：(1)

PP

假设

(2)

P

假设，结论的否定

(3)

P

(1)(2)分离显然，(2)与(3)矛盾。

由反证法，

结论得证。57/66定理(PR)((QR)(PQ))证明:(1)PR假设(2)QR假设(3)P假设(4)R(1)(3)分离(5)

Q(2)(4)拒取规则

即证得:PR,QR,P├Q由推理定理,原公式得证58/66例├((SQ)(PQ)S)P证明:（直接证明，不采用反证律）

(1)

(SQ)(PQ)S

假设

(2)S→Q

(1)化简

(3)P→Q(1)化简

(4)S(1)化简

(5)

Q(2)(4)分离

(6)

P

(3)(5)拒取

59/66例├((SQ)(PQ)S)P解:(1)

(SQ)(PQ)S假设(2)S→Q

(1)化简

(3)P→Q(1)化简

(4)S(1)化简

(5)

P

假设,结论的否定(置换)

(6)

Q(2)(4)分离

(7)Q(3)(5)分离显然，(6)与(7)矛盾。由反证法，公式得证。60/66例构造下面的假设推理证明前提：p∨q,r∨q,r→s结论：p→s证明：p∨q

假设

r∨q

假设(3)r→s

假设p附加假设q(1)(4)析取三段论r(2)(5)析取三段论s(3)(6)分离61/66半反证法、穷举法若A1，A2，…，An,β├B,A1，A2，…，An,├B,则A1，A2，…，An,β∨├B若A1，A2，…，An,β├

,则A1，A2，…，An

├

β∨62/66例

写出对应下面的假设推理证明解：记p：今天是星期天

q：去中山陵r：去玄武湖

s：中山陵游玩的人多

前提：p→(q∨r),s→q,p,s

结论：r如果今天是星期天,则小组就到中山陵或玄武湖去游玩。如果中山陵游玩的人多，小组就不去中山陵游玩。今天是星期天，中山陵游玩的人多，所以小组去玄武湖。

例4的证明：p→(q∨r)

假设s→q假设p假设s假设(5)

q∨r

(1)(3)分离q(2)(4)分离r(5)(6)析取三段论(7’)q→r等值(5)(8’)r

6)(7’)分离例

构造下面推理的证明：

若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解

设p：明天是星期一，q：明天是星期三，

r：我有课，s：我备课形式结构为前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

64直接证明法(续)证明①r®s

前提引入②Øs

前提引入③Ør①②拒取式④(pÚq)®r

前提引入⑤Ø(pÚq)③④拒取式

⑥ØpÙØq⑤置换65前提：(pÚq)®r,r®s,Øs结论：ØpÙØq

66例

找出下列推理的有效结论。如果我考试通过了，那么我很快乐。如果我快乐，那么阳光灿烂。现在阳光不灿烂且天很暖。因此我考试没通过。解设p：我考试通过了，q：我很快乐，r：阳光灿烂，s：天很暖。前提：p→q，q→r，ØrÙ

s

结论：p67前提：p→q，q→r，ØrÙ

s结论：p（1）p→q前提引入（2）q→r前提引入（3）p→r（1）（2）假言三段论（4）

r∧s前提引入（5）

r（4）化简（6）p（5）（3）拒取式所以有效结论是：我考试没通过。68例3证明Ｒ∨Ｓ是前题Ｃ∨Ｄ，Ｃ→Ｒ，Ｄ→Ｓ的有效结论，即证明：

(C∨D)∧(C→R)∧(D→S)(R∨S)。

证明：①C∨D前提引入②C→D置换③D→S前提引入④C→S②③⑤C→R前提⑥R→C⑤⑦R→S④⑥

⑧R∨S置换69例构造下面推理的证明:2是素数或合数.若2是素数，则是无理数.

若是无理数，则4不是素数.

所以，如果4是素数，则2是合数.

用附加前提证明法构造证明解设p：2是素数，q：2是合数，

r：是无理数，s：4是素数形式结构前提：pÚq,p®r,r®Øs

结论：s®q70证明①s

附加前提引入②p®r

前提引入③r®Øs

前提引入④p®Øs②③假言三段论⑤Øp①④拒取式⑥pÚq

前提引入⑦q⑤⑥析取三段论前提：pÚq,p®r,r®Øs结论：s®q71例构造下面推理的证明前提：Ø(pÙq)Úr,r®s,Øs,p

结论：Øq证明（用归缪法）①q

结论否定引入⑩ØpÙp

⑧⑨合取②r®s

前提引入③Øs

前提引入④Ør②③拒取式⑤Ø(pÙq)Úr

前提引入

⑥Ø(pÙq)④⑤析取三段论

⑦ØpÚØq

⑥置换

⑧Øp

①⑦析取三段论

⑨p

前提引入证：①A→B前提

②A

否定结论

③B①②

④

(B∨C)前提

⑤B∧C③置换

⑥B④

⑦B∧B（矛盾）

72练习1

证明

(B∨C)∧(A→B)A

6、课内练习证：⑴(A→C)否定结论

⑵A∧C1置换⑶A2化简⑷C2化简⑸A∨B前提⑹B3、5⑺C→B前提⑻B4、7

⑼B∧B(矛盾)6、873练习2证明

A∨B，C→BA→C

74练习2证明

A∨B，C→BA→C

证:(1)

A附加前提引入(2)

A∨B前提(3)B1、2(4)C→B前提(5)C3、4

75/66已知公理

A:(PQ)P

B:(PQ)Q

C:P(Q(PQ))

及分离规则和代入规则，试用假设推理证明下面公式为本系统的定理:

(PR)(((QS)(PQ))(SR))

例(10级期末试题,6分)证：（1）PR

假设

（2）(QS)(PQ)假设

（3）((QS)(PQ))(QS)

公理（A）代入

（4）((QS)(PQ))(PQ)公理（B）代入