离散数学结构 第3章 命题逻辑的推理理论.docx
- 文档编号:17506914
- 上传时间:2023-07-26
- 格式:DOCX
- 页数:27
- 大小:48.13KB
离散数学结构 第3章 命题逻辑的推理理论.docx
《离散数学结构 第3章 命题逻辑的推理理论.docx》由会员分享,可在线阅读,更多相关《离散数学结构 第3章 命题逻辑的推理理论.docx(27页珍藏版)》请在冰点文库上搜索。
离散数学结构第3章命题逻辑的推理理论
第3章命题逻辑的推理理论
3.1推理的形式结构
一、有效推理
数理逻辑的主要任务是用数学的方法来研究数学中的推理。
所谓推理是指从前提出发推出结论的思维过程,而前提是已知命题公式集合,结论是从前提出发应用推理规则推出的命题公式。
要研究推理就应该给出推理的形式结构,为此,首先应该明确什么样的推理是有效的或正确的。
定义3.1设A1,A2,…,Ak和B都是命题公式,若对于A1,A2,…,Ak和B中出现的命题变项的任意一组赋值,或者A1∧A2∧…∧Ak为假,或者当A1∧A2∧…∧Ak为真时,B也为真,则称由前提A1,A2,…,Ak推出B的推理是有效的或正确的,并称B是有效结论。
关于定义3.1还需要做以下几点说明:
1.由前提A1,A2,…,Ak推结论B的推理是否正确与诸前提的排列次序无关。
因而前提的公式不一定是序列,而是一个有限的公式集合,若将这个集合记为Г,可将由Г推B的推理记为Г├B。
若推理是正确的,则记为Г
B,否则记为Г
B。
这里,可以称Г├B和{A1,A2,…,Ak}├B为推理的形式结构。
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.1可知,只要不出现(3)中的情况,推理就是正确的,因而判断推理是否正确,就是判断是否会出现(3)中的情况。
3.由以上的讨论可知,推理正确,并不能保证结论B一定为真,这与数学中的推理是不同的。
例3.1判断下列推理是否正确:
(1){p,p→q}
q
(2){p,q→p}
q
解只要写出前提的合取式与结论的真值表,看是否出现前提合取式为真,而推论为假的情况。
(1)由表3.1可知,没有出现前提合取式为真,而结论为假的情况,因而
(1)中推理正确,即{p,p→q}
q.
(2)由表3.1可知,在赋值为10情况下,出现了前提合取式为真,而结论为假的情况,因而
(2)推理不正确,即{p,q→p}
q.
表3.1
对于本例这样简单的推理,不用写真值表也可以判断推理是否正确。
在
(1)中,当q为假时,无论p是真是假,p∧(p→q)均为假,因而不会出现前提合取式为真,结论为假的情况,因而推理正确。
而在
(2)中,当q为假,p为真时,出现了前提合取式为真,结论为假的情况,因而推理不正确。
二、有效推理的等价定理
定理3.1命题公式A1,A2,…,Ak推B的推理正确当且仅当
(A1∧A2∧…∧Ak)→B
为重言式。
证首先证明其必要性。
若A1,A2,…,Ak推B的推理正确,则对于A1,A2,…,Ak,B中所含命题变项的任意一组赋值,不会出现A1∧A2∧…∧Ak为真,而B为假的情况,因而在任何赋值下,蕴涵式(A1∧A2∧…∧Ak)→B均为真,故它为重言式。
再证明其充分性。
若蕴涵式(A1∧A2∧…∧Ak)→B为重言式,则对于任何赋值此蕴涵式均为真,因而不会出现前件为真后件为假的情况,即在任何赋值下,或者A1∧A2∧…∧Ak为假,或者A1∧A2∧…∧Ak和B同时为真,这正符合定义3.1中推理正确的定义。
由此定理知,推理形式:
前提:
A1,A2,…,Ak
结论:
B
是有效的当且仅当(A1∧A2∧…∧Ak)→B为重言式。
(A1∧A2∧…∧Ak)→B称为上述推理的形式结构。
从而推理的有效性等价于它的形式结构为永真式。
于是,推理正确
{A1,A2,…,Ak}
B
可记为
A1∧A2∧…∧Ak
B
其中
同
一样是一种元语言符号,用来表示蕴涵式为重言式。
而判断命题公式永真性有三个方法:
1.真值表法
2.等值演算法
3.主析取范式法
下面用例子说明。
例3.2判断下面推理是否正确:
(1)若a能被4整除,则a能被2整除;A能被4整除。
所以a能被2整除。
(2)若a能被4整除,则a能被2整除;A能被2整除。
所以a能被4整除。
(3)下午马芳或去看电影或去游泳;她没有看电影。
所以,她去游泳了。
(4)若下午气温超过30℃,则王小燕必去游泳;若她去游泳,她就不去看电影了。
所以王小燕没有去看电影,下午气温必超过了30℃。
解解上述类型的推理问题,首先应该将简单命题符号化。
然后分别写出前提、结论、推理的形式结构,接着进行判断。
(1)设
p:
a能被4整除。
q:
a能被2整除。
前提:
p→q,p
结论:
q
推理的形式结构:
(p→q)∧p→q (3.1)
由例3.1可知,此推理正确,即(p→q)∧p
q。
(2)设p,q的含义同
(1)。
前提:
p→q,q
结论:
p
推理的形式结构:
(p→q)∧q→p (3.2)
当然可以用真值表法、等值演算、主析取范式等方法来判断(3.2)式是否为重言式。
但在此推理中,容易看出01是(3.2)式的成假赋值,所以
(2)推理不正确。
(3)设
p:
马芳下午看电影。
q:
马芳下午去游泳。
前提:
p∨q,┐p
结论:
q
推理形式结构:
((p∨q)∧┐p)→q (3.3)
用等值演算法来判断(3.3)式是否为重言式。
((p∨q)∧p)→q
┐((p∨q)∧┐p)∨q
((┐p∧┐q)∨p)∨q
((┐p∨p)∧(┐q∨p))∨q
┐q∨p∨q
1
这说明(3.3)式为重言式,所以推理正确。
(4)设
p:
下午气温超过30℃。
q:
王小燕去游泳。
r:
王小燕去看电影。
前提:
p→q,q→┐r
结论:
┐r→p
推理的形式结构:
((p→q)∧(q→┐r))→(┐r→p) (3.4)
用主析取范式法判断(3.4)式是否为重言式。
((p→q)∧(q→┐r))→(┐r→p)
┐((┐p∨q)∧(┐q∨┐r))∨(r∨p)
((p∧┐q)∨(q∧r))∨r∨p
r∨p(用两次吸收律)
(p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨(p∧q∧r)∨(┐p∧┐q∧r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧r)
m1∨m3∨m4∨m5∨m6∨m7(重排了序)
可见(3.4)式不是重言式(主析取范式中少两个极小项m0,m2),所以推理不正确。
三、重言蕴涵式
由上一个小节可以看出:
形如A→B的重言式在推理中十分重要。
若A→B为重言式,则称B为A的推论,记为A
B,下面是几个重要的重言蕴涵式及其名称
1.A
(A∨B) 附加律
2.(A∧B)
A 化简律
3.(A→B)∧A
B 假言推理
4.(A→B)∧┐B
┐A 拒取式
5.(A∨B)∧┐B
A 析取三段论
6.(A→B)∧(B→C)
(A→C) 假言三段论
7.(A
B)∧(B
C)
(A
C) 等价三段论
8.(A→B)∧(C→D)∧(A∨C)
(B∨D) 构造性二难
(A→B)∧(┐A→B)∧(A∨┐A)
B 构造性二难(特殊形式)
9.(A→B)∧(C→D)∧(┐B∨┐D)
(┐A∨┐C) 破坏性二难
这几个蕴涵式在下节中将起重要的作用。
3.2自然推理系统P
一、形式推理系统
我们将前述推理用更严谨的形式推理系统描述出来。
定义3.2一个形式系统I由下面四个部分组成:
(1)非空的字符表集,记作A(I)。
(2)A(I)中符号构造的合式公式集,记作E(I)。
(3)E(I)中一些特殊的公式组成的公理集,记作AX(I)。
(4)推理规则集,记作R(I)。
可以将I记为.其中是I的形式语言系统,
形式系统一般分为两类。
一类是自然推理系统,它的特点是从任意给定的前提出发,应用系统中的推理规则进行推理演算,得到的最后命题公式是推理的结论(有时称为有效的结论,它可能是重言式,也可能不是)。
另一类是公理推理系统,它只能从若干给定的公理出发,应用系统中推理规则进行推理演算,得到的结论是系统中的重言式,称为系统中的定理。
二、自然推理系统P
P是一个自然推理系统,因而没有公理。
故P只有三个部分。
定义3.3自然推理系统P定义如下:
1.字母表
(1)命题变项符号:
p,q,r,…,pi,qi,ri,…
(2)联结词符号:
┐,∧,∨,→,
(3)括号和逗号:
(,),,
2.合式公式同定义1.6
3.推理规则
(1)前提引入规则:
在证明的任何步骤上都可以引入前提。
(2)结论引入规则:
在证明的任何步骤上所得到的结论都可以作为后继证明的前提。
(3)置换规则:
在证明的任何步骤上,命题公式中的子公式都可以用与之等值的公式置换,得到公式序列中的又一个公式。
由九条推理定律和结论引入规则还可以导出以下各条推理定律。
(4)假言推理规则(或称分离规则):
若证明的公式序列中已出现过A→B和A,则由假言推理定律(A→B)∧A
B可知,B是A→B和A的有效结论。
由结论引入规则可知,可将B引入到命题序列中来。
用图式表示为如下形式:
以下各条推理定律直接以图式给出,不再加以说明。
(5)附加规则:
(6)化简规则:
(7)拒取式规则:
(8)假言三段论规则:
(9)析取三段论规则:
(10)构造性二难推理:
(11)破坏性二难推理规则:
(12)合取引入规则:
本条规则说明,若证明的公式序列中已出现A和B,则可将A∧B引入序列中。
这就完成了P的定义。
三、P中的证明
P中的证明就是由一组P中公式作为前提,利用P中的规则,推出结论。
当然此结论也为P中公式。
例3.3在自然推理系统P中构造下面推理的证明:
(1)前提:
p∨q,q→r,p→s,┐s
结论:
r∧(p∨q)
(2)前提:
┐p∨q,r∨┐q,r→s
结论:
p→s
解
(1)证明:
①p→s 前提引入
②┐s 前提引入
③┐p ①②拒取式
④p∨q 前提引入
⑤q ③④析取三段论
⑥q→r 前提引入
⑦r ⑤⑥假言推理
⑧r∧(p∨q)⑦④合取
此证明的序列长为8,最后一步为推理的结论,所以推理正确,r∧(p∨q)是有效结论。
(2)证明:
①┐p∨q 前提引入
②p→q ①置换
③r∨┐q 前提引入
④q→r ③置换
⑤p→r ②④假言三段论
⑥r→s 前提引入
⑦p→s ⑤⑥假言三段论
从最后一步可知推理正确,p→s是有效结论。
可以在自然推理系统P中构造数学和日常生活中的一些推理,所得结论都是有效的,即当各前提的合取式为真时,结论必为真。
例3.4在自然推理系统P中构造下面推理的证明:
若数a是实数,则它不是有理数就是无理数;若a不能表示成分数,则它不是有理数;a是实数且它不能表示成分数。
所以a是无理数。
解首先将简单命题符号化:
设p:
a是实数。
q:
a是有理数。
r:
a是无理数。
s:
a能表示成分数。
前提:
p→(q∨r),┐s→┐q,p∧┐s
结论:
r
证明:
①p∧┐s 前提引入
②p ①化简
③┐s ①化简
④p→(q∨r)前提引入
⑤q∨r ②④假言推理
⑥┐s→┐q 前提引入
⑦┐q ③⑥假言推理
⑧r ⑤⑦析取三段论
P中证明的两个常用技巧:
1.附加前提证明法
2.归谬法
四、附加前提法
有时推理的形式结构具有如下形式
(A1∧A2∧…∧Ak)→(A→B) (3.5)
(3.5)式中结论也为蕴涵式。
此时可将结论中的前件也作为推理的前提,使结论只为B。
即,将(3.5)化为下述形式
(A1∧A2∧…∧Ak∧A)→B (3.6)
其正确性证明如下:
(A1∧A2∧…∧Ak)→(A→B))
┐(A1∧A2∧…∧Ak)∨(┐A∨B)
┐(A1∧A2∧…∧Ak∨┐A)∨B
┐(A1∧A2∧…∧Ak∧A)∨B
(A1∧A2∧…∧Ak∧A)→B
因为(3.5)式与(3.6)式是等值的,因而若能证明(3.6)式是正确的,则(3.5)式也是正确的。
用形式结构(3.6)式证明,将A称为附加前提,并称此证明法为附加前提证明法。
例3.5在自然推理系统P中构造下面推理的证明。
如果小张和小王去看电影,则小李也去看电影;小赵不去看电影或小张去看电影;小王去看电影。
所以,当小赵去看电影时,小李也去看电影。
解将简单命题符号化:
设p:
小张去看电影。
q:
小王去看电影。
r:
小李去看电影。
s:
小赵去看电影。
前提:
(p∧q)→r,┐s∨p,q
结论:
s→r
证明:
用附加前提证明法。
①s 附加前提引入
②┐s∨p 前提引入
③p ①②析取三段论
④(p∧q)→r前提引入
⑤q 前提引入
⑥p∧q ③⑤合取
⑦r ④⑥假言推理
思考:
不用附加前提证明法构造例3.5的证明。
五、归谬法
在构造形式结构为
(A1∧A2∧…∧Ak)→B
的推理证明中,如果将┐B作为前提能推出矛盾来,比如说得出(A∧┐A),则说明推理正确。
其原因如下:
(A1∧A2∧…∧Ak)→B
┐(A1∧A2∧…∧Ak)∨B
┐(A1∧A2∧…∧Ak∧┐B)
若(A1∧A2∧…∧Ak∧┐B)为矛盾式,正说明(A1∧A2∧…∧Ak)→B为重言式,即(A1∧A2∧…∧Ak)
B,
故推理正确。
例3.6在自然推理系统P中构造下面推理的证明。
如果小张守第一垒并且小李向B队投球,则A队将取胜;或者A队未取胜,或者A队获得联赛第一名;A队没有获得联赛的第一名;小张守第一垒。
因此,小李没有向B队投球。
解先将简单命题符号化。
设p:
小张守第一垒。
q:
小李向B队投球。
r:
A队取胜。
s:
A队获得联赛第一名。
前提:
(p∧q)→r,┐r∨s,┐s,p
结论:
┐q
证明:
用归谬法
①q 结论的否定引入
②┐r∨s 前提引入
③┐s 前提引入
④┐r ②③析取三段论
⑤(p∧q)→r前提引人
⑥┐(p∧q) ④⑤拒取式
⑦┐p∨┐q ⑥置换
⑧p 前提引入
⑨┐q ⑦⑧析取三段论
⑩q∧┐q ①⑨合取
由于最后一步q∧┐q
0,即(((p∧q)→r)∧(┐r∨s)∧┐s∧p)∧q
0,所以推理正确。
思考:
不用归谬法证明例3.6
主要内容
1.
推理的形式结构:
①推理的前提
②推理的结论
③推理正确
④有效结论
2.
判断推理是否正确的方法:
①真值表法
②等值演算法
③主析取范式法
3.
对于正确的推理,在自然推理系统P中构造证明
4.
①自然推理系统P的定义
②自然推理系统P的推理规则:
前提引入规则、结论引入规则、置换规则、假言推理规则、附加规则、化简规则、拒取式规则、假言三段式规则、构造性二难规则、合取引入规则。
③附加前提证明法
④归谬法
学习要求
1.
理解并记住推理的形式结构的三种等价形式,即
①{A1,A2,…,Ak}├B
②A1∧A2∧…∧Ak→B
③前提与结论分开写:
前提:
A1,A2,…,Ak
结论:
B
在判断推理是否正确时,用②;在P系统中构造证明时用③。
2.
熟练掌握判断推理是否正确的三种方法(真值表法,等值演算法,主析取范式法)。
3.
牢记P系统中的各条推理规则。
4.
对于给定的正确推理,要求在P系统中给出严谨的证明序列。
5.
会用附加前提证明法和归谬法。
1.
分别用真值表法、等值演算法、主析取范式法、构造证明法,证明下面推理是正确的。
设a,b∈R(R为实数集)。
推理如下:
“若a是奇数,则a不能被2整除;若a为偶数,则a能被2整除。
因此,若a为偶数,则a不是奇数。
”
提示参看真值表,等值演算,主析取范式,在P系统中构造证明。
答案
先将简单命题符号化,然后写出推理的前提和结论。
令p:
a是奇数,q:
a是偶数,r:
a能被2整除。
前提:
p→┐r,q→r
结论:
q→┐p
方法一、用真值表法证明推理正确。
首先写出推理的形式结构,并记为(*)
(p→┐r)∧(q→r)→(q→┐p)(*)
然后制作(*)的真值表,见下表
(*)的真值表
由于真值表的最后一列全为1,故(*)为重言式,因而推理正确。
方法二、等值演算法
(p→┐r)∧(q→r)→(q→┐r)
(┐p∨┐r)∧(┐q∨r)→(┐q∨┐p)(蕴涵等值式)
┐((┐p∨┐r)∧(┐q∨r))∨(┐q∨┐p)(蕴涵等值式)
(p∧r)∨(q∧┐r)∨┐q∨┐p(德·摩根律)
((p∧r)∨┐p)∨((q∧┐r)∨┐q)(交换、结合律)
(┐p∨r)∨(┐q∨┐r)(排中律、同一律)
(r∨┐r)∨┐p∨┐q(交换、结合律)
1∨┐p∨┐q(排中律)
1(零律)
由于等值演算的结果为1,所以(*)为重言式,故推理正确。
方法三、主析取范式法
(p→┐r)∧(q→r)→(q→┐p)
(p∧r)∨(q∧┐r)∨┐q∨┐p(见方法二第4式)
(m5∨m7)∨(m2∨m6)∨(m0∨m1∨m4∨m5)∨(m0∨m1∨m2∨m3)
m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7
由于(*)中含3个命题变项,因而共可产生8个极小项,(*)的主析取范式中含全部8个
极小项,所以(*)为重言式,故推理正确。
注意:
在演算的倒数第二步,由括号括起来的极小项分别是由相应的简单合取式
派生的极小项。
方法四、构造证明法
证明:
①p→┐r前提引入
②┐p∨┐r①置换
③┐r∨┐p②置换
④r→┐p③置换
⑤q→r前提引入
⑥q→┐p⑤④假言三段论
还可以使用附加前提证明法。
证明:
①q附加前提引入
②q→r前提引入
③r①②假言推理
④p→┐r前提引入
⑤┐p③④拒取式
2.
证明下面的推理不正确
如果今天是星期日,则明天是星期一;明天是星期一。
所以今天是星期日。
提示参看真值表,等值演算,主析取范式,推理的形式结构,推理
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学结构 第3章 命题逻辑的推理理论 离散数学 结构 命题逻辑 推理 理论