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

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

2、辑成为一门专门的学科。专门的学科。v上个世纪上个世纪30年代以后，数理逻辑进入一个崭新的发年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。等密切关联。2022-8-5 计算机科学与技术学院v1931年年Godel不完全性定理的提出，以及递不完全性定理的提出，以及递归函数可计算性的引入，促使了归函数可计算性的引入，促使了1936年年Turing机的产生，十年后，第一台电子计算机的产生，十年后，第一台电子计算机问世机问世。v从广义上讲，数理逻辑包括四论、两演算从广义上讲，数理逻辑包括四论、两演算即集合论、模型论、

3、递归论、证明论和命即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，题演算、谓词演算，但现在提到数理逻辑，一般是指一般是指命题演算命题演算和和谓词演算谓词演算。本书课程只。本书课程只研究这两个演算。研究这两个演算。2022-8-5 计算机科学与技术学院v数理逻辑与计算机学、控制论、人工智能的数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。比较热门的研究领域。2022-8-5 计算机科学与技术学院 n1.1 命题

4、命题表示方法表示方法(Proposition and Its Expression)n1.2 逻辑联结词逻辑联结词(Logical Connectives)n1.3 命题公式与翻译命题公式与翻译(ormula&Its Translation)Truth Tables and Prepositional Equivalences2022-8-5 计算机科学与技术学院蕴含蕴含Tautology and Implication Inference Theory 2022-8-5 计算机科学与技术学院n1.1.1 命题命题n1.1.2 命题的表示方法命题的表示方法n1.1.3 命题的分类命题的分类20

5、22-8-5 计算机科学与技术学院 1.1.1 命题命题（Proposition)数 理 逻 辑 研 究 的 中 心 问 题 是数 理 逻 辑 研 究 的 中 心 问 题 是 推 理推 理（inference),而推理的而推理的前提前提和和结论结论都是表达判断都是表达判断的陈述句，因而表达判断的陈述句构成了推理的陈述句，因而表达判断的陈述句构成了推理的基本单位的基本单位。2022-8-5 计算机科学与技术学院 基本概念基本概念 命题：能够判断真假的陈述句。命题：能够判断真假的陈述句。命题的真值：命题的判断结果。命题的真值只取命题的真值：命题的判断结果。命题的真值只取两个值两个值:真（真（用用T

6、(true)或或1表示表示）、假（）、假（用用F(false)或或0表表示示）。真命题：判断为正确的命题，即真值为真的命题。真命题：判断为正确的命题，即真值为真的命题。假命题：判断为错误的命题，即真值为假的命题。假命题：判断为错误的命题，即真值为假的命题。2022-8-5 计算机科学与技术学院因而又可以称因而又可以称命题是具有唯一真值的陈述句。命题是具有唯一真值的陈述句。判断命题的两个步骤判断命题的两个步骤：1、是否为陈述句；、是否为陈述句；2、是否有确定的、唯一的真值。、是否有确定的、唯一的真值。例例：判断下列句子是否为命题。：判断下列句子是否为命题。(1).100是自然数。是自然数。T (

7、2).太阳从西方升起。太阳从西方升起。F 2022-8-5 计算机科学与技术学院(3).3+3=8.F(4).How do you do?疑问句，疑问句，不是命题不是命题(5).明年的十月一日是晴天。明年的十月一日是晴天。是命题，其真值是命题，其真值到到明年十月一日方可知道。明年十月一日方可知道。(6).x+39 不是命题不是命题(7).我正在说谎。我正在说谎。是悖论是悖论2022-8-5 计算机科学与技术学院(8).1+101=110 二进制中为真，十进制中为假。二进制中为真，十进制中为假。(9).如果太阳从西方升起，那么如果太阳从西方升起，那么2是奇数是奇数。T(10).国足能杀入国足能杀

