东南大学离散数学第一章.ppt

《东南大学离散数学第一章.ppt》由会员分享，可在线阅读，更多相关《东南大学离散数学第一章.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、东南大学离散数学第南大学离散数学第一章一章绪论：什么是离散数学（离散结构）绪论：什么是离散数学（离散结构）n研究研究离散量的结构和相互关系离散量的结构和相互关系的数学科学的数学科学离散结构离散结构：集合、关系、图等：集合、关系、图等 离散量是指分散开来的、不存在中间值的量离散量是指分散开来的、不存在中间值的量 n研究对象研究对象:有限或可数个元素有限或可数个元素自然数、整数，真假值，有限节点等自然数、整数，真假值，有限节点等n 研究方法：研究方法：推理、运推理、运算和实验等算和实验等2计算机科学与工程学院绪论：为什么要学习离散数学绪论：为什么要学习离散数学n计计算机技术的算机技术的支撑科学支撑

2、科学：计算机只能处理离散的或离散化了的数量关：计算机只能处理离散的或离散化了的数量关系系培养离散思维与抽象思维能培养离散思维与抽象思维能力力 计算机专业课程学习的重要基础计算机专业课程学习的重要基础 培养理论研究和应用开发的离散建模能力培养理论研究和应用开发的离散建模能力3计算机科学与工程学院绪论：我们将学习的离散数学绪论：我们将学习的离散数学主要学习四个方面的基本内容主要学习四个方面的基本内容：数理逻辑数理逻辑集合论集合论代数结构代数结构图论图论4计算机科学与工程学院绪论：离散数学与计算机科学绪论：离散数学与计算机科学数据结构离散数学离散数学操作系统软件工程计算机网络编译原理人工智能可计算性

3、理论l离散数学与计算机科学关系总览计算机体系结构生物信息学数字通信数据库理论5计算机科学与工程学院绪论：离散数学与计算机科学绪论：离散数学与计算机科学(续续)离散数学与数据结构离散数学与数据结构线性表、栈、队列：由元素和元素之间关系建立起来的对象线性表、栈、队列：由元素和元素之间关系建立起来的对象 集合论集合论是是研究研究元素和其之间关系的理论元素和其之间关系的理论非线性结构非线性结构对象（家族图谱、计算机文件组织结构和信息网等）由树和图数据结构表示，如二叉树、网对象（家族图谱、计算机文件组织结构和信息网等）由树和图数据结构表示，如二叉树、网络等络等 图论是研究上述非线性结构和其运算的基本理论

4、图论是研究上述非线性结构和其运算的基本理论离散数学与数据库理论离散数学与数据库理论 数据库理论中的关系演算与关系模型需要用到数据库理论中的关系演算与关系模型需要用到谓词逻辑谓词逻辑关系数据库是行和列组成的二维表，表间的连接操作由笛卡尔积理论支持关系数据库是行和列组成的二维表，表间的连接操作由笛卡尔积理论支持表的操作（查询、删除、修改）与关系代数和数理逻辑密切相关表的操作（查询、删除、修改）与关系代数和数理逻辑密切相关6计算机科学与工程学院绪论：离散数学与计算机科学绪论：离散数学与计算机科学(续续)离散数学与人工智能离散数学与人工智能 计算机智能化（推理）的前提计算机智能化（推理）的前提自然语言

5、的符号化自然语言的符号化 语言符号化是数理逻辑研究的基本内容语言符号化是数理逻辑研究的基本内容离散数学与其它计算机学科离散数学与其它计算机学科计算机计算机硬件中的数字线路硬件中的数字线路设计、通讯系统设计设计、通讯系统设计数理逻辑、布尔代数等数理逻辑、布尔代数等可计算性、计算复杂性可计算性、计算复杂性抽象代数等抽象代数等DNA计算计算碱基序列编码信息，酶控制下进行碱基序列编码信息，酶控制下进行DNA反应，反应前序列为输入，反应后序列为运输结反应，反应前序列为输入，反应后序列为运输结果果7计算机科学与工程学院绪论：怎么学习离散数学绪论：怎么学习离散数学l离散数学特征离散数学特征 离散性离散性 可

