命题逻辑基本概念1.ppt

第一部分 数理逻辑,应用数理逻辑，可以把人类的推理过程分解成一些非常简单原始的、非常和机械的动作，使得用机器代替人类进行推理成为可能 提供程序员设计算法时的思维方法指导,第一部分 数理逻辑,使用电子计算机前，必须先进行程序设计，把整个推理、计算的过程，丝毫不漏地考虑到，统统编入程序，机器则依次运行 必须有足够的数理逻辑训练，熟悉推理过程的全部细节，才能从事程序的设计,第一部分 数理逻辑,程序设计是一个细致而麻烦的工作 如何设计正确的程序？ 如何防止在计算过程中出现错误？ 如何很快地发现这种错误而及时加以改正？ 程序设计理论(软件理论)中的基本而重要的内容 利用数理逻辑可以帮助证明程序(段)正确性,第一章 数理逻辑,主要内容 命题逻辑基本概念 命题逻辑等值演算 命题逻辑的推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理 学习要求 掌握命题、联结词、复合命题、命题公式、等值式、等值演算、推理及证明等基本概念 熟练进行等值演算与构造证明,命题(proposition),命题与真值 命题：判断结果惟一的陈述句(断言 assert) 真值：命题的判断结果 取值=真/假 T/F True/False 1/0 真命题与假命题 二值逻辑：vs. 多值逻辑、模糊逻辑,Example,sqrt(5) 是有理数 F 2 + 5 7 T x + 5 3 你去教室吗？ 这个苹果真大呀！ 请不要讲话！ 2025年元旦下大雪 我正在说假话 今天是星期五 7 是命题，它的真值现在不知道，到2025年元旦就知道了。命题真值一定是客观存在的，现在可以不知道,命题,注意 判断结果唯一性：“放之四海皆准” 时间性 区域性 标准性 不是命题 感叹句、祈使句、疑问句 悖论、判断结果不惟一的陈述句,命题符号化,简化、形式化 (简单)命题：小写英文字母p，q，r，pi，qi，ri 真值：“1”=真，“0”=假 Example p： 是有理数，真值=0 q：2 + 5 = 7，真值=1,课程时间调整安排,计科08、网络08合班上课 第619周一10, 11节，4313(CAI) 第69周二6, 7节，4515 第1019周二3, 4节，4518(CAI),命题概念小结,弄清概念 命题 命题的真值 真命题、假命题 学会(简单)命题符号化,(简单)命题符号化,Example p： 是有理数，真值=0 q：2 + 5 = 7，真值=1 ？目前的命题概念能够满足需要吗？ ？有无比目前命题形式更复杂的陈述句？,联结词与复合命题,2是偶数而3是奇数 p: 2是偶数而3是奇数 合适吗？ 该语句描述了2个事实，用一个符号表示，不合适！ 原语句可分解为2个陈述句 2是偶数 3是奇数 用连词“而且”将2个陈述句合为一句 2是偶数，而且， 3是奇数,联结词与复合命题,2是偶数，而且， 3是奇数 2是偶数 p：2是偶数 3是奇数 q：3是奇数 而且： 2是偶数而3是奇数：pq 复合命题,联结词与复合命题,简单命题、原子(atom)命题 不能再分解 复合命题(compound proposition) 使用联结词(connective)组合一个或多个命题构造得到的新命题 联结词：逻辑运算符(logical operator),联结词与复合命题,否定式与否定联结词“” 定义(definition): 设p为命题，复合命题“非p” 称为p的否定(negation)式 记作：p ：否定联结词 规定：p 为真当且仅当p为假,真值表,描述命题真值的所有取值 确定由简单命题组成的复合命题的真值,联结词与复合命题,合取式与合取联结词“” 定义：设p，q为二个命题，复合命题“p并且q” ，称为p与q的合取(conjunction)式 记作：pq ：合取联结词 规定：pq为真当且仅当p与q同时为真,联结词与复合命题,合取式与合取联结词“”,联结词与复合命题,合取式与合取联结词“” 描述合取式的灵活性与多样性 吴颖既用功又聪明 吴颖虽然聪明，但是不用功 吴颖不仅用功而且聪明 吴颖一面看书，一面吃苹果 王华与张兰都是好学生 王华是好学生，并且张兰是好学生 C 分清简单命题与复合命题 王华与张兰是同学 S,联结词与复合命题,合取式与合取联结词“” 可联结相互无关系的命题 235 且 天正在下雨,联结词与复合命题,析取式与析取联结词“” 定义：设p, q为二命题，复合命题“p或q”称作p与q的析取式 记作：pq ：析取联结词 规定：pq为假当且仅当p与q同时为假,联结词与复合命题,析取式与析取联结词“”,自然语言中“或”的两种含义,相容(inclusive)或、可兼或 2或4是素数 2或3是素数 4或6是素数,自然语言中“或”的两种含义,排斥(exclusive)或、异或 小元元只能拿一个苹果或一个梨 p:拿苹果，q: 拿梨 符号化：(p q) ( p q)、p q 王小红生于1975年或1976年 p: 生于1975，q: 生于1976) 符号化：(p q) ( p q) pq,联结词与复合命题,析取式与析取联结词“” 可联结无关系命题 235 或 天正在下雨,联结词与复合命题,蕴涵(implication)式与蕴涵联结词“” 定义：设p, q为二个命题，复合命题“如果p, 则q”称作p与q的蕴涵式(或条件式) 记作：pq p前件(antecedent)、前提(hypothesis)、假设(premise) q后件(consequence)、结论(conclusion) ：蕴涵联结词 规定：pq为假当且仅当p为真q为假,联结词与复合命题,蕴涵式与蕴涵联结词“”,联结词与复合命题,蕴涵式与蕴涵联结词“” pq的逻辑关系 p是q的充分(sufficient)条件 q是p的必要(necessary)条件 区分充分条件与必要条件 如果G是正方形，那么G的四边相等：前“充分”后“必要” 如果G是等边三角形，那么G的三个角相等：互为“充要”,联结词与复合命题,蕴涵式与蕴涵联结词“” pq的不同表述 如果p, 则q 若p，就q 只要p，就q p仅当q 只有q 才p 除非q, 才p 除非q，否则非p ,联结词与复合命题,当p为假时，pq为真 空证明：前提为假，任意结论都可能 如果太阳从西方出，雪就是黑的 前假、后假，肯定假 如果太阳从西方出，我就不姓黄 实际生活中的常用说法 如果太阳从西方出，我就姓黄 结论本身是正确的 天下雨，路就会湿 若天未下雨，路湿或路不湿都可能,联结词与复合命题,实际生活中的蕴涵 “如果/则”()描述的对象之间一般有内在联系，有推理的含义 有因果：原因结果 能推导：条件结论,联结词与复合命题,命题逻辑中的蕴涵：实质蕴涵 前后可无因果关系 只有“前后”、“左右” 如果天下雨，那么2+3=5 不一定是条件与结论 如果我去商店，就给你买苹果 若我没去商店，但在市场买了苹果 推测：假设推论,联结词与复合命题,实际逻辑 vs. 命题逻辑 实际含义 vs. 形式语义 形式逻辑：抽象化实际逻辑 “重结构、轻内容” 只处理真假关系，不涉及内容、意义,联结词与复合命题,蕴涵式与蕴涵联结词“” 蕴涵 vs. if 语句 语句”if p then s”、“if (p) s;” if 2+3=5 then x=x+1 if 语句蕴涵,复合命题符号化,p：天冷，q：小王穿羽绒服 pq 如果天冷，小王就穿羽绒服 因为天冷，所以小王穿羽绒服 只要天冷，小王就穿羽绒服 若小王不穿羽绒服，则天不冷,复合命题符号化,p：天冷，q：小王穿羽绒服 qp 只有天冷，小王才穿羽绒服 除非天冷，小王才穿羽绒服 如果天不冷，则小王不穿羽绒服 小王穿羽绒服仅当天冷时,逆/反命题,pq：只要天冷，小王就穿羽绒服 逆(converse)命题：qp 小王穿羽绒服仅当天冷时 反(inverse)命题： p q 如果天不冷，则小王不穿羽绒服 逆反命题： q p 若小王不穿羽绒服，则天不冷 pq 与 q p等值(真值相同),逆/反命题,联结词与复合命题,等值(equivalence)式与等值联结词“” 双条件(bi-conditional) 定义：设p，q为二个命题，复合命题“p当且仅当q”称作p与q的等值式 记作：pq ：等值联结词 规定：pq为真，当且仅当，p与q同真或同假,联结词与复合命题,等值式与等值联结词“”,联结词与复合命题,等值式与等值联结词“” p q的逻辑关系：p与q互为充分必要条件 2 + 2 4当且仅当3 + 3 6 2 + 2 4当且仅当3 是偶数 2 + 2 4当且仅当太阳从东方升起 2 + 2 4当且仅当美国位于非洲 函数f (x)在x0可导的充要条件是它在x0连续,命题基本概念小结,p, q, r, 均表示命题 联结词集为, p、pq、pq、pq、pq 基本复合式 难点：pq,命题基本概念小结,复杂陈述句翻译成复合命题/复杂逻辑式 反复使用,联结词 设p: 是无理数，q:3是奇数，r:苹果是方的，s:太阳绕地球转 (pq)(rs)p)：假命题 联结词运算顺序 优先级：(), , , , , 同级：从左到右,逆/反命题,命题逻辑基本概念的应用,搜索引擎 可视化逻辑运算符 Google、Baidu、CNKI 布尔搜索(Boolean Searching)技术 北京 AND 四合居 AND 照片 OR 视频 北京 AND 四合居 AND (照片 OR 视频),命题逻辑基本概念的应用,程序设计语言(C、Visual Basic)位操作 &、or |、and xor：异或,命题逻辑基本概念的应用,思考题,古西西里的剃头匠传说 有个住在边远小镇的剃头匠，必须穿过一条危险的山路才能找到他。他只给那些不自己剃须的人刮胡子。这样的剃头匠存在吗？,思考题,说谎的村民 有个村庄的人要么只说真话，要么只说假话，回答问题时只说“是”、“不”。假定你在那儿旅游，走到一个左右分岔的路口，一条到遗址，一条到废墟，此时恰有一村民在路口。请问你应该如何发问，才能找到正确的方向？,命题变项与(合式)公式,命题变项(变元 variable) 命题常项(constant) 0、1 命题变项 约定：小写字母 p, q, r, , pi, qi, ri, ,命题变项与合式公式,(合式)公式(well-formed formula, wff) 单个命题变项、命题常项是原子公式 若A是公式，则(A)是公式 若A, B是公式，则(AB)、(AB)、(AB)、(AB)是公式 有限次应用规则 13 形成的是(合式)公式,命题变项与合式公式,(合式)公式 约定：大写字母 外层括号可以省去 归纳(induction)或递归(recursive)定义 元语言和对象语言 元语言：描述对象语言的语言 对象语言：描述研究对象的语言,命题变项与合式公式,合式公式的层次 若公式A是单个的命题变项，则称A为0层合式 称A是n+1(n0)层公式是指下面情况之一 A=B，B是n层公式 A=BC，其中B,C分别为i层和j层公式，且n=max(i,j) A=BC，其中B,C的层次及n同上 A=BC，其中B,C的层次及n同上 A=BC，其中B,C的层次及n同上 若公式A的层次为k，则称A为k层公式,命题变项与合式公式,合式公式的层次 A=p，0层 B=p，1层 C=pq，2层 D=(pq)r，3层 E=(pq) r) (rs)，4层,公式赋值,赋值：用命题常项替换命题变项 定义：设p1,p2,pn是公式A中的命题变项，给p1,p2,pn各指定一个真值，称为对A的一个赋值(assignment)或解释(interpretation) 赋值：与命题变项位置一一对应的0,1串 成真赋值：使A真值=1的赋值 成假赋值：使A真值=0的赋值,公式的赋值(解释),赋值：0、1串 按在公式A中命题变项出现的位置顺序赋值 含n个变项的公式有2n个赋值(串) Ex. (pq) r 成真赋值：000, 010, 101, 110 成假赋值：001, 011, 100, 111,公式的类型,重言式(tautology)：永真式 矛盾式(contradiction)：永假式 可满足式(satisfaction)：不是矛盾式 一般式(contingency) 重言式是可满足式，但反之不真,公式的类型,Example 重言式：(pp)q 矛盾式：(pp)q 可满足式：pq 如何判断公式的类型？ 如何求公式A的全部的成真与成假赋值？,真值表,定义 A的真值表：A的所有取值情况列表 Example A = (pq)r B = (qp)qp C = (pq)q,A = (pq)r 真值表,B = (qp)qp 真值表,C = (pq)q 真值表,真值表,编制方法(P2页) 中间层次可不写 用途 从中得知公式 A 的一切信息 所有的可能赋值 公式的所有取值 公式的类型 其它用途？(待续),命题与公式小结,内容 命题、真值、命题的分类、命题符号化 联结词,、复合命题 命题公式及层次 公式类型 真值表,命题与公式小结,要求 深刻理解各联结词的逻辑关系 会求复合命题的真值 熟练地将复合命题符号化 准确地求公式的真值表 求公式成真赋值、成假赋值 判断公式类型,练习题,1. 将下列命题符号化 豆沙包是由面粉和红小豆做成的 苹果树和梨树都是落叶乔木 王小红或李大明是物理组成员 王小红或李大明中的一人是物理组成员 由于交通阻塞，他迟到了 如果交通不阻塞，他就不会迟到 他没迟到，所以交通没阻塞 除非交通阻塞，否则他不会迟到 他迟到当且仅当交通阻塞,练习题,解析 分清复合命题与简单命题 分清相容或与排斥或 分清必要与充分条件及必要充分条件,练习题,答案(14) 豆沙包是由面粉和红小豆做成的：简单命题 p: 豆沙包是由面粉和红小豆做成的 苹果树和梨树都是落叶乔木：合取式 p: 苹果树是落叶乔木 q: 梨树是落叶乔木 pq,练习题,答案(14) 王小红或李大明是物理组成员：析取式 王小红是物理组成员: p 李大明是物理组成员: q 王小红或李大明是物理组成员: pq 相容或,练习题,答案(14) 王小红或李大明中的一人是物理组成员：析取式 王小红是物理组成员