离散数学及其应用第1章-命题逻辑课件

1、第一部分 数理逻辑（Mathematical Logic)形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。2022/7/25 计算机科学与技术学院第一部分 数理逻辑（Mathematical Logic)1931年Godel

2、不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。从广义上讲，数理逻辑包括四论、两演算即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本书课程只研究这两个演算。2022/7/25 计算机科学与技术学院第一部分 数理逻辑（Mathematical Logic)数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional L

3、ogic） 1.1 命题及其表示方法(Proposition and Its Expression)1.2 逻辑联结词(Logical Connectives)1.3 命题公式与翻译(Propositional Formula & Its Translation)1.4 真值表与等价公式(Truth Tables and Prepositional Equivalences)2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic）1.5 重言式与蕴含式(Tautology and Implication )1.6 其它联结词(Other Connect

4、ives)1.7 对偶与范式(Dual & Normal Form)1.8 推理理论(Inference Theory )2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法1.1.1 命题1.1.2 命题的表示方法1.1.3 命题的分类2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法 1.1.1 命题（Proposition) 数理逻辑研究的中心问题是推理（inference),而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的

5、基本单位。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法 基本概念 命题：能够判断真假的陈述句。 命题的真值：命题的判断结果。命题的真值只取两个值:真（用T(true)或1表示）、假（用F(false)或0表示） 。 真命题：判断为正确的命题，即真值为真的命题。 假命题：判断为错误的命题，即真值为假的命题。2022/7/25 计算机科学与技术学院因而又可以称命题是具有唯一真值的陈述句。判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值。 例：判断下列句子是否为命题。 (1). 100是自然数。 T

6、 (2). 太阳从西方升起。 F 第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法(3). 3+3=8 . F(4). How do you do ? 疑问句，不是命题(5). 明年的十月一日是晴天。是命题，其真值到明年十月一日方可知道。(6). x+39 不是命题(7). 我正在说谎。是悖论2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法(8). 1+101=

7、110 二进制中为真，十进制中为假。(9). 如果太阳从西方升起，那么2是奇数。T(10). 国足能杀入2006世界杯当且仅当2+2=4。F(11). 今天天气多好啊！ 感叹句，不是命题(12). 请你关上门！ 祁使句，不是命题， (13). 别的星球上有生物。 是命题，客观上能判断真假。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法说明：（1）只有具有确定真值的陈述句才是命题。 一切没有判断内容的句子，无所谓 是非的句子，如感叹句、祁使句、 疑问 句等都不是命题。（2） 因为命题只有两种真值，所以“命题 逻 辑”又

8、称 “二值逻辑”。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法 (3) “具有确定真值”是指客观上的具有，与我们 是否知道它的真值是两回事。如上例中 的（5）和（13）。1.1.2 命题的表示方法 在本书中，用大写英文字母A,B,P,Q或带下标的字母P1,P2,P3 , ,或数字(1),2, ,等表示命题，称之为命题标识符。 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法例如： P：罗纳尔多是球星。 Q：5是负数。 P3：明天天气晴。 (

9、2)：太阳从西方升起。 皆为符号化的命题，其真值依次为1、0、1或0、0。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法 命题标识符又有命题常量、命题变元和原子变元之分。命题常量：表示确定命题的命题标识符。命题变元：命题标识符如仅是表示任意命题的位置标 志，就称为命题变元。原子变元：当命题变元表示原子命题时，该变元称为 原子变元。命题变元也用A,B,P,Q,P1,P2,P3 , , 表示。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.1 命题及其表示方法1.1

10、.3 命题的分类：简单/原子命题：不能分解为更简单的陈述语句的命题(如上例中的命题)。复合命题：由简单命题通过联结词联结而成的命题。联结词就是复合命题中的运算符。 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法注意：（1）一个符号(如P), 它表示的是命题常量还是命题变元，一般由上下文来确定。（2）命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与“变数x不是数”是一样的道理。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic）1.1 命题及其表示方法小结：