6、构造性可构造性 抽象性抽象性l 离散数学课程基础离散数学课程基础 数理逻辑：命题逻辑和谓词逻辑数理逻辑：命题逻辑和谓词逻辑 集合论：集合、关系和函数集合论：集合、关系和函数 代数结构：代数运算、群、格、布尔代数代数结构：代数运算、群、格、布尔代数 图论：树、图图论：树、图l 8计算机科学与工程学院绪论：教材和参考书绪论：教材和参考书n教材：教材：屈婉玲屈婉玲，耿素云，张立昂，耿素云，张立昂，离散数学离散数学，高等教育出版社，高等教育出版社，2007n参考书：参考书：Kenneth H.Rosen，离散数学和其应用离散数学和其应用，机械工业出版社，机械工业出版社，2007方世昌，离散数学，西安电

7、子科技大学出版社，方世昌，离散数学，西安电子科技大学出版社，2000朱一清，离散数学，电子工业出版社，朱一清，离散数学，电子工业出版社，20009计算机科学与工程学院绪论：课程安排（离散结构绪论：课程安排（离散结构1 1）讲授内容：讲授内容：数理逻辑（第一、二、三、四、五章）数理逻辑（第一、二、三、四、五章）集合论（第六、七、八章）集合论（第六、七、八章）代数结构（第九、十章）代数结构（第九、十章）成绩构成：成绩构成：平时成绩（平时成绩（30%）期末成绩（期末成绩（70%）平时成绩：作业、考勤（平时成绩：作业、考勤（10%）期中测试（期中测试（20%）作业：作业：周二交作业周二交作业10计算机

