左孝凌离散数学课件1.ppt

1、离散数学(Discrete Mathematics),第一部分 数理逻辑（Mathematical Logic),逻辑：是研究推理的科学。公元前四世纪由希腊的哲学家亚里斯多德首创。作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号, 又称为数理逻辑(或符号逻辑)。 逻辑可分为：1. 形式逻辑（通过数学方法） 数理逻辑 2. 辩证逻辑 指引进一套符号体系的方法。 辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。,第一部分 数理逻辑（Mathematical Logic),形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研

2、究概念、判断和推理及其正确联系的规律。 数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。 上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。,第一部分 数理逻辑（Mathematical Logic),1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。 从广义上讲，数理逻辑包括四论、两演算即集合论、模型论、递归论

3、、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本书也只研究这两个演算。,2020/9/28,第一部分 数理逻辑（Mathematical Logic),数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。 本篇我们只从语义出发，对数理逻辑中的命题演算与谓词演算等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统。,2020/9/28,第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法,1.1.1 命题（Proposition) 1.1.2 命题

4、的表示方法 1.1.3 命题的分类,2020/9/28,第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法,1.1.1 命题 数理逻辑研究的中心问题是推理（inference),而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。 基本概念 命题：能够判断真假的陈述句。 命题的真值：命题的判断结果。命题的真值只取两个 值:真（用T(true)或1表示）、假（用F(false)或0表示） 。 真命题：判断为正确的命题，即真值为真的命题。 假命题：判断为错误的命题，即真值为假的命题。,2020/9/28,哈哈， 这句话不是命题哦！,第一

5、章 命题逻辑（Propositional Logic）1.1 命题及其表示方法,因而又可以称命题是具有唯一真值的陈述句。 判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值。 例：判断下列句子是否为命题。 (1). 100是自然数。 T (2). 太阳从西方升起。 F (3). 3+3=8 . F,哈哈， 这句话不是命题哦！,第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法,(4). How do you do ? 疑问句，不是命题 (5). 明年的十月一日是晴天。是命题，其真值到明年 十月一日方可知道。 (6). x+39 不是命题 (7

6、). 我正在说谎。是悖论 (8). 1+101=110 二进制中为真，十进制中为假。 (9). 如果太阳从西方升起，那么2是奇数。T (10). 国足能杀入2006世界杯当且仅当2+2=4。F,第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法,(11). 今天天气多好啊！ 感叹句，不是命题 (12). 请你关上门！ 祁使句，不是命题， (13). 别的星球上有生物。 是命题，客观上能判断真 假。 说明： （1）只有具有确定真值的陈述句才是命题。一 切没有判断内容的句子，无所谓是非的句子， 如感叹句、祁使句、疑问句等都不是命题。,第一章 命题逻辑（Proposi

7、tional Logic）1.1 命题及其表示方法,（2） 因为命题只有两种真值，所以“命题逻辑”又称 “二值逻辑”。 (3) “具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。如上例中的（5）和（13）。 1.1.2 命题的表示方法 在本书中，用大写英文字母A,B,P,Q或带下标的字母P1,P2,P3 , ,或数字(1),2, ,等表示命题，称之为命题标识符。,第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法,例如： P：罗纳尔多是球星。 Q：5是负数。 P3：明天天气晴。 (2)：太阳从西方升起。 皆为符号化的命题，其真值依次为1、0、1或

8、0、0。 命题标识符又有命题常量、命题变元和原子变元 之分。 命题常量：表示确定命题的命题标识符。,第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法,命题变元：命题标识符如仅是表示任意命题的位置标 志，就称为命题变元。 原子变元：当命题变元表示原子命题时，该变元称为 原子变元。 命题变元也用A,B,P,Q,P1,P2,P3 , , 表示。 1.1.3 命题的分类： 简单/原子命题：不能分解为更简单的陈述语句的命题(如上例中的命题)。 复合命题：由简单命题通过联结词联结而成的命题。 联结词就是复合命题中的运算符。,第一章 命题逻辑（Propositional L

