离散数学-数理逻辑课件.ppt

1、1教材与参考资料教材与参考资料 教材：教材：离散数学离散数学（第（第2版），屈婉玲、耿素云、张立昂编，清华大学版），屈婉玲、耿素云、张立昂编，清华大学出版社出版社 参考资料：参考资料：离散数学离散数学，刘玉珍、刘咏梅编，武汉大学出版社刘玉珍、刘咏梅编，武汉大学出版社 Discrete Mathematical Structures(Sixth Edition)，Bernard Kolman,Fobert C.Busby and Sharon Ross，高等教育出版社有影印版、，高等教育出版社有影印版、译本译本 Discrete Mathematics and Its Applications(

2、Sixth Edition)，美美Kenneth H.Rosen，机械工业出版社影印版、译本，机械工业出版社影印版、译本2课程主要内容 数理逻辑数理逻辑 集合论集合论 图论图论 代数系统代数系统*3目的、意义和要求研究内容：离散量的结构及其相互间的关系。研究内容：离散量的结构及其相互间的关系。意义：计算机科学的理论基础。意义：计算机科学的理论基础。目的：打基础目的：打基础必备的数学知识必备的数学知识培养抽象思维能力、逻辑推理能力培养抽象思维能力、逻辑推理能力教学内容：教学内容：第第1-7 章重点章重点第第9、14章备选章备选第第8、11章自学章自学第第10、12、13章不要求章不要求 4学习要

3、求1、课堂要求：、课堂要求：按时上课按时上课 认真听讲认真听讲2、课外要求：、课外要求：复习复习(每次课后，安排半个小时每次课后，安排半个小时)认真、按时完成作业认真、按时完成作业(每次课后，安排每次课后，安排1个小时个小时)5学习考查方法1、出勤率：、出勤率：10%不定期检查出勤情况不定期检查出勤情况2、作业完成情况：、作业完成情况：10%对作业完成情况进行登记对作业完成情况进行登记3、课堂测验、课堂测验+期中考试：期中考试：20%共共 5 次次4、期末考试（闭卷）：、期末考试（闭卷）：60%6第一篇第一篇 数理逻辑数理逻辑第第1章章 导导 论论 数理逻辑的概念数理逻辑的概念 数理逻辑的发展

4、简史数理逻辑的发展简史 数理逻辑的地位和作用数理逻辑的地位和作用7（1）定义1.1 1.1 数理逻辑的概念数理逻辑的概念 数理逻辑是采用数学方法研究抽象思维推理规律数理逻辑是采用数学方法研究抽象思维推理规律（形式推理）的一门科学。（形式推理）的一门科学。n命题逻辑是数理逻辑的基本组成部分之一命题逻辑是数理逻辑的基本组成部分之一n推理的基本要素是命题推理的基本要素是命题n把命题作为基本单位来分析把命题作为基本单位来分析符号化符号化 研究公式间的关系研究公式间的关系 推导、演算推导、演算 8（2）方法 引入一套引入一套数学符号系统数学符号系统来进行研究，强调推理过来进行研究，强调推理过程中前提和结

5、论之间的形式关系。程中前提和结论之间的形式关系。例：例：A、B、C、D4人做百米竞赛，观众甲、乙、丙预报比赛结果的名次为：人做百米竞赛，观众甲、乙、丙预报比赛结果的名次为：甲：甲：C第一，第一，B第二第二乙：乙：C第二，第二，D第三第三丙：丙：A第二，第二，D第四第四比赛结束后发现甲乙丙每人报告的情况都各对一半，试问实际名次如何？比赛结束后发现甲乙丙每人报告的情况都各对一半，试问实际名次如何？1.引入pi,qi,ri,si分别表示“A排名第i，B排名第i，C排名第i，D排名第i”2.给出个命题之间的关系 （1）(r1 q2)(r1 q2)1 （2）(r2 s3)(r2 s3)1 （3）(p2

6、s4)(p2 s4)13.通过演算规则，得出结果9（3）内容谓词逻辑谓词逻辑命题逻辑命题逻辑10（4）分支模型论模型论证明论证明论公理集合论公理集合论递归论递归论111.2 1.2 数理逻辑的发展简史数理逻辑的发展简史创立阶段起源阶段完善阶段 发展历史发展历史12起源阶段 德国数学家、哲学家德国数学家、哲学家 G.Leibniz（16461716），提出建立一种普遍的符），提出建立一种普遍的符号语言，利用符号语言进行思维演算的设号语言，利用符号语言进行思维演算的设想。想。13创立阶段 英国数学家英国数学家 G.Bool于于1847年发表年发表逻辑的数学分逻辑的数学分析析，创建一套表示逻辑推理的

