第一章—命题逻辑(包含的是书上123章的内容).ppt

1、赵占山 E-mail: 授课: 60 学时 学分： 4 教学目标: 知识、能力、素质,Discrete Mathematics,研究数及其属性的学科叫做算术 研究量及其属性的学科叫做几何 研究数和量的学科叫做数学 亚里士得多 顺序=数 度量=量 数学=逻辑 逻辑是数学的少年时代 数学是逻辑的成年时代,离散数学 Discrete Mathematics 研究离散量的关系的一门科学。, 研究离散结构的数学分科。（辞海）,为什么要研究数理逻辑？ l“逻辑是不可战胜的，因为要反对逻辑还得使用逻辑。”P.Boutroux 数理逻辑是用数学方法研究形式逻辑的一门科学。 计算机可处理大量信息，要利用计算机就

2、要学会编制“程序”： 程序 = 算法 + 数据 算法 = 逻辑 + 控制 为了更好的使用计算机，就必须学习数理逻辑，引进一套符号体系，进行推理证明。 数理逻辑在人类脑力劳动自动化的过程中将起到越来越大的作用。,离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，所以又称为计算机数学，是计算机科学与技术专业的核心、骨干课程。 它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。 内容包含：数理逻辑、集合论、代数结构与布尔代数、图论等。 离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工

3、具性学科。,离散数学的由来与发展: 一、古老 历史: 计数:自然数 发展: 图论:Konigsberg（哥尼斯堡）七桥问题 二、年青 新生: 计算机:二进制运算,离散数学课程地位： 计算机系核心课程 信息类专业必修课程 其它类专业的重要选修课程 离散数学的后继课程： 数据结构、操作系统、 算法分析与设计、 数据库、c+语言,学习该课程的目的： 一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理、软件工程与方法学、计算机网络、程序设计等，提供必要的数学基础； 另一方面，通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实的数学基础

4、。,教学要求： 通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。 自学要求： 通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。,离散数学课程的学习方法: 强调：逻辑性、抽象性； 注重：概念、方法与应用 离散数学的学习要领： 概念（正确） 必须掌握好离散数学中大量的 概念 判断（准确） 根据概念对事物的属性进行判断 推理（可靠） 根据多个判断推出一个新的判断,离散数学的内容 第一部分 数理逻辑 命题演算、谓词演算 第二部分 集合论 集合、关系、函数 第三部分 代数系统 运算、代数系统、

5、半群、群、环、域、格、布尔代数 第四部分 图论 点与边、 路与圈、最短路、 Euler图、Hamilton图、平面图、树,参考教材：,1、离散数学 屈婉玲、耿素云、张立昂 高等教育出版社 2、 离散数学 左孝琳、李为槛、刘永才 上海科技文献版 3、 Discrete Mathematics Forth Edition: Richard Johnsonbaugh,各种事物的结构 人体的结构 人体由大脑、五官、四肢、心、肝、肺等器官所组成。 基本元素是各种细胞。 房屋的结构 房屋由地基、墙、门、窗、地板、房顶等建筑物所组成。 基本材料是砖、瓦、钢筋、水泥、石灰等。 学校的结构 学校由若干院、系、所

6、、处、科室、班级等单位所组成。 基本成员是教师、学生、管理人员、实验人员等 计算机的结构 计算机由主板、CPU、内存条、硬盘、软驱、电源、机箱、显示器、键盘、鼠标等部件所组成。 基本成员是各种超大规模集成电路芯片。,各个学科的结构 化学的结构 化学主要由无机化学和有机化学所组成。 基本成员是各种化学元素。 物理的结构 物理主要由力学、电学、光学、热学所组成。基本成员是各种场。 数学的结构 数学主要由连续数学和离散数学所组成。 基本成员是各种集合的元素。,离散数学与计算机的关系 第一部分 数理逻辑 计算机是数理逻辑和电子学相 结合的产物 第二部分 集合论 集合：一种重要的数据结构 关系：关系数据

7、库的理论基础 函数：所有计算机语言中不可 缺少的一部分 第三部分 代数系统 计算机编码和纠错码理论 数字逻辑设计基础 计算机使用的各种运算 第四部分 图论 数据结构、操作系统、编译原理 计算机网络原理的基础,第一章 命题逻辑,数理逻辑是研究推理（即研究人类思维的形式结构和规律）的科学，起源于17世纪，它采用数学符号化的方法，因此也称为符号逻辑。 从广义上讲，数理逻辑包括四论、两演算即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题逻辑和一阶逻辑(谓词逻辑)。本书也只研究这两个逻辑演算。,数理逻辑的创始人是Leibniz，为了实现把推理变为演算的想法，他把数学