9、ogic）1.1 命题及其表示方法,注意： （1）一个符号(如P), 它表示的是命题常量还是命题变元，一般由上下文来确定。 （2）命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与“变数x不是数”是一样的道理。 小结：本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、命题变元和原子变元的概念。重点理解和掌握命题、命题变元两个概念。 作业：P8 （1）,19,离散数学(Discrete Mathematics),20,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),1.2.1 否定联结

10、词(Negation) 1.2.2 合取联结词(Conjunction) 1.2.3 析取联结词(Disjunction) 1.2.4 条件联结词(蕴涵联结词Conditional) 1.2.5 双条件联结(等值联结词Biconditional) ,21,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),在命题逻辑中,主要研究的是复合命题,而复合命 题是由原子命题与逻辑联结词组合而成,联结词组是 复合命题的重要组成部分. 1.2.1 否定联结词 定义1.2.1 设P为一命题， P的否定是一个新的复合命题, 称为P的否定式，记

11、作 “P”读作“非P”. 符号“ ” 称为否定联结词。 P为真当且仅当P为假. 说明： “”属于一元(unary)运算符,22,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),“”的定义也可用下表来说明. 联结词“”的定义真值表,23,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),例1. P: 天津是一个城市. Q: 3是偶数. 于是: P: 天津不是一个城市. Q: 3不是偶数. 例2. P:苏州处处清洁. Q:这些都是男同学. P:苏州不处处清洁

12、 (注意,不是处处不清洁). Q:这些不都是男同学.,24,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),1.2.2 合取联结词(Conjunction) 定义1.2.2 设P,Q为二命题，复合命题“P并且Q”（或“P与Q”）称为P与Q的合取式，记作P Q，符号“” 称为合取联结词. PQ 为真当且仅当P和Q同时为真. 联结词“”的定义真值表,25,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),说明：“” 属于二元(binary)运算符. 合取运算

13、特点：只有参与运算的二命题全为真时，运算 结果才为真，否则为假。 自然语言中的表示“并且”意思的联结词，如“既 又”、“不但而且”、“虽然但是”、“一面一面”、 “和”、 “与”等都可以符号化为 。,26,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),例3. 将下列命题符号化. (1) 李平既聪明又用功. (2) 李平虽然聪明, 但不用功. (3)李平不但聪明,而且用功. (4)李平不是不聪明,而是不用功. 解: 设 P:李平聪明. Q:李平用功. 则 (1) PQ (2) P Q (3) PQ (4) (P) Q 注意

14、：不要见到“与”或“和”就使用联结词 ！ 例如: (1)见课本P11 例题6 (2) 李敏和李华是姐妹。 （3）李敏和张华是朋友。,27,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),例4. 试生成下列命题的合取. (1) P: 我们在XNA303. Q: 今天是星期二. (2) S：李平在吃饭. R：张明在吃饭. 解: (1) PQ :我们在XNA303且今天是星期二. (2) SR:李平与张明在吃饭.,28,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connecti

15、ves),1.2.3 析取联结词(Disjunction) 定义1.2.3 设P,Q为二命题，复合命题“P或Q” 称为P与Q的析取式，记作PQ ，符号称为析取联结词. PQ为真当且仅当 P与Q中至少有一个为真. 联结词“”的定义真值表,29,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),说明：“” 属于二元(binary)运算符. 析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。 由析取联结词的定义可以看出， “”与汉语中的联结词“或”意义相近，但又不完全相同。在现代汉语中，联结词的“或”实际上有“