11、本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、命题变元和原子变元的概念。 重点理解和掌握命题、命题变元、简单（原子）命题、复合命题四个概念。 作业：P2 1,22022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2 逻辑联结词(Logical Connectives) 1.2.1 否定联结词(Negation) 1.2.2 合取联结词(Conjunction)1.2.3 析取联结词(Disjunction)1.2.4 条件联结词(蕴涵联结词Conditional)1.2.5 双条件联结(等值联结词Biconditi

12、onal) 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives) 在命题逻辑中,主要研究的是复合命题,而复合命题是由原子命题与逻辑联结词组合而成,联结词组是复合命题的重要组成部分.2022/7/25 计算机科学与技术学院1.2.1 否定联结词 定义1.2.1 设P为一命题， P的否定是一个新的复合命题, 称为P的否定式，记作 “P”读作“非P”. 符号“ ” 称为否定联结词。 P为真当且仅当P为假.说明： “”属于一元(unary)运算符.第一章 命题逻辑（Propositional Lo

13、gic） 1.2逻辑联结词(Logical Connectives)2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)“”的定义也可用下表来说明. 联结词“”的定义真值表 P P01102022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)例1. P: 天津是一个城市. Q: 3是偶数.于是: P: 天津不是一个城市. Q: 3不是偶数.例2. P:苏州处处清洁. Q:这些都是男同学.

14、 P:苏州不处处清洁 (注意,不是处处不清洁). Q:这些不都是男同学.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)1.2.2 合取联结词(Conjunction )定义1.2.2 设P,Q为二命题，复合命题“P并且Q”（或“P与Q”）称为P与Q的合取式，记作PQ，符号“” 称为合取联结词. PQ为真当且仅当P和Q同时为真. 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)

15、 联结词“”的定义真值表PQ P Q 0000101001112022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)说明：“” 属于二元(binary)运算符.合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”、“一面一面”、 “和”、 “与”等都可以 符号化为 。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical

16、Connectives)例3. 将下列命题符号化. (1) 李平既聪明又用功. (2) 李平虽然聪明, 但不用功. (3) 李平不但聪明,而且用功. (4) 李平不是不聪明,而是不用功.解: 设 P:李平聪明. Q:李平用功.则 (1) PQ (2) PQ (3) PQ (4) (P)Q 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)注意：不要见到“与”或“和”就使用联结词 ！例如: (1)李敏和李华是姐妹。 (2)李敏和张华是朋友。 2022/7/25 计算机科学与技术学院第一章

17、命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives) 例4. 试生成下列命题的合取. (1) P: 我们在6-503. Q: 今天是星期二. (2) S：李平在吃饭. R：张明在吃饭. 解: (1) PQ :我们在6-503且今天是星期二. (2) SR:李平与张明在吃饭. 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives) 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2

18、逻辑联结词(Logical Connectives)1.2.3 析取联结词(Disjunction)定义1.2.3 设P,Q为二命题，复合命题“P或Q” 称为P与Q的析取式，记作PQ ，符号称为析取联结词. PQ为真当且仅当 P与Q中至少有一个为真. 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives) 联结词“”的定义真值表PQ PQ 0000111011112022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logica

19、l Connectives)说明：“” 属于二元(binary)运算符.析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。 由析取联结词的定义可以看出， “”与汉语中的联结词“或”意义相近，但又不完全相同。在现代汉语中，联结词的“或”实际上有“可兼或”和“排斥或”之分。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)考察下面命题：（1）小王爱打球或爱跑步。（可兼或） 设P：小王爱打球。 Q：小王爱跑步。 则上述命题可符号化为：P Q（2）林芳学过英语或法语。 （可兼

20、或）设P：林芳学过英语。 Q：林芳学过法语。 则上述命题可符号化为： P Q2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)（3）派小王或小李中的一人去开会。（排斥或） 设P：派小王去开会。Q：派小李去开会。 则上述命题可符号化为：(PQ) (PQ)（4）人固有一死，或重于泰山或轻于鸿毛. (排斥或） （5）ab=0, 即a=0 或 b=0. （可兼或） 由此可见, “P Q”表示的是“可兼或”.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Lo

21、gic） 1.2逻辑联结词(Logical Connectives)注意：当P和Q客观上不能同时发生时，“P或Q”可以符号化为“P Q”。例如：小王现在在宿舍或在图书馆。设 P：小王现在在宿舍。Q：小王现在在图书馆。则上述命题可符号化为：PQ。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)1.2.4. 条件联结词(蕴涵联结词Co

22、nditional)定义1.2.4 设P,Q为二命题，复合命题“如果P则Q(若P则Q)” 称为P与Q的条件命题,记作P Q. PQ为假当且仅当P为真且Q为假.称符号“”为条件联结词。并称P为前件，Q为后件. 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives) 联结词“”的定义真值表PQP Q0010111001112022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives) 注：（1）PQ表