8、引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。 上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。 1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。,第一章 命题逻辑,数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。 本章和下一章我们只从语义出发，对数理逻辑中的命题逻辑与谓词逻辑等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统。,第一章

9、 命题逻辑,著名物理学家爱因斯坦出过的一道题： 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”,第一章 命题逻辑,要回答这

10、样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程： (1) 什么是前提？有哪些前提？ (2) 结论是什么？ (3) 根据什么进行推理？ (4) 怎么进行推理？,第一章 命题逻辑,第一章 命题逻辑,1.1 命题符号化及联结词 基本概念 命题：能够判断真假的陈述句。 命题的真值：命题的判断结果。真值只取两个值： 真（1）、假（0）。 真命题：真值为真的命题。 假命题：真值为假的命题。 判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值。,第一章 命题逻辑,注意: 感叹句、祈使句、疑问句都不是

11、命题. 陈述句中的悖论以及判断结果不惟一确定的也不是命题,例1.1 下列句子中那些是命题？ (1) 是无理数. (2) 2 + 5 8. (3) x + 5 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(3)(7)都不是命题,第一章 命题逻辑,练习 判断下列句子是否为命题。 1. 100是自然数。 2. 太阳从西方升起。 3. 北京是中国的首都 4. 杭州是中国最大的城市 5. 关门! 6. 你去哪里? 7. How do you do ? 8. 凡石头均可炼成金。 9. x+

12、39 10. 皇马中国之行没有提升国家队的水平。,第一章 命题逻辑,命题及其真值的抽象化 在本书中，用小写英文字母p,q,r,p1,p2,p3 等表示命题,用“1”、“0”分别表示真值的真、假。 例1.2： p：姚明是球星。 q：5是负数。 p3：明天天气晴。 皆为符号化的命题，其真值依次为1、0、1或0。,第一章 命题逻辑,命题的分类 简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。 如上例中的命题。 复合命题：由简单命题通过联结词联结而成的陈述句。 例1.3 (1) 若三角形等腰，则两底角相等 (2) 若行列式两行成比例，则行列式值为0,第一章 命题逻辑,在命题逻辑的符号化过程中

13、，通常的要求是每一个引进的表示命题的符号都表示一个原子命题。 例如：将下列命题符号化 (1) 杭州不是中国的首都。 (2) 张三虽然学习努力但成绩并不优秀。 解 (1) 令P：杭州是中国的首都。 则命题“杭州不是中国的首都”符号化为：P (2) 令P：张三学习努力。Q：张三成绩优秀。 则命题“张三虽然学习努力但成绩并不优秀。” 符号化为：PQ。,第一章 命题逻辑,由此我们进一步明确指出： 原子命题是用肯定语气表达的具有真假意义的简单陈述句。上述例题中。直接令P表示“杭州不是中国的首都”。来做符号化，是不符合要求的。 在上述第2个命题中，如果简单地用一个符号P表示“张三虽然学习努力但成绩并不优秀

14、”做符号化就更不符合符号化的要求了。,第一章 命题逻辑,常用联结词 定义1.1 设p为命题，复合命题“非p”（或“p的 否定”）称为p的否定式，记作 p， 符号 称为否定联结词。 运算规则：属于单目运算符,第一章 命题逻辑,定义1.2 设p,q为二命题，复合命题“p并且q” （或“p与q”）称为p与q的合取式，记 作p q，符号称为合取联结词。 运算规则：属于双目运算符,第一章 命题逻辑,合取运算特点：只有参与运算的二命题全为真时，运 算结果才为真，否则为假。自然语言中的表示“并且” 意思的联结词，如“既又”、“不但而且”、 “虽然但是”、“一面一面”等都可以符号化为。 注意：不要见到“与”或

