真值表公式分类命题定律代入置换

关于真值表公式分类命题定律代入置换第1页，共39页，2022年，5月20日，13点32分，星期五复习引论：离散数学、数理逻辑命题联结词第2页，共39页，2022年，5月20日，13点32分，星期五复习题：本命题是假的。我不给所有自己给自己理发的人理发，但是却会给所有自己不给自己理发的人理发。第3页，共39页，2022年，5月20日，13点32分，星期五本节内容命题符号化第4页，共39页，2022年，5月20日，13点32分，星期五命题分类与命题变元命题原子命题：不包含任何联结词的命题复合命题：至少包含一个联结词的命题命题变元一个不确定的泛指的任意命题定义：以真(1)、假(0)为其变域的变元注意：命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假（对该命题变元指派真值）命题公式含有命题变元的断言称为命题公式注意：不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。第5页，共39页，2022年，5月20日，13点32分，星期五合式公式原子公式定义：单个命题变元和命题常元称为原子命题公式，简称原子公式。合式公式合式公式是由下列规则生成的公式：①单个原子公式是合式公式。②若A是一个合式公式，则(lA)也是一个合式公式。③若A、B是合式公式，则(A∧B)、(A∨B)、(A→B)和(AB)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。第6页，共39页，2022年，5月20日，13点32分，星期五合式公式(Cont.)例：下列符号串是否为命题公式。（1）P→(Q∧PR）；

（2）（P∨Q）→（¬（Q∧R））第7页，共39页，2022年，5月20日，13点32分，星期五合式公式(Cont.)当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：①优先级由高到低的次序为：l、∧、∨、→、②相同的联结词按从左至右次序计算时，圆括号可省略。③最外层的圆括号可以省略。

第8页，共39页，2022年，5月20日，13点32分，星期五合式公式(Cont.)例子

¬P∨¬P∨Q∧¬S∨¬Q∧R

与(((¬(P)∨¬(P))∨(Q∧¬(S))∨(¬(Q)∧R))

运算顺序完全一样,前者不加一个括号.

请大家特别注意先∧后∨的习惯.第9页，共39页，2022年，5月20日，13点32分，星期五命题符号化

有了联结词的合式公式概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式第10页，共39页，2022年，5月20日，13点32分，星期五命题的符号化把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为命题的符号化。符号化应注意以下几点：①确定句子是否为命题.不是就不必翻译.②确定句中连接词是否能对应于并且对应于哪一个命题连接词.③正确表示原子命题和选择命题连接词.④要按逻辑关系翻译而不能凭字面翻译.第11页，共39页，2022年，5月20日，13点32分，星期五命题的符号化(Cont.)例：试以符号形式写出命题:我们要做到身体好,学习好,工作好,为祖国四化建设而奋斗.解:A:我们要做到身体好

B:我们要做到学习好

C:我们要做到工作好

P:我们要为祖国四化建设而奋斗故命题可以表示为:第12页，共39页，2022年，5月20日，13点32分，星期五命题的符号化(Cont.)张三和李四同在做作业

P:张三做作业

Q:李四做作业 可译为P∧Q;张三和李四是兄弟

第13页，共39页，2022年，5月20日，13点32分，星期五命题的符号化(Cont.)“这盆花盛开，促使那些蜜蜂来采蜜”不可以符号化,为什么呢？ 因为连接词‘促使’不是命题连接词.根据是由它构成的复合命题的真值不能完全由构成它的原子命题的真值来确定.例如令P:这盆花盛开,值为1，Q:那些蜜蜂来采蜜,其值为1,则‘这盆花盛开促使那些蜜蜂来采蜜’值为1.又令P:海水是咸的,其值为1,Q:那些蜜蜂来采蜜值为1,则‘海水是咸的促使那些蜜蜂来采蜜’值为0.

由此可见,两组原命题都为真,但由‘促使’构成的复合命题的值一为真一为假,这不符合定义.第14页，共39页，2022年，5月20日，13点32分，星期五注意

自然语言中的一些联结词,如与”,“且”,“或”,“除非…则…”等等都各有其具体含义,需分别不同情况翻译成合适的逻辑联结词.

有时可以采用真值表的方式,来寻找合适的逻辑联结词第15页，共39页，2022年，5月20日，13点32分，星期五练习题派小王或小李出差；我们不能既划船又跑步；如果你来了，那么他唱不唱歌将看你是否伴奏而定；如果李明是体育爱好者，但不是文艺爱好者，那么李明不是文体爱好者；假如上午不下雨，我去看电影，否则就在家里看书。辱骂和恐吓决不是战斗除非天气好，否则我是不会去公园的第16页，共39页，2022年，5月20日，13点32分，星期五几个例子‘除非你努力，否则你将失败’可以符号化为：

¬P→Q,其中P:你努力，Q:你将失败.‘只有睡好觉才能恢复疲劳’可以符号化为：Q→P,其中P:睡好觉，Q:恢复疲劳.(Q是P的必要条件)第17页，共39页，2022年，5月20日，13点32分，星期五公式真值表真值指派为含有命题变元P1，P2，…,Pn的命题公式，对P1，P2，…,Pn分别指定一个真值，称为对公式的一组真值指派。在公式中，对于命题变元指派真值的各种可能组合，就确定了这个命题的各种真值情况，把它汇列成表，就是命题公式的真值表公式真值表构造方法：（1）找出公式中的全部命题变元，并按一定的顺序排列成P1，P2，…,Pn。（2）列出的2n个解释，赋值从00…0（n个）开始，按二进制递加顺序依次写出各赋值，直到11…1为止（或从11…1开始，按二进制递减顺序写出各赋值，直到00…0为止），然后从低到高的顺序列出的层次。（3）根据赋值依次计算各层次的真值并最终计算出的真值。第18页，共39页，2022年，5月20日，13点32分，星期五公式真值表(Cont.)例1：构造PQ的真值表例2：构造¬P∨Q的真值表第19页，共39页，2022年，5月20日，13点32分，星期五公式分类定义：设A为任意公式，则①对应每一个指派，公式A均相应确定真值为真，称A

为重言式，或永真式。②对应每一个指派，公式A均相应确定真值为假，称A

为矛盾式，或永假式。③至少存在一个指派，公式A相应确定真值为真，称A为可满足式。第20页，共39页，2022年，5月20日，13点32分，星期五公式分类(Cont.)由定义可知，重言式必是可满足式，反之一般不真。重点将研究重言式，它最有用，因为它有以下特点：①重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。②两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。③由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。第21页，共39页，2022年，5月20日，13点32分，星期五公式分类(Cont.)判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。在Ls中，由于任何一个命题公式的指派数目总是有限的，所以Ls的判定问题是可解的。其判定方法有真值表法和公式推演法。第22页，共39页，2022年，5月20日，13点32分，星期五等价公式定义：设A和B是两个命题公式，设P1,P2,…,Pn为所有出现于A和B中的命题变元,若给P1,P2,…,Pn任一组真值指派,A和B的真值都是相同的，则称A和B是等价的，或逻辑相等，记作AB，读作A等价B，称AB为等价式。

若公式A和B的真值表是相同的，则A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。第23页，共39页，2022年，5月20日，13点32分，星期五和的区别与联系区别：是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。联系：定理：

A

B当且仅当AB是永真式。第24页，共39页，2022年，5月20日，13点32分，星期五等价公式的性质①自反性，即对任意公式A，有A

A。②对称性，即对任意公式A和B，若A

B，则B

A。③传递性，即对任意公式A、B和C，若A

B、B

C，则A

C。第25页，共39页，2022年，5月20日，13点32分，星期五基本等价式——命题定律在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一。第26页，共39页，2022年，5月20日，13点32分，星期五(1)双否定：AA。(2)交换律：A∧BB∧A，A∨BB∨A，ABBA。第27页，共39页，2022年，5月20日，13点32分，星期五(3)结合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，(AB)CA(BC)。(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∧AA，A∨AA。第28页，共39页，2022年，5月20日，13点32分，星期五(7)同一律：A∧TA，A∨FA。(8)零律：A∧FF，A∨TT。(9)吸收律：A∧(A∨B)A，A∨(A∧B)A。(10)互补律：A∧AF，(矛盾律) A∨AT。(排中律)(11)条件式转化律：A→BA∨B，A→BB→A。第29页，共39页，2022年，5月20日，13点32分，星期五(12)双条件式转化律：AB(A→B)∧(B→A)(A∧B)∨(A∧B)AB(AB)(13)输出律：(A∧B)→CA→(B→C)。(14)归谬律：(A→B)∧(A→B)A。上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。第30页，共39页，2022年，5月20日，13点32分，星期五代入规则和替换规则

在定义合成公式时，已看到了逻辑联结词能够从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介绍“代入”和“替换”，它们也有从已知公式得到新的公式的作用。第31页，共39页，2022年，5月20日，13点32分，星期五代入规则定理1.3.2

在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式。本定理称为代入规则。例子：课本例1.3.4第32页，共39页，2022年，5月20日，13点32分，星期五替换规则定理1.3.3

设A1是合式公式A的子公式，若A1B1