16、可兼或”和“排斥或”之分。考察下面命题： （1）小王爱打球或爱跑步。（可兼或） 设P：小王爱打球。 Q：小王爱跑步。 则上述命题可符号化为：P Q,30,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),（2）林芳学过英语或法语。 （可兼或） 设P：林芳学过英语。 Q：林芳学过法语。 则上述命题可符号化为： P Q （3）派小王或小李中的一人去开会。（排斥或） 设P：派小王去开会。Q：派小李去开会。 则上述命题可符号化为：(P Q) ( PQ) （4）人固有一死，或重于泰山或轻于鸿毛.(排斥或） （5）ab=0, 即a=0

17、或 b=0. （可兼或） 由此可见, “P Q”表示的是“可兼或”.,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),注意：当P和Q客观上不能同时发生时，“P或Q”可以符号化为“P Q”。 例如：小王现在在宿舍或在图书馆。 设 P：小王现在在宿舍。Q：小王现在在图书馆。 则上述命题可符号化为：P Q。,32,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),1.2.4. 条件联结词(蕴涵联结词Conditional) 定义1.2.4 设P,Q为二命题，复

18、合命题“如果P则Q(若P则Q)” 称为P与Q的条件命题,记作P Q. P Q为假当且仅当P为真且Q为假.称符号“”为条件联结词。并称P为前件，Q为后件. 联结词“”的定义真值表,33,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),注：（1）P Q表示的基本逻辑关系是,Q是P的必要条件或P是Q的充分条件. 因此复合命题“只要P就Q”、“因为P，所以Q”、“P仅当Q”、“只有Q才P”等都可以符号化为P Q 的形式。 （2） ”“ 属于二元(binary)运算符。 例5. 将下列命题符号化。 （1）天不下雨，则草木枯黄。 P：

19、天下雨。 Q：草木枯黄。 则原命题可表示为： PQ。,34,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),（2）如果小明学日语，小华学英语，则小芳学德语。 P：小明学日语 Q：小华学英语 R：小芳学德语. 则原命题可表示为：(PQ)R （3）只要不下雨，我就骑自行车上班。 P：天下雨。Q：我骑自行车上班。 则原命题可表示为： PQ。 （4）只有不下雨，我才骑自行车上班。 P：天下雨。Q：我骑自行车上班。 则原命题可表示为： Q P 。,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logi

20、cal Connectives),（5）如果 2+2=4, 则太阳从东方升起。 (P Q, T) P Q 如果 2+2=4, 则太阳从西方升起。 (P R, F) R 如果 2+2 4, 则太阳从东方升起。 (P Q , T) 如果 2+2 4, 则太阳从西方升起。 (P R, T) 注意: (1)与自然语言的不同：前件与后件可以没有任何内在联系！ (2) 在数学中，“若P则Q”往往表示前件P为真，则后件Q为真的 推理关系. 但数理逻辑中，当前件P为假时， P Q的真值为真。,36,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectiv

21、es),1.2.5 双条件联结(等值联结词Biconditional) 定义1.2.5 设P,Q为二命题，复合命题“P当且仅当Q” 称为P与Q的双条件命题，记作P iff Q或 PQ，符号称为双条件（等值）联结词。 PQ为真当且仅当P，Q真值相同。 联结词“”的定义真值表,37,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),注：（1）P仅当Q 可译为PQ P当Q 可译为QP P当且仅当Q 译为PQ （2）“”属于二元(binary)运算符。 (3) 双条件命题PQ所表达的逻辑关系是, P与Q互为充分必要条件,相当于(P

22、Q) (Q P). 只要P与Q的真值同为1或同为0, PQ的真值就为1, 否则PQ的真值为0. 双条件联结词连接的两个命题之间可以没有因果关系。 例6.分析下列命题的真值. (1) 2+2=4 当且仅当3是奇数 . (PQ) P： 2+2=4. Q：3是奇数 .,38,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),(2) 2+2=4 当且仅当3不是奇数 . (PQ) (3) 2+2 4 当且仅当3是奇数 . (PQ) (4) 2+2 4 当且仅当3不是奇数 . (PQ) 约 定:1. 运算次序优先级：，. 2. 相同的运

