二.
真值形式的判定
5.
真值形式的类型·重言式、矛盾式和可真式·
真值形式的判定及其基本方法
真值形式有三种基本类型:重言式、矛盾式和可真式。
一个
真值形式是重言式,当且仅当它在其
命题变项的任意一组赋值下都真。例如,是重言式,不论P取什么值.它的值都为真。
一个
真值形式是矛盾式,当且仅当它在其
命题变项的任意一组赋值下都假。例如,是矛盾式,不论q取什么值,它的值都假。
一个
真值形式是可真式,当且仅它在其
命题变项的至少一组赋值下为真。例如,pq是可真式。当p和q都真时pq为真。
显然,
真值形式分为矛盾式和可真式,而可真式又分为重言式和非重言的可真式,重言式都是可真式,但可真式未必都是重言式。
一个
真值形式A是重言式,当且仅当它的否定A是矛盾式。
一个
真值形式A是可真式,当且仅当它的否定A不是重言式。
真值形式的判定,就是确定它属于重言式、矛盾式和(非重言的)可真式中的哪一种。
在各种
真值形式中,我们最感兴趣的是重言式。在
命题逻辑中,重言式也称为
逻辑规律。
真值形式的判定,主要是重言式的判定。
我们知道,一个
命题推理的
真值形式是一个蕴涵式,即前提的合取蕴涵结论。由推理有效
性的定义,显然,一个
命题推理是有效的,当且仅当它的
真值形式是个重言的蕴涵式。也就是说,判定一个
命题推理是否有效,就是判定它的
真值形式是否为一重言式。
上面例举的重言式、矛盾式和可真式,在直观上是很明显的。但一般地说,靠直观难以判定一个
真值形式的类型。要解决
真值形式的判定,就要寻求一些一般
性的方法。
下面将介绍一些判定
真值形式的基本方法,它们是
真值表方法、归谬赋值法、范式方法和
真值树方法。
真值形式的判定问题是解决了的。也就是说,存在着一种能行的方法,能通过程序化的步骤,在有限步内判定任意一个
真值形式是否为一重言式(矛盾式或可真式)。
6.
真值表·能行方法·
真值形式是能行可判定的
在以上的讨论中,已经运用了
真值表。现在来说明,如何一般
性地构造一个
真值形式的
真值表,以及如何运用
真值表来完成
真值形式的判定。
构造一个
真值形式的
真值表的步骤是:第一,确定
真值形式中有多少个不同的
命题变项;第二,列出
命题变项的所有不同的取值情况,一般地,n个
命题变项所有不同的取值情况是组;第三,相应于
命题变项的各组取值,计算出
真值形式的
真值;第四,作出完整的
真值表。
一个
真值形式是重言式当且仅当它在其
真值表各行中的取值都真。
一个
真值形式是矛盾式当且仅当它在其
真值表各行中的取值都假。
一个
真值形式是可真式当且仅当它在其
真值表至少一行中取值为真。
下面通过实例说明。
[例1] 用
真值表判定以下
真值形式:
该
真值形式共有两个
命题变项,因此其取值情况共有四种。依次计算出这四种情况下
真值形式的值,即得
真值表如下:
1 1 1 0 0 1 0 0
以上的
真值运算过程在
真值表中可以省去。上述
真值表可写成:
1 1 1 1 0 1 0 1 1 0 0 1
该
真值形式为重言式。
[例2] 用
真值表判定下列
真值形式:
(1)
(2)
1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1
(1)式是矛盾式,(2)式是非重言的可真式。
[例3] 用
真值表判定下列
命题推理是否有效:
(1) 此案的作案者是张三,或者是李四。有证据证明张三没作案。因此,作案者是李四。
(2) 此案的作案者是张三,或者是李四。有证据证明张三作案。因此,作案者不是李四。
(3) 此案的作案者是张三,或者是李四。因此,并非如果李四没作案,就一定是张三作案。
[解] 令p=作案者是张三,q=作案者是李四。则上述三个推理的
真值形式是:
(1)
(2)
(3)
构造三个
真值形式的
真值表如下:
1 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 (1)式是重言式,因而推理(1)有效。
(2)式是非重言的可真式,(3)式是矛盾式。因此,推理(2)和推理(3)无效。
上面的结论也说明,并非只有当其
真值形式是矛盾式时,一个
命题推理才是无效的;当且仅当其
真值形式是重言式时,一个
命题推理才是有效的。
[例4] 用
真值表判定以下
命题推理:
或者
逻辑难学,或者没有多少学生喜欢它。如果数学容易学,那么
逻辑不难学。因此,如果许多学生喜欢
逻辑,那么数学并不太容易。
[解] 令p=
逻辑难学,q=没有多少学生喜欢
逻辑,r=数学容易学。
则该推理的
真值形式是:
构造它的
真值表如下:
p q r 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 推理有效。
真值表方法是一种能行方法。
能行方法是一种问题求解的方法。
一种问题求解的方法是能行的,是指:第一,这种方法对问题求解的每-步都给出确定的操作指令;第二,作为第n步求解操作的结果,这种方法给出第n+1步的确定操作指令;第三,这种方法确保在有限步内完成问题的求解。
显然,能行方法有两个根本
特点:一是操作方法是机械的,二是操作步骤是有限的。
真值表方法完全具备这两个
特点。对于任一
真值形式,运用
真值表方法,都能在有限步内作出机械的判定。因此,
真值形式的判定问题是解决了的,或者说,任一
真值形式都是能行可判定的。
7.归谬赋值法
真值表方法的优点是它的能行
性,但是,如果
命题变项的数目较多,这种方法就显得不够简便,例如,如果出现四个
命题变项,相应的
真值表就须有16行。
归谬赋值法是一种较为简便的判定方法,也称为简化
真值表,它专门用来判定一蕴涵式是否为重言式。我们已经指出,
逻辑的核心问题,是推理有效
性的判定。在
命题逻辑中,
命题推理的
真值形式是一蕴涵式,因此,
命题推理的判定,就是判定相应的蕴涵式是否为重言式。这说明,在
真值形式的判定中,判定蕴涵式是否为重言式具有
特别重要的地位。这也说明归谬赋值法的意义。
归谬赋值法的基本思想是这样的:为了证明所要判定的蕴涵式是重言式,先假设它不是重言式,即假设该蕴涵式前件真而后件假,并依据这个假设给每个
命题变项赋值。如果在这个赋值过程中,为了满足前件真而后件假,必须给同一
命题变项既赋真又赋假,即出现矛盾,这说明假设不成立,即所要判定的蕴涵式不可能前件真而后件假,因面是重言式。如果在这个赋值过程中没有出现矛盾,也就是说找到一组赋值使该蕴涵式满足前件真而后件假,因此该蕴涵式不是重言式。
[例1] 用归谬赋值法判定以下推理:
如果地球围绕太阳公转,但并不围绕自己的轴心自转,那么地球上就没有白天和黑夜。因为事实是地球上有白天和黑夜,所以,或者地球并不公转,或者地球既公转又自转。
[解] 令p表示地球(围绕太阳)公转,q表示地球(围绕自己的轴心)自转,r表示地球上有白天和黑夜,则该推理的
真值形式及其归谬赋值如下:
1 0 1 1 1 1 0
0
归谬赋值的过程是:假设前件真,后件假,并根据这一假设给各
命题变项赋值。后件是析取式,为使后件假,必须使p和这两个析取支都假。为使p假,必须给P赋真,为使假,由于p已赋真,必须结q赋假。前件是合取式。为使前件真,两个合取支和r必须都真,即必须绘r赋真。由于P已赋真而q已赋假,所以真,为使真,r必须赋假。但r已赋真,矛盾!所以假设不成立,该推理形式是重言式,推理有效。
[例2] 用归谬赋值法判定以下推理:
事实是我的勺是干的,所以我没有在自己的咖啡中加糖。因为我如果搅动了咖啡,我的勺一定是潮的。然而我不会搅动咖啡,除非我给它加糖。
[解] 令P表示我的勺是于的,q表示我没有在自己的咖啡中加糖,r表示我搅动了咖啡。
该推理的结论是“我没有在自己的咖啡中加糖”,其余的断定都是前提。
该推理的
真值形式及归谬赋值如下;
0 1 1 0 1 1
在归谬赋值的过程中,没有出现矛盾,即找到以上一组赋值,使
真值形式满足前件真而后件假,因此,推理无效。
8.常用重言式·范式·合取范式和析取范式·范式的存在
性·求范式的方法·置换和代入·范式方法在
命题推理判定中的运用
常用重言式
下面列出一些常用重言式。这些重言式可用
真值表或归谬赋值法判定。
(1) (同一律)
(2) (分离律)
(3) (排中律)
(4) (不矛盾律)
(5) (否定后件律)
(6) (析取否定肯定律)
(7) ; (合取分解律)
(8) (连锁蕴涵律)
(9) (归谬律)
它的含义是:如果从一个
命题可以推出矛盾,那么,这个
命题就是假的。
(10) (析取添加律)
以上(5)一(10)式是重言蕴涵式。以下是一些重要的重言等值式。
(11) (双重否定律)
(12) ; (德摩根律)
(13)(合取交换律)
(析取交换律)
(14)(合取对于析取的分配律)
(析取对于合取的分配律)
简称分配律。
(15) (蕴涵析取律)
(16); (加元律)
(17);
(等值律)
(18); (简化律)
这些重言式大都非常直观,容易记住,它们要经常用到,必须熟记。
范式
设A为一
真值形式,是它的范式。具有如下两个
特点:第一,;第二,直观可判定,也就是说,是否为重言式或矛盾式,通过对其规范形式本身的观察即可判定。因此,对一个
真值形式的判定,可归结为求它的范式。
范式分为合取范式和析取范式。为了定义合取范式和析取范式,先需定义一些相关基本概念。
定义8.1 一个析取式为一简单析取式,当且仅当它的任一析取支是一
命题变项或其否定。
如和是简单析取式,则不是。一个简单析取式是重言式,当且仅当至少存在一个
命题变项及其否定同时是它的析取支。如,是重言的简单析取式,而则不是。显然,一个简单析取式是否为重言式,依据其形式即可直观判定。
为什么一个简单析取式是重言式,当且仅当至少存在一个
命题变项及其否定同时是它的析取支呢?因为在任意的赋值下,一
命题变项及其否定总有一真,而一析取式只要有一析取支真,它的值就真。因此,如果一
命题变项及其否定同时作为析取支出现,这样的析取式总是真的;另一方面,如果不存在一
命题变项及其否定同时作为析取支出现,那么,只要给不出现否定号的析取支中的
命题变项赋假,结出现否定号的析取支中的
命题变项赋真,整个简单析取式的值显然是假的,因此不是重言式。
定义8.2 一个合取式为一简单合取式,当且仅当它的任一合取支是一
命题变项或其否定。
如和是简单合取式,则不是。同理,一个简单合取式是矛盾式,当且仅当至少存在一个
命题变项及其否定同时是它的合取支。如,是矛盾的简单合取式,而则不是。同样显然,一个简单合取式是否为矛盾式,也是直观可判定的。
我们约定,单个的
命题变项或其否定,如p,q,等,既可看作简单析取式,又可看作简单合取式。
定义了简单析取式和简单合取式后,就可定义合取范式和析取范式了。
定义8.3 合取范式是这样一种合取式,它的每个合取支都是简单析取式。
如和是合取范式,则不是。
一合取范式是重言式,当丛仅当它的每个合取支都是重言的简单析取式。由于一个简单析取式是否为重言式是直观可判定的,因此,一合取范式是否为重言式自然也是直观可判定的。
定义8.4 析取范式是这样一种析取式,它的每个析取支都是简单合取式。
如和是合取范式,则不是。
一析取范式是矛盾式,当且仅当它的每个析取支都是矛盾的简单合取式。由于一个简单合取式是否为矛盾式是直观可判定的,因此,一析取范式是否为矛盾式自然也是直观可判定的。
由于一个
真值形式和它的范式是等值的,因此,判定一个
真值形式是否为重言式,可归结为求它的合取范式;判定一个
真值形式是否为矛盾式,可归结为求它的析取范式。
范式的存在
性、求范式的方法
现在的问题自然就是:一个
真值形式的范式是否一定存在?如何求一个
真值形式的范式?
求一个
真值形式的范式,包括这样几个具体步骤:
第-,先将
真值形式中可能包含的和完全销去。即用置换;用置换。(这里,置换和被置换的两个
真值形式是互相等值的。两个互相等值的
真值形式可以互相置换,后面将证明相关的定理。)
第二,将逐步内移至
命题变项之前,并销去双重否定号。即用置换,用置换,用A置换。
经过上述两个步骤后,
真值形式中只包含
命题变项及其否定,以及和。
第三.在上述步骤的基础上,运用析取分配律并加以化简就得到原
真值形式的合取范式,运用合取分配律并加以化简就得到析取范式。
任何
真值形式,运用上述方法,都能在有限步内得到它的范式。因此,任一
真值形式的范式是存在的。
[例1] 用范式方法判定以下
真值形式是否为重言式:
[解] 判定该式是否为重言式,须求它的合取范式:
销去: (1)
内移: (2)
(3)
销去: (4)
展开: (5)
(5)式即为原式的合取范式,显然是重言式。因此原式是重言式。
置换和代入
在求范式的过程中,我们运用了等值置换的方法。例如,依据和等值,我们在中,用置换,得到。
现在的问题是,这样的置换,能否确保置换后得到的
真值形式和原
真值形式等值呢?
答案是肯定的。下面是置换定理及相关的代人定理及其证明。
定理8.5 (置换定理)令表示A是C的组成部分。是以B置换A在C中的部分或全部出现所得到的结果。则:如果A和B等值,则和等值,即如果是重言式,则是重言式。
例如.在上面提到的实例中,如果以A表示,B表示,就是,就是 。
[证明] 如果是重言式,则对于和中所有
命题变项(自然也包括A和B中的所有
命题变项)的任意一组赋值,的值都真,因而的值也都真,因为与的区别只在于,A在C中的一处或数处出现换成了B,而A和B的值相同,因此,和的值相同。因此,是重言式。即如果A和B等值,则和等值。证毕。
定理8.6 (重言式代入定理)如果A是一重言式,A中出现的所有
命题变项为,,…。B是以,,…,分别替代A中,,…的所得到的结果。不必不同于
(1i,jn)。则B也是重言式。即一重言式代入的结果是重言式。
[证明] 设A为一重言式。对于B中的
命题变项的一组赋值,,,…,有
真值,如果使,,…分别取值,那么A的值也是当的值为时B所取的值。因为A是重言式,它的值恒真,所以B的值也恒真,为一重言式。证毕。
例如,是重言式,因此,由重言式代入定理,也是重言式。
注意置换和代人的区别:第一,被代人的公式必须是重言式,而被置换的公式不必是重言式;第二,代入是以
真值形式B对一
命题变项p在某一
真值形式A中的出现作代人,对该
命题变项的每一出现都必须代以同一
真值形式B,而置换则以
真值形式B置换
真值形式C的组成部分A,但不必把A的每处出现都换成B。通常被置换的A不是
命题变项,并且A和B须等值,即是重言式。
范式方法在
命题推理判定中的运用
下面通过实例来说明范式方法在
命题推理判定中的运用。一
命题推理有效,当且仅当它的
真值形式是重言式,因此,一
命题推理有效
性的判定,可归结为求它的合取范式。
[例2] 试判定以下两个推理的有效
性:
(1) 与人民为敌,而又不受历史的惩罚,这是妄想。因此,要想不受历史的惩罚,只有不与人民为敌。
(2) 与人民为敌、而又不受历史的惩罚,这是忘想。因此,只要不与人民为敌,就能不受历史的惩罚。
[解] 令P表示“与人民为敌”,q表示“受历史的惩罚”(
命题的主语均省略),则推理(1)的
真值形式是:;
推理(2)的
真值形式是:。
这里说明一下,为什么推理(1)的结论“要想不受历史惩罚,只有不与人民为敌”的
真值形式是。我们知道,“只有A,才B”的
真值形式是,因此“只有不与人民为敌,不受历史惩罚”的
真值形式是,即。
先求的合取范式:
销去: (1)
销去: (2)
展开: (3)
(3)式即为合取范式,显然是重言式。因此,推理(1)有效。
再求的合取范式:
销去: (1)
销去: (2)
展开: (3)
(3)式即为合取范式,不是重言式,因此,推理(2)无效。
[例3] 按照上帝创世说,上帝在创造地球的三天之后创造了太阳。有人构造了以下的推理驳斥这种说法。试判定该推理的有效
性:
如果上命创世说的故事是真实的,那么,地球在存在的头三天就没有太阳。而“一天”的概念正是由太阳来定义的。不可能“一天”的概念既这样定义,地球又在太阳的创造之前已存在了三天。因此,上帝创世说是不真实的。
[解] 令p表尔“上帝创世说是真实的”,q表示“地球存在的头三天没有太阳”,r表示“'一天’的概念由太阳定义”。则推理形式为:。
注意,“地球又在太阳的创造之前已存在了三天”的意思就是“地球存在的头三天没有太阳”,因此,以q表示。
求该
真值形式的合取范式:
销去: (1)
内移: (2)
(3)
销去: (4)
展开:
(5)
(5)式即为合取范式,是重言式,因此推理有效。
运用分配律进行展开时,符号纷杂,稍有不慎,就会出错。这里有个简明的操作方法。在进入展开步骤时,若求合取范式,则用算术运算符号“十”代替,用“.”(乘号)代替并把它省略;若求析取范式,则用“十”代替,用“.”代替并省略。代换后的符号式成了代数式,对其运用分配律,展开整理后再复原。如以上(4)式
代换后得:
即:
对其运用分配律就明了得多了。
9.优范式·优析取范式和优合取范式·优范式的唯一
性·如何求优范式·优范式的应用
什么是优范式
求范式的方法是一种程序
性的方法,这说明,每个
真值形式的范式都是存在的。现在的问题是,一个
真值形式的合取范式或析取范式是否是惟一的呢?
事实上,一般的范式不满足惟一
性。例如,就可以有两种不同的合取范式(自然它们一定是等值的);
如果依据等值于,即等值于来销去,则得到的合取范式是:
(1)
如果依据等值于来销去,则得到的合取范式是:
(2)
下面定义的优范式,是一种满足惟一
性,同时还具有另一些
特殊作用的范式。
先定义优析取范式,有优合取范式的定义是类似的。
定义9.1 一个
真值形式是优析取范式,当且仅当它满足下列条件:
第一,是析取范式;
第二,如果一
命题变项在其中出现,那么必须在它的每个析取支中都出现。(如不是优析取范式,因为p、 q和r没有在每个析取支中都出现)
第三,不出现矛盾的析取支,即没有析取支是矛盾的简单合取式。(如不是优析取范式)
第四,在每个析取支即简单合取式中,不出现相同的合取支。(如不是优析取范式)
第五 ,
命题变项及其否定按字母符号的字典次序排列,即:
p、、q 、q、r、r、s、、t、。
如果和是其中的两个析取支,并且的第一个合取支的符号在排列顺序中列于的第一个合取支的符号之前,则列于之前,如果第一个合取支相同,则以同样的标很考察第二个合取支,以此类推;如果和是某一析取文(简单合取式)中的两个合取支,并且在符号排列中列于之前,则列于之前。(如不是优析取范式)
第六,不出现相同的析取支。(如不是优析取范式)
在上述定义中,将“析取”替换“合取”的每一出现,将“合取”替换“析取”的每一出现,并将第二条改为:不出现重言的合取支,即没有合取支是重言的简单析取式,就得到了优合取范式的定义。
优范式的惟一
性现在来证明优范式的惟一
性。
定理9.2 (1)任-
真值形式都有惟一的优析取范式。
(2)有n个不同的
命题变项的
真值形式是重言式,当且仅当它的优析取范式的析取支的数目是。
(3)有n个不同的
命题变项的
真值形式是矛盾式,当且仅当它的优析取范式的析取支的数目是0。
[证明] (1)令A是任一
真值形式,A中所有不同的
命题变项是。构造A的
真值表。A中有n个不同的
命题变项,所以A的
真值表共有行。从上至下逐行考察A的值。如果在某行A的值为真,则写下简单合取式:,其中,如果
命题变项(i=1,…,n)在该行的值为真,则是;否则,是,把这样构造好的简单合取式,依据构造时的顺序用联结成一析取式D。这样构造的析取式D,依照定义,显然是-优析取范式;并且D与A有相同的
真值表,因此,D是A的优析取范式。这就证明了A的优析取范式的存在
性。
再考虑优析取范式的惟一
性。每个包含n个
命题变项的
真值形式,都惟一地对应了一个n元
真值函数。我们知道n元
真值函数,共有个。依据以上D的构造,对应于每一n元
真值函数,都有一个相应的优析取范式,不同的
真值函数,对应于不同的优析取范式。这样,包含n个
命题变项的所有不同的优析取范式的数目是个。因此,任一
真值形式只与一个优析取范式等值,即任一
真值形式的优析取范式是惟一的。
(2)设A是一有n个不同
命题变项的
真值形式,则A的
真值表共有行。如果A是重言式,则A在其中每一行的值都真。依据上面优析取范式的构造,A的优析取范式共有个析取支,由优析取他式的惟一
性,可知A的优析取范式的析取支必为个。如果A不是重言式,则在其
真值表中,在某些行A的值为假,A的优析取范式中,没有与这些行相应的析取支,因此,A的优析取范式的析取支的数目必少于个。
(3)如果上述A是矛盾式,则其优析取范式的每个析取支必为矛盾的简单合取式,由定义,优析取范式中不出现矛盾的析取支,因此,A的优析取范式的析取支的数目是0。这样的
真值形式,称为空式,即其中
命题变项和
真值联结词都零次出现。
定理9.3 (1)任一
真值形式都有惟一的优合取范式。
(2)有n个不同的
命题变项的
真值形式是重言式,当且仅当它的优合取范式的合取支的数目是0。
(3)有n个不同的
命题变项的
真值形式是矛盾式,当且仅当它的优合取范式的合取支的数目是。
[证明 (1)证明优析取范式惟一
性的方法不能简单地用于证明优合取范式的惟一
性,这需要寻求其他的证明途径。
我们已经知道,包含n个
命题变项的
真值函数是个。如果能够证明包含n个
命题变项的优合取范式的总数也是个,由于不同的
真值函数对应于不同的优合取范式,这自然就证明了每个
真值函数即
真值形式具有惟一的优合取范式。
如何确定包含n个
命题变项的优合取范式的总数呢?这取决于两点:第一,这样的优合取范式所有可能的合取支的总数是多少?第二,由这些合取支可能构成的所有合取式是多少(包括空式)?在包含n个
命题变项的优合取范式的每个合取支(简单析取式)中,这n个
命题变项,或者自身出现,或者自身的否定出现。因此,满足这样条件的简单析取式的总数是个。例如,包含p和q两个
命题变项的优合取范式所有可能的合取支的总
数是=4个:。
上述这个不同的简单析取式,可以组成多少种不问的优合取范式呢,这个问题相当于2个简单析取式共有多少种不同的组合(包括空式)?这种组合的总数可用以下公式求得:
=
因此,优合取范式的总数是个。(在上面的等式中,以表示空式,即重言的优合取范式的数量,表示矛盾的优合取范式的数量,显然,二者的数值都为1。表示只有一个合取支的优合取范式的数量,……,一般地,表示有i个合取支的优合取范式的数量。)因为n元
真值函数的总数也是个,而不同的
真值函数对应于不同的优合取范式,这就证明了每一
真值形式具有惟一的优合取范式。
上述证明方法显然也可用来证明优析取范式的惟一
性。
(2)设A为重言的优合取范式,则A为重言的合取范式,则A的每个合取支都为重言的简单析取式。由优合取范式的定义,A中不出现重言的合取支,因此,A的合取支的数目是0,即A为空式。
(3)假设A是包含n个
命题变项的矛盾的优合取范式,它的合取支的数目少于。由(1)中的论证已知,包含n个
命题变项的优合取范式所有可能的合取支的总数是个。由假设,
在上述个合取支中,至少有一个合取支C没有在A中出现,并且,对于A中任一合取支B,C中至少有一个析取支不在B中出现。现定义对n个
命题变项的一组赋值,使得在该组赋值下C假,即C的每个析取支都假,又因为C中至少有一个析取支不在A的任一合取支B中出现,所以,A的任一合取支中,至少有一个和C的某一析取支矛盾的
命题变项或其否定作为析取支,这样,在上述这组斌值下,A的任一合取支中,都存在一个析取支为真,因而A的所有合取支都真,即A真,这和A是矛盾式的假设矛盾!因此,假设不成立,A的合取支的数目不少于个,又A的合取支的数目不多于个,所以,A的合取支的数目等于个。
假设A不是矛盾式,它的优合取范式的合取支的数目等于。记A中所有的
命题变项为。因为A不是矛盾式,所以存在一组对
命题变项的赋值,使得在该组赋值下A真。在该组赋值下,如果真,令表示;如果假,令表示 (i=1,…,n)。显然,在该组赋值下,假。因为A的合取支的总数为,所以必为A的一个合取支,可得A在该组赋值下假,与假设矛盾。所以假设不成立,A的合取支的数目不等于,即少于。
如何求优范式
以下是求优合取范式的一般步骤,求优析取范式是类似的。
第一.先求合取范式。
第二,如果合取范式中的某个
命题变项没有在某个合取支C中出现,则根据,
用置换C,并把展开为。
第三,如果在某个合取支中出现重复的析取支,或在范式中出现重复的合取支,则根据和,用A置换AA或AA。
第四,如果出现重言的合取支,则根据,用A置换。
第五,根据符号排列的字典顺序,如果需要,重排合取析取支的顺序,及重排合取支的顺序,这一步的根据是和。
依据这些步骤,就能得到一
真值形式的优合取范式。
类似地,也能得到一
真值形式的优析取范式。
[例1] 求的优合取范式。
[解] 先求得该式的合取范式: (1)
在(1)式中,用置换,用置换 ,并将所得结果展开,得:
(2)
按符号的字母顺序,重排(2)得:
(3)
在(3)式中销去重复出现的合取支,得:
(4)
(4)式即为优合取范式。
优范式的应用
优范式有着一般范式所不具有的某些作用。
第一,一真恒形式的范式不是惟一的,但它的优范式是惟一的。因此,两个
真值形式等值,当且仅当它们具有相同的优范式。
如果A和B都是重言式,则分别求A和B的合取范式就能判定它们等值;如果A和B都是矛盾式,则分别求A和B的析取范式就能判定它们等值。但如果A和B既不是重言式也不是矛盾式,则通过分别求它们的一般范式就不能判定它们是否等值,因为范式不具有惟一
性,两个等值的
真值形式完全可能具有不同的范式。而通过求它们的忧范式就能判定它们是否等值。因为优范式具有惟一
性,所以,A和B等值,当且仅当它们具有相同的优范式。
第二,用优范式可将一
真值形式化简。因为
所以,可用P置换。同理,可用p置换,达到化简的目的。
[例2] 如果可能的话,化简
[解] 不妨先求其优析取范式:
(1)
自(1)得: (2)
由(2)化简,得: (3)
自(3)分配,得: (4)
由(4)化简,得: (5)
即是的简化式,二者等值。
第三,给定一集前提,通过求优合取范式,可以提供该集前提所能推出的所有结论的一个系统综览。具体方法是:把该前提集的各个前提的
真值形式加以合取,所得的合取式即是该前提集的
真值形式;求该
真值形式的优合取范式;在该优合取范式中,任意选择若干个(可以是-个)合取支,用联结(如果合取支多于一个),可能的话加以化简。这样,就得到了从该前提集所能得出的一个推论;如果穷尽了上述所有的选择,就能得到该前提集所能推出的一切结论。
[例3] 从下列前提能推出哪些结论:
“肺癌在男
性吸烟者中比女
性吸烟者中更为普遍;如果吸烟是肺癌的原因的话,那么,这不会是事实;肺癌在男
性吸烟者中比女
性吸烟者中更为普遍的事实,意味着肺癌是由某种男
性造成的东西引起的。”
[解] 令p表示“肺癌在男
性吸烟者中比女
性吸烟者中更为普遍”,q表示“吸烟是肺癌的原因”,r表示“肺癌是由某种男
性造成的东西引起的”。
则该前提集的
真值形式是:
求它的优合取范式,得:
在上述优合取范式中,任取若干个合取支用联结,即为一个推论,穷尽了合取支的各种组合,即求出了该前提集的所有推论。
例如,取第一、三、五和六个合取支用联结,得:
(1)
这就是一个推论。可将其化简:
由(1)得: (2)
由(2)得: (3)
由(3)得: (4)
由(4)得: (5)
由(5)得: (6)
所以是一个推论。即“肺癌是由某种男
性造成的东西引起的”是原前提集的一个推论。
再如,取第三、四、六和七个合取支,得:
(1)
由(1)得: (2)
由(2)得: (3)
由(3)得: (4)
由(4)得: (5)
所以是一个推论。即“吸烟不是肺癌的原因”是原前提集的一个推论。
n个合取支的的所有不同的组合有种。所以,上述前提集的所有不同4的推论(包括自身)共127个,这说明,日常议论所
逻辑地蕴涵的“言外之意”是惊人的。上面的两个推论能从原前提集中推出是很直观的,事实上,从显然能得出r,从显然能得出q。但有些推论却并不直观。以下断定,都是上述前提集的推论,都是原议论的“言外之意”,感兴趣的话,可以逐条证明:
(1) 如果肺癌在男
性吸烟者中比女
性吸烟者小普遍的话,那么,只有男
性造成的某种东西引起肺癌,才能说明吸烟不是肺癌的原因。
(2) 如果并非男
性造成的某种东西引起肺癌,那么,吸烟是肺癌的原因和肺癌在男
性吸烟者中比女
性吸烟者中普遍,这两个断定是互相矛盾的。
等等。
严格地说,由于重言式是任意前提的
逻辑推论,因此,任何前提的
逻辑推论是无穷的。但在日常思维中,当我们说从某些断定能推出哪些结论时,是不包含这样的
逻辑推论的。以上的讨论,正是在这种日常的意义上进行的。
10.
真值树
除了判定推理的有效
性以外,在
命题逻辑中,
逻辑分析的另一个重要课题,是判定一段议论是否不自相矛盾,即判定一集
命题是否一致。
传统
逻辑中的不矛盾律(以及排中律和同一律)是揭露思想及其表述中自相矛盾、前后不一致的传统工具。但是,如果判定的对象稍微复杂一点,这种工具就不够用了。例如:
如果某甲犯了谋杀罪,那么他一定进入过爱害人的房间,并且不会在凌晨前离去。某甲或者进入过受害人的房间,或者没有,二者必居其一。除非某甲在凌晨前离去,否别看门人就会看到他。但情况井非是,如果看门人没看见某甲。他就一定不犯有谋杀罪。
这段议论是否自相矛盾?回答这个问题,传统的工具就显得不够用了.
可用求范式的方法对此进行判定。
一集
命题是自相矛盾的,或者说不一致的,当且仅当它的
真值形式是矛盾式。而判定一
真值形式是否为矛盾式,求它的析取范式就可以了。
令P表示“某甲犯了谋杀罪”,q表示“某甲进入过受害人的房间”,r表示“某甲在凌晨前离去”,s表示“看门人看到过某甲”。上述议论的
真值形式是:
求该式的析取范式(过程略),得:
该式是矛盾的析取范式,因此,原议论是自相矛盾的。
这里再介绍一种判定
命题集一致
性的方法--
真值树方法;这种方法比求析取范式较为简明。运用这种方法的步骤是:
第一,把听要判定的
命题集中的每一
命题作为前提,分别按顺序写出它们的
真值形式。
第二,按照给出的规则对每一前提进行分解.直到其中除了外不出现其他的
真值联结词,并将分解的结果以规定的树状结构列出。以这样的方式构成的所有树状结构,构成该
命题集的一个
真值树。
第三,如果在一
真值树的每一分枝上都有一
命题变项及其否定同时出现,则称该
真值树是封闭的;否则,称该
真值树是开放的。一
命题集是不一致的(自相矛盾的),当且仅当它的
真值树是封闭的。
构造
真值树的规则是
(1) 合取分解:
√
A
B
根据该规则,合取式被分解后,它的合取支写这该合取式下方的同一枝上。
真值形式被分解后,写上“√”标志,表示该式已经过分解。
(2) 析取分解:
√
A B
根据该规则,析取支被分解后,它的析取支写这该析取式下方的不同分枝上。
真值形式被分解后,写上“√”标志,表示该式已经过分解。
(3) 双否分解:
√
A
基本规则只有这三条。由于任一
真值联结郡可由、和定义,因此,依据以上三条规则可分解任意
真值形式。例如:
因为,所以下面的分解成立:
√
B
因为,所以下面的分解成立:
√
因为,所以下面的分解成立:
√
因为,所以下面的分解成立:
√
因为,所以下面的分解成立:
√
A
B
因为,所以下面的分解成立:
√
A
B
为了操作方便,一般地说,第一,先分解那些不产生新分叉的的
真值形式;第二,再分解那些能在同一分叉上迅速产生一
命题变项及其否定的
真值形式;如果前两条都不能满足,那就先分解最复杂的直值形式。
[例1] 判定是否一致。
[解] 构造该
命题集的
真值树。
(1) √ 前提
(2) C 前提
(3) √ 前提
(4) A (1)分解
(5) (1)分解
(6) (3)分解
真值树封闭,
命题集不一致。
[例2] 以下议论中有没有矛盾?
谋杀至少由管家、女仆和园丁三人中一人参与;有证据说明,或者谋杀在室内发生,或者管家参与了谋杀;如果谋杀在室内发生,则园丁可排除作案的可能;如果使用了毒药,那么除非女仆作案,否则管家不会作案。但是,第一,女仆没参与作案,第二,谋杀确实使用了毒药。
[解] 令p表示“管家参与谋杀”,q表示“女仆参与谋杀”,r表示“园丁参与谋杀”,s表示“谋杀在室内发生”,t表示“谋杀使用的毒药”。
题目中的议论包括六个
命题,构造这个
命题集的
真值树如下:
(1) √ 前提
(2) √ 前提
(3) √ 前提
(4) √ 前提
(5) 前提
(6) 前提
(7) √ (4)分解
×
(8) (7)分解
q
×
(10) s p (2)分解
×
(11) (3)分解
×
(12) p q r (1)分解
× × ×
真值树封闭,题目中的议论自相矛盾。
由于A是重言式,当且仅当A是矛盾式,因此,
真值树方法同样可以用来判定一
真值形式是否为重言式,即可以用来判定一
命题推理是否有效。
[例3] 用
真值树方法判定下面推理是否有效:
如果“世界上没有真理”这个
命题是真的话,那么,它就是假的。因此,“世界上没有真理”这个
命题是假的。
令P表示“世界上没有真理”,则上述推理的
真值形式是:
该
真值形式是重言式,当且仅当它的否定是矛盾式。因此,只要通过构造
真值树来判定是否为矛盾式就可以了。
构造的
真值树如下:
(1) √ 前提
(2) √ (1)分解
(3) √ (1)分解
(4) p (3)分解
(5) (2)分解
× ×
真值树封闭,推理有效。