23、示的基本逻辑关系是,Q是P的必要条件或P是Q的充分条件. 因此复合命题“只要P就Q”、“因为P，所以Q”、“P仅当Q”、“只有Q才P”等都可以符号化为 PQ 的形式。（2） “” 属于二元(binary)运算.2022/7/25 计算机科学与技术学院第一章 命题逻辑（ProPositional Logic） 1.2逻辑联结词(Logical Connectives)例5. 将下列命题符号化。 （1）天不下雨，则草木枯黄。 P：天下雨。 Q：草木枯黄。则原命题可表示为： PQ。 （2）如果小明学日语，小华学英语，则小芳学德语。 P：小明学日语. Q：小华学英语. R：小芳学德语.则原命题可表示为

24、：(PQ)R2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives) （3）只要不下雨，我就骑自行车上班。 P：天下雨。Q：我骑自行车上班。 则原命题可表示为： PQ。 （4）只有不下雨，我才骑自行车上班。 P：天下雨。Q：我骑自行车上班。 则原命题可表示为： Q P 。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives) （5）如果 2+2=4, 则太阳从东方升起。 (PQ, T) P

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

26、onal Logic） 1.2逻辑联结词(Logical Connectives)1.2.5 双条件联结(等值联结词Biconditional) 定义1.2.5 设P,Q为二命题，复合命题“P当且仅当Q” 称为P与Q的双条件命题，记作P iff Q或 PQ，符号称为双条件（等值）联结词。 PQ为真当且仅当P，Q真值相同。 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives) 联结词“”的定义真值表PQP Q0010101001112022/7/25 计算机科学与技术学院第一章 命题逻辑（P

27、ropositional Logic） 1.2逻辑联结词(Logical Connectives)注：（1）P仅当Q 可译为PQ P当Q 可译为QP P当且仅当Q 译为PQ （2）“”属于二元(binary)运算符。 (3) 双条件命题PQ所表达的逻辑关系是, P与Q互为充分必要条件,相当于(PQ)(QP). 只要P与Q的真值同为1或同为0, PQ的真值就为1, 否则PQ的真值为0. 双条件联结词连接的两个命题之间可以没有因果关系。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)例6.

28、分析下列命题的真值. (1) 2+2=4 当且仅当3是奇数 . (PQ) P： 2+2=4. Q：3是奇数 . (2) 2+2=4 当且仅当3不是奇数 . (PQ)(3) 2+24 当且仅当3是奇数 . (PQ)(4) 2+24 当且仅当3不是奇数 . (PQ)2022/7/25 计算机科学与技术学院第一章 命题逻辑（ProPositional Logic） 1.2逻辑联结词(Logical Connectives)约 定:1. 运算次序优先级：，. 2. 相同的运算符按从左至右次序计算，否则要加上括号。 3.最外层圆括号可省去。 小结: 本节介绍了五种联结词(，),重点是理解和掌握五种联结词

29、的内涵及它们与自然语言中相应联结词的不同之处.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.2逻辑联结词(Logical Connectives)作业: 1. P5 2 2. 预习 1.3, 1.4思考题: 1. 何谓合式公式? 2. 复合命题符号化的基本步骤是什么? 3.何谓真值表? 4. 两个命题公式等价的涵义是什么? 5.两个等价的命题公式其真值表有何关系?2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.3命题公式与翻译1.3 命题公式与翻译1.3.1 命题公式1.3.2 复

30、合命题的符号化(翻译)2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.3命题公式与翻译(Propositional Formula & Its Translation)1.3.1 命题合式公式(Well-formed formula)(wff)定义1.3.1:单个命题变元和命题常量称为原子公式。命题合式公式是由命题变元、命题常量、联结词和圆括号按一定的逻辑关系联结起来的符号串。我们以如下递归的形式来定义合式公式：2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.3命题公式与翻译定义1.

31、3.2：(1)原子公式是合式公式(wff)。 （2）若A是合式公式，则(A)也是合式公式。 （3）若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。 （4）当且仅当有限次地应用(1)(3)所得到的包含原子公式、联结词和括号的符号串是合式公式。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.3命题公式与翻译注: (1)合式公式也称为命题公式，并简称为公式。 (2)命题公式一般不是命题,仅当公式中的命题变元用确定的命题代入时,才得到一个命题.其真值依赖于代换变元的那些命题的真值.2022/7/25 计算机科学与技术学院