23、算符按从左至右次序计算，否则要 加上括号。 3.最外层圆括号可省去。 小结: 本节介绍了五种联结词(，),重点是理解和掌握五种联结词的内涵及它们与自然语言中相应联结词的不同之处.,39,第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives),作业: 1. P8 (3), (5). 2. 预习1.3, 1.4 思考题: 1. 何谓合式公式? 2. 复合命题符号化的基本步骤是什么? 3.何谓真值表? 4. 两个命题公式等价的涵义是什么? 5.两个等价的命题公式其真值表有何关系?,40,离散数学(Discrete Mathematics

24、),41,第一章 命题逻辑（Propositional Logic）1.3命题公式与翻译,1.3.1 命题公式 1.3.2 复合命题的符号化(翻译) 1.3.1 命题合式公式(Well-formed formula)(wff) 定义1.3.1:单个命题变元和命题常量称为原子公式。 命题合式公式是由命题变元、命题常量、联结词和圆括号按一定的逻辑关系联结起来的符号串。我们以如下递归的形式来定义合式公式：,42,第一章 命题逻辑（Propositional Logic）1.3命题公式与翻译,定义1.3.2：(1)原子公式是合式公式(wff)。 （2）若A是合式公式，则( A)也是合式公式。 （3）若

25、A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。 （4）当且仅当有限次地应用(1)(3)所得到的包含原子公式、联结词和括号的符号串是合式公式。 注: (1)合式公式也称为命题公式，并简称为公式。 (2)命题公式一般不是命题,仅当公式中的命题变元用确定的命题代入时,才得到一个命题.其真值依赖于代换变元的那些命题的真值.,43,第一章 命题逻辑（Propositional Logic）1.3命题公式与翻译,例1：指出(P(PQ)是否是命题公式(wff)，如果是，则具体说明。 解： P是wff 由(1) Q是wff 由(1) PQ是wff 由(3) (P(PQ) 由(3) 例

26、2: (P Q) , (R S) Q , P，( P)等均为合式公式，而PQ S , (P W) Q)等不是合式公式。,44,第一章 命题逻辑（Propositional Logic）1.3命题公式与翻译,1.3.2 复合命题的符号化(翻译) 有了命题演算的合式公式的概念,我们可以把自然语言中的有些语句(复合命题),翻译成数理逻辑中的符号形式.基本步骤如下: (1) 分析出各简单命题,将它们符号化; (2) 使用合适的联结词,把简单命题逐个的联结起来,组成复合命题的符号化表示.,45,第一章 命题逻辑（Propositional Logic）1.3命题公式与翻译,例3： 1) 我今天进城，除非

27、下雨。1-3.(7) 2) 仅当你走我将留下。 3) 假如上午不下雨，我去看电影，否则就在家里 读书或看报。 4)除非你努力，否则你将失败。P11例5 5)一个人起初说：“占据空间的、有质量的而且不断变化的叫做物质”；后来他改说，“占据空间的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式进行分析。 1-3.(6),46,第一章 命题逻辑（Propositional Logic）1.3命题公式与翻译,例4：P10 例题1 小结：本节介了命题公式的概念及复合命题的符号化.重点是理解命题公式的递归定义,掌握复合命题的符号化方法. 作业: P12 (1),(5),4

28、7,离散数学(Discrete Mathematics),48,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,1.4.1 真值表(Truth Table) 1.4.2 等价公式(Propositional Equivalences) 1.4.1 真值表 前面在定义联结词时,曾经使用过真值表,下面给出 真值表的定义. 定义1.4.1 (对公式的赋值或解释)设P1 , P2 ,Pn是出 现在公式A中的全部的命题变元, 给P1 , P2 ,Pn各指 定一个真值，称为对A的一个赋值或解释。若指定的 一组值使A的真值为真(假), 称这组值为A的成真(假)赋值.,49

29、,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,比如:对公式(PQ)R,赋值011(即令P=0,Q=1,R=1) 为(PQ)R的成真赋值; 另一组赋值010为(PQ)R的成假赋值；还有000，001，111 考虑：含有n个命题变元的公式共有多少组不同的赋值？ 定义1.4.2(真值表)在命题公式A中, 对于命题变元的每一组赋值和由它们所确定的命题公式A的真值列成表，称做命题公式A 的真值表。,50,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,对公式A构造真值表的具体步骤为： （1）找出公式中所有命题变元P1 , P2

