《离散数学-ch1.ppt》由会员分享，可在线阅读，更多相关《离散数学-ch1.ppt（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1/73离散数学离散数学 I I肖明军Web:http:/ 2/73引言引言课程简介课程简介离离散散数数学学是是现现代代数数学学的的一一个个重重要要分分支支，是是计计算算机机科科学学中中基基础础理理论论的的核核心心课课程程，它它研研究究的的对对象象是是有有限限个个或或可可数数的的离离散散量量。充充分分描描述述了了计计算算机机科科学学离散性的特征。离散性的特征。离散数学是传统的离散数学是传统的逻辑学逻辑学、集合论集合论、数论数论基础、基础、算法设计、组合分析、离散概率、关系理论、算法设计、组合分析、离散概率、关系理论、图图论论与与树树、抽象代数抽象代数、布尔代数布尔代数、计算模型等汇集、计算模型
2、等汇集起来的一门综合学科。离散数学的应用遍及现代起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。科学技术的诸多领域。离离散散数数学学是是随随着着计计算算机机科科学学的的发发展展而而逐逐步步建建立立起来的一门新兴的工具性学科，形成于七十年代。起来的一门新兴的工具性学科，形成于七十年代。3/73引言引言课程意义课程意义离离散散数数学学是是计计算算机机科科学学的的数数学学基基础础，其其基基本本概概念念、理理论论、方方法法大大量量地地应应用用在在数数字字电电路路、编编译译原原理理、数数据据结结构构、操操作作系系统统、数数据据库库系系统统、算算法法设设计计、人人工工智智能能、计计算算机机网
3、网络络等等专专业业课课程程中中，是是这这些些课课程程的的基基础课程。础课程。离离散散数数学学学学习习十十分分有有益益于于概概括括抽抽象象能能力力、逻逻辑辑思思维维能能力力、归归纳纳构构造造能能力力的的提提高高，能能够够培培养养提提高高学学生生的数学思维能力和对实际问题的求解能力。的数学思维能力和对实际问题的求解能力。教学内容教学内容数理逻辑数理逻辑、集合论集合论、代数结构代数结构、图论、图论4/73引言引言教学内容教学内容第一部分第一部分 数理逻辑数理逻辑第一章第一章 命题逻辑命题逻辑第二章第二章 谓词逻辑谓词逻辑第二部分第二部分 集合论集合论第三章第三章 集合代数集合代数第四章第四章 二元关
4、系二元关系5/73引言引言教学内容教学内容第二部分第二部分 集合论集合论第五章第五章 函数函数第六章第六章 集合的基数集合的基数第三部分第三部分 代数结构代数结构第七章第七章 代数系统代数系统第八章第八章 群论群论6/73引言引言教学内容教学内容第三部分第三部分 代数结构代数结构第九章第九章 环与域环与域第十章第十章 格与布尔代数格与布尔代数7/73第一部分第一部分 数理逻辑数理逻辑逻辑学逻辑学是一门研究思维形式和规律的科学。分为辩证逻是一门研究思维形式和规律的科学。分为辩证逻辑和形式逻辑两种。思维的形式结构包括了辑和形式逻辑两种。思维的形式结构包括了概念概念 判断判断和和推理推理之间的结构和
5、联系，其中之间的结构和联系，其中概念概念是思是思维的基本单位，通过概念对事物是否具有某种属维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，就是性进行肯定或否定的回答，就是判断判断。由一个或。由一个或几个判断推出另一判断的思维形式就是几个判断推出另一判断的思维形式就是推理推理。数理逻辑数理逻辑用数学方法研究推理的规律称为数理逻辑。所谓用数学方法研究推理的规律称为数理逻辑。所谓数学方法就是引用一套符号体系的方法，所以数数学方法就是引用一套符号体系的方法，所以数理逻辑又称作符号逻辑。理逻辑又称作符号逻辑。8/73第一部分第一部分 数理逻辑数理逻辑现代数理逻辑现代数理逻辑逻辑演算、逻
6、辑演绎、模型论、证明论、逻辑演算、逻辑演绎、模型论、证明论、递归函数论、公理化集合论等。递归函数论、公理化集合论等。我们要介绍的是数理逻辑中最基本的内容：我们要介绍的是数理逻辑中最基本的内容：命题逻辑和谓词逻辑。即一般所谓的古典命题逻辑和谓词逻辑。即一般所谓的古典逻辑。逻辑。德国数学家莱布尼茨德国数学家莱布尼茨Leibniz（现代逻辑的（现代逻辑的首席创始人）；布尔首席创始人）；布尔Boole（奠基人，逻辑（奠基人，逻辑的数学分析）；弗雷格（数论的基础）的数学分析）；弗雷格（数论的基础）9/73第一章第一章 命题逻辑命题逻辑 命题逻辑也称命题演算或语句逻辑。它研究命题逻辑也称命题演算或语句逻辑
7、。它研究以以“命题命题”为基本单位构成的前提和结论之为基本单位构成的前提和结论之间的可推导关系，研究什么是命题？如何表间的可推导关系，研究什么是命题？如何表示命题？怎样由一组前提推导一些结论。示命题？怎样由一组前提推导一些结论。概念概念判断判断推理推理10/731.1 命题与命题联结词命题与命题联结词1.1.1命题命题定义定义1.1：具有：具有确切真值确切真值的的陈述句陈述句(或断言或断言)称称为命题为命题(Proposition)。命题的取值称为真值。真值只有命题的取值称为真值。真值只有“真真”和和“假假”两种，分别用两种，分别用“T”或或“1”和和“F”或或“0”表示。表示。注意：命题的真
8、值非真即假，只有两种取值，注意：命题的真值非真即假，只有两种取值，这样的系统为二值逻辑系统。这样的系统为二值逻辑系统。11/731.1 命题与命题联结词命题与命题联结词例例1-1：命题示例。：命题示例。(a):今天下雪今天下雪(b):3+3=6(c):2是偶数而是偶数而3是奇数是奇数(d):陈胜起义那天，杭州下雨陈胜起义那天，杭州下雨(e):较大的偶数都可表为两个质数之和较大的偶数都可表为两个质数之和(f):x+y4(g):真好啊真好啊!(h):x=3(i):你去哪里？你去哪里？(j):我正在说谎。我正在说谎。注意：注意：由定义知，一切没有判断内容的句子由定义知，一切没有判断内容的句子如命令，
9、感叹句，疑问句，祈使句，二义性如命令，感叹句，疑问句，祈使句，二义性的陈述句等都不能作为命题。的陈述句等都不能作为命题。12/731.1 命题与命题联结词命题与命题联结词例例1-2：下列句子哪些是命题，判断命：下列句子哪些是命题，判断命题的真假。题的真假。(1):2是素数是素数(2):北京是中国的首都北京是中国的首都(3):这个语句是假的这个语句是假的(4):x+y0(5):我喜欢踢足球我喜欢踢足球(6):地球外的星球上也有人地球外的星球上也有人(7):明年国庆节是晴天明年国庆节是晴天(8):把门关上把门关上(9):你要出去吗？你要出去吗？(10):今天天气真好啊！今天天气真好啊！13/73注
10、意注意命题一定是通过陈述句来表达；反之，并非一切命题一定是通过陈述句来表达；反之，并非一切的陈述句都一定是命题。的陈述句都一定是命题。命题的真值有时可明确给出，有时还需要依靠环命题的真值有时可明确给出，有时还需要依靠环境条件，实际情况，时间才能确定其真值。但其境条件，实际情况，时间才能确定其真值。但其真值一定是唯一确定的。真值一定是唯一确定的。1.1 命题与命题联结词命题与命题联结词14/731.1 命题与命题联结词命题与命题联结词命题可分为两种类型：命题可分为两种类型：简简单单命命题题：若若一一个个命命题题已已不不能能分分解解成成更更简简单单的的命命题题，则则该该命命题题叫叫原原子子命命题题
11、或或本本原原命命题题或或简简单单命命题题（Simple Proposition）复复合合命命题题（Compound Proposition）：可可以以分分解解为为简简单单命命题题的的命命题题，而而且且这这些些简简单单命命题题之之间间是是通通过过关关联联词词（如如“或或者者”,“并并且且”,“不不”，“如如果果 则则”,“当当且且仅仅当当”等等）和和标标点点符符号号复复合合而构成一个复合命题。而构成一个复合命题。例，合肥是安徽的省会当且仅当鸟会飞。例，合肥是安徽的省会当且仅当鸟会飞。注意：注意：命题通常用大写英文字母（可带下标）来表示。命题通常用大写英文字母（可带下标）来表示。15/731.1.
12、2 命题联结词命题联结词命命题题通通常常可可以以通通过过一一些些联联结结词词复复合合而而构构成成新新的的命命题题，这这些些联联结结词词被被称称为为逻逻辑辑联联结结词词。用用数数学学方方法法研研究究命命题题之之间间的的逻逻辑辑关关系系时时（也也就就是是在在命命题题演演算算中中），这这些些联联结结词词可可以以看看作作是是运运算算符符，因因此此也也叫叫作逻辑运算符。作逻辑运算符。常用的联结词有以下常用的联结词有以下5个：个：定定义义1.2：设设P是是任任一一命命题题，复复合合命命题题“非非P”（或或“P的的否否定定”）称称为为P的的否否定定式式（Negation），记记作作P，“”为否定联结词。为否
13、定联结词。P为真当且仅当为真当且仅当P为假。为假。如：如：P：2是素数，则是素数，则P：2不是素数。不是素数。1.1 命题与命题联结词命题与命题联结词16/731.1 命题与命题联结词命题与命题联结词定定义义1.3：设设P Q是是任任意意两两个个命命题题，复复合合命命题题“P并并且且 Q”（或或“P和和 Q”）称称 为为 P与与 Q的的 合合 取取 式式（Conjunction），记记作作P Q，“”为为合合取取联联结词。结词。P Q为真当且仅当为真当且仅当P，Q同为真。同为真。例例，P：2是是素素数数，Q：2是是偶偶数数。则则P Q：2是是素素数并且是偶数。数并且是偶数。17/731.1 命
14、题与命题联结词命题与命题联结词定定义义1.4：设设P Q是是任任意意两两个个命命题题，复复合合命命题题“P或或Q”称称为为P与与Q的的析析取取式式（Disjunction），记记作作P Q，“”为为析析取取联联结结词词。P Q为为真真当当且且仅仅当当P，Q至少一个为真。至少一个为真。例例，P：2是是素素数数，Q：2是是奇奇数数。则则P Q：2是是素素数或是奇数。数或是奇数。18/731.1 命题与命题联结词命题与命题联结词定定义义1.5：设设P Q是是任任意意两两个个命命题题，复复合合命命题题“如如果果P则则Q”称称为为P与与Q的的蕴蕴含含式式（Implication），记记作作PQ，“”为为
15、 蕴蕴含含联联结结词词，P称称为为蕴蕴含含式式的的前前提提，假假设设或或前前件件，而而Q称称为为结结论论式式后后件件。PQ为假当且仅当为假当且仅当P为真为真Q为假。为假。例例，P：G是是正正方方形形，Q：G的的四四边边相相等等，则则PQ：如果：如果G是正方形，则是正方形，则G的四边相等。的四边相等。蕴含式蕴含式PQ可以用多种方式陈述：可以用多种方式陈述：“若若P，则则Q”;“P是是Q的的充充分分条条件件”;“Q是是P的的必必要要条件条件”;“Q每当每当P”;“P仅当仅当Q”等。等。19/731.1 命题与命题联结词命题与命题联结词给给定定命命题题PQ，我我们们把把QP，PQ，QP分分别别叫叫作
16、作命命题题PQ的的逆逆命命题题，反反命命题题和和逆逆反命题。反命题。定定义义1.6：设设P，Q是是任任意意两两个个命命题题，复复合合命命题题“P当当且且仅仅当当Q”称称为为P与与Q的的等等价价式式(Equivalence)，记记作作PQ，“”为为等等价价联联结结词词。PQ为为真真当当且仅当且仅当P，Q同为真假。同为真假。例例如如，P：合合肥肥是是安安徽徽省省会会，Q：鸟鸟会会飞飞，则则PQ：合肥是安徽省会当且仅当鸟会飞。：合肥是安徽省会当且仅当鸟会飞。如如果果PQ是是真真，则则PQ和和QP是是真真，反反之之亦亦然然，因因此此PQ也也读读作作“P是是Q的的充充要要条条件件”或或“P当当且且仅当仅
17、当Q”。20/731.1 命题与命题联结词命题与命题联结词五个联结词的真值表五个联结词的真值表联结词联结词记号记号表达式表达式读法读法真值结果真值结果否定否定P非非PP为为真真当当且且仅仅当当P为为假假合取合取P QP且且QP Q为为真真当当且且仅仅当当P，Q同为真同为真析取析取P QP或或QP Q为为真真当当且且仅仅当当P，Q至少一个为真至少一个为真蕴含蕴含PQ若若P则则QPQ为为假假当当且且仅仅当当P为真为真Q为假为假等价等价PQP当且仅当当且仅当QPQ为为真真当当且且仅仅当当P，Q同为真假同为真假21/731.1 命题与命题联结词命题与命题联结词一般约定：一般约定：a)：运运算算符符(联
18、联结结词词)结结合合力力强强弱弱顺顺序序为为：，；凡符合此顺序的，括号可省略。；凡符合此顺序的，括号可省略。b)：相相同同的的运运算算符符，从从左左到到右右次次序序计计算算时时，括括号号可省去。可省去。c)：最外层括号可省。：最外层括号可省。如，如，(P Q)R)(R P)Q)(P QR)R PQ22/73例例1.3：符号化下列命题。：符号化下列命题。a)：他既有理论知识又有实践经验：他既有理论知识又有实践经验b)：i.如果明天不是雨夹雪则我去学校如果明天不是雨夹雪则我去学校 ii.如果明天不下雨并且不下雪，则我去学校如果明天不下雨并且不下雪，则我去学校 iii.如果明天下雨或下雪则我不去学校
19、如果明天下雨或下雪则我不去学校 iv.明天我将风雨无阻一定去学校明天我将风雨无阻一定去学校 v.当且仅当明天不下雪并且不下雨时我才去当且仅当明天不下雪并且不下雨时我才去学校学校1.1 命题与命题联结词命题与命题联结词23/731.1 命题与命题联结词命题与命题联结词c)：说说小小学学生生编编不不了了程程序序，或或说说小小学学生生用用不不了了个个人计算机，那是不对的。人计算机，那是不对的。d)：若若不不是是他他生生病病了了或或出出差差了了，我我是是不不会会同同意意他他不参加学习的。不参加学习的。e)：如如果果我我上上街街了了，我我就就去去书书店店看看看看，除除非非我我很很累。累。24/731.1
20、 命题与命题联结词命题与命题联结词注意：注意：(1)是是自自然然语语言言中中的的“非非”“不不”和和“没没有有”等等的逻辑抽象的逻辑抽象(2)是是自自然然语语言言中中的的“并并且且”“既既 又又”“且且”“和和”等的逻辑抽象等的逻辑抽象(3)是是自自然然语语言言中中的的“或或”和和“或或者者”等等的的逻逻辑辑抽抽象象；但但“或或”有有“可可兼兼或或”“不不可可兼兼或或”“近似或近似或”三种三种(4)PQ是是自自然然语语言言中中的的“只只要要P，就就Q”“因因为为P，所以所以Q”“P仅当仅当Q”等的逻辑抽象等的逻辑抽象25/73(5)是是自自然然语语言言中中的的“充充分分必必要要条条件件”和和“
21、当当且且仅当仅当”等的逻辑抽象等的逻辑抽象(6)联联结结词词连连接接的的是是两两个个命命题题真真值值之之间间的的联联结结，而而不不是是命命题题内内容容之之间间的的连连接接，因因此此复复合合命命题题 的的真真值值只只取决于构成他们的各原子命题的真取决于构成他们的各原子命题的真 值值(7)，具有对称性，而具有对称性，而，没有没有(8)，与与计计算算机机中中的的与与门门，或或门门，非非门门电电路路是相对应的是相对应的看看P6-7 例例1.4-1.5，P9 例例1.71.1 命题与命题联结词命题与命题联结词26/731.2.1：命题公式：命题公式就就像像在在代代数数学学里里引引入入变变量量一一样样，为
22、为了了更更广广泛泛的的应应用用命命题题演演算算，在在数数理理逻逻辑辑中中也也引引入入了了命命题题变变量量。使使得得在在研研究究时时，只只需需考考虑虑命命题题的的真真值值，而而不不知知晓晓命命题题的的具体含义。具体含义。定定 义义 1.7：一一 个个 特特 定定 的的 命命 题题 是是 一一 个个 常常 值值 命命 题题(Constant Proposition)，它它 不不 是是 具具 有有 值值“T”(“1”)，就就是是具具有有值值“F”(“0”)。而而一一个个任任意意的的没没有有赋赋予予具具体体内内容容的的原原子子命命题题是是一一个个变变量量命命题题，常常称称它它为为命命题题变变量量(或或
23、命命题题变变元元、命命题题变变项项)(Proposition Variable)。命命题题变变量量无无具具体体的的真真值值，它的值域是集合它的值域是集合T，F(或或1，0)。1.2 公式的解释与真值表公式的解释与真值表27/73原原子子命命题题在在不不指指派派真真值值时时称称为为命命题题变变元元，而而复复合合命命题题由由原原子子命命题题和和联联结结词词构构成成，可可以以看看作作是是命命题题变变元元的的函函数数，且且该该函函数数的的值值仍仍为为“真真”或或“假假”，可可以以称称为为真真值值函函数数（True Value Function）或或命命题题公公式式。但但不不是是说说原原子子命命题题和和
24、联联结结词词的的一一个个随随便便的的组组合合都都可可以以为为命命题题公公式式，我我们们用用递递归归的的方方法法来来定定义义命命题题公公式式。1.2 公式的解释与真值表公式的解释与真值表28/731.2 公式的解释与真值表公式的解释与真值表定义定义1.8：命题公式：命题公式(1).命题变元本身是一个公式；命题变元本身是一个公式；(2).如果如果P是公式，则是公式，则P也是公式；也是公式；(3).如如果果P，Q是是公公式式，则则(PQ)PQ PQ PQ也是公式；也是公式；(4).命命题题公公式式(Prepositional Formula)是是仅仅由由有有限限步步使使用用规规则则(1)(3)后后产
25、产生生的的结结果果。公公式式常常用用符符号号G H等表示。等表示。例例，(PQ)，(P(P Q)，(PQ)(R Q)(P R)是命题公式是命题公式(P Q)Q)，(P Q，(PQ(R，PQ 不是命题公式不是命题公式29/73注意：注意：如如果果G是是含含有有n个个命命题题变变元元 P1,P2,Pn的的公公式式，通常记为通常记为G（P1,Pn）或简记为）或简记为G。原原子子命命题题变变元元是是最最简简单单的的（合合式式）公公式式，也也叫叫原原子（合式）公式。子（合式）公式。合合成成公公式式没没有有真真值值，只只有有对对其其变变元元进进行行指指派派后后才才有真值。有真值。合成公式无限多。合成公式无
26、限多。1.2 公式的解释与真值表公式的解释与真值表30/731.2 公式的解释与真值表公式的解释与真值表合式公式的层次：合式公式的层次：(1).若若公公式式A是是一一单单个个的的命命题题变变项项，则则称称A为为0层层公公式；式；(2).称称A是是n+1(n0)层公式只需满足下列情况只一：层公式只需满足下列情况只一：a).A=B，B是是n层公式；层公式；b).A=BC，其其中中B，C分分别别为为i层层和和j层层公公式式,且且n=max(i,j)；c).A=BC，其中，其中B，C的层次同的层次同b；d).A=BC，其中，其中B，C的层次同的层次同b；e).A=BC，其中，其中B，C的层次同的层次同
27、b；从从图图论论的的观观点点来来看看每每个个多多层层公公式式可可以以用用一一个个“树树”来表示。来表示。31/731.2 公式的解释与真值表公式的解释与真值表1.2.2：公式的解释与真值表：公式的解释与真值表公公式式本本身身没没有有真真值值，只只有有在在对对其其所所有有命命题题变变元元指指定真值后才变成一个具有真值的命题。定真值后才变成一个具有真值的命题。定定义义1.9：设设命命题题变变元元P1,P2,Pn是是出出现现在在公公式式G中中的的所所有有命命题题变变元元，指指定定P1,P2,Pn一一组组真真值值，则则这这组组这这组组称称为为G的的一一个个解解释释(Explanation),并并记记作
28、作I。一一般般来来说说，若若有有n个个命命题题变变元元，则则应应有有2n个个不不同同的的解释。解释。定定义义1.10：公公式式G在在其其所所有有可可能能的的解解释释下下所所取取真真值值的表，称作的表，称作G的真值表的真值表(Truth)。32/731.2 公式的解释与真值表公式的解释与真值表例例1.4：5个联结词的真值表个联结词的真值表(T：1，F：0)PQPPQP Q PQ PQ001001101101101000100110111133/731.2 公式的解释与真值表公式的解释与真值表例例1.5：设设公公式式G=(PQ)R)(PQ)，其其中中P，Q，R是是G的命题变元，则其真值表如下：的命
29、题变元，则其真值表如下：PQRPQ(PQ)R PQ(PQ)R)(PQ)0000111001011101001000110100100010010101001101010111110034/731.2 公式的解释与真值表公式的解释与真值表1.2.3：一些特殊的公式：一些特殊的公式例例1.6：考虑：考虑：G1=(PQ)P；G2=(PQ)P；G3=(P Q)(PQ)公公式式G1对对所所有有可可能能的的解解释释都都具具有有“真真”值值，G3对对所所有有解解释释都都具具有有“假假”值值，公公式式G2则则具具有有“真真”和和“假假”值。值。35/731.2 公式的解释与真值表公式的解释与真值表1.重言式：
30、重言式：定义定义1.11：(1).公公式式G称称为为永永真真公公式式（重重言言式式），如如果果在在它它的所有解释下都为的所有解释下都为“真真”；(2).公式公式G称为可满足的，如果它不是永假的；称为可满足的，如果它不是永假的；(3).公公式式G称称为为永永假假公公式式（矛矛盾盾式式）,如如果果在在它它的的所所有有解解释释下下都都为为“假假”;有有时时也也称称永永假假公公式式为为不不可可满足公式。满足公式。注意：注意：(1).重重言言式式的的否否定定是是矛矛盾盾式式，矛矛盾盾式式的的否否定定是是重重言式，所以研究其一就可以了；言式，所以研究其一就可以了；36/731.2 公式的解释与真值表公式的
31、解释与真值表(2).重重言言式式的的合合取取，析析取取，蕴蕴含含，等等值值等等都是重言式；都是重言式；(3).重重言言式式中中有有许许多多非非常常有有用用的的恒恒等等式式叫叫永真蕴含式。永真蕴含式。对对任任意意的的公公式式，判判定定其其是是否否为为永永真真公公式式，永永假假公公式式，可可满满足足公公式式的的问问题题称称为为给给定定公公式式的的判判定定问问题题。由由于于一一个个命命题题公公式式的的解解释释的的数数目目是是有有穷穷的的，所所以以命命题题逻逻辑辑的的判判定定问问题题是是可可解解的的，即即命命题题的的永永真真，永永假假性性是是可可判判定定的的。其其判定方法有判定方法有真值表法真值表法和
32、和公式推演法公式推演法。37/731.2 公式的解释与真值表公式的解释与真值表例例1.7：判定公式：判定公式：(1).(PQ)(PQ);(2).(PQ)P)Q；(3).P(Q R)。2.恒等式：恒等式：定定义义1.12：公公式式G，H，如如果果在在其其任任意意解解释释下下，其其真真值值相相同同，则则称称G是是H的的等等价价式式(Equivalent)或或称称G恒等于恒等于H，记作，记作GH。38/731.2 公式的解释与真值表公式的解释与真值表定定理理1.1：对对于于公公式式G和和H，GH的的充充分分必必要要条条件件是公式是公式G H是重言式。是重言式。证明：证明：必必要要性性：假假定定GH，
33、则则G和和H在在其其任任意意解解释释I下下，或或同同为为真真或或同同为为假假，由由“”的的意意义义知知，G H在任意解释在任意解释I下，其真值为真，即下，其真值为真，即G H为重言式；为重言式；充充分分性性：假假设设公公式式G H是是重重言言式式，I是是它它的的任任意意解解释释，在在I下下，G H为为真真，因因此此，G，H或或同同为为真真或同为假，由于或同为假，由于I的任意性，故有的任意性，故有GH。39/731.2 公式的解释与真值表公式的解释与真值表注意注意与与不同：不同：(1).：逻辑等价关系，：逻辑等价关系，G H不是命题公式；不是命题公式；(2).：逻辑联结词，：逻辑联结词，G H是
34、命题公式；是命题公式；(3).计计算算机机不不能能判判断断G，H是是否否逻逻辑辑等等价价，而而可可计计算算G H是否为重言式。是否为重言式。40/731.2 公式的解释与真值表公式的解释与真值表常用逻辑恒等式（常用逻辑恒等式（P，Q，R为任意命题，为任意命题，T为真命为真命题，题，F为假命题）：为假命题）：E1PP双否定双否定E2PPP的幂等律的幂等律E3PPP的幂等律的幂等律E4PQQP的交换律的交换律E5PQQP的交换律的交换律E6(PQ)RP(QR)的结合律的结合律E7(PQ)RP(QR)的结合律的结合律E8P(QR)PQPR在在上的分配律上的分配律E9P(QR)(PQ)(PR)在在上的
35、分配律上的分配律E10(PQ)PQ德德摩根定律摩根定律E11(PQ)PQ41/731.2 公式的解释与真值表公式的解释与真值表E12P(PQ)P吸收律吸收律E13P(PQ)PE14(PQ)PQ蕴含等值式蕴含等值式E15(PQ)(PQ)(QP)等价等值式等价等值式E16PTT零律零律E17PFFE18PFP同一律同一律E19PTPE20PPT排中律排中律E21PPF矛盾律矛盾律E22(PQR)(P(QR)输出律输出律E23(PQ)(PQ)P归谬律归谬律E24(PQ)QP逆反律逆反律42/731.2 公式的解释与真值表公式的解释与真值表3.永真蕴含式：永真蕴含式：定定义义1.13：若若AB是是一一
36、永永真真式式，那那么么称称为为永永真真蕴蕴含式，记为含式，记为AB，读作，读作A永真蕴含永真蕴含B常用的永真蕴含式常用的永真蕴含式I1P=PQI2PQ=PI3P(PQ)=QI4(PQ)Q=PI5P(PQ)=QI6(PQ)(QR)=(PR)I7(PQ)=(QR)(PR)I8(PQ)(RS)=(PRQS)I9(PQ)(RS)=(PR)43/731.2 公式的解释与真值表公式的解释与真值表4.恒等式和永真蕴含式的两个性质：恒等式和永真蕴含式的两个性质：(1).若若AB，BC，则则AC；若若A=B，B=C，则则A=C.(即即逻逻辑辑恒恒等等和和永永真真蕴蕴含含都都是是可可传传递的递的)证证明明：AB，
37、BC，即即AB，BC为为重重言言式式，对对任任意意的的解解释释I，A和和B，B和和C的的真真值值相相同同，则则A和和C的真值相同。的真值相同。A C为重言式，即为重言式，即AC；A=B，B=C，即，即AB，BC为真；为真；(AB)(BC)为为真真，由由公公式式I6：AC为为重重言言式，即式，即A=C。44/731.2 公式的解释与真值表公式的解释与真值表(2).若若A=B，A=C，则，则A=BC.证证明明：A为为真真时时，B，C都都为为真真，则则BC也也为为真真，即即ABC为为真真；A为为假假时时，则则不不管管BC是是真真还还是假时，是假时，ABC均为真，因此均为真，因此A=BC。45/731
38、.2 公式的解释与真值表公式的解释与真值表1.2.4：代入规则和替换规则：代入规则和替换规则当当一一个个公公式式是是永永真真式式或或永永假假式式时时，其其公公式式的的真真值值完完全全跟跟随随其其命命题题变变元元的的真真值值的的变变化化而而变变化化，因因此此，当当用用其其他他公公式式来来取取代代公公式式中中的的命命题题变变元元时时，不不会会改变公式的永真性和永假性改变公式的永真性和永假性定定理理1.2(代代入入定定理理)：设设G(P1,Pn)是是一一个个命命题题公公式式，其其中中P1,Pn是是命命题题变变元元，G1(P1,Pn),Gn(P1,Pn)为为任任意意的的命命题题公公式式，此此时时若若G
39、是是永永真真公公式式或或永永假假公公式式，则则用用G1取取代代P1,Gn取取代代Pn后后，得得到到的的新新的的命命题题公公式式G(G1,Gn)G(P1,Pn)也是一个永真公式或永假公式。也是一个永真公式或永假公式。46/731.2 公式的解释与真值表公式的解释与真值表例例1.8：设设G(P,Q)=(PQ)P；用；用H(P,Q)=(P Q)；S(P,Q)=(P Q)代入代入G验证代入定理。验证代入定理。定定理理1.3(替替换换定定理理)：设设G1是是G的的子子公公式式，H1是是任任意意的的命命题题公公式式，在在G中中凡凡出出现现G1处处都都以以H1替替换换后后得到的新的命题公式得到的新的命题公式
40、H，若，若G1H1，则，则GH。例例1.9：简化开关电路：简化开关电路：S SS SR RQ QP PP P47/731.2 公式的解释与真值表公式的解释与真值表例例1.10：将下面程序语言进行化简：将下面程序语言进行化简：if A then if B then X else Y else if B then X else Y例例1.11：简化逻辑电路：简化逻辑电路：R RQQP P48/731.2 公式的解释与真值表公式的解释与真值表例例1.12：求证：求证：(1).P(PQ)Q)是永真公式；是永真公式；(2).P(QR)(PQ)R;(3).(P(QR)(PQ R)P;(4).(P(QR)(
41、QR)(PR)R;49/731.2 公式的解释与真值表公式的解释与真值表1.2.5：对偶原理：对偶原理定定义义1.14：设设公公式式A，其其中中仅仅有有联联结结词词，。在在A中中将将，T，F分分别别换换以以，F，T得得到公式到公式A*，则，则A*称为称为A的对偶公式。的对偶公式。对对A*采采取取同同样样的的替替换换，又又得得到到A，所所以以A也也是是A*的的对偶，即对偶是相互的。对偶，即对偶是相互的。例例，P(QR)和和P(QR)互互为为对对偶偶；PF和和PT互为对偶。互为对偶。定定理理1.4：设设A和和A*是是对对偶偶式式，P1,P2,Pn是是出出现现于于A和和A*中所有命题变元，于是中所有
42、命题变元，于是A(P1,P2,Pn)A*(P1,P2,Pn)公式公式(1)50/731.2 公式的解释与真值表公式的解释与真值表定定理理1.5：若若AB，且且A，B为为命命题题变变元元P1,P2,Pn及及 联联 结结 词词，构构 成成 的的 公公 式式，则则A*B*(对偶原理对偶原理)例例，若若(PQ)(P(PQ)PQ，则则由由对对偶原理，得偶原理，得 (PQ)(P(P Q)PQ定定理理1.6：如如果果A=B，且且A，B为为命命题题变变元元P1,P2,Pn及联结词及联结词，构成的公式，则构成的公式，则B*=A*51/731.3 联结词的完备集联结词的完备集我我们们知知道道，命命题题公公式式通通
43、过过等等价价公公式式的的转转换换，可可以以以以不不同同的的形形式式表表示示出出来来。我我们们前前面面介介绍绍了了5个个联联结结词，是否够用呢？词，是否够用呢？1.3.1 联结词的扩充联结词的扩充1.一元运算：一元运算：我我们们来来看看一一个个命命题题变变元元在在一一个个一一元元运运算算的的作作用用下下可能的真值表。可能的真值表。Pf1f2f3f4000111010152/731.3 联结词的完备集联结词的完备集因因此此，最最多多只只能能定定义义4种种运运算算，但但除除了了否否定定之之外外，永永假假，永永真真，恒恒等等作作为为运运算算意意义义不不大大，所所以以一一般般不不再再定定义义其其它一元运
44、算。它一元运算。2.二元运算：二元运算：考虑两个变元在一个二元运算作用下可能的真值表。考虑两个变元在一个二元运算作用下可能的真值表。PQf1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16000100011100011011010010010011011101100001001010110111110000000101101111永假或非蕴含否定蕴含否定合取非P非Q等价异或恒等Q恒等P与非蕴含析取蕴含永真 53/731.3 联结词的完备集联结词的完备集：已定义；：已定义；：意义不大；：意义不大；：可再定义：可再定义f1=PP=F，f2=(PQ)，f3=(PQ)，f4=
45、(QP)，f5=PQ，f6=P，f7=Q，f8=(PQ)，f9=(PQ)f10=Q，f11=P，f12=(PQ)，f13=PQ，f14=PQ，f15=QP，f16=PP=T，其中：其中：f2，f3(或或f4)，f9，f12都是两个联结词的组都是两个联结词的组合，为了叙述方便，可以引进下列几个联结词：合，为了叙述方便，可以引进下列几个联结词：54/731.3 联结词的完备集联结词的完备集联结词联结词记号记号复合命题复合命题读法读法记法记法备注备注f9异或P不可兼或QP异或QPQ逻辑电路中的异或门f3，f4蕴含否定P和Q的蕴含否定P蕴含否定QP Qf12与非P和Q的与非P与非QPQ逻辑电路中的与非
46、门f2或非P和Q的或非P或非QPQ逻辑电路 中的或非门P Q(PQ)P Q(PQ)，P Q(PQ)P Q(PQ)，PQ(PPQ(PQ)Q)，PQ(PPQ(PQ)Q)，这这这这9 9个联结词构成命题演算中的所有联结词。个联结词构成命题演算中的所有联结词。个联结词构成命题演算中的所有联结词。个联结词构成命题演算中的所有联结词。55/731.3 联结词的完备集联结词的完备集1.3.2 与非，或非，异或的性质与非，或非，异或的性质1.与非的性质：与非的性质：PQQP，PP P，(PQ)(PQ)PQ，(PP)(QQ)PQ2.或非的性质：或非的性质：PQ QP，PP P，(PQ)(PQ)PQ，(PP)(Q
47、Q)PQ 3.异或的性质：异或的性质：P0，0 PP，1 PP56/731.3 联结词的完备集联结词的完备集1.3.3：全功能联结词：全功能联结词定义定义1.15：设设S是联结词的集合，是联结词的集合，(1)用用S中的联结词表示中的联结词表示的公式，可以等价地表示任何命题公式，则称的公式，可以等价地表示任何命题公式，则称S是一个联是一个联结词完备集结词完备集(或全功能集合或全功能集合)(Adequate Set of Connectives)，(2)S是一个联结词的完备集，且是一个联结词的完备集，且S中无冗中无冗余的联结词余的联结词(即集合中不存在可以被其中的其它联结词所即集合中不存在可以被其
48、中的其它联结词所定义的联结词定义的联结词)，则称，则称S为极小联结词完备集。为极小联结词完备集。由由1.3.1的分析知，的分析知，,是一个联结词完备是一个联结词完备集，而集，而ABAB，AB(AB)(BA)，所，所以以，是冗余的，故是冗余的，故,也是一个联结词完备也是一个联结词完备集集,而而AB(AB)，所以，所以也是冗余的也是冗余的,也是一个联结词完备集，进一步地也是一个联结词完备集，进一步地,可知可知,是是一个极小联结词完备集。一个极小联结词完备集。57/731.3 联结词的完备集联结词的完备集证明证明:联结词完备集联结词完备集,是一个极小的。是一个极小的。注意：注意：同理，同理，,，,，
49、,也是极小完备也是极小完备集，此外由集，此外由1.3.2中中，的性质可知的性质可知，也是极小完备集；也是极小完备集；,及其子集不是完备集；及其子集不是完备集；实际应用中经常采取的联结词集合为实际应用中经常采取的联结词集合为,。例例1.13：试将公式试将公式(P(QR)(PQ)用仅含用仅含，的公式等价地表示出来。的公式等价地表示出来。58/731.4：范式：范式1.4.1：范式：范式 对于给定公式的判定问题，可用真值表方法加以解对于给定公式的判定问题，可用真值表方法加以解释，但当公式中命题变元的数目较大时，计算量释，但当公式中命题变元的数目较大时，计算量较大，每增加一个命题变元，真值表的行数要翻
50、较大，每增加一个命题变元，真值表的行数要翻倍，计算量加倍，此外，对于同一问题，可以从倍，计算量加倍，此外，对于同一问题，可以从不同的角度去考虑，产生不同的但又等价的命题不同的角度去考虑，产生不同的但又等价的命题公式，即同一个命题可以有不同的表达形式。这公式，即同一个命题可以有不同的表达形式。这样给命题演算带来了一定的困难，因此，有必要样给命题演算带来了一定的困难，因此，有必要使命题公式规范化，为此，引入了范式的概念。使命题公式规范化，为此，引入了范式的概念。59/731.4：范式：范式定义定义1.16：(1)：命题变元或命题变元的否定称为文字；：命题变元或命题变元的否定称为文字；(2)：有限个