8、入2006世界杯当且仅当世界杯当且仅当2+2=4。F(11).今天天气多好啊！今天天气多好啊！感叹句，感叹句，不是命题不是命题(12).请你关上门！请你关上门！祁使句，不祁使句，不是命题，是命题，(13).别的星球上有生物。别的星球上有生物。是命题，客观上能判是命题，客观上能判断真假。断真假。2022-8-5 计算机科学与技术学院 说明：说明：（1）只有具有确定真值的陈述句才是命题。）只有具有确定真值的陈述句才是命题。一切没有判断内容的句子，无所谓一切没有判断内容的句子，无所谓 是非的句子，如是非的句子，如感叹句、祁使句、感叹句、祁使句、疑问疑问 句等都不是命题。句等都不是命题。（2）因为因为

9、命题只有两种真值，所以命题只有两种真值，所以“命题命题 逻逻 辑辑”又称又称“二值逻辑二值逻辑”。2022-8-5 计算机科学与技术学院 (3)“具有确定真值具有确定真值”是指客观上的具有，与我们是指客观上的具有，与我们 是否知道它的真值是两回事。如上例中是否知道它的真值是两回事。如上例中 的（的（5）和（）和（13）。）。1.1.2 命题的表示方法命题的表示方法 在本书中，用大写英文字母在本书中，用大写英文字母A,B,P,Q或带下或带下标的字母标的字母P1,P2,P3,或数字或数字(1),2,等表示命等表示命题，称之为命题标识符。题，称之为命题标识符。2022-8-5 计算机科学与技术学院

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

11、原子命题时，该变元称为：当命题变元表示原子命题时，该变元称为 原子变元。原子变元。命题变元也用命题变元也用A,B,P,Q,P1,P2,P3,表示。表示。2022-8-5 计算机科学与技术学院 1.1.3 命题的分类：命题的分类：简单简单/原子命题：原子命题：不能分解为更简单的陈述语不能分解为更简单的陈述语句的命题句的命题(如上例中的命题如上例中的命题)。复合命题：复合命题：由简单命题通过由简单命题通过联结词联结词联结而成联结而成的命题。的命题。联结词就是复合命题中的运算符。联结词就是复合命题中的运算符。2022-8-5 计算机科学与技术学院注意注意：（1）一个符号）一个符号(如如P),它表示的

12、是命题常量还是它表示的是命题常量还是命题变元，一般由上下文来确定。命题变元，一般由上下文来确定。（2）命题变元可以表示任意命题，它不能确定）命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与真值，故命题变元不是命题。这与“变数变数x不不是数是数”是一样的道理。是一样的道理。2022-8-5 计算机科学与技术学院小结：小结：本节主要介绍了命题、命题的真值、本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、原子命题、复合命题、命题标识符、命题常量、命题变元和原子变元的概念。命题变元和原子变元的概念。重点理解和掌握命题、命题变元、简单（原子）重点理解和掌握命题

13、、命题变元、简单（原子）命题、复合命题四个概念。命题、复合命题四个概念。作业：作业：P2 1,22022-8-5 计算机科学与技术学院 1.2 逻辑联结词逻辑联结词(Logical Connectives)1.2.1 否定联结词否定联结词(Negation)1.2.2 合取联结词合取联结词(Conjunction)1.2.3 析取联结词析取联结词(Disjunction)1.2.4 条件联结词条件联结词(蕴涵联结词蕴涵联结词Conditional)1.2.5 双条件联结双条件联结(等值联结词等值联结词Biconditional)2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词

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

15、属于一元(unary)运算符运算符.1.2逻辑联结词逻辑联结词(Logical Connectives)2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)n“”的定义也可用下表来说明的定义也可用下表来说明.联结词联结词“”的定义真值表的定义真值表 P P01102022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)例例1.P:天津是一个城市天津是一个城市.Q:3是偶数是偶数.于是于是:P:天津不是一个城市天津不是一个城市.Q:3不是偶数不是偶数.例例2.P:苏州处处清洁苏州处处清洁.

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

17、机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)联结词联结词“”的定义真值表的定义真值表PQ P Q 0 00 00 00 01 10 01 10 00 01 11 11 12022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)说明：说明：“”属于二元属于二元(binary)运算符运算符.合取运算特点合取运算特点：只有参与运算的二命题全为真：只有参与运算的二命题全为真时，运算结果才为真，否则为假。时，运算结果才为真，否则为假。自然语言中的表示自然语言中的表示“并且并且”意思的联结词，如意思的联结词，如“

