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