8、科学与工程学院绪论：数理逻辑绪论：数理逻辑n逻辑学分类逻辑学分类辩证逻辑：是研究事物发展的客观规律辩证逻辑：是研究事物发展的客观规律形式逻辑：是研究思维的概念、判断和推理的问题形式逻辑：是研究思维的概念、判断和推理的问题n数理逻辑数理逻辑（又称符号逻辑）（又称符号逻辑）数学方法研究形式逻辑的一门科学数学方法研究形式逻辑的一门科学，使用符号，使用符号数理逻辑创始人数理逻辑创始人莱布尼兹莱布尼兹(Leibniz,1646-1716,(Leibniz,1646-1716,德德)现代数理逻辑：公理化集合论、模型论、递归函数论、证明论现代数理逻辑：公理化集合论、模型论、递归函数论、证明论最基本组成最基本

9、组成内容内容：命题演算、谓词演算：命题演算、谓词演算应用：逻辑电路、自动控制、人工智能等应用：逻辑电路、自动控制、人工智能等11计算机科学与工程学院绪论：数理逻辑学习意义绪论：数理逻辑学习意义E.W.Dijkstra（荷兰计算机科学家，提出了程序设计中常用的（荷兰计算机科学家，提出了程序设计中常用的GOTO语句的三大危害；语句的三大危害；解决有向图中最短解决有向图中最短路径问题路径问题的的Dijkstra算法）：算法）：“我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早年

10、在数理逻辑上好好下点功夫的话，我就不会犯这么多的错误，不少东西逻辑学家早就说了，可我不知道。要是我能年轻二好下点功夫的话，我就不会犯这么多的错误，不少东西逻辑学家早就说了，可我不知道。要是我能年轻二十岁的话，就要回去学逻辑。十岁的话，就要回去学逻辑。”数理逻辑数理逻辑提供了提供了计算机科学与技术研究中的重要工具与方法计算机科学与技术研究中的重要工具与方法12计算机科学与工程学院第一部分第一部分第一部分第一部分 数理逻辑数理逻辑数理逻辑数理逻辑 主要主要内容内容 命题逻辑命题逻辑基本概念基本概念 命题逻辑等值演算命题逻辑等值演算 命题逻辑推理理论命题逻辑推理理论 一阶逻辑基本概念一阶逻辑基本概念

11、 一阶逻辑等值演算与推理一阶逻辑等值演算与推理13计算机科学与工程学院第第第第1 1 1 1章命题逻辑基本概念章命题逻辑基本概念章命题逻辑基本概念章命题逻辑基本概念Propositional LogicPropositional Logic命题与联结词命题与联结词命题和其分类命题和其分类联结词与复合命题联结词与复合命题命题公式和其赋值命题公式和其赋值两个逻辑推理的例子如果火车晚点且火车站没有出租车，那么老李开会就迟到。老李开会没有迟到。火车晚点。所以，火车站有出如果火车晚点且火车站没有出租车，那么老李开会就迟到。老李开会没有迟到。火车晚点。所以，火车站有出租车。租车。如果天下雨且王小姐没带雨伞

12、，那么她将被淋湿。王小姐没被淋湿。天下雨了。所以，王小姐带了雨伞。如果天下雨且王小姐没带雨伞，那么她将被淋湿。王小姐没被淋湿。天下雨了。所以，王小姐带了雨伞。If p and Not q,then r.Not r.p.Therefore,q.15计算机科学与工程学院1.1 1.1 命题命题与联接词与联接词n命题命题(Proposition)：具有唯一真值陈述句：具有唯一真值陈述句 唯一性：唯一性：或真或假但不能两者都是的或真或假但不能两者都是的 命题所用符号：常用小写命题所用符号：常用小写2626个英文字母个英文字母n例子例子十是整数十是整数21002100年人类将在月球生活年人类将在月球生活

13、x x=3=3现在是几点？现在是几点？1+1=21+1=2我现在说假话我现在说假话悖论！悖论！16计算机科学与工程学院1.1 1.1 命题命题与联接词与联接词n判断下列语句是否为命题判断下列语句是否为命题明天下雨明天下雨加拿大是一个国家加拿大是一个国家x x+y y44 注：注：命题是陈述句，陈述句不一定是命题命题是陈述句，陈述句不一定是命题命题有唯一真值，但真值可能受范围、时空、环境、判断标准、认识程度限制，一时无法确定命题有唯一真值，但真值可能受范围、时空、环境、判断标准、认识程度限制，一时无法确定一个句子本身能否分辨真假与我们知道它的真假值是两回事一个句子本身能否分辨真假与我们知道它的真

14、假值是两回事17计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词n命题分类命题分类简单命题：不能被分解成更简单的陈述句简单命题：不能被分解成更简单的陈述句复合命题：简单陈述句复合命题：简单陈述句+联接词联接词n例子例子今天没有天晴今天没有天晴王华的成绩很好并且品德很好王华的成绩很好并且品德很好小李是学数学或者计算机科学小李是学数学或者计算机科学如果天下雨，那么地下湿如果天下雨，那么地下湿18计算机科学与工程学院1.1 命题与联接词n基本联结词基本联结词 否定否定(negation)合取合取(conjunction)析取析取(disjunction)蕴含蕴含(implication)

15、等价等价(equivalence/bi-implication)19计算机科学与工程学院1.1 命题命题与联接词联接词n否定联接词否定联接词 符号符号,读作读作“非非”，“否定否定”n定义：命题定义：命题 p p p p的否定式：复合命题的否定式：复合命题“p p的否定的否定”（“非非p”p”）符号：符号：p p(符号符号 称作否定联结词称作否定联结词)p p为真当且仅当为真当且仅当p p为假为假n例子例子 今天没有天晴今天没有天晴 p p p p ：今天天晴今天天晴p pTFFT20计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词n合取联接词合取联接词符号符号,读作读作“合取合取

16、”n定义：命题定义：命题 p p，q q p p与与q q的合取式：复合命题的合取式：复合命题“p p并且并且q q”符号：符号：p p q q(符号符号 称作合取联结词称作合取联结词)p p q q为真当且仅当为真当且仅当p p和和q q同时为真同时为真n例子例子 王华的成绩很好并且品德很好王华的成绩很好并且品德很好 p p q qp p：王华的成绩很好：王华的成绩很好q q：王华的品德很好：王华的品德很好pqp qFFFFTFTFFTTT21计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词n析取联接词析取联接词符号符号,读作读作“析取析取”n定义：命题定义：命题 p p，q q

17、 p p与与q q的析取式：复合命题的析取式：复合命题“p p或或q q”符号：符号：p p q q(符号符号 称作析取联结词称作析取联结词)p p q q为假当且仅当为假当且仅当p p和和q q同时为假同时为假n例子例子 小李是学数学或者计算机科学小李是学数学或者计算机科学p p q qp p：小李是学数学：小李是学数学q q：小李是学计算机科学：小李是学计算机科学pqp qFFFFTTTFTTTT22计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词 析取联接词（相容或）析取联接词（相容或）“排斥或排斥或”n排斥或：排斥或：符号符号 n定义：命题定义：命题 p p，q q 符号：

18、符号：p p q q 等价于等价于(p pq q)(p p q q)p p q q为假当且仅当为假当且仅当p p和和q q同时为假或同时为假或 同时为真同时为真n例子：例子：小李正在教学楼看书或在图书馆上网小李正在教学楼看书或在图书馆上网 小李在看书或者听音乐小李在看书或者听音乐 （析取）（析取）pqp qFFFFTTTFTTTF23计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词n蕴含联接词蕴含联接词符号符号,读作读作“如果如果则则”、“蕴含蕴含”n定义：命题定义：命题 p p，q q p p与与q q的蕴涵式：复合命题的蕴涵式：复合命题“如果如果p p，则，则q q”符号：符号

19、：p pq q(符号符号称作蕴含联结词称作蕴含联结词)p pq q为假当且仅当为假当且仅当p p为真，为真，q q为假为假n例子例子 如果天下雨，那么地下湿如果天下雨，那么地下湿 p pq qp p：天下雨：天下雨q q：地下湿地下湿pqpqFFTFTTTFFTTT24计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词n 更多关于蕴含联接词更多关于蕴含联接词n p pq q：q q是是p p的必要条件的必要条件n 其他：其他：p pq q的叙述方式：的叙述方式：“只要只要p p，就，就q q”，“因为因为p p，所以，所以q q”等等 p p为假，则为假，则p pq q永远为真永远为

20、真 如果给我一个支点，我能把如果给我一个支点，我能把 地球撬起来地球撬起来 区别于自然语言的区别于自然语言的“如果如果p p,则则q q”在自然语言中在自然语言中p p和和q q有语义有语义(内容内容)上的内在联系上的内在联系联结联结词是命题真值之间的联结，而不是命题词是命题真值之间的联结，而不是命题内容之间的联结内容之间的联结pqpqFFTFTTTFFTTT25计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词n更多例子更多例子 如果天晴，则雪是白的如果天晴，则雪是白的 p pq q 如果不天晴，则雪不是白的如果不天晴，则雪不是白的 p pq q（对给定正整数（对给定正整数a a）

21、只要）只要a a能被能被4 4整除，则整除，则a a能被能被2 2整除整除 p pq q26计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词n给定命题给定命题p pq q它的逆命题它的逆命题 q qp p它的反命题它的反命题 p pq q它的逆反命题它的逆反命题 q qp pn各种命题关系各种命题关系 p pq q q qp p q qp p p pq q27计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词n等价式等价式符号符号,读作读作“当且仅当当且仅当”n定义：命题定义：命题 p p，q qp p与与q q的等价式：复合命题的等价式：复合命题“p p当且仅当当且仅当

22、q q”符号：符号：p pq q(符号符号称作等价联结词称作等价联结词)p pq q为真当且仅当为真当且仅当p p与与q q真值相同真值相同n例子例子 当且仅当当且仅当a a=2=2，才有，才有a a2 2=4 =4 p pq qp p：a a=2=2q q：a a2 2=4=4这里这里a a是符号，指某个具体数是符号，指某个具体数,而不是指未知数而不是指未知数pqpqFFTFTFTFFTTT28计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词联接词的定义总结联接词的定义总结pq pp qp qpqpqFFTFFTTFTTFTTFTFFFTFFTTFTTTT29计算机科学与工程学院

23、1.1 1.1 命题与命题与联接词联接词n联接词的优先级联接词的优先级l 、n括号最优先括号最优先n同一优先级：从左到右同一优先级：从左到右n例子：求于命题例子：求于命题 p p q qr r含义相同的命题含义相同的命题(p p)q q)r r(p p q q)r r p p(q qr r)(p p q qr r)30计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词例：例：p p：北京比天津人口多：北京比天津人口多q q：2 22 24 4r r：乌鸦是白色的：乌鸦是白色的求下列命题真值求下列命题真值(p q)(p p q)(p q)rq)r(qr)(p(qr)(pr)r)(p p

24、r)r)(p(pr)r)TTF31计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词n例子：符号化下面命题例子：符号化下面命题小强虽然不聪明，但很用功小强虽然不聪明，但很用功小李学过英语或者法语小李学过英语或者法语小李正在教室看书或在图书馆上网小李正在教室看书或在图书馆上网金无足赤，人无完人金无足赤，人无完人得道多助，失道寡助得道多助，失道寡助pqpq(pq)(pq)pq(pq)(pq)32计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词问题问题1 1：区别：区别 x x+y y44 明天下雨明天下雨33计算机科学与工程学院1.1 1.1 命题与命题与联接词联接词问题问题

