离散数学-数理逻辑课件

离离离离 散散散散 数数数数 学学学学Discrete MathematicsDiscrete Mathematics离 散 数 学Discrete Mathematics离散数学课程地位：离散数学课程地位：计算机系核心课程计算机系核心课程信息类专业必修课程信息类专业必修课程其它类专业的重要选修课程其它类专业的重要选修课程离散数学的后继课程：离散数学的后继课程：数据结构、操作系统、数据结构、操作系统、算法分析与设计、算法分析与设计、数据库、数据库、c+c+语言语言离散数学课程地位：学习该课程的目的：学习该课程的目的：一方面一方面，它给后继课，如数据结构、编，它给后继课，如数据结构、编译系统、操作系统、数据库原理、软件工程与译系统、操作系统、数据库原理、软件工程与方法学、计算机网络、程序设计等，提供必要方法学、计算机网络、程序设计等，提供必要的数学基础；的数学基础；另一方面另一方面，通过学习离散数学，可以培养，通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实后的软、硬件学习和研究开发工作，打下坚实的数学基础。的数学基础。学习该课程的目的：教学要求：教学要求：通过该课程的学习，学生应当了解并掌通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。些基本概念、基本思想、基本方法。自学要求自学要求：通过反复看书及做课后习题，来加深对通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。自己的抽象思维和逻辑推理能力。教学要求：离散数学课程的学习方法离散数学课程的学习方法:强调：逻辑性、抽象性；强调：逻辑性、抽象性；注重：概念、方法与应用注重：概念、方法与应用离散数学的学习要领：离散数学的学习要领：概念（正确）概念（正确）必须掌握好离散数学中大量的概念必须掌握好离散数学中大量的概念 判断（准确）判断（准确）根据概念对事物的属性进行判断根据概念对事物的属性进行判断 推理（可靠）推理（可靠）根据多个判断推出一个新的判断根据多个判断推出一个新的判断离散数学课程的学习方法:离散数学的内容离散数学的内容第一部分第一部分 数理逻辑数理逻辑：命题逻辑、谓词逻辑命题逻辑、谓词逻辑第二部分第二部分 集合论集合论：集合、关系、函数集合、关系、函数 第三部分第三部分 代数系统代数系统：运算、代数系统、半群、运算、代数系统、半群、群、环、域、格、布尔代数群、环、域、格、布尔代数 第四部分第四部分 图论图论：点与边、点与边、路与圈、最短路、路与圈、最短路、EulerEuler图、图、HamiltonHamilton图、平面图、树图、平面图、树 离散数学的内容离散数学与计算机的关系离散数学与计算机的关系第一部分第一部分 数理逻辑数理逻辑 计算机是数理逻辑和电子学相结合的产物。计算机是数理逻辑和电子学相结合的产物。第二部分第二部分 集合论集合论 集合是一种重要的数据结构关系，关系数据库的理论基集合是一种重要的数据结构关系，关系数据库的理论基础函数，所有计算机语言中不可缺少的一部分。础函数，所有计算机语言中不可缺少的一部分。第三部分第三部分 代数系统代数系统 计算机编码和纠错码理论数字逻辑设计基础计算机使用计算机编码和纠错码理论数字逻辑设计基础计算机使用的各种运算。的各种运算。第四部分第四部分 图论图论 数据结构、操作系统、编译原理计算机网络原理的基础。数据结构、操作系统、编译原理计算机网络原理的基础。离散数学与计算机的关系第一部分 数理逻辑 第一章第一章 命题逻辑命题逻辑数数理理逻逻辑辑是是研研究究推推理理（即即研研究究人人类类思思维维的的形形式式结结构构和和规规律律）的的科科学学，起起源源于于1717世世纪纪，它它采采用用数数学学符号化的方法，因此也称为符号逻辑。符号化的方法，因此也称为符号逻辑。从从广广义义上上讲讲，数数理理逻逻辑辑包包括括四四论论、两两演演算算即即集集合合论论、模模型型论论、递递归归论论、证证明明论论和和命命题题逻逻辑辑演演算算、谓谓词词逻逻辑辑演演算算，但但现现在在提提到到数数理理逻逻辑辑，一一般般是是指指命命题题逻逻辑辑和和谓谓词词逻逻辑辑。本本书书也也只只研研究究这这两两个个逻辑演算。逻辑演算。第一章 命题逻辑数理逻辑是研究推理（即研究人类思维的形式结数数理理逻逻辑辑的的创创始始人人是是LeibnizLeibniz，为为了了实实现现把把推推理理变变为为演演算算的的想想法法，他他把把数数学学引引入入了了形形式式逻逻辑辑。其其后后，又又经经多多人人努努力力，逐逐渐渐使使得得数数理理逻逻辑辑成成为为一门专门的学科。一门专门的学科。上上个个世世纪纪3030年年代代以以后后，数数理理逻逻辑辑进进入入一一个个崭崭新新的的发发展展阶阶段段，逻逻辑辑学学不不仅仅与与数数学学结结合合，还还与与计计算机科学等密切关联。算机科学等密切关联。19311931年年GodelGodel不不完完全全性性定定理理的的提提出出，以以及及递递归归函函数数可可计计算算性性的的引引入入，促促使使了了19361936年年TuringTuring机机的产生，十年后，第一台电子计算机问世。的产生，十年后，第一台电子计算机问世。数理逻辑的创始人是Leibniz，为了实现把推理变为演算的想数数理理逻逻辑辑与与计计算算机机学学、控控制制论论、人人工工智智能能的的相相互互渗渗透透推推动动了了其其自自身身的的发发展展，模模糊糊逻逻辑辑、概概率率逻逻辑辑、归归纳纳逻逻辑辑、时时态态逻逻辑辑等等都都是是目目前前比比较较热热门的研究领域。门的研究领域。本本章章和和下下一一章章我我们们只只从从语语义义出出发发，对对数数理理逻逻辑辑中中的的命命题题逻逻辑辑与与谓谓词词逻逻辑辑等等作作一一简简单单的的、直直接接的、非形式化的介绍，将不涉及任何公理系统。的、非形式化的介绍，将不涉及任何公理系统。数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的第一章 命题逻辑命题逻辑1.1.命题及其表示命题及其表示命命题题：是是指指具具有有确确定定真真值值的的陈陈述述句句或或者者能能够够判判断断真真假假的陈述句。的陈述句。命命题题的的真真值值：命命题题的的判判断断结结果果。真真值值只只取取两两个个值值：真真（1 1或或T T）、假（）、假（0 0或或F F）。）。真命题：真值为真的命题。真命题：真值为真的命题。假命题：真值为假的命题。假命题：真值为假的命题。判断命题的两个步骤判断命题的两个步骤：1 1、是否为陈述句；、是否为陈述句；2 2、是否有确定的、唯一的真值、是否有确定的、唯一的真值。1.11.1节节 命题及联结词命题及联结词第一章 命题逻辑1.命题及其表示1.1节 命题及联结词 注意:感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题.陈述句中陈述句中的悖论以及判断结果不惟一确定的也不是命题。的悖论以及判断结果不惟一确定的也不是命题。例例1.1 1.1 下列句子中那些是命题？下列句子中那些是命题？（1 1）重庆是直辖市。）重庆是直辖市。（2 2）教师是人类灵魂的工程师。）教师是人类灵魂的工程师。（3 3）4 4是素数。是素数。（4 4）1+11+12 2。（5 5）21002100年的春节是晴天。年的春节是晴天。（6 6）火星上有生物。）火星上有生物。（7 7）请安静！）请安静！（8 8）今天天气多好啊）今天天气多好啊!（9 9）现在是几点钟）现在是几点钟?（1010）我正在说假话。）我正在说假话。（1111）注意:感叹句、祈使句、疑问句都不是命题.陈述句中（1 1）、（）、（2 2）、（）、（3 3）、（）、（4 4）、（）、（5 5）和（）和（6 6）都是命题。其中）都是命题。其中（1 1）、（）、（2 2）、（）、（4 4）是真命题，（）是真命题，（3 3）是假命题。）是假命题。至于（至于（5 5）和（）和（6 6）真假值是确定的，只是现在无法知道，因此它）真假值是确定的，只是现在无法知道，因此它是命题。是命题。（7 7）、（）、（8 8）、（）、（9 9）、（）、（1010）、（）、（1111）都不是命题。原因在于）都不是命题。原因在于（7 7）是祈使句，（）是祈使句，（8 8）是感叹句，（）是感叹句，（9 9）是疑问句，而（）是疑问句，而（1010）是）是悖论，即若悖论，即若(10)(10)的真值为真，即的真值为真，即“我正在说假话我正在说假话”为真，也就是为真，也就是我说的是假话，因此（我说的是假话，因此（1010）又是错误的；反之，若）又是错误的；反之，若(10)(10)的真值为的真值为假，即假，即“我正在说假话我正在说假话”为假，也就是我在说真话，因此为假，也就是我在说真话，因此 (10)(10)的真值应为真。的真值应为真。像像(10)(10)这样既不为真又不为假的陈述句不是命题，这种陈述句称这样既不为真又不为假的陈述句不是命题，这种陈述句称为悖论。凡是悖论都不是命题。（为悖论。凡是悖论都不是命题。（1111）中的）中的x x、y y 的值不确定，的值不确定，某些某些x x、y y使为真，某些使为真，某些x x、y y使为假，即的真假随使为假，即的真假随x x、y y的变化而变的变化而变化。因此，的真假无法确定，所以不是命题。化。因此，的真假无法确定，所以不是命题。（1）、（2）、（3）、（4）、（5）和（6）都是命题。其中练习练习 判断下列句子是否为命题。判断下列句子是否为命题。1.1001.100是自然数。是自然数。2.2.太阳从西方升起。太阳从西方升起。3.3.北京是中国的首都北京是中国的首都4.4.重庆是中国最大的城市重庆是中国最大的城市5.5.关门关门!6.6.你去哪里你去哪里?7.How do you do?7.How do you do?8.8.凡石头均可炼成金。凡石头均可炼成金。9.x+399.x+3910.10.皇马中国之行没有提升国家队的水平。皇马中国之行没有提升国家队的水平。练习 判断下列句子是否为命题。命题表示命题表示 在本书中，用大写的英文字母在本书中，用大写的英文字母P,Q,R,P,Q,R,，P1,P2,P3P1,P2,P3，11，22等表示命题等表示命题,用用“1(1(或者或者T T）”、“0 0（或者（或者F F）”分别表示真值的真、假。分别表示真值的真、假。如如 P P：太阳从东边升起。：太阳从东边升起。Q Q：5 5是负数。是负数。11：20082008北京举办奥运会北京举办奥运会。其真值依次为其真值依次为1 1、0 0、1 1。命题表示命题的分类命题的分类简简单单/原原子子命命题题：由由不不能能再再分分解解为为更更简简单单的的陈陈述句的陈述句构成。述句的陈述句构成。复复合合命命题题：由由简简单单命命题题通通过过联联结结词词联联结结而而成成的陈述句。的陈述句。如：如：命题命题“如果如果2 2是素数，则是素数，则3 3也是素数也是素数”通过通过“如果如果，则，则”组合而成，是复合命题，而组合而成，是复合命题，而“2 2是是素数素数”和和“3 3是素数是素数”是简单命题。是简单命题。命题的分类2.2.命题联结词命题联结词在日常语言中，一些简单的陈述句，可以通过某些联在日常语言中，一些简单的陈述句，可以通过某些联结词联结起来，组成较为复杂的语句。结词联结起来，组成较为复杂的语句。例如可以说：例如可以说：“如果下星期日是晴天，那么我就去如果下星期日是晴天，那么我就去春游。春游。”这里就是用：这里就是用：“如果如果，那么，那么”把两个把两个陈述句陈述句“下星期日是晴天下星期日是晴天”和和“我去春游我去春游”联结起来联结起来组成的一个新复合命题。组成的一个新复合命题。在日常语言中还有许多联结词，如在日常语言中还有许多联结词，如“不不”、“并且并且”、“或者或者”、“当且仅当当且仅当”，“只要只要就就”，“除非除非否则否则”等都是联结词。等都是联结词。使用它们可以将一个命题加以否定或将两个命题连接使用它们可以将一个命题加以否定或将两个命题连接起来得到新的复合命题。起来得到新的复合命题。下面介绍常用的下面介绍常用的5 5种常用的联结词。种常用的联结词。2.命题联结词在日常语言中，一些简单的陈述句，可以通过某些（1 1）否定联结词）否定联结词 设设 p p为为 命命 题题，复复 合合 命命 题题“非非 P”P”（或或“P P的的 否否定定”）称称为为P P的的否否定定式式，记记作作 P P，符号符号 称为否定联结词。称为否定联结词。运算规则运算规则：属于单目运算符：属于单目运算符（1）否定联结词（2 2）合取联结词）合取联结词设设 P,QP,Q为为 二二 命命 题题 变变 元元，复复 合合 命命 题题“P P并并 且且 Q”Q”（或或“P P与与Q”Q”）称称为为P P与与Q Q的的合合取取式式，记记 作作P QP Q，符号，符号称为合取联结词。称为合取联结词。运算规则：运算规则：属于双目运算符属于双目运算符（2）合取联结词合取运算特点合取运算特点：只只有有参参与与运运算算的的二二命命题题全全为为真真时时，运运算算结结果果才才为为真真，否否则则为为假假。自自然然语语言言中中的的表表示示“并并且且”意意思思的的联联结结词词，如如“既既又又”、“不不但但而而且且”、“虽然虽然但是但是”等都可以符号化为等都可以符号化为例如例如：将下列命题符号化：将下列命题符号化(1)(1)北京不仅是中国的首都而且是一个故都。北京不仅是中国的首都而且是一个故都。解：解：设设P P：北京是中国的首都；：北京是中国的首都；Q Q：北京是一个故都；：北京是一个故都；则原命题符号化为：则原命题符号化为：PQPQ。合取运算特点：例如：将下列命题符号化（2）小丽既聪明，又能干。小丽既聪明，又能干。解：解：设设P：小丽聪明；：小丽聪明；Q：小丽能干；：小丽能干；则原命题符号化为：则原命题符号化为：PQ。（3）小刚聪明但不努力。）小刚聪明但不努力。解：解：设设P：小刚聪明；：小刚聪明；Q：小刚努力；：小刚努力；则原命题符号化为：则原命题符号化为：PQ。（4）小刚和小明是同学。）小刚和小明是同学。解：解：这是一个原子命题，不能分解为更细的命题。这是一个原子命题，不能分解为更细的命题。（2）小丽既聪明，又能干。（3 3）析取联结词）析取联结词 设设P,QP,Q为为二二命命题题变变元元，复复合合命命题题“P P或或Q”Q”称称为为 P P与与Q Q的的析析取取式式，记记作作P P Q Q，符号，符号称为析取联结词。称为析取联结词。运算规则：运算规则：属于双目运算符。属于双目运算符。（3）析取联结词 说明说明：联结词析取：联结词析取的意义与日常所使用的意义与日常所使用的的“或或”意思并不完全相同。在日常生活意思并不完全相同。在日常生活中，中，“或或”实际上分为实际上分为“排斥或排斥或”和和“可可兼或兼或”，还有一种是描述，还有一种是描述模糊数据模糊数据。本书。本书将析取表示将析取表示“可兼或可兼或”。“排斥或排斥或”用等用等价的联结词代替。价的联结词代替。说明：联结词析取的意义与日常所使用的“或”意思并不完例如例如:(1)(1)今天晚上我在家看电视或听音乐。今天晚上我在家看电视或听音乐。解：设解：设P P：今天晚上我在家看电视；：今天晚上我在家看电视；Q Q：今天晚上我在家听音乐；：今天晚上我在家听音乐；则原命题符号化为：则原命题符号化为：P Q P Q。（可兼或）。（可兼或）（2 2）从重庆到北京的）从重庆到北京的T10T10次列车是中午次列车是中午1 1点或点或1 1点半开。点半开。解：该命题中的解：该命题中的“或或”不是不是“可兼或可兼或”，不能用联结词析，不能用联结词析取。我们用一种等价形式来代替。取。我们用一种等价形式来代替。设设P P：重庆到北京的：重庆到北京的T10T10次列车是中午次列车是中午1 1点开；点开；Q Q：重庆到北京的：重庆到北京的T10T10次列车是中午次列车是中午1 1点半开；点半开；则原命题符号化为：则原命题符号化为：(P(P Q)(Q)(PQ).PQ).例如:例如例如:（3 3）小刚是山东或山西人。）小刚是山东或山西人。解：设解：设P P：小刚是山东人；：小刚是山东人；Q Q：小刚是山西人；：小刚是山西人；则原命题符号化为：则原命题符号化为：(P(P Q)(Q)(PQ).PQ).（排斥或）（排斥或）（4 4）小刚是有）小刚是有2020或或3030岁。岁。解：这是一个原子命题，这里的解：这是一个原子命题，这里的“或或”表示一个模糊数表示一个模糊数据。据。在遇到含有在遇到含有“或或”的命题符号化时，要分清它是的命题符号化时，要分清它是“可兼或可兼或”、“排斥或排斥或”、还是表示模糊数的、还是表示模糊数的“或或”，析取联结词表示，析取联结词表示“可兼或可兼或”。例如:（4 4）单条件联结词）单条件联结词 设设P,QP,Q为二命题变元为二命题变元,复合命题复合命题“如果如果P,P,则则Q”Q”称为称为P P与与Q Q的单条件（蕴涵式），记作的单条件（蕴涵式），记作P PQ Q，并称，并称P P为单条为单条件的前件，件的前件，Q Q为单条件的后件，符号为单条件的后件，符号称为单条件结称为单条件结词。词。运算规则：运算规则：属于双目运算符属于双目运算符 与自然语言的不同：与自然语言的不同：前件与后件可以没有任何内在联系！前件与后件可以没有任何内在联系！（4）单条件联结词说明：说明：P PQ Q 的逻辑关系：的逻辑关系：Q Q 为为 P P 的必要条件的必要条件“如果如果 P P，则，则 Q”Q”的不同表述法很多：的不同表述法很多：“若若P P，就，就Q”Q”“只要只要P P，就，就Q”Q”“P “P仅当仅当Q”Q”“只有只有Q Q才才P”P”“除非除非Q,Q,才才P”P”或或“除非除非Q,Q,否则非否则非P”.P”.等等。等等。当当P P为假时，无论为假时，无论Q Q是什么，是什么，P PQ Q均为真。均为真。常出现的错误：常出现的错误：不分充分与必要条件！不分充分与必要条件！说明：PQ 的逻辑关系：Q 为 P 的必要条件例如：例如：（1 1）如果天下雨，那么我们在室内活动。如果天下雨，那么我们在室内活动。解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动；原命题符号化为：原命题符号化为：P PQ Q。（2 2）只要天下雨，我们就在室内活动。）只要天下雨，我们就在室内活动。解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动；原命题符号化为：原命题符号化为：P PQ Q。（3 3）因为天下雨，所以我们在室内活动。）因为天下雨，所以我们在室内活动。解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动；原命题符号化为：原命题符号化为：P PQ Q。在实际的语言中，很多联结词可以转化为用单条在实际的语言中，很多联结词可以转化为用单条件，但是要注意前件和后件的关系。件，但是要注意前件和后件的关系。例如：（4 4）只有天下雨，我们才在室内活动。）只有天下雨，我们才在室内活动。解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动；原命题符号化为：原命题符号化为：Q QP P。（5 5）仅当天下雨，我们在室内活动。仅当天下雨，我们在室内活动。解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动；原命题符号化为：原命题符号化为：Q QP P。（6 6）除非天下雨，否则我们不在室内活动。除非天下雨，否则我们不在室内活动。解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动；原命题符号化为：原命题符号化为：Q QP P，或者，或者 P P Q Q 。（4）只有天下雨，我们才在室内活动。（5 5）双条件联结词）双条件联结词 设设P,QP,Q为为二二命命题题变变元元，复复合合命命题题“P P当当且且仅仅当当Q”Q”称称为为P P与与Q Q的的双双条件，记作条件，记作P P Q Q，符号符号称为双条件联结词。称为双条件联结词。说明说明:(1)P:(1)PQ Q 的逻辑关系的逻辑关系:P:P与与Q Q互为充分必要条件互为充分必要条件 (2)P(2)PQ Q为真当且仅当为真当且仅当P P与与Q Q同真或同假。同真或同假。运算规则：运算规则：属于双目运算符。属于双目运算符。（5）双条件联结词例如：例如：(1)2+2(1)2+24 4 当且仅当当且仅当 3+33+36.6.解：设解：设P P：2+2 2+2 4 4；Q Q：3+3 3+3 6.6.；原命题符号化为：原命题符号化为：P P Q Q。（2 2）1+1=21+1=2当且太阳从东边升起。当且太阳从东边升起。解：设解：设P P：1+1=21+1=2；Q Q：太阳从东边升起；：太阳从东边升起；原命题符号化为原命题符号化为：P P Q Q。例如：3命题公式与真值表命题公式与真值表 将命题将命题“如果明天天晴，且我有空，我就去踢球如果明天天晴，且我有空，我就去踢球”符号符号化。化。设设P P：明天天晴；：明天天晴；Q Q：我有空；：我有空；R R：我去踢球。：我去踢球。本命题符号化为：本命题符号化为：（P P Q QR R。命题变元和联结词构成复合命题的形式化描述，为了能命题变元和联结词构成复合命题的形式化描述，为了能够更加准确的描述命题，本节主要讨论命题公式及其命够更加准确的描述命题，本节主要讨论命题公式及其命题公式的赋值。题公式的赋值。命题公式与真值表命题公式命题公式（1 1）单个命题变项是合式公式，并称为原子命题公式。）单个命题变项是合式公式，并称为原子命题公式。（2 2）若）若A A是合式公式，则是合式公式，则(A)A)也是合式公式。也是合式公式。（3 3）若若A A，B B是是合合式式公公式式，则则(AB)(AB)，(AB)(AB)，(A(AB)B)，(A(AB)B)也是合式公式。也是合式公式。（4 4）只只有有有有限限次次地地应应用用(1)(1)、（2 2）、(3)(3)形形成成的的包包含含命命题题变变元、联结词和圆括号的符号串是命题合式公式。元、联结词和圆括号的符号串是命题合式公式。命题合式公式也称为命题公式或命题形式，并简称为公式。命题合式公式也称为命题公式或命题形式，并简称为公式。命题公式例如：例如：(P(PQ)Q)，(RS)(RS)Q Q，Q QP P等均为合式公式等均为合式公式;而而PQS PQS,(P,Q(P,Q）R R，(PQ)(PQ)R R，(P(PW)Q)W)Q)等等不不是合式公式是合式公式。联联结结词词之之间间的的运运算算有有不不同同的的优优先先级级，联联结结词词运运算算的的优优先先次次序序为为:，如如果果有有括括号号，则则先先进进行行括括号内的运算。号内的运算。例如：真值表真值表 设设A A是一个命题公式，是一个命题公式，P P1 1，P P2 2，.，P Pn n是出现在是出现在A A中的所有命题变元，对这些命题变元赋予一个确定的真中的所有命题变元，对这些命题变元赋予一个确定的真值称为对命题公式的一种赋值。值称为对命题公式的一种赋值。不同的赋值，命题公式有不同真值情况。将命题公不同的赋值，命题公式有不同真值情况。将命题公式在所有的赋值下的真值情况汇成一个表，这个表就称式在所有的赋值下的真值情况汇成一个表，这个表就称为真值表。如果一个命题公式有为真值表。如果一个命题公式有n n个命题变元，每个命题个命题变元，每个命题变元有两种真值情况，则共有变元有两种真值情况，则共有n n2 2种不同的赋值情况。种不同的赋值情况。真值表 设A是一个命题公式，P1，P2，.对公式对公式A A构造真值表的具体步骤为：构造真值表的具体步骤为：(1)找找出出公公式式中中所所有有的的全全体体命命题题变变项项p1，p2，pn，列出，列出2n个赋值。个赋值。(2)按按从从高高到到低低（从从低低到到高高）的的顺顺序序写写出出公公式式的的各各个个层次。层次。(3)对对应应各各个个赋赋值值计计算算出出各各层层次次的的真真值值，直直到到最最后后计计算出公式的真值。算出公式的真值。对公式A构造真值表的具体步骤为：例如例如：求命题公式：求命题公式 (P(PQ)RQ)R的真值表。的真值表。例如：求命题公式(PQ)R的真值表。例如例如：求命题公式：求命题公式 (P(P Q)Q)R R的真值表。的真值表。例如：求命题公式(PQ)R的真值表。例如例如：求命题公式：求命题公式(P(PQ)Q)(Q Q P P)的真值表。的真值表。例如：求命题公式(PQ)(Q P)的真值表。例如例如：求命题公式：求命题公式(P(PQ)Q Q)Q 的真值表。的真值表。例如：求命题公式(PQ)Q 的真值表。例如例如：求命题公式：求命题公式P PQ Q和和(P Q)的真值表。的真值表。例如：求命题公式PQ和(P Q)的真值表。命题公式等值命题公式等值 设设A,BA,B是是两两个个命命题题公公式式，若若A A，B B构构成成的的等等价价式式A AB B为为重重言言式式，则则称称A A与与B B是是等等值值的的记记作作A A B.B.即即A A B B的充要条件是的充要条件是A AB B为重言式。为重言式。判断两个公式等值的方法判断两个公式等值的方法1 1：真值表法。：真值表法。命题公式等值 设A,B是两个命题公式，若A，B构成的等价式例如：例如：P P(Q QR)R)与与(P(PQ)Q)R R等价等价例如：P(QR)与(PQ)R等价离散数学-数理逻辑课件命题公式中有很多公式都是等价的；命题公式中有很多公式都是等价的；要记住大量的等价公式是困难的；要记住大量的等价公式是困难的；然而一些然而一些基本的、重要的基本的、重要的等价公式是应等价公式是应该掌握的。该掌握的。下面列出一些最基本的等价公式。也称下面列出一些最基本的等价公式。也称命题定律。命题定律。命题公式中有很多公式都是等价的；双重否定律双重否定律 :P PP P等幂律等幂律：P P P PP;PP;P P PP P交换律交换律:P:P Q QQ Q P;PP;P Q QQ Q P P结合律结合律:(P:(P Q)Q)R RP P(Q(Q R)R)(P (P Q)Q)R RP P(Q(Q R)R)分配律分配律:P:P(Q(Q R)R)(P(P Q)Q)(P(P R)R)P P(Q(Q R)R)(P(P Q)Q)(P(P R)R)双重否定律:PP德德摩根律摩根律 :(P(P Q)Q)P PQ Q (P(P Q)Q)P PQ Q吸收律吸收律:P:P(P(P Q)Q)P,PP,P(P(P Q)Q)P P零零 律律:P:P 1 11,P1,P 0 00 0 同一律同一律:P:P 0 0P,PP,P 1 1P P排中律排中律:P:PP P1 1矛盾律矛盾律:P:PP P0 0等值蕴涵律等值蕴涵律:P:PQ Q P P Q Q假言异位律假言异位律:P:PQ Q Q Q P P等价等值律等价等值律:P:PQ Q（P PQ Q）（Q Q P P）德摩根律:(PQ)PQ置换规则置换规则：若：若A AB B,则则(B B)(A A)。用等值公式可以进行等值演算，证明等值公式、用等值公式可以进行等值演算，证明等值公式、判定公式类型判定公式类型.下面举例说明下面举例说明.试证试证:证明：证明：置换规则：若AB,则(B)(A)。试证:证明：又如又如：验证：验证 P P(Q QR)R)(P(P Q)Q)R R 右右(P(PQ)Q)R R P P Q QR R P P(Q QR)R)P P（Q QR)R)P P(Q(QR)R)又如：验证 P(QR)(P Q)R公式的分类公式的分类 重言式重言式：给定一个命题公式，若无论对其中的命：给定一个命题公式，若无论对其中的命题变元作何种赋值，其对应的真值永为题变元作何种赋值，其对应的真值永为1 1，则称，则称该命题公式为重言式或永真式。该命题公式为重言式或永真式。永假式永假式：给定一个命题公式，若无论对其中的命：给定一个命题公式，若无论对其中的命题变元作何种赋值，其对应的真值永为题变元作何种赋值，其对应的真值永为0 0，则称，则称该命题公式为矛盾式或永假式。该命题公式为矛盾式或永假式。可满足式可满足式：给定一个命题公式，若存在一种赋值：给定一个命题公式，若存在一种赋值使得公式的真值为使得公式的真值为1 1，则称该命题公式为可满足，则称该命题公式为可满足式。式。公式的分类 重言式：给定一个命题公式，若无论对其中的命题变用等值演算法判断公式用等值演算法判断公式Q Q(P(PQ)Q)的类型。的类型。解：解：Q Q(P(PQ)Q)Q Q(P P Q)Q)Q Q(P(PQ)Q)P P(Q(QQ)Q)P P 0 0 0 0该式为矛盾式该式为矛盾式.用等值演算法判断公式Q(PQ)的类型。用等值演算法判断公式用等值演算法判断公式(P(PQ)Q)(Q QP)P)的类型。的类型。解解:(P:(PQ)Q)(Q QP)P)(P P Q)Q)(Q(QP)P)(P P Q)Q)(P P Q)Q)1 1该式为重言式该式为重言式.用等值演算法判断公式1.3 1.3 命题公式的范式与主范式命题公式的范式与主范式文字文字：命题变项及其否定统称为文字。：命题变项及其否定统称为文字。如：如：P ,Q P ,Q，Q Q等等简单析取式简单析取式：仅有有限个文字组成的析取式。：仅有有限个文字组成的析取式。如：如：P P，Q Q，P QP Q，PP QRQR简单合取式简单合取式：仅有有限个文字组成的合取式。：仅有有限个文字组成的合取式。如：如：P P，P P，PQ PQ，P P Q Q R R而而PP（QR)QR)不是简单合取不是简单合取,（P R)P R)不是简不是简单析取。单析取。1.3 命题公式的范式与主范式文字：命题变项及其否定统称为文显然，简单析取式是重言式当且仅当它含显然，简单析取式是重言式当且仅当它含有同一个变元及其该变元的否定；有同一个变元及其该变元的否定；简单合取式是矛盾式当且仅当它含有简单合取式是矛盾式当且仅当它含有同一个变元及其该变元的否定。同一个变元及其该变元的否定。命题公式是千变万化的，这给研究命题演命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命算带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，这种题公式化归为一个标准形式的问题，这种标准形式就叫标准形式就叫范式和主范式范式和主范式。显然，简单析取式是重言式当且仅当它含有同一个变元及其该变元的离散数学-数理逻辑课件将一个命题公式转化为析取范式和合取范式的将一个命题公式转化为析取范式和合取范式的主要方法是利用基本的命题等价公式如主要方法是利用基本的命题等价公式如德摩根德摩根律、分配律、蕴涵等值律、同一律、排中律和律、分配律、蕴涵等值律、同一律、排中律和吸收律吸收律等将公式转化为要求的范式。等将公式转化为要求的范式。将一个命题公式转化为析取范式和合取范式的主要方法是利用基本的由此可以看出，一个命题公式总可以通过等值由此可以看出，一个命题公式总可以通过等值变化化为与之等值的析取范式和合取范式，但变化化为与之等值的析取范式和合取范式，但是一个命题公式的析取范式和合取范式分别有是一个命题公式的析取范式和合取范式分别有多个，多个，不一定是惟一不一定是惟一的。为了能够惟一的表示的。为了能够惟一的表示一个命题公式，下面我们主要讨论命题公式的一个命题公式，下面我们主要讨论命题公式的主范式主范式。由此可以看出，一个命题公式总可以通过等值变化化为与之等值的析离散数学-数理逻辑课件离散数学-数理逻辑课件说明：说明：(1)n个个命命题题变变项项产产生生2n个个极极小小项项和和2n个个极极大大项项,2n个个极极小项（极大项）均互不等值小项（极大项）均互不等值.(2)用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值是该极小项成真赋值的十进制表示的十进制表示.用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极是该极大项成假赋值的十进制表示大项成假赋值的十进制表示,mi(Mi)称为极小项称为极小项(极大极大项项)的名称的名称.mi与与Mi的关系的关系:mi Mi,Mi mi 说明：由由p,q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项 由p,q两个命题变项形成的极小项与极大项 由由p p,q q,r r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项 由p,q,r三个命题变项形成的极小项与极大项 我们容易归纳得到我们容易归纳得到极小项极小项的如下性质：的如下性质：每个极小项有且仅有一个成真赋值，该成真赋值每个极小项有且仅有一个成真赋值，该成真赋值与该极小项的编码下标一致。与该极小项的编码下标一致。任意两个不同极小项的合取为矛盾式。任意两个不同极小项的合取为矛盾式。全体极小项的析取为重言式。全体极小项的析取为重言式。同样，我们容易得到同样，我们容易得到极大项极大项的如下性质：的如下性质：每个极大项有且仅有一个成假赋值，该成假赋值每个极大项有且仅有一个成假赋值，该成假赋值与该极大项的编码下标一致。与该极大项的编码下标一致。任意两个不同极大项的析取为重言式。任意两个不同极大项的析取为重言式。全体极大项的合析取为矛盾式。全体极大项的合析取为矛盾式。我们容易归纳得到极小项的如下性质：主析取范式与主合取范式主析取范式与主合取范式主析取范式与主合取范式定定理理 任任何何命命题题公公式式都都存存在在着着与与之之等等值值的的主主析析取范式和主合取范式取范式和主合取范式,并且是惟一的并且是惟一的.求公式的主范式的主要方法：求公式的主范式的主要方法：方法一（等值添项法）方法一（等值添项法）方法二（真值表法）方法二（真值表法）定理 任何命题公式都存在着与之等值的主析取范式和主合取范式,方法一（等值添项法）方法一（等值添项法）求主析取范式的主要步骤：求主析取范式的主要步骤：第第1 1步：将命题公式化为析取范式；步：将命题公式化为析取范式；第第2 2步：在每个不是极小项的简单合取式中用否定律增加缺少的文字；步：在每个不是极小项的简单合取式中用否定律增加缺少的文字；（注意按照一定顺序添加）（注意按照一定顺序添加）第第3 3步：用分配律展开得到新的析取范式；如果还存在简单合取式不步：用分配律展开得到新的析取范式；如果还存在简单合取式不是极小项时，重复第是极小项时，重复第2 2步；步；第第4 4步：删除重复的极小项，得到主析取范式。步：删除重复的极小项，得到主析取范式。求主合取范式的主要步骤：求主合取范式的主要步骤：第第1 1步：将命题公式化为合取范式；步：将命题公式化为合取范式；第第2 2步：在每个不是极大项的简单析取式中用否定律增加缺少的文字；步：在每个不是极大项的简单析取式中用否定律增加缺少的文字；（注意按照一定顺序添加）（注意按照一定顺序添加）第第3 3步：用分配律展开得到新的合取范式；如果还存在简单析取式不步：用分配律展开得到新的合取范式；如果还存在简单析取式不是极大项时，重复第是极大项时，重复第2 2步；步；第第4 4步：删除重复的极大项，得到主合取范式。步：删除重复的极大项，得到主合取范式。方法一（等值添项法）求主析取范式的主要步骤：离散数学-数理逻辑课件离散数学-数理逻辑课件方法二（真值表法）方法二（真值表法）定理：定理：一个命题公式的真值表中，成真赋值对应一个命题公式的真值表中，成真赋值对应的极小项的析取是该公式的主析取范式；成假赋的极小项的析取是该公式的主析取范式；成假赋值对应的极大项的合取是该公式的主合取范式值对应的极大项的合取是该公式的主合取范式。真值表法求主析取范式的主要步骤：真值表法求主析取范式的主要步骤：第第1 1步：求公式的真值表；步：求公式的真值表；第第2 2步步:找出所有的成真赋值，并形成对应的极小项的编码；找出所有的成真赋值，并形成对应的极小项的编码；第第3 3步步:将极小项的编码转化成极小项，得到主析取范式。将极小项的编码转化成极小项，得到主析取范式。真值表法求主合取范式的主要步骤：真值表法求主合取范式的主要步骤：第第1 1步：求公式的真值表；步：求公式的真值表；第第2 2步步:找出所有的成假赋值，并形成对应的极大项的编码；（注意找出所有的成假赋值，并形成对应的极大项的编码；（注意编码的转化问题）编码的转化问题）第第3 3步步:将极大项的编码转化成极大项，得到主合取范式。将极大项的编码转化成极大项，得到主合取范式。方法二（真值表法）定理：一个命题公式的真值表中，成真赋值对离散数学-数理逻辑课件离散数学-数理逻辑课件由真值表法很容易得到主范式的如下由真值表法很容易得到主范式的如下性质性质：主析取范式和主合取范式具有主析取范式和主合取范式具有互补性互补性（即它们（即它们的编码恰好构成全体赋值情况），知道主析取的编码恰好构成全体赋值情况），知道主析取范式可以得到主合取范式，知道主合取范式也范式可以得到主合取范式，知道主合取范式也可以得到主析取范式。可以得到主析取范式。重言式的主析取范式是全体极小项的析取，其重言式的主析取范式是全体极小项的析取，其主合取范式规定为主合取范式规定为1 1；矛盾式的主合取范式是；矛盾式的主合取范式是全体极大项的合取，其主析取范式规定为全体极大项的合取，其主析取范式规定为0 0。如果两个不同形式的公式等值，则它们的真值如果两个不同形式的公式等值，则它们的真值表相同，因而它们有相同的主范式。表相同，因而它们有相同的主范式。由真值表法很容易得到主范式的如下性质：离散数学-数理逻辑课件离散数学-数理逻辑课件 一个公式的主范式是惟一的（除去一个公式的主范式是惟一的（除去极小项和极小项的顺序外）。极小项和极小项的顺序外）。主范式的主范式的主要用途在于主要用途在于：规范命题公式的形式；规范命题公式的形式；求公式的成真和成假赋值；求公式的成真和成假赋值；判定公式是否等值；判定公式是否等值；实际应用。实际应用。一个公式的主范式是惟一的（除去极小项和极小项的顺离散数学-数理逻辑课件 又例又例 某公司要从赵、钱、孙、李、周五名新毕业的大学生中某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习选派一些人出国学习.选派必须满足以下条件：选派必须满足以下条件：(1)(1)若赵去，钱也去；若赵去，钱也去；(2)(2)李、周两人中至少有一人去；李、周两人中至少有一人去；(3)(3)钱、孙两人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人；(4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去；(5)(5)若周去，则赵、钱也去若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？试用主析取范式法分析该公司如何选派他们出国？解此类问题的步骤为：解此类问题的步骤为：将简单命题符号化将简单命题符号化 写出各复合命题写出各复合命题 写出由写出由中复合命题组成的合取式中复合命题组成的合取式 求求中所得公式的主析取范式中所得公式的主析取范式 又例 某公司要从赵、钱、孙、李、周五名新毕业的大学生中解解 设设p p：派赵去，：派赵去，q q：派钱去，：派钱去，r r：派孙：派孙 去，去，s s：派李去，：派李去，u u：派周去：派周去.(1)(p (1)(pq)q)(2)(s (2)(s u)u)(3)(q (3)(qr)r)(q q r)r)(4)(r (4)(r s)s)(r rs)s)(5)(u (5)(u(p(p q)q)(1)-(5)(1)-(5)构成的合取式为构成的合取式为 A=(pA=(pq)q)(s(s u)u)(q(qr)r)(q q r)r)(r (r s)s)(r rs)s)(u(u(p(p q)q)解 设p：派赵去，q：派钱去，r：派孙 A (pq r su)(p qrs u)结论：由结论：由可知，可知，A的成真赋值为的成真赋值为00110与与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）周去（孙、李不去）.A的演算过程如下的演算过程如下:A (p q)(qr)(q r)(s u)(u(p q)(r s)(rs)（交换律（交换律)B1=(p q)(qr)(q r)(p qr)(pq r)(qr)(分配分配律律)A (pqrsu)(pqB2=(s u)(u(p q)(su)(p q s)(p q u)（分配律）（分配律）B1 B2 (p qr su)(pq r su)(qr su)(p qr s)(p qr u)再令再令 B3=(r s)(rs)得得 A B1 B2 B3 (pq r su)(p qrs u)B2=(su)(u(pq)离散数学-数理逻辑课件又如又如：某公司需要从：某公司需要从A,BA,B和和C C这这3 3名骨干人员中派名骨干人员中派2 2名到国外考察，名到国外考察，由于工作需要，选派时需要满足以下条件：由于工作需要，选派时需要满足以下条件：若若A A去，则去，则C C同去；同去；若若B B去，则去，则C C不能去；不能去；若若C C不去，则不去，则A A或或B B可以去。可以去。请问如何安排？请问如何安排？又如：某公司需要从A,B和C这3名骨干人员中派2名到国外考察离散数学-数理逻辑课件4 4 联结词的完备集联结词的完备集4 联结词的完备集离散数学-数理逻辑课件离散数学-数理逻辑课件离散数学-数理逻辑课件单元素联结词构成的联结词完备集单元素联结词构成的联结词完备集 人们还可构造形式上更为简单的联结词完备集。在计算人们还可构造形式上更为简单的联结词完备集。在计算机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需要构造新联结词完备集。要构造新联结词完备集。单元素联结词构成的联结词完备集 人们还可构造形离散数学-数理逻辑课件离散数学-数理逻辑课件5 5 命题推理理论命题推理理论 人人工工智智能能的的重重要要研研究究内内容容是是知知识识的的表表示示与与推推理理，如如果果将将知知识识用用命命题题符符号号化化的的形形式式给给出出后后，如如何何按按照照一一定定的的规规则则推导出新的结论和知识是一个重要的内容。推导出新的结论和知识是一个重要的内容。本本节节将将介介绍绍一一些些经经典典的的命命题题推推理理规规则则和和推推理理方方法法。一一般般说说来来，根根据据经经验验，如如果果前前提提是是真真的的，根根据据提提供供的的推推理理规规则所推出的结论也应该是真的。则所推出的结论也应该是真的。给给出出一一些些推推理理规规则则，从从前前提提出出发发推推导导出出结结论论，这这种种结结论论称为有效结论，这种论证过程称为有效论证。称为有效结论，这种论证过程称为有效论证。在在数数理理逻逻辑辑中中，重重点点研研究究的的是是推推理理的的有有效效性性，而而不不是是通通常所说的正确性。常所说的正确性。5 命题推理理论 人工智能的重要研究内容是知识的表示与推理，推推理理是是从从前前提提推推出出结结论论的的思思维维过过程程，前前提提是是指指已已知知的的命命题题公公式式，结结论论是是从从前前提提出出发发应应用用推推理理规规则则推推出出的的命命题题公公式式，前前提提可可多多个个，由由前前提提A A1 1，A A2 2，A Ak k推推出出结结论论B B的的严严格格定定义义如如下：下：有有效效结结论论（1 1）：若若(A(A1 1A A2 2A Ak k)B B 为为重重言言式式，则则称称A A1 1，A A2 2，A Ak k，推推结结论论B B的的结结论论正正确确，B B是是A A1 1，A A2 2，A Ak k，的的逻逻辑辑结结论论或或有有效效结结论论，称称(A(A1 1A A2 2A Ak k)B B 为为由由前前提提A A1 1，A A2 2，A Ak k推结论推结论B B的推理的形式结构。的推理的形式结构。推理是从前提推出结论的思维过程，前提是指已知的命题公式，离散数学-数理逻辑课件对于任一组赋值，前提和结论的取值有以下四种对于任一组赋值，前提和结论的取值有以下四种情况：情况：A1 A1，A2A2，AkAk为为0 0，B B为为0 0。A1 A1，A2A2，AkAk为为0 0，B B为为1 1。A1 A1，A2A2，AkAk为为1 1，B B为为0 0。A1 A1，A2A2，AkAk为为1 1，B B为为1 1。对于任一组赋值，前提和结论的取值有以下四种情况：推理的另一种形式：推理的另一种形式：命题公式命题公式A A1 1，A A2 2，A Ak k推推B B的推理正确当且仅当的推理正确当且仅当 (A(A1 1 A A2 2 A Ak k)B B 为重言式。为重言式。于是推理的一般形式可转化为：于是推理的一般形式可转化为：(A(A1 1 A A2 2 A Ak k)B B推理正确转化为：推理正确转化为：A A1 1 A A2 2 A Ak k B B推理的另一种形式：证明证明(A(A1 1 A A2 2 A Ak k)B B的方法有：的方法有：1 1、真真值值表表法法；2 2、等等值值演演算算法法；3 3、主析取范式法。主析取范式法。但但是是，在在前前提提和和结结论论中中，若若命命题题变变元元的的数数目目较较大大时时，使使用用真真值值表表的的方方法法、等等值值演演算算、等等值值添添项项和和主主范范式式的的方方法法都都显显得得很很麻麻烦烦。此此时时可可以以采采用用推理的方法进行证明。推理的方法进行证明。因因此此，接接下下来来引引入入构构造造论论证证的的方方法法，这这种种方方法需要一些等值定律和推理规则。法需要一些等值定律和推理规则。证明(A1 A2 Ak)B的方法有：等值定律等值定律离散数学-数理逻辑课件推理规则推理规则推理规则下面举例说明推理定律和推理规则的应用下面举例说明推理定律和推理规则的应用下面举例说明推理定律和推理规则的应用离散数学-数理逻辑课件 判定推理是否有效：判定推理是否有效：如如果果今今天天是是星星期期六六，我我们们就就要要到到西西湖湖或或大大清清谷谷去去玩玩。如如果果西西湖湖游游人人太太多多，我我们们就就不不到到西西湖湖去去玩玩。今今天天是是星星期期六六。西西湖湖游游人人太太多。所以我们到大清谷玩。多。所以我们到大清谷玩。解解：首先将命题符号化：首先将命题符号化：p:p:今天是星期六。今天是星期六。q:q:我们到西湖去玩。我们到西湖去玩。r:r:我们到大清谷去玩。我们到大清谷去玩。s:s:西湖游人多。西湖游人多。前提前提：p p(q(q r r),s),s q,p,sq,p,s结论结论：r r证明证明：s s q q 前提引入前提引入 s s 前提引入前提引入 q q 假言推理假言推理 p p 前提引入前提引入 p p(q(q r)r)前提引入前提引入 q q r r 假言推理假言推理 r r 析取三段论析取三段论 判定推理是否有效：以上两个例子主要是直接证明的方法，下面讨论以上两个例子主要是直接证明的方法，下面讨论两种间接证明方法。两种间接证明方法。（一）附加前提法（一）附加前提法（CPCP规则法）规则法）欲证明欲证明(A1(A1 A2 A2 Ak Ak)(A(A B)B)，只需证明，只需证明 (A1(A1 A2 A2 Ak Ak A)A)B B 即可，因为即可，因为:(A1(A1 A2 A2 Ak Ak)(A(A B)B)(A1(A1 A2 A2 Ak Ak)(A(A B)B)(A1(A1 A2 A2 Ak Ak)(A B)A B)(A1 A1 A2 A2 Ak Ak)(A B)A B)A1 A1 A2 A2 Ak Ak A B A B(A1 A1 A2 A2 Ak Ak A)B A)B (A1(A1 A2 A2 Ak Ak A)A)B B (A1(A1 A2 A2 Ak Ak A)A)B B 注注:A:A B B AB AB (A(AB)B)A A B