离散数学-命题逻辑课件

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

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

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

4、词,1.3 命题公式与翻译,1.4 真值表与等价公式,1.5 重言式与蕴含式,1.6 其他联结词,1.7 对偶与范式,1.8 推理理论,2020/9/15,7,1.1 命题及其表示方法,命题的定义,命题的表示方法,命题的分类,小结,2020/9/15,8,一、命题(Statement,Proposition)的定义,数理逻辑研究的中心问题是推理(inference)，而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。,命题的真值(Truth,Value)：命题的判断结果。命题的真值只取两个值：真(用T(true)或1表示)、假(用F(false)或0表示) 。,

5、定义1-1.1 具有确定真假值的陈述句，称为命题。,真命题：判断为正确的命题，即真值为真的命题。,假命题：判断为错误的命题，即真值为假的命题。,1-1 命题及其表示方法,2020/9/15,9,判断命题的两个步骤： 是否为陈述句； 是否有确定的、唯一的真值。,例 判断下列句子是否为命题。 (1) 今天天气多好啊！ (2) 请你关上门. (3) How do you do ? (4) 3+3=8 . (5) 吸烟有害健康。,T,感叹句，不是命题,祈使句，不是命题,疑问句，不是命题,F,1-1 命题及其表示方法,2020/9/15,10,(6) 太阳从西方升起。 (7) x+39 (8) 1+10

6、1=110 (9) 国足能杀入2014世界杯当且仅当2+2=4。 (10)如果太阳从西方升起，那么2是奇数。 (11)今年五月一日是晴天。 (12)明天我去看电影。 (13)宇宙中有外星人。 (14)我正在说谎。,不是命题,二进制中为真，十进制中为假,F,T,是命题，其真值到五月一日方可知道,是命题，客观上能判断真假,悖论，不是命题,F,是命题，客观上能判断真假,1-1 命题及其表示方法,2020/9/15,11,说明 只有具有确定真值的陈述句才是命题。一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。 因为命题只有两种真值，所以“命题逻辑”又称 “二值逻辑”。

7、“具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。如上例中的(11)(12)(13).,1-1 命题及其表示方法,2020/9/15,12,二、命题的表示方法,在本书中，用大写英文字母 A,B,P,Q 或带下标的字母P1,P2,P3, , 或数字(1),2, ,等表示命题，称之为命题标识符(Proposition Identifier)。,例如 P：梅西是球星。 Q：5是负数。 P3：明天天气晴。 (2)：太阳从西方升起。 皆为符号化的命题，其真值依次为1、0、1或0、0。,1-1 命题及其表示方法,2020/9/15,13,命题常量(Proposition Constant)

8、：表示确定命题的命题标识符。,命题标识符又有命题常量、命题变元和原子变元之分。,命题变元(Proposition Valiable) ：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。,原子变元(Atomic Valiable)：当命题变元表示原子命题时，该变元称为原子变元。,1-1 命题及其表示方法,2020/9/15,14,注意：,一个符号(如P)，它表示的是命题常量还是命题变元，一般由上下文来确定。 命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与“变数x不是数”是一样的道理。,1-1 命题及其表示方法,2020/9/15,15,简单命题(Simple Prop

9、osition)/原子命题(Atomic Proposition)/本原命题(Primitive Proposition)：不能分解为更简单的陈述语句的命题(如上例中的命题)。,三、命题的分类,复合命题(Compound Proposition) ：由简单命题通过联结词联结而成的命题。联结词就是复合命题中的运算符。,1-1 命题及其表示方法,2020/9/15,16,四、小结,本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、命题变元和原子变元的概念。 重点理解和掌握命题、命题变元两个概念。,作业：P8 (1),1-1 命题及其表示方法,2020/9/15,17,离散数

10、学(Discrete Mathematics),2020/9/15,18,1-2 命题联结词(Logical Connectives),否定联结词(Negation) 合取联结词(Conjunction) 析取联结词(Disjunction) 条件联结词(蕴涵联结词Conditional) 双条件联结(等值联结词Biconditional) 小结,2020/9/15,19,一、否定联结词(Negation) ,在命题逻辑中，主要研究的是复合命题，而复合命题是由原子命题与逻辑联结词组合而成，联结词是复合命题的重要组成部分。,定义1-2.1 设P为一命题，P的否定是一个新的复合命题，称为P的否定式

11、，记作 “P”，读作“非P”，符号“” 称为否定联结词。 P为真当且仅当P为假.,1-2 命题联结词(Logical Connectives),2020/9/15,20,联结词“”的定义真值表,“” 属于一元运算符.,1-2 命题联结词(Logical Connectives),2020/9/15,21,例1 P：西安是一个城市. Q：3是偶数. 则 P：西安不是一个城市. Q：3不是偶数.,例2 P：西安处处清洁. Q：这些都是男同学. 则 P：西安不处处清洁 (注意，不是处处不清洁). Q：这些不都是男同学.,1-2 命题联结词(Logical Connectives),2020/9/15

