左孝凌离散数学课件

《左孝凌离散数学课件》由会员分享，可在线阅读，更多相关《左孝凌离散数学课件（148页珍藏版）》请在装配图网上搜索。

1、v逻辑：是研究推理的科学。公元前四世纪逻辑：是研究推理的科学。公元前四世纪由希腊的哲由希腊的哲学家亚里斯多德首创。作为一门独立科学，十七世纪，学家亚里斯多德首创。作为一门独立科学，十七世纪，德国的莱布尼兹德国的莱布尼兹(Leibniz)给逻辑学引进了符号给逻辑学引进了符号,又称又称为数理逻辑为数理逻辑(或符号逻辑或符号逻辑)。逻辑逻辑可分为：可分为：1.形式逻辑（通过数学方法）形式逻辑（通过数学方法）数理逻辑数理逻辑 2.辩证逻辑辩证逻辑 指引进一套符号体系的方法。指引进一套符号体系的方法。辩证逻辑辩证逻辑是研究反映客观世界辩证发展过程的人类思是研究反映客观世界辩证发展过程的人类思维的形态的。

2、维的形态的。v形式逻辑形式逻辑是研究思维的形式结构和规律的科学，它撇是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。念、判断和推理及其正确联系的规律。v数理逻辑数理逻辑是用数学方法研究推理的形式结构和推理的是用数学方法研究推理的形式结构和推理的规律的数学学科。它的创始人规律的数学学科。它的创始人Leibniz，为了实现把，为了实现把推理变为演算的想法，把数学引入了形式逻辑。其后，推理变为演算的想法，把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学又经多人

3、努力，逐渐使得数理逻辑成为一门专门的学科。科。v上个世纪上个世纪30年代以后，数理逻辑进入一个崭新的发展年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。切关联。2023-3-8 1.1.1 命题（命题（Proposition)1.1.2 命题的表示方法命题的表示方法 1.1.3 命题的分类命题的分类2023-3-81.1.1 命题命题 数理逻辑研究的中心问题是推理（数理逻辑研究的中心问题是推理（inference),而而推理的前提和结论都是表达判断的陈述句，因而表达推理的前提和结论都是表达判断的陈述句，因而

4、表达判断的陈述句构成了推理的基本单位判断的陈述句构成了推理的基本单位。基本概念基本概念 命题：能够判断真假的陈述句。命题：能够判断真假的陈述句。命题的真值：命题的判断结果。命题的真值只取两个命题的真值：命题的判断结果。命题的真值只取两个 值值:真（真（用用T(true)或或1表示表示）、假（）、假（用用F(false)或或0表示表示）。真命题：判断为正确的命题，即真值为真的命题。真命题：判断为正确的命题，即真值为真的命题。假命题：判断为错误的命题，即真值为假的命题。假命题：判断为错误的命题，即真值为假的命题。因而又可以称因而又可以称命题是具有唯一真值的陈述句。命题是具有唯一真值的陈述句。判断命

5、题的两个步骤判断命题的两个步骤：1 1、是否为陈述句；、是否为陈述句；2 2、是否有确定的、唯一的真值。、是否有确定的、唯一的真值。例例：判断下列句子是否为命题。：判断下列句子是否为命题。(1).100是自然数。是自然数。T (2).太阳从西方升起。太阳从西方升起。F (3).3+3=8.F(4).How do you do?疑问句，疑问句，不是命题不是命题(5).明年的十月一日是晴天。明年的十月一日是晴天。是命题，其真值到是命题，其真值到明年明年 十月一日方可知道。十月一日方可知道。(6).x+39 不是命题不是命题(7).我正在说谎。我正在说谎。是悖论是悖论(8).1+101=110 二进

6、制中为真，十进制中为假。二进制中为真，十进制中为假。(9).如果太阳从西方升起，那么如果太阳从西方升起，那么2是奇数是奇数。T(10).国足能杀入国足能杀入2006世界杯当且仅当世界杯当且仅当2+2=4。F(11).今天天气多好啊！今天天气多好啊！感叹句，感叹句，不是命题不是命题(12).请你关上门！请你关上门！祁使句，不祁使句，不是命题，是命题，(13).别的星球上有生物。别的星球上有生物。是命题，客观上能判断真是命题，客观上能判断真 假。假。说明：说明：（1）只有）只有具有确定真值具有确定真值的的陈述句陈述句才是命题。一才是命题。一 切没有判断内容的句子，无所谓是非的句子，切没有判断内容的

7、句子，无所谓是非的句子，如如感叹句、祁使句、疑问句等都不是命题。感叹句、祁使句、疑问句等都不是命题。（2）因为因为命题只有两种真值，所以命题只有两种真值，所以“命题逻辑命题逻辑”又称又称 “二值逻辑二值逻辑”。(3)“具有确定真值具有确定真值”是指客观上的具有，与我们是否是指客观上的具有，与我们是否知道它的真值是两回事。如上例中的（知道它的真值是两回事。如上例中的（5）和（）和（13）。）。1.1.2 命题的表示方法命题的表示方法 在本书中，用大写英文字母在本书中，用大写英文字母A,B,P,Q或带下标的字或带下标的字母母P1,P2,P3,或数字或数字(1),2,等表示命题，称之为等表示命题，称

8、之为命题标识符。命题标识符。例如：例如：P：罗纳尔多是球星。：罗纳尔多是球星。Q：5是负数。是负数。P3：明天天气晴。明天天气晴。(2)：太阳从西方升起。：太阳从西方升起。皆为符号化的命题，其真值依次为皆为符号化的命题，其真值依次为1、0、1或或0、0。命题标识符又有命题常量、命题变元和原子变元命题标识符又有命题常量、命题变元和原子变元之分。之分。命题常量命题常量：表示确定命题的命题标识符。：表示确定命题的命题标识符。命题变元命题变元：命题标识符如仅是表示任意命题的位置标：命题标识符如仅是表示任意命题的位置标 志，就称为命题变元。志，就称为命题变元。原子变元原子变元：当命题变元表示原子命题时，