25、2 2：得道多助，失道寡助得道多助，失道寡助(pq)(pq)34计算机科学与工程学院1.1 命题与联接词联接词n课堂练习：课堂练习：p p：2+3=52+3=5q q：大熊猫产在中国：大熊猫产在中国r r：太阳从西部升起：太阳从西部升起n求下列命题真值求下列命题真值(r r(p p q q)(p pr r)TFFTTTFF35计算机科学与工程学院1.2 1.2 命题公式命题公式和其赋值和其赋值任何任何命题命题都可以通过简单命题（原子命题）联结词、括号而构成的合法的符号串表示都可以通过简单命题（原子命题）联结词、括号而构成的合法的符号串表示研研究命题演算时，只考虑命题的究命题演算时，只考虑命题的

26、“真真”、“假假”，而不管它的具体含义，即对于符号，而不管它的具体含义，即对于符号p p、q q、r r，并不关心它，并不关心它们所代表的是什么具体命题，而是只关心其本身的真假值们所代表的是什么具体命题，而是只关心其本身的真假值命题公式命题公式36计算机科学与工程学院1.2 1.2 命题公式命题公式和其赋值和其赋值n 命题常项：简单命题命题常项：简单命题n 命题变项：表示命题的变量命题变项：表示命题的变量 真值可以变化的陈述句真值可以变化的陈述句 命题变项不是命题命题变项不是命题 命题变项用确定命题代入才能确定真值命题变项用确定命题代入才能确定真值 命题变项所用符号：常用小写命题变项所用符号：

27、常用小写2626个英文字母个英文字母 命题变量不同于代数式的变量命题变量不同于代数式的变量 x x+y y44的的x x，y y不是命题变量不是命题变量37计算机科学与工程学院1.2 1.2 命题公式命题公式和其赋值和其赋值n 合式公式（命题公式）的递归定义：合式公式（命题公式）的递归定义：1.1.单个命题常项或命题变项是合式公式（原子命题公式）；单个命题常项或命题变项是合式公式（原子命题公式）；2.2.A A为合式公式，则为合式公式，则 A A是合式公式；是合式公式；3.3.A A，B B为合式公式，则（为合式公式，则（A A B B），），(A A B B），），A AB B），），(A

28、AB B）为合式公式；）为合式公式；4.4.有限次应用有限次应用1-31-3形成的字符串为合式公式形成的字符串为合式公式。n 子公式子公式B B：给定合式公式：给定合式公式A AB B是是A A的一部分的一部分B B是合式公式是合式公式38计算机科学与工程学院1.2 1.2 命题公式命题公式和其赋值和其赋值n符号说明符号说明大写字母大写字母A A，B B表示合式公式表示合式公式n公式简写法则：公式简写法则：公式最外层括号可以省略公式最外层括号可以省略（A A）的括号可以省略）的括号可以省略根据运算符优先级省略括号根据运算符优先级省略括号 省略括号不能影响公式解释省略括号不能影响公式解释39计算

29、机科学与工程学院1.2 1.2 命题公式命题公式和其赋值和其赋值合式公式的树状展开合式公式的树状展开 (A (A B)B)(C)C)(D(DC)C)A A B BA A B B(C)C)(D(DC)C)(C)C)D DC CC CD DC C40计算机科学与工程学院1.2 1.2 命题公式命题公式和其赋值和其赋值例子例子(A A B B)C C(p pq q)(q qr r)(B B)pqpqr r41计算机科学与工程学院1.2 命题公式和其赋值n公式层次公式层次若公式若公式A A是单个的命题变元，则称是单个的命题变元，则称A A为为0 0层合式层合式称公式称公式是是n n+1(+1(n n0

30、)0)层公式是指下面情况之一层公式是指下面情况之一a)a)A A B B，B B是是n n层公式层公式b)b)A AB B C C，其中，其中B B，C C分别为分别为i i层和层和j j层公式，且层公式，且n nmax(max(i i,j j)c)c)A AB B C C ，其中，其中B B，C C的层次和的层次和n n同同(b)(b)d)d)A AB B C C ，其中，其中B B，C C的层次和的层次和n n同同(b)(b)e)e)A AB B C C ，其中，其中B B，C C的层次和的层次和n n同同(b)(b)若公式若公式的层次为的层次为k k，则称，则称A A是是k k层公式层公