12、,22,二、合取联结词(Conjunction) ,定义1-2.2 设P,Q为命题，复合命题“P并且Q” (或“P与Q”)称为P与Q的合取式，记作PQ，符号“” 称为合取联结词。当且仅当P和Q同时为真时PQ 为真。,联结词“”的定义真值表,1-2 命题联结词(Logical Connectives),2020/9/15,23,“” 属于二元(binary)运算符. 合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。 自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”、“一面一面”、 “和”、 “与”等都可以符号化为 。,1-2 命题联结词(Logi

13、cal Connectives),2020/9/15,24,24,例3 将下列命题符号化. (1) 张三既聪明又用功. (2) 张三虽然聪明，但不用功. (3) 张三不但聪明，而且用功. (4) 张三不是不聪明，而是不用功.,不要见到“与”或“和”就使用联结词 。例如: (1) 我与你是兄弟。 (2) 张三和李四是朋友。,解,解 设 P：张三聪明。 Q：张三用功。,1-2 命题联结词(Logical Connectives),则,(2) PQ,(3) PQ,(4) (P)Q,(1) PQ,2020/9/15,25,例4 试生成下列命题的合取. (1) P：房间里有张桌子. Q：今天是星期三.

14、(2) S：李平在吃饭. R：张明在吃饭.,“”与自然语言中“与”“和”的不同之处：,解,(1) PQ：房间里有张桌子且今天是星期二.,1-2 命题联结词(Logical Connectives),(2) SR：李平与张明在吃饭.,2020/9/15,26,三、析取联结词(Disjunction),定义1-2.3 设P,Q为命题，复合命题“P或Q” 称为P与Q的析取式，记作PQ ，符号称为析取联结词. PQ为真当且仅当 P与Q中至少有一个为真.,联结词“”的定义真值表,1-2 命题联结词(Logical Connectives),2020/9/15,27,“” 属于二元(binary)运算符.

15、,析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。,由析取联结词的定义可以看出， “”与汉语中的联结词“或”意义相近，但又不完全相同。在现代汉语中，联结词的“或”实际上有“可兼或”和“排斥或”之分。考察下面命题： (1) 小王爱打球或爱跑步。,设P：小王爱打球。 Q：小王爱跑步。,1-2 命题联结词(Logical Connectives),（可兼或）,则上述命题可符号化为：P Q,2020/9/15,28,(4)人固有一死，或重于泰山或轻于鸿毛.,(2) 张三学过英语或法语。,设P：张三学过英语。 Q：张三学过法语,(3) 派小王或小李中的一人去开会。,设P：派小王去开

16、会。Q：派小李去开会。,(5) ab=0, 即a=0 或 b=0.,由此可见, “P Q”表示的是“可兼或”.,则上述命题可符号化为： P Q,则上述命题可符号化为：(PQ) (PQ),1-2 命题联结词(Logical Connectives),（可兼或）,（排斥或）,（排斥或）,（可兼或）,2020/9/15,29,注意：当P和Q客观上不能同时发生时，“P或Q”可以符号化为“P Q”。,“”与自然语言中“或”的不同之处：,例如：小王现在在宿舍或在图书馆。 设 P：小王现在在宿舍。Q：小王现在在图书馆。,则上述命题可符号化为：P Q。,1-2 命题联结词(Logical Connective

17、s),2020/9/15,30,四、条件联结词(蕴涵联结词Conditional),定义1-2.4 设P,Q为命题，复合命题“如果P那么Q(若P则Q)” 称为P与Q的条件命题，记作P Q. P Q为假当且仅当P为真且Q为假。称符号“”为条件联结词。并称P为前件，Q为后件.,联结词“”的定义真值表,1-2 命题联结词(Logical Connectives),2020/9/15,31,PQ表示的基本逻辑关系是：Q是P的必要条件或P是Q的充分条件. 因此复合命题“只要P就Q”、“因为P，所以Q”、“P仅当Q” 、“Q每当P” 、“只有Q才P”等都可以符号化为P Q 的形式。 “”属于二元(bina

18、ry)运算符。,例5 将下列命题符号化。 (1)天不下雨，则草木枯黄。,设 P：天下雨。Q：草木枯黄。,则原命题可表示为： PQ。,1-2 命题联结词(Logical Connectives),2020/9/15,32,(2)如果小明学日语，小华学英语，则小芳学德语。,设 P：小明学日语 Q：小华学英语 R：小芳学德语,(3)只要不下雨，我就骑自行车上班。,(4)只有不下雨，我才骑自行车上班。,设 P：天下雨。Q：我骑自行车上班。,设 P：天下雨。Q：我骑自行车上班。,则原命题可表示为：(PQ)R,则原命题可表示为： PQ,则原命题可表示为： Q P 。,1-2 命题联结词(Logical C

19、onnectives),2020/9/15,33,例6 设 P：2+2=4 Q：太阳从东方升起 R：太阳从西方升起 符号化下列命题，并判断命题的真值： (1) 如果 2+2=4，则太阳从东方升起。 (2) 如果 2+2=4，则太阳从西方升起。 (3) 如果 2+24，则太阳从东方升起。 (4) 如果 2+24，则太阳从西方升起。,解,(1) P Q， T,1-2 命题联结词(Logical Connectives),(2) PR， F,(3) P Q ， T,(4) P R， T,2020/9/15,34,注意:,与自然语言的不同：前件与后件可以没有任何内在联系！ 在数学中，“若P则Q”往往表