7、基本符号以及符号的，创建一套表示逻辑推理的基本符号以及符号的运算规律，建立了布尔代数。运算规律，建立了布尔代数。德国数学家德国数学家 G.Frege于于1879年在年在概念的演算概念的演算一书中引进谓词符号和量词符号，创建第一个比较严一书中引进谓词符号和量词符号，创建第一个比较严格的逻辑演算系统。格的逻辑演算系统。14完善阶段 英国逻辑学家英国逻辑学家 A.N.Witehead和和B.Russel于于1910将当时的数理逻辑写入了将当时的数理逻辑写入了数学原理数学原理中，使数理逻中，使数理逻辑成为了一门专门的学科。辑成为了一门专门的学科。20 世纪世纪 30 年代，由于众多科学家的努力，衍生出

8、年代，由于众多科学家的努力，衍生出许多新的分支，如：直觉主义逻辑、多值逻辑、组合许多新的分支，如：直觉主义逻辑、多值逻辑、组合逻辑等。逻辑等。151.3 1.3 数理逻辑的地位和作用数理逻辑的地位和作用1、计算机科学的重要的理论基础之一；、计算机科学的重要的理论基础之一；2、对数学、计算机科学、人工智能、语言学、控、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。制论等诸多学科产生深远的影响。3、在计算机科学中的应用：软件、硬件设计、在计算机科学中的应用：软件、硬件设计16第第2章章 命题逻辑命题逻辑 2.1 命题逻辑基本概念命题逻辑基本概念 2.2 命题逻辑等值演算命题

9、逻辑等值演算 2.3 范式范式 2.4 命题逻辑推理理论命题逻辑推理理论 172.1 命题逻辑基本概念命题逻辑基本概念 2.1.1 命题与联结词命题与联结词 命题与真值命题与真值(简单命题简单命题,复合命题复合命题)联结词联结词(,)2.2.2 命题公式及其分类命题公式及其分类命题公式及其赋值命题公式及其赋值真值表真值表命题公式的分类命题公式的分类 182.1.1 2.1.1 命题与联结词命题与联结词1 1、命题及相关概念、命题及相关概念（1 1）命题的定义）命题的定义两者必居其一且只居其一两者必居其一且只居其一二值逻辑二值逻辑 命题定义的理解：从两个方面把握这个概念（命题定义的理解：从两个方

10、面把握这个概念（1）陈述句；）陈述句；（2）真值唯一性（注意：真值可能目前还不知道答案）。）真值唯一性（注意：真值可能目前还不知道答案）。命题：命题：一个具有真假意义的陈述句。一个具有真假意义的陈述句。什么是真值：只包含真什么是真值：只包含真/假两个值的量。假两个值的量。T/1真真 F/0假假19 注意：（注意：（1）感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题 （2）陈述句中的悖论以及判断结果不唯一确）陈述句中的悖论以及判断结果不唯一确定的也不是命题定的也不是命题20中国的首都在北京。中国的首都在北京。1+1=101+1=10请开门！请开门！x+y=1x+y=1明年明年1

11、010月月1 1日是晴天。日是晴天。本命题是假的。本命题是假的。李红既学英语又学日语。李红既学英语又学日语。例例1 判断下列个自然语言是否是命题判断下列个自然语言是否是命题21（2）几个基本概念）几个基本概念 真命题真命题与与假命题假命题 命题变元命题变元与与命题常元命题常元 真命题真命题:真值为真的命题真值为真的命题 假命题假命题:真值为假的命题真值为假的命题 若若p p即可以表示真命题，又可以表示假命题，则称即可以表示真命题，又可以表示假命题，则称p p为为命题变元。命题变元。T T永远表示真命题，永远表示真命题，F F表示假命题，称表示假命题，称T T和和F F为为命题常元。命题常元。2