15、“和”就使用联结词 ！ 例1.4 下列命题符号化 (1) 北京不仅是中国的首都而且是一个故都 p：北京是中国的首都。 q：北京是一个故都。 pq：北京是中国的首都并且是一个故都。 宝玉和林妹妹是好朋友 P:宝玉和林妹妹是好朋友,第一章 命题逻辑,例1.4 将下列命题符号化. (3) 王晓既用功又聪明. (4) 王晓不仅聪明，而且用功. (5) 王晓虽然聪明，但不用功. (6 张辉与王丽都是三好生. (7) 张辉与王丽是同学. 解 令 p：王晓用功，q：王晓聪明，则 (3) pq (4) pq (5) pq. 令 r : 张辉是三好学生，s :王丽是三好学生 (6) rs. (7) 令 t :

16、张辉与王丽是同学， t 是简单命题 .,定义1.3 设p,q为二命题，复合命题“p或q” 称为 p与q的析取式，记作p q，符号称 为析取联结词。 运算规则：属于双目运算符,第一章 命题逻辑,注意： 按定义1.3在析取式pq中，若p，q都为真，则pq为真。 “或”还有另外一种用法：当p，q都为真时，析取起来为假。前者称为相容或，后者称为排斥或(排异或)。,例1.5 将下列命题符号化 (1) 张晓静爱唱歌或爱听音乐 . (2) 张晓静是江西人或安徽人 . (3) 张晓静只能挑选202或203房间 . 解：在解题时，先将原子命题符号化。 (1) p：张晓静爱唱歌。q：张晓静爱听音乐。 显然(1)中

17、“或”为相容或，即p与q可以同时为真，符号化为pq. (2) r：张晓静是江西人。s：张晓静是安徽人。易知，(2)中“或”应为排斥或，但r与s不能同时为真，因而也可以符号化为rs.,例1.5 将下列命题符号化 (3) 张晓静只能挑选202或203房间 . t：张晓静挑选202房间。u：张晓静挑选203房间。 由题意可知，(3)中“或”应为排斥或。t，u的联合取值情况有四种：同真，同假，一真一假(两种情况)。如果也符号化为tu，张晓静就可能同时得到两个房间，这违背题意。因而不能符号化为tu.如何达到只能挑一个房间的要求呢？可以使用多个联结词，符号化为(tu)(tu)此复合命题为真当且仅当t，u中

18、一个为真，一个为假，它准确地表达了(3)的要求。当t为真u为假时，张晓静得到202房间，t为假u为真时，张晓静得到203房间，其它情况下，她得不到任何房间。,定义1.4 设p,q为二命题,复合命题“如果p,则 q” 称为p与q的蕴涵式，记作p q， 并称p为蕴涵式的前件，q为蕴涵式的 后件，符号称为蕴涵联结词。 与自然语言的不同： 前件与后件可以没有任何内在联系！ 运算规则：属于双目运算符,第一章 命题逻辑,pq 的逻辑关系：q 为 p 的必要条件 “如果 p，则 q ” 的不同表述法很多： 若 p， 就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或 除非 q,

19、 否则非 p， 当 p 为假时，pq 为真 常出现的错误：不分充分与必要条件,例1.6 设 p:天冷，q:小王穿羽绒服， 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,注意： pq 与 qp 等值（真值相同）,pq,pq,pq,pq,qp,qp,qp,qp,例1.6 将下列命题符号化 (9) 如果22=5，则雪是黑的 令 p

20、： 22=5， q： 雪是黑的， 于是命题符号化为 p q 这是和人们日常生活中语言不一致的地方 (10) 如果我得到这部小说，那么我今夜就读完它 令 p1：我得到这部小说 q1：我今夜就读完它 于是命题符号化为 p1 q1,定义1.5 设p,q为二命题，复合命题“p当且仅当 q” 称为p与q的等价式，记作p q， 符号称为等价联结词。 说明: (1) pq 的逻辑关系:p与q互为充分必要条件 (2) pq为真当且仅当p与q同真或同假 运算规则：属于双目运算符,第一章 命题逻辑,例1.7 求下列复合命题的真值 (1) 2 + 2 4 当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当

21、 3 是偶数. (3) 2 + 2 4 当且仅当 太阳从东方升起. (4) 2 + 2 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在x0 可导的充要条件是它在 x0 连续. 它们的真值分别为 1，0，1，0，0.,第一章 命题逻辑,例1.7 (6) 2是素数当且仅当三角形有3条边； (7) 雪是黑的当且仅当太阳从东方升起. 解: (1) 令 p：2是素数， q：三角形有3条边， 则原命题符号化为pq. (2) 令 p1：雪是黑， q1：太阳从东方升起， 则原命题符号化为p1 q1 ，这是假命题 以上例子充分说明: 等价运算p q 表示的逻辑关系是：p与q互为充分必要条件。 相当于

22、(p q) (q p).,第一章 命题逻辑,例1.8 将下列命题符号化 (1) 如果你走路时看书，那么你一定会成为近视眼。 解 令p：你走路；q：你看书； r：你是近视眼。 于是，上述语句可表示为（pq）r。 (2) 除非他以书面或口头的方式正式通知我，否则我不 参加明天的会议。 解 令p：他书面通知我； q：他口头通知我； r：我参 加明天的会议。 于是，上述语句可表示为(pq) r。 (3) 设p，q，r的意义如下： p：苹果是甜的；q：苹果是红的； r：我买苹果。 试用日常语言复述下述复合命题： (a) (pq)r (b) (pq)r 解：(a)如果苹果甜且红，那么我买。 (b)我没买苹

23、果，因为苹果不甜也不红。,以上5种最基本、最常用、最重要的联结词可以组成 一个集合 ，成为一个联结词集， 其运算的优先级为： ， ，对于同一 级者，先出现者先运算。,第一章 命题逻辑,例1.9 求命题公式(pq) pq真值表.,1.2 命题公式及其分类 基本概念 简单命题/命题常项/命题常元：真值唯一确定的陈述句。 命题变项/命题变元：真值可以变化的陈述句。 命题常项与命题变项都可以用p,q,r等表示，具体情况由上下文确定。 合式公式/命题公式：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。 当使用联结词集 ，时，合式公式定义如下：,第一章 命题逻辑,定义1.6 （1）单个命题变

24、项是合式公式，并称为原子 命题公式。 （2）若A是合式公式，则(A)也是合式公式。 （3）若A，B是合式公式，则(AB)，(AB) (A B)，(A B)也是合式公式。 （4）只有有限次地应用(1)(3)形成的符号串 才是合式公式。 合式公式也称为命题公式或命题形式，并简称为公式。,第一章 命题逻辑,(p q) , (r t) e , p，(p)等均为合式公式， 而pq t , ( p w) q)等不是合式公式。 上述归纳定义方式中的符号A,B不同于具体 公式里面的p,q,r等符号，可以用来表示任意的 合式公式,属于元语言符号。 对象语言：用来描述研究对象的语言。 元语言：用来描述对象语言的语

