1、离散数学离散数学【0232402324】主讲：王喜斌主讲：王喜斌希赛网希赛网 专业的在线教育平专业的在线教育平台台概述概述p 离散数学课程包括数理逻辑、集合论、离散数学课程包括数理逻辑、集合论、代数结构、图论等部分。代数结构、图论等部分。p 数理逻辑包括命题演算和谓词演算，数理逻辑包括命题演算和谓词演算，重点是公式演算与推理证明；重点是公式演算与推理证明；p 集合论的重点是关系理论与映射的描集合论的重点是关系理论与映射的描述；述；p 代数结构主要是从系统宏观的代数方代数结构主要是从系统宏观的代数方法去研究客观事物的各种性质与特征；法去研究客观事物的各种性质与特征；p 图论则着重于数形结合的描述
2、以及各图论则着重于数形结合的描述以及各种实际应用。种实际应用。概述概述p 国家自学考试时间为国家自学考试时间为150150分钟，在这段分钟，在这段时间内，如果不对离散数学的基础知时间内，如果不对离散数学的基础知识有扎实的功底，就不可能得到理想识有扎实的功底，就不可能得到理想的成绩。的成绩。p 考生一定要培养对概念、知识的熟练考生一定要培养对概念、知识的熟练运用。运用。p 真值表、主析取和主合取范式、集合真值表、主析取和主合取范式、集合关系运算、群环域及图论几部分，容关系运算、群环域及图论几部分，容易出现考试内容，所占分值较高，考易出现考试内容，所占分值较高，考生要重点掌握。生要重点掌握。概述概
3、述p 最后还要再提一下，基础知识是参加最后还要再提一下，基础知识是参加离散数学自学考试的关键，考查基础离散数学自学考试的关键，考查基础知识的基本题大约占试卷的百分之八知识的基本题大约占试卷的百分之八十左右，要求我们一定要重点掌握。十左右，要求我们一定要重点掌握。前面的选择和填空题都是考察对基本前面的选择和填空题都是考察对基本概念和原理的掌握情况，后面的分析概念和原理的掌握情况，后面的分析计算题是考查理解和运用能力。计算题是考查理解和运用能力。考核内容与考核要求考核内容与考核要求1.1.命题与命题联结词，要求达到命题与命题联结词，要求达到“领会领会”层次。层次。能对命题进行符号化；能对命题进行符
4、号化；掌握命题联结词，能够使用联结词熟练构掌握命题联结词，能够使用联结词熟练构造复合命题。造复合命题。2.2.命题公式的等值演算，要求达到命题公式的等值演算，要求达到“简单应用简单应用”层次。层次。掌握命题公式的概念，能够构造命题公式掌握命题公式的概念，能够构造命题公式的真值表，能够正确判断重言式、矛盾式的真值表，能够正确判断重言式、矛盾式和可满足公式。和可满足公式。熟记常用的命题定律和蕴含式，掌握命题熟记常用的命题定律和蕴含式，掌握命题公式的等值关系和蕴含关系，能够进行简公式的等值关系和蕴含关系，能够进行简单的公式论证。单的公式论证。3.3.联结词完备集，要求达到联结词完备集，要求达到“领会
5、领会”层次。层次。第1章 命题与命题公式重点：重点：1.1.命题与命题联结词，命题与命题联结词，2.2.将命题进行符号化，将命题进行符号化，3.3.命题公式的真值表，命题公式的真值表，4.4.命题公式的化简及命题的等值演算。命题公式的化简及命题的等值演算。难点：难点：1.1.命题公式的化简命题公式的化简2.2.等值演算及其应用等值演算及其应用第1章 命题与命题公式1.1 1.1 命题与命题联结词命题与命题联结词命题基本概念命题基本概念 数理逻辑的任务是采用数学方法研究抽象数理逻辑的任务是采用数学方法研究抽象的思维规律，研究的中心问题是推理，而的思维规律，研究的中心问题是推理，而推理基本要素是命
6、题。推理基本要素是命题。具有确切真值的陈述句称作命题。具有确切真值的陈述句称作命题。所谓真值就是命题为真或为假的性质。所谓真值就是命题为真或为假的性质。判断一个语句是否为命题，首先要判断它判断一个语句是否为命题，首先要判断它是否是陈述句，然后判断是否具有唯一的是否是陈述句，然后判断是否具有唯一的真假值。真假值。在判断一个陈述句是否具有唯一的真假时，在判断一个陈述句是否具有唯一的真假时，要注意：一个陈述句的真假暂时不能唯一要注意：一个陈述句的真假暂时不能唯一地确定，但总有一天可以唯一确定，与一地确定，但总有一天可以唯一确定，与一个陈述句的真假不能唯一确定是两件事。个陈述句的真假不能唯一确定是两件
7、事。1.1 1.1 命题与命题联结词命题与命题联结词例如：明年国庆节是个晴天。例如：明年国庆节是个晴天。虽然现在谁也不知道它的真值，但是到了虽然现在谁也不知道它的真值，但是到了明年国庆节，就能判断真假，因此它的真明年国庆节，就能判断真假，因此它的真值仍然是唯一的。值仍然是唯一的。例如：这个语句是错的。例如：这个语句是错的。不能判断真值。不能判断真值。真命题，假命题真命题，假命题 原子命题：不能再分解更简单的命题，原子命题：不能再分解更简单的命题，也称为简单命题。也称为简单命题。复合命题：能够分解为更简单的命题。复合命题：能够分解为更简单的命题。命题联结词：否定，合取，析取，条命题联结词：否定，
8、合取，析取，条件，双条件件，双条件1.1 1.1 命题与命题联结词命题与命题联结词例例1.1 1.1 判断下列句子中哪些构成命题。判断下列句子中哪些构成命题。(1)8(1)8不是素数不是素数;(2)(2)雪是黑的雪是黑的;(3)(3)到到20492049年世界人口将超过年世界人口将超过9090亿亿;(4)(4)每台计算机都有唯一的每台计算机都有唯一的IPIP地址地址;(5)(5)喜马拉雅山好高啊喜马拉雅山好高啊!(6)(6)基本粒子是不可分的基本粒子是不可分的;(7)(7)离散数学难学吗离散数学难学吗?(8)(8)请遵守交通规则请遵守交通规则(9)x+1=2(9)x+1=2。1.1 1.1 命
9、题与命题联结词命题与命题联结词例例1.2 1.2 将下面命题符号化将下面命题符号化,并指出它们的真值并指出它们的真值。(1)(1)丌是有理数丌是有理数;(2)(2)所有的素数都是奇数所有的素数都是奇数;(3)6(3)6是一个合数。是一个合数。解解:分别使用分别使用P P、Q Q和和R R来表示上述三个命题来表示上述三个命题:P:P:丌丌是有理数。是有理数。Q:Q:所有的素数都是奇数。所有的素数都是奇数。R:6R:6是一个合数。是一个合数。丌是无理数丌是无理数,所以所以P P的真值为的真值为F F。2 2是素数是素数,也是偶数也是偶数,除此之外除此之外,其他的素数都其他的素数都是奇数。是奇数。Q
10、 Q的真值为的真值为F F。因为因为2 2和和3 3都是都是6 6的因子的因子,所以所以6 6是合数是合数,R,R的真值的真值为为T T。1.1 1.1 命题与命题联结词命题与命题联结词PPTFTFFTFT1.1.否定否定的定义的定义五个命题联结词五个命题联结词例例1.3 1.3 给出命给出命题题P P：“今天是今天是星期五星期五”的否定的否定，并用自然语言，并用自然语言表示出来。表示出来。解解 P P：今天：今天不是星期五不是星期五1.1 1.1 命题与命题联结词命题与命题联结词2.2.合取合取的定义的定义PQPQTTTTFFFTFFFFl “并且并且”l“既既又又”l“不但不但而且而且”l
11、“虽然虽然但是但是”l“一面一面一面一面”具有对称性具有对称性P PQ=QQ=QP P1.1 1.1 命题与命题联结词命题与命题联结词例例1.4 1.4 将下面命题符号化。将下面命题符号化。(1)2(1)2既是偶数既是偶数,也是素数也是素数;(2)(2)我今天不但听了离散数学课我今天不但听了离散数学课,还听了数据还听了数据结构课结构课(3)(3)今天的离散数学课停上今天的离散数学课停上,美元上涨。美元上涨。解解:(1):(1)设设P:2P:2是偶数是偶数,Q:2,Q:2是素数。是素数。故故(1)(1)可表示为可表示为PQPQ(2)(2)设设P:P:我今天听了离散数学课我今天听了离散数学课,Q:
12、,Q:我今天听我今天听了数据结构课。了数据结构课。故故(2)(2)可表示为可表示为PQPQ。(3)(3)设设P:P:今天的离散数学课停上今天的离散数学课停上,Q:,Q:今天美元今天美元上涨上涨故故(3)(3)可表示为可表示为PQPQ。1.1 1.1 命题与命题联结词命题与命题联结词3.3.析取析取的定义的定义PQPQTTTTFTFTTFFF具有对称性具有对称性P PQ Q=Q QP Pl “同或同或”l 非非“异或异或”1.1 1.1 命题与命题联结词命题与命题联结词例例1.51.5将下面命题符号化。将下面命题符号化。(1)(1)王小林是本年度校运动会的跳高或王小林是本年度校运动会的跳高或10
13、0100米短跑的米短跑的冠军冠军(2)(2)我今天或者去听离散数学课我今天或者去听离散数学课,或者去听数据结构或者去听数据结构课。课。解解:(1):(1)设设P:P:王小林是本年度校运动会的跳高冠军王小林是本年度校运动会的跳高冠军,Q:,Q:王小林是本年度校运动会的王小林是本年度校运动会的100100米短跑的冠军。米短跑的冠军。故故(1)(1)可表示为可表示为PVQPVQ。这个命题表达的是王小林或者。这个命题表达的是王小林或者是跳高冠军是跳高冠军,或者是短跑冠军或者是短跑冠军,也有可能是两个项目也有可能是两个项目的冠军。的冠军。(2)(2)设设P:P:我今天去听离散数学课我今天去听离散数学课,
14、Q:,Q:我今天去听数据我今天去听数据结构课。结构课。故故(2)(2)可表示为可表示为PVQPVQ。这个命题表达的是我今天可能。这个命题表达的是我今天可能去听离散数学或者数据结构课去听离散数学或者数据结构课,也可能两门课都去也可能两门课都去听。听。1.1 1.1 命题与命题联结词命题与命题联结词 此处此处,“,“或或”表示的是表示的是“相容相容”的含义的含义,也也称为称为“同或同或”,即两者并不互相排斥即两者并不互相排斥,可能可能同时成立。同时成立。自然语言中有时会使用自然语言中有时会使用“或或”来表示来表示“相相斥斥”的含义的含义,即用即用“或或”连接的两者不能连接的两者不能同时成立同时成立
15、,这样的语句不能表示为析取。这样的语句不能表示为析取。例例1.6 1.6 分析以下的复合命题。分析以下的复合命题。(1)(1)王小林今天或者去美国王小林今天或者去美国,或者去欧洲。或者去欧洲。(2)(2)王小林或者是坐火车去北京王小林或者是坐火车去北京,或者是乘或者是乘飞机去北京。飞机去北京。1.1 1.1 命题与命题联结词命题与命题联结词解解:(1):(1)设设P:P:王小林今天去美国王小林今天去美国,Q:,Q:王小林今天去欧洲王小林今天去欧洲。显然。显然,如果王小林今天去了美国如果王小林今天去了美国,他就不可能去欧洲他就不可能去欧洲,反之也是一样。王小林没有分身术反之也是一样。王小林没有分
16、身术,他只能去一个地他只能去一个地方。所以方。所以(1)(1)不能简单地表示为不能简单地表示为PVQPVQ(2)(2)设设P:P:王小林坐火车去北京王小林坐火车去北京,Q:,Q:王小林乘飞机去北京王小林乘飞机去北京。这个命题假设王小林只需乘坐一种交通工具即可到。这个命题假设王小林只需乘坐一种交通工具即可到达北京。与达北京。与(1)(1)类似类似,王小林不能同时既坐火车又乘飞王小林不能同时既坐火车又乘飞机。机。PVQPVQ也不能精确地表达也不能精确地表达(2)(2)中命题的含义。中命题的含义。(1)(1)和和(2)(2)所表述的这两个例子有一个共同的特点所表述的这两个例子有一个共同的特点,即即复
17、合命题中的两个原子命题不会同时成立，它们之间复合命题中的两个原子命题不会同时成立，它们之间具有相斥性，这样的具有相斥性，这样的“或或”表示的是表示的是“异或异或”。实际。实际上，（上，（1 1）和（）和（2 2）均可表示为：）均可表示为：(P(P Q)V(Q)V(P Q)P Q)1.1 1.1 命题与命题联结词命题与命题联结词4.PQ 的定义的定义PQPQTTTTFFFTTFFT不具有对称性不具有对称性注意：条件（蕴含）注意：条件（蕴含）l“如果如果，则，则”l“若若，则则”l 除非除非Q Q否则否则P P；l PQPQ为假当且仅当为假当且仅当P P为真且为真且Q Q为假。为假。1.1 1.1
18、 命题与命题联结词命题与命题联结词例例1.7 1.7 将下面命题符号化。将下面命题符号化。(1)(1)如果今天不下雨如果今天不下雨,我就去公园锻炼。我就去公园锻炼。(2)(2)如果我考试通过如果我考试通过,就能拿到合格证书就能拿到合格证书解解:(1):(1)设设P:P:今天下雨今天下雨,Q:,Q:我去公园锻炼我去公园锻炼故故(1)(1)可表示为可表示为PQPQ。注意：仅当今天没有下雨而我没去公园锻炼时注意：仅当今天没有下雨而我没去公园锻炼时,命题命题(1)(1)为为F F(2)(2)设设P:P:我考试通过我考试通过,Q:,Q:我拿到合格证书。我拿到合格证书。故故(2)(2)可表示为可表示为PQ
19、PQ。1.1 1.1 命题与命题联结词命题与命题联结词需要注意需要注意,条件命题的前件和后件之间可以在语义上条件命题的前件和后件之间可以在语义上不存在逻辑关系。这与我们日常的表述是有差异的不存在逻辑关系。这与我们日常的表述是有差异的。例例1.8 1.8 如果雪是黑的如果雪是黑的,则房间里有则房间里有2020张桌子张桌子解解:设设P:P:雪是黑的雪是黑的;Q:;Q:房间里有房间里有2020张桌子。张桌子。本例还是可以符号化为本例还是可以符号化为:PQ:PQ。命题命题pqpq表示表示“q q是是p p的必要条件的必要条件”。自然语言中。自然语言中表示表示“q q是是p p的必要条件的必要条件”有许
20、多不同的叙述方式有许多不同的叙述方式,例如例如,“,“只要只要p,p,就就q”,“q”,“因为因为p,p,所以所以q”,“pq”,“p仅当仅当q”,“q”,“只有只有q q才才p”,p”,等等。等等。1.1 1.1 命题与命题联结词命题与命题联结词例例1.9 1.9 将下列命题符号化。将下列命题符号化。(1)(1)如果今天不下雨而且不刮风如果今天不下雨而且不刮风,我会去爬山我会去爬山;(2)(2)若今天是星期一若今天是星期一,则明天是星期二。则明天是星期二。(3)(3)只有今天是星期一只有今天是星期一,明天才是星期二。明天才是星期二。解解:(1):(1)设设P:P:今天下雨今天下雨,Q:,Q:
21、今天刮风今天刮风,R:,R:我去爬山我去爬山则则(1)(1)可表示为可表示为(P PQ)RQ)R(2)(2)设设P:P:今天是星期一今天是星期一,Q:,Q:明天是星期二。明天是星期二。则则(2)(2)可表示为可表示为PQPQ 本例还隐含着另一层意思本例还隐含着另一层意思,即如果今天不是星即如果今天不是星期一期一(前件为假时前件为假时),),则明天可能是星期二则明天可能是星期二,也可能不是星也可能不是星期二期二,不得而知。或者反过来说不得而知。或者反过来说,如果明天是星期二如果明天是星期二,则则不表明今天一定是星期一。要注意不表明今天一定是星期一。要注意,命题的含义一定要命题的含义一定要和我们日
22、常的概念分开。和我们日常的概念分开。(3)(3)设设P:P:今天是星期一今天是星期一,Q:,Q:明天是星期二。明天是星期二。则则(3)(3)可表示为可表示为QPQP 本例中表述的另一层含义是本例中表述的另一层含义是“明天是星期二明天是星期二”的的话话,“,“今天一定是星期一今天一定是星期一”。1.1 1.1 命题与命题联结词命题与命题联结词PQTTTTFFFTFFFT具有对称性具有对称性P PQ=QQ=QP Pl “等价等价”l“充分必要条件充分必要条件”l“当且仅当当且仅当”5.5.1.1 1.1 命题与命题联结词命题与命题联结词例例1.10 1.10 将下面命题符号化将下面命题符号化,并指
23、出其真值并指出其真值(1)(1)当且仅当实数当且仅当实数R R可以表示为分数时可以表示为分数时,R,R是有理数是有理数;(2)3(2)3是无理数当且仅当加拿大位于亚洲。是无理数当且仅当加拿大位于亚洲。解解:(1):(1)设设P:P:实数实数R R可以表示为分数可以表示为分数,Q:,Q:实数实数R R是有理数是有理数。则则(1)(1)可表示为可表示为P PQ Q。由数学知识可知。由数学知识可知,(1),(1)所表述的即所表述的即是有理数的定义是有理数的定义,所以它的真值为所以它的真值为T T。(2)(2)设设P:3P:3是无理数是无理数,Q:,Q:加拿大位于亚洲加拿大位于亚洲则则(2)(2)可表
24、示为可表示为P PQ Q。由数学知识知。由数学知识知,P,P为为T,T,而由地理知而由地理知识知识知,Q,Q为为F,F,所以所以(2)(2)的真值为的真值为F F1.1 1.1 命题与命题联结词命题与命题联结词综合练习综合练习设设P:P:今天下雨今天下雨,Q:,Q:今天刮风今天刮风,R:,R:我去爬山。将下面命题我去爬山。将下面命题用自然语言表述。用自然语言表述。(PVQ)(PVQ)R;R;R(R(P P Q);Q);PP Q Q PP Q;Q;QPQP 表示表示:今天要是下雨或者刮风今天要是下雨或者刮风,我就不去爬山了我就不去爬山了;表示表示:如果我去爬山了如果我去爬山了,则今天既没下雨也没
25、刮风则今天既没下雨也没刮风 表示表示:今天下雨了今天下雨了,但没有刮风但没有刮风;表示表示:如果今天下雨如果今天下雨,就不会刮风就不会刮风;表示表示:如果今天刮风如果今天刮风,就会下雨。就会下雨。1.2 1.2 命题公式的等值演算命题公式的等值演算命题公式命题公式 命题符号化的过程中命题符号化的过程中,可以用一个符号表示可以用一个符号表示一个命题。当符号一个命题。当符号P P代表一个具体的命题时代表一个具体的命题时,符号符号P P称为称为命题常项命题常项,此时此时P P的真值是确定的的真值是确定的,所以称为所以称为“常常”项。这类似于数学表达式中项。这类似于数学表达式中的一个常数。的一个常数。
26、而当符号而当符号P P仅仅表示是一个命题仅仅表示是一个命题,但并没有指但并没有指明是哪个命题时明是哪个命题时,P,P为为命题变元命题变元。命题变元。命题变元P P可以代表任一个命题可以代表任一个命题,正如数学表达式中的正如数学表达式中的一个变量一样。如果给一个变量一样。如果给P P代入一个真值为代入一个真值为T T的的命题命题,P,P的真值为的真值为T;T;如果代入一个真值为如果代入一个真值为F F的的命题命题,P,P的真值为的真值为F F。在代入之前。在代入之前,P,P的值是不的值是不确定的确定的,所以称为所以称为“变变”元。一般地元。一般地,命题变命题变元不是命题。元不是命题。1.2 1.
27、2 命题公式的等值演算命题公式的等值演算 在表示数学操作时在表示数学操作时,我们可以用操作符将操我们可以用操作符将操作数连接起来作数连接起来,得到一个数学表达式得到一个数学表达式,比如比如a+3a+3。同时可以使用圆括号改变操作符的运。同时可以使用圆括号改变操作符的运算次序算次序,比如比如2 2*(x+3)(x+3)。在命题逻辑中也是一样在命题逻辑中也是一样,可以使用联结词将可以使用联结词将命题连接起来命题连接起来,得到一个更复杂的命题得到一个更复杂的命题,即即复合命题复合命题。这里。这里,命题类似于表达式中的操命题类似于表达式中的操作数作数,联结词类似于表达式中的操作符。联联结词类似于表达式
28、中的操作符。联结词连接的命题符号既可以是命题常项结词连接的命题符号既可以是命题常项,也也可以是命题变元。同样可以是命题变元。同样,也可以在这样的式也可以在这样的式子中添加圆括号。子中添加圆括号。将命题用联结词和圆括号按一定的逻辑关将命题用联结词和圆括号按一定的逻辑关系联结起来的符号串称为系联结起来的符号串称为合式公式合式公式1.2 1.2 命题公式的等值演算命题公式的等值演算1.2 1.2 命题公式的等值演算命题公式的等值演算例例1.12 1.12 设设P P、Q Q、R R分别代表命题变元或命题常项分别代表命题变元或命题常项,给给定以下字符串定以下字符串,判断哪些是合式公式。判断哪些是合式公
29、式。(P(P Q)Q)(P(P Q)V(Q)V(P PQ)Q)P P QV(QV(P PQ)Q)PVQPVQ解解:、都是合式公式。都是合式公式。不是合式公式。不是合式公式。实际上实际上,合式公式最外层的括号是可以省略的合式公式最外层的括号是可以省略的,所以所以还可以表示为还可以表示为:PQ:PQ。本身已去掉了最外层的括号。本身已去掉了最外层的括号。有意思的是有意思的是与与相比相比,它去掉了第一对括号。数理逻它去掉了第一对括号。数理逻辑中规定辑中规定,不影响运算次序的括号也可以省去。不影响运算次序的括号也可以省去。与数学表达式一样与数学表达式一样,合式公式中的括号可以改变运算次合式公式中的括号可
30、以改变运算次序序与与相差的只是第一对括号相差的只是第一对括号,去掉它会不会改变运去掉它会不会改变运算次序呢算次序呢?这要看各联结词的优先级了。这要看各联结词的优先级了。命题逻辑中规定命题逻辑中规定,联结词优先次序依次为联结词优先次序依次为:,V,V,。的优先级高于的优先级高于V V的优先级的优先级,有没有有没有括号括号,都要先计算都要先计算运算。运算。1.2 1.2 命题公式的等值演算命题公式的等值演算定义定义 设设A Ai i是公式是公式A A的一部分的一部分,且且A Ai i是一个合是一个合式公式式公式,称称A Ai i是是A A的的子公式子公式,或或公式分量公式分量。例例1.13 1.1
31、3 指出合式公式指出合式公式(PVQ)(PVQ)(R(R(PQ)PQ)中的子公式有哪些。中的子公式有哪些。解解:它的子公式有以下一些它的子公式有以下一些:A A1 1:P:PA A2 2:Q:QA A3 3:R:RA A4 4:P PA A5 5:PVQ:PVQA A6 6:PQPQA A7 7:R(:R(PQ)PQ)1.2 1.2 命题公式的等值演算命题公式的等值演算 在命题公式中在命题公式中,由于有命题变元的出现由于有命题变元的出现,因而真值是不确定的。用命题常项替因而真值是不确定的。用命题常项替换公式中的命题变元称作指派。当将换公式中的命题变元称作指派。当将公式中出现的全部命题变元都指派
32、成公式中出现的全部命题变元都指派成具体的命题常项之后具体的命题常项之后,公式就成了真值公式就成了真值确定的命题。确定的命题。1.2 1.2 命题公式的等值演算命题公式的等值演算2 2、指派与真值表、指派与真值表 一个含有命题变元的命题公式是没有确定真值一个含有命题变元的命题公式是没有确定真值的。只有在命题公式中每个命题变元用指定的的。只有在命题公式中每个命题变元用指定的命题常量代替后，命题公式才有确定的真值，命题常量代替后，命题公式才有确定的真值，成为命题。成为命题。设设P P为一命题公式，为一命题公式，P P1 1，P P2 2，P Pn n为出现在为出现在P P中的所有命题变元，对中的所有
33、命题变元，对P P1 1，P P2 2，P Pn n指定一指定一组真值称为对组真值称为对P P的一种指派（解释或赋值）。的一种指派（解释或赋值）。若指定的一种指派，使若指定的一种指派，使P P的值为真，则称这组的值为真，则称这组值为值为成真指派成真指派；使；使P P的值为假，则称这组值为的值为假，则称这组值为成假指派成假指派。含含n n个命题变元的命题公式，个命题变元的命题公式，共有共有2 2n n组指派组指派。将命题公式将命题公式P P在所有指派下取值情况，列成表在所有指派下取值情况，列成表，称为，称为P P的真值表的真值表。1.2 1.2 命题公式的等值演算命题公式的等值演算 真值表真值表
34、构造构造方法方法：如果公式如果公式A A中有中有n n个命题符个命题符（命题变元（命题变元），则，则A A的真值表共有的真值表共有2 2n n+1+1行。第一行行。第一行称为表头，在表头的第一列写出所有称为表头，在表头的第一列写出所有的命题符，从表头第二列开始，依次的命题符，从表头第二列开始，依次写上公式写上公式A A的生成过程中生成的子串的生成过程中生成的子串（这些子串也是（这些子串也是子子公式）。公式）。剩下的剩下的2 2n n行，每一行对应一个指派行，每一行对应一个指派。一般按二进制的加法顺序依次赋值。一般按二进制的加法顺序依次赋值。对于每一个指派，依次求出各个子串对于每一个指派，依次求
35、出各个子串的值，的值，直到直到最后求出最后求出A A的值。的值。1.2 1.2 命题公式的等值演算命题公式的等值演算例如例如：给出：给出(PQ)(PQ)(PPQ)Q)的真值表。的真值表。PQPQPQPQ(PQ)(PQ)11001011001000011000000110111.2 1.2 命题公式的等值演算命题公式的等值演算3 3公式分类公式分类 设设A A为一命题公式，若为一命题公式，若A A在它的各种指在它的各种指派情况下，其取值均为真，则称公式派情况下，其取值均为真，则称公式A A为为重言式或永真式重言式或永真式。设设A A为一命题公式，若为一命题公式，若A A在它的各种指在它的各种指派
36、情况下，其取值均为假，则称公式派情况下，其取值均为假，则称公式A A为为矛盾式或永假式矛盾式或永假式。设设A A为一命题公式，若为一命题公式，若A A在各种真值指在各种真值指派下至少存在一组成真指派，称派下至少存在一组成真指派，称A A是是可可满足式满足式。若可满足式。若可满足式A A至少存在一个成至少存在一个成假赋值，则假赋值，则A A称为称为非重言式的可满足式非重言式的可满足式。1.2 1.2 命题公式的等值演算命题公式的等值演算1.2 1.2 命题公式的等值演算命题公式的等值演算 公式G，H是等价的，如果在其任意的指派下其真值相同。证明两个公式等价或永真永假或可满足式，可用等值演算或真值
37、表法等值演算或真值表法。常用的命题定律如下表(P.28P.29)：1.2 1.2 命题公式的等值演算命题公式的等值演算1.2 1.2 命题公式的等值演算命题公式的等值演算1.3 1.3 联结词完备集联结词完备集1.3 1.3 联结词完备集联结词完备集考核内容与考核要求考核内容与考核要求1.1.范式，要求达到范式，要求达到“领会领会”层次。层次。范式的概念，掌握范式的概念与性质，能够范式的概念，掌握范式的概念与性质，能够正确计算给定公式的范式。正确计算给定公式的范式。小项与大项，掌握小项与大项的概念与性质小项与大项，掌握小项与大项的概念与性质，能够正确计算给定公式的成真赋值、成假，能够正确计算给
38、定公式的成真赋值、成假赋值及对应的编码。赋值及对应的编码。2.2.主范式，要求达到主范式，要求达到“简单应用简单应用”层次。层次。主析取范式，掌握主析取范式的概念及性质主析取范式，掌握主析取范式的概念及性质，能够正确计算给定公式的主析取范式。，能够正确计算给定公式的主析取范式。主合取范式，掌握主合取范式的概念及性质主合取范式，掌握主合取范式的概念及性质，能够正确计算给定公式的主合取范式。，能够正确计算给定公式的主合取范式。3.3.自然推理系统，要求达到自然推理系统，要求达到“简单应用简单应用”层次。层次。第第2 2章命题逻辑的推理理论章命题逻辑的推理理论第第2 2章命题逻辑的推理理论章命题逻辑
39、的推理理论重点：重点：1.1.命题公式的主范式表示及相互转换，命题公式的主范式表示及相互转换，2.2.使用使用P P规则、规则、T T规则、规则、CPCP规则进行命题推理。规则进行命题推理。难点：难点：命题推理及其应用命题推理及其应用2.1 2.1 范式范式范式的概念：范式的概念：命题变项及其否定统称作文字。仅有有命题变项及其否定统称作文字。仅有有限个文字构成的析取式称作简单析取式限个文字构成的析取式称作简单析取式。仅有有限个文字构成的合取式称作简。仅有有限个文字构成的合取式称作简单合取式。单合取式。p,qp,q等为一个文字构成简单析取式，等为一个文字构成简单析取式，pppp，pqpq等为等为
40、2 2个文字构成的简单个文字构成的简单析取式，析取式，ppqrqr,p,pqrqr等为等为3 3个文字构成的简单析取式。个文字构成的简单析取式。p,qp,q等为一个文字构成的简单合取式，等为一个文字构成的简单合取式，pppp，pqpq等为等为2 2个文字构成的简单个文字构成的简单合取式合取式,pqpqr,r,ppqppq等为等为3 3个个文字构成的简单合取式。文字构成的简单合取式。2.1 2.1 范式范式 应该注意，一个文字既是简单析取式，应该注意，一个文字既是简单析取式，又是简单合取式。为方便起见，有时用又是简单合取式。为方便起见，有时用A1,A2,AsA1,A2,As表示表示s s个简单析
41、取式或个简单析取式或s s个简个简单合取式。单合取式。简单合取式的重要特点是它的成真指派简单合取式的重要特点是它的成真指派很容易找到，且它的永假性也容易判定很容易找到，且它的永假性也容易判定一个简单合取式是永假的，当且仅当它一个简单合取式是永假的，当且仅当它至少含一个变元及其否定至少含一个变元及其否定2.1 2.1 范式范式 定理：定理：（1 1）一个简单析取式是重言式当且仅当它同）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。时含某个命题变项及它的否定式。（2 2）一个简单合取式是矛盾式当且仅当它同）一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。时含有某
42、个命题变项及它的否定式。证明：设证明：设AiAi是含是含n n个文字的简单析取式，若个文字的简单析取式，若AiAi中既含有中既含有某个命题变项某个命题变项pjpj，又含有它的否定式，又含有它的否定式pjpj，由交换律，由交换律、排中律和零律可知，、排中律和零律可知，AiAi为重言式。反之，若为重言式。反之，若AiAi为重为重言式，则它必同时含某个命题变项及它的否定式，否言式，则它必同时含某个命题变项及它的否定式，否则，若将则，若将AiAi中的不带否定号的命题变项都取中的不带否定号的命题变项都取0 0，带否定，带否定号的命题变项都取号的命题变项都取1 1，此赋值为，此赋值为AiAi的成假赋值，这
43、与的成假赋值，这与AiAi是重言式相矛盾。类似的讨论可知，若是重言式相矛盾。类似的讨论可知，若AiAi是含是含n n个命题个命题变项的简单合取式，且变项的简单合取式，且AiAi为矛盾式，则为矛盾式，则AiAi中必同时含中必同时含有某个命题变项及它的否定式，反之亦然。有某个命题变项及它的否定式，反之亦然。2.1 2.1 范式范式如：如：pppp，pprppr都是重言式。都是重言式。pqpq，pqrpqr都不是重言式都不是重言式2.1 2.1 范式范式小项：小项：n n个命题变员的合取式，称作布尔合取个命题变员的合取式，称作布尔合取或小项，其中每个变元与它的否定不能或小项，其中每个变元与它的否定不
44、能同时存在，但两者之一必须出现且仅出同时存在，但两者之一必须出现且仅出现一次。现一次。两个命题变元两个命题变元P P和和Q Q，其小项为，其小项为PQPQ，PPQ Q，PQPQ，PPQ Q2.1 2.1 范式范式2.1 2.1 范式范式2.1 2.1 范式范式 三个命题变元的大项：三个命题变元的大项：M000=PQRM000=PQR M001=PQM001=PQR R M010=PM010=PQRQR M011=PM011=PQQR R M100=M100=PQRPQR M101=M101=PQPQR R M110=M110=PPQRQR M111=M111=PPQQ R R或记为或记为Mi(
45、Mi(i i=0=0，1 1，2 2，3 3，4 4，5 5，6 6，7)7)。2.2 2.2 主范式主范式 主析取范式：主析取范式：对于给定的命题公式，如对于给定的命题公式，如果有一个等价公式，它仅由小项的析取果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取所组成，则该等价式称作原式的主析取范式。范式。主合取范式主合取范式：对于给定的命题公式，如：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取所组成，则该等价式称作原式的主合取范式。范式。2.2 2.2 主范式主范式真值表法真值表法：在真值表中，
46、一个公式的真值为在真值表中，一个公式的真值为T T的指的指派所对应的小项的析取，即为此公式主派所对应的小项的析取，即为此公式主析取范式。析取范式。在真值表中，一个公式的真值为在真值表中，一个公式的真值为F F的指的指派所对应的大项的合取，即为此公式主派所对应的大项的合取，即为此公式主合取范式。合取范式。除了真值表法外，还可以用除了真值表法外，还可以用等值演算法等值演算法求求主析取范式和主合取范式。主析取范式和主合取范式。2.2 2.2 主范式主范式2.2 2.2 主范式主范式例例 写出公式写出公式(pq)(qpq)(qp)p)的主析取范式的主析取范式解：方法一，真值表法：列出真值表解：方法一，
47、真值表法：列出真值表从真值表看出，真值为从真值表看出，真值为1 1的小项有的小项有m m0000，m m0101，m m1010三项，故三项，故原式的析取范式为原式的析取范式为m m0000m m0101m m1010=(=(p pq)q)(p pq)q)(p(pq)q)2.2 2.2 主范式主范式2.2 2.2 主范式主范式例例 求求pqrpqr的主合取范式。的主合取范式。解：方法一，真值表法：列出真值表解：方法一，真值表法：列出真值表:PqrPqpqr00000001010100001101100001010111011111112.2 2.2 主范式主范式从表中可以看出，真值为从表中可以
48、看出，真值为F F所对应的大项编所对应的大项编码有码有M M000000，M M010010，M M100100，所以与原式等价的主，所以与原式等价的主合取范式为合取范式为M M000000M M010010M M100100=(0,2,4)=(0,2,4)2.2 2.2 主范式主范式方法二，等值演算法：方法二，等值演算法：pqr pqr (pq)r (pq)r(pr)(qr)(pr)(qr)(p(q(p(qq)r)(pq)r)(pp)qr)p)qr)(pqr)(p(pqr)(pqr)(pqr)(qr)(pqr)(pqr)pqr)(pqr)(p(pqr)(pqr)(qr)(pqr)pqr)M0
49、00M010M100 M000M010M100 M0M2M4=(0,2,4)M0M2M4=(0,2,4)2.2 2.2 主范式主范式主范式之间的关系：主范式之间的关系：设命题公式设命题公式A A中含有中含有n n个命题变元，且个命题变元，且A A的主的主析取范式中含有析取范式中含有k k个小项个小项m mi1i1，m mi2i2，m mikik，则则A A的主合取范式必含有的主合取范式必含有2 2n n-k-k个大项个大项 如果命题公式如果命题公式A A的主析取范式为的主析取范式为(i(i1 1,i,i2 2,i ik k)，则则A A的主合取范式为：的主合取范式为：(0(0，1 1，2 2，
50、i i1 1-1-1，i i1 1+1+1，i ik k-1-1，i ik k+1+1，2 2n n-1)-1)。2.2 2.2 主范式主范式 从从A A的主析取范式求其主合取范式步骤为的主析取范式求其主合取范式步骤为：（1 1）求出）求出A A的主析取范式中未包含小项的的主析取范式中未包含小项的下标。下标。（2 2）把（）把（1 1）中求出的）中求出的“下标下标”写成对应写成对应大项。大项。（3 3）做（）做（2 2）中写成的大项合取，即为）中写成的大项合取，即为A A的的主合取范式。主合取范式。例例 (PQ)Q(PQ)Q 主析取范式主析取范式(1,3)=m01m11(1,3)=m01m11
