资源描述：
《离散数学知识学习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2021/2/211离散数学第一章命题逻辑什么是逻辑学:逻辑学是一门研究思维形式及思维规律的科学。逻辑学的分类:辩证逻辑与形式逻辑。其中,辩证逻辑是以辩证法认识论的世界观为基础的逻辑学;形式逻辑主要是对人的思维形式结构和规律进行研究的类似于语法的一门工具性2021/2/212学科。思维的形式结构主要包括概念、判断和推理之间的结构和联系,其中概念是思维的基本单位,通过概念对事物是否具有某种属性进行肯定或否定的回答,这就是判断。由一个或几个判断推出另一判断的思维形式就是推理。研究推理有很多方法,用数学的方法研究推理的规律称为数理逻辑。所谓的数学方法
2、就是引进一套符号体系的方法,所以数理逻辑又称符号逻辑,它是从量的方面来研究思维规律的。2021/2/213现代数理逻辑分为证明论、模型论、递归函数论、公理化集合论等。在此我们介绍的是数理逻辑最基本的内容:命题逻辑和谓词逻辑。2021/2/214第一节命题与命题联结词什么是命题:能够判断真假的陈述语句。命题的真值:真（T或1)和假（F或0）命题的种类:简单命题（原子命题）与复合命题命题的表示:大写或小写英文字母或带下标的英文字母。表示命题的字母称为命题标识符。命题常量与命题变元:表示确定命题的标识符成为命题常量;仅仅表示命题的的位置标志的标识符称
3、为命题变元。2021/2/215注意:命题常量具有确定的真值;而命题变元可以标识任意命题,它不能确定真值,它本身也不是命题。常用的命题联结词1、否定定义:设P为一命题,P的否定是一个新的命题,记为P。若P为T,P为F,若P为F,P为T。2、合取定义:设P、Q是两个命题,P与Q的合取是一个复合命题,记为PQ。当且仅当P,Q2021/2/216P、Q同时为T时,PQ为T,否则PQ为F。注:①合取类似于自然语言中的“与”,“且”等,但又不完全相同。②合取是一个二元运算。3、析取定义:设P、Q是两个命题,P与Q的析取是一个复合命题,记为P
4、Q。当且仅当P,Q同为F时,PQ为F,否则PQ为T。注:①析取类似于自然语言中的“或”但也不完全一样。自然语言中的“或”分为二种,即:“排斥或”与“可兼或”。而析取表示的是自然语言中的“可兼或”2021/2/217②析取是二元运算。4、条件定义:给定两个命题P、Q,它们的条件命题是一个复合命题,记为PQ。当且仅当P为T,Q为F时,PQ为F,否则PQ为T.注:①在PQ中P成为前件,Q称为后件。②条件联结词与自然语言中的“如果那么”类似,但也不尽相同。③善意的推断2021/2/218④二元运算5、双条件定义:给定两个命题P、Q,它们
5、的双条件命题是一个复合命题,记为PQ。当且仅当P、Q的真值相同时,PQ为T,否则PQ为F.注:①双条件联结词与自然语言中的“当且仅当”,“充分必要”类似,但也不尽相同。②二元运算2021/2/219命题联结词除了上述五个之外,还有不可兼析取、条件否定、与非、或非联结词。在一个复合命题中往往含有多个命题联结词,其运算的次序是:、、、、第二节命题公式及其分类直观地说,由命题变元、命题常量、命题联结词、括号组成的一个有意义的式子成为命题公式。2021/2/2110定义:①命题常量、命题变元是命题公式②如果A是命题公式,则A是命题公式
6、③如果A、B是命题公式,则AB、AB、AB、AB也是命题公式④只有有限次地应用①——③产生的符号串才是命题公式。命题公式的赋值:命题公式的分类:重言式、矛盾式、可满足式2021/2/2111第三节等值演算等值的概念:设A,B是两个命题公式,p1,p2,,pn为出现在A,B中的所有的命题变元,如果对p1,p2,,pn的任何一种真值指派,A,B的真值都相同,则称A,B是等价（或等值）的。记为AB验证命题公式等值常用的方法有:真值表法、蕴含法、公式法（直接证法）。1、真值表法:例:证明AB(AB)(BA)2021/2/2112
7、2、蕴含法:定理1:设A,B是两个命题公式,则AB当且仅当AB为永真式。蕴含的定义:定义2:如果AB为永真式,则称A蕴含B,记为AB蕴含常见的性质:1、自反性2、传递性3、如果AB,AC,则ABC4、如果AC,BC,则ABC2021/2/2113由前面的例子和定理1我们马上可以得到定理2:AB当且仅当AB,BA分析蕴含的验证方法例1:证明:Q(PQ)P例2:证明:(PQ)PQ3、公式法常用的等值演算公式有24个。置换规则子公式:如果X是命题公式A的一部分,且X本身也是一个命题公式,则称X是命题
8、公式A的子公式。定理:（置换规则）设X是命题公式A的子公式,2021/2/2114如果XY,则将A中的X用Y置换所得到的命题公式B与A等价。例题:1