31、式n层次层次联接词数联接词数42计算机科学与工程学院1.2 1.2 命题公式命题公式和其赋值和其赋值n例子：例子：p,q,r,s为命题变元为命题变元(pq)r)s(pq)(qr)(pq r)s(p q r)43543计算机科学与工程学院1.2 1.2 命题公式命题公式和其赋值和其赋值命题公式是由命题变元和联结词和括号组成的合法符号串，其中的命题变元是抽象的概念：命题公式是由命题变元和联结词和括号组成的合法符号串，其中的命题变元是抽象的概念：若不指定命题变元的真值，则公式没有真值。但是，若不指定命题变元的真值，则公式没有真值。但是，若所有命题变元都指定了一定的真值，则命题公式就变成了一个具有确定

32、真值的命题！若所有命题变元都指定了一定的真值，则命题公式就变成了一个具有确定真值的命题！解释解释赋值赋值44计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值n命题公式的真值命题公式的真值命题变项的常量化：常项替换（解释）命题变项的常量化：常项替换（解释）n例子：公式例子：公式p p q qr r真值为真值为T T的解释的解释p:3p:3是奇数；是奇数；q:7q:7是奇数；是奇数；r:3r:3乘乘7 7是奇数是奇数真值为真值为F F的解释的解释p:3p:3是奇数；是奇数；q:7q:7是奇数；是奇数；r:3r:3乘乘7 7是偶数是偶数n赋值赋值命题变项赋真命题命题变项赋真命题命