9、该变元称为：当命题变元表示原子命题时，该变元称为 原子变元。原子变元。命题变元也用命题变元也用A,B,P,Q,P1,P2,P3,表示。表示。1.1.3 命题的分类：命题的分类：简单简单/原子命题：原子命题：不能分解为更简单的陈述语句的命题不能分解为更简单的陈述语句的命题(如如上例中的命题上例中的命题)。复合命题：复合命题：由简单命题通过由简单命题通过联结词联结词联结而成的命题。联结而成的命题。联结词就是复合命题中的运算符。联结词就是复合命题中的运算符。注意注意：（1）一个符号）一个符号(如如P),它表示的是命题常量还是命题变它表示的是命题常量还是命题变元，一般由上下文来确定。元，一般由上下文来

10、确定。（2）命题变元可以表示任意命题，它不能确定真值，）命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与故命题变元不是命题。这与“变数变数x不是数不是数”是一样是一样的道理。的道理。小结：小结：本节主要介绍了命题、命题的真值、原子命题、本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、命题变元和原子复合命题、命题标识符、命题常量、命题变元和原子变元的概念。变元的概念。重点理解和掌握命题、命题变元两个概重点理解和掌握命题、命题变元两个概念。念。作业：作业：P8 （1）13 1.2逻逻辑联结词辑联结词(Logical Connectives)1.2.1 否

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

12、“P”读作读作“非非P”.符符号号“”称为否定联结词。称为否定联结词。P为真当且仅当为真当且仅当P为为假假.说明说明：“”属于一元属于一元(unary)运算符运算符15“”的定义也可用下表来说明的定义也可用下表来说明.联结词联结词“”的定义真值表的定义真值表 P P011016例例1.P:天津是一个城市天津是一个城市.Q:3是偶数是偶数.于是于是:P:天津不是一个城市天津不是一个城市.Q:3不是偶数不是偶数.例例2.P:苏州处处清洁苏州处处清洁.Q:这些都是男同学这些都是男同学.P:苏州不处处清洁苏州不处处清洁 (注意注意,不是处处不清洁不是处处不清洁).Q:这些不都是男同学这些不都是男同学.

13、171.2.2 合取合取联结联结词词(Conjunction)定义定义1.2.2 设设P,Q为二命题，复合命题为二命题，复合命题“P并且并且Q”（或（或“P与与Q”）称为）称为P与与Q的合取式，记作的合取式，记作P Q，符号，符号“”称为合取联结词称为合取联结词.P P Q Q 为真当且仅当为真当且仅当P P和和Q Q同同时为真时为真.联结词联结词“”的定义真值表的定义真值表P PQ Q P P Q Q 0 00 00 00 01 10 01 10 00 01 11 11 118说明：说明：“”属于二元属于二元(binary)运算符运算符.合取运算特点合取运算特点：只有参与运算的二命题全为真时

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

