命题逻辑的推理理论

命题逻辑的推理理论目录

第一节：推理的形式结构第二节：自然推理系统P第三章:命题逻辑的推理理论主要内容推理的形式结构推理的正确与错误推理的形式结构判断推理正确的方法推理定律自然推理系统P形式系统的定义与分类自然推理系统P在P中构造证明:直接证明法、附加前提证明法、归谬法3.1推理形式结构逻辑(语义)蕴涵：给定A1,…,Ak和B符号：{A1,…,Ak}⊨B对任意赋值v:如果v(Ai)=T,则v(B)=T或者存在Ai使得v(Ai)=F称由前提A1,…,Ak推出结论B的推理是有效的B为有效结论讨论蕴涵跟蕴涵式的关系？注意:推理正确不能保证结论一定正确例子{p,p

q}⊨q{p,q

p}⊨qpqp(p

q)qp(q

p)qFFFFFFFTFTFTTFFFTFTTTTTT3.1推理形式结构定理：{A1,…,Ak}⊨B当且仅当

A1

…

Ak

B

为重言式证明必要性：任意v,v(Ai)=T则v(B)=T

所以v(A1

…

Ak

B)=T

充分性：任意v,v(A1

…

Ak

B)=T如果v(Ai)=T则v(B)=T3.1推理形式结构蕴涵元符号：

A1

…

Ak

B代表{A1,…,Ak}⊨B推理形式结构前提A1,…,Ak结论：B3.1推理形式结构判断推理是否正确方法真值表法等值演算法主析取范式法3.1推理形式结构9推理实例例1

判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所以,明天是5号.(2)若今天是1号，则明天是5号.明天是5号.所以,今天是1号.解设p：今天是1号，q：明天是5号.(1)推理的形式结构:(p

q)

p

q用等值演算法

(p

q)

p

q

((

p

q)

p)

q

p

q

q

1

由定理3.1可知推理正确10推理实例(2)推理的形式结构:(p

q)

q

p

用主析取范式法

(p

q)

q

p

(

p

q)

q

p

((

p

q)

q)

p

q

p

(

p

q)

(p

q)

(p

q)

(p

q)

m0

m2

m3

结果不含m1,故01是成假赋值，所以推理不正确推理定律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)

(B

D)(A

B)

(

A

B)

B(A

B)

(C

D)

(

B

D)

(

A

C)附加律破坏性二难构造性二难（特殊形式）构造性二难等价三段论假言三段论析取三段论拒取式假言推理化简律3.1推理形式结构推理定律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)

(B

D)(A

B)

(

A

B)

B(A

B)

(C

D)

(

B

D)

(

A

C)附加律破坏性二难构造性二难（特殊形式）构造性二难等价三段论假言三段论析取三段论拒取式假言推理化简律3.1推理形式结构证明：(AB)

(BC)

(AC)

((AB)

(BC))

(AC)((AB)

(BC))

(AC)((AB)

(BC))

(AC)((AB)

(BC))

(AC)((AB)

(BC))

(AC)((AB)

A)

((BC)C))(B

A)

(BC)T3.1推理形式结构3.2自然推理系统P从一组已知为真的事实出发，直接运用经典逻辑推理规则推出结论的过程为什么要自然演绎(naturaldeduction)？给出验证的推理过程需要引入证明的概念自然演绎模拟人类的推理A1

…

Ak

B3.2自然推理系统P定义3.2

一个形式系统I由下面四个部分组成：

(1)非空的字母表，记作A(I).(2)A(I)中符号构造的合式公式集，记作E(I).(3)E(I)中一些特殊的公式组成的公理集，记作AX(I).(4)推理规则集，记作R(I).

记I=<A(I),E(I),AX(I),R(I)>,其中<A(I),E(I)>是I的形式语言系统,<AX(I),R(I)>是I的形式演算系统.自然推理系统:无公理,即AX(I)=

公理推理系统推出的结论是系统中的重言式,称作定理感兴趣的可以阅读《GEB－－一条永恒的金带》有一位理发师声称，他给所有不给自己理发的人理发爱皮梅尼特是一个克里特岛人。他说：“所有的克里特岛人都撤谎。”第一类集合不能以自己为元素，也就是说自己不能属于自己，我们称为r型。第二类集合可以以自己为元素，我们称为s型。证明《数学原理》所定义的系统既是一致的(无矛盾)又是完备的(该系统的理论框架中容纳了每个正确的数论命题)。这就是数学史上著名的希尔伯特纲领。自然推理系统P定义3.3自然推理系统P定义如下:1.字母表

(1)命题变项符号：p,q,r,…,pi,qi,ri,…(2)联结词符号：

,

,

,

,

(3)括号与逗号：(,),，2.合式公式（同定义1.6）3.推理规则

(1)前提引入规则

(2)结论引入规则

(3)置换规则3.2自然推理系统P假言推理规则

A

B

A

结论：B(A

B)

A