32、第一章 命题逻辑（ProPositional Logic）1.3命题公式与翻译例1：指出(P(PQ)是否是命题公式(wff)，如果是，则具体说明。解： P是wff 由(1) Q是wff 由(1) PQ是wff 由(2) (P(PQ) 由(2) 2022/7/25 计算机科学与技术学院第一章 命题逻辑（ProPositional Logic）1.3命题公式与翻译例2: (P Q) , (R S) Q , P，(P)等均为合式公式，而PQ S , (P W) Q)等不是合式公式。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.3命题公式与翻译

33、1.3.2 复合命题的符号化(翻译)有了命题演算的合式公式的概念,我们可以把自然语言中的有些语句(复合命题),翻译成数理逻辑中的符号形式.基本步骤如下:(1) 分析出各简单命题,将它们符号化;(2) 使用合适的联结词,把简单命题逐个的联结起来,组成复合命题的符号化表示.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.3命题公式与翻译例3：1) 我今天进城，除非下雨。2) 仅当你走我将留下。3) 假如上午不下雨，我去看电影，否则就在家里 读书或看报。4)除非你努力，否则你将失败。5)一个人起初说：“占据空间的、有质量的而且不断变化的叫做物质

34、”；后来他改说，“占据空间的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式进行分析。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.3命题公式与翻译例4：P6 例1.3.3 ，例1.3.4(5) ，例1.3.5小结：本节介了命题公式的概念及复合命题的符号化.重点是理解命题公式的递归定义,掌握复合命题的符号化方法.作业: P7: 22022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式1.4.1 真值表(Truth Table)1.4.2

35、 等价公式(ProPositional Equivalences)1.4.1 真值表 前面在定义联结词时,曾经使用过真值表,下面给出真值表的定义.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式定义1.4.1 (对公式的赋值或解释)设P1 , P2 ,Pn是出现在公式A中的全部的命题变元, 给P1 , P2 ,Pn各指定一个真值，称为对A的一个赋值或解释。若指定的一组值使A的真值为真(假), 称这组值为A的成真(假)赋值.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic）

36、1.4真值表与等价公式例如:对公式(PQ)R，赋值011(即令P=0，Q=1， R=1) 为(PQ)R的成真赋值; 另一组赋值010为(PQ)R的成假赋值；还有000，001，1112022/7/25 计算机科学与技术学院第一章 命题逻辑（ProPositional Logic） 1.4真值表与等价公式考虑：含有n个命题变元的公式共有多少组不同的赋值？定义1.4.2(真值表)在命题公式A中, 对于命题变元的每一组赋值和由它们所确定的命题公式A的真值列成表，称做命题公式A 的真值表。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与

37、等价公式对公式A构造真值表的具体步骤为：（1）找出公式中所有命题变元P1 , P2 ,Pn , 列出全部的2n组赋值。（2）按从小到大的顺序列出对命题变元P1 , P2 ,Pn ,的全部2n组赋值。（3）对应各组赋值计算出公式A的真值，并将其列在对应赋值的后面。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式例1. 给出(PQ)(PQ)的真值表：PQPQ(PQ)PQ(PQ)(PQ)000110112022/7/25 计算机科学与技术学院第一章 命题逻辑（ProPositional Logic） 1.4真值表与等价公式例1

38、.给出(PQ)(PQ)的真值表：PQPQ(PQ)PQ(PQ)(PQ)0001110101111001111110012022/7/25 计算机科学与技术学院第一章 命题逻辑（ProPositional Logic） 1.4真值表与等价公式例2：构造公式 (P Q) R的 真值表。PQRPQ(P Q) R0000010100111001011101112022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式例2：构造公式 (P Q) R的 真值表。PQRPQ(P Q) R000100011101010011111000010100

39、11010111112022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式练习1：构造公式 (PQ)(Q P)真值表。PQPQPQQP(PQ)(QP)000110112022/7/25 计算机科学与技术学院第一章 命题逻辑（ProPositional Logic） 1.4真值表与等价公式练习1：构造公式 (PQ)(Q P)真值表。PQPQPQQP(PQ)(QP)00111110110111100100111001112022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表