25、言。,第一章 命题逻辑,定义1.7公式层次 （1）若公式A是单个的命题变项，则称A为0层合式 公式。 （2）称A是n+1(n0)层公式是指下列情况之一： (a) A= B, B是n层公式； (b) A=BC, 其中B, C分别为i层和j层公式, 且n=max(i,j) ； (c) A=BC, 其中B, C的层次及n同(b); (d) A=B C, 其中B, C的层次及n同(b); (e) A=B C, 其中B, C的层次及n同(b); （3）若公式A的层次为k，则称A是k层公式。,第一章 命题逻辑,例:公式 p 0层 p 1层 pq 2层 (pq)r 3层 (pq) r)(rs) 4层,第一章

26、 命题逻辑,定义1.8公式赋值 设p1 ， p2 ， ， pn是出现在公式A中的全 部的命题变项，给p1 ， p2 ， ， pn各指定一个 真值，称为对A的一个赋值或解释。 比如：对公式(p q) r一组赋值为011(意即令 p=0,q=1,r=1)可得真值为1，另一组赋值为010可得真值为0；还有000，001，111 考虑：含有n个命题变项的公式共有多少个 不同的赋值？,第一章 命题逻辑,2n个赋值.,若指定的一组值使A的真值为1，则 称这组值为A的成真赋值。( 使公式为真的赋值 ) 如对公式(p q)r赋值011，还有? 若指定的一组值使A的真值为0，则 称这组值为A的成假赋值。(使公式

27、为假的赋值) 如对公式(p q) r赋值010，还 有?,第一章 命题逻辑,真值表 将命题公式A在所有赋值下取值情况列成 表称做A的真值表。 对公式A构造真值表的具体步骤为： （1）找出公式中所有的全体命题变项p1 ， p2 ， ， pn，列出2n个赋值。 （2）按从低到高的顺序写出公式的各个层次。 （3）对应各个赋值计算出各层次的真值，直 到最后计算出公式的真值。,第一章 命题逻辑,例1.10 (1)求命题公式 (p q) r的 真值表,第一章 命题逻辑,(2) 求命题公式 (pq)( q p)的真值表。,第一章 命题逻辑,(3) 求命题公式 (p q) q 的真值表。,第一章 命题逻辑,(

28、4) 求(qp) qp 的真值表,(5) 求 (pq) q 的真值表,(6) 求 (pq) r 的真值表,公式的又一种分类方式 定义1.9 设A为任一命题公式， （1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式。 （2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式。 （3）若A不是矛盾式，则称A为可满足式。,第一章 命题逻辑,真值表的作用： （1） 表示出公式的成真或成假赋值。 （2） 判断公式类型： (a) 若真值表最后一列全为1，则为重言式； (b) 若真值表最后一列全为0，则为矛盾式； (c) 若真值表最后一列至少有一个1，则为 可满足式；,第一章 命题逻辑,有很多