18、既既又又”、“不但不但而且而且”、“虽然虽然但是但是”、“一一面面一面一面”、“和和”、“与与”等都可以等都可以 符号化为符号化为。2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)n例例3.将下列命题符号化将下列命题符号化.(1)李平既聪明又用功李平既聪明又用功.(2)李平虽然聪明李平虽然聪明,但不用功但不用功.(3)李平不但聪明李平不但聪明,而且用功而且用功.(4)李平不是不聪明李平不是不聪明,而是不用功而是不用功.解解:设设 P:李平聪明李平聪明.Q:李平用功李平用功.则则 (1)PQ (2)PQ (3)PQ (4)(P)Q 20

19、22-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)注意注意：不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词！例如例如:(1)李敏和李华是姐妹。李敏和李华是姐妹。(2)李敏和张华是朋友。李敏和张华是朋友。2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)例例4.试生成下列命题的合取试生成下列命题的合取.(1)P:我们在我们在6-503.Q:今天是星期二今天是星期二.(2)S：李平在吃饭：李平在吃饭.R：张明在吃饭：张明在吃饭.解解:(1)PQ:我们在我们在6-503且今天

20、是星期二且今天是星期二.(2)SR:李平与张明在吃饭李平与张明在吃饭.2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)同之处的不和与语言中与日常.):(,)2(1).(.(,)1(李华和李敏是姐妹如去翻译不能一概用和与不同意义上使用联结词自然语言中有时在各种如上例的命题原子命题生成一个新的甚至互为否定的独立无关的逻辑学中允许两个相互2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)1.2.3 析取析取联结联结词词(Disjunction)定义定义1.2.3 设设P,Q为二命题，

21、复合命题为二命题，复合命题“P或或Q”称为称为P与与Q的析取式，记作的析取式，记作PQ，符号，符号称为称为析取联结词析取联结词.PQ为真当且仅当为真当且仅当 P与与Q中至少有中至少有一个为真一个为真.2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)联结词联结词“”的定义真值表的定义真值表PQ P Q 0 00 00 00 01 11 11 10 01 11 11 11 12022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)说明：说明：“”属于二元属于二元(binary)运算符运算

22、符.析取运算特点析取运算特点：只有参与运算的二命题全为假：只有参与运算的二命题全为假时，运算结果才为假，否则为真。时，运算结果才为假，否则为真。由析取联结词的定义可以看出，由析取联结词的定义可以看出，“”与汉与汉语中的联结词语中的联结词“或或”意义相近，但又不完全相同。意义相近，但又不完全相同。在现代汉语中，联结词的在现代汉语中，联结词的“或或”实际上有实际上有“”和和“”之分。之分。2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)考察下面命题：考察下面命题：（1）小王爱打球或爱跑步。）小王爱打球或爱跑步。（设设P：小王爱打球。：小王

23、爱打球。Q：小王爱跑步。：小王爱跑步。则上述命题可符号化为：则上述命题可符号化为：P Q（2）林芳学过英语或法语。）林芳学过英语或法语。（设设P：林芳学过英语林芳学过英语。Q：林芳学过法语林芳学过法语。则上述命题可符号化为：则上述命题可符号化为：P Q2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)（3）派小王或小李中的一人去开会。）派小王或小李中的一人去开会。（）设设P：派小王去开会。派小王去开会。Q：派小李去开会。派小李去开会。则上述命题可符号化为：则上述命题可符号化为：(PQ)(PQ)（4）人固有一死，或重于泰山或轻于鸿毛）人固

24、有一死，或重于泰山或轻于鸿毛.(）（5）ab=0,即即a=0 或或 b=0.（由此可见由此可见,“P Q”表示的是表示的是“2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)注意：注意：当当P和和Q客观上不能同时发生时，客观上不能同时发生时，“P或或Q”可以符号化为可以符号化为“P Q”。例如：小王现在在宿舍或在图书馆。设例如：小王现在在宿舍或在图书馆。设 P：小王现在在宿舍。：小王现在在宿舍。Q：小王现在在图书馆。：小王现在在图书馆。则上述命题可符号化为：则上述命题可符号化为：PQ。2022-8-5 计算机科学与技术学院 1.2逻辑联