33、题变项的真值为命题变项的真值为T T命题变项赋假命题命题变项赋假命题命题变项的真值为命题变项的真值为F F45计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值命题变项赋值命题变项赋值A A中命题变项：中命题变项：p p1 1,p pn n对对p p1 1,p pn n赋值赋值v v：v v(p pi i)=)=i i，i i T,FT,F对对A A的真值递归定义的真值递归定义v v(B)=T iff B)=T iff v v(B)=F(B)=Fv v(B(B C)=T iff C)=T iff v v(B)=(B)=v v(C)=T(C)=Tv v(B(B C)=F iff

34、 C)=F iff v v(B)=(B)=v v(C)=F(C)=Fv v(B(BC)=F iff C)=F iff v v(B)=T(B)=T，v v(C)=F(C)=Fv v(B(BC)=T iff C)=T iff v v(B)=(B)=v v(C)(C)赋值（解释）简写：赋值（解释）简写：1 1 2 2,n nn n个变项的公式，共有个变项的公式，共有2 2n n个不同赋值个不同赋值46计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值n命题命题公式公式赋值赋值成真赋值：成真赋值：v v(A A)=T)=T成假赋值：成假赋值：v v(A A)=F)=Fn例子：公式例子

35、：公式(p pq q)r rFFF(FFF(p p=F,=F,q q=F,=F,r r=F)=F)TFF?TFF?(pq)rFFF47计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值n 真值表真值表(Truth Table)：A A所有赋值列成表所有赋值列成表n 真值表构造：真值表构造：找出找出A A中命题变项：中命题变项：p p1 1,p pn n列出列出2 2n n个赋值（个赋值（2 2进制加法形式）进制加法形式）从高到低写成公式各个层次从高到低写成公式各个层次各个赋值：计算各层的真值各个赋值：计算各层的真值48计算机科学与工程学院1.2 1.2 命题公式和其命题公式和

