离散数学

离散数学 前言 课程性质:计算机数学基础 课程安排:三个学期教授三个部分 第一部分:离散数学 第一篇:数理逻辑 第二篇:集合论 第三篇:图论 代数系统 第二部分:计算数学 第三部分:组合数学 学习目的:1、初步掌握现代数学的观点和方法; 2、初步掌握处理离散结构和方法，提高计算机系统设计和程序设计的逻辑数字的能力; 3、初步掌握计算机在进行数的处理时的方法和计算; 4、培养学习抽象思维和缜密思考的能力; 第一篇 数理逻辑 第一章 命题逻辑 ?1.1 命题和命题联结词 一. 命题: 定义:具有确定真值的表达判断的陈述句称为命题。 说明:?命题的真值:作为命题所表达的判断只有两个结果:正确和错误，此结果称为 命题的真值。 命题是正确的，称此命题的真值为真;命题是错误的，称此命题的真值为假。 真值为真的命题称为真命题 ;真值为假的命题称为假命题。 ?其它类型的句子，如疑问句、祈使句、感叹句均没有真假意义，因为均不是命 题。 在数理逻辑中，命题的真值的真和假，有时分别用1和0来表达，也有时分别 用T和F来表达。 命题的分类: 原子命题:不能分解成更简单的命题的命题。 复合命题:由若干个原子命题用命题联结词、标点符号联结起来的命题。 例: (1)10是整数。 真 原子命题 (2)北京是我们祖国的首都。 真 原子命题 (3)雪是黑的。 假 原子命题 (4)煤是白的。 假 原子命题 (5)今天是7号。 在一定条件下是真命题(如果今天是7号)。 (6)1+11=100。 在一定条件下是真命题(在二进制中)。 (7)我学英语，或者学法文。 复合命题 (8)如果 天气好，我就去游泳。 复合命题 (9)向右看齐～ 祈使句 非命题 (10)请勿吸烟～ 祈使句 非命题 (11)你吃饭了吗,疑问句 非命题 (12)你上网了吗,疑问句 非命题 (13)本命题是假的。悖论 (14)我正在说谎。 悖论 (15)我不给所有自己给自己理发的人理发，但是却会给所有自己不给自己理发的人理 发。悖论 命题标识符:用大写字母P、Q、R、P、P？来表示命题，这些大写字母称 12 为命题标识符。 命题常量:用命题标识符表示的确定的命题称为命题常量，它有确定的真值。 命题变量:表示任何一个命题的标识符，称为命题变量，它有不确定的真值。 二(命题联结词: 常见联结词 否定、合取、析取、蕴含、等价和异或 ，1. 否定 符号: ，P是命题，P读作“非P”。 ，P真值表为 ，P P 0 1 1 0 否定的性质 ，， 双重否定律 : (P) P , ，说明:1、P是一元联结词 所谓一元联结词就是联结一个命题的联结词。 2、念作“等值”，表示该符号两边的两个命题在任何情况下真值相同。 , 2. 合取 符号: , P、Q是命题 PQ 读作“P且Q”，“P合取Q”。 , PQ 真值表 , P Q P Q , 0 0 0 0 1 0 1 0 0 1 1 1 例:P:今天下雨。Q:今天刮风。则PQ :今天下雨且刮风。 , 合取的性质 1) 幂等律 PPP ,, 2) 交换律 PQQP ,,, 3) 结合律 (PQ)CP(QC) ,,,,, 4) 零一律 P0 0 ,, 5) 同一律 P1 P ,, ，6) 否定律 PP 0 ,, 3. 析取 符号: , P、Q是命题,记作PQ ，读作“P或Q”，“P析取Q”。 , PQ 真值表 , P Q PQ , 0 0 0 0 1 1 1 0 1 1 1 1 例:P:今天下雨。Q:今天刮风。则 PQ :今天下雨或刮风。 , 析取的性质: 1) 幂等律 PPP ,, QQP 2) 交换律 P,,, 3) 结合律 (PQ)CP(QC) ,,,,, 0P 4) 同一律 P,, 5) 零一律 P11 ,, ，6) 否定律 PP 0 ,, 7) 吸收律 P(PQ) P, P(PQ) P ,,,,,, 8) 分配律 P(QC) (PQ)(PC) P (QC) (PQ) ,,,,,,,,,, (PC) ,, ，，，，，，9) 德、摩根律 (PQ) P Q, (PQ) PQ ,,,,,,说明:(1)和混合运算只能用分配律，不能用结合律。例:P(PQ)与P (QC),,,,,, 不等值。 (2)和的分配律:P (QC) (PQ) (PC)，形如乘与加的分配律P× ,,,,,,,,(Q+C)。 (3)可兼或与不可兼或 可兼或:明天下雨或刮风。 不可兼或:今天晚上去电影院看电影，或在家看电视。 4.蕴含 符号: , P、Q是命题 P Q 读作“P蕴含Q”，“如果P则Q”，“当P，则Q”，“P是Q的充分条件”。 , 例:P:我去上海。 Q:我给你买衣服。 P Q:如果我去上海，就给你买衣服。 , P假Q假 我没去上海，也没给你买衣服。 P Q真 , P假Q真 我没去上海，但没给你买衣服。 P Q真 , P真Q假 我去了上海，但没给你买衣服。 P Q假 , P真Q真 我没去上海，也没给你买衣服。 P Q真 , PQ 真值表 , PQ P Q , 0 0 1 0 1 1 1 0 0 1 1 1 P也称为前件;Q称为后件。 前件为假时，P Q必为真; , 后件为真时，P Q必为真。 , 蕴含的性质 ，，1) 归化:PQPQ 所谓归化就是用、、表示其它联结词。 ,,,,, ，，2) PQQP ,,, 证明: ，，QP PQ ，P Q P ,, 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 ，，，，在全部四种情况下，PQ与QP的真值表相同，所以PQQP ,,,,, ，，3)(PQ)PQ ,,, 例:将下列命题符号化 1) 如果1+2,3,则太阳从东边升起 PQ , ，2) 如果1+2?3,则太阳从东边升起 PQ , ，3) 如果1+2,3,则太阳从东边升起 PQ , ，，4) 如果1+2?3,则太阳从东边升起 PQ ,P:1+2=3 Q:表示太阳从东边升起 说明(1)蕴涵不存在交换律、结合律 PQ与QP不等值 ,, (PQ)R与P(QP)等值 ,,,, (2)在数理逻辑中，即使 Q没有内在联系 PQ仍有意义 P、, 5. 等价 符号: , P、Q是命题 从 读作“P等价于Q”，“ P当且仅当Q”，“P是Q的充要条件”。 PQ 真值表 , PQ P Q , 0 0 1 0 1 0 1 0 0 1 1 1 等价的性质PQ(PQ)(QP)从,,,,, ，，，，(PQ)(PQ)(PQ)(PQ ,,,,,,, 1) 交换律:PQ QP ,,, 2) 结合律:(PQ)R P(QR) ,,,,, 3) PQ(PQ)(QP) ,,,,, ，，，，4) 归化:PQ(PQ)(PQ)(PQ)(PQ) ,,,,,,,,, 证明结合律 PQ R P(QR) QPQR (PQ)R ,,,,,, 000 1 0 1 0 001 1 1 0 1 010 0 1 0 1 011 0 0 1 0 100 0 1 1 1 101 0 0 0 0 110 1 0 0 0 111 1 1 1 1 左右两边在全部八种情况下均相等，所以两边等值，(PQ)R P(QR)。 ,,,,, 说明: 1) 是逻辑联结词，而是公式关系符。A、B是命题，AB仍是命题，而AB,,,, 不是命题。 2) P、Q两命题，没有内在联系 PQ仍有意义。 , 例:2+2=5的充要条件是太阳从西边升起。 真 该命题为真 6. 不可兼或(异或) , 两个公式P、Q的异或是复合命题， 记作“PQ” , 读作“P异或Q”，“P不可兼析取Q”。 不可兼或就是两个命题不可能同时为真，当且仅当一个为真，一个为假时，为真。 例:(1)今天下雨或刮风。 (可兼或) (2)今天第一节课是语文课或数学课。 (不可兼或) (3)他现在在301室或302室。 (不可兼或) P,Q 真值表 P Q P,Q 0 0 0 0 1 1 1 0 1 1 1 0 与或的区别:P为1且Q为1时，PQ为假。 , 性质:(1)PQQP 交换律 ,,, (2)(PQ)RP(QR) 结合律 ,,,,, (3)P(QR)(PQ)(PR) 对的分配律 ,,,,,,,, ，， (4)PQ(PQ)(PQ) ,,,,, ，， (PQ)(PQ) ,,,, ， (5)PQ(PQ) ,,, 三(命题公式: 1( 命题公式 由命题标识符、逻辑联结词和圆括号按照一定的正确规则组成的合式，简称公式。 命题公式的规定: (1) 单个命题变项是合式公式。 ，(2) 如果A是合式公式，则A是合式公式。 (3) 如果A、B是合式公式，则AB、 AB、AB、AB、AB也是合,,,,, 式公式。 (4) 当且仅当有限次运用(1)(2)(3)所得到的符号串是合式公式。 逻辑联结词的运算优先次序依次为: ， ,,,,, ， 例:(PQ)，P(QR)，P(QR)是公式 ,,,,, ， (PQ，P，PQ，P不是公式 ,,, P(QR)的括号可以省略 ,, (PQ)R 的括号不能省略 ,, 2( 命题变项的指派(赋值) ，公式(PQ)(PQ)对命题变项P、Q、R没有真值指定，公式没有确定,,, 的真值。 指派(赋值):命题公式中出现n个不同的命题变项P？P，对这n个命题给定1n 一组真值指定称为这个公式的一个指派或称为一个赋值。 若一个公式中出现n个不同的命题变项，每个变项分别可以取成1、0，那么该公 n式共有个2不同的指派。 3 例:前面公式共有P、Q、R三个不同命题变项，则共有2 =8个指派。 P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 3( 公式的真值表 列出公式的所有指派及其相应的公式真值形成的称为公式的真值表 PC(QR)的真值表 例:, P Q R (QR) P(QR ,,, 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 公式真值表对我们进行证明以及判断公式的恒真、恒假起很大作用 4( 两公式的等值 n给定两公式A、B，A、B中共出现n个不同的命题变项，对于所有的个2不同的 指派，A、B两公式的真值均相同，记AB，读作“A与B等值”。 ,说明: 等值与等价不是一回事 等价是命题联结词，是AB公式，在某些指派下为真，某些指派下为假。 , 等值不是逻辑联结词是公式关系符，AB描述了A、B两公式之间的关系， , 只有“成立”，“不成立”的区别。 5( 全功能联结词组 定义了六个联结词，某些联结词可以同其他联结词替换 ，例:PQPQ ,,, ，，PQ(PQ)(PQ) ,,,,, ，，P,Q(PQ)(PQ),,,, ，、、,可以用、、等代换 ,,,, 一个联结词集合，若对于任何一个公式均可以用该集合中的联结词来等值比较， 就称他为全功能联结词组(联结功能完备集) 如果该集合任意去掉一个联结词，就不再具备这种特性，就称为最小全功能联结 词组(最小功能完备集) ，例:{、、}是全功能联结词组 ,, ，，，又因PQ=(PQ) ,, ，，{、}、{、}是最小全功能联结词组 ,, 第一节小结 必须熟练掌握:什么是命题 什么是命题逻辑联结词 命题联结词的真值表的定义及命题联结词的性质 ?1.2 命题公式与赋值 命题公式:简单讲就是由命题表示符，逻辑联结词，括号按正确的规律联结起来，形成 的符号串。 n公式的指派:一个公式中如果出现n个不同的命题变项，那么此公式就有2个公式指 派。 公式真值表:将所有的公式指派列出来，并且相对应的列出公式的真值所得到的表格。 例:求下列公式的真值表 ，(1)PQ , ，(2)(PQ)P ,, ，，，(3)(PQ)(PQ) ,,, ，(4)(PQ)R ,, (5)(P(PQ))R ,,, ，(6)(PQ)QR ,,, 六个公式的真值表如下: ，(1)PQ , ，P Q PQ , 0 0 1 0 1 1 1 0 0 1 1 1 ，(2)(PQ)P ,, ，P Q PQ (PQ)P ,,, 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 ，，，(3)(PQ)(PQ) ,,, ，，，，，，(PQ)(PQ) ,,P Q R PQ (PQ) PQ ,,,, 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 1 ，Q)R (4)(P,, ，，，P Q R Q PQ (PQ)R ,,,0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 ，(5)(PQ)QR ,,, Q P，，(PQ) (PQ)QR ,,,P Q R ,, 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 (6)(P(PQ))R ,,, (PQ) (P(PQ))R PP Q R PQ ,,,,,, 0 0 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 命题公式的分类: 永真式(重言式):公式在一切赋值下的真值均为真。 永假式(矛盾式):公式在一切赋值下的真值均为假。 可满足式: 如公式不是矛盾式就是可满足式，即至少存在一个赋值使公式为真。 仅可满足式:既不是矛盾式，又不是重言式的公式，即至少存在一个指派使公式为真， 至少存在一个指派使公式为假。 , 矛盾式 公式 , , 重言式 , 可满足式 , , 仅可满足式 说明: (1)公式若不是永真式未必是永假式。 ，(2)如公式G是永真式，则公式G是永假式(反之也成立)。 (3)证明公式是永真式和永假式的方法: 方法之一:使用真值表 方法之二: ， 否定律:PP1(永真式) ,, ， P P0(永假式) ,, 零一律:P 00(永假式) ,, P11(永真式) ,, 第二节小结 讲解了公式的分类，永真式、永假式及其判断方法 , , , ， , , 第四节 范式 一、对偶式和对偶原理 定义1:在仅含有联结词， , ,，,，的命令题公式A中，将,换成,，将,换成,，同时T和F **(既0和1)互相替代，所得公式A称为A的对偶式。显然A是A的对偶式A的对偶式。 例一(试写出下列命题公式的对偶式 (1)A:(P,Q),R *则A为(P,Q),R (2)A:(P,Q),(P,，(Q,，S)) * 则A为(P,Q),(P,，(Q,，S)) (3)A:((P,Q),0),(1,，(R,，P)) * 则A为((P,Q),1),(0,，(R,，P)) 下面两个定理是对偶定理 定理2:A和是互为对偶式，P，P ，„„P是出现在A和的原子变元，则 2n*， A(P，„，P),A(， P，„，， P) n n**A(， P，„，， P),， A(P，„，P) nn 即公式的否定等值于其变元否定的对偶式。 *例:A为P,Q，则A为P,Q，则，(P,Q), ，P,，Q 这就是De Morgan律。 *再例如:A为(P,，R),Q则A为(P,，R),Q则，((P,，R),Q), (，P,R),，Q ****定理3:设A ，B分别是A和B的对偶式，如果A, B，则A, B。 这就是对偶原理。如果证明了一个等值公式，其对偶式的等值式同时也成立。可以起到事半功倍的效果。 例如:A,(P,Q),(，P,(，P,Q)) B,， P,Q 可以证明A,B *而A的对偶式为A,(P,Q),(，P,(，P,Q)) *B的对偶式为B,， P,Q **根据对偶原理，则A, B也成立。 说明:1)含有另外三个联结词, ，,，,的公式，必须将其归化为然后再化为对偶式。 例:P,Q,(，P,Q),(P,，Q) P,Q,(，P,Q),(P，,Q) 从而可知P,Q的对偶式是P,Q *2)对偶原理不是说A与其对偶式A等值，一般公式与对偶是不是等值的。 二、范式: 1( 简单析取式和简单合取式 定义2:仅有有限个命题变元或其否定的析取构成的析取式称为简单析取式。而仅有有限个命题变元或其否定的合取构成的合取式称为简单合取式。例如:，P,Q,R， ，P,，Q,P是简单析取式，，P,R，Q,R,，Q是简单合取式。P，，Q一个变项本身可以看作简单析取式也可以看作简单合取式。 而，P,(Q,R)，(P,Q),，R不是简单析取式。 2( 范式: 定义3: ? 析取范式:由有限个简单合取式的析取构成的析取式称为析取范式。 ? 合取范式:由有限个简单析取式的合取构成的合取式称为合取范式。 例:P,(P,Q),(，P,，Q,，R)是析取范式 (P,Q),，Q,(Q,，R,S)是合取范式 P,Q,R是析取范式是三个简单合取范式的析取，同时也是合取范式是一个简单析取范式的合取。而(P,Q),(，P,(Q,R))不是析取范式，因为，P,(Q,R)不是简单合取范式。含有双重刮号的公式，肯定不是范式。 (P ,Q),(Q ,R)不是合取范式，因为其含有,，范式中只能包含,、,、，等逻辑联结词。 3、范式的存在性 定理:任意一个命题公式均存在一个与之等值的析取范式和合取范式 此定理证明是一个构造性证明，证明过程说明了公式的范式如何求得。 ，第一步: 将公式中出现的，，,，用，，来归化。 ,,,, ，所用公式为 ? PQPQ ,,, ，， ? PQ(PQ)(PQ) ,,,,, ，， (PQ)(PQ) ,,,, ，， ? PQ (PQ)(PQ) ,,,,, ，， (PQ)(PQ) ,,,, ，，，第二步:用双重否定律PQ，或用德莫根律将一直移到命题变元之前 , 第三步:用分配律、结合律化去额二重以上刮号成为析取范式或合取范式 例2:求公式((PQ)R)的析取范式和合取范式 ,, ，，，解:((PQ)R)((PQ)R)P((PQ)R)P ,,,,,,,,,, ，，(PQ)(QR)P析取范式 ,,,,, ，，，(P(PR))(QR)P(QR)析取范式 ,,,,,,,, ，，，原式:((PQ)R)P (PQP)(RP)合取范式(PQ)(PR),,,,,,,,,,,,,合取范式 例3:求公式(PQ)(QR)的析取范式和合取范式 ,,, ，，，，，解:(PQ)(QR)(PQ)(QR)(QR)(PQ),,,,,,,,,,,, ，，(QR)(QR)析取范式 ,,, ，，，，，，，原式(PQ)((QR)(QR))(PQ)((QR)(QR)),,,,,,,,,,,, ，，，，，，，，(PQR)(PQR)(QQR)(QQR)合取范,,,,,,,,,,,, ，，，，，式(PQR)(PQR)(QR)合取范式 ,,,,,,,, 总结: 一个公式的析取范式与合取范式并不唯一。要使任一命题公式化为唯一的等值命题的形式，就要用到主析取范式与主合取范式的概念。 三、主析取范式: 1(极小项 定义4:如公式中共有N个命题变项P，……，P这N个变项的合取n 式中，每个变项P或其否定， P，均出现且两者仅出现一个，并且按ii 命题变项的下标排列(字母按字典序列)这样的简单合取式称为极小项，又称布尔合取。 例如:公式中出现P，Q，R三个命题变项 P,，Q,R，，P,Q,，R是极小项 P,，Q不是极小项，其中没出现R P,，Q,， P不是极小项，P，，P同时出现 2(极小项和赋值的一一对应 n每一个极小项只有一个赋值使其为真，其余2-1个赋值使其为假。 例如:公式中出现P，Q，R三个不同的赋值。极小项，P,Q,，R，赋 3值010使其为真，其余2-1=7个赋值使其为假。这样极小项与赋值建立了一一对应关系。而，P,Q不是极小项，有两个赋值010，011使其为真，其余6个赋值使其为假。 3(极小项的记法 n公式共有2个赋值，每个赋值对应一个极小项。如极大项对应赋值 naaa，把其看作二进数，化为十进数为k , k , 2-1,则该极小项记作1230 m,也记作ma1a2a3k 极小项 对应的赋值 十进制数 记法 000 0 M或M，P,，Q,，R 0000 001 1 M或M，P,，Q,R 0011 010 2 M或M，P,Q,，R 0102 011 3 或MM，P,Q,R 0113 100 4 或M MP,，Q,，R 1004 101 5 M或M P,，Q,R 1015 110 6 M或M P,Q,，R 1106 111 7 M或MP,Q,R 1117 4.主析取范式: 定义4:若干个不同的极小项的析取式，称为主析取范式 定理5:任何一个命题公式均存在一个与之等值的主析取范式， 而且是唯一的。 例如: P,(，P,Q)，(P,Q),(，P,R)是析取范式,但不是主析取范式。 (P,Q,，R),(，P,Q,R)是主析取范式，当然也是析取范式。 5(求主析取范式方法之一:真值表法 一个公式的主析取范式与该公式的真值是一一对应的 例如:由三个极小项组成的主析取范式 (P,Q,R),(，P,Q,R),(，P,Q,，R) 这三个极小项对应的赋值分别是111，011，010，则该三个赋值使 公式为真，而其它五个赋值使公式为假。 而反过来如果这三个赋值公式为真，而其它赋值使公式为假，则该公式的主析取范式就是有这三个赋值对应的极小值的析取而成。 因此我们可以用真值表的方法来求出公式的主析取范式。 例4:用真值表的方法求，(P,Q)的主析取范式 解:，(P,Q)的真值表 P Q ，(P,Q) P,Q 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 找使公式为真的赋值。 00对应的极小项是，P,，Q (m) 0 01对应的极小项是，P,Q (m) 1 10对应的极小项是P,，Q (m) 2 则原公式的主析取范式是 ，(P,Q),(，P,，Q) ,(，P,Q),(P,，Q) , m, m, m012 例5:用真值表的方法求(P,Q),(Q,R)的主析取范式。 解:(P,Q),(Q,R)的真值表 P Q R (P,Q),(Q,R) 对应极小项 P,Q Q,R 0 0 0 0 1 1 ，P,，Q,，R 0 0 1 0 0 1 ，P,，Q,R 0 1 0 1 0 0 0 1 1 1 1 1 ，P,Q,R 1 0 0 1 1 1 P,，Q,，R 1 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 1 1 P,Q,R 找使公式真值为1的赋值。 由此主析取范式为: (P,Q),(Q,R),(，P,，Q,，R),(，P,，Q,R),(，P,Q,R) ,(P,，Q,，R),(P,Q,R) ,m, m, m, m, m 01347 6.求主析取范式的方法之二:等值演算法 利用十六个命题公式、命题定理用等值演算的方法一步步将它化为主析取范式。 第一步:将公式化为析取范式，“消去”含有矛盾式的简单合取式， 这是因为(P,，P,Q),G,G，而P,P用P代替。 0 第二步:若析取范式中的简单合取式项不是极小项，即该项中缺命题变项，则添加(P,，P)再用分配律展开。 ii 例如:公式中含P、Q、R，某合取项为P,，R，缺Q。 则P,，R, P,，R,(Q,，Q),(P ,Q,，R),(P ,，Q,，R) 第三步:用幂等律将重复的极小项删去，即m,m,m然后将各极小iiI 项按顺序排列。 例6:求((P,Q),R),P的主析取范式。 解:原公式,，(，(P,Q),R),P ,((P,Q),，R),P ,(P,，R),(Q,，R),P(析取范式) ,P,(Q,，R)(析取范式) ,(P,(Q,，Q),(R,，R)),((Q,，R),( P,，P)) ,(P,Q,R),(P,Q,，R),(P,，Q ,R),(P,，Q ,，R) ,(P,Q,，R),(，P,Q,，R) (六个极小项，其中重复了一个) ,(P,Q,R),(P,Q,，R),(P,，Q ,R),(P,，Q ,，R) ,(，P,Q,，R) ,m, m, m, m, m24567 ,,(2,4,5,6,7) 5、间接证法 1) CP规则: 有时要证的结论以蕴含的形式出现。要证A1?A2?„?Am,B,C。 如果把结论中的前件B作为附加条件加入前提集合中，即证出了 A1,A2,„,Am,B,C，则原来要证的结论成立。称之为附加前提证明法。 简称CP规则。 证明:A1,A2,„,Am,B,C, A1,A2,„,Am,B,C 证明:A1,A2,„,Am,B,C, A1,A2,„,Am, (B,C) ,，( A1,A2,„,Am),(，B,C),( ，( A1,A2,„,Am), ，B),C , ，( A1,A2,„,Am, B),C,( A1,A2,„,Am, B) ,C ?CP规则成立。 例6:试证(P?(Q?S))?(，R?P)?Q,R?S 前提公式集合P?(Q?S), ，R?P, Q, 结论R?S 将结论R,S中的前项R引入前提集合，而去演绎出S。 证明:(1)，R?P规则P (2)R规则P (附加前提) (3)P规则T由(1) (2) (析取三段论) (4) P?(Q?S) 规则P (5)Q?S规则T由(3) (4) (假言推理) (6)Q规则P (7)S规则T由(5) (6) (假言推理) (8) R?S规则CP 例:证明{，A?B，，B?C，C?D}逻辑的推出A?D 证法1:用CP规则 (1)，A?B规则P (2)A规则P (附加前提) (3)B规则T由(1) (2) (析取三段论) (4) ，B?C 规则P (5)C规则T由(3) (4) (析取三段论) (6) C?D规则P (7)D规则T由(5) (6) (假言推理) (8) A?D规则CP 证法2:不用CP规则 (1)，A?B规则P (2)A?B规则T由(1) (蕴含律) (3) ，B?C 规则P (5)A?C规则T由(2) (4) (假言三段论) (4)B?C 规则T由(3) (蕴含律) (6)C?D规则P (7)A?D规则T由(5) (6) (假言三段论) 2)归谬法 设A1，A2，„，Am是命题公式， 如果A1?A2,„,Am是可满足的，称A1，A2，„，Am是相容的。 如果A1,A2,„,Am是矛盾式，称A1，A2，„，Am是不相容的。 理论根据 A1,A2,„,Am,C,，， A1,A2,„,Am ，,C,，， A1,A2,„,Am,，C) 则A1,A2,„,Am,C，即A1,A2,„,Am,C为重言式，A1,A2,„,Am,，C是矛盾式。 从而得到如A1，A2，„，Am，，C不相容，则C是A1，A2，„，Am的有效结论。 因此我们可以把，C作为附加前提推出矛盾来，从而可以得到C是A1，A2，„，Am的有效结 论。这种方法称为归谬法，也就是我们通常说的反证法。 例7:是证明(R,，Q),(R,S),(S,，Q),(P,Q),，P 证明:(1) P,Q规则P (2)P规则P (附加前提) (3)Q规则T由(1) (2) (假言推理) (4) R,，Q 规则P (5)，R规则T由(3) (4) (拒取式) (6) S,，Q规则P (7)，S规则T由(3) (6) (拒取式) (8) ，R,，S规则T由(4) (7) (合取引入) (9)，，R,S，规则T由(8) (德.摩根律) (10) R,S规则P (11) ，，R,S，,，R,S，规则T由(9) (10) (合取引入) (12) ，，R,S，,，R,S，是矛盾式，所以P为前提公式的有效结论 ?1.7 自我练习 1:求命题公式(P,(P,Q)),R的真值表 自我练习2: 求(P,Q,R),(，P,，Q,，R)的主析取范式。 解:原公式,(，P,(Q,R)),(P,(，Q,，R)) ,(，P,P),(，P,，Q,，R),(Q,R,P),(Q,R,，Q,，R) ,0,(，P,，Q,，R), (P,Q,R),0 ,0,(，P,，Q,，R), (P,Q,R),m0,m7,?(0,7) 自我练习3: ((A,B),C),(B,(D,C)),(B,(D,A)),C 证明:左边,(，(A,B),C),(，B,(D,C)) ,(，A,，B,C),(，B,C,D) 右边,，(B,(，D,A)),C,(，B,(D,，A)),C, (，A,，B,C),(，B,C,D) 所以左边,右边 自我练习4:构造下面推理证明 前提:，，P,，Q，,，Q,R,，R 结论:，P 证明: (1) ，Q,R 规则P (2)，R规则P (3)，Q规则T由(1)(2)(析取三段论) (4)，(P,，Q)规则P (5)，P,Q规则T由(3)(德.摩根律) (6)，P规则T由(3)(5)(析取三段论) 作业: P32 练习1.5:(A)1,3,5(B)1,2,3 P35 习题1: 8(2)(3)(4)(5) 第二章 谓词逻辑 苏格拉底三段论: 凡人要死，苏格拉底是人，所以苏格拉底要死， P:凡人要死 Q:苏格拉底是人 R:苏格拉底要死 此三段论表示为(P,Q),R 苏格拉底三段论是正确的，但P,Q,R却不是重言式，这就是命题逻 辑的局限性。 ?2.1 谓词逻辑的基本概念 一、 谓词 1.个体域: 命题逻辑中将命题(句子)继续细分。命题是由主语和谓语 两部分组成。主语是名词，称之为个体词。是独立存在的客体，可以 是具体事物也可以是抽象概念。 在谓语中含有宾语，它也是名词，它也是个体词。 个体域:客体(个体)的取值范围。 例如:吴华是大学生，用P表示， 李明是大学生，用Q表示。 在命题逻辑中就没办法表示出两句的联系。 “……是大学生”用A(X)表示，x是大学生，命题符号含有个体词变量。 a表示吴华，A(a)表示吴华是大学生。 b表示李明，A(b)表示李明是大学生。 相当于“……是大学生”，用A(?)来表示，这就是谓词。 例:张三比李四高， 用H(x,y)表示x比y高。 a:张三b:李四 H(a,b):张三比李四高 H(b,a):李四比张三高 x,y,a,b表示客体，H(?,?)是谓词这个谓词涉及了两个客体，是二元谓词。 2.谓词: 只涉及一个客体的谓词称为一元谓词，涉及两个客体的谓词称为二元谓词，涉及n个客体的谓词称为n元谓词。 一般，如A表示谓词符号，用X表示第i个客体变项，则ni 元谓词表示为A(x,…,x),如a,a,…,a是个体域中的客体名词，则 1n12n A(a,a,…,a)是个命题。不含客体变项的谓词称零元谓词，零元谓12n 词本身就是命题。 注意: (1) n元谓词中，客体变项的次序很重要 。 例:F(x,y)表示x是y的父亲， a:张三，b:张小明。 F(a,b)表示张三是张小明的父亲。 F(b,a)表示张小明是张三的父亲。 两个命题至多一个是真 (2) 在讨论一个问题是必须先确定好个体域D。 如不作限制，表示宇宙一切事物组成的个体，成为全总个体域。 (3) 同一个n元谓词，取不同的客观，真假会不同。 A(x):x是大学生。 A(a) 真值可能为真，而A(b)真 值可能为假。 (4) 对于同一谓词，个体域D不同，真值可能也不同。 例:对于A(x)，x是大学生。 如D={大学生全体}，A(x)是重言式。 如D={学生全体}，A(x)是仅可满足式。 如D={计算机全体}，A(x)是永假式。 3.命题函数 对于谓词B(x)，B(x,y)，H(x,y,z)等，本身不是命 题。 只有命题变项在D中取出个体名称时才成为一个确定的命题。 故谓词也称为命题函数或简单命题函数。 有限个简单命题函数用联结词，，,，,，,，,，,进行联结而成，成为复合命题函数。 二、 量词: 1.全称量词: “所有的”，“任何一个”，“每一个”，“凡是”，“一切”表示个体域中每一个，用符号“,”表示，称为全称量词。 例1:将下列命题符号化 (1) 所有人都要呼吸 (2) 每个人都是要死的 解: (1)设M(x):x是人，M(x):x是要呼吸。 命题符号化为:, x(M(x),H(x))。 (3) 设M(x):x是人，D(x):x是要死的。 命题符号化为:, x(M(x),D(x))。 2.存在量词: “有些”，“存在”，“至少有一个”，表示个体域D中存在个体，用符号“，”表示。 例2:将下列命题符号化 (1)有些人是聪明和美丽的。 (2)有人早饭吃面包。 解: (1)设M(x):x是人，Q(x):x是聪明的， R(x):x是美丽的。 命题符号化为:，x(M(x),Q(x),R(x))。 (3)设M(x):x是人，E(x):x是早饭时吃面包， 命题符号化为:，x(M(x),E(x)) 说明:命题符号化之前，必须明确个体域的范围，以上两例子均为 全总个体域。 如果将个体域改为D={人类}，则特性谓词M(x)就不需要 了。 例1:(1), xH(x)，(2), xD(x) 例2:(1)，x(Q(x),R(x)) (2)，xE(x) 3.含量词的谓词的真值规定 说明:不含量词的谓词公式G(x) ，它不是命题，而是命题函 数，其真值依赖于x从个体域中取的个体名词的不同而不 同。 例:D表示某班全体学生，G(x)表示x是男生。 则G(李刚)是真，而G(王芳)是假。 而, xG(x)与，xG(x)是命题了，x仅是一个“指导变量” , xG(x)与, xG(y)意义完全相同。 , xG(x):全班每个人均是男生。 ， xG(x):全班存在一个人是男生。 含量词的谓词公式的真值不再依赖于x的选取了。 (1), xG(x)的真值规定 , xG(x)的命题是“对任意x,D，均有G(x)” , xG(x)的真值为1，当且仅当，对一切x,D，G(x)真 值 均为1，, xG(x)的真值为0，当且仅当，对一切x,D， 0 G(x)真 值为0。 0 (2) ，xG(x)的真值规定 ，xG(x)的命题是“存在一个x,D，使得G(x)成00立” ，xG(x)的真值为1，当且仅当存在x,D， 0 G(x)的真值为1。 0 ，xG(x)的真值为0， 当且仅当，对一切x,D， G(x)的真值为0。 例如:D={a,b,c},由以上规定可知: , xG(x),G(a), G(b),G(c) ，xG(x),G(a), G(b), G(c) 注:对于一个谓词，如其每个变量均在量词的管辖下，则该 不是命题函数，而是命题了，它有确定的真值了。 例3 将下列语句表示为谓词逻辑的命题。 (1) 所有的正数均可开方。 )若个体域为全体正实数R+，S(X):X可以开方，则命题符号化为:,xS(x) 解:(i (ii)若个体域为全体实数集R，G(x，y):x>y，则命题符号化为:,x((G(x，0), S(x)) (iii)若D，全总个体域,R(x):x是实数，则符号化为:, x(R(x)?G(x，0), S(x)) 4:03 (2)没有最大的自然数 即理解为“对所有x，若x是自然数，则存在y，y也是自然数，且y>x” 解:N(x):x是自然数，G(x,y):x>y,符号化为:,x(N(x),，y(N(y) ?G(y,x)) 也可以理解为“下句话是不对的‘存在一个x，x是自然数且对一切自然数y，x均大于y’”， 符号化为:，，x(N(x) ?,y(N(y),G(x,y)) 以后可以证明，这两个公式是等值的。 8:15 注:不可以用最大来直接定义谓词。 设B(x):x是最大的，N(x):x是自然数。 以上命题可以表示为:，，x(B(x) ?N(x)) 这是不对的。“最大”是比较而来，依赖于其它客体，最大最小不能直接作谓词。 10:08 ?2.2谓词公式 一、 谓词公式的定义: 1.谓词公式中出现的字母表: 定义1:字母表如下: (1)个体常量:a,b,c,...,a1,a2,a3,... (2)个体变量:x,y,z,...,x1,x2,x3,... (3)函数符号:f,g,h,...,f1,f2,f3,... (4)谓词符号:P,Q,R,...,S0,S1,S2,... (5)量词符号:,,， (6)逻辑符号:，,,,,,,,,,, (7)括号和逗号:(,), 15:10:30 2.项的定义: 项在谓词公式中起的是名词的作用，它不是句子。 定义2:项的递归定义如下: (1)任意个体常量或个体变量是项。 (2)如果f(X1,X2,X3,...,Xn)是任意n元函数，t1,t2,...tn是项，则f(t1,t2,...,tn) 仍然是项。 (3) 只有有限次使用(1) ,(2)生成的符号串才是项。 19:10 例:D是个体名称集，x,D，人名变量，a:张三，b:李四。 x,a,b是项， f(x):x的父亲,S(x,y),x和y的儿子。 f(a): 张三的父亲,仍然是个名词，不是句子，它仍是项。 f(f(a)): 张三的祖父， 而P(x,y):x是y的父亲，是句子而不是名词。其是命题函数，而不是项了。 23:17 例:D:是实数集的全体。 f(x)=lnx，g(x，y)=x+y，h(x，y)=x*y 其均是函数，算术表达式，其结果仍是数，仍可以在函数的自变量位置上出现。 g(g(x，y)，h(x，y))=(( x+y)+( x*y)) f(g(x,y))= ln(x+y) x+y=5,x*y+a>5,此类是逻辑表达式，其结果不是数了，是成立或不成立，是真或 假,因而不是项。 26:51 3(原子公式的定义 原子公式是公式的最小单位，最小的句子单位。项不是公式。 定义3:若P(x1,...,xn)是n元谓词，t1,...，tn是项，则P(t1,...，tn)为原子公式。 (1)从中可以看出，项也可以出现在谓词的变量位置，相当于名词，可以做句子的主语或宾语。 (2)函数f(t1,...，tn)不是句子，仅是词，因而不是公式仅是项。项的结果仍是个体名称集中的名词，而公式的结果(真值)是成立或不成立(是1或0)。30:37 4(谓词公式的定义: 定义4:合式公式的递归定义如下: (1)原子公式是合式公式; (2)如A，B是公式，则，A,A,B,A,B,A,B,A,B,A,B也是公式; (3)如A是公式，x是A中出现的任意有关变元，则,xA,，xA也是合式公式。 (4)只有有限次使用(1)(2)(3)生成的符号串才是合式公式(也称谓词公式) 例:H(a,b),C(x),B(x),,x(M(x),H(x)),，x(M(x),C(x),B(x)), ,x，y(M(x), H(x,y),L(x,y))等均是合式公式。当然以上出现的大写英文字母均是谓词符号。 38:01 二、 约束变量和自由变量 定义5:在合式公式,xA和，xA中，x是指导变元，A为相应量词的作用域或辖域。在辖域中x的出现称为x在公式A中的约束出现;约束出现的变元称为约束变元;A中不是约束出现的其它变元称为该变元的自由出现，自由出现的变元成为自由变元。 40:05 例一 指出各公式的指导变元，辖域、约束变元和自由变元。 (1),x(p(x),，yQ(x,y)) 解:由,x后的()，x是指导变元，,x的辖域是后面整个式子，y是指导变元，辖域仅Q(x，y)此部分。x两次出现均是约束出现，y的一次出现是约束出现，故x，y是约束变元，而不是自由变元。 (2)，xF(x),G(x,y)) 解:，x的辖域仅F(x),x是指导变元，变元x第一次出现是约束出现，第二次出现是自由出现，y的出现是自由出现。所以第一个x是约束变元，第二个x是自由变元，本质上这两个x的含义是不同的;而y仅是自由变元。 45:22 22(3),x(x=y,x+x<5,x