29、公式具有相同的真值表。如：,第一章 命题逻辑,还有 p q、 p q等,1.3 等值演算 定义1.10 设A,B是两个命题公式，若A，B构成 的等价式A B为重言式，则称A与B 是等值的记作AB. 即AB的充要 条件是A B为重言式 判断两个公式等值的方法1：真值表法。2010/10/18,第一章 命题逻辑,小结 命题与真值（或真假值）简单命题与复合命题 联结词：否定联结词，合取联结词，析取联结词，蕴涵联结词，等价联结词 命题公式（简称公式） 命题公式的层次和公式的赋值 真值表 公式的类型（重言式（或永真式），矛盾式（或永假式），可满足式）,第一章 命题逻辑,由真值表可知，两个公式为等值式。,

30、例1.10 判断公式 p(qr)与(p q) r 是否等价,等值 演算：由已知的等值式推演出另外一些 等值式的过程。 等值演算中使用的一条重要规则：置换规则 定理1.1 设(A)是含公式A的命题公式,(B) 是用公式B置换了(A)中所有的A后 得到的命题公式， 若B A，则(A) (B)。,第一章 命题逻辑,基本等值式,双重否定律 : AA 等幂律： AAA, AAA 交换律: ABBA, ABBA 结合律: (AB)CA(BC) (AB)CA(BC) 分配律: A(BC)(AB)(AC) A(BC) (AB)(AC),基本等值式(续),德摩根律 : (AB)AB (AB)AB 吸收律: A(

31、AB)A, A(AB)A 零律: A11, A00 同一律: A0A, A1A 排中律: AA1 矛盾律: AA0,基本等值式(续),蕴涵等值式: ABAB 等价等值式: AB(AB)(BA) 假言易位: ABBA 等价否定等值式: ABAB 归谬论: (AB)(AB) A 注意: A,B,C代表任意的命题公式 牢记这些等值式是继续学习的基础,等值演算与置换规则,等值演算: 由已知的等值式推演出新的等值式的过程 置换规则：若AB, 则(B)(A) 等值演算的基础： (1) 等值关系的性质：自反、对称、传递 (2) 基本的等值式 (3) 置换规则,等值演算的用途一：证明等值式。 例1.10 验证

32、 p(qr) (p q) r 右 (p q) r 蕴涵等值式 p q r 德摩根律 p ( q r) 结合律 p ( q r) 蕴涵等值式 p ( q r) 蕴涵等值式 注:A B AB,第一章 命题逻辑,例1.11 证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假. 方法一 真值表法（自己证） 方法二 观察赋值法. 容易看出000, 010等是左 边的成真赋值，是右边的成假赋值. 方法三 用等值演算先化简两个公式，再观 察,例1.12 用等值演算法判断下列公式的类型 (1) q(pq) 解 q(pq) q

33、(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律） 由最后一步可知，该式为矛盾式.,(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1 由最后一步可知，该式为重言式. 问：最后一步为什么等值于1？,(3) (pq)(pq)r) 解 (pq)(pq)r) (p(qq)r （分配律） p1r （排中律） pr （同一律） 这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.,总结：A为矛盾式当且仅当A0 A为重言式当且仅当A1

34、 说明：演算步骤不惟一,应尽量使演算短些,等值演算的用途二：判断公式类型。 例1.13：判断公式(pq) p q的类型 原式 (pq) p) q (p q) p) q 蕴涵等值式 (p q) p q 德摩根律 (p q) p q 德摩根律 (p p) ( p q) q 分配率 1 ( p q) q ( p q) q p ( q q) p 1 1 所以为永真式。,第一章 命题逻辑,第一章 命题逻辑,例1.14：判断公式 (pq)r的类型 解： 列出真值表如下，可知其是可满足式的,等值演算的用途三：文字断案问题。 例：参见教材p11 例1.11 解：设pi, qi, ri, si分别表示A第i名,

