离散数学 上海科学技术出版社 第1章 命题逻辑.ppt

第1,章 命题逻辑,第1,章 命题逻辑,1.1,命题及联结词,1.2,命题公式与翻译,1.3,真值表和等价公式,1.4,重言式,1.5,范式,1.6,全功能联结词集,1.7,对偶式与蕴含式,1.8,命题逻辑的推理理论,返回总目录,第1,章 命题逻辑,1.1,命题及联结词,1.1.1,命题的基本概念,在数理逻辑中把,能判断真假的陈述句称为命题。一般用小写英文字母或小写英文字母带下标表示。,命题的概念包含了以下,3,个要素：,只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题。,一个语句虽是陈述句,但不能判断真假不是命题。,虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。,一个命题表达的判断结果称为命题的真值。命题的真值有,“,真,”,和,“,假,”,两种，分别用,True、T、1,(,真,),和,False、F、0,(,假,),来表示。真值为真的命题称为真命题，真值为假的命题称为假命题。任何命题的真值是惟一的。,在命题逻辑中对命题不再细分，因而命题是数理逻辑中最基本的也是最小的研究单位。,【例1.1】,判断以下语句是否为命题。若是命题，确定其真值。,上海是个小村庄。,存在外星人。,禁止吸烟！,北京是中国的首都。,4,是素数,或,6,是素数。,今天你吃了吗？,11+1=100,我正在说谎。,解：,命题,(,F)，,命题,(,待定,),，不是命题,(,祈使句,),，,命题,(,T,)，,命题,(,F)，,不是命题,(,疑问句,),命题,(,由上下文确定,),不是命题,(,悖论,),。,表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。,命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。,如果一个命题不能再分解成更简单的命题，则称该命题为原子命题。,如果一个命题不是原子命题，称,该命题,为复合命题。,如果命题变元表示原子命题时，该命题变元称为原子变元。,在自然语言中，可以通过,“,如果,，那么,”,，,“,不但,，而且,”,这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将原子变元联结起来表示复合命题。,1.1.2,命题联结词,常用的逻辑联结词有五种：否定联结词、合取联结词、析取联结词、条件联结词和双条件联结词。,1.,否定联结词,定义,1.1.1,设,p,为命题，则,p,的否定是一个复合命题，记作：,p,，,读作,“,非,p,”,或,“,p,的否定,”,。定义为：若,P,为,T,，,则,p,为,F,；,若,p,为,F,，,则,p,的真值为,T,。,表,1.1,p,p,0,1,1,0,p,和,p,的关系如表,1.1,所示，表,1.1,叫做否定联结词“,”,的真值表,(,下同,),。,联结词,“,”,也可以看作逻辑运算，它是一元运算。,【例,1.2,】,否定下列命题。,p,：,王强是一名大学生。,p,：,王强不是一名大学生。,2.,合取联结词,定义,1.1.2,设,p,和,q,均为命题，则,p,和,q,的合取是一个复合命题，记作,p,q,，,读作,“,p,与,q,”,或,“,p,合取,q,”,。,定义为：当且仅当,p,和,q,均为,T,时，,p,q,的才为,T,。,联结词“”的真值表,如,表,1.2,所示,。,联结词“”,也可以看成逻辑运算，它是二元逻辑运算。,表,1.2,p,q,p,q,0,0,0,0,1,0,1,0,0,1,1,1,【例,1.3,】,设,p,：,2008,年将在北京举办奥运会。,q,：,中国是世界四大文明古国之一。,则,p,q,：,2008,年将在北京举办奥运会并且中国是世界四大文明古国之一。,3.,析取联结词,定义,1.1.3,设,p,和,q,均为命题，则,p,和,q,的析取是一个复合命题，记作,p,q,，,读作,“,p,或,q,”,或者,“,p,析取,q,”,。,定义为：当且仅当,p,和,q,均为,F,时，,p,q,才为,F,。,联结词,“,”,的真值表如表,1.3,所示。,联结词,“,”,也可以看成逻辑运算，它是二元逻辑运算。,表,1.3,p,q,p,q,0,0,0,0,1,1,1,0,1,1,1,1,“,”,与汉语中的,“,或,”,相似，但又不相同。汉语中的或有可兼或与不可兼或,(,排斥或,),的区分。,【例,1.4,】,下列两个命题中的,“,或,”,，哪个是可兼或？哪个是不可兼或？,在电视上看这场杂技或在剧场里看这场杂技。,(,不可兼,),灯泡有故障或开关有故障。,(,可兼,“,”,是,可兼,或,),4.,条件联结词,定义,1.1.4,设,p,和,q,均为命题，,其条件命题是个复合命题，记为：,p,q,。,读作“如果,p,，,那么,q,”,或“若,p,，则,q,”,。,定义为：当且仅当,p,为,T,，,q,为,F,时，,p,q,才为,F,。,p,称为条件命题,p,q,的前件，,q,称为条件命题,p,q,的后件。,联结词,“,”,真值表如表,1.4,所示。,联结词,“,”,也可以看成逻辑运算，它是二元逻辑运算。,表1.4,p,q,p,q,0,0,1,0,1,1,1,0,0,1,1,1,【,例,1.5,】,p,：,小王努力学习。,q,：,小王学习成绩优秀。,p,q,：,如果小王努力学习，那么他的学习成绩就优秀。,联结词,“,”,与汉语中的,“,如果,，那么,”,或,“,若,，则,”,相似，但又是不相同的。,5.,双条件联结词,定义,1.1.5,设,p,和,q,均为命题，其复合命题,p,q,称为双条件命题，读作：,“,p,双条件,q,”,或者,“,p,当且仅当,q,”,。,定义为：当且仅当,p,和,q,的真值相同时，,p,q,为,T,。,联结词,“,”,的真值表如表,1.5,所示。,联结词,“,”,也可以理解成逻辑运算，它是二元,逻辑,运算。,双条件联结词表示的是一个充分必要关系，与前面所述相同，也可以不必,表1.5,p,q,p,q,0,0,1,0,1,0,1,0,0,1,1,1,顾及其前因后果，而只根据联结词的定义来确定其真值。,【,例,1.6】,设,p,：,张华是三好学生。,q,：,张华德、智、体全优秀。,p,q,：,张华是三好学生当且仅当德、智、体全优秀。,返回章目录,1.2,命题公式与翻译,把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。当使用联结词集,，,时，合式公式定义如下：,定义,1.2.1,按下列规则构成的符号串称为命题演算的合式公式，也称为命题公式，简称公式。,单个命题变元和常元是合式公式。,如果,A,是合式公式，那么,A,是合式公式。,如果,A,和,B,是合式公式，那么,(,A,B,),、,(,A,B,),、,(,A,B,),和,(,A,B,),是合式公式。,当且仅当有限次地应用了、所得到的符号串是合式公式。,命题公式一般的用大写的英文字母,A,，,B,，,C,，,表示。,依照这个定义，下列符号串是合式公式：,(,p,q,),，,(,p,q,),，,(,p,(,p,q,),，,(,p,q,),(,q,r,)(,s,t,),下列符号串不是合式公式：,(,p,q,),(,q,),，,(,p,q,，,(,p,q,),q,),定义,1.2.1,给出合式公式定义的方法称为归纳定义，它包括三部分：基础，归纳和界限。定义,1.2.1,中的是基础，和是归纳，是界限。下文中还将多次出现这种形式的定义。,为方便起见，对命题公式约定如下：,最外层括号可以省略。,规定联结词的优先级由高到低依次为,，,。按此优先级别，如果去掉括号，不改变原公式运算次序，也可以省掉这些括号。,一般地说，命题公式中包含命题变元，因而无法计算其真值，所以不是命题。,命题公式中的命题变元，也叫命题公式的分量。,有了命题公式的概念，就可以用命题公式表示复合命题，常将这个过程称为命题的符号化。命题的符号化可按如下步骤进行：,找出复合命题中的原子命题。,用小写的英文字母或带下标的小写的英文字母表示这些原子命题。,使用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来。,【例,1.7,】,将下列命题符号化：,他或者骑自行车去学校，或者乘公共汽车去学校。,解：,令,p,：,他骑自行车去学校。,q,：,他乘公共汽车去学校。,此,命题中的或是不可兼或，所以不能符号化为：,p,q,。,而要,符号化为：,(,p,q,),或(,p,q,)(,p,q,),。,稍后会看到这个表示是正确的。,返回章目录,1.3,真值表和等价公式,1.3.1,命题公式的真值表,定义,1.3.1,设,p,l,，,p,2,，,，,p,n,是出现在公式,A,中的全部命题变元，给,p,l,，,p,2,，,，,p,n,各指定一个真值，称为对公式,A,的一个赋值或解释。若指定的赋值使,A,的真值为,T,，,则称这个赋值为,A,的成真赋值，若使,A,的真值为,F,，,则称这个赋值为,A,的成假赋值。,例如，给公式,(,p,q,r,),赋值,011,是指,p,=0，,q,=1，,r,=1，,它是该公式的成真赋值；赋值,110,是指,p,=1，,q,=1，,r,=0，,它是该公式的成假赋值。,定义,1.3.2,在命题公式,A,中，对,A,的每一个赋值，就确定了,A,的一个真值，把它们汇列成表，称该表为命题公式,A,的真值表。,【例,1.8,】,构造命题公式,p,q,的真值表，并求成真赋值和成假赋值。,解：,命题公式,p,q,的真值表如表,1.6,所示。,00,，,01,，,11,是成真赋值，,10,是成假赋值。,表1.6,p,q,p,p,q,0,0,1,1,0,1,1,1,1,0,0,0,1,1,0,1,表1.7,p,q,p,q,p,q,p,q,(,p,q,),(,p,q,),0,0,0,1,1,1,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,0,0,0,1,【,例,1.9,】,构造命题公式,(,p,q,),(,p,q,),的真值表，并求成真赋值和成假赋值。,解：,命题公式,(,p,q,)(,p,q,),的真值表如表,1.7,所示。,00,，,11,是成真赋值，,01，10,是成假赋值。,1.3.2,命题公式的等价,定义,1.3.3,设,A,和,B,是两个命题公式，对,A,和,B,的任一赋值，,A,和,B,的真值都相同，则称,A,和,B,是等价的或逻辑相等的，记为,A,B,可以证明，命题公式等价有下面的三条性质：,自反性，即对任意命题公式,A,，,A,A,对称性，即对任意命题公式,A,和,B,，,若,A,B,，,则,B,A,传递性，即对任意命题公式,A,，,B,和,C,，,若,A,B,，,B,C,，,则,A,C,根据定义,1.3.3,，,可以用真值表证明命题公式是等价的，请看下面的例题。,【例1.12】,根据等价的定义，用真值表证明,p,(,q,p,),p,(,p,q,),证明：,构造,p,(,q,p,),和,p,(,p,q,),的真值表，如表,1.10,所示。,p,(,q,p,),和,p,(,p,q,),所在的列完全相同，它们具有相同的真值表。所以,p,(,q,p,),p,(,p,q,),表1.10,p,q,p,q,q,p,p,(,q,p,),p,q,p,(,p,q,),0,0,1,1,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,0,1,证明等价,的,另外一种方法叫做等价演算法,，,其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。,基本等价式常叫命题定律。下面是常用的命题定律。,1.,双重否定律,A,A,2.,交换律,A,B,B,A,，,A,B,B,A,3.,结合律,(,A,B,),C,A,(,B,C,),(,A,B,),C,A,(,B,C,),4.,分配律,A,(,B,C,),(,A,B,),(,A,C,),A,(,B,C,),(,A,B,),(,A,C,),5.,德摩根律,(,A,B,),A,B,(,A,B,),A,B,6.,幂等律,A,A,A,，,A,A,A,7.,吸收律,A,(,A,B,),A,，,A,(,A,B,),A,8.,零律,A,1,1,，,A,0,0,9.,同一律,A,0,A,，,A,1,A,10.,排中律,A,A,1,11.,矛盾律,A,A,0,12.,条件等价式,A,B,A,B,13.,双条件等价式,A,B,(,A,B,),(,B,A,),14.,假言易位式,A,B,B,A,15.,双条件否定等价式,A,B,A,B,以上共,23,个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律。,【例,1.13,】,用真值表证明德摩根律,(,A,B,),A,B,解：,表,1.11,是,(,A,B,),和,A,B,的真值表，从表中可以看出德摩根律成立,。,表,1.11,A,B,A,B,A,B,A,B,(,A,B,),0,0,1,1,1,0,1,0,1,1,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,0,1,0,定义,1.3.4,如果,X,是合式公式,A,的一部分且,X,本身也是合式公式，则称,X,为公式,A,的子公式。,例如，,A,q,(,p,(,p,q,),，,X,p,q,，,则,X,是,A,的子公式。,定理,1.3.1,设,X,是合式公式,A,的子公式，若,X,Y,，,如果将,A,中的,X,用,Y,来置换，得到的公式记为,B,，,则,B,与,A,等价，即,A,B,证明,：,对,A,、,B,的任一赋值，,X,与,Y,的真值相同，而,A,、,B,的其它部分完全相同，公式,B,与公式,A,的真值必相同。,A,B,满足此定理的置换叫做等价置换,。,【例,1.17,】,用等价演算法证明,p,q,(,p,q,),(,p,q,),证明：,p,q,(,p,q,),(,q,p,)(,双条件等价式,),(,p,q,),(,q,p,)(,条件等价式,),(,p,q,),(,p,p,),(,q,q,),(,q,p,)(,分配律,),(,p,q,),0,0,(,q,p,)(,矛盾律,),(,p,q,),(,q,p,)(,同一律,),(,p,q,),(,p,q,)(,交换律,),p,q,(,p,q,),(,p,q,),(,等价的传递性,),返回章目录,1.4,重言式,定义,1.4.1,设,A,是任一命题公式。,若对,A,的任意赋值，其真值永为真，则称命题公式,A,为重言式或永真式。,若对,A,的任意赋值，其真值永为假，则称命题公式,A,为矛盾式或永假式。,若,A,不是矛盾式，则称命题公式,A,为可满足的。,由定义,1.4.1,可以看出，任何重言式都是可满足的。,显然，重言式的真值表的最后一列全为,1,，矛盾式的真值表的最后一列全为,0,，可满足的公式真值表的最后一列至少有一个,1,。根据这个结论借助于真值表可以判断一个公式是否为重言式，矛盾式或可满足的。当然也可以用等价演算法判断公式的类型。,【例,1.18,】,用等价演算法判断下列公式的类型。,q,(,p,q,),p,),(,p,p,)(,q,q,),r,),(,p,q,),p,解,：,q,(,p,q,),p,),q,(,p,p,)(,q,p,)(,分配律,),q,(0(,q,p,)(,矛盾律,),q,(,q,p,)(,同一律,),q,(,q,p,)(,德摩根律,),(,q,q,),p,(,结合律,),1,p,(,排中律,),1 (,零律,),由此可知，,为,重言式。,(,p,p,)(,q,q,),r,),1(,q,q,),r,)(,排中律,),1(0,r,)(,矛盾律,),10 (,零律,),0 (,条件联结词的定义,),由此可知，,为,矛盾式。,(,p,q,),p,(,p,q,),p,(,条件等价式,),p,(,吸收律,),由此可知，是可满足的。,定理,1.4.1,任何两个重言式的合取或析取都是重言式。,证明：,设,A,、,B,是重言式，对,A,和,B,的任何赋值，总有,A,为1，,B,为1,，所以,A,B,1，,A,B,1，,故,A,B,和,A,B,都是重言式。,推论,任何两个矛盾式的合取或析取是矛盾式。,定理,1.4.2,一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式,。,推论,：,一个矛盾式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是矛盾式。,【例,1.19,】,利用定理,1.4.2,证明,(,p,q,),r,),(,p,q,),r,),为重言式。,证明,：,由排中律知,p,p,为重言式，以,(,p,q,),r,),去置换其中的,p,，,得公式,(,p,q,),r,)(,p,q,),r,)，,根据定理,1.4.2,，这是重言式。,定理,1.4.3,设,A,、,B,为两个命题公式，,A,B,当且仅当,A,B,是重言式,。,证明：,设,A,B,，,下证,A,B,是重言式。,给,A,，,B,的任何赋值，因为,A,B,，,所以,A,，,B,具有相同的真值，由双条件联结词的定义知,A,B,为真，所以,A,B,为重言式。,设,A,B,为重言式，下证,A,B,给,A,，,B,的任何赋值，因为,A,B,为重言式，故,A,，,B,的真值相同，由命题公式等价的定义知,A,B,返回章目录,1.5,范式,1.5.1,析取范式与合取范式,定义,1.5.1,由一些命题变元或其否定构成的析取式称为基本和，也叫简单析取式。约定单个变元或其否定是基本和。,例如，,p,q,、,p,q,、,p,q,、,q,、,p,、,q,都是基本和。,定义,1.5.2,由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。,例如，,p,q,、,p,q,、,p,q,、,p,、,q,、,p,都是基本积。,定义,1.5.3,由,基本和的合取构成的公式叫做合取范式。,约定单个,基本和,是,合取范式,。,定义,1.5.4,由基本积的析取构成的公式叫做析取范式。,约定单个,基本积,是,析取范式,。,任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下：,消去联结词,“,”,和,“,”,利用双重否定律消去否定联结词,“,”,或利用德摩根律将否定联结词,“,”,移到各命题变元前,(,内移,),。,利用分配律，结合律将公式归约为合取范式和析取范式。,【,例1.21,】,求命题公式,(,p,q)p,的合取范式和析取范式。,解：,求合取范式,(,p,q,),p,(,p,q,),p,)(,p,(,p,q,)(,消去,),(,(,p,q,),p,)(,p,(,p,q,)(,消去,),(,p,q,),p,)(,p,(,p,q,)(,内移,),(,p,p,)(,q,p,)(,p,p,q,)(,分配律，合取范式,),1(,q,p,)(1,q,)(,排中律,),1(,q,p,)1 (,零律，合取范式,),(,q,p,),(,同一律,，,合取范式,),由此例可以看出，公式的合取范式并不惟一。,求析取范式,(,p,q,),p,(,p,q,),p,),(,p,q,),p,)(,消去,),(,p,q,),p,),(,p,q,),p,)(,内移,),p,(,p,q,p,)(,吸收律,，,析取范式,),p,(,p,p,q,)(,交换律,),p,(,p,q,)(,幂等律,，,析取范式,),由此例可以看出，命题公式的析取范式也不惟一。,1.5.2,主析取范式,由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。,析取范式和合取范式的基本成分是基本积和基本和，而主析取范式和主合取范式的基本成分是极小项和极大项，它们分别是特殊的基本积和基本和,。,定义,1.5.5,在基本积中，每个变元及其否定不同时存在，,但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取也叫小项或极小项。,p,，,q,的极小项为：,p,q,，,p,q,，,p,q,，,p,q,两个命题变元的极小项共,4(=2,2,)个,三个命题变元的极小项共,8(=2,3,)个,。一般地说，,n,个命题变元共有,2,n,个极小项。,表,1.12,是两个变元,p,和,q,的极小项的真值表。极小项有下列的性质：,每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码，并把编码作为,m,的下标来表示该极小项，叫做该极小项的名称。,两个命题变元的极小项、成真赋值,和名称如表,1.13,所示。,三个命题变元的极小项，成真赋值和名称如表,1.14,所示。,从表,1.13,和表,1.14,中可以看出，极小项与其成真赋值的对应关系为：变元对应,1,，而变元的否定对应,0,。,表1.12,p,q,p,q,p,q,p,q,p,q,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,1,1,1,0,0,0,表1.13,极小项,成真赋值,名称,p,q,00,m,0,p,q,01,m,1,p,q,10,m,2,p,q,11,m,3,表1.14,极小项,成真赋值,名称,p,q,r,000,m,0,p,q,r,001,m,1,p,q,r,010,m,2,p,q,r,011,m,3,p,q,r,100,m,4,p,q,r,101,m,5,p,q,r,110,m,6,p,q,r,111,m,7,任意两个不同的极小项的合取式为永假式。,例如：,m,001,m,100,(,p,q,r,)(,p,q,r,),p,q,r,p,q,r,0,全体极小项的析取式为永真式。记为：,m,0,m,1,1,定义,1.5.6,对于给定的命题公式，如果有一个它的等价公式，仅由,极,小项的析取组成，称该公式为原公式的主析取范式,。,任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得：,等价演算法：即用基本等价公式推出。,用等价演算法求主析取范式的步骤如下：,化归为析取范式。,除去析取范式中所有永假的基本积。,在基本积中，将重复出现的合取项和相同变元合并。,在基本积中补入没有出现的命题变元，即添加,(,p,p,),，,再用分配律展开，最后合并相同的极小项。,【例,1.22,】,用等价演算法求,(,p,q,),(,p,r,),(,q,r,),的主析取范式。,解,：,(,p,q,)(,p,r,)(,q,r,),(,p,q,(,r,r,)(,p,r,(,q,q,)(,q,r,(,p,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,)(,p,q,r,)(,p,q,r,),m,111,m,110,m,011,m,001,m,7,m,6,m,3,m,1,1，3，6，7,真值表法：即用真值表求主析取范式。,用真值表求主析取范式的步骤如下：,构造命题公式的真值表。,找出,公式的成真赋值对应的极小项。,这些极小项的析取就是此公式的主析取范式。,【例,1.24,】,用真值表法，求,(,p,q,),r,的主析取范式。,解：,表,1.15是(,p,q,),r,的真值表，公式的成真赋值对应 的极小项为：,p,q,r,(,成真赋值为,001),p,q,r,(,成真赋值为,011),p,q,r,(,成真赋值为,100),p,q,r,(,成真赋值为,101),p,q,r,(,成真赋值为,111),(,p,q,),r,的主析取范式为：,(,p,q,r,)(,p,q,r,)(,p,q,r,)(,p,q,r,),(,p,q,r,),m,111,m,101,m,100,m,011,m,001,m,7,m,5,m,4,m,3,m,1,1，3，4，5，7,表1.15,p,q,r,p,q,(,p,q,),r,0,0,0,1,0,0,0,1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,矛盾式无成真赋值，因而主析取范式不含任何极小项，将矛盾式的主析取范式记为,0,。而重言式无成假赋值，因而主析取范式含,2,n,(,n,为公式中命题变元的个数,),个极小项。至于可满足式，它的主析取范式中极小项的个数一定小于等于,2,n,。,1.5.3,主合取范式,定义,1.5.7,在基本和中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本和叫作布尔析取，也叫大项或极大项。,两个变元,p,，,q,构成的极大项为：,p,q,，,p,q,，,p,q,，,p,q,三个命题变元,p,，,q,，,r,构成的极大项为：,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,两个命题变元的极大项共,4(=2,2,),个,三个命题变元的极大项共,8(=2,3,),个,。一般地说，,n,个变元共有,2,n,个极大项。,极大项有下列三个性质：,每个极大项只有一个成假赋值，极大项不同，成假赋值也不同。极大项和它的成假赋值构成了一一对应的关系。故可用成假赋值为该极大项进行编码，并把编码作为,M,的下标来表示该极大项，叫做极大项的名称。,例如，两个变元,p,，,q,的极大项,p,q,，,它的成假赋值是,11,，表示为,M,11,，,把11,理解为,2,进制数，它的,10,进制表示为,3,，所以,M,11,又表示为,M,3,。,表1.16,极大项,成假赋值,名称,p,q,00,M,0,p,q,01,M,1,p,q,10,M,2,p,q,11,M,3,两个命题变元的极大项，成假赋值及名称见表,1.16,，三个命题变元的极大项，成假赋值及名称见表,1.17,。,从表,1.16,和表,1.17,中可以看出，极大项与成假赋值的对应关系为：变元对应,0,，而变元的否定对应,1,。,任意两个不同的极大项的析取式为永真式。,全体极大项的合取式为永假式。记为：,表1.17,极大项,成假赋值,名称,p,q,r,000,M,0,p,q,r,001,M,1,p,q,r,010,M,2,p,q,r,011,M,3,p,q,r,100,M,4,p,q,r,101,M,5,p,q,r,110,M,6,p,q,r,111,M,7,M,0,M,1,0,定义,1.5.8,对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的主合取范式。,任何命题公式都存在着与之等价的主合取范式。主合取范式也可以由以下两种方法求得。,等价演算法：即用基本等价公式推出。,其演算步骤如下：,化归为合取范式。,除去所有永真的基本和。,在基本和中合并重复出现的析取项和相同的变元。,在基本和中补入没有出现的命题变元。即增加,(,p,p,),，,然后，应用分配律展开公式，最后合并相同的极大项。,【例1.25】,用等价演算法求,(,p,q,),r,的主合取范式。,解：,(,p,q,),r,(,p,q,),r,(,p,q,),r,(,p,r,),(,q,r,),(,p,r,(,q,q,),(,q,r,(,p,p,),(,p,r,q,)(,p,r,q,)(,p,q,r,)(,p,q,r,),(,p,q,r,)(,p,q,r,)(,p,q,r,),M,000,M,010,M,110,M,0,M,2,M,6,0，2，6,真值表法：用真值表求主合取范式。,用真值表求主,合,取范式的步骤如下：,构造命题公式的真值表。,找出公式的成假赋值对应的极大项。,这些极大项的析取就是此公式的主合取范式。,【例,1.26,】,用真值表法求,(,p,q,),r,的主合取范式。,解,：,(,p,q,),r,的真值表是表,1.15,。公式的成假赋值对应的大项为：,p,q,r,(,成假赋值为,000),p,q,r,(,成假赋值为,010),p,q,r,(,成假赋值为,110),主合取范式为：,(,p,q,r,),(,p,q,r,),(,p,q,r,),M,000,M,010,M,110,M,0,M,2,M,6,0,，,2,，,6,矛盾式无成真赋值，因而矛盾式的主合取范式含,2,n,(,n,为公式中命题变元的个数,),个极大项。而重言式无成假赋值，因而主合取范式不含任何极大项。将重言式的主合取范式记为,1,。至于可满足式，它的主合取范式中极大项的个数一定小于,2,n,。,在例,1.23,和例,1.24,中求出,(,p,q,),r,的主析取范式为：,m,7,m,5,m,4,m,3,m,1,1,，,3,，,4,，,5,，,7,在例,1.25,和例,1.26,中求出该公式的主合取范式为：,M,0,M,2,M,6,0,，,2,，,6,比较这两个结果，得出以下的结论：同一公式的主析取范式中,m,的下标和主合取范式中,M,的下标是互补的。因此，知道了主析,(合),取范式就可以写出主合,(析),取范式。,返回章目录,1.6,全功能联结词集,定义,1.6.1,设,p,和,q,是两个命题，复合命题,p q,称作,p,和,q,的不可兼析取，也叫异或。定义为：,p q,为,T,当且仅当,p,和,q,的真值不相同时。联结词,“”,称为异或联结词。,表,1.18,p,q,0,0,0,0,1,1,1,0,1,1,1,0,p,q,联结词,“”,的真值表,如表,1.18,所示。,“”,也可以看成逻辑,运算，它是二元逻辑运算。它在程序设中有广泛的引用。,不可兼析取有下列的性质,：,p q,q p,(,交换律,),(,p q,),r,p,(,q r,)(,结合律,),p,(,q r,),(,p,q,)(,p,r,)(,合取对异或的分配律,),p q,(,p,q,),(,p,q,),p q,(,p,q,),p p,0,，,0,p,p,，,1,p,p,定理,1.6.1,设,A,，,B,，,C,为命题公式，如果,A B,C,，,则,A C,B,，,B C,A,，,A B C,为一矛盾式。,定义,1.6.2,设,p,和,q,是两个命题，复合命题,p,q,称作,p,和,q,的与非。定义为：当且仅当,p,和,q,真值都是真时，,p,q,才为假。联结词,“,”,称为与非联结词。,联结词,“,”,的真值表如表,1.19,所示。,“,”,也可以看成逻辑运算，它是二元逻辑运算。,由定义可以看出下式成立：,p,q,(,p,q,),联结词,“,”,还有以下几个性质：,表1.19,p,q,p,q,0,0,1,0,1,1,1,0,1,1,1,0,p,p,(,p,p,),p,(,p,q,),(,p,q,),(,p,q,),(,p,q,),p,q,(,p,p,),(,q,q,),(,p,),(,q,),(,p,q,),p,q,定义,1.6.3,设,p,和,q,是两个命题，复合命题,p,q,称作,p,和,q,的或非。定义为：当且仅当,p,、,q,的真值都为假时，,p,q,的真值为真。联结词,“,”,称为或非联结词。,联结词,“,”,的真值表如表,1.20,所示。,“,”,也可以看成逻辑运算，它是二元逻辑运算。,表1.20,p,q,p,q,0,0,1,0,1,0,1,0,0,1,1,0,由此定义可得到下面的公式：,p,q,(,p,q,),联结词还有下面的几个性质：,p,p,(,p,p,),p,(,p,q,),(,p,q,),(,p,q,),(,p,q,),p,q,(,p,p,),(,q,q,),p,q,(,p,q,),p,q,至此已经学了,8,个联结词：,，,，。类似于定义,1.2.1,的方法，可以定义包含上述,8,个联结词的命题公式。,定义,1.6.4,设,S,是一个联结词集合，如果任何,n,(,n,1),个变元组成的公式，都可以由,S,中的联结词来表示，则称,S,是全功能联结词集。,根据命题公式的定义,，,，,是全功能联结词集。,利用下列,3,个等价式可将任何命题公式中的命题联结词,“”,、,“,”和“,”,去掉。,p q,(,p,q,),p,q,(,p,q,),p,q,(,p,q,),所以,，,是全功能联结词集。,利用下列,2,个等价式可将任何命题公式中的,命题,联结词,“,”,和,“,”,去掉。,p,q,p,q,p,q,(,p,q,)(,q,p,),(,p,q,)(,q,p,),所以,，,是全功能联结词集。,用德摩根律可证明,，,和,，,是全功能联结词集。,可以证明,，,和,，,的任何子集都不是全功能联结词集。,定义,1.6.5,设,S,是全功能联结词集，如果去掉其中的任何 联结词后，就不是全功能联结词集，则称,S,是最小全功能联结词集。,可以证明,，,，,，,，,，,是最小全功能联结词集。,现在讨论，,n,个命题变元可以构成多少个不等价的命题公式。,两个命题变元可以构成多少个不等价的命题公式？,由等价的概念知道，等价的命题公式有相同的真值表，所以上述问题就转化为两个命题变元构成的命题公式有多少个不同的真值表？,表1.21,p,q,公式,0,0,1,或,0,0,1,1,或,0,1,0,1,或,0,1,1,1,或,0,两个命题变元构成的命题公式的真值表的格式如表,1.21,所示。真值表中每行公式的真值都有,1,，,0,两种可能，所以,命题,公式的真值有,2,2,2,2=2,4,=16,种可能，既有 个不同的真值表。故有 种不等价的公式。,返回章目录,三个变元可构成,2,8,=,个不等价的命题公式，,n,个变元可构成 个不等价的命题公式。,1.7,对偶式与蕰含式,1.7.1,对偶式,从,1.3,节的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的,“,”,和,“,”,分别换成,“,”,和,“,”,，就可以由一个得到另一个。例如，将命题定律,(,A,B,),C,A,(,B,C,),中的,“,”,换成,“,”,就得到了命题定律,(,A,B,),C,A,(,B,C,),。,这些成对出现的等价式反映了等价的对偶性。本节介绍对偶式和对偶原理。,定义,1.7.1,在仅含联结词,，的命题公式,A,中，将联结词，,F,，,T,分别换成，,T,，,F,所得的公式称为公式,A,的对偶式，记为,A,*,。,设,A,*,是,A,的对偶式，将,A,*,中的，,F,，,T,分别换成，,T,，,F,，,就会得到,A,。,即,A,是,A,*,的对偶式，,(,A,*)*,A,。,所以说,A,*,和,A,互为对偶式。,【例,1.27,】求,p,q,和,p,q,的对偶式。,解,：,p,q,(,p,q,),(,p,q,),的对偶式是,(,p,q,),p,q,故,p,q,的对偶式是,p,q,；,同样的方法可以证明,p,q,的对偶式是,p,q,。,根据例,1.27,，对偶式概念可以推广为：在仅含有联结词,，的命题公式中，将联结词，,F,，,T,分别换成,，,T,，,F,，,就得到了它的对偶式。,关于对偶式有以下两个结论。,定理,1.7.1,设,A,*,是,A,的对偶式，,p,1,，,p,2,，,p,n,是出现在,A,和,A,*,中的原子变元，则,A,(,p,1,，,p,2,，,，,p,n,),A,*(,p,1,，,p,2,，,，,p,n,),A,(,p,1,，,p,2,，,，,p,n,),A,*(,p,1,，,p,2,，,，,p,n,),【例,1.28,】,设命题公式,A,(,p,q,r,),(,p,q,),r,，,试用此公式验证定理,1.7.1,的有效性。,证明：,验证,A,(,p,q,r,),A,*(,p,q,r,),A,(,p,q,r,),(,p,q,),r,A,(,p,q,r,),(,p,q,),r,),(,p,q,),r,A,*(,p,q,r,),(,p,q,),r,A,*(,p,q,r,),(,p,q,),r,所以，,A,(,p,q,r,),A,*(,p,q,r,),验证,A,(,p,q,r,),A,*(,p,q,r,),A,(,p,q,r,