25、结词逻辑联结词(Logical Connectives)同之处的不或语言中与日常(1).(2),(:63)P逻辑学中允许联结两个毫无关系的命题自然语言中有时在各种不同意义上使用联结词 或 不能一概用去翻译 如例2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)1.2.4.条件条件联结联结词词(蕴涵蕴涵联结联结词词Conditional)定义定义1.2.4 设设P,Q为二命题，复合命题为二命题，复合命题“如果如果P则则Q(若若P则则Q)”称为称为P与与Q的条件命题的条件命题,记作记作P Q.PQ为假当且仅当为假当且仅当P为真且为真且Q为假

26、为假.称符称符号号“”为条件联结词。并称为条件联结词。并称P为前件，为前件，Q为后为后件件.2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)联结词联结词“”的定义真值表的定义真值表PQP Q0 00 01 10 01 11 11 10 00 01 11 11 12022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)注：注：（1）PQ表示的基本逻辑关系是表示的基本逻辑关系是,Q是是P的必要的必要条件或条件或P是是Q的充分条件的充分条件.因此复合命题因此复合命题“只只要要P就就Q”、“

27、因为因为P，所以，所以Q”、“P仅当仅当Q”、“只有只有Q才才P”等都可以符号化为等都可以符号化为 PQ 的形式。的形式。（2）“”属于二元属于二元(binary)运算运算.2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)例例5.将下列命题符号化。将下列命题符号化。（1 1）天不下雨，则草木枯黄。）天不下雨，则草木枯黄。P：天下雨。：天下雨。Q：草木枯黄。：草木枯黄。则原命题可表示为：则原命题可表示为：PQ。（2）如果小明学日语，小华学英语，则小芳）如果小明学日语，小华学英语，则小芳学德语。学德语。P：小明学日语：小明学日语.Q：小华

28、学英语：小华学英语.R：小芳学德语：小芳学德语.则原命题可表示为：则原命题可表示为：(PQ)R2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)（3）只要不下雨，我就骑自行车上班。）只要不下雨，我就骑自行车上班。P：天下雨。：天下雨。Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：PQ。（4）只有不下雨，我才骑自行车上班。）只有不下雨，我才骑自行车上班。P：天下雨。：天下雨。Q：我骑自行车上班。：我骑自行车上班。则原命题可表示为：则原命题可表示为：Q P。2022-8-5 计算机科学与技术学院 1.2逻辑联结词

29、逻辑联结词(Logical Connectives)（5）如果如果 2+2=4,则则太阳从东方升起太阳从东方升起。(PQ,T)P Q 如果如果 2+2=4,则则太阳从西方升起太阳从西方升起。(PR,F)R 如果如果 2+24,则太阳从东方升起。则太阳从东方升起。(PQ,T)如果如果 2+2 4,则太阳从西方升起。则太阳从西方升起。(PR,T)2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)注意注意:(1)与自然语言的不同：与自然语言的不同：前件与后件可以没有任前件与后件可以没有任何内在联系！何内在联系！(2)在数学中，在数学中，“若若

30、P则则Q”往往表示前件往往表示前件P为真，为真，则后件则后件Q为真的推理关系为真的推理关系.但数理逻辑中，当前但数理逻辑中，当前件件P为假时，为假时，PQ的真值为真。的真值为真。2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)1.2.5 双条件双条件联结联结(等值等值联结联结词词Biconditional)定义定义1.2.5 设设P,Q为二命题，复合命题为二命题，复合命题“P当且仅当且仅当当Q”称为称为P与与Q的双条件命题，记作的双条件命题，记作P iff Q或或 PQ，符号，符号称为双条件（等值）联结词。称为双条件（等值）联结词。P