20、示前件P为真，则后件Q为真的推理关系. 但数理逻辑中，当前件P为假时， P Q的真值为真。,1-2 命题联结词(Logical Connectives),2020/9/15,35,五、双条件联结词(等值联结词Biconditional) ,定义1-2.5 设P,Q为命题，复合命题“P当且仅当Q” 称为P与Q的双条件命题，记作 P iff Q 或 PQ，符号称为双条件（等值）联结词。 PQ为真当且仅当P与Q的真值相同。,联结词“”的定义真值表,1-2 命题联结词(Logical Connectives),2020/9/15,36,“P仅当Q” 可译为,“P每当Q” 可译为,“P当且仅当Q” 可译

21、为,说明:,1-2 命题联结词(Logical Connectives),PQ,QP,PQ,“”属于二元(binary)运算符。 双条件命题PQ所表达的逻辑关系是，P与Q互为充分必要条件，相当于(PQ)(QP). 只要P与Q的真值同为1或同为0，PQ的真值就为1， 否则PQ的真值为0。双条件联结词连接的两个命题之间可以没有因果关系。,2020/9/15,37,例6 分析下列命题的真值(P: 2+2=4 Q: 3是奇数 ) (1) 2+2=4 当且仅当3是奇数 . (2) 2+2=4 当且仅当3不是奇数 . (3) 2+24 当且仅当3是奇数 . (4) 2+24 当且仅当3不是奇数 .,PQ，

22、,约定:,运算次序优先级：，. 相同的运算符按从左至右次序计算，否则要加上括号。 最外层圆括号可省去。,PQ，,PQ，,PQ，,1-2 命题联结词(Logical Connectives),T,F,F,T,2020/9/15,38,作业: P8 (3), (5). 预习1.3, 1.4，并思考: (1) 何谓合式公式? (2) 复合命题符号化的基本步骤是什么? (3) 何谓真值表? (4) 两个命题公式等价的涵义是什么? (5) 两个等价的命题公式其真值表有何关系?,六、小结,本节介绍了五种联结词(，)。 重点是理解和掌握五种联结词的内涵及它们与自然语言中相应联结词的不同之处.,1-2 命题联

23、结词(Logical Connectives),2020/9/15,39,离散数学(Discrete Mathematics),2020/9/15,40,1-3 命题公式与翻译,命题公式的定义 复合命题的符号化(翻译) 小结,2020/9/15,41,一、命题公式(Proposition Formula)的定义,定义1-3.1 单个命题变元和命题常量称为原子公式。,定义1-3.2 命题演算的合式公式(wff：Well-formed formula)，规定为： (1) 原子公式是合式公式。 (2) 若A是合式公式，则(A)也是合式公式。 (3) 若A，B是合式公式，则(AB)，(AB)， (AB

24、)，(AB)也是合式公式。 (4) 当且仅当有限次地应用(1)(3)所得到的包含原 子公式、联结词和括号的符号串是合式公式。,1-3 命题公式与翻译,2020/9/15,42,命题演算的合式公式是由命题变元、命题常量、联结词和圆括号按一定的逻辑关系联结起来的符号串，是以递归的形式来定义的,合式公式也称为命题公式，并简称为公式。,命题公式一般不是命题，仅当公式中的命题变元用确定的命题代入时，才得到一个命题。其真值依赖于代换变元的那些命题的真值。,1-3 命题公式与翻译,2020/9/15,43,1-3 命题公式与翻译,约定：,运算次序优先级：，. 相同的运算符按从左至右次序计算，否则要加上括号。