40、与等价公式PQ (PQ)(PQ) (PQ)Q00011011练习2：构造公式 (PQ)Q真值表。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式PQ (P Q)(PQ) (PQ)Q00100011001001011100练习2：构造公式 (PQ)Q真值表。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式1.4.2 等价公式给定n个 命题变元, 按合式公式的形成规则可以形成无数多个命题公式, 但这些无穷尽的命题公式中，有些具有相同的真值表。考虑：由n

41、个命题变元能生成? 种真值(表)不同的命题公式？2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式定义1.4.3: 给定两个命题公式A和B，设P1 ,P2 ,Pn为出现于A和B中的所有原子变元,若给P1 , P2 ,Pn任一组真值指派, A和B的真值都相同,则称A和B是等价的或逻辑相等.记作A B。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式注: (1) “ ”不是逻辑联结词.(2)命题公式之间的逻辑相等关系具有： 自反性：A A ； 对称性：若

42、A B，则B A； 传递性：若A B且B C，则A C。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式证明公式等价的方法：1. 真值表法 2. 等值演算法1. 真值表法 例1.(PQ) (PQ) 见真值表例题1.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式例2. 证明: PQ (PQ)(QP)PQPQQPPQ(PQ)(QP)000110112022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic）

43、1.4真值表与等价公式例2. 证明: PQ (PQ)(QP)PQPQQPPQ(PQ)(QP)0011110100101001001111112022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式例3：判断公式 P(QR)、(PQ)R是否等价。PQRPQQRP(QR)(PQ)R00001001010100001101100011010111010111112022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式PQRPQQRP(QR)(PQ)R000011100

44、10111010001101101111000111101011111010001111111例3：判断公式 P(QR)、(PQ)R是否等价。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式 由真值表可知，两个公式为等价式。2. 等值演算法(Equivalent Calculation) 等值演算中使用的一条重要规则：置换规则定义1.4.4(子公式)：如果X是wff A的一部分,且X本身也是wff，则称X是A的子公式。例如, P(PQ)为Q (P(PQ)的子公式。2022/7/25 计算机科学与技术学院第一章 命题逻辑

45、（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。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4真值表与等价公式注: 满足定理1.4.1的条件的置换称为等价置 换(或等价代换).定义1.4.5(等值演算)：根据已知的等价公式,推演出另外一些等价公式的过程称

46、为等值演算.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式常用的等价式： 1.双重否定律： P P 2.结合律：(PQ)RP(QR) (PQ)RP(QR) (PQ)RP(QR) 3.交换律: PQQP PQ QP PQ QP 4. 分配律: P(QR )(PQ)(PR) P(QR)(PQ)(PR)2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式常用的等价式： 5.幂等律: PP P PP P 6.吸收律: P(PQ) P P(PQ) P 7.

47、德.摩根律: (PQ)PQ (PQ)PQ 8.同一律: PFP PTP 9.零律: PTT PFF2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式常用的等价式： 10.否定律： PPT PPF 11. 蕴涵等值式: PQ PQ 12. 等价等值式: PQ(PQ)(QP) 13. 假言易位: PQQ P 14. 等价否定等值式: PQPQ 15. 归谬论: (PQ )( PQ)P 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式其中P, Q, R

48、等代表任意命题公式. 这样上面的每一个公式都是一个模式, 它可以代表无数多个同类型的命题公式. 例如, PPT 中, 用(PQ)置换P,则得 (PQ)(PQ)T ,用P置换P,则得 (P)(P)T 。2022/7/25 计算机科学与技术学院第一章 命题逻辑（ProPositional Logic） 1.4真值表与等价公式例1： 证明 Q(P(PQ)QP证: Q(P(PQ) QP P(吸收律)例2： 证明 PQQPQ证：(PQ)Q(PQ)(QQ)(PQ)T PQ2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式例3：证明(

49、PQ)(QR) PQR证：(PQ)(QR) (PQ)(QR) (PQ)(QR) (PQ)(QR) (PQR)(QQR) PQR 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式例4：验证P(QR) (PQ)R证: 右(PQ)R PQR P(QR) P(QR) P(QR)练：1.(PQ)(PR)P(QR) 2.(PQ)(PQ)(PQ)(PQ) 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式等值演算在计算机硬件设计中,在开关理论和电子元器件中都占

50、有重要地位.小结: 本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式（26个）。重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.4 真值表与等价公式作业：Pg.13: 1 (2),(4)； 2 (2),(4)； 4 ；6（3）预习: 1.5, 1.6思考题： Pg.13: 52022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)

51、1.5.1 命题公式的分类1.5.2 重言式(Tautology)与矛盾式 (contradictory)的性质1.5.3 蕴含式( ImPlication)2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)1.5.1 命题公式的分类 复合命题2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)定义1.5.1 设A为任一命题公式，(1)若A在其各种赋值