31、Q为真当且仅当为真当且仅当P，Q真值相同。真值相同。2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)联结词联结词“”的定义真值表的定义真值表PQP Q0 00 01 10 01 10 01 10 00 01 11 11 12022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)注：注：（1）P仅当仅当Q 可译为可译为PQ P当当Q 可译为可译为QP P当且仅当当且仅当Q 译为译为PQ （2）“”属于二元属于二元(binary)运算符。运算符。(3)双条件命题双条件命题PQ所表达的逻辑

32、关系是所表达的逻辑关系是,P与与Q互为充分必要条件互为充分必要条件,相当于相当于(PQ)(QP).只要只要P与与Q的真值同为的真值同为1或同为或同为0,PQ的真值就的真值就为为1,否则否则PQ的真值为的真值为0.双条件联结词连接的双条件联结词连接的两个命题之间可以没有因果关系。两个命题之间可以没有因果关系。2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)例例6.分析下列命题的真值分析下列命题的真值.(1)2+2=4 当且仅当当且仅当3是奇数是奇数.(PQ)P：2+2=4.Q：3是奇数是奇数.(2)2+2=4 当且仅当当且仅当3不是奇数

33、不是奇数.(PQ)(3)2+24 当且仅当当且仅当3是奇数是奇数.(PQ)(4)2+24 当且仅当当且仅当3不是奇数不是奇数.(PQ)2022-8-5 计算机科学与技术学院 1.2逻辑联结词逻辑联结词(Logical Connectives)约约 定定:1.运算次序优先级：运算次序优先级：，.2.相同的运算符按从左至右次序计算，否相同的运算符按从左至右次序计算，否则要加上括号。则要加上括号。3.最外层圆括号可省去。最外层圆括号可省去。小结小结:本节介绍了五种联结词本节介绍了五种联结词(，),重点是理解和掌握重点是理解和掌握五种联结词的内涵及它五种联结词的内涵及它们与自然语言中相应联结词的不同之

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

35、命题公式1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)2022-8-5 计算机科学与技术学院1.3命题公式与翻译命题公式与翻译(ormula&Its Translation)1.3.1 命题合式公式命题合式公式(Well-formed formula)(wff)定义定义1.3.1:单个命题变元和命题常量称为单个命题变元和命题常量称为原子公原子公式式。命题合式公式命题合式公式是由命题变元、是由命题变元、命题常量、命题常量、联结联结词和圆括号按一定的逻辑关系联结起来的符号词和圆括号按一定的逻辑关系联结起来的符号串。我们以如下递归的形式来定义合式公式：串。我们以如下递归的形式来定义合式公式

36、：2022-8-5 计算机科学与技术学院 1.3命题公式与翻译命题公式与翻译定义定义1.3.2：(1)(1)原子公式是原子公式是合式合式公式公式(wff)。（2）若）若A是合式公式，则是合式公式，则(A)也是合式公式。也是合式公式。（3）若）若A，B是合式公式，则是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。（4）当且仅当当且仅当有限次地应用有限次地应用(1)(3)所得到的包所得到的包含含原子公式、原子公式、联结词和括号的符号串是合式公联结词和括号的符号串是合式公式。式。2022-8-5 计算机科学与技术学院 1.3命题公式与翻译命题公式与翻译注注:(1)合式

37、公式也称为合式公式也称为命题公式命题公式，并简称为，并简称为公式。公式。(2)命题公式命题公式一般一般不是不是命题命题,仅当仅当公式中的公式中的命题变命题变元元用用确定的命题确定的命题代入时代入时,才得到一个命题才得到一个命题.其真值其真值依赖于代换变元的那些命题的真值依赖于代换变元的那些命题的真值.2022-8-5 计算机科学与技术学院1.3命题公式与翻译命题公式与翻译例例1：指出：指出(P(P Q)是否是命题公式是否是命题公式(wff)，如果是，则具体说明如果是，则具体说明。解：解：P是是wff 由由(1)Q是是wff 由由(1)P Q是是wff 由由(2)(P(P Q)由由(2)2022

38、-8-5 计算机科学与技术学院1.3命题公式与翻译命题公式与翻译例例2:(P Q),(R S)Q,P，(P)等均等均为合式公式，而为合式公式，而PQ S,(P W)Q)等不等不是合式公式。是合式公式。2022-8-5 计算机科学与技术学院 1.3命题公式与翻译命题公式与翻译n1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)n有了命题演算的合式公式的概念有了命题演算的合式公式的概念,我们可以把我们可以把自然语言中的有些语句自然语言中的有些语句(复合命题复合命题),翻译成数翻译成数理逻辑中的符号形式理逻辑中的符号形式.基本步骤如下基本步骤如下:n(1)分析出各简单命题分析出各简单命题,将它