15、 (1)PQ (2)P Q (3)PQ (4)(P)Q 注意注意：不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词！例如例如:(1)见课本见课本P11 例题例题6 (2)李敏和李华是姐妹。李敏和李华是姐妹。（3）李敏和张华是朋友。）李敏和张华是朋友。20 例例4.试生成下列命题的合取试生成下列命题的合取.(1)P:我们在我们在XNA303.Q:今天是星期二今天是星期二.(2)S：李平在吃饭李平在吃饭.R：张明在吃饭张明在吃饭.解解:(1)PQ:我们在我们在XNA303且今天是星期二且今天是星期二.(2)SR:R:李平与张明在吃饭李平与张明在吃饭.同之处的不和与语言中与日常.):(,

16、)2(1).(.(,)1(李华和李敏是姐妹如去翻译不能一概用和与不同意义上使用联结词自然语言中有时在各种如上例的命题原子命题生成一个新的甚至互为否定的独立无关的逻辑学中允许两个相互211.2.3 析取联结析取联结词词(Disjunction)定义定义1.2.3 设设P,Q为二命题，复合命题为二命题，复合命题“P或或Q”称为称为P与与Q的的析取式，记作析取式，记作PQ，符号，符号称为析取联结词称为析取联结词.PQ为真为真当且仅当当且仅当 P与与Q中至少有一个为真中至少有一个为真.联结词联结词“”的定义真值表的定义真值表P PQ Q P P Q Q 0 00 00 00 01 11 11 10 0

17、1 11 11 11 122说明：说明：“”属于二元属于二元(binary)运算符运算符.析取运算特点析取运算特点：只有参与运算的二命题全为假时，：只有参与运算的二命题全为假时，运算结果才为假，否则为真。运算结果才为假，否则为真。由析取联结词的定义可以看出，由析取联结词的定义可以看出，“”与汉与汉语中的联结词语中的联结词“或或”意义相近，但又不完全相同。意义相近，但又不完全相同。在现代汉语中，联结词的在现代汉语中，联结词的“或或”实际上有实际上有“”和和“”之分。考察下面命题：之分。考察下面命题：（1）小王爱打球或爱跑步。）小王爱打球或爱跑步。（设设P：小王爱打球。：小王爱打球。Q：小王爱跑步

18、。：小王爱跑步。则上述命题可符号化为：则上述命题可符号化为：P Q23（2）林芳学过英语或法语。）林芳学过英语或法语。（设设P：林芳学过英语林芳学过英语。Q：林芳学过法语林芳学过法语。则上述命题可符号化为：则上述命题可符号化为：P Q（3）派小王或小李中的一人去开会。）派小王或小李中的一人去开会。（）设设P：派小王去开会。派小王去开会。Q：派小李去开会。派小李去开会。则上述命题可符号化为：则上述命题可符号化为：(P Q)(PQ)（4）人固有一死，或重于泰山或轻于鸿毛）人固有一死，或重于泰山或轻于鸿毛.(）（5）ab=0,即即a=0 或或 b=0.（由此可见由此可见,“P Q”表示的是表示的是“

19、注意：注意：当当P和和Q客观上不能同时发生时，客观上不能同时发生时，“P或或Q”可可以符号化为以符号化为“P Q”。例如：小王现在在宿舍或在图书馆。例如：小王现在在宿舍或在图书馆。设设 P：小王现在在宿舍。：小王现在在宿舍。Q：小王现在在图书馆。：小王现在在图书馆。则上述命题可符号化为：则上述命题可符号化为：P Q。同之处的不或语言中与日常)36:(,)2(.)1(例如去翻译不能一概用或不同意义上使用联结词自然语言中有时在各种题联结两个毫无关系的命逻辑学中允许P251.2.4.条件联结词条件联结词(蕴涵联结词蕴涵联结词Conditional)定义定义1.2.4 设设P,Q为二命题，复合命题为二

20、命题，复合命题“如果如果P则则Q(若若P则则Q)”称为称为P与与Q的条件命题的条件命题,记作记作P Q.P Q为假当且为假当且仅当仅当P为真且为真且Q为假为假.称符号称符号“”为条件联结词。并称为条件联结词。并称P为前件，为前件，Q为后件为后件.联结词联结词“”的定义真值表的定义真值表P PQ QP P Q Q0 00 01 10 01 11 11 10 00 01 11 11 126 注：注：（1）P Q表示的基本逻辑关系是表示的基本逻辑关系是,Q是是P的必要的必要条件或条件或P是是Q的充分条件的充分条件.因此复合命题因此复合命题“只要只要P P就就Q Q”、“因为因为P P，所以，所以Q

21、Q”、“P P仅当仅当Q Q”、“只有只有Q才才P”等都可以符号化为等都可以符号化为P Q 的形式。的形式。（2）”“属于二元属于二元(binary)运算符。运算符。例例5.5.将下列命题符号化。将下列命题符号化。（1 1）天不下雨，则草木枯黄。）天不下雨，则草木枯黄。P P：天下雨。：天下雨。Q Q：草木枯黄。：草木枯黄。则原命题可表示为：则原命题可表示为：PQPQ。27（2）如果小明学日语，小华学英语，则小芳学德语。）如果小明学日语，小华学英语，则小芳学德语。P P：小明学日语：小明学日语 Q Q：小华学英语：小华学英语 R R：小芳学德语：小芳学德语.则原命题可表示为：则原命题可表示为：

22、(PQ)R(PQ)R （3）只要不下雨，我就骑自行车上班。）只要不下雨，我就骑自行车上班。P：天下雨。：天下雨。Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：PQPQ。（4）只有只有不下雨，我才骑自行车上班。不下雨，我才骑自行车上班。P：天下雨。：天下雨。Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：Q Q P P。（5）如果如果 2+2=4,则则太阳从东方升起太阳从东方升起。(P Q,T)P Q 如果如果 2+2=4,则则太阳从西方升起太阳从西方升起。(P R,F)R 如果如果 2+2 4,则太阳从东方升起。则太阳从东方升起。(P Q,

23、T)如果如果 2+2 4,则太阳从西方升起。则太阳从西方升起。(P R,T)注意注意:(1)与自然语言的不同：与自然语言的不同：前件与后件可以没有任何内在联系！前件与后件可以没有任何内在联系！(2)在数学中，在数学中，“若若P则则Q”往往表示前件往往表示前件P为真，则后件为真，则后件Q为真的为真的推理关系推理关系.但数理逻辑中，当前件但数理逻辑中，当前件P为假时，为假时，P Q的真值为真。的真值为真。291.2.5 双条件联结双条件联结(等值联结词等值联结词Biconditional)定义定义1.2.5 设设P,Q为二命题，复合命题为二命题，复合命题“P当且仅当当且仅当Q”称为称为P与与Q的双

24、条件命题，记作的双条件命题，记作P iff Q或或 PQ，符号，符号称为双条件（等值）联结词。称为双条件（等值）联结词。PQ为真当且仅当为真当且仅当P，Q真值相同真值相同。联结词联结词“”的定义真值表的定义真值表P PQ QP P Q Q0 00 01 10 01 10 01 10 00 01 11 11 130注：注：（1 1）P P仅当仅当Q Q 可译为可译为PQPQ P P当当Q Q 可译为可译为QPQP P当且仅当当且仅当Q 译为译为PQ （2）“”属于二元属于二元(binary)运算符。运算符。(3)双条件命题双条件命题PQ所表达的逻辑关系是所表达的逻辑关系是,P与与Q互为充分必要条

25、件互为充分必要条件,相当于相当于(P Q)(Q P).只要只要P与与Q的真值同为的真值同为1或同为或同为0,PQ的真值就为的真值就为1,否则否则PQ的真值为的真值为0.双条件联结词连接的两个命题之间可以没双条件联结词连接的两个命题之间可以没有因果关系。有因果关系。例例6.6.分析下列命题的真值分析下列命题的真值.(1)2+2=4 (1)2+2=4 当且仅当当且仅当3 3是奇数是奇数.(P PQ)Q)P P：2+2=4.Q2+2=4.Q：3 3是奇数是奇数.31(2)2+2=4 2+2=4 当且仅当当且仅当3 3不是奇数不是奇数.(P PQ)Q)(3)2+2 4(3)2+2 4 当且仅当当且仅当

26、3 3是奇数是奇数.(PPQ)Q)(4)2+2 4(4)2+2 4 当且仅当当且仅当3 3不是奇数不是奇数.(PPQ)Q)约约 定定:1.1.运算次序优先级：运算次序优先级：，.2.2.相同的运算符按从左至右次序计算，否则要相同的运算符按从左至右次序计算，否则要 加上括号。加上括号。3.3.最外层圆括号可省去。最外层圆括号可省去。小结小结:本节介绍了五种联结词本节介绍了五种联结词(，),),重重点是理解和掌握点是理解和掌握五种联结词的内涵及它们与自然语五种联结词的内涵及它们与自然语言中相应联结词的不同之处言中相应联结词的不同之处.32作业作业:1.P8 (3),(5).2.预习预习1.3,1.