BAllmenaremortalSocratesisaman

ThereforeSocratesismortal3.2自然推理系统P附加规则

A

结论：A

BA

(A

B)3.2自然推理系统P化简规则

A

B

结论：A合取引入规则A

B

结论：A

B(A

B)

A3.2自然推理系统P证明p,q,p

q

r⊨r

p

q

p

qp

q

rr推理过程可以写成证明树3.2自然推理系统P拒取式规则

A

B

B

结论：A假言三段式规则A

B

B

C

结论：A

C(A

B)

B

A(A

B)

(B

C)

(A

C)

3.2自然推理系统P析取三段式规则

A

B

B

结论：A构造二难推理规则A

B

C

DA

C

结论：B

D(A

B)

B

A(A

B)

(C

D)

(A

C)

(B

D)3.2自然推理系统P破坏性二难推理规则

A

B

C

D

B

D

结论：

A

C

(A

B)

(C

D)

(

B

D)

(

A

C)3.2自然推理系统P形式推演(语法蕴涵)：给定A1,…,Ak和B符号：{A1,…,Ak}⊢B存在公式序列C1,C2,…,Cn，对每个i(i=1,…,n),Ci是某个Aj或者Ci是有序列中前面的公式应用推理规则得到Cn=B称C1,…,Cn是有A1,…,Ak推B的证明

3.2自然推理系统P例：考虑下述论证如果这里有球赛，则通行是困难的如果他们按时到达，则通行是不困难的他们按时到达了所以这里没有球赛设p:这里有球赛q:通行是困难的r:他们按时到达p

q

r

qr

p

3.2自然推理系统P证明前提：p

q，r

q，r结论：

p

解：

r

r

q

q

p

q

p前提引入前提引入假言推理前提引入拒取式3.2自然推理系统P证明c

d,c

r,d

s

⊢r

s

解：

c

d

c

d

d

s

c

s

c

r

r

c

r

s

r

s前提引入前提引入假言三段论前提引入置换规则置换规则假言三段论置换规则3.2自然推理系统P构造证明的方法附加前提证明法归谬法

3.2自然推理系统P附加前提证明法对形如(A1…Ak)(A

B)的证明

为什么呢？

转化为：

A1,…,Ak,A⊢B3.2自然推理系统P证明((p

(q

s))

(¬r

p)

q)

(r

s)

解：

r

¬r

p

r

p

p

p

(q

s)

q

s

q

s前提引入前提引入假言推理前提引入置换规则假言推理假言推理前提引入练习P53,14(6)P5415(2)3.2自然推理系统P归谬法对形如(A1…Ak)

B的证明

转化为：

A1…Ak

B为矛盾式3.2自然推理系统P证明

((r¬q)

(r∨s)

(s

q)

(p

q))

p解：

p

p

q

q

s

q

q

s

s

r∨s

r

r¬q¬qP5416(2)第三章习题课主要内容推理的形式结构判断推理是否正确的方法真值表法等值演算法主析取范式法推理定律自然推理系统P构造推理证明的方法直接证明法附加前提证明法归谬法(反证法)基本要求理解并记住推理形式结构的两种形式：

1.(A1

A2

…

Ak)

B2.前提：A1,A2,…,Ak

结论：B熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）牢记P系统中各条推理规则熟练掌握构造证明的直接证明法、附加前提证明法和归谬法会解决实际中的简单推理问题练习1：判断推理是否正确1.判断下面推理是否正确:(1)前提：

p

q,

q

结论：

p解推理的形式结构:(

p

q)

q

p方法一：等值演算法

(

p

q)

q

p

((p

q)

q)

p

(

p

q)

q

p

((

p

q)

(

q

q))

p

p

q易知10是成假赋值，不是重言式，所以推理不正确.练习1解答方法二：主析取范式法，

(

p

q)

q

p((p

q)q)p

p

q

M2

m0

m1

m3未含m2,不是重言式,推理不正确.练习1解答方法三真值表法

不是重言式,推理不正确111001110100(

p

q)

q

pqp

p

q0111(p

q)

q0010方法四直接观察出10是成假赋值练习1解答用等值演算法

(q

r)

(p

r)(q

p)(q

r)(p

r)(q

p)

((q

r)(p

r))(q

p)

((q

p)(q

r)(r

p))(q

p)((q

p)(q

r)(r

p))(q

p)1推理正确(2)前提：q

r,p

r

结论：q

p

解推理的形式结构：(q

r)

(p

r)(q

p)练习2：构造证明2.在系统P中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩.如果颐和园游人太多，就不去颐和园.今天是周六，并且颐和园游人太多.所以,我们去圆明园或动物园玩.证明：

(1)设p：今天是周六，q：到颐和园玩，

r：到圆明园玩，s：颐和园游人太多

t：到动物园玩

(2)前提：p

(q

r),s

q,p,s

结论：r

t练习2解答(3)证明：①p

(q

r)前提引入②p