39、们符号化将它们符号化;n(2)使用合适的联结词使用合适的联结词,把简单命题逐个的联把简单命题逐个的联结起来结起来,组成复合命题的符号化表示组成复合命题的符号化表示.2022-8-5 计算机科学与技术学院 1.3命题公式与翻译命题公式与翻译n例例3：1)我今天进城，除非下雨。我今天进城，除非下雨。n2)仅当你走我将留下。仅当你走我将留下。n3)假如上午不下雨，我去看电影，否则就在家里假如上午不下雨，我去看电影，否则就在家里n 读书或看报。读书或看报。n4)除非你努力，否则你将失败。除非你努力，否则你将失败。n5)一个人起初说：一个人起初说：“占据空间的、有质量的而且占据空间的、有质量的而且不断变

40、化的叫做物质不断变化的叫做物质”；后来他改说，；后来他改说，“占据空间占据空间的有质量的叫做物质，而物质是不断变化的。的有质量的叫做物质，而物质是不断变化的。”问问他前后主张的差异在什么地方，试以命题形式进行他前后主张的差异在什么地方，试以命题形式进行分析分析。2022-8-5 计算机科学与技术学院 1.3命题公式与翻译命题公式与翻译n例例4：P6 例例1.3.3，例，例1.3.4(5)，例，例1.3.5n小结小结：本节介了命题公式的概念及复合命题的：本节介了命题公式的概念及复合命题的符号化符号化.重点是理解命题公式的递归定义重点是理解命题公式的递归定义,掌握掌握复合命题的符号化方法复合命题的

41、符号化方法.n作业作业:P7:22022-8-5 计算机科学与技术学院 1.4.1 真值表真值表(Truth Table)1.4.2 等价公式等价公式()1.4.1 真值表真值表 前面在定义联结词时前面在定义联结词时,曾经使用过真值表曾经使用过真值表,下面下面给出真值表的定义给出真值表的定义.2022-8-5 计算机科学与技术学院 定义定义1.4.1(对公式的赋值或解释对公式的赋值或解释)设设P1,P2,Pn是出现在公式是出现在公式A中的全部的命题变元中的全部的命题变元,给给P1,P2,Pn各指定一个真值，称为对各指定一个真值，称为对A的一个的一个赋值赋值或或解释解释。若指定的一组值使。若指定

42、的一组值使A的真值为真的真值为真(假假),称这组值为称这组值为A的的成真成真(假假)赋值赋值.2022-8-5 计算机科学与技术学院 例如例如:对公式对公式(PQ)R，赋值，赋值011(即令即令P=0，Q=1，R=1)为为(PQ)R的成真赋值的成真赋值;另一组另一组赋值赋值010为为(PQ)R的成假赋值；还有的成假赋值；还有000，001，1112022-8-5 计算机科学与技术学院考虑：考虑：含有含有n个命题变元的公式共有多少个命题变元的公式共有多少组不同的赋值？组不同的赋值？定义定义1.4.2(真值表真值表)在命题公式在命题公式A中中,对于命题变对于命题变元的每一组赋值和由它们所确定的命题

43、公式元的每一组赋值和由它们所确定的命题公式A的真值列成表，称做命题公式的真值列成表，称做命题公式A 的的真值表真值表。2022-8-5 计算机科学与技术学院 对公式对公式A构造真值表的具体步骤为：构造真值表的具体步骤为：（1）找出公式中所有命题变元）找出公式中所有命题变元P1,P2,Pn,列出全部的列出全部的2n组赋值。组赋值。（2）按从小到大的顺序列出对命题变元）按从小到大的顺序列出对命题变元P1,P2,Pn,的全部的全部2n组赋值。组赋值。（3）对应各组赋值计算出公式）对应各组赋值计算出公式A的真值，并的真值，并将其列在对应赋值的后面。将其列在对应赋值的后面。2022-8-5 计算机科学与

