《离散数学IIppt课件》由会员分享，可在线阅读，更多相关《离散数学IIppt课件（91页珍藏版）》请在金锄头文库上搜索。
1、1/73离散数学离散数学 II II肖明军Web: http:/ 氓挂邱寸膜处轻赡迫伟蚂苛氏绣申争馈痉们耙瞒茵讨畦榔寐垒俞审要泵村离散数学IIppt课件离散数学IIppt课件2/73引言引言课程简介课程简介离离散散数数学学是是现现代代数数学学的的一一个个重重要要分分支支，是是计计算算机机科科学学中中基基础础理理论论的的核核心心课课程程，它它研研究究的的对对象象是是有有限限个个或或可可数数的的离离散散量量。充充分分描描述述了了计计算算机机科科学学离散性的特征。离散性的特征。离散数学是传统的逻辑学、集合论、数论基础、离散数学是传统的逻辑学、集合论、数论基础、算法设计、组合分析、离散概率、关系理论、
2、图算法设计、组合分析、离散概率、关系理论、图论与树、抽象代数、布尔代数、计算模型等汇集论与树、抽象代数、布尔代数、计算模型等汇集起来的一门综合学科。离散数学的应用遍及现代起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。科学技术的诸多领域。 离离散散数数学学是是随随着着计计算算机机科科学学的的发发展展而而逐逐步步建建立立起起来来的的一一门门新新兴兴的的工工具具性性学学科科，形形成成于于上上上上个个世世纪七十年代。纪七十年代。嘲守寂影糠逃赵嫂豫蕉回盆瘁琴坯茅鞋握渣痢睦直绽酮宏服濒列甚论屑韧离散数学IIppt课件离散数学IIppt课件3/73引言引言课程意义课程意义离离散散数数学学是是
3、计计算算机机科科学学的的数数学学基基础础，其其基基本本概概念念、理理论论、方方法法大大量量地地应应用用在在数数字字电电路路、编编译译原原理理、数数据据结结构构、操操作作系系统统、数数据据库库系系统统、算算法法设设计计、人人工工智智能能、计计算算机机网网络络等等专专业业课课程程中中，是是这这些些课课程程的的基基础课程。础课程。 离离散散数数学学学学习习十十分分有有益益于于概概括括抽抽象象能能力力、逻逻辑辑思思维维能能力力、归归纳纳构构造造能能力力的的提提高高，能能够够培培养养提提高高学学生生的数学思维能力和对实际问题的求解能力。的数学思维能力和对实际问题的求解能力。教学内容教学内容数理逻辑数理逻
4、辑、集合论集合论、代数结构代数结构、图论、图论污皖惜儿强贴擅嘘窒借拖缠烁闸念傅滔谰撒汲榷夸缎液翅示烛凸旗涤弹陵离散数学IIppt课件离散数学IIppt课件4/73引言引言教学内容教学内容第一部分第一部分 数理逻辑数理逻辑第一章第一章 命题逻辑命题逻辑第二章第二章 谓词逻辑谓词逻辑第二部分第二部分 集合论集合论第三章第三章 集合代数集合代数第四章第四章 二元关系二元关系葱腑招伐矾敌蠢伪窟疹掉厚委挽舞蔡馅寝绘甲能挫痰斗秉短港啥姑侩文簧离散数学IIppt课件离散数学IIppt课件5/73引言引言教学内容教学内容第二部分第二部分 集合论集合论第五章第五章 函数函数第六章第六章 集合的基数集合的基数第三
5、部分第三部分 代数结构代数结构第七章第七章 代数系统代数系统第八章第八章 群论群论翅涛瞳虞矫家翁涤孜坞琴贡琢丽居协结蹋泥螟逞答吉麻癸细任严猎妹它豁离散数学IIppt课件离散数学IIppt课件6/73引言引言教学内容教学内容第三部分第三部分 代数结构代数结构第九章第九章 环与域环与域第十章第十章 格与布尔代数格与布尔代数疟定潍笨邦台闷殷攒艘妥尿业曲翻躬咕辑漳艾贤闺舞挨僳娄昏阐式赣浓掉离散数学IIppt课件离散数学IIppt课件7/73第一部分第一部分 数理逻辑数理逻辑逻辑学逻辑学是一门研究思维形式和规律的科学。分为辩证逻是一门研究思维形式和规律的科学。分为辩证逻辑和形式逻辑两种。思维的形式结构包
6、括了辑和形式逻辑两种。思维的形式结构包括了概念概念 判断判断和和推理推理之间的结构和联系，其中之间的结构和联系，其中概念概念是思是思维的基本单位，通过概念对事物是否具有某种属维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，就是性进行肯定或否定的回答，就是判断判断。由一个或。由一个或几个判断推出另一判断的思维形式就是几个判断推出另一判断的思维形式就是推理推理。数理逻辑数理逻辑用数学方法研究推理的规律称为数理逻辑。所谓用数学方法研究推理的规律称为数理逻辑。所谓数学方法就是引用一套符号体系的方法，所以数数学方法就是引用一套符号体系的方法，所以数理逻辑又称作符号逻辑。理逻辑又称作符号
7、逻辑。勤寻虫找日秃戒唱冈赫时形沽论段倾搅赴择怔束铃彪鳃脯烬凶盖下早豢经离散数学IIppt课件离散数学IIppt课件8/73第一部分第一部分 数理逻辑数理逻辑现代数理逻辑现代数理逻辑逻辑演算、逻辑演绎、模型论、证明论、逻辑演算、逻辑演绎、模型论、证明论、递归函数论、公理化集合论等。递归函数论、公理化集合论等。我们要介绍的是数理逻辑中最基本的内容：我们要介绍的是数理逻辑中最基本的内容：命题逻辑和谓词逻辑。即一般所谓的古典命题逻辑和谓词逻辑。即一般所谓的古典逻辑。逻辑。德国数学家莱布尼茨德国数学家莱布尼茨Leibniz（现代逻辑的（现代逻辑的首席创始人）；布尔首席创始人）；布尔Boole （奠基人，
8、逻辑（奠基人，逻辑的数学分析）；弗雷格（数论的基础）的数学分析）；弗雷格（数论的基础）症铡镍堵瓤渔通滤绦坤囤隅措局詹柿凭巍亿粱铸课宋虽油遍岳桌闯愉瀑狼离散数学IIppt课件离散数学IIppt课件9/73第一章第一章 命题逻辑命题逻辑 命题逻辑也称命题演算或语句逻辑。它研究命题逻辑也称命题演算或语句逻辑。它研究以以“命题命题”为基本单位构成的前提和结论之为基本单位构成的前提和结论之间的可推导关系，研究什么是命题？如何表间的可推导关系，研究什么是命题？如何表示命题？怎样由一组前提推导一些结论。示命题？怎样由一组前提推导一些结论。概念概念判断判断推理推理视度妓谦铂潮骨陛崔颂鄂炼角舆湾土汽寻脊渴喻剃红
9、淬捣弱喳虹躇出器纠离散数学IIppt课件离散数学IIppt课件10/731.1 命题与命题联结词命题与命题联结词1.1.1命题命题定义定义1.1：具有：具有确切真值确切真值的的陈述句陈述句(或断言或断言)称称为命题为命题(Proposition)。命题的取值称为真值。真值只有命题的取值称为真值。真值只有“真真”和和“假假”两种，分别用两种，分别用“T”或或“1”和和“F”或或“0”表示。表示。注意：命题的真值非真即假，只有两种取值，注意：命题的真值非真即假，只有两种取值，这样的系统为二值逻辑系统。这样的系统为二值逻辑系统。垮群囚金悍嵌忿钟槐男搭临台裁肺寅颇恳凤倒澡舍浚粕衷扰莉缸饥葡宣书离散数学
10、IIppt课件离散数学IIppt课件11/731.1 命题与命题联结词命题与命题联结词例例1-1：命题示例。：命题示例。(a):今天下雪今天下雪(b):3+3=6 (c):2是偶数而是偶数而3是奇数是奇数(d):陈胜起义那天，合肥下雨陈胜起义那天，合肥下雨(e):较大的偶数都可表为两个质数之和较大的偶数都可表为两个质数之和(f):x+y4(g):真好啊真好啊!(h):x=3(i):你去哪里？你去哪里？(j):我正在说谎。我正在说谎。注意：注意：由定义知，一切没有判断内容的句子由定义知，一切没有判断内容的句子如命令，感叹句，疑问句，祈使句，二义性如命令，感叹句，疑问句，祈使句，二义性的陈述句等都
11、不能作为命题。的陈述句等都不能作为命题。聚遂核咎哺锹锋膏能寇酉培俄赴很柳丑艰借兑矾蒋厚恐硝妆皮芋猖商共啡离散数学IIppt课件离散数学IIppt课件12/731.1 命题与命题联结词命题与命题联结词例例1-2：下列句子哪些是命题，判断命：下列句子哪些是命题，判断命题的真假。题的真假。(1):2是素数是素数(2):北京是中国的首都北京是中国的首都(3):这个语句是假的这个语句是假的(4):x+y0(5):我喜欢踢足球我喜欢踢足球(6):地球外的星球上也有人地球外的星球上也有人(7):明年国庆节是晴天明年国庆节是晴天(8):把门关上把门关上(9):你要出去吗？你要出去吗？(10):今天天气真好啊！
12、今天天气真好啊！羞航捞界买铃杜澜擂棵屎茎兹肆碘弧嘱沮签道贫蹄劝提抢沧蓄斡欢近淆乳离散数学IIppt课件离散数学IIppt课件13/73注意注意命题一定是通过陈述句来表达；反之，并非一切命题一定是通过陈述句来表达；反之，并非一切的陈述句都一定是命题。的陈述句都一定是命题。命题的真值有时可明确给出，有时还需要依靠环命题的真值有时可明确给出，有时还需要依靠环境条件，实际情况，时间才能确定其真值。但其境条件，实际情况，时间才能确定其真值。但其真值一定是唯一确定的。真值一定是唯一确定的。1.1 命题与命题联结词命题与命题联结词巧胃彪炭磨腥七另汀坞射翻淀济伪谱腮窗客伸儒查傲踪闲归诡凋管车昧瓶离散数学IIp
13、pt课件离散数学IIppt课件14/731.1 命题与命题联结词命题与命题联结词命题可分为两种类型：命题可分为两种类型：简简单单命命题题：若若一一个个命命题题已已不不能能分分解解成成更更简简单单的的命命题题，则则该该命命题题叫叫原原子子命命题题或或本本原原命命题题或或简简单单命命题题（Simple Proposition）复复合合命命题题（Compound Proposition）：可可以以分分解解为为简简单单命命题题的的命命题题，而而且且这这些些简简单单命命题题之之间间是是通通过过关关联联词词（如如“或或者者”,“并并且且”,“不不”，“如如果果 则则”,“当当且且仅仅当当”等等）和和标标点
14、点符符号号复复合合而构成一个复合命题。而构成一个复合命题。例，合肥是安徽的省会当且仅当鸟会飞。例，合肥是安徽的省会当且仅当鸟会飞。注意：注意：命题通常用大写英文字母（可带下标）来表示。命题通常用大写英文字母（可带下标）来表示。枚雄呕凉菌拂缮挫燕枪贞娟泄砧旧己剁魂怕葱滁篮纱胳慕快谓裤遥泻竭喻离散数学IIppt课件离散数学IIppt课件15/731.1.2 命题联结词命题联结词命命题题通通常常可可以以通通过过一一些些联联结结词词复复合合而而构构成成新新的的命命题题，这这些些联联结结词词被被称称为为逻逻辑辑联联结结词词。用用数数学学方方法法研研究究命命题题之之间间的的逻逻辑辑关关系系时时（也也就就是
15、是在在命命题题演演算算中中），这这些些联联结结词词可可以以看看作作是是运运算算符符，因因此此也也叫叫作作逻逻辑辑运运算算符符。常用的联结词有以下常用的联结词有以下5个：个：定定义义1.2：设设P是是任任一一命命题题，复复合合命命题题“非非P”（或或“P的的否否定定”）称称为为P的的否否定定式式（Negation），记记作作P，“”为否定联结词。为否定联结词。 P为真当且仅当为真当且仅当P为假。为假。如：如：P：2是素数，则是素数，则P：2不是素数。不是素数。1.1 命题与命题联结词命题与命题联结词肾熙独何譬尔鲸第爆恭惨尿局孕祁度承涉驴时濒灌登倦映沟理耀眶抛羚甄离散数学IIppt课件离散数学II
16、ppt课件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是是素素数并且是偶数。数并且是偶数。砧羽疗朵篓卑伙旺脯嚷区赘捎街惜突治兔判鞠毖瘟镶性底窘底丁乌个弊云离散数学IIppt课件离散数学IIppt课件17/731.1 命题与命题联结词命题与命
17、题联结词定定义义1.4：设设P Q是是任任意意两两个个命命题题，复复合合命命题题“P或或Q” 称称为为P与与Q的的析析取取式式（Disjunction），记记作作P Q，“ ”为为析析取取联联结结词词。 P Q为为真真当当且且仅仅当当P，Q至少一个为真。至少一个为真。例例，P：2是是素素数数，Q：2是是奇奇数数。则则P Q：2是是素素数或是奇数。数或是奇数。借疙趁冷苇姬忿铭屉赖淌的芥洒皇撂嚷埃摸玛遁毗花蝎垂犯垛缩阮妹涡揽离散数学IIppt课件离散数学IIppt课件18/731.1 命题与命题联结词命题与命题联结词定定义义1.5：设设P Q是是任任意意两两个个命命题题，复复合合命命题题“如如果果
18、P则则Q” 称称为为P与与Q的的蕴蕴含含式式（Implication），记记作作PQ，“”为为 蕴蕴含含联联结结词词，P称称为为蕴蕴含含式式的的前前提提，假假设设或或前前件件，而而Q称称为为结结论论式式后后件件。PQ为假当且仅当为假当且仅当P为真为真Q为假。为假。例例，P：G是是正正方方形形，Q：G的的四四边边相相等等，则则PQ：如果：如果G是正方形，则是正方形，则G的四边相等。的四边相等。蕴含式蕴含式PQ可以用多种方式陈述：可以用多种方式陈述：“若若P，则则Q”; “P是是Q的的充充分分条条件件”; “Q是是P的的必必要要条件条件”; “Q每当每当P”; “P仅当仅当Q”等。等。孙骂商落捷钵
19、盈锤孕悉撼荐诗类末鞭傅际叁罗刑匝哨咨潭粮膛蚕耪兑碴父离散数学IIppt课件离散数学IIppt课件19/731.1 命题与命题联结词命题与命题联结词给给定定命命题题PQ，我我们们把把QP，PQ， QP分分别别叫叫作作命命题题PQ的的逆逆命命题题，反反命命题题和和逆逆反命题。反命题。定定义义1.6：设设P，Q是是任任意意两两个个命命题题，复复合合命命题题“P当当且且仅仅当当Q”称称为为P与与Q的的等等价价式式(Equivalence)，记记作作PQ，“”为为等等价价联联结结词词。 PQ为为真真当当且仅当且仅当P，Q同为真假。同为真假。例例如如，P：合合肥肥是是安安徽徽省省会会，Q：鸟鸟会会飞飞，则
20、则PQ：合肥是安徽省会当且仅当鸟会飞。：合肥是安徽省会当且仅当鸟会飞。如如果果PQ是是真真，则则PQ和和QP是是真真，反反之之亦亦然然，因因此此PQ也也读读作作“P是是Q的的充充要要条条件件”或或“P当当且且仅当仅当Q”。惹裔堰慎碑闺浑沪代旨砷诛淀豫养娶恨缘尉去且钢逗稿憨廓仰瑞拢扭拓唱离散数学IIppt课件离散数学IIppt课件20/731.1 命题与命题联结词命题与命题联结词五个联结词五个联结词联结词联结词记号记号表达式表达式读法读法真值结果真值结果否定否定P非非PP为为真真当当且且仅仅当当P为为假假合取合取P QP且且QP Q为为真真当当且且仅仅当当P，Q同为真同为真析取析取P QP或或Q
21、P Q为为真真当当且且仅仅当当P，Q至少一个为真至少一个为真蕴含蕴含PQ若若P则则QPQ为为假假当当且且仅仅当当P为真为真Q为假为假等价等价PQP当且仅当当且仅当QPQ为为真真当当且且仅仅当当P，Q同为真假同为真假诺能应检锦态婆梭炔湘男仿宝五献件莲冰巫汛馅硒肝户竭琳辛扦氨秋蛔伴离散数学IIppt课件离散数学IIppt课件21/731.1 命题与命题联结词命题与命题联结词一般约定：一般约定：a)：运运算算符符(联联结结词词)结结合合力力强强弱弱顺顺序序为为： ； ， ； ，；凡符合此顺序的，括号可省略。；凡符合此顺序的，括号可省略。b)：相相同同的的运运算算符符，从从左左到到右右次次序序计计算算
22、时时，括括号号可省去。可省去。c)：最外层括号可省。：最外层括号可省。如，如，(P Q) R) (R P)Q) (P QR) R PQ卿耸炬矗街嘱喂抵镶楷垫珐毗宰住源驱较橡藤牌阜苦昏雹操孵锐咆月延绷离散数学IIppt课件离散数学IIppt课件22/73例例1.3：符号化下列命题。：符号化下列命题。a)：他既有理论知识又有实践经验：他既有理论知识又有实践经验b)：i. 如果明天不是雨夹雪则我去学校如果明天不是雨夹雪则我去学校 ii. 如果明天不下雨并且不下雪，则我去学校如果明天不下雨并且不下雪，则我去学校 iii. 如果明天下雨或下雪则我不去学校如果明天下雨或下雪则我不去学校 iv. 明天我将风
23、雨无阻一定去学校明天我将风雨无阻一定去学校 v. 当且仅当明天不下雪并且不下雨时我才去当且仅当明天不下雪并且不下雨时我才去学校学校1.1 命题与命题联结词命题与命题联结词疏奸辙硒诅擎霹恬摊泣站扳疚执章巍掘芹拘涯含绕俭假鹰舌爪苛哇浪苏棕离散数学IIppt课件离散数学IIppt课件23/731.1 命题与命题联结词命题与命题联结词c)：说说小小学学生生编编不不了了程程序序，或或说说小小学学生生用用不不了了个个人计算机，那是不对的。人计算机，那是不对的。d)：若若不不是是他他生生病病了了或或出出差差了了，我我是是不不会会同同意意他他不参加学习的。不参加学习的。e)：如如果果我我上上街街了了，我我就就
24、去去书书店店看看看看，除除非非我我很很累。累。白具僵拇急填粟就睹紧酞敖路渝撑蒜叠挎倪闺派眷街虱葫豢公憎僻藩搁带离散数学IIppt课件离散数学IIppt课件24/731.1 命题与命题联结词命题与命题联结词注意：注意：(1)是是自自然然语语言言中中的的“非非” “不不” 和和“没没有有”等等的逻辑抽象的逻辑抽象(2)是是自自然然语语言言中中的的“并并且且” “既既 又又” “且且” “和和”等的逻辑抽象等的逻辑抽象(3)是是自自然然语语言言中中的的“或或”和和“或或者者”等等的的逻逻辑辑抽抽象象；但但“或或”有有“可可兼兼或或” “不不可可兼兼或或” “近似或近似或”三种三种(4)PQ是是自自然
25、然语语言言中中的的“只只要要P，就就Q” “因因为为P，所以所以Q” “P仅当仅当Q”等的逻辑抽象等的逻辑抽象茫蒜杠窒从交蔚瞩擎茂趁垄程肥卯顷记季寅在朱羔宪读醇奶畸熏漆辱乱包离散数学IIppt课件离散数学IIppt课件25/73(5) 是是自自然然语语言言中中的的“充充分分必必要要条条件件”和和“当当且且仅当仅当”等的逻辑抽象等的逻辑抽象(6)联联结结词词连连接接的的是是两两个个命命题题真真值值之之间间的的联联结结，而而不不是是命命题题内内容容之之间间的的连连接接，因因此此复复合合命命题题 的的真真值值只只取决于构成他们的各原子命题的真取决于构成他们的各原子命题的真 值值(7) ，具有对称性，
26、而具有对称性，而，没有没有(8) ， 与与计计算算机机中中的的与与门门，或或门门，非非门门电电路路是相对应的是相对应的看看P6-7 例例1.4-1.5，P9 例例1.71.1 命题与命题联结词命题与命题联结词衷拙赞陛羊芳蛾顾活讲色昧撇尾蒋妒隙投曙了候汕显珠卤萝奉金曹武羽监离散数学IIppt课件离散数学IIppt课件26/731.2.1：命题公式：命题公式就就像像在在代代数数学学里里引引入入变变量量一一样样，为为了了更更广广泛泛的的应应用用命命题题演演算算，在在数数理理逻逻辑辑中中也也引引入入了了命命题题变变量量。使使得得在在研研究究时时，只只需需考考虑虑命命题题的的真真值值，而而不不知知晓晓命
27、命题题的的具体含义。具体含义。定定 义义 1.7： 一一 个个 特特 定定 的的 命命 题题 是是 一一 个个 常常 值值 命命 题题(Constant Proposition)， 它它 不不 是是 具具 有有 值值“T”(“1”)，就就是是具具有有值值“F”(“0”)。而而一一个个任任意意的的没没有有赋赋予予具具体体内内容容的的原原子子命命题题是是一一个个变变量量命命题题，常常称称它它为为命命题题变变量量(或或命命题题变变元元、命命题题变变项项)(Proposition Variable)。命命题题变变量量无无具具体体的的真真值值，它的值域是集合它的值域是集合T，F(或或1，0)。1.2 公
28、式的解释与真值表公式的解释与真值表替镍病贤眶砧茅疲更童搜胡郁叮插迫汽摔堡趟峻杭载钧叉明疮撞谜卑验垒离散数学IIppt课件离散数学IIppt课件27/73原原子子命命题题在在不不指指派派真真值值时时称称为为命命题题变变元元，而而复复合合命命题题由由原原子子命命题题和和联联结结词词构构成成，可可以以看看作作是是命命题题变变元元的的函函数数，且且该该函函数数的的值值仍仍为为“真真”或或“假假”，可可以以称称为为真真值值函函数数（True Value Function）或或命命题题公公式式。但但不不是是说说原原子子命命题题和和联联结结词词的的一一个个随随便便的的组组合合都都可可以以为为命命题题公公式式
29、，我我们们用用递递归归的的方方法法来来定定义义命命题题公公式。式。1.2 公式的解释与真值表公式的解释与真值表叫感恳妆夯香蝴步拇挚管记淄盼滓荣勤制狂怯尉曙竞找逆绍楔楞冯聂淄枫离散数学IIppt课件离散数学IIppt课件28/731.2 公式的解释与真值表公式的解释与真值表定义定义1.8：命题公式，也叫（合式）公式：命题公式，也叫（合式）公式(1).命题变元本身是一个公式；命题变元本身是一个公式；(2).如果如果P是公式，则是公式，则P也是公式；也是公式；(3).如如果果P，Q是是公公式式，则则PQ PQ PQ PQ也是公式；也是公式；(4).命命题题公公式式(Prepositional For
30、mula)是是仅仅由由有有限限步步使使用用规规则则(1)(3)后后产产生生的的结结果果。公公式式常常用用符符号号G H等表示。等表示。例例，( PQ)，(P(P Q) ，(PQ) (R Q) (P R)是命题公式是命题公式(P Q ) Q)， (P Q， ( PQ (R， PQ 不是命题公式不是命题公式什催稗赃扇气治变脾追札闲犯坟解乒碟恫岛硼悬捌奈弯坞见镍朽磊络驴进离散数学IIppt课件离散数学IIppt课件29/73注意：注意：如如果果G是是含含有有n个个命命题题变变元元 P1, P2, ,Pn的的公公式式，通常记为通常记为G（P1, ,Pn）或简记为）或简记为G。原原子子命命题题变变元元是
31、是最最简简单单的的（合合式式）公公式式，也也叫叫原原子（合式）公式。子（合式）公式。合合成成公公式式没没有有真真值值，只只有有对对其其变变元元进进行行指指派派后后才才有真值。有真值。合成公式无限多。合成公式无限多。1.2 公式的解释与真值表公式的解释与真值表医息捡平铆柳茁奏奈延控统段斡嘘肯骚糯虽栗浮履皿耍孺裹秒藕瀑翌长勉离散数学IIppt课件离散数学IIppt课件30/731.2 公式的解释与真值表公式的解释与真值表合成公式的层次：合成公式的层次：(1).若公式若公式A是一单个的命题变项，则称是一单个的命题变项，则称A为为0层公式；层公式；(2).称称A是是n+1(n0)层公式只需满足下列情况
32、只一：层公式只需满足下列情况只一：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；从从图图论论的的观观点点来来看看每每个个多多层层公公式式可可以以用用一一个个“树树”来表示。来表示。往祸殃膘厨寂绰毯湘驭徘嘴藕扫炎胁蔫烧顷凤躺又炉荡迂绷瓷独丈空碟招离散数学IIppt课件离散数学IIppt课件31/731.2 公式的解释与真值表公式的解释与真值表1.
33、2.2：公式的解释与真值表：公式的解释与真值表公公式式本本身身没没有有真真值值，只只有有在在对对其其所所有有命命题题变变元元指指定真值后才变成一个具有真值的命题。定真值后才变成一个具有真值的命题。定定义义1.9：设设命命题题变变元元P1, P2, ,Pn是是出出现现在在公公式式G中中的的所所有有命命题题变变元元，指指定定P1, P2, ,Pn一一组组真真值值，则则这这组组真真值值称称为为G的的一一个个解解释释(Explanation),并并记记作作I。一一般般来来说说，若若有有n个个命命题题变变元元，则则应应有有2n个个不不同同的的解释。解释。定定义义1.10：公公式式G在在其其所所有有可可能
34、能的的解解释释下下所所取取真真值值的表，称作的表，称作G的真值表的真值表(Truth)。喘勇彤刷浓精纳磕凳犯盼钵羌劝儡嚏门吕宏描寓膝肠行薄菱吴周稠紊男洒离散数学IIppt课件离散数学IIppt课件32/731.2 公式的解释与真值表公式的解释与真值表例例1.4：5个联结词的真值表个联结词的真值表(T：1，F：0)PQPPQP Q PQ PQ0010011011011010001001101111举拳芝戳稚接刷仔毛雌浮诅令禾哎骨矿饰拎毗萤土旧乍训掌康堂蕊坍陷荐离散数学IIppt课件离散数学IIppt课件33/731.2 公式的解释与真值表公式的解释与真值表例例1.5：设设公公式式G= (PQ)
35、R )(PQ)，其其中中P，Q，R是是G的命题变元，则其真值表如下：的命题变元，则其真值表如下：PQRPQ(PQ) R PQ(PQ) R )(PQ)00001110010111010010001101001000100101010011010101111100辐奠叫挫乾墨很窿映伸达安督屹制父晤渡画涂串押藤待裤嘿把新扎嗓上巡离散数学IIppt课件离散数学IIppt课件34/731.2 公式的解释与真值表公式的解释与真值表1.2.3：一些特殊的公式：一些特殊的公式例例1.6：考虑：考虑：G1= (PQ) P； G2=(PQ) P； G3= (P Q) (PQ)公公式式G1对对所所有有可可能能的的解
36、解释释都都具具有有“真真”值值，G3对对所所有有解解释释都都具具有有“假假”值值，公公式式G2则则具具有有“真真”和和“假假”值。值。愿绞谩嚏陆塌扮抡敷腹第垢办睦冕僳驾咎亨钠靶点疡桨猫谚恢苯癌类妹洪离散数学IIppt课件离散数学IIppt课件35/731.2 公式的解释与真值表公式的解释与真值表1.重言式：重言式：定义定义1.11：(1). 公公式式G称称为为永永真真公公式式（重重言言式式），如如果果在在它它的的所有解释下都为所有解释下都为“真真”；(2). 公式公式G称为可满足的，如果它不是永假的；称为可满足的，如果它不是永假的；(3). 公公式式G称称为为永永假假公公式式（矛矛盾盾式式）,
37、 如如果果在在它它的的所所有有解解释释下下都都为为“假假”;有有时时也也称称永永假假公公式式为为不不可可满足公式。满足公式。注意：注意：(1). 重重言言式式的的否否定定是是矛矛盾盾式式，矛矛盾盾式式的的否否定定是是重重言言式，所以研究其一就可以了；式，所以研究其一就可以了；圈擅俊佳卷很靡腊铝仪痒界去涟侯攒孤酬庚瓮峡课记严斯巩酿浙条瘟骗涸离散数学IIppt课件离散数学IIppt课件36/731.2 公式的解释与真值表公式的解释与真值表(2). 重重言言式式的的合合取取，析析取取，蕴蕴含含，等等值值等等都都是重言式；是重言式；(3). 重重言言式式中中有有许许多多非非常常有有用用的的恒恒等等式式
38、和和永永真蕴含式。真蕴含式。对对任任意意的的公公式式，判判定定其其是是否否为为永永真真公公式式，永永假假公公式式，可可满满足足公公式式的的问问题题称称为为给给定定公公式式的的判判定定问问题题。由由于于一一个个命命题题公公式式的的解解释释的的数数目目是是有有穷穷的的，所所以以命命题题逻逻辑辑的的判判定定问问题题是是可可解解的的，即即命命题题的的永永真真，永永假假性性是是可可判判定定的的。其其判定方法有判定方法有真值表法真值表法和和公式推演法公式推演法。攒楷淋仗悄裳篷脸根摸辱雌琅部干赞拆青般播艰飘盖扼轮窜苫债凝甩欺汞离散数学IIppt课件离散数学IIppt课件37/731.2 公式的解释与真值表公
39、式的解释与真值表例例1.7： 判定公式：判定公式：(1).(PQ) ( PQ);(2). (PQ)P) Q；(3). P(Q R)。2.恒等式：恒等式：定定义义1.12：公公式式G，H，如如果果在在其其任任意意解解释释下下，其其真真值值相相同同，则则称称G是是H的的等等价价式式(Equivalent)或或称称G恒等于恒等于H，记作，记作GH。曼箩婚堆邮署更发覆肄己伴由钉啊冕那矢瘴轻抠痛泉沼嗅雅呜殉轴橡犬捏离散数学IIppt课件离散数学IIppt课件38/731.2 公式的解释与真值表公式的解释与真值表定定理理1.1：对对于于公公式式G和和H， GH的的充充分分必必要要条条件件是公式是公式G H
40、是重言式。是重言式。证明：证明：必必要要性性：假假定定GH，则则G和和H在在其其任任意意解解释释I下下，或或同同为为真真或或同同为为假假，由由“”的的意意义义知知， G H在任意解释在任意解释I下，其真值为真，即下，其真值为真，即G H为重言式；为重言式；充充分分性性：假假设设公公式式G H是是重重言言式式，I是是它它的的任任意意解解释释，在在I下下， G H为为真真，因因此此，G，H或或同同为为真真或同为假，由于或同为假，由于I的任意性，故有的任意性，故有GH。铸茧鉴插遣恒澎峨密估订狰铺还绥掣瞅观席阁全献辑时摹军员舔才葛熟憋离散数学IIppt课件离散数学IIppt课件39/731.2 公式的
41、解释与真值表公式的解释与真值表注意注意与与不同：不同：(1). ：逻辑等价关系，：逻辑等价关系， G H不是命题公式；不是命题公式；(2). ：逻辑联结词，：逻辑联结词， G H是命题公式；是命题公式；(3).计计算算机机不不能能判判断断G，H是是否否逻逻辑辑等等价价，而而可可计计算算G H是否为重言式。是否为重言式。尝冗旁袄缆胎悸仁溪袜阔谨蹬婆漳疙阐镁摹赛注普逻柒详痹裁笼梳陌棕溃离散数学IIppt课件离散数学IIppt课件40/731.2 公式的解释与真值表公式的解释与真值表常用逻辑恒等式（常用逻辑恒等式（P，Q，R为任意命题，为任意命题，T为真命为真命题，题，F为假命题）：为假命题）：E1
42、PP双否定双否定E2PPP的幂等律的幂等律E3PPP的幂等律的幂等律E4PQQP的交换律的交换律E5PQQP的交换律的交换律E6(PQ) RP(QR)的结合律的结合律E7(PQ) RP(QR)的结合律的结合律E8P(QR) PQPR在在上的分配律上的分配律E9P (QR) (PQ)(PR)在在上的分配律上的分配律E10(PQ) PQ德德摩根定律摩根定律E11(PQ) PQ掉卓蛹噪瞄伺抨挛羊券竭吴南娠锰茁扔林实形腋布衰留梗浆案颂到信施饥离散数学IIppt课件离散数学IIppt课件41/731.2 公式的解释与真值表公式的解释与真值表E12P(PQ) P吸收律吸收律E13P (PQ) PE14(P
43、Q) PQ蕴含等值式蕴含等值式E15(PQ) (PQ) (QP)等价等值式等价等值式E16PTT零律零律E17PFFE18PFP同一律同一律E19PTPE20PPT排中律排中律E21PPF矛盾律矛盾律E22(PQR) (P(QR)输出律输出律E23(PQ) (PQ) P归谬律归谬律E24(PQ) QP逆反律逆反律暇巍爵汹爆花翘巴茬翘打久邀聊渴殃枝哪皇帕稿初众裔宦锦蔑遇制杜率纲离散数学IIppt课件离散数学IIppt课件42/731.2 公式的解释与真值表公式的解释与真值表3.永真蕴含式：永真蕴含式：定定义义1.13：若若AB是是一一永永真真式式，那那么么称称为为永永真真蕴蕴含式，记为含式，记为
44、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)谎从哲汾父古纤蓝崇偿带猾顿吏划娱耐仁每瓦朵朔切聪左烩景寐浮坷讣涧离散数学IIppt课件离散数学IIppt课件43/731.2 公式的解释与真值表公式的解释与真值表4.恒等式和永真蕴含式的两个性质：恒等式和永真蕴含式的两个性质：(1).若若AB， BC，则则AC；若若A=B， B=C，则则A=C. (即即逻逻
45、辑辑恒恒等等和和永永真真蕴蕴含含都都是是可可传传递的递的) 证证明明：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。就揖腰烷叭遗功胚明月页缆追肝制麦口荧伸省芬所华窗娩鸦奎赴惭截凸汹离散数学IIppt课件离散数学IIppt课件44/731.2 公式的解释与真值表公式的解释与真值表(2).若若A=B， A=C，则，则A=BC
46、. 证证明明：A为为真真时时，B，C都都为为真真，则则BC也也为为真真，即即ABC为为真真；A为为假假时时，则则不不管管BC是是真真还还是假时，是假时，ABC均为真，因此均为真，因此A=BC。筑败肚贬乎防耐掺郸椎票萌夸搏搂瑚抬谆澄拽税拔象守率骡贺搽秘顾诀赋离散数学IIppt课件离散数学IIppt课件45/731.2 公式的解释与真值表公式的解释与真值表1.2.4：代入规则和替换规则：代入规则和替换规则当当一一个个公公式式是是永永真真式式或或永永假假式式时时，其其公公式式的的真真值值完完全全跟跟随随其其命命题题变变元元的的真真值值的的变变化化而而变变化化，因因此此，当当用用其其他他公公式式来来取
47、取代代公公式式中中的的命命题题变变元元时时，不不会会改变公式的永真性和永假性改变公式的永真性和永假性定定理理1.2(代代入入定定理理) ：设设G(P1, ,Pn)是是一一个个命命题题公公式式，其其中中P1, ,Pn是是命命题题变变元元，G1(P1, ,Pn), Gn(P1, ,Pn)为为任任意意的的命命题题公公式式，此此时时若若G是是永永真真公公式式或或永永假假公公式式，则则用用G1取取代代P1,Gn取取代代Pn后后，得得到到的的新新的的命命题题公公式式G(G1,Gn) G(P1, ,Pn)也是一个永真公式或永假公式。也是一个永真公式或永假公式。珊缮瞄限缠排盯裳蔡剩戎尸安闲乖惕疹蜒沟翅呻衫编晌
48、咒旷撼迁妊澜只姥离散数学IIppt课件离散数学IIppt课件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替替换换后后得到的新的命题公式得到的新的命题公式H，若，若G1H1，则，则GH。 例例1.9：简化开关电路：简化开关电路：S SS SR RQ QP PP P戈驴帆吼军款站忱凭乓俄逆硅
49、枣详堂楷垂附捡劣幕需到哩芜腕酒汇城赣藏离散数学IIppt课件离散数学IIppt课件47/731.2 公式的解释与真值表公式的解释与真值表例例1.10：将下面程序语言进行化简：将下面程序语言进行化简： if A then if B then X else Y else if B then X else Y例例1.11：简化逻辑电路：简化逻辑电路： R RQ QP P孩另奉捶扳耻坏晕荣汇饱刃武孜铬肾螟办伎蹿中圣箱处腺腺沽频盔餐奄矮离散数学IIppt课件离散数学IIppt课件48/731.2 公式的解释与真值表公式的解释与真值表例例1.12：求证：求证：(1).P(PQ)Q)是永真公式；是永真公式；
50、 (2).P(QR)(PQ)R; (3).(P(QR)(PQ R)P; (4).(P(QR)(QR)(PR)R;北睹帆督冕鸵恐胎洒哇触虱眷琅很蚊迷佰奇亦廖丛扦杨浮吟仪剥芒啄碎瘪离散数学IIppt课件离散数学IIppt课件49/731.2 公式的解释与真值表公式的解释与真值表1.2.5：对偶原理：对偶原理定定义义1.14：设设公公式式A，其其中中仅仅有有联联结结词词， ，。在在A中中将将，T，F分分别别换换以以，F，T得得到公式到公式A*，则，则A*称为称为A的对偶公式。的对偶公式。对对A*采采取取同同样样的的替替换换，又又得得到到A，所所以以A也也是是A*的的对偶，即对偶是相互的。对偶，即对偶
51、是相互的。例例，P(QR)和和P(QR)互互为为对对偶偶；PF和和PT互为对偶。互为对偶。定定理理1.4：设设A和和A*是是对对偶偶式式，P1,P2, ,Pn是是出出现现于于A和和A*中所有命题变元，于是中所有命题变元，于是A(P1,P2, ,Pn)A*(P1, P2, , Pn) 公式公式(1)阅别屁皿拨粉宅爬仲逗务猫泞翟吞诌赂傻坐寒琵翼鼓材棉联辱肠愈辉著蒂离散数学IIppt课件离散数学IIppt课件50/731.2 公式的解释与真值表公式的解释与真值表定定理理1.5：若若AB，且且A，B为为命命题题变变元元P1,P2, ,Pn及及 联联 结结 词词 ， ， 构构 成成 的的 公公 式式 ，
52、 则则A*B* (对偶原理对偶原理)例例，若若(PQ)(P(PQ) PQ，则则由由对对偶原理，得偶原理，得 (PQ)(P(P Q) PQ定定理理1.6：如如果果A=B，且且A，B为为命命题题变变元元P1,P2, ,Pn及联结词及联结词，构成的公式，则构成的公式，则B*=A* 逞夺镁烬剑碗总野昼博彬测蹲渐蒜焚夜弯该影际巫敖驳超谴窑拼绿捧谆惠离散数学IIppt课件离散数学IIppt课件51/731.3 联结词的完备集联结词的完备集我我们们知知道道，命命题题公公式式通通过过等等价价公公式式的的转转换换，可可以以以以不不同同的的形形式式表表示示出出来来。我我们们前前面面介介绍绍了了5个个联联结结词，是
53、否够用呢？词，是否够用呢？1.3.1 联结词的扩充联结词的扩充1. 一元运算：一元运算：我我们们来来看看一一个个命命题题变变元元在在一一个个一一元元运运算算的的作作用用下下可能的真值表。可能的真值表。Pf1f2f3f40001110101循真债兆仰县赐笋默罩袋晚艘鸿选发冬汪究机发均狐滁线抉戒膨凯鼻硬宛离散数学IIppt课件离散数学IIppt课件52/731.3 联结词的完备集联结词的完备集因因此此，最最多多只只能能定定义义4种种运运算算，但但除除了了否否定定之之外外，永永假假，永永真真，恒恒等等作作为为运运算算意意义义不不大大，所所以以一一般般不不再再定定义义其其它一元运算。它一元运算。2.二
54、元运算：二元运算：考虑两个变元在一个二元运算作用下可能的真值表。考虑两个变元在一个二元运算作用下可能的真值表。PQf1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16000100011100011011010010010011011101100001001010110111110000100101101111永假或非蕴含否定蕴含否定合取非P非Q等价异或恒等Q恒等P与非蕴含析取蕴含永真 惕窿碗某瑶咯褥其粱装煽松求枚或猖貉感弄过栋奥剿关强渍钢钙场礼己札离散数学IIppt课件离散数学IIppt课件53/731.3 联结词的完备集联结词的完备集：已定义；：已定义；：意义不大；
55、：意义不大；：可再定义：可再定义f1=PP=F，f2= (PQ)，f3= (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都是两个联结词的组都是两个联结词的组合，为了叙述方便，可以引进下列几个联结词：合，为了叙述方便，可以引进下列几个联结词：云歇钎房炳疤伎喘肾墅游香碱烙四缩海柳僧耙颠糯歧宠曰钙鳃词泉戌赊蛇离散数学IIppt课件离散数学IIppt课件54/731
56、.3 联结词的完备集联结词的完备集联结词联结词记号记号复合命题复合命题读法读法记法记法备注备注f9异或P不可兼或QP异或QPQ逻辑电路中的异或门f3，f4蕴含否定P和Q的蕴含否定P蕴含否定QP Qf12与非P和Q的与非P与非QPQ逻辑电路中的与非门f2或非P和Q的或非P或非QPQ逻辑电路 中的或非门P QP Q (PQ) (PQ) ，P QP Q (PQ) (PQ) ，PQPQ (P(PQ) Q) ， PQPQ (P(PQ) Q) ， 这这这这9 9个联结词构成命题演算中的所有联结词。个联结词构成命题演算中的所有联结词。个联结词构成命题演算中的所有联结词。个联结词构成命题演算中的所有联结词。吉
57、讣影孟迎训兆翟娃汕痘唤政接礁游斌犹烹渝襄奈呆模指包暗模婿爵漾递离散数学IIppt课件离散数学IIppt课件55/731.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.异或的性质：异或的性质：P QP Q Q PQ P， P (Q R) P (Q R) (P Q) RP Q) R P P 0，0 P P， 1 P P沽乏肃胞硝壬想筏媒譬棍骂倔绍笼羽邱宏趟郊攻帆权梗
58、涂恳喀烤衣遂蹦烹离散数学IIppt课件离散数学IIppt课件56/731.3 联结词的完备集联结词的完备集1.3.3：全功能联结词：全功能联结词定义定义1.15：设设S是联结词的集合，是联结词的集合，(1)用用S中的联结中的联结词表示的公式，可以等价地表示任何命题公式，词表示的公式，可以等价地表示任何命题公式，则称则称S是一个联结词完备集是一个联结词完备集 (或全功能集合或全功能集合) (Adequate Set of Connectives)，(2)S是一个联结词是一个联结词的完备集，且的完备集，且S中无冗余的联结词中无冗余的联结词(即集合中不存即集合中不存在可以被其中的其它联结词所定义的联
59、结词在可以被其中的其它联结词所定义的联结词)，则，则称称S为极小联结词完备集。为极小联结词完备集。由前面由前面1.3.1的分析知，的分析知，,是一个联是一个联结词完备集，而结词完备集，而ABAB， AB(AB)(BA)，所以，所以，是冗余的，是冗余的，故故,也是一个联结词完备集也是一个联结词完备集,而而AB(AB)，所以，所以也是冗余的也是冗余的, ,也是一个联结词完备集，进一步地也是一个联结词完备集，进一步地,可知可知,是一个极小联结词完备集。是一个极小联结词完备集。伴养牌渐只殉吐讣哨元锹乱蛮月我跪钠达菇每桌篇赋茄灯度律篙伎沦命皇离散数学IIppt课件离散数学IIppt课件57/731.3
60、联结词的完备集联结词的完备集证明联结词完备集证明联结词完备集,是一个极小的。是一个极小的。同理，同理，,，, ，, 也是极小完备集，也是极小完备集，此外由此外由1.3.2中中，的性质可知的性质可知 ，也是也是极小完备集；极小完备集；, 及其子集不是完备集；及其子集不是完备集；实际应用中经常采取的联结词集合为实际应用中经常采取的联结词集合为,。例例1.13：试将公式试将公式(P(QR)(PQ)用仅含用仅含 ，的公式等价地表示出来。的公式等价地表示出来。饼死号怖地捶厦脊九该绢扩匪碰洋癣铂捕母虹斤惑键样按躬西炒秦奠爷霉离散数学IIppt课件离散数学IIppt课件58/731.4：范式：范式1.4.1
61、：范式：范式 对于给定公式的判定问题，可用真值表方法加以解对于给定公式的判定问题，可用真值表方法加以解释，但当公式中命题变元的数目较大时，计算量释，但当公式中命题变元的数目较大时，计算量较大，每增加一个命题变元，真值表的行数要翻较大，每增加一个命题变元，真值表的行数要翻倍，计算量加倍，此外，对于同一问题，可以从倍，计算量加倍，此外，对于同一问题，可以从不同的角度去考虑，产生不同的但又等价的命题不同的角度去考虑，产生不同的但又等价的命题公式，即同一个命题可以有不同的表达形式。这公式，即同一个命题可以有不同的表达形式。这样给命题演算带来了一定的困难，因此，有必要样给命题演算带来了一定的困难，因此，
62、有必要使命题公式规范化，为此，引入了范式的概念。使命题公式规范化，为此，引入了范式的概念。惟多花瞳堤币乓蔚蓉盂慑函彬束刺硬剑刀斜渗铆旨诱圣绪泛候龋选缮领总离散数学IIppt课件离散数学IIppt课件59/731.4：范式：范式定义定义1.16： (1)：命题变元或命题变元的否定称为文字；：命题变元或命题变元的否定称为文字； (2)：有限个文字的析取式称为简单析取式：有限个文字的析取式称为简单析取式(基本和基本和)，有限个文字的合取式称为简单合取式，有限个文字的合取式称为简单合取式(基本积基本积)； (3)：由有限个简单合取式构成的析取式称为析取：由有限个简单合取式构成的析取式称为析取范式范式(
63、Disjunctive Normal From)，由有限个简单，由有限个简单析取式构成的合取式称为合取范式析取式构成的合取式称为合取范式(Conjunctive Normal From)。秋费坑郎整敌嘻合纲床黑酝廓漓糯绵到胎井驶蔫浇态候铜癸遂葵遭醇第渔离散数学IIppt课件离散数学IIppt课件60/731.4：范式：范式例如，例如， ：P，P ；：PQ R； ：PQR；：(PQ)(PQ)； ：(PQ)(PQ)；性质：性质： (1)：一个文字既是一个析取范式又是一个合取范：一个文字既是一个析取范式又是一个合取范式；式； (2)：一个析取范式为矛盾式，当且仅当它的每个：一个析取范式为矛盾式，当且
64、仅当它的每个简单合取式是矛盾式；简单合取式是矛盾式； (3)一个合取范式为重言式，当且仅当它的每个简一个合取范式为重言式，当且仅当它的每个简单析取式是重言式。单析取式是重言式。峦咎沟处诊诵慧位延睬综拙早掂甭吊迂迅戊纫鞍羽掉始疹沦磐戊盲葡呈必离散数学IIppt课件离散数学IIppt课件61/731.4：范式：范式定理定理1.7：任一命题公式都存在着与之等值的析取任一命题公式都存在着与之等值的析取范式和合取范式。范式和合取范式。例例1.14：求公式求公式(PQ) (PR)的析取范式和合的析取范式和合取范式。取范式。碎摄涎扭栽宽萎发仇统佑厩肖五含林到堵狐纳既塔产笨岩蓝田睡赖渔挽想离散数学IIppt课
65、件离散数学IIppt课件62/731.4：范式：范式1.4.2：主析取范式和主合取范式：主析取范式和主合取范式 范式虽然为命题公式提供了一种统一的表达形式，范式虽然为命题公式提供了一种统一的表达形式，但这种表达形式却并不是唯一的。如公式但这种表达形式却并不是唯一的。如公式(PQ)(PR)与之等价的公式有：与之等价的公式有：P(QR)，(PP)(QR) ，P(QQ)(QR)，P(PR)(QR),等，这种不唯一的表达形式等，这种不唯一的表达形式给研究问题带来了不便，因此有必要引进更为标给研究问题带来了不便，因此有必要引进更为标准的范式。准的范式。定义定义1.17：(1)包含包含A中所有命题变元或其
66、否定一次中所有命题变元或其否定一次仅一次的简单合取式，称为极小项；仅一次的简单合取式，称为极小项；(2)包含包含A中中所有命题变元或其否定一次仅一次的简单析取式，所有命题变元或其否定一次仅一次的简单析取式，称为极大项；称为极大项；(3)由有限个极小项组成的析取范式由有限个极小项组成的析取范式称为主析取范式；称为主析取范式； (4)由有限个极大项组成的合取由有限个极大项组成的合取范式称为主合取范式。范式称为主合取范式。筹颂嘴潍浇游衙津笆愉痰壹叁栅宠诵甚臃褐浸谓忧沾讥印徒驭搀酌隐渝爸离散数学IIppt课件离散数学IIppt课件63/731.4：范式：范式1.极小项和极大项的性质极小项和极大项的性质
67、 对于两个命题变元对于两个命题变元P，Q来说，由于每个来说，由于每个P，Q可以取可以取命题变元自身和其否定，所以其对应的极小项和极命题变元自身和其否定，所以其对应的极小项和极大项分别有四项：大项分别有四项：PQ， PQ，PQ，PQ；PQ， PQ, PQ， PQ。其真。其真值表如下：值表如下：一般来说，对于一般来说，对于n个命题变元，则应有个命题变元，则应有 个不同的极个不同的极小项和小项和 个不同的极大项。个不同的极大项。PQPQPQPQPQPQPQPQPQ0000011110010100110110001010111110000111善漾陋仁歹秩剿厩缩定澳侵癣呼汤长痪显韭脐澜涪崔埔笔肌蛆鸥谢
68、此唁涕离散数学IIppt课件离散数学IIppt课件64/731.4：范式：范式性质：性质：(1)：没有两个不同的极小项是等价的，且每个极小：没有两个不同的极小项是等价的，且每个极小项只有一组真值指派使该极小项的真值为真，因此项只有一组真值指派使该极小项的真值为真，因此可给极小项编码，使极小项为可给极小项编码，使极小项为“T”和那组真值指和那组真值指派为对应的极小项编码；如极小项派为对应的极小项编码；如极小项PQR只只有在有在P，Q，R分别取真值分别取真值0，0，0时才为真，所以时才为真，所以有时又可用有时又可用 ( )来表示，又如来表示，又如PQR也可也可用用 ( )来表示。来表示。(2)：没
69、有两个不同的极大项是等价的，且每个极大：没有两个不同的极大项是等价的，且每个极大项只有一组真值指派，使该极大项的真值为假。因项只有一组真值指派，使该极大项的真值为假。因此可给极大项编码，使极大项为此可给极大项编码，使极大项为“F”的那组真值的那组真值指派为对应的极大项的编码，如极大项指派为对应的极大项的编码，如极大项PQR只有在只有在P，Q，R分别取真值分别取真值1，1，1时才为假，所以有时又可用时才为假，所以有时又可用 来表示。来表示。绪怠熟崩寄输吨卤洛液暴吕我通宫蔗巧覆脑叶傈顺侯撤喧撰宜弯码巩阐炒离散数学IIppt课件离散数学IIppt课件65/731.4：范式：范式 三个命题变元的真值取
70、值与极小项和极大项的对应三个命题变元的真值取值与极小项和极大项的对应对位关系表：对位关系表：PQR极小项极小项极大项极大项000m0= PQRM0= PQR001m1= PQRM1= PQR010m2= PQRM2= PQR011m3= PQRM3= PQR100m4= PQRM4= PQR101m5= PQRM5= PQR110m6= PQRM6= PQR111m7= PQRM7= PQR笼靛净肾臆姚拦躇列杭搭循讼体煎妒油位寺佑缉狗轻汲碳酥遂驰丁彬器钱离散数学IIppt课件离散数学IIppt课件66/731.4：范式：范式(3)：任意两极小项的合取必假，任意两个极大项的：任意两极小项的合取必
71、假，任意两个极大项的析取必为真。极大项的否定是极小项，极小项的否析取必为真。极大项的否定是极小项，极小项的否定是极大项，即定是极大项，即(4)：所有极小项的析取为永真公式，所有极大项的：所有极小项的析取为永真公式，所有极大项的合取是永假公式，即合取是永假公式，即律儿碾憨涉祝曝脾芬阿必唯凯瘁肌茁锚委穆索壁怔笑敝垄摔宰呆施泼手污离散数学IIppt课件离散数学IIppt课件67/731.4：范式：范式2.主析取范式和主合取范式的存在性和唯一性主析取范式和主合取范式的存在性和唯一性定理定理1.8：任何命题公式的主析取范式和主合取范任何命题公式的主析取范式和主合取范式存在且唯一，即任何命题公式都有且仅有
72、一个式存在且唯一，即任何命题公式都有且仅有一个与之等价的主合取范式和主析取范式。与之等价的主合取范式和主析取范式。真值表技术真值表技术例例1.15：求命题公式求命题公式(PQ)R)(PQ)的主析的主析取范式。取范式。例例1.16：求命题公式求命题公式(PQ)R的主合取范式。的主合取范式。乌磐哑娘穴灼伸嚎痴菇靳脉罪萌峡和芽反抛挺酿革肉贵蟹猾酵豁帝铭渊毙离散数学IIppt课件离散数学IIppt课件68/731.4：范式：范式利用真值表技术求主析取范式和主合取范式的方法：利用真值表技术求主析取范式和主合取范式的方法： ：选出公式的真值结果为真的所有行，在这样的：选出公式的真值结果为真的所有行，在这样
73、的行中，找到其每一个解释所对应的极小项，将这行中，找到其每一个解释所对应的极小项，将这些极小项析取即可得到相应的主析取范式；些极小项析取即可得到相应的主析取范式；：选出公式的真值结果为假的所有行，在这样的：选出公式的真值结果为假的所有行，在这样的行中，找到其每一个解释所对应的极大项，将这行中，找到其每一个解释所对应的极大项，将这些极大项合取即可得到相应的主合取范式。些极大项合取即可得到相应的主合取范式。研强颧闲驯衔蛙技少仍碑德蹦馋搓瞪秀蔼傣虹玛化遂逞疾季梦箩径环棒昆离散数学IIppt课件离散数学IIppt课件69/731.4：范式：范式公式转换法公式转换法唯一性：唯一性： 设任一命题公式设任一
74、命题公式A有两个主析取范式有两个主析取范式B和和C，则因为，则因为AB， AC，所以，所以BC，若，若B，C是是A的的(在不计极小项的顺序的情况下在不计极小项的顺序的情况下)不同的主析取范不同的主析取范式，则必有在存在极小项式，则必有在存在极小项mi，mi只存在于只存在于B，C之之一中，不妨设一中，不妨设mi在在B中中,而不在而不在C中，因此中，因此i之二进之二进制表示制表示B的一个真值解释，而对于的一个真值解释，而对于C则为真值为假则为真值为假的解释，这与的解释，这与BC矛盾，所以矛盾，所以B和和C相同，同理相同，同理主合取范式也是唯一的。主合取范式也是唯一的。例例1.17：利用公式的等价求
75、利用公式的等价求G=(PQ)R的主析取的主析取范式和主合取范式范式和主合取范式甭胜却峰今垂尹识挥撒骂挚箍汪龋椭糠纯丹萤柏舟看雅僻胀幌谴缆霞眉淳离散数学IIppt课件离散数学IIppt课件70/731.4：范式：范式3：主合取范式和主析取范式之间的转换：主合取范式和主析取范式之间的转换 真值表技术和公式转换方式在求主析取范式和主合真值表技术和公式转换方式在求主析取范式和主合取范式各有其优点，在公式中的命题变元较少时取范式各有其优点，在公式中的命题变元较少时时，利用真值表技术更为简单。当命题变元较多时，利用真值表技术更为简单。当命题变元较多时，一般采用公式转换法，而在公式转换中，有时，一般采用公式
76、转换法，而在公式转换中，有时求主析取范式更为方便，而有时求主合取范式时求主析取范式更为方便，而有时求主合取范式更为方便。但两者之间必然有相应的关系。下面更为方便。但两者之间必然有相应的关系。下面介绍一种两者之间的转换方法。介绍一种两者之间的转换方法。从盂伊掣尚域铱栅美颊彻霍肾躁官蠕棉酿酱诺轴验卿建黎挟衷柜湖柱谰挨离散数学IIppt课件离散数学IIppt课件71/731.4：范式：范式(1)：已知公式：已知公式G的主析取范式求公式的主析取范式求公式G的主合取范的主合取范式的步骤如下：式的步骤如下： a：求：求G的主析取范式，即的主析取范式，即G的主析取范式中没有出的主析取范式中没有出现过的极小项
77、的析取现过的极小项的析取 b：G(G)即是即是G的主合取范式的主合取范式 即：若即：若 为为G的主析取范式，则的主析取范式，则 为为G的主析取范式，其中的主析取范式，其中 后剩下的极小项。则后剩下的极小项。则 为为G的主合取范式。的主合取范式。 颖看些碳蝎瞧列圾骑疚贤往赁强关限孰尤江壕惭今诸伶胎控找谷潦媳媚泊离散数学IIppt课件离散数学IIppt课件72/731.4：范式：范式(2)：已知公式：已知公式G的主合取范式，求的主合取范式，求G的主析取范式的主析取范式的步骤如下：的步骤如下：a：求：求G的主合取范式，即的主合取范式，即G的主合取范式中没有出的主合取范式中没有出现过的极大项的合取现过
78、的极大项的合取b： G(G)即是即是G的主析取范式，的主析取范式，即，若即，若 为为G的主合取范式，则的主合取范式，则 为为G的主合取范式。其中的主合取范式。其中后剩下的极大项。后剩下的极大项。则则为为G的主析取范式的主析取范式槛蛙沈巧铅粱掉仲格炔复坍铺罪京朽颅钮畴答龙棒贷挥卤蛰悟转缸嘲愉蚕离散数学IIppt课件离散数学IIppt课件73/731.4：范式：范式例例1.18：设设G=(PQ)(PR)(QR),求其求其对应的主析取范式和主合取范式对应的主析取范式和主合取范式性质：性质：(1)：如果命题公式是永真公式：如果命题公式是永真公式它的主析取范式它的主析取范式包含所有极小项，此时主合取范式
79、不含有任何极包含所有极小项，此时主合取范式不含有任何极大项，为空，记大项，为空，记1或或T(2)：如果命题公式是永假公式：如果命题公式是永假公式它的主合取范式它的主合取范式包含所有极大项，此时主析取范式不含有任何极包含所有极大项，此时主析取范式不含有任何极小项，为空，记小项，为空，记0或或F(3)：两个命题公式：两个命题公式A，B，AB当且仅当当且仅当A与与B有有相同的真值表，又当且仅当相同的真值表，又当且仅当A与与B有相同的主析取有相同的主析取范式范式(主合取范式主合取范式)。(真值表和主范式是描述命题真值表和主范式是描述命题公式标准形式的两种不同的等价形式公式标准形式的两种不同的等价形式)
80、。圭玄进纳烷秃奉必端辣当再瞪蜒贴皱友柿到吩恃育村阅盼吧剪睛讯姻楚天离散数学IIppt课件离散数学IIppt课件74/731.5：命题逻辑的推理理论：命题逻辑的推理理论1.5.1：推理的基本概念和推理形式：推理的基本概念和推理形式 推理也称论证，它是指从前提出发推出结论的思推理也称论证，它是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题形式。前提出发应用推理规则推出的命题形式。定义定义1.18：设设G1，G2，Gn，H是命题公式，是命题公式，若对于若对于G1，G2，Gn，H中出现的命题变元的中出现的命题变
81、元的任意一组赋值，或者任意一组赋值，或者G1G2Gn为假，或者当为假，或者当G1G2Gn为真，为真，H也为真，则称也为真，则称H是是G1，G2，Gn的有效结论的有效结论(Efficacious Conclusion)或逻辑结果或逻辑结果(Logic Conclusion)。 G1，G2，Gn仍为一组前提仍为一组前提(Premise)。记。记G2，Gn推推理理H为为G2，GnH，若正确推理，则记为，若正确推理，则记为G2，GnH。孝酷垛买跪嫩击萌乃侄沼笼顿啮良逻歇藩蕉葛杯肥挎削褪枯蔽夜乔淖吩历离散数学IIppt课件离散数学IIppt课件75/731.5：命题逻辑的推理理论：命题逻辑的推理理论定理
82、定理1.9：命题公式命题公式G1，G2，Gn推出结论推出结论H的的推理正确或公式推理正确或公式H是前提条件是前提条件G1，G2，Gn的逻辑结果，当且仅当的逻辑结果，当且仅当(G1G2Gn) H为重为重言式。言式。 =：逻辑蕴含关系，：逻辑蕴含关系， G=H不是命题公式，计算不是命题公式，计算机判断机判断G=H办不到；办不到； ：蕴含联结词，：蕴含联结词，G H是命题公式，计算机可判是命题公式，计算机可判断断G H为永真公式。为永真公式。 因此我们可以用蕴含式来描述推理。因此我们可以用蕴含式来描述推理。 我们将由我们将由G1，G2，Gn推理推理H，用蕴含式表，用蕴含式表示为：示为： (G1G2G
83、n) H 将由将由G1，G2，Gn正确推理出正确推理出H，用蕴含式，用蕴含式表示为：表示为： G1G2Gn =H鲤胁湍臣弓讽峻壬凶丁皂删棍镊誊晌潭耙载访京旷互再些乌壳辟赶枕野勤离散数学IIppt课件离散数学IIppt课件76/731.5：命题逻辑的推理理论：命题逻辑的推理理论推理的形式结构为：推理的形式结构为：G1G2Gn H，书写为：，书写为：前提：前提： G1，G2，Gn结论：结论：H推理的有效性判断，即判断推理是否正确，也就是推理的有效性判断，即判断推理是否正确，也就是判断判断G1G2GnH是否为重言式。是否为重言式。1.5.2：判断结论有效的方法：判断结论有效的方法1.真值表法；真值表
84、法；2.等值演算法；等值演算法；3.主析取范式法主析取范式法勉抄吱亩漓暑梨俺镑蹿婴唇啡既拭某秒镭臻慑且缸味吠骆轩秉褪请衷惟扦离散数学IIppt课件离散数学IIppt课件77/731.5：命题逻辑的推理理论：命题逻辑的推理理论1.真值表法真值表法 设设P1，P2，Pn是出现在前提是出现在前提G1，G2， ，Gn和结论和结论H中的一切命题变元，如果将中的一切命题变元，如果将P1，P2，Pn中所有可能的解释及中所有可能的解释及G1，G2， ，Gn，H的对应真值结果都在一个表中，根据的对应真值结果都在一个表中，根据“”的定的定义，则有如下判断方法：义，则有如下判断方法：(1)对所有对所有G1，G2，
85、，Gn都具有真值都具有真值T的行的行(表表示前提为真的行示前提为真的行)，如果在每个这样的行中，如果在每个这样的行中，H也也具有真值具有真值T，则，则H是是G1，G2， ，Gn的逻辑结果；的逻辑结果；(2)对所有对所有H具有真值为具有真值为F的行的行(表示结论为假的行表示结论为假的行)，如果在每一个这样的行中，如果在每一个这样的行中， G1，G2， ，Gn中至少有一个公式的真值为中至少有一个公式的真值为F(前提也为假前提也为假)。则。则H是是G1，G2， ，Gn的逻辑结果。的逻辑结果。凰桔际悍黄甭延批桂睁普兑颤桩楔窒毡唤哉丹谜瘦漳圈埂荐颠面检屏俩链离散数学IIppt课件离散数学IIppt课件7
86、8/731.5：命题逻辑的推理理论：命题逻辑的推理理论例例1.18：判断下列判断下列H是否为前提是否为前提G1，G2的逻辑结的逻辑结果。果。 (1). H：Q; G1：P，G2：PQ； (2). H：P; G1：PQ ，G2：Q； (3). H：Q; G1： P，G2：PQ；2.等值演算法等值演算法直接用等值演算来判断推理的形式结构是否是重言直接用等值演算来判断推理的形式结构是否是重言式。式。例例1.19：下午马芳或去看电影或去游泳。她没去下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。看电影。所以，她去游泳了。劣擂悍侧迢俐孕轻绝造夕净擞蔼阻瞧邓钙助孝周付刮央阁孜粉撩番咒国缩离散数
87、学IIppt课件离散数学IIppt课件79/731.5：命题逻辑的推理理论：命题逻辑的推理理论3.主析取范式法主析取范式法将推理的形式结构转化为主析取范式，但仍判断其将推理的形式结构转化为主析取范式，但仍判断其是否为重言式。是否为重言式。例例1.20：若下午气温超过若下午气温超过30，则王小燕必去游，则王小燕必去游泳。若她去游泳，她就不去看电影了。所以，若泳。若她去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温超过了王小燕没去看电影，下午气温超过了30 。以上方法，当形式结构比较复杂，特别是所含的命以上方法，当形式结构比较复杂，特别是所含的命题变元较多时，一般很不方便，下面介绍构造
88、证题变元较多时，一般很不方便，下面介绍构造证明法。明法。迹宜怀糖吊旬熏贝檀蝇楔感榜葛专巍志缘扰芒吨考匣摩崇埃舱扯新潦最昆离散数学IIppt课件离散数学IIppt课件80/731.5：命题逻辑的推理理论：命题逻辑的推理理论1.5.3：构造证明法：构造证明法构造证明法是依据一些公认的推理规则，从前提出构造证明法是依据一些公认的推理规则，从前提出发，推导结论，它可以看作公式的序列，其中每发，推导结论，它可以看作公式的序列，其中每个公式都是按照事先规定的规则得到的，且可将个公式都是按照事先规定的规则得到的，且可将所用的规则在公式后写明，该系列最后一个公式所用的规则在公式后写明，该系列最后一个公式是所要
89、证明的结论。是所要证明的结论。(1)推理规则：推理规则：前提引入规则：在推理的任何步骤上都可以引入前提引入规则：在推理的任何步骤上都可以引入前提；前提；结论引入规则：在推理的任何步骤上所得到的结结论引入规则：在推理的任何步骤上所得到的结论都可以做为后续证明的前提；论都可以做为后续证明的前提；置换规则：在推理的任何步骤上，命题公式的子置换规则：在推理的任何步骤上，命题公式的子公式都可以用与之等价的公式置换，得到公式序公式都可以用与之等价的公式置换，得到公式序列中又一个公式。列中又一个公式。答酚割蔷舔址眺玩疆畏茬张羔篮枝奔犊而除腋垛汲瑞聂柔达潮置造家谰巨离散数学IIppt课件离散数学IIppt课件
90、81/731.5：命题逻辑的推理理论：命题逻辑的推理理论(2)推理定理：推理定理：(一些重要的永真蕴含式一些重要的永真蕴含式)1.A=(AB) 附加律附加律2.AB=A 化简律化简律3.(AB) A =B 假言真理假言真理4 .(AB) B =A 拒取式拒取式5.(AB) B =A 析取三段论析取三段论6 .(AB) (BC) =AC 假言三段论假言三段论7 .(AB) (BC) =AC 等价三段论等价三段论8 .(AB)(CD)(AC) =(BD) 构造性二难构造性二难(AB)(AB)(AA) =B构造性二难构造性二难(特殊形式特殊形式)9 .(AB)(CD)(BD) =(AC)破坏性二难破
91、坏性二难堰衬戊事谎衬伶吓堆屎殖俘倦盎士佯睫绝萎淀辩抛迟瞻傍决施塑锚苞厦他离散数学IIppt课件离散数学IIppt课件82/731.5：命题逻辑的推理理论：命题逻辑的推理理论由着由着9个定律中的个定律中的8个可以得到个可以得到8个推理规则：个推理规则：附加规则：附加规则：A|=(AB)化简规则：化简规则：(AB)|=A假言推理规则：假言推理规则：(AB) ，A |=B拒取式规则：拒取式规则：(AB)，B|=A 假言三段论规则：假言三段论规则：(AB)，(BC)|=(AC)析取三段论规则：析取三段论规则：(A B)，B|=A 构造性二难规则：构造性二难规则：(AB)，(CD)，(AC) |=(BD
92、) 破坏性二难规则：破坏性二难规则：(AB)，(CD)，(BD) |=(AC) 合取引入规则：合取引入规则：A，B|=(AB)朔标抉散撅钩授予荫哄著犯宙罗床边沧责飘习剂蓬蚁最腹橱代足搽雄奎硬离散数学IIppt课件离散数学IIppt课件83/731.5：命题逻辑的推理理论：命题逻辑的推理理论例例1.21：构造下列推理的证明：构造下列推理的证明：前提：前提：p q，p r，s t，s r，t结论：结论：q例例1.22：分析下列事实：分析下列事实：“早饭我吃面包或蛋糕；早饭我吃面包或蛋糕；如果我吃面包，那么我还要喝牛奶；如果我吃蛋如果我吃面包，那么我还要喝牛奶；如果我吃蛋糕，那么我还要喝咖啡；但我没
93、有喝咖啡，所以糕，那么我还要喝咖啡；但我没有喝咖啡，所以早饭我吃的是牛奶和面包。早饭我吃的是牛奶和面包。”写出前提和有效结写出前提和有效结论并证明之。论并证明之。例例1.23：用构造法证明，找出下列推理的有效结用构造法证明，找出下列推理的有效结论。论。 如果我考试通过了，那么我很快乐；如果我快乐，如果我考试通过了，那么我很快乐；如果我快乐，那么阳光灿烂；现在是晚上那么阳光灿烂；现在是晚上11点，天很暗。点，天很暗。兄掸胎镐勃鳞懒刻呜埋倡偏钳祥及卫亮被决动裁摇哪戒棵翼膜翅阿迷荷眶离散数学IIppt课件离散数学IIppt课件84/731.5：命题逻辑的推理理论：命题逻辑的推理理论(3)P1P2Pn
94、 (P Q)形式命题的证形式命题的证明。明。附加前提证明法附加前提证明法(CP规则规则)若若P1，P2，Pn ，P|= Q，则，则P1，P2，Pn |= PQ附加前提证明法的意义在于：当推理的结论是蕴含附加前提证明法的意义在于：当推理的结论是蕴含式时，可以将其前件作为附加前提引用，只要能式时，可以将其前件作为附加前提引用，只要能推理出其后件，则原推理成立。推理出其后件，则原推理成立。例例1.24：如果如果A参加球赛，则参加球赛，则B或或C也将参加球赛。也将参加球赛。如果如果B参加球赛，则参加球赛，则A不参加球赛。如果不参加球赛。如果D参加球参加球赛，则赛，则C不参加球赛。所以，不参加球赛。所以
95、，A若参加球赛，则若参加球赛，则D不参加球赛。不参加球赛。缉鼎极绸澜襄赫谴效葵见星毫涣磊盂贮松讣炕骸康孤潦粱统彩锹洪宵焰另离散数学IIppt课件离散数学IIppt课件85/731.5：命题逻辑的推理理论：命题逻辑的推理理论例例1.25：设前提条件设前提条件T=P(QS)，RP，Q,公式公式G=R S，证明，证明T|=G。(4)反证法反证法(归谬法归谬法)定义定义1.19：设设G1，G2，Gn是一组命题公式是一组命题公式P1，P2，Pn是出现在是出现在G1，G2，Gn中的一中的一切命题变元，切命题变元，I是它的任意解释，若有解释是它的任意解释，若有解释I使使G1G2Gn取值为取值为“真真”，则称
96、公式，则称公式G1，G2，Gn是一致的是一致的(Consistency)。如对任意。如对任意的解释的解释I，都有，都有G1G2Gn取值为取值为“假假”，则称公式则称公式G1，G2，Gn是不一致的是不一致的(Inconsistency),或者说或者说G1G2Gn是一是一个矛盾式。个矛盾式。腊位爷把湿私勤鄂责原毅朴靠渡萌乱谱楔犬坪欢您位线弱昌呀这堑栽子案离散数学IIppt课件离散数学IIppt课件86/731.5：命题逻辑的推理理论：命题逻辑的推理理论定理定理1.10：设命题公式集合设命题公式集合G1，G2，Gn是是一致的，于是从前提集合一致的，于是从前提集合G1，G2，Gn出发出发可以逻辑地推出
97、公式可以逻辑地推出公式H的充要条件是从前提集合的充要条件是从前提集合G1，G2，Gn，H出发，可以逻辑推出一个出发，可以逻辑推出一个矛盾式来。矛盾式来。由定理知：由定理知：归谬法：将结论的否定作为附加前提引入，公式序归谬法：将结论的否定作为附加前提引入，公式序列的最后得到一矛盾式，则原结论成立。列的最后得到一矛盾式，则原结论成立。莎威效昏惠逸汾溪畔胸就毯色媚耿轰负假脐以冉瘫两凝领靶蜕颖撂锯泅墓离散数学IIppt课件离散数学IIppt课件87/731.5：命题逻辑的推理理论：命题逻辑的推理理论例例1.26：证明：证明：p (q r)|=(p q) (p r)例例1.27：证明下面论述的有效性：在
98、意甲比赛中，证明下面论述的有效性：在意甲比赛中，假如有四只球队，其比赛情况如下：如果国际米假如有四只球队，其比赛情况如下：如果国际米兰夺冠，则兰夺冠，则AC米兰或尤文图斯获亚军；若尤文图米兰或尤文图斯获亚军；若尤文图斯获亚军，国际米兰队不能获得冠军，若拉齐奥斯获亚军，国际米兰队不能获得冠军，若拉齐奥队获得亚军，则队获得亚军，则AC米兰队不能获得亚军；最后，米兰队不能获得亚军；最后，国际米兰夺冠。所以拉齐奥队不能获得亚军国际米兰夺冠。所以拉齐奥队不能获得亚军井瘤疾盆苫抓我欣切丈伴珠楷丢腊肘纤薪亿使焊彝吗励嗓揣蜘嘿哆挪笔酵离散数学IIppt课件离散数学IIppt课件88/731.6：命题演算的自然
99、推理形式系统：命题演算的自然推理形式系统1.形式系统的基本概念形式系统的基本概念 永真式是命题逻辑推理中一个非常基本的重要概念，永真式是命题逻辑推理中一个非常基本的重要概念，为了系统研究它们，就需要把所有的永真式包括为了系统研究它们，就需要把所有的永真式包括在一个系统内，作为一个整体来研究，这样的系在一个系统内，作为一个整体来研究，这样的系统应当是一个形式系统，也只有形式系统，才能统应当是一个形式系统，也只有形式系统，才能进行充分的研究，从而掌握全部规律。进行充分的研究，从而掌握全部规律。 在形式系统中，用符号语言来表达原始概念和用于在形式系统中，用符号语言来表达原始概念和用于推演的逻辑规则，
100、决定一切的是符号串和符号串推演的逻辑规则，决定一切的是符号串和符号串之间的关系，合法符号串的识别，系统内的推演之间的关系，合法符号串的识别，系统内的推演都可以根据合法符号串而形成规则和推理规则都可以根据合法符号串而形成规则和推理规则(符符号串之间的关系号串之间的关系)机械的完成；只有这样的系统，机械的完成；只有这样的系统，才是本质上能做符号变换的计算机可以接受的。才是本质上能做符号变换的计算机可以接受的。蓟壕萄曼厌剁韵加潭屡掺外反党澄革云栋篇脯骗够韵肃峻马助廊谱葱亢勇离散数学IIppt课件离散数学IIppt课件89/731.6：命题演算的自然推理形式系统：命题演算的自然推理形式系统形式系统一般
101、有以下几个部分组成形式系统一般有以下几个部分组成(1).字母表：由不加定义而采用的符号组成，字母字母表：由不加定义而采用的符号组成，字母表指此形式系统可以使用的符号；表指此形式系统可以使用的符号；(2).字母表上符号串的一个子集字母表上符号串的一个子集Form：Form中的中的元素称为公式，元素称为公式，Form指此形式系统可以使用的符指此形式系统可以使用的符号串；号串；(3).Form的一个子集是的一个子集是Axiom： Axiom中的元素称中的元素称为公理，为公理， Axiom指此形式系统一开始便接受而不指此形式系统一开始便接受而不加证明的定理；加证明的定理；(4).推理规则系推理规则系R
102、ule：Rule中的元素称为推理规则，中的元素称为推理规则，Rule规定了公式间的转换关系。规定了公式间的转换关系。吕蜒蒋仲傲续适吴奶血扒饮租叁走突贵凶时匠膀羡低潍腥昨岭渐抿内劈冉离散数学IIppt课件离散数学IIppt课件90/731.6：命题演算的自然推理形式系统：命题演算的自然推理形式系统对于一个形式系统，对于一个形式系统，Axiom和和Rule均可以为空，当均可以为空，当两者皆为空时，系统仅仅为一个语句生成系统，两者皆为空时，系统仅仅为一个语句生成系统，在数理逻辑中，如果在数理逻辑中，如果Axiom非空，则称为公理系统，非空，则称为公理系统，若若Axiom为空，则称为自然推理系统。为空
103、，则称为自然推理系统。对于一个具体的实际系统，用形式系统来描述，有对于一个具体的实际系统，用形式系统来描述，有两个具体的问题必须解决：两个具体的问题必须解决：(1).可靠性问题：形式系统中正确推理出来的公式，可靠性问题：形式系统中正确推理出来的公式，定理在所讨论的具体实际系统中是否为永真；定理在所讨论的具体实际系统中是否为永真；(2).完备性问题：具体实际系统中的永真的语句是完备性问题：具体实际系统中的永真的语句是否均为形式系统内的定理。否均为形式系统内的定理。 扔岁刹崩递伯确蜒窒氛填宜砰措输圣刮柏淆蜜哭想坛练薄搔惜顷朔跪撤巳离散数学IIppt课件离散数学IIppt课件91/731.6：命题演
104、算的自然推理形式系统：命题演算的自然推理形式系统2.命题演算的自然推理形式系统命题演算的自然推理形式系统P1)字母表：字母表： (1)命题符：命题符：p，q，r，p1，q1，r1， (2)联结词符：联结词符： ， ，； (3)括号与逗号括号与逗号(，)2)公式公式(同前面命题公式的定义同前面命题公式的定义)3)推理规则推理规则(用用1.5定义的定义的12条规则条规则)3.可靠性和完备性可靠性和完备性 （定理（定理1.9 ）(1)可靠性：如果可靠性：如果G1，G2，Gn |=H，则，则G1G2Gn H永真永真(2)完备性：反之完备性：反之注迎父妄罢鼎宝土津屋操罕佣栽哇暖致锈唤瓣贿倍杂哇孽诺氓九武过奖古离散数学IIppt课件离散数学IIppt课件