30、,Pn , 列出全部的2n组赋值。 （2）按从小到大的顺序列出对命题变元P1 , P2 ,Pn ,的全部2n组赋值。 （3）对应各组赋值计算出公式A的真值，并将其列在对应赋值的后面。,51,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,例1. 给出(PQ)(PQ)的真值表：,52,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,例1. 给出(PQ)(PQ)的真值表：,53,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,例2：构造公式 (P Q) R的 真值表。,54,第一章 命题逻辑

31、（Propositional Logic） 1.4真值表与等价公式,例2：构造公式 (P Q) R的 真值表。,55,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,练习1：构造公式 (PQ)( Q P真值表。,56,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,练习1：构造公式 (PQ)( Q P真值表。,57,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,练习2：构造公式 (P Q Q 真值表。,58,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价

32、公式,练习2：构造公式 (P Q Q 真值表。,59,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,1.4.2 等价公式 给定n个 命题变元, 按合式公式的形成规则可以形成无数多个命题公式, 但这些无穷尽的命题公式中，有些具有相同的真值表。考虑：由n个命题变元能生成? 种真值(表)不同的命题公式？,60,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,1.4.2 等价公式 定义1.4.3: 给定两个命题公式A和B,设P1 , P2 ,Pn为出现于A和B中的所有原子变元,若给P1 , P2 ,Pn任一组真值指派, A和B的

33、真值都相同,则称A和B是等价的或逻辑相等.记作A B 注: (1) “ ”不是逻辑联结词. (2)命题公式之间的逻辑相等关系具有： 自反性：A A ；对称性：若A B，则B A； 传递性：若A B且B C，则A C。,61,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,证明公式等价的方法： 1. 真值表法 2. 等值演算法 1. 真值表法 例1. (PQ) (PQ) 见真值表例题1. 例2. 证明: PQ (PQ)(QP),62,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,证明公式等价的方法： 1. 真值表法 2.

34、等值演算法 1. 真值表法 例1. (PQ) (PQ) 见真值表例题1. 例2. 证明: PQ (PQ)(QP),63,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,例3：判断公式 P(QR)、(PQ)R是否等价。,64,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,由真值表可知，两个公式为等价式。 2、等值演算法(Equivalent Caculation)（利用P15表1-4.8) 重要的等价式(补充): 11. 蕴涵等值式: PQ PQ 12. 等价等值式: PQ (PQ)(QP) 13. 假言易位: PQ Q

35、P 14. 等价否定等值式: PQ PQ 15. 归谬论: (PQ ) ( P Q) P,65,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,其中P, Q, R等代表任意命题公式. 这样上面的每一个公式都是一个模式, 它可以代表无数多个同类型的命题公式. 例如, PPT 中, 用(PQ)置换P,则得 (PQ)(PQ)T ,用P置换P,则得 (P)(P)T 。 等值演算中使用的一条重要规则：置换规则。 定义1.4.4(子公式)：如果X是wff A的一部分,且X本身也是wff，则称X是A的子公式。例如, P(PQ)为Q (P(PQ)的子公式。,66,第一章 命

36、题逻辑（Propositional Logic） 1.4真值表与等价公式,定理1.4.1(置换定理Axiom of replacement)设X是wff A的子wff，若XY，则若将A中的X用Y来置换，所得公式B与A等价，即AB。 证：因为对变元的任一指派,X与Y真值相同，所以Y 取代X后，公式B与公式A对变元的任一指派真值也相同,所以AB。 注: 满足定理1.4.1的条件的置换称为等价置换(或等价代换). 定义1.4.5(等值演算)：根据已知的等价公式,推演出另外一些等价公式的过程称为等值演算.,67,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,例1：

37、 证明 Q（P（PQ）QP 证: Q（P（PQ）QP P(吸收律) 例2： 证明 PQQ PQ 证： (PQ)Q(PQ)(QQ)(PQ)TPQ 例3：证明（PQ）（QP） PQR 证：（PQ）（QP） （PQ）（QR） （PQ）（QR） （PQ）（QR） （PQR）（QQR） PQR,68,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,例4：验证P(QR) (P Q) R 证: 右 (P Q) R P Q R P ( Q R) P (Q R) P (Q R) 练：1.(P Q) (P R) P (Q R) 2.(P Q) ( P Q) (P Q) (P Q

38、),69,第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,等值演算在计算机硬件设计中,在开关理论和电子元器件中都占有重要地位. 小结: 本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式（24个）。重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。 作业：P17 1 c,e, 4 a,c, 7d,e, 8. 预习: 1.5, 1.6 思考题：9,70,离散数学(Discrete Mathematics),张捷,71,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology

39、and Implication),1.5.1 命题公式的分类 1.5.2 重言式(Tautology)与矛盾式 (contradictory)的性质 1.5.3 蕴含式( Implication),72,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),1.5.1 命题公式的分类 复合命题 (compound propositions) 定义1.5.1 设A为任一命题公式， （1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式, 记为T或1。 （2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假

40、式, 记为F或0。 （3）若A不是矛盾式则称A为可满足式(satisfiable)。注: 由定义可知,重言式一定是可满足式,反之不真.,73,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),判别命题公式的类型有两种方法: 真值表法和等值 演算法. 等值演算法是将所给命题公式通过等值演算化为最 简单的形式, 然后再进行判别. 例1.判别下列命题公式的类型. (1). Q(PQ)P) (重言式) (2). (PP) (QQ)R (矛盾式) (3). (P Q)P. (可满足式),74,第一章 命题逻辑（Prop