35、 B第i名, C第i名, D第i名,由题意可知下列命题成立。 (r1q2)(r1q2) 1 (r2s3)(r2s3) 1 (p2s4)(p2s4) 1 1 (r1q2)(r1q2)(r2s3)(r2s3) (r1q2)(r2s3)(r1q2)(r2s3) (r1q2)(r2s3)(r1q2)(r2s3),第一章 命题逻辑,这里用到分配率公式 (AB)(CD) = (AC)(BC) (AD)(BD) ,由于C不能既第一又第二, 又B和C不能都第二, 故 (r1q2)(r2s3) 0 (r1q2)(r2s3) 0, (r1q2)(r1q2) 1 (r2s3)(r2s3) 1 (p2s4)(p2s4

36、) 1 1 (r1q2)(r2s3)(r1q2) (r2s3) 1 1 1p2q2r1r2s3 s4 由上式可知r1, p2, s3 是真命题，即C第一，A第二，D第三，B只能第四了。,例：参见教材p11 例1.11 解：设pi, qi, ri, si分别表示A第i名, B第i名, C第i名, D第i名,由题意可知下列命题成立。,1.4 联结词全功能集 定义1.11 设p，q是两个命题，复合命题 “p, q之中恰有一个成立”称为p与q的排斥或或异或，记作p q， 称作排斥或或异或联结词。 P q为真当且仅当p，q中恰有一个为真。,第一章 命题逻辑,P q P q 0 0 0 0 1 1 0 1

37、 1 1 0,例：马腾云现在在宿舍或在 图书馆里 令 p: 马腾云在宿舍 q:马腾云在图书馆里 该命题可表示为 P q,第一章 命题逻辑,定义1.12 设p，q是两个命题，复合命题 “p与q的否定” 称为p与q的与非式，记作pq。 “”称作与非 联结词。 pq为真当且仅当p，q不同时为 真。 由定义可知： pq=(pq)。 p q pq 0 0 1 0 1 1 1 0 1 1 1 0,定义1.13 设p，q是两个命题，复合命题 “p或q的否定”称为p与q的或非式，记作pq， 称作或非联结词。 pq为真当且仅当p，q同时为假。 由定义可知： pq=(pq),第一章 命题逻辑,p q pq 0 0

38、 1 0 1 0 1 0 0 1 1 0,第一章 命题逻辑,定义1.14 一个n(n1)维卡氏积0,1n到0,1的函数称 为一个n元真值函数。设F是一个n元真值 函数，则可记为F： 0,1n 0,1 n个命题变项，共有2n个可能的赋值，对于每个赋值真值函数的函数值非 0 即 1 ，于是n个命题变元共可以形成22 个不同的真值函数。 见教材P13 表1.6,n,命题公式与真值函数,对于任何一个含n个命题变项的命题公式A，都存在 惟一的一个n元真值函数F为A的真值表. 等值的公式对应的真值函数相同. 下表给出所有2元真值函数对应的真值表, 每一个含 2个命题变项的公式的真值表都可以在下表中找到.

39、例如：pq, pq, (pq)(pq)q) 等都对应 表中的,2元真值函数对应的真值表,其实，每个真值函数可对应无穷多个命题公式，它们彼此都是等值的，有很多公式具有相同的真值表。如：,第一章 命题逻辑,还有 p q、 p q等,第一章 命题逻辑,定义1.15 在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词。 前面给出的5个联结词组成的联结词集为 ，由于 p q p q p q (p q) (q p ) (p q ) (q p ) 所以 ， 都是冗余的，又，中，由于 p q (pq) (p q ) 所以可看成是冗余的，但在,中无冗

40、余的联结词,第一章 命题逻辑,定义1.16 若任一真值函数都可以用仅含某一联结词的命题公式表示，则称该联结词集为全功能集。若一个联结词集的全功能集中不含冗余的的联结词，则称它为极小全功能集 例1.13 若已知， 是全功能集，证明，也是 全功能集 证明 由于，是全功能集，因而任一真值函数均可由仅含，中的联结词的命题公式表示，而对于任意的命题形式A，B，有 A B AB 因而任一真值函数均可由含，中的联结词的命题公式表示，所以它是全功能集。,联结词的全功能集实例,(1) S1=, , , (2) S2=, , , , (3) S3=, (4) S4=, (5) S5=, (6) S6= (7) S