27、4思考题思考题:1.何谓合式公式何谓合式公式?2.复合命题符号化的基本步骤是什么复合命题符号化的基本步骤是什么?3.何谓真值表何谓真值表?4.两个命题公式等价的涵义是什么两个命题公式等价的涵义是什么?5.两个等价的命题公式其真值表有何关系两个等价的命题公式其真值表有何关系?331.3命题公式与翻译命题公式与翻译1.3.1 命题公式命题公式1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)1.3.1 命题合式公式命题合式公式(Well-formed formula)(wff)定义定义1.3.1:单个命题变元和命题常量称为单个命题变元和命题常量称为原子公式原子公式。命题合式公式命题合式公式是

28、由命题变元、是由命题变元、命题常量、命题常量、联结词和圆括号按一定的逻辑关系联结起联结词和圆括号按一定的逻辑关系联结起来的符号串。我们以如下递归的形式来定来的符号串。我们以如下递归的形式来定义合式公式：义合式公式：34 定义定义1.3.2：(1)(1)原子公式是原子公式是合式合式公式公式(wffwff)。（2）若）若A是合式公式，则是合式公式，则(A)也是合式公式。也是合式公式。（3）若）若A，B是合式公式，则是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。（4）当且仅当当且仅当有限次地应用有限次地应用(1)(3)所得到的包含所得到的包含原原子公式、子公式、联结

29、词和括号的符号串是合式公式。联结词和括号的符号串是合式公式。注注:(1)合式公式也称为命题公式，并简称为公式。合式公式也称为命题公式，并简称为公式。(2)命题公式一般不是命题命题公式一般不是命题,仅当公式中的命题变仅当公式中的命题变元用确定的命题代入时元用确定的命题代入时,才得到一个命题才得到一个命题.其真值依其真值依赖于代换变元的那些命题的真值赖于代换变元的那些命题的真值.35例例1 1：指出指出(P(P(P(P Q)Q)是否是命题公式是否是命题公式(wffwff)，如果是，则具体说明。如果是，则具体说明。解：解：P P是是wffwff 由由(1)(1)Q Q是是wffwff 由由(1)(1

30、)P P Q Q是是wffwff 由由(3)(3)(P(P(P(P Q)Q)由由(3)(3)例例2:2:(P Q),(R S)Q,P，(P)等均为合等均为合式公式，而式公式，而PQ S,(P W)Q)等不是合式等不是合式公式。公式。36 1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)有了命题演算的合式公式的概念有了命题演算的合式公式的概念,我们可我们可以把自然语言中的有些语句以把自然语言中的有些语句(复合命题复合命题),翻译成数理逻辑中的符号形式翻译成数理逻辑中的符号形式.基本步骤基本步骤如下如下:(1)分析出各简单命题分析出各简单命题,将它们符号化将它们符号化;(2)使用合适的联结

31、词使用合适的联结词,把简单命题逐个的把简单命题逐个的联结起来联结起来,组成复合命题的符号化表示组成复合命题的符号化表示.37 例例3：1)我今天进城，除非下雨。我今天进城，除非下雨。1-3.(7)2)仅当你走我将留下。仅当你走我将留下。3)假如上午不下雨，我去看电影，否则就在家里假如上午不下雨，我去看电影，否则就在家里 读书或看报。读书或看报。4)除非你努力，否则你将失败。除非你努力，否则你将失败。P11例例5 5)一个人起初说：一个人起初说：“占据空间的、有质量的而且占据空间的、有质量的而且不断变化的叫做物质不断变化的叫做物质”；后来他改说，；后来他改说，“占据空占据空间的有质量的叫做物质，