41、ositional Logic） 1.5重言式与蕴含式(Tautology and Implication),1.5.2 重言式(Tautology)与矛盾式(contradictory)的性质定理1.5.1:任何两个重言式的合取或析取,仍然是一重言式.（由幂等律立得） 证明:设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为T,故A B T,A B T 定理1.5.2:一个重言式(矛盾式),对同一分量都用任何合式公式置换,其结果仍为一重言式(矛盾式). 证明: 由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以任何合式公式置换后，重言式(矛盾式)的真值仍永为T（

42、F）。,75,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),定理1.5.3： A,B是两个命题公式，A B的充要条件是A B为重言式。 证明: 若AB为重言式，则AB永为T，即A，B的真 值表相同，所以AB。 反之，若A B，则A，B真值表相同， 所以 AB永为T，所以AB为重言式。 1.5.3 蕴含式( Implication) 定义1.5.2：当且仅当P Q是一个重言式时，我们称“P蕴含Q”，并记作P Q.,76,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tau

43、tology and Implication),它们之间具有如下关系: PQ Q P 由P21 表1-5.1 QP P Q 可以得出 因此, 要证明P Q有三种方法: 1)真值表法:即列出PQ的真值表,观察其是否为永真。 2)直接证法:假定前件P是真，推出后件Q是真。 3)间接证法:假定后件是假，推出前件是假,即证 Q P 。,77,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),例: 证明Q（PQ）P 1) 法1：真值表 2) 法2：若 Q(PQ)为真，则 Q，PQ为真， 所以Q为假，P为假，所以P为真。

44、 3) 法3：若P为假，则P为真，再分二种情况： 若Q为真，则Q为假,从而Q（PQ） 为假. 若Q为假，则PQ为假，则Q（PQ）为假. 根据 ，所以 Q（PQ）P P21 表1-5.2给出了14个蕴含式, 它们都可以用上述方法加以推证.,78,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),等价式与蕴含式的关系: 定理1.5.4: 设P,Q为任意两个命题公式,PQ的充要条件为PQ且QP. 证：若PQ，则PQ为永真式 因为 PQ （PQ）（QP） 所以 PQ，QP为永真式,从而 PQ，QP. 反之，若PQ，Q