41、8=, ,定义1.1.7 在仅含联结词, , 的命题公式A中，将 换成， 换成, 若A中含0或1，就将0换成1，1换 成0，所得命题公式称为A的对偶式，记作A*。 从定义不难看出，(A*)*=A 如:公式 P (Q F)的对偶公式为P (Q F) 定理1.2 设A和A*互为对偶式，设p1,pn是出现在A 和A* 中的全部的命题变项，若将A和A* 写成n元函数 形式，则 A(P1, P2 ,Pn) A*( P1, P2 , Pn); A( P1, P2 , Pn) A*( P1, P2 , Pn).,第一章 命题逻辑,定理1.3 设A、B为两命题公式，若A B，则A*B* 其中A*，B* 分别为

42、A，B的对偶式。 该定理称为对偶原理 由对偶原理可知，若A为重言式，则A*必为矛盾 式，反之亦然 给定一个命题公式，判断它是重言式、矛盾式、 还是可满足式，这类问题称为判定问题。,第一章 命题逻辑,析取范式与合取范式 含n个命题变项的公式两种规范表示方法 定义1.18 文字：命题变项及其否定统称为文字。 如：p , q 简单析取式：仅有有限个文字组成的析取式。 如：p , q , p q , p q r 简单合取式：仅有有限个文字组成的合取式。 如：p , q , p q , p q r,第一章 命题逻辑,命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命题公式化归为一个

43、标准形式的问题，这样命题演算的研究问题就归结为对标准形式的研究问题，这种标准形式就叫范式。 析取范式 它是这样一种标准形式，在此式内不出现联结词 及，否定符号只出现在命题变元前。它是一个析取式，式中的每个析取项是个合取式，每个合取式中只包含命题变元或命题变元的否定。 例如 p(pq)(qr) 此式即具有析取范式之形式 注意:一个公式的析取范式并不唯一，如p(rq) ,可以写成(pp)(rq),合取范式 它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个合取式，式中的每个合取项是个析取式，每个析取式中只包含命题变元或命题变元的否定。 例如 p (pq) (q r)

44、 此式即具有合取范式之形式 注意:一个公式的合取范式并不唯一， 如 p (r q) 可以写成(p p) (r q),定义1.9 析取范式：由有限个简单合取式构成的析取式。 如：p q , (p q) (p q r) 合取范式：由有限个简单析取式构成的合取式。 如：p q ,（p q）（ p qr） 范式：析取范式与合取范式统称为范式。,第一章 命题逻辑,设Ai(i=1,2,3,n)为简单合取式，则 A=A1 A2 An 就是析取范式， 而 B=A1 A2 An 就是合取范式。 析取范式和合取范式有下列性质： （1）一个析取范式是矛盾式它的每个简单合取式 都是矛盾式。 （2）一个合取范式是重言式

45、它的每个简单析取式 都是重言式。,第一章 命题逻辑,定理1.4 (范式存在定理) 任一个命题公式都存在着与之等值的析 取范式与合取范式。 求范式的具体步骤： （1）消去对 ,来说冗余的联结词 ，即， 。利用下列等值式： A B ( A B) A B ( A B) (A B),第一章 命题逻辑,（2）否定词的消去或内移。 利用下列等值式： A B ( A B) ( A B) A B ( A B) A B （3）利用分配律： C ( AB) （CA）（C B） C ( AB ) （CA）（C B）,第一章 命题逻辑,例1.14 求下列公式的析取范式与合取范式 (1) A=(pq)r 解 (pq)r

46、 (pq)r （消去） pqr （结合律） 这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）,(2) B=(pq)r 解 (pq)r (pq)r （消去第一个） (pq)r （消去第二个） (pq)r （否定号内移德摩根律） 这一步已为析取范式（两个简单合取式构成） 继续： (pq)r (pr)(qr) （对分配律） 这一步得到合取范式（由两个简单析取式构成）,(3) 求(p q)(p r)的析取范式。 解：(p q) (p r) (p q) ( p r) (p q) p) (p q) r) (pp)(q p)(p r)(qr) (q p)(

47、p r)(q r),第一章 命题逻辑,(4) 求(p q)(p r)的合取范式。 解：(p q) (p r) (p q) ( p r),第一章 命题逻辑,(5) 求(p q)(pr)的析取/合取范式。 解: (1) 求析取范式 (p q) (p r) (p q) ( p r ) p q ( p r ),第一章 命题逻辑,(6) 求(p q)(pr)的析取/合取范式。 解：(2) 求合取取范式 (p q) (p r) (p q) ( p r ) ( p r ) (p q) (p r) p) q (p p) ( p r) q (p pq )( pr q ) (合取范式),第一章 命题逻辑,用到公式