32、而物质是不断变化的。间的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式问他前后主张的差异在什么地方，试以命题形式进行分析进行分析。1-3.(6)38 例例4：P10 例题例题1 小结小结：本节介了命题公式的概念及复合：本节介了命题公式的概念及复合命题的符号化命题的符号化.重点是理解命题公式的递重点是理解命题公式的递归定义归定义,掌握复合命题的符号化方法掌握复合命题的符号化方法.作业作业:P12 (1),(5)391.4.1 真值表真值表(Truth Table)1.4.2 等价公式等价公式(1.4.1 真值表真值表 前面在定义联结词时前面在定义联结词时,曾经

33、使用过真值表曾经使用过真值表,下面给出下面给出真值表的定义真值表的定义.定义定义1.4.1(对公式的赋值或解释对公式的赋值或解释)设设P1,P2,Pn是出是出现在公式现在公式A中的全部的命题变元中的全部的命题变元,给给P1,P2,Pn各指各指定一个真值，称为对定一个真值，称为对A的一个的一个赋值赋值或或解释解释。若指定的。若指定的一组值使一组值使A的真值为真的真值为真(假假),称这组值为称这组值为A的的成真成真(假假)赋值赋值.40比如比如:对公式对公式(PQ)R,赋值赋值011(即令即令P=0,Q=1,R=1)为为(PQ)R的成真赋值的成真赋值;另一组赋值另一组赋值010为为(PQ)R的成假

34、赋值；还有的成假赋值；还有000，001，111考虑：考虑：含有含有n个命题变元的公式共有多少组个命题变元的公式共有多少组不同的赋值？不同的赋值？定义定义1.4.2(真值表真值表)在命题公式在命题公式A中中,对于命题变元的对于命题变元的每一组赋值和由它们所确定的命题公式每一组赋值和由它们所确定的命题公式A的真值列的真值列成表，称做命题公式成表，称做命题公式A 的的真值表真值表。41对公式对公式A构造真值表的具体步骤为：构造真值表的具体步骤为：（1）找出公式中所有命题变元）找出公式中所有命题变元P1,P2,Pn,列出全部的列出全部的2n组赋值。组赋值。（2）按从小到大的顺序列出对命题变元）按从小

35、到大的顺序列出对命题变元P1,P2,Pn,的全部的全部2n组赋值。组赋值。（3）对应各组赋值计算出公式）对应各组赋值计算出公式A的真值，并的真值，并将其列在对应赋值的后面。将其列在对应赋值的后面。42例例1.1.给出给出(P(P Q)Q)(P(P Q)Q)的真值表：的真值表：P P Q Q P P Q Q(P(P Q)Q)PP Q Q(P(P Q)Q)(P(P Q)Q)0 0 0 00 01 11 11 10 0 1 10 01 11 11 11 1 0 00 01 11 11 11 1 1 11 10 00 01 143例例2：构造公式：构造公式(P Q)R的的 真值表。真值表。PQRPQ(

36、P Q)R000100011101010011111000010100110101111144 练习练习1：构造公式：构造公式(PQ)(Q P真值表。真值表。P Q P QP Q Q P(P Q)(Q P)001111101101111001001110011145PQ(P Q)(P Q)(P Q)Q00100011001001011100练习练习2：构造公式：构造公式 (P Q Q 真值表。真值表。461.4.2 等价公式等价公式给定给定n个个 命题命题变元变元,按合式按合式公式的形公式的形成规则可以形成无数多个命题公式成规则可以形成无数多个命题公式,但这但这些无穷尽的些无穷尽的命题公式中，

37、有些具有相同的命题公式中，有些具有相同的真值表。真值表。考虑：考虑：由由n个命题变元能生成个命题变元能生成?种真值种真值(表表)不同的命题公式？不同的命题公式？)1(n471.4.2 等价公式等价公式定义定义1.4.3:给定两个命题公式给定两个命题公式A和和B,设设P1,P2,Pn为出现于为出现于A和和B中的所有原子变元中的所有原子变元,若给若给P1,P2,Pn任一组真值指派任一组真值指派,A和和B的真值都相同的真值都相同,则称则称A和和B是是等价的或逻辑相等等价的或逻辑相等.记作记作A B注注:(1)“”不是逻辑联结词不是逻辑联结词.(2)命题公式之间的逻辑相等关系具有命题公式之间的逻辑相等

38、关系具有：自反性：自反性：A A；对称性：若；对称性：若A B，则，则B A；传递性：若传递性：若A B且且B C，则，则A C。48 证明公式等价的方法：证明公式等价的方法：1.真值表法真值表法 2.等值演算法等值演算法v1.真值表法真值表法 例例1.(P1.(P Q)Q)(P(P Q)Q)见真值表例题见真值表例题1.1.例例2.2.证明证明:P:PQ Q(PQ)(PQ)(QP)(QP)P PQ QP PQ QQPQPPQPQ(PQ)(PQ)(QP)(QP)0 00 01 11 11 11 10 01 10 00 01 10 01 10 00 01 10 00 01 11 11 11 11

39、11 149例例3：判断公式：判断公式 P(QR)、(PQ)R是否等价。是否等价。P Q RP QQ R P(Q R)(P Q R0000111001011101000110110111100011110101111101000111111150 由真值表可知，两个公式为等价式。由真值表可知，两个公式为等价式。2、等值演算法、等值演算法(Equivalent Caculation)（利用（利用P15表表1-4.8)重要的等价式重要的等价式(补充补充):11.蕴涵等值式蕴涵等值式:P PQ Q P P Q Q 12.等价等价等值式等值式:P PQ Q(PQ)(PQ)(QP)(QP)13.假言易位

40、假言易位:P PQ Q Q Q PP 14.等价否定等价否定等值式等值式:P PQ Q PPQ Q 15.归谬论归谬论:(P PQ Q)(P P Q)Q)P P 51 其中其中P,Q,R等代表任意命题公式等代表任意命题公式.这样上面的每一这样上面的每一个公式都是一个模式个公式都是一个模式,它可以代表无数多个同类它可以代表无数多个同类型的命题公式型的命题公式.例如例如,P P PPT T 中中,用用(P(P Q)Q)置置换换P,P,则得则得 (P(P Q)Q)(P(P Q)Q)T,T,用用P P置换置换P,P,则则得得 (P(P)(P(P)T T。等值演算中使用的一条重要规则：等值演算中使用的一

41、条重要规则：置换规则。置换规则。定义定义1.4.4(1.4.4(子公式子公式)：如果如果X X是是wffwff A A的的一部分一部分,且且X X本身也是本身也是wffwff，则称，则称X X是是A A的的子公式。例如子公式。例如,P,P(P(P Q)Q)为为Q Q(P P(P(P Q)Q)的子公式。的子公式。52定理定理1.4.1(置换定理置换定理Axiom of replacement)设设X X是是wffwff A A的子的子wffwff，若，若X XY Y，则若将，则若将A A中的中的X X用用Y Y来置换，来置换，所得公式所得公式B B与与A A等价，即等价，即A AB B。证：因为

42、对变元的任一指派证：因为对变元的任一指派,X,X与与Y Y真值相同，所以真值相同，所以Y Y 取代取代X X后，公式后，公式B B与公式与公式A A对变元的任一指派真对变元的任一指派真值也相同值也相同,所以所以A AB B。注注:满足满足定理定理1.4.1的条件的置换称为等价置换的条件的置换称为等价置换(或等或等价代换价代换).定义定义1.4.5(1.4.5(等值演算等值演算)：根据已知的等价公式根据已知的等价公式,推演推演出另外一些等价公式的过程称为出另外一些等价公式的过程称为等值演算等值演算.53例例1 1：证明证明 QQ（P P（P P Q Q）QPQP 证证:Q:Q（P P（P P Q

43、 Q）QPQP P(P(吸收律吸收律)例例2 2：证明证明 P P QQ Q Q P P Q Q证：证：(P(P Q)Q)Q Q(P(P Q)Q)(QQ Q)Q)(P P Q)Q)T TP P Q Q例例3 3：证明（：证明（PQPQ）（Q Q P P）P P Q Q R R证：（证：（PQPQ）（Q Q P P）（P P Q Q）（Q Q R R）（P P Q Q）（Q Q R R）（P P QQ）（Q Q R R）（P P Q Q R R）（Q Q Q Q R R）P Q R 54例例4：验证验证P(QR)(P Q)R证证:右右 (P Q)R P Q R P (Q R)P (Q R)P (

44、Q R)练：练：1.(P Q)(P R)P(Q R)2.(P Q)(P Q)(P Q)(P Q)55v等值演算等值演算在计算机硬件设计中在计算机硬件设计中,在开关理论和电子元在开关理论和电子元器件中都占有重要地位器件中都占有重要地位.v小结小结:本节介绍了真值表、公式等价、等值演算和等本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式（价置换等概念，给出了常用的重要等价公式（24个）。个）。重点掌握用真值表法验证公式的等价性和等值演算法重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。推演两个公式等价。作业：作业：P17 1 c,e,4 a,c,7d,

45、e,8.预习预习:1.5,1.6思考题：思考题：9561.5.1 命题公式的分类命题公式的分类1.5.2 重言式重言式(与矛盾式与矛盾式 (contradictory)的性质的性质1.5.3 蕴含蕴含571.5.1 命题公式的分类命题公式的分类 复合命题复合命题(compound propositions)定义定义1.5.1 设设A为任一命题公式，为任一命题公式，（1）若）若A在其各种赋值下的取值均为真，则称在其各种赋值下的取值均为真，则称A是是重言式重言式或或永真式永真式,记为记为T或或1。（2）若）若A在其各种赋值下的取值均为假，则称在其各种赋值下的取值均为假，则称A是是矛盾式矛盾式或或永

46、假式永假式,记为记为F或或0。（3）若）若A不是矛盾式则称不是矛盾式则称A为为可满足式可满足式(satisfiable)。注注:由定义可知由定义可知,重言式一定是可满足式重言式一定是可满足式,反之不真反之不真.)()()log(esatisfiablorycontradictytauto可满足式矛盾式重言式或永真式58 判别命题公式的类型有两种方法判别命题公式的类型有两种方法:真值表法和等值真值表法和等值演算法演算法.等值演算法等值演算法是将所给命题公式通过等值演算化为最是将所给命题公式通过等值演算化为最简单的形式简单的形式,然后再进行判别然后再进行判别.例例1.判别下列命题公式的类型判别下列

47、命题公式的类型.(1).Q(PQ)P)(重言式重言式)(2).(PP)(QQ)R (矛盾式矛盾式)(3).(P Q)P.(可满足式可满足式)591.5.2 重言式重言式(与矛盾式与矛盾式(contradictory)的性质的性质定理定理1.5.1:任何两个重言式的合取或析取任何两个重言式的合取或析取,仍然是一重言式仍然是一重言式.（由幂等律立得）（由幂等律立得）证明证明:设设A和和B为两个重言式为两个重言式,则不论则不论A和和B的分量指派任的分量指派任何真值何真值,总有总有A为为T,B为为T,故故A B T,A T,A B B T T 定理定理1.5.2:1.5.2:一个重言式一个重言式(矛盾

48、式矛盾式),对同一分量都用任何对同一分量都用任何合式公式置换合式公式置换,其结果仍为一重言式其结果仍为一重言式(矛盾式矛盾式).证明证明:由于由于重言式重言式(矛盾式矛盾式)的真值与对变元的赋值无关，的真值与对变元的赋值无关，故对同一变元以任何故对同一变元以任何合式公式置换后，重言式合式公式置换后，重言式(矛盾式矛盾式)的真值仍永为的真值仍永为T（F）。）。60 定理定理1.5.3：A,B是两个命题公式，是两个命题公式，A B的的充要条件是充要条件是A B为重言式。为重言式。证明证明:若若A AB B为重言式，则为重言式，则A AB B永为永为T T，即，即A A，B B的真的真 值表相同，所

49、以值表相同，所以A AB B。反之，反之，若若A A B B，则，则A A，B B真值表相同，真值表相同，所以所以 A AB B永为永为T T，所以，所以A AB B为重言式。为重言式。1.5.3 定义定义1.5.2：当且仅当：当且仅当P Q是一个重言式时，是一个重言式时，我们称我们称“P蕴含蕴含Q”，并记作，并记作P Q.61 它们之间具有如下关系它们之间具有如下关系:PQ Q P 由由P21 表表1-5.1 QP P Q 可以得出可以得出 因此因此,要证明要证明P Q有三种方法有三种方法:1)1)真值表法真值表法:即列出即列出PQ的的真值表真值表,观察其是否为永真。观察其是否为永真。2)2

50、)直接证法直接证法:假定前件假定前件P P是真，推出后件是真，推出后件Q Q是真。是真。3)3)间接证法间接证法:假定后件是假，推出前件是假假定后件是假，推出前件是假,即证即证 Q P。原命题原命题逆换式逆换式反换式反换式逆反式逆反式PQQP P Q Q P62例例:证明证明Q Q（PQPQ）P P1)1)法法1 1：真值表：真值表2)2)法法2 2：若：若 Q Q(PQ)PQ)为真，则为真，则 Q Q，PQPQ为真，为真，所以所以Q Q为假，为假，P P为假，所以为假，所以P P为真。为真。3)3)法法3 3：若：若P P为假，则为假，则P P为真，再分二种情况：为真，再分二种情况：若若Q