25、 最外层圆括号可省去。,2020/9/15,44,例1 指出(P(PQ)是否是命题公式，如果是，则具体说明。,解 P是wff 由(1) Q是wff 由(1) PQ是wff 由(3) (P(PQ) 由(3) ,例2 (P Q) , (R S) Q , P，P等均为合式公式，而PQ S , (P W) Q)等不是合式公式。,1-3 命题公式与翻译,2020/9/15,45,二、复合命题的符号化(翻译),有了命题演算的合式公式的概念，我们可以把自然语言中的有些语句(复合命题)，翻译成数理逻辑中的符号形式。基本步骤如下： (1) 分析出各原子命题，将它们符号化； (2) 使用合适的联结词，把简单命题逐

26、个的联结起来，组成复合命题的符号化表示.,1-3 命题公式与翻译,2020/9/15,46,例3 符号化下列命题： (1) 尽管他有病，但他仍坚持工作。 设P：他有病。Q：他坚持工作。 则该命题可以表示为：PQ (2) 说数理逻辑枯燥无味或毫无价值，那是不对的。 设P：数理逻辑枯燥无味。Q：数理逻辑毫无价值。 则该命题可以表示为：(PQ) (3) 张三与李四组成一个学习小组。 设P：张三与李四组成一个学习小组。 则该命题可以表示为：P,1-3 命题公式与翻译,2020/9/15,47,(4) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P：上午下雨。Q：我去看电影。R：我在家读书。

27、S：我在家看报。 则该命题可以表示为： (PQ)(P(RS) (5) 除非你通知我，否则我不开会。 设P：你通知我。Q：我开会。 则该命题可以表示为： PQ (6) 除非你努力，否则你将失败。 设P：你努力。Q：你将失败。 则该命题可以表示为： PQ,1-3 命题公式与翻译,2020/9/15,48,(7) 一个人起初说：“占据空间的、有质量的而且不断变化的叫做物质”；后来他改说：“占据空间的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式进行分析。 设P：它占据空间。Q：它有质量。R：它不断变化。W：它是物质。 则第一句话可表示为： (PQR)W 第一句话可

28、表示为： (PQW)( WR) (8) 只要我还有一口气，我就要战斗。 设P：我有一口气。Q：我要战斗。 则该命题可以表示为： PQ,1-3 命题公式与翻译,2020/9/15,49,(9) 只要功夫深，铁杵磨成针。 设P：功夫深。Q：铁杵磨成针。 则该命题可以表示为： PQ (10) 只有睡觉才能恢复体力。 设P：睡觉。Q：恢复体力。 则该命题可以表示为： QP (11)小王晚上回家，除非下大雨。 设P：小王晚上回家。Q：下大雨。 则该命题可以表示为： QP,1-3 命题公式与翻译,2020/9/15,50,(12)若要人不知，除非己莫为。 设P：人知。Q：己为。 则该命题可以表示为： QP

29、 (13)除非天气好，我才骑自行车上班。 设P：天气好。Q：我骑自行车上班。 则该命题可以表示为： PQ (14)除非你陪我或代我叫辆车子，否则我不出去。 设P：你陪我。Q：你代我叫辆车。R：我出去。 则该命题可以表示为： (PQ)R,1-3 命题公式与翻译,2020/9/15,51,(15)天黑了，我得回家了。 设P：天黑了。Q：我回家。 则该命题可以表示为： PQ (16)张三与李四有且仅有一人是大学生。 设P：张三是大学生。Q：李四是大学生。 则该命题可以表示为： (PQ) (17)张三正在游泳或正在睡觉。 设P：张三正在游泳。Q：张三正在睡觉。 则该命题可以表示为： (PQ),1-3

30、命题公式与翻译,2020/9/15,52,三、小结,作业: P12 (5),(7),本节介了命题公式的概念及复合命题的符号化。 重点是理解命题公式的递归定义，掌握复合命题的符号化方法.,1-3 命题公式与翻译,2020/9/15,53,离散数学(Discrete Mathematics),2020/9/15,54,1-4 真值表与等价公式,真值表(Truth Table) 等价公式(Propositional Equivalences) 小结,2020/9/15,55,一、真值表,定义1-4.1 设P1,P2, ,Pn是出现在公式A中的全部的命题变元，给P1, P2 , Pn 各指定一个真值，

31、称为对A的一个真值指派或赋值(Assigment)或解释。若指定的一组值使A的真值为真(假)，称这组值为A的成真(假)指派.,前面在定义联结词时，曾经使用过真值表，本节给出真值表的定义。,1-4 真值表与等价公式,2020/9/15,56,比如:对公式(PQ)R，赋值011(即令P=0，Q=1，R=1)为(PQ)R的成真赋值；另一组赋值010为(PQ)R的成假赋值；还有000，001，111 考虑：含有n个命题变元的公式共有多少组不同的赋值？,定义1-4.2 在命题公式A中，对于命题变元的每一种可能的真值指派和由它们所确定的命题公式A的真值列成表，称做命题公式A的真值表。,1-4 真值表与等价

32、公式,2020/9/15,57,对公式A构造真值表的具体步骤为： (1)找出公式中所有命题变元P1,P2,Pn。 (2)按从小到大的顺序列出命题变元P1,P2,Pn的全部2n组赋值。 (3)对应各组赋值计算出公式A的真值，并将其列在对应赋值的后面。,1-4 真值表与等价公式,2020/9/15,58,例1 给出(PQ)(PQ)的真值表。,1-4 真值表与等价公式,0,0,0,1,1,1,1,0,1,1,1,0,1,1,1,1,2020/9/15,59,例2 构造公式 (P Q)R的真值表。,1-4 真值表与等价公式,1,1,1,1,0,0,1,1,0,1,0,1,0,0,0,1,2020/9/

33、15,60,练习1 构造公式 (PQ)(QP)的真值表。,1-4 真值表与等价公式,1,1,0,0,1,0,1,0,1,1,0,1,1,1,0,1,1,1,1,1,2020/9/15,61,练习2 构造公式 (P Q) Q 的真值表。,1-4 真值表与等价公式,1,1,0,1,0,0,1,0,0,0,0,0,2020/9/15,62,给定n个 命题变元，按合式公式的形成规则可以形成无数多个命题公式, 但这些无穷尽的命题公式中，有些具有相同的真值表。 考虑：由n个命题变元能生成多少种真值(表)不同的命题公式？,二、等价公式,1-4 真值表与等价公式,2020/9/15,63,定义1-4.3 给定

34、两个命题公式A和B，设P1,P2, Pn为出现于A和B中的所有原子变元，若给P1, P2, ,Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等，记作A B。,“”不是逻辑联结词. 命题公式之间的逻辑相等关系具有： (1) 自反性：A A ； (2) 对称性：若A B，则B A； (3) 传递性：若A B且B C，则A C。,1-4 真值表与等价公式,2020/9/15,64,证明公式等价的方法： 真值表法 等值演算法,1、真值表法,例3 证明: PQ (PQ)(QP),1-4 真值表与等价公式,1,0,0,1,1,0,1,1,1,1,0,1,1,0,0,1,2020/9/1

35、5,65,例4 判断公式 P(QR)、(PQ)R是否等价。,由真值表可知，两个公式为等价式。,1-4 真值表与等价公式,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,2020/9/15,66,2、等值演算法(Equivalent Caculation) （利用P15表1-4.8),重要的等价式(补充)：,11. 条件转化律： PQ PQ 12. 双条件转化律: PQ (PQ)(QP) 13. 逆否律(假言易位)： PQ QP 14. 双条件否定等价式：PQ PQ 15. 归谬律： (PQ)(PQ) P,其中P，Q

36、，R等代表任意命题公式.,1-4 真值表与等价公式,2020/9/15,67,置换/替换规则(Rule of Replacement)：等值演算中使用的一条重要规则。,定义1-4.4(子公式) 如果X是wff A的一部分，且X本身也是wff，则称X是A的子公式(Subformula)。,例如，P(PQ) 为Q (P(PQ)的子公式。,1-4 真值表与等价公式,2020/9/15,68,定理1-4.1(置换定理Axiom of replacement) 设X是wff A的子wff，若XY，则若将A中的X用Y来置换，所得公式B与A等价，即AB。,证：因为对变元的任一指派，X与Y真值相同，所以Y取代

37、X后，公式B与公式A对变元的任一指派真值也相同，所以AB。,满足定理1-4.1条件的置换称为等价置换(或等价代换).,定义1-4.5(等值演算) 根据已知的等价公式，推演出另外一些等价公式的过程称为等值演算.,1-4 真值表与等价公式,2020/9/15,69,例6 证明 (PQ)Q PQ,例5 证明 Q(P(PQ)QP,证 Q(P(PQ)QP (吸收律),证 (PQ)Q (PQ)(QQ) (PQ)T PQ,1-4 真值表与等价公式,2020/9/15,70,例7 证明（PQ）（QP） PQR,证 (PQ)(QP) (PQ)(QR) (PQ)(QR) (PQ)(QR) (PQR)(QQR) P

38、QR,1-4 真值表与等价公式,2020/9/15,71,例8 验证P(QR) (P Q) R,练习：,(1) (P Q) (P R) P (Q R) (2) (P Q) (P Q) (P Q) (P Q),证 (P Q) R (P Q) R P Q R P (Q R) P (Q R) P (Q R),1-4 真值表与等价公式,2020/9/15,72,等值演算在计算机硬件设计中,在开关理论和电子元器件中都占有重要地位.,三、小结,本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式（24个）。 重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。,作业：

39、P17 (1)b,d,e. (4)c,d (7)e,g,h (8). 思考题：(9) 预习：1.5, 1.6,1-4 真值表与等价公式,2020/9/15,73,离散数学(Discrete Mathematics),2020/9/15,74,1-5 重言式与蕴含式,命题公式的分类 重言式(Tautology)的性质 蕴含式( Implication) 小结,2020/9/15,75,一、命题公式的分类,重言式(Tautology)/永真式,矛盾式(Contradiction)/永假式(Absurdity),可满足式(Satisfactory),仅可满足式/偶然式(Contingency),1-

40、5 重言式与蕴含式,2020/9/15,76,定义1-5.1 设A为任一命题公式， (1) 若A在其各种赋值下的取值均为真，则称A是重言式或永真式，记为T或1。 (2) 若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式，记为F或0。 (3) 若A不是矛盾式则称A为可满足式。 (4) 既不是重言式，也不是矛盾式，称为偶然式。,1-5 重言式与蕴含式,2020/9/15,77,判别命题公式的类型的方法: 真值表法 等值演算法：将所给命题公式通过等值演算化为最简单的形式, 然后再进行判别.,(重言式),例1 判别下列命题公式的类型. (1) Q(PQ)P) (2) (PP)(QQ)R (3)

41、(PQ)P,(矛盾式),(可满足式),1-5 重言式与蕴含式,2020/9/15,78,二、重言式的性质,定理1-5.1 任何两个重言式的合取或析取，仍然是一重言式.,证明 设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故AB T，AB T,1-5 重言式与蕴含式,2020/9/15,79,定理1-5.2 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。,证明：由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以任何合式公式置换后，重言式(矛盾式)的真值仍永为T（F）。,1-5 重言式与蕴含式,2020/9/15,80,定理1-5.3 A，B

42、是两个命题公式，A B的充要条件是A B为重言式。,证明 若AB为重言式，则AB永为T， 即A，B的真值表相同，所以AB。 反之，若A B，则A，B真值表相同， 所以AB永为T，从而AB为重言式。,1-5 重言式与蕴含式,2020/9/15,81,三、蕴含式( Implication),定义1-5.2 当且仅当 P Q 是一个重言式时，我们称“P蕴含Q”，并记作 P Q.,设原命题为PQ，则,逆换式：QP 反换式：PQ 逆反式：QP,1-5 重言式与蕴含式,2020/9/15,82,它们之间具有如下关系: PQ QP QP PQ,证明 PQ 的三种方法： 真值表法：即列出PQ的真值表，观察其是

43、否为永真。 直接证法：假定前件P是真，推出后件Q是真。 间接证法：假定后件是假，推出前件是假，即证QP 。,1-5 重言式与蕴含式,2020/9/15,83,例1 证明 Q （PQ） P,证法1：真值表法(略),证法2：若 Q(PQ)为真，,证法3：若P为假，则P为真，再分二种情况： 若Q为真，则Q为假，从而Q(PQ)为假； 若Q为假，则PQ为假，从而Q(PQ)为假， 根据 ，有 Q(PQ)P。,1-5 重言式与蕴含式,则 Q，PQ为真，,所以Q为假，P为假，,所以P为真。,2020/9/15,84,P21表1-5.2给出了14个蕴含式。,1-5 重言式与蕴含式,2020/9/15,85,P2

44、1表1-5.2给出了14个蕴含式。,1-5 重言式与蕴含式,2020/9/15,86,等价式与蕴含式的关系：,定理1-5.4 设P，Q为任意两个命题公式，PQ的充要条件为 PQ 且 QP.,证 若PQ，则PQ为永真式，因为 PQ （PQ）（QP），所以 PQ，QP为永真式，从而 PQ，QP. 反之，若PQ，QP，则PQ，QP为永真式， 所以（PQ）（QP）为永真式，从而 PQ为永真式，即PQ.,1-5 重言式与蕴含式,2020/9/15,87,蕴含的性质：,设A，B，C为任意wff, (1) 若AB，且A为永真式，则B必为永真式. (2) 若AB，BC，则AC. (3) 若AB，AC，则ABC

45、. (4) 若AB且CB，则ACB.,1-5 重言式与蕴含式,2020/9/15,88,四、小结,本节介绍了命题公式的分类，重言式、矛盾式与蕴含式的概念及其性质，等价式与蕴涵式的关系。 重点掌握： (1) 用等值演算法判别命题公式的类型。 (2) 重言式、矛盾式与蕴涵式的性质。 (3) 等价式与蕴涵式的关系。,作业：P23 (1)a,b,c (7) (8)e,f (9).,1-5 重言式与蕴含式,2020/9/15,89,离散数学(Discrete Mathematics),2020/9/15,90,1-6 其它联结词,不可兼析取(排斥或/异或)(Exclusive or) 与非联结词(Nan

46、d) 或非联结词(Nor) 条件否定联结词(Non-conditional) 最小联结词组(The minimal set of connectives) 小结,2020/9/15,91,在第二节(1.2)中我们定义了五种基本的联结词， ，但在命题逻辑中，这些联结词还不能很广泛地直接表达命题之间的联系(例如, “P异或Q”只能间接地表示为(PQ)(PQ)，为此本节再给出逻辑设计中常用的另外四种联结词.,1-6 其它联结词,2020/9/15,92,一、不可兼析取/排斥或/异或(Exclusive-OR， ),1-6 其它联结词,2020/9/15,93,例 派小王或小李中的一人去开会。（排斥或

47、）,定义了联结词“ ”后，命题逻辑中的有些命题就可以符号化为非常简捷的形式.,设P：派小王去开会。Q：派小李去开会。,则上述命题可符号化为： P Q,1-6 其它联结词,2020/9/15,94,“ ” 属于二元(binary)运算符。,1-6 其它联结词,联结词 的性质：设P，Q，R为命题公式，则有 (1) P Q Q P (交换律) (2) (P Q) R P (Q R) (结合律) (3) P(Q R) (PQ) (PR) (分配律) (4) (P Q) (PQ) (PQ) (5) (P Q) (PQ) (6) P P F, F P P, T P P,2020/9/15,95,定理1-6

48、.1 设P，Q， R为命题公式， 如果P Q R，则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 RR RF,1-6 其它联结词,2020/9/15,96,二、与非联结词(NAND，),定义1-6.2 设P,Q为二命题，复合命题“P与Q的否定” 称为P与Q的与非式，记作 PQ，符号“” 称为与非联结词。PQ 为真当且仅当P和Q不同时为真.,1-6 其它联结词,2020/9/15,97,由定义可知，PQ (PQ) “” 属于二元(binary)运算符 联结词“”的性质： (1) PP (

49、PP) P (2) (PQ)(PQ) ( PQ)(PQ) (3)(PP)(QQ) PQ(PQ)PQ,1-6 其它联结词,2020/9/15,98,定义1-6.3 设P,Q为二命题，复合命题“P或Q的否定” 称为P与Q的或非式，记作PQ ，符号“”称为或非联结词. PQ为真当且仅当P与Q同为假.,三、或非联结词(NOR，),1-6 其它联结词,2020/9/15,99,由定义可知，PQ (PQ) “” 属于二元(binary)运算符 联结词“”的性质： (1) PP (PP) P (2) (PQ)(PQ) (PQ) (PQ) (3)(PP)(QQ)PQ(PQ)PQ,1-6 其它联结词,2020/

50、9/15,100,四、条件否定联结词(Non-conditional， ),定义1-6.4 设P，Q为二命题，复合命题“P Q” 称为命题P与Q的条件否定式P Q为真当且仅当P为真且Q为假.,1-6 其它联结词,2020/9/15,101,由定义可知，P Q (P Q) “ ” 属于二元(binary)运算符. 有了联结词 后，命题演算的合式公式的定义1-3.2可加入这四个联结词.,1-6 其它联结词,2020/9/15,102,至此，对于一元和二元逻辑运算，我们一共定义了9个联结词，为了直接表达命题之间的联系，是否还需要定义其它联结词呢? 如果不需要定义其他联结词，那这9个联结词是否都是必须

51、的？ 哪些是必须的？,五、最小联结词组(The minimal set of connectives),1-6 其它联结词,下面以含两个命题变元P、Q的所有互不等价的命题公式为例，来说明这一问题。,2020/9/15,103,由两个命题变元P，Q所构成的互不等价的24个命题公式如下：,1-6 其它联结词,2020/9/15,104,由上表可知，9个联结词足以直接表达命题之间的各种联系，即含n个命题变元的所有 个互不等价的命题公式，均可由这9个联结词直接表达，不需要定义其他联结词。,1-6 其它联结词,在二元运算中，9个联结词并不都是必要的。为此，我们定义最小联结词组。,2n,2020/9/15

52、,105,定义1-6.5 一个联结词集合，如果用其中联结词足以把任何命题公式等价地表示出来，而去掉其中任何一个联结词则不能，我们称这个联结词集合为最小联结词组(The minimal set of connectives),最小联结词组具有： (1) 完备性 (2) 最小性,1-6 其它联结词,2020/9/15,106,对于9个联结词的集合, , ，,(1) PQ (PQ)(QP) (2) PQPQ (3) PQ (PQ) (4) PQ (PQ) (5) (P Q) (PQ) (6) PQ (PQ) (7) PQ (PQ) (8) P Q (PQ),1-6 其它联结词,2020/9/15,1

53、07,任意命题公式都可由仅包含，或， 的命题公式等价代换，即9个联结词的集合中至少有七个冗余联结词。而联结词，和， 不再有冗余联结词，故，或， 为最小联结词组。 实际中为了使用方便, 命题公式常常同时包含， .,1-6 其它联结词,其他最小联结词组： ， ,2020/9/15,108,P (PP)PP PQ (PQ) (PQ)(PQ)(PQ) PQ (PQ) (PP)(QQ) (PP)(QQ),例1 试证是最小联结词组.,证,例2 试证，是最小联结词组,证,1-6 其它联结词,PQ(PQ)(PQ) PQ(P)QPQ,2020/9/15,109,本节主要介绍了四种新的联结词 及最小联结词组.,五

54、、小结,作业: P29 (1), (2), (4),1-6 其它联结词,2020/9/15,110,预习1.7，并思考： (1)何谓命题公式的(主)析(合)取范式? (2)命题公式的(主)析(合)取范式唯一吗? (3)为何要将命题公式化为与之等价的主析(合)取范式? (4)如何将命题公式化为与之等价的主析(合)取范式? (5)两个等价的命题公式其(主)析(合)取范式有何关 系?,1-6 其它联结词,2020/9/15,111,离散数学(Discrete Mathematics),2020/9/15,112,1-7 对偶与范式(Dual & Normal Form),对偶式与对偶原理(Duali

55、stic Formula & Duality Principle) 命题公式的析(合)取范式(The Disjunctive & Conjunctive Normal Forms of a Propositional Formula) 命题公式的主析(合)取范式(The Principal Disjunctive & Conjunctive Normal Form of a Propositional Formula) 小结,2020/9/15,113,一、对偶式与对偶原理,在1.4中我们给出了命题定律(P15表1-4.8)，其中多数等价公式（仅含联结词，）都是成对出现的，每一对公式的不同之处

56、是将与互换，T与F互换，我们把这样的公式称为是对偶的.,定义1-7.1 设命题公式A仅含有联结词、，在A中将、F、T分别换以、T、F，得出公式A*，则A*称为A的对偶公式。,(A*)*=A,1-7 对偶与范式(Dual & Normal Form),2020/9/15,114,例1,1-7 对偶与范式(Dual & Normal Form),(P(QR)*=P(QR) (PQ)1)*=(PQ)0) 由 PQ (PQ) 和 PQ (PQ) 可知 (PQ)*= PQ,2020/9/15,115,关于对偶式我们有如下两个定理:,定理1-7.1 设A，A*是对偶式， P1，P2，Pn是出现于A和A*中

57、的所有原子变元，则 (1) A(P1 , P2 ,Pn )A*(P1 , P2 , Pn) (2) A(P1 , P2 , Pn)A*(P1 , P2 ,Pn),证明 因为 (PQ)PQ，(PQ)PQ 所以A(P1 , P2 ,Pn )A*(P1 , P2 , Pn) 同理A*(P1 , P2 ,Pn )A(P1 , P2 , Pn)。,1-7 对偶与范式(Dual & Normal Form),2020/9/15,116,定理1-7.2(对偶原理) 设A，B为两个仅含有联结词，的命题公式，若AB，则A*B*。,证 设P1 , P2 ,Pn是出现于A和B中的所有原子变元. 因为 A(P1 ,

58、P2 ,Pn)B(P1 , P2 ,Pn) 所以 A(P1 , P2 ,Pn)B(P1 , P2 ,Pn)永真. 故 A(P1 , P2 , Pn)B(P1 , P2 , Pn) 永真. 由定理1-7.1得 A*(P1 , P2 ,Pn)B*(P1 , P2 ,Pn ). 因此 A*B* 。,1-7 对偶与范式(Dual & Normal Form),2020/9/15,117,例2 因为 P(PQ)P 由对偶原理，有 P(PQ) P.,例3 若A1 则 A*(1)* 即 A*0.,例4 设A为 (PQ)(P(PQ)，B为PQ， 且AB，则 A*B*PQ。,1-7 对偶与范式(Dual & N

59、ormal Form),2020/9/15,118,定理1-7.3 设A，B为两个仅含有联结词，的命题公式，若AB，则B*A*。,证 设P1，P2，Pn是出现于A和B中的所有原子变元. 因为 A(P1 , P2 ,Pn)B(P1 , P2 ,Pn) 所以 A(P1 , P2 ,Pn)B(P1 , P2 ,Pn) 永真. 从而 B(P1 , P2 ,Pn)A(P1 , P2 ,Pn) 永真.,1-7 对偶与范式(Dual & Normal Form),2020/9/15,119,即 B*(P1 , P2 , Pn)A*(P1 , P2 , Pn) 永真. 以 Pi代Pi (i=1，2n)，得 B*(P1 , P2 , Pn)A*(P1 , P2 , Pn) 永真. 所以 B