12、2例例2 2真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(1),(2),(5)是命题是命题,(3),(4),(6)(8)都不是命题都不是命题真值确定真值确定,但未知但未知 下列句子中哪些是命题？并指出命题的真值。下列句子中哪些是命题？并指出命题的真值。(1)(1)北京是中华人民共和国的首都北京是中华人民共和国的首都.(2)2+5(2)2+5 8.8.(3)(3)x x+5 +5 3.3.(4)(4)你会开车吗？你会开车吗？(5)2050(5)2050年元旦北京是晴天年元旦北京是晴天.(6)(6)这只兔子跑得真快呀！这只兔子跑得真快呀！(7)(7)请关

13、上门！请关上门！(8)(8)我正在说谎话我正在说谎话.23（1 1）简单命题与复合命题）简单命题与复合命题（2 2）联结词的定义）联结词的定义（3 3）联结词的优先级）联结词的优先级2.2.联接词联接词24（1 1）简单命题与复合命题）简单命题与复合命题简单命题简单命题(原子命题原子命题):简单陈述句构成的命题。简单陈述句构成的命题。简单命题的符号化简单命题的符号化:用用p,q,r,p,q,r,p pi i,q qi i,r ri i(i i1)1)表示表示 用用“1”“1”表示真，用表示真，用“0”“0”表示假表示假复合命题复合命题:由简单命题通过联结词联结而成的陈述句。由简单命题通过联结词

14、联结而成的陈述句。例如例如 如果明天天气好如果明天天气好,我们就出去郊游我们就出去郊游 设设p p:明天天气好明天天气好,q q:我们出去郊游我们出去郊游,如果如果p p,则则q q 又如又如 张三一面喝茶一面看报张三一面喝茶一面看报 设设p p:张三喝茶张三喝茶,q q:张三看报张三看报,p p并且并且q q25（2）联结词的定义）联结词的定义 否定词否定词（）定义定义2.1 设设p为命题，复合命题为命题，复合命题“非非p”(或或“p的否定的否定”)称为称为p的的否定式否定式，记作，记作 p，符号，符号 称作称作否定联结词否定联结词,并并规定规定 p为真当且仅当为真当且仅当 p为假。为假。例

15、如例如 p:2是合数是合数,p:2不是合数。不是合数。p为假为假,p为真。为真。26 合取词合取词（）定义定义2.2 设设p,q为二命题为二命题,复合命题复合命题“p并且并且q”(或或“p与与q”)称为称为p与与q的的合取式合取式,记作记作pq,称作称作合取联结词合取联结词,并规定并规定 pq为真当且仅当为真当且仅当 p与与q同时为真同时为真.例如例如 p:2是偶数是偶数,q:2是素数是素数,pq:表示的含义是表示的含义是2是偶素数。是偶素数。因为因为p为真为真,q也为真，所以也为真，所以 pq为真。为真。27例例3 将下列命题符号化将下列命题符号化.解：解：记记 p:王晓用功王晓用功,q:王

16、晓聪明王晓聪明(1)pq(2)pq(3)q p(4)记记 r:张辉是三好生张辉是三好生,s:王丽是三好生王丽是三好生,rs(5)简单命题简单命题,记记 t:张辉与王丽是同学张辉与王丽是同学(1)王晓既用功又聪明王晓既用功又聪明.(2)王晓不仅聪明，而且用功王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与王丽是同学张辉与王丽是同学.28 析取词析取词（）定义定义2.3 设设 p、q为命题，复合命题为命题，复合命题“p或或q”称作称作p与与q的的析取式析取式，记作，记作pq,称作称作析取联结词析取联结词,并规定

17、并规定pq为假当且仅当为假当且仅当p与与q同时为假。同时为假。例如例如 张三和李四至少有一人会英语张三和李四至少有一人会英语设设 p:张三会英语张三会英语,q:李四会英语李四会英语,符号化为符号化为pq。29相容或与排斥或相容或与排斥或 析取词表示的是析取词表示的是相容或相容或，即，即 p 和和 q 均为真时均为真时(p q)亦为真，而与之对应的还有一个是亦为真，而与之对应的还有一个是排斥或排斥或，它表示的，它表示的含义是含义是p 和和 q 不能同时为真。不能同时为真。例如例如 这件事由张三和李四中的一人去做这件事由张三和李四中的一人去做 设设 p:张三做这件事张三做这件事,q:李四做这件事李