52、下的取值均为真，则称 A是重言式或永真式, 记为T或1。(2)若A在其各种赋值下的取值均为假，则称 A是矛盾式或永假式, 记为F或0。(3)若A不是矛盾式则称A为可满足式(satisfiable)。注: 由定义可知,重言式一定是可满足式,反之不真.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication) 判别命题公式的类型有两种方法: 真值表法和等值演算法. 等值演算法是将所给命题公式通过等值演算化为最简单的形式, 然后再进行判别.例1.判别下列命题公式的类型.(1). Q(P

53、Q)P) (重言式)(2). (PP)(QQ)R (矛盾式)(3). (PQ)P. (可满足式)2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)1.5.2 重言式(Tautology)与矛盾式(contradictory)的性质定理1.5.1:任何两个重言式的合取或析取,仍然是一重言式.（由幂等律立得）证明:设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为T,故AB T，ABT。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propos

54、itional Logic） 1.5重言式与蕴含式(Tautology and Implication)定理1.5.2:一个重言式(矛盾式),对同一分量都用任何合式公式置换,其结果仍为一重言式(矛盾式).证明：由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以任何合式公式置换后，重言式(矛盾式)的真值仍永为T（F）。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)定理1.5.3：A,B是两个命题公式，A B的充要条件是A B为重言式。 证明: 若AB为重言式，

55、则AB永为T，即A，B的真值表相同，所以AB。 反之，若A B，则A，B真值表相同， 所以 AB永为T，所以AB为重言式。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)它们之间具有如下关系: PQ Q P QP P Q原命题逆换式反换式逆反式PQQPP QQ P1.5.3 蕴含式（ ImPlication）定义1.5.2：当且仅当P Q是一个重言式时，我们称“P蕴含Q”，并记作P Q.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional

56、 Logic） 1.5重言式与蕴含式(Tautology and Implication)因此, 要证明PQ有三种方法:1)真值表法: 即列出PQ的真值表,观察其是 否永为真。2)等值演算法：通过证明PQ 1来证PQ3)分析法： 直接分析法: 假定前件P是真，推出后件Q是真。 间接分析法: 假定后件是假，推出前件是假,即证 QP 。2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)例: 证明Q(PQ)P1) 法1：真值表（略）2) 法2： Q(PQ) P (Q(PQ)(P

57、 ) Q(PQ)(P ) (PQ)(PQ) 1 即Q(PQ)P2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)3) 直接分析法：若 Q(PQ)为真，则 Q，PQ为真，所以Q为假，P为假，所以P为真。 间接分析法：若P为假，则P为真，再分二种情况： 若Q为真，则Q为假,从而Q(PQ) 为假. 若Q为假，则PQ为假，则Q(PQ)为假. 根据 ，所以 Q(PQ)P2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与

58、蕴含式(Tautology and Implication)下面常用的14个蕴含式, 都可以用上述方法加以推证. 1. PQP 2. PQQ 3. PPQ 4. PPQ 5. QPQ 6. (PQ )P 7. (PQ )Q 8. P (PQ )Q 9. Q (PQ )P 10. P(PQ )Q11. (PQ )(QR)PR12. (PQ )(PR)(QR)R13. (PQ)(RS) (PR)(QS )14. (PQ)(QR) (PR)2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implic

59、ation)等价式与蕴含式的关系:定理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.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)蕴含的性质:设A，B，C为任意wff,1) 若AB，且A为永真式，则B必为永真式.2) 若AB，BC，则AC.

60、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.2022/7/25 计算机科学与技术学院第一章 命题逻辑（Propositional Logic） 1.5重言式与蕴含式(Tautology and Implication)3) （AB）（AC） （AB）（AC） A（BC） ABC4) (AB)(CB) (AB)(CB) (AC)B (AC)B ACB 2022/7/25 计算机科学与技术学院第一章 命题逻辑（Proposi