48、 A(BC)= （AB)(AC ),定义1.20 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为 极小项（极大项）.10/18/2010 10:29 PM,第一章 命题逻辑,说明： n个命题变项产生2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示, mi(Mi)称为极小项(极大项)的名称. mi与Mi的关系: mi Mi , M

49、i mi,第一章 命题逻辑,由p, q两个命题变项形成的极小项与极大项,由p, q, r三个命题变项形成的极小项与极大项,极小项与极大项关系 设mi和Mi是命题变项p1 ， p2 ， pn形成的极小项和极大项，则 mi Mi ， Mi mi 定义1.21 设由n个命题变项构成的析（合）取范式中所 有的简单合（析）取式都是极小（大）项， 则称该析（合）取范式为主析（合）取范式。,由不同最小项所组成的析取式称为主析取范式 由不同最大项所组成的合取式称为主合取范式,定理 1.5 任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是惟一的. 用等值演算法求公式的主范式的步骤： (1) 先求析

50、取范式（合取范式） (2) 将不是极小项（极大项）的简单合取式 （简单析取式）化成与之等值的若干个极小 项的析取（极大项的合取），需要利用同一 律（零律）、排中律（矛盾律）、分配律、 幂等律等. (3) 极小项（极大项）用名称mi（Mi）表示， 并按角标从小到大顺序排序.,例1.15 某公司要从赵、钱、孙、李、周五名新毕 业的大学生中选派一些人出国学习. 选派 必须满足以下条件： (1)若赵去，钱也去； (2)李、周两人中至少有一人去； (3)钱、孙两人中有一人去且仅去一人； (4)孙、李两人同去或同不去； (5)若周去，则赵、钱也去. 试用主析取范式法分析该公司如何选派他们出国？ 解此类问题

51、的步骤为： 将简单命题符号化 写出各复合命题 写出由中复合命题组成的合取式 求中所得公式的主析取范式,解 设p：派赵去，q：派钱去，r：派孙 去，s：派李去，u：派周去. (1) (pq) (2) (su) (3) (qr)(qr) (4) (rs)(rs) (5) (u(pq) (1) (5)构成的合取式为 A=(pq)(su)(qr)(qr) (rs)(rs)(u(pq), A (pqrsu)(pqrsu) 结论：由可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）. A的演算过程如下: A (pq)(qr)(qr)(su)(u(pq

52、) (rs)(rs) （交换律) B1= (pq)(qr)(qr) (pqr)(pqr)(qr) (分配律),B2= (su)(u(pq) (su)(pqs)(pqu) （分配律） B1B2 (pqrsu)(pqrsu) (qrsu)(pqrs)(pqru) 再令 B3 = (rs)(rs) 得 A B1B2B3 (pqrsu)(pqrsu) 注意：在以上演算中多次用矛盾律 要求：自己演算一遍,例1.17 求(p q) (p r)的主析取范式。 解法1： P q r p p q p r (p q) (p r) 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1

53、0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1,第一章 命题逻辑,所以：(pq)(pr)m2m3m5m7(2,3,5,7),解法2： (p q) (p r) (q p) (p r)(q r) (析取范式) (pr)(q q)(pq)(rr) ( qr) (pp ) (p qr) (p q r) ( pq r) (pq r ) (主析取范式) m2 m3m5 m7 (2,3,5,7),第一章 命题逻辑,例1.18 求(p q) (p r)的主合取范式。 解法1： P q r p p q p r (p q)

54、 (p r) 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1,第一章 命题逻辑,所以：(pq)(pr)M0M1M4 M6(0,1,4,6),解法2：(p q) (p r) (pq) ( p r) (合取范式) (p q) (r r ) ( p r) (q q ) (p q r ) (p q r )(pq r) (pq r) (p q r ) (p q r )(pq r) (pq r) (主合取范式) M0M1M4 M6 (0,1,4,6),第一章 命题逻辑,例1.19 判断命题公式(p q)(p r)的类型 解法1： P q r p q p r (p q)(pr) 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1