18、四做这件事 应符号化为应符号化为 (p q)(p q)30例例4 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值解：记解：记 p:2是素数是素数,q:3是素数是素数,r:4是素数是素数,s:6是素数是素数(1)pr,(2)pq,(3)rs,(4)记记t:元元拿一个苹果元元拿一个苹果,u:元元拿一个梨元元拿一个梨真值真值:1真值真值:1真值真值:0(t u)(tu)(5)记记v:王晓红生于王晓红生于1975年年,w:王晓红生于王晓红生于1976年年(v w)(vw)又可形式化为又可形式化为 vw(1)2或或4是素数是素数.(2)2或或3是素数是素数.(3)4或或6是素数是素数.(4

19、)元元只能拿一个苹果或一个梨元元只能拿一个苹果或一个梨.(5)王晓红生于王晓红生于1975年或年或1976年年.31 蕴涵词（蕴涵词（）定义定义2.4 设设 p,q为二命题为二命题,复合命题复合命题“如果如果p,则则q”称称作作p与与q的的蕴涵式蕴涵式,记作记作pq,并称并称p是蕴涵式的是蕴涵式的前件前件,q为蕴涵式的为蕴涵式的后件后件.称作称作蕴涵联结词蕴涵联结词,并规定并规定,pq为假当且仅当为假当且仅当 p为真且为真且q为假为假.例如例如 如果明天天气好如果明天天气好,我们就出去郊游我们就出去郊游 设设p:明天天气好明天天气好,q:我们出去郊游我们出去郊游,形式化为形式化为 pq32蕴涵

20、词的其它表述方式蕴涵词的其它表述方式pq 的逻辑关系的逻辑关系:q为为p的必要条件的必要条件,p为为q的充分条件。的充分条件。“如果如果p,则则q”的多种表述方式：的多种表述方式：若若p,就就q 只要只要p,就就q p仅当仅当q 只有只有q 才才p 除非除非q,才才p 除非除非q,否则非否则非p当当p为假时，为假时，pq为真为真(不管不管q为真为真,还是为假还是为假)33例例5 设设p:天冷天冷,q:小王穿羽绒服，将下列命题符号化小王穿羽绒服，将下列命题符号化 注意：注意：pq 与与 qp 等值（真值相同）等值（真值相同）pqpq qp 或或 pqpqqp qp pq 或或 qpqp(1)只要

21、天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.34 等价词（等价词（）定义定义2.5 设设p,q为命题为命题,复合命题复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价

22、式,记作记作pq,称作称作等价联结词等价联结词.并规定并规定pq为真为真当且仅当当且仅当 p与与q同时为真或同时为假。同时为真或同时为假。pq 的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件例如例如 这件事张三能做好这件事张三能做好,且只有张三能做好且只有张三能做好 设设p:张三做这件事张三做这件事,q:这件事做好了这件事做好了 形式化为形式化为:pq35例例6 求下列复合命题的真值：求下列复合命题的真值：1011(1)2+24 当且仅当当且仅当 3+36.(2)2+24 当且仅当当且仅当 3是偶数是偶数.(3)2+24 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2

23、+25 当且仅当当且仅当 美国位于非洲美国位于非洲.36分析找出分析找出简单命题简单命题用字母表示用字母表示简单命题简单命题用联接词联接用联接词联接命题符号命题符号 命题符号化的一般规则命题符号化的一般规则37分析找出分析找出简单命题简单命题用字母表示用字母表示简单命题简单命题用联接词联接用联接词联接命题符号命题符号解解 令令 p:p:我上街我上街 q:q:我累我累 r:r:我去书店看看我去书店看看 则可符号化为：（则可符号化为：（p pq)q)r r例例7 将下列命题符号化：将下列命题符号化：如果我上街并且我不累，我就去书店看看。如果我上街并且我不累，我就去书店看看。简单命题：我上街。我累。

24、我去书店看看。简单命题：我上街。我累。我去书店看看。38例例8 8 试将下列命题符号化：试将下列命题符号化：如果你不看电影，那么我也不看电影如果你不看电影，那么我也不看电影小王一边吃饭，一边看书小王一边吃饭，一边看书解解:（1 1）设）设p p：你看电影，：你看电影，q q：我看电影，则：我看电影，则：p p q q （2 2）设）设p p：小王吃饭，：小王吃饭，q q：小王看书，则：小王看书，则：p p q q39（3）联结词的优先级）联结词的优先级联结词优先级联结词优先级:(),同级按从左到右的顺序进行同级按从左到右的顺序进行401 1、分析下列各命题的真值、分析下列各命题的真值 （1 1

