命题逻辑的推理理论

第1页，课件共35页，创作于2023年2月数理逻辑的主要任务是用数学的方法来研究数学中的推理。推理是指从前提出发推出结论的思维过程。前提是已知命题公式集合。结论是从前提出发应用推理规则推出的命题公式。证明是描述推理正确或错误的过程。要研究推理，首先应该明确什么样的推理是有效的或正确的。第2页，课件共35页，创作于2023年2月定义1.24

设A1,A2,…,Ak和B都是命题公式，若对于A1,A2,…,Ak和B中出现的命题变项的任意一组赋值，

（1）或者A1∧A2∧…∧Ak为假;

（2）或者当A1∧A2∧…∧Ak为真时，B也为真;

则称由前提A1,A2,…,Ak推出B的推理是有效的或正确的，并称B是有效结论。有效推理的定义即：（A1∧A2∧…∧Ak）→B为重言式第3页，课件共35页，创作于2023年2月关于有效推理的说明＝{A1，A2，…，Ak}

由推B的推理记为┣B

若推理是正确的，记为

╞

B

若推理是不正确的，记为

B由前提A1，A2，…，Ak推结论B的推理是否正确与诸前提的排列次序无关。第4页，课件共35页，创作于2023年2月设A1，A2，…，Ak，B中共出现n个命题变项，对于任何一组赋值α1α2…αn(αi=0或者1，i=1,2,…,n)，前提和结论的取值情况有以下四种：

(1)A1∧A2∧…∧Ak为0，B为0。

(2)A1∧A2∧…∧Ak为0，B为1。

(3)A1∧A2∧…∧Ak为1，B为0。

