3-第一章命题逻辑

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息工程学院,大连大学,第一章 命题逻辑,1.1,命题及其表示法,1.2,联结词,1.3,命题公式与翻译,1.4,真值表与等价公式,1.5,重言式与蕴含式,1.7,对偶与范式,1.8,推理理论,Propositional Logic,第一章 命题逻辑,1.1,命题及其表示法,1.2,联结词,1.3,命题公式与翻译,1.4,真值表与等价公式,1.5,重言式与蕴含式,1.7,对偶与范式,1.8,推理理论,Propositional Logic,第,10,页,定义,1-3.1,命题合式公式,(Well-formed formula,wff,),（,1,）单个命题变元本身是合式公式。,（,2,）若,A,是合式公式，则,(,A),也是合式公式。,（,3,）若,A,，,B,是合式公式，则,(AB),，,(AB),，,(A,B),，,(A,B),也是合式公式。,（,4,）当且仅当有限次地应用,(1)(3),所得到的包含命题变元、联结词和括号的符号串是合式公式。,1.3,命题公式与翻译,第,10,页,1.3,命题公式与翻译,例：判断下列式子是否是合适公式,第,12,页,例,1,给出 的真值表。,练习：给出下列命题公式的真值表。,（,1,）,（,2,）,1.4,真值表与等价公式,n,个命题变元组成的命题公式共有,2,n,种赋值（指派）。,定义,1-4.2,设,A,B,为两个命题公式，若,A,B,构成的,双条件,A,B,为重言式，则称,A,与,B,是,等价的（等值的）记作,A B,。,第,12,页,1.4,真值表与等价公式,第,13,页,1.4,真值表与等价公式,定义,1-4.3,如果,X,是合式公式,A,的一部分，且,X,本身,也是一个合式公式，则称,X,为公式,A,的,子公式,。,定理,1-4.1,设,X,是合式公式,A,的子公式，若,X Y,，,如果将,A,中的,X,用,Y,来置换，所得到公式,B,与公式,A,等价，即,A B,。,第,16,页,复习,练习,1,：化简下面的式子。,（,1,）,（,2,）,第一章 命题逻辑,1.1,命题及其表示法,1.2,联结词,1.3,命题公式与翻译,1.4,真值表与等价公式,1.5,重言式与蕴含式,1.7,对偶与范式,1.8,推理理论,Propositional Logic,第,16,页,1.7,对偶与范式,定义,1-7.1,在给定的命题公式中，如果它仅用联结词 ，则将联结词 换成 ，将 换成 ，若有特殊变元,F,和,T,亦相互取代，所得公式称为原,公式的对偶式。,例,1,：写出下列表达式的对偶式,一、对偶式,对偶式的作用,见书上,30,页,定理,7.1-7.2,第,17,页,1.7,对偶与范式,二、范式,定义,1-7.2,一个命题公式称为合取范式，当且仅当,它具有型式：,其中 都是由命题变元或其否定所组成,的析取式。,合取范式的特点：,（,1,）不出现 和 （,2,）否定符号出现在变元前,（,3,）总体看是合取式（,4,）每个合取项是析取式,（,5,）每个合取项中只包含命题变元或其否定。,第,18,页,1.7,对偶与范式,二、范式,定义,1-7.3,一个命题公式称为析取范式，当且仅当,它具有型式：,其中 都是由命题变元或其否定所组成,的合取式。,析取范式的特点：,（,1,）不出现 和 （,2,）否定符号出现在变元前,（,3,）总体看是析取式（,4,）每个析取项是合取式,（,5,）每个析取项中只包含命题变元或其否定。,第,19,页,1.7,对偶与范式,二、范式,例,2:,判断下列各式是否为析取范式或合取范式。,第,20,页,1.7,对偶与范式,二、范式,例,3:,求 合取范式。,例,4:,求 析取范式。,合取范式和析取范式的化归步骤：见书上,31,页,第,20,页,1.7,对偶与范式,三、主范式,例,5:,试求 和,的主析取范式。,例,6:,试求 主析取范式。,主析取范式的化归步骤：见书上,36,页,(1),主析取范式,每个析取项中所有变元都要出现,每个变元只出现一次（命题变元或其否定）,第,20,页,1.7,对偶与范式,三、主范式,定义,1-7.4,n,个变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但,两者必须出现且仅出现一次。,定义,1-7.5,对于给定的命题公式，如果有一个等价,公式，它仅由小项的析取所组成，则该等价式称为原式的主析取范式。,定理,1-7.3,在真值表中，一个公式的真值为,T,的指派所对应的小项的析取，即为此公式的主析取范式。,第,20,页,1.7,对偶与范式,三、主范式,例,7:,试求 的主合取范式。,例,8:,试求 主合取范式。,主合取范式的化归步骤：见书上,38,页,(2),主合取范式,每个合取项中所有变元都要出现,每个变元只出现一次（命题变元或其否定）,第,20,页,1.7,对偶与范式,三、主范式,定义,1-7.6,n,个变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但,两者必须出现且仅出现一次。,定义,1-7.7,对于给定的命题公式，如果有一个等价,公式，它仅由大项的合取所组成，则该等价式称为原式的主合取范式。,定理,1-7.3,在真值表中，一个公式的真值为,T,的指派所对应的大项的合取，即为此公式的主合取范式。,第,21,页,1.7,对偶与范式,例,9:,用真值表求 的主合取范式。,例,10:,求 的成真指派。,例,11:,某科研所要从,3,名科研骨干,A,B,C,中挑选,12,名出国进修，由于工作需要，选派需满足如,下条件：,（,1,）若,A,去，则,C,同去；,（,2,）若,B,去，则,C,不能去；,（,3,）若,C,不去，则,A,或,B,可以去。,问：有几种选派方案,分别都是什么？,