44、技术学院 例例1.1.给出给出(P Q)(P Q)的真值表：的真值表：P QP Q(P Q)P Q(P Q)(P Q)0 0 0 00 0 1 11 1 0 01 1 1 12022-8-5 计算机科学与技术学院例例1.1.给出给出(P(P Q)Q)(P(P Q)Q)的真值表：的真值表：P Q P Q(P Q)P Q(P Q)(P 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 12022-8-5 计算机科学与技术学院例例2：构造公式：构造公式(P Q)R的的 真值表。真值表。PQRPQ(

45、P Q)R0000010100111001011101112022-8-5 计算机科学与技术学院 例例2：构造公式：构造公式(P Q)R的的 真值表。真值表。PQRPQ(P Q)R00010001110101001111100001010011010111112022-8-5 计算机科学与技术学院 n练习练习1：构造公式：构造公式(PQ)(Q P)真值表。真值表。PQPQPQQP(PQ)(QP)000110112022-8-5 计算机科学与技术学院n练习练习1：构造公式：构造公式(PQ)(Q P)真值表。真值表。PQPQPQQP(PQ)(QP)0011111011011110010011100

46、1112022-8-5 计算机科学与技术学院 PQ(PQ)(PQ)(PQ)Q00011011练习练习2：构造公式：构造公式(PQ)Q真值表。真值表。2022-8-5 计算机科学与技术学院 PQ(P Q)(PQ)(PQ)Q00100011001001011100练习练习2：构造公式：构造公式(PQ)Q真值表。真值表。2022-8-5 计算机科学与技术学院 n1.4.2 等价公式等价公式n给定给定n个个 命题命题变元变元,按合式按合式公式的形成公式的形成规则可以形成无数多个命题公式规则可以形成无数多个命题公式,但这些无穷但这些无穷尽的尽的命题公式中，有些具有相同的真值表命题公式中，有些具有相同的真

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

48、辑相等关系具有：自反性：自反性：A A；对称性：若对称性：若A B，则，则B A；传递性：若传递性：若A B且且B C，则，则A C。2022-8-5 计算机科学与技术学院 n证明公式等价的方法：证明公式等价的方法：n1.真值表法真值表法 2.等值演算法等值演算法v1.真值表法真值表法 n例例1.1.(P Q)(P Q)见真值表例题见真值表例题1.2022-8-5 计算机科学与技术学院 例例2.证明证明:PQ(PQ)(QP)PQ PQ QP PQ(PQ)(QP)0 00 00 01 11 10 01 11 12022-8-5 计算机科学与技术学院 例例2.证明证明:PQ(PQ)(QP)PQ P

49、Q QP PQ(PQ)(QP)0 00 01 11 11 11 10 01 10 00 01 10 01 10 00 01 10 00 01 11 11 11 11 11 12022-8-5 计算机科学与技术学院 例例3：判断公式判断公式 P(QR)、(PQ)R是否等价。是否等价。P Q RPQQRP(QR)(PQ)R00001001010100001101100011010111010111112022-8-5 计算机科学与技术学院 P Q RPQQRP(QR)(PQ)R00001110010111010001101101111000111101011111010001111111例例3：判

50、断公式判断公式 P(QR)、(PQ)R是否等价。是否等价。2022-8-5 计算机科学与技术学院 由真值表可知，两个公式为等价式。由真值表可知，两个公式为等价式。n2.等值演算法等值演算法(Equivalent Calculation)等值演算中使用的一条重要规则：等值演算中使用的一条重要规则：置换规则置换规则定义定义1.4.4(子公式子公式)：如果如果X是是wff A的一部分的一部分,且且X本身也是本身也是wff，则称，则称X是是A的子公式。例如的子公式。例如,P(P Q)为为Q(P(P Q)的子公式。的子公式。2022-8-5 计算机科学与技术学院定理定理1.4.1(置换定理置换定理Axi