(4)A1∧A2∧…∧Ak为1，B为1。只要不出现(3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现(3)中的情况。推理正确，并不能保证结论B一定为真。

第5页，课件共35页，创作于2023年2月

(1){p,p→q}├q

(2){p,q→p}├q

例1

判断下列推理是否正确。（真值表法）pqp(p→q)qp(q→p)q000000010101100010111111正确不正确第6页，课件共35页，创作于2023年2月当推理正确时，形式（1）记为╞

B。形式（2）记为A1A2…AkB。

表示蕴涵式为重言式。

={A1,A2,…,Ak}，记为┣B。

A1A2…AkB前提：A1,A2,…,Ak

结论：B说明推理的形式结构第7页，课件共35页，创作于2023年2月

真值表法等值演算法主析取范式法判断推理是否正确的方法是否有其他的证明方法？思考当命题变项较少时,这三种方法比较方便。说明第8页，课件共35页，创作于2023年2月

下午马芳或去看电影或去游泳。她没去看电影，所以，她

去游泳了。例2

判断下列推理是否正确。（等值演算法）

解：设p:马芳下午去看电影，q:马芳下午去游泳。 前提：p∨q，┐p

结论：q

推理的形式结构：((p∨q)∧┐p)→q((p∨q)∧┐p)→q

┐((p∨q)∧┐p)∨q((┐p∧┐q)∨p)∨q((┐p∨p

)∧(┐q∨p))∨

q(┐q∨p)∨

q

1例题第9页，课件共35页，创作于2023年2月(1)A(A∨B)

附加律(2)(A∧B)A

化简律(3)

(A→B)∧AB

假言推理(4)(A→B)∧┐B┐A

拒取式(5)(A∨B)∧┐BA

析取三段论(6)

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

假言三段论(7)

(AB)∧(BC)(AC) 等价三段论(8)

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

构造性二难(9)(A→B)∧(C→D)∧(┐B∨┐D)(┐A∨┐C)破坏性二难

推理定律--重言蕴含式第10页，课件共35页，创作于2023年2月关于推理定律的几点说明A,B,C为元语言符号，代表任意的命题公式。若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。1.3节给出的24个等值式中的每一个都派生出两条推理定律。例如双重否定律A

A产生两条推理定律A

A和

AA。由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则。第11页，课件共35页，创作于2023年2月构造性证明方法判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。当推理中包含的命题变项较多时，上述三种方法演算量太大。对于由前提A1,A2,…,Ak推B的正确推理应该给出严谨的证明。证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。第12页，课件共35页，创作于2023年2月常用的推理规则（1）前提引入规则：在证明的任何步骤上，都可以引入前提。（2）结论引入规则：在证明的任何步骤上，所证明的结论都可以作为后续证明的前提。（3）置换规则：在证明的任何步骤上，命题公式中任何子命题公式都可以用与之等价的命题公式置换。第13页，课件共35页，创作于2023年2月（4）假言推理规则

AB

A

B（5）附加规则

A

AB（6）化简规则

AB

A（4）若今天下雪,则将去滑雪。今天下雪，所以去滑雪。

（5）现在气温在冰点以下。因此，要么现在气温在冰点以下，要么现在下雨。（6）现在气温在冰点以下并且正在下雨。因此，现在气温在冰点以下。第14页，课件共35页，创作于2023年2月（7）拒取式规则

AB

B

A（8）

假言三段论规则

AB

BC

AC（9）析取三段论规则

AB

B

A第15页，课件共35页，创作于2023年2月（10）构造性二难推理规则

AB

CD

AC

BD（11）破坏性二难推理规则

AB

CD

BD

AC（12）合取引入规则

A

B

AB第16页，课件共35页，创作于2023年2月构造证明构造证明就是由一组公式作为前提，利用自然推理系统中的规则，推出结论。构造形式结构A1A2…AkB的推理的书写方法：

前提：A1,A2,…,Ak

结论：B证明方法：直接证明法附加前提法归谬法（或称反证法）第17页，课件共35页，创作于2023年2月例3.1

构造下面推理的证明：

前提：┐p∨q,r∨┐q,r→s

结论：p→s①┐p∨q

前提引入②p→q

①置换③r∨┐q

前提引入④q→r

③置换⑤p→r

②④假言三段论⑥r→s

前提引入⑦p→s

⑤⑥假言三段论

第18页，课件共35页，创作于2023年2月例题例3.2

构造下面推理的证明：

前提：p→（q→r）,p∧q

结论：┐r→s①p→（q→r）

前提引入②p∧q

前提引入③p

②化简④q

②化简⑤q→r

①③假言推理⑥r

④⑤假言推理⑦r∨s

⑥附加⑧┐r→s ⑦置换第19页，课件共35页，创作于2023年2月技巧一：附加前提证明法(A1∧A2∧…∧Ak)→(A→B)

等价于

(A1∧A2∧…∧Ak∧A)→B即原来结论中的前件变成前提了！第20页，课件共35页，创作于2023年2月例4

构造下面推理的证明。

如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。构造证明：（1）将简单命题符号化：设 p:小张去看电影。

q:小王去看电影。

r:小李去看电影。

s:小赵去看电影。

第21页，课件共35页，创作于2023年2月（2） 形式结构：

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

结论：s→r（3）证明：用附加前提证明法

①s

附加前提引入②┐s∨p

前提引入

③p

①②析取三段论④(p∧q)→r 前提引入⑤q

前提引入

⑥p∧q

③⑤合取

⑦r

④⑥假言推理

第22页，课件共35页，创作于2023年2月技巧二：归谬法(A1∧A2∧…∧Ak)→B等价于┐（A1∧A2∧…∧Ak∧┐B）因此，若A1∧A2∧…∧Ak与┐B不相容（即A1∧A2∧…∧Ak∧┐B为矛盾式，或┐（A1∧A2∧…∧Ak∧┐B）为重言式），则说明B是A1∧A2∧…∧Ak的逻辑结论。这种将┐B作为附加前提推出矛盾的证明方法成为归谬法。第23页，课件共35页，创作于2023年2月例5

构造下面推理的证明。

如果小张守第一垒并且小李向B队投球，则A队将取胜；或者A队未取胜，或者A队获得联赛第一名；A队没有获得联赛的第一名；小张守第一垒。因此，小李没有向B队投球。构造证明：（1）将简单命题符号化：设p:小张守第一垒。 q:小李向B队投球。

r:A队取胜。 s:A队获得联赛第一名。（2）形式结构：

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

结论：┐q

第24页，课件共35页，创作于2023年2月例题（3）证明：用归谬法①q

结论的否定引入②┐r∨s

前提引入③┐s

前提引入④┐r

②③析取三段论⑤(p∧q)→r 前提引人⑥┐(p∧q)

④⑤拒取式⑦┐p∨┐q

⑥置换⑧p

前提引入⑨┐q

⑦⑧析取三段论⑩q∧┐q

①⑨合取由于最后一步为矛盾式，所以推理正确。

小节结束第25页，课件共35页，创作于2023年2月本节主要内容推理的形式结构：

推理的前提

推理的结论

推理正确判断推理是否正确的方法：

真值表法

等值演算法

主析取范式法

对于正确的推理，给予构造证明:

1.常用的推理规则：

2.附加前提证明法

3.归谬法第26页，课件共35页，创作于2023年2月本章学习要求理解并记住推理的形式结构的三种等价形式，即

①{A1,A2,…,Ak}├B

②A1∧A2∧…∧Ak→B

③前提：A1,A2,…,Ak

结论：B在判断推理是否正确时，用②；在系统中构造证明时用③。

熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。

牢记各条推理规则。

对于给定的正确推理，要求在系统中给出严谨的证明序列。

会用附加前提证明法和归谬法。

第27页，课件共35页，创作于2023年2月典型例题1、用不同的方法验证下面推理是否正确。对于正确的推理还要在系统中给出证明。（1）前提：pq,q结论：p（2）

前提：qr,pr结论：qp

第28页，课件共35页，创作于2023年2月（1）不正确。验证答案，只需证明(pq)qp不是重言式。方法一等值演算(pq)qp

((pq)q)p(pq)qp((pq)(qq))p

pq易知10是成假赋值，故(pq)qp不是重言式，所以推理不正确。第29页，课件共35页，创作于2023年2月方法二主析取范式法经过演算后可知(pq)qp

m0m1m3未含m2,故(pq)qp不是重言式。方法三直接观察出10是成假赋值。第30页，课件共35页，创作于2023年2月方法四真值表法(pq)qp的真值表为pq(pq)qp001101010111结论（不正确）是对的。第31页，课件共35页，创作于2023年2月（2）推理正确方法一真值表法（自己做）方法二等值演算法（自己做）方法三主析取范式法（自己做）