离散数学 课件 PPT 精品课程 考研 大学课程 数学一 第一章 命题逻辑.ppt

第1章 命题逻辑 数理逻辑是用数学方法来研究推理的形式结构和 推理规律的数学学科。 现代数理逻辑可分为逻辑演算、证明论、公理集 合论、递归论和模型论。 本课程介绍的是数理逻辑最基本的内容，也是与 计算机科学关系最为密切的：命题逻辑和谓词逻辑 （一阶逻辑） 主要内容 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值值演算 1.4 联结词联结词 全功能集 1.5 对对偶与范式 1.6 推理理论论 1.1 命题符号化及联结词 命题：能判断真假的陈述句。 真值：一个命题表达的判断结果称为命题的真值 。命题的真值有“真”和“假”两种，分别用True、T、 1(真)和False、F、0(假)来表示。真值为真的命题称 为真命题，真值为假的命题称为假命题。任何命题 的真值是惟一的。 注: 一切没有判断内容的句子，无所谓是非的句子 ，如感叹句、疑问句、祈使句等都不是命题。 例1： n2是素数。 n雪是黑色的。 n2+3=5 。 n明年十月一日是晴天。 n这朵花多好看呀！ n3能被2整除. n明天下午有会吗？ n请关上门！ nx+y5 。 n地球外的星球上也有人。 命题判断的关键： 1.是否是陈述句； 2.真值是否是唯一的。 简单命题（原子命题）：不能分解为更简 单的陈述句。 简单命题又称为命题常项或命题常元。对 于真值可以变化的简单陈述句称为命题变项 或命题变元。 复合命题：由联结词把几个原子命题联结 起来的命题。 表示法： 表示法例子有关概念 简单命题p,q,r, pi,qi,ri, p: 2是素数 q:雪是黑色的 命题符号化：将命题 的符号放在该命题的 前面 命题常项 （常元） 同上同上真值确定的简单命题 命题变项 （变元） 同上p: x+y5真值可以变化的简单 陈述句 复合命题pq2是素数和偶数 注：一个符号表示的是命题常项还是命题变项由上下文决定 。 例2：将下列各命题符号化 1. 3不是偶数. 2. 2是素数和偶数. 3. 林芳学过英语或日语. 4. 如果角A和角B是对顶角,则角A等于角 B. 1. 否定联结词 定义1.1 设p为命题，则p的否 定是一个复合命题，记作：p，读 作“非p”或“p的否定”。 为否定联 结词。p为真当且仅当p为假。 表1.1 p p 0 1 1 0 【例】否定下列命题。 p：王强是一名大学生。 p：王强不是一名大学生。 命题联结词 常用的逻辑联结词有五种：否定联结词、合取 联结词、析取联结词、蕴涵联结词和等价联结词。 2. 合取联结词 定义1.2 设p和q均为命题， 则p和q的合取是一个复合命题 ，记作pq，读作“p与q”或“p 合取q”。 为合取联结词。 pq为真当且仅当p和q同时为 真。 表1.2 pqpq 0 00 010 100 111 【例】设 p：北京成功举办了第29届夏季奥运会。 q：今年10月1日是我国国庆60周年。 则pq：北京成功举办了第29届夏季奥运会并且今年10 月1日是我国国庆60周年。 例3：将下列各命题符号化 n李平既聪明又用功. n李平虽然聪明，但不用功. n李平不但聪明，而且用功. n李平不是不聪明，而是不用功. 3. 析取联结词 定义1.3 设p和q均为命题 ，则p和q的析取是一个复合 命题，记作pq，读作“p或 q”或者“p析取q”。 为析取 联结词。pq为真当且仅当p 与q中至少一个为真。 表1.3 pqpq 000 011 101 111 “”与汉语中的“或”相似，但又不相同。汉语中的或有 可兼或与不可兼或(排斥或)的区分。 【例】下列两个命题中的“或”，哪个是可兼或？哪个是不 可兼或？ 在家里看奥运会或在现场看奥运会。(不可兼或) 灯泡有故障或开关有故障。(可兼或) 注：“”是可兼或。 4. 蕴涵联结词 定义1.4 设p和q均为命题， p与q的蕴涵式是个复合命题，记 为：pq。读作“如果p，那么q” 或“若p，则q”。 为蕴涵联结词 。pq为假当且仅当p为真且q为 假。p称为条件命题pq的前件 ，q称为条件命题pq的后件。 表1.4 pqpq 001 011 100 111 【例】 p：小王努力学习。q：小王学习成绩优秀。 pq：如果小王努力学习，那么他的学习成绩就优秀 。 联结词“”与汉语中的“如果，那么”或“若，则 ”相似，但又是不相同的。 例4：将下列各命题符号化 n只要不下雨，我就骑自行车上班. n只有不下雨，我才骑自行车上班. n若2+2=4，则太阳从东方升起. n若2+24，则太阳从东方升起. n若2+2=4，则太阳从西方升起. n若2+24，则太阳从西方升起. 5. 等价联结词 定义1.5 设p和q均为命题 ，其复合命题pq称为等价式 ， pq读作：“p当且仅当q”。 为等价联结词。pq为真当 且仅当p和q的真值相同。 表1.5 pqpq 001 010 100 111 【例】 p：张华是三好学生。 q：张华德、智、体全优秀。 pq：张华是三好学生当且仅当德、智、体 全优秀。 例5 分析下列各命题的真值 n2+2=4当且仅当3是奇数. n2+2=4当且仅当3不是奇数. n2+24当且仅当3是奇数. n2+24当且仅当3不是奇数. 联结词的比较表 p,q为两个命题 注：以上5种联结词也称真值联结词或逻辑联结词或逻辑运 算符。 n小王是游泳冠军或百米赛跑冠军. n小王现在在宿舍或图书馆里. n选小王或小李中的一人当班长. n如果我上街，我就去书店看看，除非我很 累. n王一乐是计算机系的学生，他生于1968或 1969年，他是三好学生. 例6：将下列命题符号化 1.2 命题公式及分类 定义1.6 按下列规则构成的符号串称为命题演算 的合式公式，也称为命题公式，简称公式。 单个命题常项或变项p,q,r,pi,qi,ri,，0 ，1是合式公式； 如果A是合式公式，那么(A)是合式公式； 如果A和B是合式公式，那么(AB)、(AB) 、(AB)和(AB)是合式公式； 只有有限次地应用了、所得到的符 号串是合式公式。 命题公式一般的用大写的英文字母A，B，C， 表示。 依照这个定义，下列符号串是合式公式： (pq)， (p(pq)， (pq)(qr)(st) 下列符号串不是合式公式： (pq)(q)，(pq(pq)q) 定义1.6给出合式公式定义的方法称为归纳定 义，它包括三部分：基础，归纳和界限。定义1.6 中的是基础，和是归纳，是界限。 今后还将多次出现这种形式的定义。 为方便起见，对命题公式约定如下： 最外层括号可以省略； 规定联结词的优先级由高到低依次为， ，。按此优先级别，如果去掉括号， 不改变原公式运算次序，也可以省掉这些括号。 一般地说，命题公式中包含命题变元，因而无 法计算其真值，所以不是命题。 命题公式中的命题变元，也叫命题公式的分量 。 定义1.7 命题公式的层次的定义： n若A是单个命题（常项或变项）， p,q,r,pi,qi,ri,0,1,则称A是0层公式. n称A是n+1(n0)层公式是指A符合下列情况之一： A= B,B是n层公式； A= BC，其中B，C分别为i层和j层公式，且 n=max(i,j)； A= BC，其中B，C的层次同； A= BC，其中B，C的层次同； A= BC，其中B，C的层次同； 若A的最高层次为k，则称A是k层公式. 对一个公式的解释和赋值定义如下： 定义1.8 设A为一个命题公式，p1, p2,， pn为出现在A中的所有的命题变项。给p1, p2,， pn指定一组真值，称为对A的一个赋值或解释。若 指定的一组值使A的值为真，则称这组值为A的成 真赋值，若使A的值为假，则称这组值为A的成假 赋值。 例如，给公式(pqr)赋值011是指p=0，q=1， r=1，它是该公式的成真赋值；赋值110是指p=1， q=1，r=0，它是该公式的成假赋值。 含n个命题变项的命题公式，共有2n组赋值 。将命题公式A在所有赋值之下取值的情况列 成表，称为A的真值表。 构造真值表的步骤： n找出命题公式中所含的所有命题变项p1, p2,，pn ，列出所有可能赋值（ 2n 个）； n按从低到高的顺序写出各层次； n对应每个赋值，计算命题公式各层次的值， 直到最后计算出命题公式的值。 pqrrq rp (q r) 000110 001000 010110 011010 100111 101000 110111 111011 例7：求下列命题公式的真值表 （1） p (q r)； （2）(p(pq)q ； pqpqp(pq) (p(pq)q 00101 01101 10001 11111 （3） (pq)q ； pqpq(pq)(pq)q 00100 01100 10010 11100 定义1.9 设A为一个命题公式 n若A在它的各种赋值下取值为真，则称A为重言式 或永真式. n若A在它的各种赋值下取值为假，则称A为矛盾式 或永假式. n若A至少存在一组赋值是成真赋值，则称A为可满 足式. 由定义1.9可以看出，任何重言式都是可满足的。 显然，重言式的真值表的最后一列全为1，矛盾式 的真值表的最后一列全为0，可满足的公式真值表 的最后一列至少有一个1。 1.3 等值演算 定义1.10 设A,B为两个命题公式，若等价式 AB是重言式，则称A与B是等值的，记作 AB. AB不是命题公式 可通过判断A与B的真值表是否相同，来判 断A与B是否等值。 例8：判断下列命题公式是否等值 （1） (pq)与pq ； （2） (pq)与pq ； pqp qpq(pq)pqpq 00110111 01101010 10011010 11001000 l根据已知的等值式推演出另外一些等值式的过程 称为等值演算。 定理1.1（置换定理） 设(A) 是含命题公式A的命题 公式，(B)是用命题公式B置换了(A)中的A之后得 到的命题公式。如果AB，则(A)(B)。 l等值演算的用途： （1）验证两个公式等值； （2）判别命题公式的类型； （3）解决实际问题. 例9：验证下列等值式. （1） p(qr) (pq)r； （2） p(pq)(pq). 例10：判别下列公式的类型. （1） q(pq)p)； （2） (pp)(qq)r)； （3） (pq)p. 例11：用等值演算法解决下面问题. A、B、C、D四人百米竞赛.观众甲、乙、丙预测比 赛名次为： 甲：C第一，B第二； 乙：C第二，D第三； 丙：A第二，D第四. 比赛结束后发现甲、乙、丙每人预测的情况都各对 一半，试问实际名次如何（假设无并列情况）？ 1.4 联结词全功能集 一个n(n1)维卡氏积0,1n到0,1的函数称为一个 n元真值函数。设F是一个n元真值函数，则可记为F ：0,1n0,1 在一个联结词的集合中，如果一个联结词可由集 合中的其他联结词定义，则称此联结词为冗余的联 结词，否则称为独立的联结词。 若任一真值函数都可以用仅含某一联结词集中的 联结词的命题公式表示，则称该联结词集为全功能 集。若一个联结词的全功能集中不含冗余的联结词 ，则称它是极小全功能集。 例12：分别以下列给出的各联结词集中的联结词 写出命题公式(pq)的等值式. (1),; (2), ;(3); (4). 定义1.17 仅含有联结词,的命题公式 A中,将换成,换成,若A中含0或1,就将 0换成1,1换成0,所得命题公式称为A的对偶式, 记作A*. 从定义不难看出,A是A*的对偶式,即对偶式是 相互的.又(A*)*A. 1.5 对偶与范式 定理1.2 设A和A*互为对偶式,p1,p2,pn是 出现在A和A*中的全部的命题变项,若将A和A* 写成n元函数形式,则 (1) A(p1,p2, ,pn)A*( p1, p2, , pn); (2) A( p1, p2, , pn) A*(p1,p2,.,pn). 例:A(p,q,r) p ( qr) 0 则 A*(p,q,r) p( qr) 1 A(p,q,r) p(q r) 1; A*(p,q,r) p(qr)1; 所以, A(p,q,r) A*( p, q, r). 类似地,有A(p, q, r) A*(p,q,r) 定理1.3(对偶原理) 设A,B为两命题公式,若 A B,则A* B*,其中A*,B*分别为A,B的对 偶式. 由对偶原理可知, 若A为重言式,则A*必为矛盾式. 例如, 设 A p( p(q q), 则 A* p( p(q q) A p( p0) p p 1, A* 0. 已知A B,且B是比A简单的命题公式,则由对 偶原理可直接求出较简单的B*与A*等值.例如 (pq) ( p(pq) pq, 则 (pq)(p( pq) pq. 判定问题及判定方法 方法1: 真值表法; 方法2: 等值演算法. 方法3: 当命题变项的数目较多时, 可把命 题公式化成标准型(主析取范式和主合取范 式).使同一真值函数所对应的所有命题公式 具有相同的标准型 定义1.18.1 仅由有限个命题变项或其否定 构成的析取式称为简单析取式. 例如 pq、pq、pq、q、p、q 定义1.18.2 仅由有限个命题变项或其否定 构成的合取式称为简单合取式. 例如 pq、pq、pq、p、q、p 从定义不难看出 (1)一个简单析取式是重言式,当且仅当它 同时含一个命题变项及其否定; (2)一个简单合取式是矛盾式,当且仅当它 同时含一个命题变项及其否定. 定义1.19 (1)仅由有限个简单合取式构成的 析取式称为析取范式; (2)仅由有限个简单析取式构成的合取式称 为合取范式. 设AA1A2An,Ai(i1,2,n)为简 单合取式,则A是析取范式, 设AA1A2An,Ai(i1,2,n)为简 单析取式,则A是合取范式. 任何析取范式的对偶式为合取范式; 任何合取范式的对偶式为析取范式. 性质: (1)一个析取范式是矛盾式,当且仅当它的 每个简单合取式都是矛盾式; (2)一个合取范式是重言式,当且仅当它的 每个简单析取式都是重言式. 定理1.4(范式存在定理) 任一命题公式都存 在着与之等值的析取范式和合取范式. 所用的基本等值式是 p q pq; p q ( pq)(p q); p q (p q)(pq); pq (pq); pq (pq). v(1)消去对,来说冗余的联结词; 求范式的具体步骤(3步) 利用双重否定律和德摩根律,即 p p; (pq) p q; (pq) p q; v(2)否定号的消去或内移; 最后,若是求析取范式,应该利用“”对“” 的分配律;若是求合取范式,应该利用“”对 “”的分配律. 任给一个命题公式A,经过以上三步演算,即 得到一个与A等值的析取范式或合取范式. 任何命题公式的析取范式和合取范式都不 是唯一的. v(3)利用分配律. 例1.14 求下面命题公式的合取范式和析取 范式. (pq) r) p. 解 (1)求合取范式 (pq ) r) p ( (pq)r) p (消去第一个) (pq)r)p (消去第二个) (p q)r)p (内移) ( p q) r)p (内移) (pq) r)p (消去) (pqp)(rp) (对分配律) 再利用交换律和等幂律得 (pqp)(rp) (pq)(rp), 可见,(pq)(rp)也是原公式的合取 范式,这说明与某个命题公式等值的合取范 式是不唯一的. (2)求析取范式 用对的分配律就可得到析取范式,即 (pq) r) p (pq) r)p (p r)(q r)p (对分配律) 最后结果为原公式的析取范式.利用交换 律和吸收律得p(q r),也是原公式的析取 范式,由此可见,与命题公式等值的析取范式 也是不唯一的. 定义1.20 在含n个命题变项的简单合取式 中,若每个命题变项与其否定不同时存在,而 二者之一必出现且仅出现一次,且第i个命题 变项或其否定出现在从左起的第i位上(若命 题变项无角标,则按字典顺序排序),这样的简 单合取式称为极小项. 3个命题变项，8个极小项对应情况如下： pqr 000 0, 记作m0； pqr 001 1, 记作m1； p qr 010 2, 记作m2； p qr 011 3, 记作m3； pqr 100 4, 记作m4； p q r 101 5, 记作m5； p qr 110 6, 记作m6； p qr 111 7, 记作m7. 一般情况下,n个命题变项共产生2n个极小项,分别 记为m0,m1,.m2n-1. 定义1.21 设命题公式A中含n个命题变项,如 果A的析取范式中的简单合取式全是极小项, 则称该析取范式为A的主析取范式. 定理1.5 任何命题公式的主析取范式都是存 在的,并且是唯一的. 求给定命题公式A的主析取范式的步骤 (1)求A的析取范式A. (2)若A的某简单合取式B中不含命题变项pi或其否 定 pi,则将B展成如下形式： B B1 B(pipi) (Bpi)(Bpi). (3)将重复出现的命题变项、矛盾式及重复出现的 极小项都“消去”,如pp用p代,pp用0代,mimi 用mi代. (4)将极小项按由小到大的顺序排列,并用表示之. 如m1m2m5用(1,2,5)表示. 例1.15 求例1.14中给出的命题公式的主析 取范式. (pq) r) p. 解 由例1.14可知, 原公式的析取范式为, p (q r) 用p(qq)(rr)取代p. 用(pp)(q r)取代(q r). 然后展开得极小项. (pq) r) p p(q r) (析取范式) (p(qq) (rr) (pp)(q r) (pqr)(pqr) (p q r)(p q r) (pqr)(p q r) m4 m5 m6m7m2m6 m2m4m5m6m7 (2,4,5,6,7). 由极小项的定义可知,上式中,2,4,5,6,7的二进制表 示010,100,101,110,111为原公式的成真赋值,而此公 式的主析取范式中没出现的极小项m0,m1,m3的角码 0,1,3的二进制表示000,001,011为原公式的成假赋 值.因而,只要知道了一个命题公式A的主析取范式,可 立即写出A的真值表. 反之,若知道了A的真值表,找出所有的成真赋值,及 其对应的十进制数作为角码的极小项即为A的主析取 范式中所含的全部极小项,从而可立即写出A的主析 取范式. 例1.16 试由pqr的真值表求它的主析取范式. pqrp qp q r 00000 00101 01000 01101 10000 10101 11011 11111 pqr m1m3m5m6m7 (1,3,5,6,7). 主析取范式的用途 由于任何命题公式的主析取范式都是唯一 的,因而 若A B,说明A与B有相同的主析取范式. 反之,若A,B有相同的主析取范式,必有A B. 1.判断两命题公式是否等值. 2.判断命题公式的类型 设A是含n个命题变项的命题公式, A为重言式,当且仅当A的主析取范式中含 全部2n个极小项. A为矛盾式,当且仅当A的主析取范式中不 含任何极小项,可设A的主析取范式为0. 若A的主析取范式中至少含一个极小项,则 A是可满足式. 例1.17 判断下列命题公式的类型. (1) (pq)q； (2)(pq)p)q； (3)(pq)q. 解 (1) (pq)q (pq)q pqq 0. (2)(pq)p) q (pq)p)q (pq) pq (pq) pq (pq)p(qq)(pp)q (pq)( pq)(p q)(pq) m0m1m2m3 (0,1,2,3). (3)(pq)q (pq)q (pq)q (pp) (pq)(pq) m1m3. (1,3). 由以上推演可知,(1)矛盾式,(2)为重言式, (3)为可满足式. 3.求命题公式的成真和成假赋值. 在上例(2)中(pq)q (1,3). 01,11是成真赋值,00,10是成假赋值. 定义1.22 在含n个命题变项的简单析取式 中,若每个命题变项与其否定不同时存在,而二 者之一必出现且仅出现一次,且第i个命题变项 或其否定出现在左起的第i位上(若命题变项无 角码,则按字典顺序排列),这样的简单析取式 称为极大项. 同极小项情况类似,n个命题变项可产生2n个 极大项,每个极大项对应一个二进制数和一个 十进制数.二进制数为该极大项的成假赋值,十 进制数作为该极大项抽象表示的角码. 3个命题变项，8个极大项对应情况如下： pqr 0000，记作M0 pqr 0011，记作M1 pqr 0102，记作M2 pqr 0113，记作M3 pqr 1004，记作M4 pqr 1015，记作M5 pqr 1106，记作M6 pq r 1117，记作M7 定义1.23 设命题公式A中含n个命题变项,如 果A的合取范式中的简单析取式全是极大项, 则称该合取范式为主合取范式. 任一命题公式的主合取范式一定存在,且是 唯一的. 求一命题公式A的主合取范式的步骤: （1）先求出合取范式A. （2）若A的某简单析取式B中不含命题变项 pi ,或其否定pi,则将B展成如下形式： BB0B(pi pi)(Bpi)(B pi). 例1.18 求pqr的主合取范式. 解 (pq) r (pr)(qr) (合取范式) (p(q q)r)(p p)qr) (pqr)(p qr) (pqr) ( pqr) (pqr)(p qr)(pqr) M0M2M4 (0,2,4), 其中表示合取. mi Mi， Mi mi. 设命题公式A中含n个命题变项,且设A的主析 取 范式中含k个极小项mil,mi2,mik则 A的主析 取 范式中必含2n-k个极小项,设为mjl,mj2, , , 即 A mjl mj2 A A (mjl mj2 ) mjl mj2 Mjl Mj2 极小项与极大项之间的关系 由A的主析取范式求主合取范式的步骤 (1)求出A的主析取范式中没包含的极小 项mj1,mj2, . (2)求出与(1)中极小项角码相同的极大项 Mj1,Mj2, . (3)由以上极大项构成的合取式为A的主 合取范式. 例如,A中含3个命题变项,主析取范式为 A m0m1m5m7 (0,1,5,7) 则主合取范式为 A M2M3M4M6 (2,3,4,6). 通过主合取范式也可以判断公式之间是否 等值，判断公式的类型，求成假赋值等. 1.6 推理理论 数理逻辑的主要任务是用逻辑的方法研究数学 中的推理。所谓推理是指从前提出发，应用推理规 则推出结论的思维过程。任何一个推理都由前提和 结论两部分组成。前提就是已知的命题公式，结论 则是从前提应用推理规则推出的命题公式。 定义1.24 若(A1A2Ak)B为重言式， 则称A1,A2,Ak推出结论B的推理正确，B是 A1,A2,Ak的逻辑结论逻辑结论 或有效结论结论 .称 (A1A2Ak)B为由前提A1,A2,Ak推出结 论B的推理的形式结构. 用“AB”表示“AB”是重言式. 因而，若由前提 A1，A2，Ak推出结论B的推理正确，也记 (A1A2Ak)B. 由定义1.24可以看出，要证明B是一组前提A1，A2 ，Ak 的有效结论，只需证明 A1A2AkB为重言式。 证明一个公式为重言式，可以用真值表、等价演 算、主析(合)取范式等方法进行。 例1.19 判断下面各推理是否正确. （1）如果天气凉快，小王就不去游泳. 天气凉快. 所以小王没去游泳. （2）如果