51、Q为真，则为真，则Q Q为假为假,从而从而Q Q（PQPQ）为假为假.若若Q Q为假，则为假，则PQPQ为假，则为假，则Q Q（PQPQ）为假）为假.根据根据 ，所以，所以 Q Q（PQPQ）P PP21 P21 表表1-5.21-5.2给出了给出了1414个个蕴含式蕴含式,它们都可以用上述方法加它们都可以用上述方法加以推证以推证.63 等价式与蕴含式的关系等价式与蕴含式的关系:定理定理1.5.4:1.5.4:设设P,QP,Q为任意两个命题公式为任意两个命题公式,P,PQ Q的的充要条件为充要条件为P PQ Q且且Q QP.P.证：若证：若P PQ Q，则，则P PQ Q为永真式为永真式 因为

52、因为 P PQ Q（PQPQ）（QPQP）所以所以 PQPQ，QPQP为永真式为永真式,从而从而 P PQ Q，Q QP.P.反之，若反之，若P PQ Q，Q QP P，则，则PQPQ，QPQP为永真式为永真式,所以（所以（PQPQ）（QPQP）为永真式，）为永真式，从而从而 P PQ Q为永真式，即为永真式，即P PQ.Q.64 蕴含的性质蕴含的性质:设设A A，B B，C C为任意为任意wffwff,1)1)若若A AB B，且，且A A为永真式，则为永真式，则B B必为永真式必为永真式.2)2)若若A AB B，B BC C，则，则A AC.C.3)3)若若A AB B，A AC C，则

