第3章2命题逻辑推理系统.ppt
《第3章2命题逻辑推理系统.ppt》由会员分享,可在线阅读,更多相关《第3章2命题逻辑推理系统.ppt(56页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 第三节第三节 命题演算命题演算 一、重言式及其判定一、重言式及其判定(一)真值联结词、真值形式复合命题形式在数理逻辑中叫真值形式。表示关系的联结词叫真值联结词。真值联结词是日常语言联结词在真假关系上的一种抽象。真值联结词有五个:否定真值联结词有五个:否定 、合取合取、析取、析取、蕴涵、蕴涵、等值等值。真值形式就是真值真值形式就是真值联结词与命题变项所构成的形联结词与命题变项所构成的形式结构。命题变项是组成复合式结构。命题变项是组成复合命题的原子命题命题的原子命题,用字母用字母p、q、r、s表示。表示。五种基本的真值形式:五种基本的真值形式:合取式:合取式:p pq q析取式:析取式:p pq
2、 q蕴涵式:蕴涵式:p pq q等值式:等值式:p pq q否定式:否定式:p p五种基本形式可生成更复杂的形式,五种基本形式可生成更复杂的形式,1 1、(、(pqpq)(pp q q)p p;2 2、(、(pqpq)(rsrs)(prpr)(qsqs)真值形式最外层的括号根据五个联结词的结合力可以省略,结合力按照下列顺序递减:、(pq)r)(ps)可以省略为:pqr ps复合命题真假与其支命题真假之间的关系与数学中的函数类似。在数学中,函数是用下面的公式表示的:y=f(x)其中,x是自变元,y是函数的值,f是函数关系。例如:y=x2数理逻辑引入函数原理来说明复合命题与其支命题之间的真假关系,
3、它把这种关系当作一种函项关系,把这种函数叫做真值函项。真值函项的值不是数,而是真值。数学中同一个函数可以有不同的表现形式,例如:y=2x2+x,y=x(2x+1)同样,数理逻辑中,同一个真值函项也可以有不同的真值形式,例如:pq,(pq)真值形式的数目是无穷的,但是在命题变项的数目给定之后,真值函项的数目也就确定了。n个命题变项的真假组合会有多少个真值函项?当n=1时,只有一个命题变项p,而p本身有真或假两种取值,当p取真时,对应的真值函项有真或假两种可能,当p取假时,对应的真值函项也有真或假两种可能。因此,一个命题变项对应的真值函项有四种。当当n=2时,命题变项时,命题变项p和和q取值:取值
4、:p真时,对应真时,对应q有真假两种可能;有真假两种可能;p假时,假时,q也有真假两种可能;、也有真假两种可能;、两个命题变项有四种真假取值。两个命题变项有四种真假取值。对于对于p和和q的四种取值,其真值函的四种取值,其真值函项真假取值情况项真假取值情况共有共有1616种。种。两个命题变项有四种真假取值两个命题变项有四种真假取值为:p q T T T F F T F F对应对应的的1616种真种真值值函函项项有有p q f1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16T T TT T T T T T T F F F F F F F FT F TT T T F F
5、F F T T T T F F F FF T TT F F T T F F T T F F T T F FF F TF T F T F T F T F T F T F T F计算方法:计算方法:1 1个命题变项,其真假取值有个命题变项,其真假取值有2 21 1个,个,对应的真值函项有对应的真值函项有2 2的的2 21 1次方个。次方个。2 2个命题变项,其真假取值有个命题变项,其真假取值有2 22 2个,个,对应的真值函项有对应的真值函项有2 2的的2 22 2次方个。次方个。n n个命题变项,其真假取值有个命题变项,其真假取值有2 2n n个,个,对应的真值函项又有对应的真值函项又有2 2的
6、的2 2n n次方个。次方个。设想一下:两张红黑扑克牌,它们的红黑组合有多少种?这就相当于两个命题变项的4种真假组合。你猜对或猜不对各种组合的情况有多少种可能?这就相当于两个命题变项的4种真假组合对应的16种真值函项再设想一下:你参加两次考试,它们及格和不及格的组合有多少种?这也相当于两个命题变项的4种真假组合。而4种情形对应的你考试时的精神状态的好坏有多少种?这也相当于两个命题变项的4种真假组合对应的16种真值函项(二)真值函项的种类及其判定方法(二)真值函项的种类及其判定方法(1 1)真值函项的种类)真值函项的种类按真值函项的取值,真值函项分为:按真值函项的取值,真值函项分为:常真的。常真
7、的。常假的。常假的。可满足的。可满足的。真值形式也分为三类:真值形式也分为三类:重言式。如:重言式。如:p p p p、p pp p等。等。矛盾式。如:矛盾式。如:p p p p、p p p p。可满足式。如:可满足式。如:p pq q、p pq q。命题逻辑中有效的推理在形式命题逻辑中有效的推理在形式上都是重言式。要判定一个复上都是重言式。要判定一个复合命题推理是否有效,其实质合命题推理是否有效,其实质也就是判定反映该推理的公式也就是判定反映该推理的公式是否为重言式。是否为重言式。介绍两种判定重言式的方法:介绍两种判定重言式的方法:真值表法真值表法归谬赋值法。归谬赋值法。(2)真值表判定方法
8、:)真值表判定方法:第一步:找出公式中所有不同的命题变第一步:找出公式中所有不同的命题变项,竖行列出它们之间所有可能的真假项,竖行列出它们之间所有可能的真假组合。例:判定(组合。例:判定(pq)p)q p qT TT FF TF F第二步:由简单到复杂横行列出该公式的所有子公式与该公式本身 p q pq (pq)p (pq)pq T TT FF TF F 第三步:计算出各子公式的真值与该公式的真值。若该公式值都真,为重言式,都假,为矛盾式,有真有假,为可满足式。p q pq (pq)p (pq)pq T T T T T T F F F T F T T F T F F T F T(3 3)归谬赋
9、值法)归谬赋值法第一步:假定被判定的公式为假。第一步:假定被判定的公式为假。第第二二步步:从从这这一一假假定定出出发发,按按照照不不同同联联结词的要求对公式各部分赋以真值。结词的要求对公式各部分赋以真值。第第三三步步:检检查查变变项项真真值值,如如出出现现逻逻辑辑矛矛盾盾,证证明明原原假假定定为为假假,原原公公式式是是重重言言式式;如如未未导导致致矛矛盾盾,证证明明原原假假定定成成立立,原原公公式不是重言式。式不是重言式。(p pq q)(q qr r)(p pr r)1 1)F F2 2)T F T F3 3)T T T F T T T F4 4)T T T T F F5)q q真与真与 q
10、 q假假 矛盾矛盾6)证明原假定为假,原公式是重言式证明原假定为假,原公式是重言式((p q )q )p 假 (1)真 假 (2)真 真 (3)假 假 (4)q假与 q真矛盾 (5)证明原假定为假,原公式是重言式证明原假定为假,原公式是重言式 ((p p q)q)p p )q q 假假 真真 真真 真真 假假 假假 真真 证明原假定成立,原公式不是重言式证明原假定成立,原公式不是重言式二、命题逻辑的公理系统二、命题逻辑的公理系统命题演算是命题逻辑的形式系统。命题演算是命题逻辑的形式系统。形式系统是指用人工语言表示的系统。形式系统是指用人工语言表示的系统。形式系统形式系统只考虑符号与符号之间的关
11、系。只考虑符号与符号之间的关系。一个形式系统通常包括形式语言与演绎系统。一个形式系统通常包括形式语言与演绎系统。形式语言:包括初始符号与形成规则形式语言:包括初始符号与形成规则 演绎系统:包括公理、推理规则与定理。演绎系统:包括公理、推理规则与定理。一个形式公理系统一般由初始符号、一个形式公理系统一般由初始符号、形成规则、初始公式与变形规则四形成规则、初始公式与变形规则四个部分组成个部分组成。希希尔尔伯伯特特(D DHilbertHilbert)与与阿阿克克曼曼(W Wackermann)ackermann)提提出出的的系系统统,简简称称系统系统P P。P P系统包括如下出发点:系统包括如下出
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 命题逻辑 推理 系统
限制150内