36、其赋值赋值pqp q(p q)p(p q)p)FFFFTFTTFTTFTTFTTTTF例例(p q)p)49计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值pqrq rp(q r)FFFF FFFTF FFTFF FFTTT TTFFF TTFTF TTTFFTTTTT T例例p(q r)50计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值p qpqp qp q p q公式公式FFTTTTTFTTFFFTTFFTFFTTTFFTTT例例(p q)(p q p q)51计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值n命题公式分类：命题

37、公式分类：A A重言式重言式(永真式永真式)：v v(A)=T(A)=T，对任意，对任意v v矛盾式矛盾式(永假式永假式)：v v(A)=F(A)=F，对任意，对任意v v可满足式：可满足式：v v(A)=T(A)=T，对某个，对某个v vn关系关系重言式是可满足式，反之不一定成立重言式是可满足式，反之不一定成立n真值判断法真值判断法重言式：真值表最后一列全为重言式：真值表最后一列全为T T矛盾式：真值表最后一列全为矛盾式：真值表最后一列全为F F可满足式：真值表最后一列至少一个可满足式：真值表最后一列至少一个T T52计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值真值表

38、有限性：给定真值表有限性：给定n n个命题变项个命题变项共有共有2 22 2n n个真值表个真值表例题：下列哪些具有相同真值？例题：下列哪些具有相同真值？a)a)p pq qb)b)q qp pc)c)(p(pq)q)d)d)(p(p q)q)p p53计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值p qpqqp(pq)(p q)pFFTTTFFTTFTTTFFTFFTTTTTF例题例题54计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值例题：下列哪些具有相同真值？例题：下列哪些具有相同真值？a)a)p pq qb)b)p p(q q r)r)c)c)

39、(p p q)q)(p(p r)r)p)p)55计算机科学与工程学院1.2 1.2 命题公式和其命题公式和其赋值赋值pqrpqp(q r)(p q)(p r)p)FFFT FT FFTT FT FTFT FT FTTT FT TFFF TF TFTF FF TTFTTTTTTT TT 例题例题56计算机科学与工程学院学习要点学习要点学习要点学习要点 命题命题的概念：定义、逻辑值、的概念：定义、逻辑值、符号化表示符号化表示 从简单命题到从简单命题到复合命题复合命题：逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级 从命题常量到命题变量，从命题常量到命题变量，从复合命题到从复合命题

40、到命题公式命题公式：命题公式的真值描述：真值表命题公式的真值描述：真值表 命题公式的命题公式的分类分类：永真公式、永假公式、可满足公式永真公式、永假公式、可满足公式 、一般公式、一般公式 57计算机科学与工程学院命题逻辑命题逻辑58计算机科学与工程学院第一章课后作业第一章课后作业符号化符号化P12：1(1)(3)(5)(7)(9)(11)(13),2P13:4(2)(3)，5(5)，9(1)(3)(5)(7)P14:12(3)，14(13)公式和赋值公式和赋值P15:15(4)，16(3)(4)，17 p15：19(3)(5)p15：20（3）p15：21（3）公式分类公式分类P15：22，25，26，27，2959计算机科学与工程学院谢谢！