53、，则A AB B C.C.4)4)若若A AB B且且C CB B，则，则A A C CB.B.证：证：1)1)因为因为ABAB，A A永为永为T,T,所以所以B B必永为必永为T.T.2)2)由由I I1111 （AB)AB)(BCBC）AC,AC,所以若所以若A AB B，B BC C，则（，则（AB)AB)(BCBC）永为）永为T,T,从而从而ACAC永永 为为T,T,故故A AC.C.653)3)（ABAB）（ACAC）（A A B B）（A A C C）A A（B B C C）ABAB C C4)4)（ABAB）（CBCB）（A A B B）（C C B B）（A A CC）B B

54、（A A C C）B B A A CBCB66 小结：小结：本节介绍了命题公式的分类，重言式、矛盾式本节介绍了命题公式的分类，重言式、矛盾式与蕴含式的概念及其性质，等价式与蕴涵式的关系。与蕴含式的概念及其性质，等价式与蕴涵式的关系。重点掌握重点掌握:（1 1）用等值演算法判别命题公式的类型。）用等值演算法判别命题公式的类型。（2 2）重言式、矛盾式与蕴涵式的性质。）重言式、矛盾式与蕴涵式的性质。（3 3）等价式与蕴涵式的关系。）等价式与蕴涵式的关系。作业作业:P23(1)c,d,(2)a,(9).:P23(1)c,d,(2)a,(9).预习预习:1.6:1.6 思考题思考题:1):1)为什么要