45、P，则PQ，QP为永真式, 所以（PQ）（QP）为永真式， 从而 PQ为永真式，即PQ.,79,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),蕴含的性质: 设A，B，C为任意wff, 1) 若AB，且A为永真式，则B必为永真式. 2) 若AB，BC，则AC. 3) 若AB，AC，则ABC. 4) 若AB且CB，则ACB. 证：1)因为AB，A永为T,所以B必永为T. 2)由I11 （AB)(BC）AC,所以若AB， BC，则（AB)(BC）永为T,从而AC永 为T, 故AC.,80,第一章 命题逻辑（Pr

46、opositional Logic） 1.5重言式与蕴含式(Tautology and Implication),3) （AB）（AC） （AB）（AC） A（BC） ABC 4) （AB）（CB） （AB）（CB） （AC）B （AC）B ACB,81,第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication),小结：本节介绍了命题公式的分类，重言式、矛盾式与蕴含式的概念及其性质，等价式与蕴涵式的关系。 重点掌握: （1）用等值演算法判别命题公式的类型。 （2）重言式、矛盾式与蕴涵式的性质。 （3）等价式与蕴涵式的关

47、系。 作业: P23 (1)c,d ,(2) a ,(9). 预习:1.6 思考题:1) 为什么要引入联结词 ? 2) 什么是最小联结词组?,82,离散数学(Discrete Mathematics),张捷,83,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),1.6.1 不可兼析取(排斥或/异或)(exclusive or) 1.6.2 与非联结词(Nand) 1.6.3 或非联结词(Nor) 1.6.4 条件否定联结词(Non-conditional) 1.6.5 最小联结词组(The minimal set of con

48、nectives),84,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),在第二节(1.2)中我们定义了五种基本的联结词， ， ，,但在命题逻辑中,这些联结词还不能很广泛 地直接表达命题之间的联系(例如, “P异或Q”只能间接地 表示为(PQ)(PQ),为此本节再给出逻辑设计中 常用的另外四种联结词. 1.6.1 不可兼析取(排斥或/异或)(exclusive or) 定义1.6.1:设P,Q为二命题，复合命题“P, Q之中恰有一个为真” 称为P与Q的不可兼析取，记作P Q，符号“ ” 称为异或联结词. P Q 为真当且仅当P

49、和Q的真值不同.,85,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),联结词“ ”的定义真值表,定义了联结词“ ”后, 命题逻辑中的有些命题就可以符号化为非常简捷的形式. 例: 派小王或小李中的一人去开会。（排斥或） 设P：派小王去开会。Q：派小李去开会。 则上述命题可符号化为：(P Q),86,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),说明：“ ” 属于二元(binary)运算符. 联结词“ ”的性质: 设P, Q, R为命题公式, 则有 (1) P

50、 Q Q P (交换律) (2) (P Q) R P (Q R) (结合律) (3) P(Q R) (PQ ) (PR) (分配律) (4) (P Q) (P Q) ( PQ) (5) (P Q) (PQ) (6) P P F, F P P, T P P,87,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),定理1.6.1:设P, Q, R为命题公式, 如果 P QR,则 P RQ ,Q RP, 且P Q R 为一矛盾式. 证: 由 P QR 得 P RP (P Q)(P P) QF QQ Q RQ (P Q)F PP P Q

51、 RR RF,88,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),1.6.2 与非联结词(Nand) 定义1.6.2 设P,Q为二命题，复合命题“P与Q的否定” 称为P与Q的与非式，记作PQ，符号“” 称为与非联结词. PQ 为真当且仅当P和Q不同时为真. 联结词“”的定义真值表,89,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),说明: (1) 由定义可知, PQ (PQ) (2)“” 属于二元(binary)运算符. 联结词“”的性质: (1) PP