25、）2+2=42+2=4当且仅当当且仅当3 3是奇数是奇数 （2 2）2+2=42+2=4当且仅当当且仅当3 3不是奇数不是奇数 （3 3）2+22+24 4当且仅当当且仅当3 3是奇数是奇数 （4 4）2+22+24 4当且仅当当且仅当3 3不是奇数不是奇数2 2、将下列命题符号化、将下列命题符号化 （1 1）小王是游泳冠军或者百米赛跑冠军）小王是游泳冠军或者百米赛跑冠军 （2 2）小王现在在宿舍或者在图书馆）小王现在在宿舍或者在图书馆 （3 3）选小王或者小李中的一人当班长）选小王或者小李中的一人当班长 （4 4）如果我上街，我就去书店看看，除非我很累）如果我上街，我就去书店看看，除非我很累

26、课堂练习（课堂练习（1）41课堂练习（课堂练习（2 2）3 3、将下列命题符号化、将下列命题符号化 （1 1）李平既聪明又用功）李平既聪明又用功 （2 2）李平虽然聪明，但不用功）李平虽然聪明，但不用功 （3 3）李平不但聪明，而且用功）李平不但聪明，而且用功 （4 4）李平不是不聪明，而是不用功）李平不是不聪明，而是不用功4 4、将下列命题符号化、将下列命题符号化 （1 1）只要不下雨，我就骑自行车上班）只要不下雨，我就骑自行车上班 （2 2）只有不下雨，我才骑自行车上班）只有不下雨，我才骑自行车上班 （3 3）若）若2+2=42+2=4，则太阳从东方升起，则太阳从东方升起 （4 4）若）若

27、2+22+24,4,则太阳从东方升起则太阳从东方升起422.1.2 2.1.2 合式公式及其分类合式公式及其分类1.1.命题语言的字母表命题语言的字母表 ：2.2.合式公式的基本概念合式公式的基本概念3.3.真值表真值表4.4.合式公式的分类合式公式的分类431.1.命题语言的字母表命题语言的字母表命题语言的字母表命题语言的字母表 ：命题常元：命题常元：T,F(T,F(或或 1 1，0)0)命题变元：命题变元：p p1 1,p p2 2,p pn n 联接词：联接词：，辅助符号：（辅助符号：（）44（1）合式公式）合式公式(命题公式命题公式,公式公式)的定义的定义定义定义2.6 合式公式合式公

28、式递归定义如下：递归定义如下：(1)单个命题常项或变项是合式公式，并称作单个命题常项或变项是合式公式，并称作原子合式公式；原子合式公式；(2)若若A是合式公式是合式公式,则则(A)也是合式公式；也是合式公式；(3)若若A,B是合式公式是合式公式,则则(A B),(A B),(AB),(AB)也是也是合式公式；合式公式；(4)只有有限次地应用只有有限次地应用(1)(3)形成的符号串才是合式公式。形成的符号串才是合式公式。2、合式公式的基本概念、合式公式的基本概念说明说明:(1)元语言符号与对象语言符号元语言符号与对象语言符号 (2)在不影响运算顺序时在不影响运算顺序时,括号可以省去括号可以省去

29、例如例如 0,p,p q,(p q)(p r),p q r,(pq)r45（2）合式公式的层次）合式公式的层次定义定义2.7 (1)单个命题变项或命题常项是单个命题变项或命题常项是0层公式层公式(2)称称A是是n+1(n0)层公式是指下面情况之一：层公式是指下面情况之一：(a)A=B,B是是n层公式层公式(b)A=B C,其中其中B,C分别为分别为i层和层和j层公式层公式,且且 n=max(i,j)(c)A=B C,其中其中B,C的层次及的层次及n同同(b)(d)A=BC,其中其中B,C的层次及的层次及n同同(b)(e)A=BC,其中其中B,C的层次及的层次及n同同(b)例如例如 p 0层层