55、引入联结词为什么要引入联结词?2)2)什么是最小联结词组什么是最小联结词组?c,671.6.1 不可兼析取不可兼析取(排斥或排斥或/异或异或)(exclusive or)1.6.2 与非联结词与非联结词(Nand1.6.3 或非联结词或非联结词(Nor1.6.4 条件否定联结词条件否定联结词(Non-conditional1.6.5 最小联结词组最小联结词组(The minimal set of connectives68 在第二节在第二节(1.2)中我们定义了五种基本的联结词中我们定义了五种基本的联结词，,但在但在命题逻辑中命题逻辑中,这些联结词还不能很广泛这些联结词还不能很广泛地直接表达命

56、题之间的联系地直接表达命题之间的联系(例如例如,“P异或异或Q”只能间接地只能间接地表示为表示为(P Q)Q)(P Q),Q),为此本节再给出逻辑设计中为此本节再给出逻辑设计中常用的另外四种常用的另外四种联结词联结词.1.6.1 不可兼析取不可兼析取(排斥或排斥或/异或异或)(exclusive or)定义定义1.6.1:设设P,Q为二命题，复合命题为二命题，复合命题“P,Q之中之中恰有一恰有一个个为真为真”称为称为P与与Q的的不可兼析取不可兼析取，记作，记作P Q，符号，符号“”称为称为异或异或联结词联结词.P Q P Q 为真当且仅当为真当且仅当P P和和Q Q的的真值不同真值不同.69

57、联结词联结词“”的定义真值表的定义真值表P PQ Q P P Q Q 0 00 00 00 01 11 11 10 01 11 11 10 0定义了定义了联结词联结词“”后后,命题逻辑中的有些命题就可命题逻辑中的有些命题就可以符号化为非常简捷的形式以符号化为非常简捷的形式.例例:派小王或小李中的一人去开会。派小王或小李中的一人去开会。（）设设P：派小王去开会。派小王去开会。Q：派小李去开会。派小李去开会。则上述命题可符号化为：则上述命题可符号化为：(P Q)70说明：说明：“”属于二元属于二元(binary)运算符运算符.联结词联结词“”的性质的性质:设设P,Q,R为命题公式为命题公式,则有则

58、有(1)P 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 P71 定理定理1.6.1:设设P,Q,R为命题公式为命题公式,如果如果 P QR,R,则则 P RQ,Q RP,P,且且P Q R P Q R 为一矛盾式为一矛盾式.证证:由由 P QR R 得得 P RP RP (P Q)P (P Q)(P P)Q(P P)QF QF QQ Q Q R Q RQ (P Q)Q (P Q)F PF PP P P Q R P Q

59、 RR RR RF F721.6.2 与非联结词与非联结词(Nand定义定义1.6.2 设设P,Q为二命题，复合命题为二命题，复合命题“P与与Q的否定的否定”称称为为P与与Q的与非式，记作的与非式，记作PQ，符号，符号“”称为与非联称为与非联结词结词.PQ PQ 为真当且仅当为真当且仅当P P和和Q Q不同时为真不同时为真.联结词联结词“”的定义真值表的定义真值表P PQ Q P PQ Q 0 00 01 10 01 11 11 10 01 11 11 10 073说明说明:(1)由定义可知由定义可知,PQ (PQ)(2)“”属于二元属于二元(binary)运算符运算符.联结词联结词“”的性质

60、的性质:(1)PP (PPP)P(2)(PQ)(PQ)(PQ Q)(PQQ)(3)(3)(PP)(QQ)P Q(P Q)PQ 741.6.3 或非联结词或非联结词(Nor定义定义1.6.3 设设P,Q为二命题，复合命题为二命题，复合命题“P或或Q的否定的否定”称为称为P与与Q的或非式，记作的或非式，记作PQ，符号，符号“”称为或非联结词称为或非联结词.PQ为真当且仅当为真当且仅当 P与与Q同为假同为假.联结词联结词“”的定义真值表的定义真值表P PQ Q PQ PQ 0 00 01 10 01 10 01 10 00 01 11 10 075说明说明:(1)由定义可知由定义可知,PQ (PQ)

61、(2)“”属于二元属于二元(binary)运算符运算符.联结词联结词“”的性质的性质:(1)PP (PP P)P(2)(PQ)(PQ)(PQ)(PQ Q)(3)(3)(PP)(QQ)P Q(P Q)PQ 761.6.4 条件否定联结词条件否定联结词(Non-conditional定义定义1.6.4 设设P,Q为二命题，复合命题为二命题，复合命题“P Q”称为命称为命题题P与与Q的条件否定式的条件否定式,P Q为真当且仅当为真当且仅当P为真且为真且Q为假为假.联结词联结词“”的定义真值表的定义真值表P PQ QP P Q Q0 00 00 00 01 10 01 10 01 11 11 10 0

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

63、价的命题公式,均可由这均可由这 9 9个联结词直接表达个联结词直接表达.下面我们以含两个命题变元下面我们以含两个命题变元P P，Q Q的所的所有互等价的命题公式为例，来说明这一问题。有互等价的命题公式为例，来说明这一问题。ccc,n2278由两个命题变元由两个命题变元P P，Q Q所构成的互不等价的所构成的互不等价的 个命题公式个命题公式如下如下:42P QFPQPQP QPQ PQP Q PQ0 0 000000000 1 000011111 0 001100111 1 01010101 c c 由上表可知由上表可知,9 9个联结词足以直接表达命题之间的各种联个联结词足以直接表达命题之间的各

64、种联系系.二元运算中，二元运算中，9 9个联结词并不都是必要的。个联结词并不都是必要的。P Q P Q PQ Q QP P PQ P QT0 0111111110 1000011111 0001100111 101010101定义定义1.6.5：在一个联结词的集合中在一个联结词的集合中,如果一个联结词可如果一个联结词可由该集合中的其它联结词定义由该集合中的其它联结词定义,则则称此称此联结词为冗余联联结词为冗余联结词结词,否则称为独立联结词否则称为独立联结词.不含冗余联结词的联结词组不含冗余联结词的联结词组称为称为最小联结词组最小联结词组.说明说明:最小联结词组中的联结词构成的式子足以把一切最小

65、联结词组中的联结词构成的式子足以把一切命题公式等价的表达出来。命题公式等价的表达出来。对于对于9 9个联结词的集合个联结词的集合,由于由于(1)PQ(PQ)(PQ)(QP)(QP)(2)P (2)PQ QPP Q Q (3)P P Q Q(P(P Q)Q)(4)P P Q Q(P(P Q)Q)c81 (5)(5)(P Q)(PQ)(6)PQ (PQ)(7)PQ (PQ)(8)P Q (P Q)故任意命题公式都可由仅包含故任意命题公式都可由仅包含,或或,的命题的命题公式等价代换公式等价代换.即即9 9个联结词的集合中至少有七个个联结词的集合中至少有七个冗余联冗余联结词结词.又注意到联结词又注意到

66、联结词,和和,不再有冗余联结不再有冗余联结词词,故故,或或,为最小联结词组为最小联结词组.但实际中为了使但实际中为了使用方便用方便,命题公式常常同时包含命题公式常常同时包含,.c82例例1:试证试证是最小联结词组是最小联结词组.证：证：P P(P(P P)P)PP PP P P Q Q(P(P Q)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)P P Q Q(P(P Q)Q)(PP)(PP)(QQ)(QQ)(PP)(QQ)(PP)(QQ)例例2.2.试证试证，是最小联结词组是最小联结词组 证：证：P P Q Q(P(P Q)Q)(PQ)(PQ)P P Q Q(P)(P)Q QPQPQ小结小结:本节主要介绍了四种新的联结词本节主要介绍了四种新的联结词 及最及最小联结词组小联结词组.作业作业:1.P29(1),(2),(4)c,832.预习预习1.7思考题思考题:1.何谓命题公式的何谓命题公式的(主主)析析(合合)取范式取范式?2.命题公式的命题公式的(主主)析析(合合)取范式唯一吗取范式唯一吗?3.为何要将命题公式化为与之等价的主析为何要将命题公式化为与之等价的主析(合合)取范式取