1.2真值表、公式分类、命题定律、代入置换.ppt

《1.2真值表、公式分类、命题定律、代入置换.ppt》由会员分享，可在线阅读，更多相关《1.2真值表、公式分类、命题定律、代入置换.ppt（38页珍藏版）》请在三一办公上搜索。

1、符号化、公式分类命题定律、代入置换,授课教师：程文刚,复习,引论：离散数学、数理逻辑命题联结词,复习题：,本命题是假的。我不给所有自己给自己理发的人理发，但是却会给所有自己不给自己理发的人理发。,本节内容,命题符号化,命题分类与命题变元,命题原子命题：不包含任何联结词的命题复合命题：至少包含一个联结词的命题命题变元一个不确定的泛指的任意命题定义：以真(1)、假(0)为其变域的变元注意：命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假（对该命题变元指派真值）命题公式含有命题变元的断言称为命题公式注意：不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。,合式公式,原

2、子公式定义：单个命题变元和命题常元称为原子命题公式，简称原子公式。合式公式合式公式是由下列规则生成的公式：单个原子公式是合式公式。若A是一个合式公式，则(lA)也是一个合式公式。若A、B是合式公式，则(AB)、(AB)、(AB)和(A B)都是合式公式。只有有限次使用、和生成的公式才是合式公式。,合式公式(Cont.),例：下列符号串是否为命题公式。（1）P(QPR）；（2）（PQ）（QR）,合式公式(Cont.),当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：优先级由高到低的次序为：l、相同的联结词按从左至右次序计算时，圆括号可省略。最外层的圆括号可以省略。

3、,合式公式(Cont.),例子 PPQSQR 与(P)(P)(Q(S)(Q)R)运算顺序完全一样,前者不加一个括号.请大家特别注意先后的习惯.,命题符号化,有了联结词的合式公式概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式,命题的符号化,把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为命题的符号化。符号化应注意以下几点：确定句子是否为命题.不是就不必翻译.确定句中连接词是否能对应于并且对应于哪一个命题连接词.正确表示原子命题和选择命题连接词.要按逻辑关系翻译而不能凭字面翻译.,命题的符号化(Cont.),例：试以符号形式写出命题:我们要做到身体

4、好,学习好,工作好,为祖国四化建设而奋斗.解:A:我们要做到身体好 B:我们要做到学习好 C:我们要做到工作好 P:我们要为祖国四化建设而奋斗故命题可以表示为:,命题的符号化(Cont.),张三和李四同在做作业P:张三做作业 Q:李四做作业可译为PQ;张三和李四是兄弟,命题的符号化(Cont.),“这盆花盛开，促使那些蜜蜂来采蜜”不可以符号化,为什么呢？因为连接词促使不是命题连接词.根据是由它构成的复合命题的真值不能完全由构成它的原子命题的真值来确定.例如令 P:这盆花盛开,值为1，Q:那些蜜蜂来采蜜,其值为1,则这盆花盛开促使那些蜜蜂来采蜜值为1.又令 P:海水是咸的,其值为1,Q:那些蜜蜂

5、来采蜜值为1,则海水是咸的促使那些蜜蜂来采蜜 值为0.由此可见,两组原命题都为真,但由促使构成的复合命题的值一为真一为假,这不符合定义.,注意,自然语言中的一些联结词,如与”,“且”,“或”,“除非 则”等等都各有其具体含义,需分别不同情况翻译成合适的逻辑联结词.有时可以采用真值表的方式,来寻找合适的逻辑联结词,练习题,派小王或小李出差；我们不能既划船又跑步；如果你来了，那么他唱不唱歌将看你是否伴奏而定；如果李明是体育爱好者，但不是文艺爱好者，那么李明不是文体爱好者；假如上午不下雨，我去看电影，否则就在家里看书。辱骂和恐吓决不是战斗除非天气好，否则我是不会去公园的,几个例子,除非你努力，否则你

6、将失败 可以符号化为：PQ,其中 P:你努力，Q:你将失败.只有睡好觉才能恢复疲劳可以符号化为：QP,其中 P:睡好觉，Q:恢复疲劳.(Q是P的必要条件),公式真值表,真值指派为含有命题变元P1，P2，,Pn的命题公式，对P1，P2，,Pn分别指定一个真值，称为对公式的一组真值指派。在公式中，对于命题变元指派真值的各种可能组合，就确定了这个命题的各种真值情况，把它汇列成表，就是命题公式的真值表公式真值表构造方法：（1）找出公式中的全部命题变元，并按一定的顺序排列成P1，P2，,Pn。（2）列出的2n个解释，赋值从000（n个）开始，按二进制递加顺序依次写出各赋值，直到111为止（或从111开始

7、，按二进制递减顺序写出各赋值，直到000为止），然后从低到高的顺序列出的层次。（3）根据赋值依次计算各层次的真值并最终计算出的真值。,公式真值表(Cont.),例1：构造P Q的真值表例2：构造P Q的真值表,公式分类,定义：设 A 为任意公式，则 对应每一个指派，公式 A 均相应确定真值为真，称 A 为重言式，或永真式。对应每一个指派，公式 A 均相应确定真值为假，称 A 为矛盾式，或永假式。至少存在一个指派，公式 A 相应确定真值为真，称 A 为可满足式。,公式分类(Cont.),由定义可知，重言式必是可满足式，反之一般不真。重点将研究重言式，它最有用，因为它有以下特点：重言式的否定是矛盾

8、式，矛盾式的否定是重言式，这样只研究其一就可以了。两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。,公式分类(Cont.),判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。在Ls中，由于任何一个命题公式的指派数目总是有限的，所以Ls的判定问题是可解的。其判定方法有真值表法和公式推演法。,等价公式,定义：设A和B是两个命题公式，设P1,P2,Pn为所有出现于A和B中的命题变元,若给P1,P2,Pn任一组真值指派,A和B的真值都是相同的，则称A和B是等价的，或逻辑相等

9、，记作AB，读作A等价B，称AB为等价式。若公式A和B的真值表是相同的，则A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。,和的区别与联系,区别：是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。联系：定理：A B当且仅当AB是永真式。,等价公式的性质,自反性，即对任意公式A，有A A。对称性，即对任意公式A和B，若A B，则B A。传递性，即对任意公式A、B和C，若A B、B C，则A C。,基本等价式命题定律,在判定公式间是否等价，有一些简单而又经常使用的等价式，称

10、为基本等价式或称命题定律。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一。,(1)双否定：AA。(2)交换律：ABBA，ABBA，ABBA。,(3)结合律：(AB)CA(BC)，(AB)CA(BC)，(AB)CA(BC)。(4)分配律：A(BC)(AB)(AC)，A(BC)(AB)(AC)。(5)德摩根律：(AB)AB，(AB)AB。(6)等幂律：AAA，AAA。,(7)同一律：ATA，AFA。(8)零 律：AFF，ATT。(9)吸收律：A(AB)A，A(AB)A。(10)互补律：AAF，(矛盾律)AAT。(排中律)(11)条件式转化律：ABAB，ABBA。,(12)双条件式转化律：AB(

11、AB)(BA)(AB)(AB)AB(AB)(13)输出律：(AB)CA(BC)。(14)归谬律：(AB)(AB)A。上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。,代入规则和替换规则,在定义合成公式时，已看到了逻辑联结词能够从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介绍“代入”和“替换”，它们也有从已知公式得到新的公式的作用。,代入规则,定理1.3.2 在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式。本定理称为代入规则。例子：课本例1.3.4,替换规则,定

12、理1.3.3 设A1是合式公式A的子公式，若A1B1，并且将A中的A1用B1 替换得到公式B，则AB。称该定理为替换规则。满足定理1.3.3条件的替换，称为等价替换。例子：课本 例1.3.5&例1.3.6,代入和替换有两点区别：代入是对原子命题变元而言的，而替换可对命题公式实行。代入必须是处处代入，替换则可部分替换，亦可全部替换。,总结,真值表公式分类、等价公式命题定律代入置换,思考题,在某研讨会的休息时间，名与会者根据王教授的口音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人；乙说王教授不是上海人，是苏州人；丙说王教授既不是上海人，也不是杭州人。听完以上 人的判断后，王教授笑着说，他们 人中有一人说的全对，有一人说对了一半，另一人说的全不对。试问王教授是哪里人？,下次课程,对偶、蕴涵和其他联结词,Thank you,