30、p 1层层 pq 2层层 (pq)r 3层层 (p q)r)(r s)4层层46（3 3）公式的赋值）公式的赋值定义定义2.8 设设 p1,p2,pn是出现在公式是出现在公式A中全部的命题变中全部的命题变项，给项，给 p1,p2,pn指定一组真值，称为对指定一组真值，称为对A的一个的一个赋赋值值或或解释解释。使公式为真的赋值称作使公式为真的赋值称作成真赋值成真赋值,使公式为假的赋值称使公式为假的赋值称作作成假赋值。成假赋值。说明说明:(1)赋值记作赋值记作=1 2 n，其中，其中 i=0或或1，诸，诸 i之间之间不加标点符号；不加标点符号；(2)通常赋值与命题变项之间按下标或字母顺序对应通常赋

31、值与命题变项之间按下标或字母顺序对应,即：即：当当A的全部命题变项为的全部命题变项为p1,p2,pn时时,给给A赋值赋值 1 2 n是指是指 p1=1,p2=2,pn=n;当当A的全部命题变项为的全部命题变项为p,q,r,时时,给给A赋值赋值 1 2 3是指是指p=1,q=2,r=3,47实例实例例例8 公式公式A=(p1 p2 p3)(p1 p2)000是成真赋值是成真赋值,001是成假赋值是成假赋值 公式公式B=(pq)r 000是成假赋值是成假赋值,001是成真赋值是成真赋值483、真值表、真值表真值表真值表:命题公式在所有可能的赋值下的取值的列表。命题公式在所有可能的赋值下的取值的列表

32、。含含n个变项的公式有个变项的公式有2n个赋值个赋值 用用0或或1表示公式中命题变元的取值，并依据联结表示公式中命题变元的取值，并依据联结词的逻辑规则计算出复合命题（公式）的真值，用词的逻辑规则计算出复合命题（公式）的真值，用一个对应表表示的一种方法。一个对应表表示的一种方法。49基本复合命题真值表汇总基本复合命题真值表汇总 p q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 150 p q qp (qp)q (qp)qp 0 00 11 01 1 1011 0001 1111例例9 给出公式的真值表给

33、出公式的真值表(1)(qp)qp；(2)(p q)q；(3)(p q)r.例951 p q p p q (p q)(p q)q0 00 11 01 1 1100110100100000(2)(p q)q52 p q r p q r (p q)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 11101010(3)(p q)r534、命题公式的分类、命题公式的分类重言式重言式(永真式永真式):无成假赋值的命题公式无成假赋值的命题公式矛盾式矛盾式(永假式永假式):无成真赋值的命题公式无成真赋值的命题公式可满足式可满足式:

34、非矛盾式的命题公式非矛盾式的命题公式注意注意:重言式是可满足式，但反之不真重言式是可满足式，但反之不真.例如例如 上例中上例中(1)(qp)qp为重言式为重言式(2)(p q)q为矛盾式为矛盾式(3)(p q)r为非重言式的可满足式为非重言式的可满足式542、判断下列命题公式的类型（1）（2）课堂练习课堂练习1、构造下列命题公式的真值表（1）（2）)(rqp)()(qpqpsrqp)(ppp)(552.2 命题逻辑等值演算命题逻辑等值演算 2.2.1 等值式与等值演算等值式与等值演算 等值式等值式 基本等值式基本等值式 等值演算等值演算 2.2.2 联结词完备集联结词完备集 真值函数真值函数

35、联结词完备集联结词完备集 与非联结词和或非联结词与非联结词和或非联结词56 2.2.1 等值式与等值演算1、等值式的定义、等值式的定义定义定义2.11 若等价式若等价式AB是永真式是永真式,则称则称A与与B等值等值,记作记作AB,并称并称AB是是等值式。等值式。57(1)是是元语言符号元语言符号,不要混同于不要混同于和和=。(2)A与与B等值当且仅当等值当且仅当A与与B在所有可能赋值下的真值都相在所有可能赋值下的真值都相同同,即即A与与B有相同的真值表。有相同的真值表。(3)可能有哑元出现可能有哑元出现.在在B中出现中出现,但不在但不在A中出现的命题变中出现的命题变项称作项称作A的的哑元哑元.

36、同样同样,在在A中出现中出现,但不在但不在B中出现的命题变中出现的命题变项称作项称作B的哑元的哑元.哑元的值不影响命题公式的真值。哑元的值不影响命题公式的真值。说明说明582、性质、性质(1)A A(2)若若A B，则，则 B A(3)若若A B且且B C，则，则 A C593、真值表法判断公式是否等值、真值表法判断公式是否等值结论结论:(p q)(p q)p q p q p q (p q)p q (p q)(p q)0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1例例1 判断判断 (p q)与与 p q 是否等值是

37、否等值解解60 p q r p(qr)(pq)r (p q)r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 p(qr)与与(p q)r等值等值,但与但与(pq)r不等值不等值 例例2 判断下述判断下述3个公式之间的等值关系个公式之间的等值关系:p(qr),(pq)r,(p q)r解解614、基本等值式、基本等值式（1）双重否定律：）双重否定律：（2）等幂律：）等幂律：pppppppp62（3）交换律：）交换律：（4）结合律：）结合律：（5）分配律：

38、）分配律：12211221pppppppp123123123123()()()()pppppppppppp12312131231213()()()()()()pppppppppppppp（6）德）德 摩根定律：摩根定律：12121212()()pppppppp 63（7）吸收律：）吸收律：（8）蕴含等值式：）蕴含等值式：11211121()()pppppppp1212pppp（9）等价等值式：）等价等值式：121221()()pppppp64（10）零律：）零律：（11）同一律：）同一律：pTTpFFpFppTp（12）排中律：）排中律：ppT65（13）矛盾律：）矛盾律：（14）等价否定等值

39、式：）等价否定等值式：ppF1212()()pppp （15）归谬律：）归谬律：（16）假言易位：）假言易位：12121()()ppppp 1221()()pppp 66 (1)代入规则代入规则 代入规则代入规则：对于重言式中的任一命题变元出现的对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。每一处均用同一命题公式代入，得到的仍是重言式。例如例如 F=（pq）（qp）是重言式，若）是重言式，若用公式用公式rs代换命题变元代换命题变元p得公式得公式 F1=（rs）q）（q（rs），），F1仍是重言式。仍是重言式。注意：因为注意：因为A B当且仅当当且仅当A B是重言

40、式。所以，是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。一命题公式代入，则得到的仍是等值式。5、等值演算、等值演算67(2)置换规则置换规则 例如例如 设公式设公式A=A=（PQPQ）（P PQ Q）（RR S S）。）。则则 PQ，PQ，（，（PQ）（R S）等均是）等均是A的子公式，的子公式，置换规则：置换规则：设设C C是公式是公式A A的子公式，的子公式，C CD D。如果将。如果将公式公式A A中的子公式中的子公式C C置换成公式置换成公式D D之后，得到的公式是之后，得到的公式是B B

41、，则则A AB B。子公式子公式：设设C C是命题公式是命题公式A A的一部分（即的一部分（即C C是公式是公式A A中中连续的几个符号），且连续的几个符号），且C C本身也是一个命题公式，则称本身也是一个命题公式，则称C C为为公式公式A A的子公式。的子公式。68(3)(3)等值演算等值演算 等值演算等值演算是指利用已知的一些等值式，根据置换是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。一些等值式的过程。例例3 证明证明 p(qr)(p q)r证证 p(qr)p(q r)（蕴涵等值式）蕴涵等值

42、式）(pq)r （结合律）结合律）(p q)r （德摩根律）德摩根律）(p q)r （蕴涵等值式）蕴涵等值式）69 例例4：证明（：证明（AB)(BA)是永真式。是永真式。证明证明:(A B)(B A)蕴涵等值式蕴涵等值式 (AB)(BA)德德摩根律、双重否定律摩根律、双重否定律 (AB)(BA)分配律分配律 (ABA)(BBA)交换律、结合律、补余律交换律、结合律、补余律 T （AB)(BA)是永真式是永真式70)()(qpqpp)()()(1qpqpqqppp（同一律）（同一律）（排中律）（排中律）（分配律）（分配律）证明证明 例5证：证：71例例6 用等值演算法判断下列公式的类型用等值演

43、算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）蕴涵等值式）q(pq)（德摩根律）德摩根律）p(qq)（交换律，结合律）交换律，结合律）p 0 （矛盾律）矛盾律）0 （零律）（零律）该式为矛盾式该式为矛盾式.72例例6(续续)(2)(pq)(qp)解解 (pq)(qp)(p q)(qp)（蕴涵等值式）蕴涵等值式）(p q)(p q)（交换律）交换律）1该式为重言式该式为重言式.73例例6(续续)(3)(p q)(pq)r)解解 (p q)(pq)r)(p(qq)r （分配律）分配律）p 1 r （排中律）排中律）p r （同一律）同一律）非重言式的可满足式非重言

44、式的可满足式.如如101是它的成真赋值是它的成真赋值,000是它的是它的成假赋值成假赋值.总结总结:A为矛盾式当且仅当为矛盾式当且仅当A0;A为重言式当且仅当为重言式当且仅当A1说明说明:演算步骤不惟一演算步骤不惟一,应尽量使演算短些应尽量使演算短些74例7：应用题 某勘探队有某勘探队有3名队员，有一天取得一块矿样，名队员，有一天取得一块矿样，3人的人的判断如下：判断如下：甲说：这不是铁，也不是铜甲说：这不是铁，也不是铜 乙说：这不是铁，是锡乙说：这不是铁，是锡 丙说：这不是锡，是铁丙说：这不是锡，是铁 经过实验鉴定后发现，其中一人经过实验鉴定后发现，其中一人2个判断都是正确个判断都是正确的，

45、一人判断对了一半，另外一个人全错了。根据以的，一人判断对了一半，另外一个人全错了。根据以上情况判断矿样的种类。上情况判断矿样的种类。750001)()()()()()()()()(rprpqprprpqprprprpqpF丙全错乙对一半甲全对解：解：设设 p：矿样为铁，：矿样为铁，q：矿样为铜，：矿样为铜，r：矿样为锡，则可得：矿样为锡，则可得：76000)()()()()()()()()(2rprpqprprpqprprprpqpF丙对一半乙全错甲全对)()()()()()()()()()()(qrpqrpqprprpqprprprprpqpqpF03丙全错乙全对甲对一半77)()()()(

46、)()()()()()()(qrpqrpqprprpqprprprprpqpqpF04丙全对乙全错甲对一半05)()()(丙全对乙对一半甲全错F06)()()(丙对一半乙全对甲全错F78等值演算不能直接证明两个公式不等值等值演算不能直接证明两个公式不等值.证明两个公式不证明两个公式不等值的基本思想是找到一个赋值使一个成真等值的基本思想是找到一个赋值使一个成真,另一个成假另一个成假.例例8 证明证明:p(qr)(pq)r方法一方法一 真值表法真值表法方法二方法二 观察法观察法.容易看出容易看出000使左边成真使左边成真,使右边成假使右边成假.方法三方法三 先用等值演算化简公式先用等值演算化简公式

47、,再观察再观察.79 2、证明 3、证明 是永真式。课堂练习课堂练习 1、证明qpqpp)()()()(rprqqp用等值演算证明：qrpqrqp)()()(80 2.2.2 联结词完备集1、真值函数、真值函数n元真值函数共有元真值函数共有 个个每一个命题公式对应于一个真值函数每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式每一个真值函数对应无穷多个命题公式n221元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1)1(3)1(2)1(1)1(0FFFF定义定义2.12 称称F:0,1n0,1为为n元元真值函数真值函数812元真值函数元真值函数 p q 0 0

48、0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 p q 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF82定义定义2.13 设设S是一个联结词集合是一个联结词集合,如果任何如果任何n(n 1)元真值元真值函数都可

49、以由仅含函数都可以由仅含S中的联结词构成的公式表示中的联结词构成的公式表示,则称则称S是是联结词完备集联结词完备集定理定理2.1 下述联结词集合都是完备集下述联结词集合都是完备集:(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,(6)S6=,2、联结词完备集83举例AB (AB)(BA)AB A BA B (A B)(AB)A B (AB)A B (A)B AB84与非、或非与非式与非式:p q(p q),称作称作与非联结词与非联结词或非式或非式:p q(p q),称作称作或非联结词或非联结词p q为真当且仅当为真当且仅当p,q不同时为真不同时为真p q为真当且仅当为真当且仅当p,q同时为假同时为假定理定理2.2 ,是联结词完备集是联结词完备集证证 p (p p)p p p q (p q)(p q)(p q)(p q)得证得证 是联结词完备集是联结词完备集.对于对于 可类似证明可类似证明.85P80-81：2.10，2.12，2.13（2），），2.15（1），），2.16，2.18（1），），2.19（2），），2.20，2.21（1），），2.22（2），），2.23（1）（）（3）本节习题