《真值表公式分类命题定律代入置换》由会员分享，可在线阅读，更多相关《真值表公式分类命题定律代入置换（38页珍藏版）》请在金锄头文库上搜索。
1、符号化、公式分类 命题定律、代入置换授课教师：程文刚 复习l引论：离散数学、数理逻辑l命题l联结词复习题：l本命题是假的。l我不给所有自己给自己理发的人理发，但 是却会给所有自己不给自己理发的人理发 。本节内容l命题符号化命题分类与命题变元l命题原子命题：不包含任何联结词的命题复合命题：至少包含一个联结词的命题l命题变元一个不确定的泛指的任意命题定义：l以真(1)、假(0)为其变域的变元注意：命题变元不是命题，只有用一个特定的命题取代才能确定它 的真值：真或假（对该命题变元指派真值）l命题公式含有命题变元的断言称为命题公式注意：不是所有由命题变元、联结词和括号所组成的字符串都能成 为命题公式
2、。合式公式l原子公式定义：单个命题变元和命题常元称为原子命题公式， 简称原子公式。l合式公式 合式公式是由下列规则生成的公式： 单个原子公式是合式公式。 若A是一个合式公式，则(lA)也是一个合式公式。 若A、B是合式公式，则(AB)、(AB)、(AB)和 (A B)都是合式公式。 只有有限次使用、和生成的公式才是合式公 式。合式公式(Cont.)例：下列符号串是否为命题公式。（1） P(QPR）；（2）（PQ）（QR）合式公式(Cont.)l当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：优先级由高到低的次序为：l、 相同的联结词按从左至右次序计算时，圆括号可
3、省略。最外层的圆括号可以省略。合式公式(Cont.)l例子PPQSQR与 (P)(P)(Q(S)(Q)R) 运算顺序完全一样,前者不加一个 括号. l请大家特别注意先后的习惯.命题符号化有了联结词的合式公式概念，我们可以 把自然语言中的有些语句，翻译成数理逻 辑中的符号形式命题的符号化l把一个用文字叙述的命题相应地写成由命题标识 符、联结词和圆括号表示的合式公式，称为命题 的符号化。 符号化应注意以下几点： 确定句子是否为命题.不是就不必翻译. 确定句中连接词是否能对应于并且对应 于哪一个命题连接词. 正确表示原子命题和选择命题连接词. 要按逻辑关系翻译而不能凭字面翻译.命题的符号化(Cont
4、.)例：试以符号形式写出命题: 我们要做到身体 好,学习好,工作好,为祖国四化建设而奋斗. 解: A:我们要做到身体好B:我们要做到学习好C:我们要做到工作好P:我们要为祖国四化建设而奋斗 故命题可以表示为:命题的符号化(Cont.)l张三和李四同在做作业 P:张三做作业 Q:李四做作业 可译为PQ;l张三和李四是兄弟命题的符号化(Cont.)“这盆花盛开，促使那些蜜蜂来采蜜”不可以符 号化,为什么呢？因为连接词促使不是命题连接词.根据 是由它构成的复合命题的真值不能完全由构成 它的原子命题的真值来确定. 例如令 P:这盆花 盛开,值为1，Q:那些蜜蜂来采蜜,其值为1,则 这盆花盛开促使那些蜜
5、蜂来采蜜值为1.又令 P:海水是咸的,其值为1,Q:那些蜜蜂来采蜜值为 1,则海水是咸的促使那些蜜蜂来采蜜 值为 0.由此可见,两组原命题都为真,但由促使 构成的复合命题的值一为真一为假,这不符合 定义.注意自然语言中的一些联结词,如与”,“且”, “或 ”,“除非 则 ”等等都各有其具体含义, 需分别不同情况翻译成合适的逻辑联结词.有时可以采用真值表的方式,来寻找合适 的逻辑联结词练习题l派小王或小李出差；l我们不能既划船又跑步；l如果你来了，那么他唱不唱歌将看你是否伴奏而 定；l如果李明是体育爱好者，但不是文艺爱好者，那 么李明不是文体爱好者；l假如上午不下雨，我去看电影，否则就在家里看
6、书。l辱骂和恐吓决不是战斗l除非天气好，否则我是不会去公园的几个例子l除非你努力，否则你将失败 可以 符号化为： PQ,其中 P:你努力，Q:你将失败.l只有睡好觉才能恢复疲劳可以符 号化为：QP,其中 P:睡好觉，Q:恢 复疲劳.(Q是P的必要条件)公式真值表l真值指派为含有命题变元P1，P2，,Pn的命题公式，对P1，P2， ,Pn分别指定一个真值，称为对公式的一组真值指派。l在公式中，对于命题变元指派真值的各种可能组合 ，就确定了这个命题的各种真值情况，把它汇列成 表，就是命题公式的真值表l公式真值表构造方法：（1）找出公式中的全部命题变元，并按一定的顺序排列成 P1，P2，,Pn 。（
7、2）列出的2n个解释，赋值从000（n个）开始，按二进 制递加顺序依次写出各赋值，直到111为止（或从111 开始，按二进制递减顺序写出各赋值，直到000为止）， 然后从低到高的顺序列出的层次。（3）根据赋值依次计算各层次的真值并最终计算出的真值 。公式真值表(Cont.)例1：构造P Q的真值表例2：构造P Q的真值表公式分类定义： 设 A 为任意公式，则 对应每一个指派，公式 A 均相应确定真值 为真，称 A 为重言式，或永真式。 对应每一个指派，公式 A 均相应确定真值 为假，称 A 为矛盾式，或永假式。 至少存在一个指派，公式 A 相应确定真值 为真，称 A 为可满足式。公式分类(Co
8、nt.)由定义可知，重言式必是可满足式，反之一般不真 。 重点将研究重言式，它最有用，因为它有以下特点 ： 重言式的否定是矛盾式，矛盾式的否定是重言式 ，这样只研究其一就可以了。 两重言式的合取式、析取式、条件式和双条件式 等都仍是重言式。于是，由简单的重言式可构造 出复杂的重言式。 由重言式使用公认的规则可以产生许多有用等价 式和蕴涵式。公式分类(Cont.)l判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。l在Ls中，由于任何一个命题公式的指派数目总是有限的，所以Ls的判定问题是可解的。其判定方法有真值表法和公式推演法。等价公式l定义：设A和B是两个命题公式，设P
9、1,P2, ,Pn为所有出 现于A和B中的命题变元, 若给P1,P2, ,Pn任一组真值指派 , A和B的真值都是相同的，则称A和B是等价的，或逻辑相 等，记作AB，读作A等价B，称AB为等价式。若公式A和B的真值表是相同的，则A和B等价。因此 ，验证两公式是否等价，只需做出它们的真值表即可。和的区别与联系l区别：是逻辑联结词，属于目标语言中 的符号，它出现在命题公式中；不是逻 辑联结词，属于元语言中的符号，表示两 个命题公式的一种关系，不属于这两个公 式的任何一个公式中的符号。l联系：定理： A B当且仅当AB是永真式。等价公式的性质 自反性，即对任意公式A，有A A。 对称性，即对任意公式
10、A和B，若A B，则B A。 传递性，即对任意公式A、B和C，若A B、B C，则A C。基本等价式命题定律l在判定公式间是否等价，有一些简单而又 经常使用的等价式，称为基本等价式或称 命题定律。牢固地记住它并能熟练运用， 是学好数理逻辑的关键之一。l(1)双否定：AA。l(2)交换律：ABBA，ABBA， ABBA。l(3) 结合律：(AB)CA(BC)， (AB)CA(BC)， (AB)CA(BC)。l(4) 分配律：A(BC)(AB)(AC)， A(BC)(AB)(AC)。l(5) 德摩根律：(AB)AB， (AB)AB。l(6) 等幂律：AAA，AAA。l(7) 同一律：ATA，AFA
11、。l(8) 零 律：AFF，ATT。l(9) 吸收律：A(AB)A，A(AB)A。l(10) 互补律：AAF，(矛盾律)AAT。(排中律)l(11) 条件式转化律：ABAB，ABBA。l(12) 双条件式转化律：AB(AB)(BA)(AB)(AB)lAB(AB)l(13) 输出律：(AB)CA(BC)。l(14) 归谬律：(AB)(AB)A。l上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。代入规则和替换规则在定义合成公式时，已看到了逻辑联结词能够从 已知公式形成新的公式，从这个意义上可把逻辑 联结词看成运算。除逻辑联结词外，还要介绍“ 代
12、入”和“替换”，它们也有从已知公式得到新的公 式的作用。代入规则l定理1.3.2 在一个永真式A中，任何一个原 子命题变元R出现的每一处， 用另一个公 式代入，所得公式B仍是永真式。本定理称 为代入规则。l例子 ：课本例1.3.4替换规则l定理1.3.3 设A1是合式公式A的子公式，若 A1B1，并且将A中的A1用B1 替换得到公 式B，则AB。称该定理为替换规则。l满足定理1.3.3条件的替换，称为等价替换 。l例子：课本 例1.3.5 & 例1.3.6l代入和替换有两点区别： 代入是对原子命题变元而言的，而替换可对命题公式实行。 代入必须是处处代入，替换则可部分替换，亦可全部替换。总结l真值表l公式分类、等价公式l命题定律l代入置换思考题l在某研讨会的休息时间， 名与会者根据王 教授的口音对他是哪个省市的人进行了判 断：甲说王教授不是苏州人，是上海人； 乙说王教授不是上海人，是苏州人；丙说 王教授既不是上海人，也不是杭州人。听 完以上 人的判断后，王教授笑着说，他们 人中有一人说的全对，有一人说对了一半 ，另一人说的全不对。试问王教授是哪里 人？下次课程l对偶、蕴涵和其他联结词Thank you