52、( PP) P (2) (PQ)(PQ) ( PQ)(PQ) (3)(PP)(QQ) P Q(PQ) PQ,90,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),1.6.3 或非联结词(Nor) 定义1.6.3 设P,Q为二命题，复合命题“P或Q的否定” 称为P与Q的或非式，记作PQ ，符号“”称为或非联结词. PQ为真当且仅当 P与Q同为假. 联结词“”的定义真值表,91,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),说明: (1) 由定义可知, PQ (

53、PQ) (2)“” 属于二元(binary)运算符. 联结词“”的性质: (1) PP ( PP) P (2) (PQ)(PQ) (PQ) (PQ) (3)(PP)(QQ)PQ(PQ)PQ,92,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),1.6.4 条件否定联结词(Non-conditional) 定义1.6.4 设P,Q为二命题，复合命题“P Q” 称为命题P与Q的条件否定式, P Q为真当且仅当P为真且Q为假. 联结词“ ”的定义真值表,93,第一章 命题逻辑（Propositional Logic） 1.6其它联结

54、词(Other Connectives),说明: (1) 由定义可知, P Q (P Q) (2)“ ” 属于二元(binary)运算符. 有了联结词 后，合式公式的定义1.3.2可加入这 四个联结词. 1.6.5 最小联结词组(The minimal set of connectives) 至此,我们一共定义了9个联结词,为了直接表达命题之间 的联系,是否还需要定义其它联结词呢? 回答是否定的.即 含n个命题变元的所有 个互不等价的命题公式,均可由这 9个联结词直接表达.下面我们以含两个命题变元P，Q的所 有互等价的命题公式为例，来说明这一问题。,94,第一章 命题逻辑（Propositio

55、nal Logic） 1.6其它联结词(Other Connectives),由两个命题变元P，Q所构成的互不等价的 个命题公式 如下:,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),由上表可知, 9个联结词足以直接表达命题之间的各种联系.二元运算中，9个联结词并不都是必要的。,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),定义1.6.5：在一个联结词的集合中,如果一个联结词可 由该集合中的其它联结词定义,则称此联结词为冗余联 结词,否则称为独立联结词.

56、不含冗余联结词的联结词组 称为最小联结词组. 说明:最小联结词组中的联结词构成的式子足以把一切命题公式等价的表达出来。 对于9个联结词的集合, , , , 由于 (1) PQ (PQ)(QP) (2) PQPQ (3) PQ(PQ) (4) PQ(PQ),97,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),(5) (P Q) (PQ) (6) PQ (PQ) (7) PQ (PQ) (8) P Q (P Q) 故任意命题公式都可由仅包含,或, 的命题 公式等价代换.即9个联结词的集合中至少有七个冗余联 结词. 又注意到联结词

57、,和, 不再有冗余联结 词, 故,或, 为最小联结词组.但实际中为了使 用方便, 命题公式常常同时包含, .,98,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),例1:试证是最小联结词组. 证：P(PP)PP PQ(PQ)(PQ)(PQ)(PQ) PQ(PQ)(PP)(QQ) (PP)(QQ) 例2.试证，是最小联结词组 证：PQ(PQ)(PQ) PQ(P)QPQ 小结:本节主要介绍了四种新的联结词 及最 小联结词组. 作业: 1. P29 (1), (2), (4),99,第一章 命题逻辑（Propositional Lo

58、gic） 1.6其它联结词(Other Connectives),2. 预习1.7 思考题: 1. 何谓命题公式的(主)析(合)取范式? 2.命题公式的(主)析(合)取范式唯一吗? 3.为何要将命题公式化为与之等价的主析(合)取范式? 4. 如何将命题公式化为与之等价的主析(合)取范式? 5.两个等价的命题公式其(主)析(合)取范式有何关系?,100,离散数学(Discrete Mathematics),张捷,101,第一章 命题逻辑（Propositional Logic） 1.7对偶与范式(Dual (2)一个合取范式是重言式,当且仅当它的每一个简单析取式都是重言式. 定理1.7.4 (范式存在定理) 任一个命题公式都存在着与之等价的析取范式与合取范式。,112,第一章 命题逻辑（Propositional Logic） 1.7对偶与范式(Dual (2) 除去 中所有永假的析取项;,122,第一章 命题逻辑（Pr