第1章 基础：逻辑和证明 1.1 命题逻辑

1.1 命题逻辑 形式逻辑：采用抽象符号表示推理过程 利用符号，可以把人的推理过程分解成一些简单、原始、机械的步骤 使得用计算机代替人进行推理成为可能

1.1 命题逻辑 程序设计时，需要把整个推理及计算过程，丝毫不漏地全盘考虑到，并统统编入程序，机器才能依次执行 必须有足够的数理逻辑训练，熟悉推理过程的全部细节，才能做好程序设计

1.1 命题逻辑 程序设计是一个细致而麻烦的工作 如何设计正确的程序？ 逻辑正确是程序(段)正确的必要条件 如何防止在计算过程中出现错误？，如何很快地发现这种错误而及时加以改正？ 逻辑可以帮助证明程序(段)的正确性

1.1 命题逻辑 基本概念 基础工具 相关应用 命题、真值 逻辑运算符(联结词) 真值表 逻辑表达式、布尔检索、逻辑难题、位运算 非、与、或、蕴含、双蕴含 基础工具 真值表 相关应用 逻辑表达式、布尔检索、逻辑难题、位运算

1.1.2 命题(proposition) 定义1：一个命题就是一条陈述句 定义2：命题的真假叫做命题的真值 陈述的事情能够判别其真假 要么真、要么假，不能即真又假 定义2：命题的真假叫做命题的真值 只有两种真值：真、假 True、False；1、0 ；T、F

1.1.2 命题 一个命题就是一条陈述句 非陈述句不是命题 陈述的事情能够判别其真假 感叹句、祈使句、疑问句 为什么？ 无法判断真假 P1 例1 1、2、4 非陈述句不是命题 感叹句、祈使句、疑问句 P2 例2 1、2、“真好啊！” 为什么？ 无法判断真假

1.1.2 命题 一个命题就是一条陈述句 每条陈述句都是一个命题 正确吗？ P1 例1 3 是命题吗？能够判断其真假吗？ 1＋1＝2 为真，那么 1＋1＝10 为假吗？ 当明确了规则后，上述语句才是命题 注意：在判断命题(陈述句)真假时，需要其所在的场景(即上下文) 正确吗？ 二进制加法

1.1.2 命题 在判断命题(陈述句)真假时，需要明确其所在的场景(即上下文) P2 例3 “今天是星期五”是命题吗？ 今天是哪一天？语句的真假能被明确判断吗？ 当明确了时间后，上述语句才是命题

1.1.2 命题 在判断命题(陈述句)真假时，需要明确其所在的场景(即上下文) “这块黑板上没有写字”是命题吗？ 如果我站在隔壁教室说话呢？ 当明确了说话的地点后，上述语句才是命题

1.1.2 命题 在判断命题(陈述句)真假时，需要明确其所在的场景(即上下文) “这盘菜是咸的”是命题吗？ 如果说话的人是自贡人？ 当明确了说话的人后，上述语句才是命题

1.1.2 命题 在判断命题(陈述句)真假时，需要明确其所在的场景(即上下文) P2 例2 3、4 真的就不能是命题吗？ 当 x=1 时，x+1=2 是命题吗？ 当 x=y=2、z=3 时，x+y=z 是命题吗？ 如果变量被赋值后，上述语句可以是命题 预习：1.3 小节 谓词和量词

1.1.2 命题 一个命题就是一条(明确了其上下文的)陈述句 “飞碟来自外星球”是命题吗？ “哥德巴赫猜想是正确的”是命题吗？ ∴都是命题！ ∵虽真假未知，但真假可知 ∴都是命题！

1.1.2 命题 一个命题就是一条(明确了其上下文的)陈述句 “悖论”不是命题！ 剃头匠说：“我只给不自己剃须的人刮胡子” 这条已明确了上下文的陈述句是命题吗？ “悖论”不是命题！ 请问：他给自己刮胡子吗？ 悖论2：本语句为假 请判断这条陈述句的真假

1.1.2 命题 一个命题就是一条(明确了其上下文的)陈述句 要么真、要么假，不能即真又假 命题逻辑是一种“二值”逻辑 “我是高兴的”是真还是假？ 因为没有确定其真假的方法，所以无法判断 这样的陈述句不在本书范围内：“三值”逻辑 命题逻辑是一种“二值”逻辑

1.1.2 命题 一个命题就是一条(明确了其上下文的)陈述句：要么真、要么假，不能即真又假 “雪花是形状规则、重量小、无色、无味、冰凉、冬天才有的水合物”是命题吗？ 是真还是假？ 你需要分几步，才能完成对其真假的判断

1.1.2 命题 你能一次就能完成对其真假的判断吗？ 原子命题：其真假独立于其它命题 “雪花是形状规则、重量小、无色、无味、冰凉、冬天才有的水合物” “雪花是水合物”：可以独立的一次完成 原子命题：其真假独立于其它命题 命题的基本单位 复合命题

练习1 以下哪些陈述句是命题？其真值是什么？ 能整除 7 的整数只有 1 和 7 本身 对于每个正整数 n，存在一个大于 n 的素数 是，T 宇宙中地球是惟一有生命的星球 是，T 是，T 是，未知

(原子)命题的符号化表示 概念形式化 (原子)命题变元：p，q，r，s，… 真值：真＝T，假＝F 为什么要符号化表示？ 缺点：抽象不具体 好处：？ 字少写得快？ 概念形式化

复合命题(compound proposition) 定义：已有命题用逻辑运算符组合成的新命题 “雪花是形状规则、重量小、无色、无味、冰凉、冬天才有的水合物”就是一个复合命题 “雪花是形状规则的”：p “雪花是重量小的”：q “雪花是无色的”：r “雪花是无味的”：s “雪花是冰凉的”：t “雪花是冬天才有的”：u “雪花是水合物”：v 复合命题的符号化表示：p∧q∧r∧s∧t∧u∧v 逻辑运算符

逻辑运算符 组合命题的符号：也叫联结词 否定、合取、析取、蕴涵、双蕴涵 表示原子命题之间的逻辑关系

否定命题(negation) 命题 p 的否定：p ：非运算符 否定命题的真值 当p为假时，p 为真

真值表(truth table) 枚举命题真值的所有取值情况 否定命题的真值表 p ┐p T F

合取命题(conjunction) p与q的合取：p∧q 当p与q同时为真时， p∧q为真，否则为假 p q p ∧ q T T T F F T F F T F

练习2 符号化以下命题 王华既用功又聪明 王华虽然用功，但是不聪明 王华不仅用功而且聪明 王华用功：p，王华聪明：q p∧q

练习3 符号化以下命题 王华与张兰都是好学生 王华是好学生，并且张兰是好学生 虽然1+1=3，但是一个世纪是一百年 既有2＋3＝5，又有天正在下雨 王华与张兰是同学

析取命题(disjunction) p与q的析取：p∨q 当p与q同时为假时，p∨q为假，否则为真 同或(inclusive or) p q T T T F F T F F T F 同或(inclusive or)

“或”的两种含义 异或(exclusive or)：记号⊕ 当p、q中恰有一个为真时，p⊕q为真 小元元只能拿一个苹果或一个梨 王小红生于1975年或1976年 p q p⊕q T T T F F T F F F T

1.1.3 蕴涵(implication) 蕴涵命题 p→q 当p为真q为假时，p→q为假 p：假设(premise)、前项(antecedent)、前提(hypothesis) q：结论(conclusion)、推论(consequence) 也称为条件语句(conditional statement)

1.1.3 蕴涵(implication) 蕴涵命题 p→q 当 p 为真 q 为假时，p→q 为假 p q p →q T F

1.1.3 蕴涵(implication) p→q 的自然语句描述 如果 p，那么 q vs. q 如果 p

1.1.3 蕴涵(implication)的特殊性 当 p 为假时，pq 为真？？？ 当前提为假时，任意结论都可能 如果太阳从西方出，雪就是黑的 如果太阳从西方出，我就不姓黄 如果地球会飞，则地球有翅膀 前提虽然为假，但可能正确推导出结论

1.1.3 蕴涵(implication)的特殊性 当 p 为假时，pq 为真？？？ 当前提为假时，任意结论都可能 前提虽然为假，却可能正确推导出结论 0=1  3=9 0=1  4=4 ① 0=1 ② 4=5 ①＋4 ③ 0=-1 ②×-1 ④ 4=4 ②＋③ ① 0=1 ② 1=2 ①＋1 ③ 3=6 ②×3 ④ 0=3 ①×3 ⑤ 3=9 ③＋④

1.1.3 蕴涵(implication)的特殊性 pq (实质蕴涵) 可以不是因果关系 可以不是条件与结论 如果天下雨，那么 2+3 = 5 可以不是条件与结论 如果我去商店，就给你买苹果 若我没去商店，但仍然可以买苹果

1.1.3 蕴涵(implication)的特殊性 实际逻辑 vs. 命题逻辑 实际含义 vs. 形式语义 形式逻辑：抽象化实际逻辑 “重结构、轻内容” 只处理真假关系，可以不关心内容、意义 形式化符号串形式化处理

1.1.3 蕴涵(implication)的特殊性 蕴涵与 if 语句之间有所不同 if ( p ) s; if (2+3==5) x=x+1; 程序设计语言中的 if 语句是动作控制结构 条件和动作之间有因果关系 命题逻辑中的蕴涵是逻辑关系结构 前提和结论之间不一定非要有因果关系

1.1.3 蕴涵(implication) p→q 的形式意义 其中的符号 p, q 可表示任何命题 其中的蕴涵 →可表示现实不存在的关系 命题变量 / 命题变元 其中的蕴涵 →可表示现实不存在的关系 实质蕴涵

蕴涵的逆、反、倒置 练习：P12 12 原命题：pq 逆(converse)：qp (换位) 反(inverse)： p  q (取反) 倒置(contrapositve)： q  p (换位、取反) 也称为逆反命题 注意：pq 与  q  p 真值相同(等价) 练习：P12 12

蕴涵的逆、反、倒置 原命题 逆命题 反命题 逆反命题 换位 取反

1.1.3 蕴涵(implication) 练习 p q p∨q

1.1.3 蕴涵(implication) 练习 p q T F p∨q

双蕴含(biconditional) 双蕴含命题 pq 当pq、qp同真时，pq为真 p q p ↔ q T T T F F T

双蕴含(biconditional) iff p  q的逻辑关系：p、q之间互为充要条件 示例 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6 2 + 2 ＝ 4 当且仅当 3 是偶数 2 + 2 ＝ 4 当且仅当 太阳从东方升起 2 + 2 ＝ 4 当且仅当 美国位于非洲 函数f (x)在x0可导的 充要条件 是它在x0连续 iff

1.1.5 逻辑运算符的优先级 优先级相同时左结合(约定) 高 ( )  ∧ ∨ → 低 

1.1.6 翻译语句 将陈述句翻译为逻辑表达式的目的 消除歧义 确定真值 逻辑推理

1.1.6 翻译语句 将陈述句翻译为逻辑表达式的步骤 分解成分 逐一表示 确定算符 将陈述句翻译为逻辑表达式的方法 语法、语义分析 例12

1.1.6 翻译语句 例13 分解成分，逐一表示 确定算符 描述的是什么逻辑关系？ q：你能乘公园滑行铁道游乐车 r：你身高不足 4 英尺 s：你已满 16 周岁 确定算符 除非 A，否则 B 描述的是什么逻辑关系？

1.1.6 翻译语句 例13 除非 s，否则 rq q：你能乘公园滑行铁道游乐车 s：你已满 16 周岁，r：你身高不足 4 英尺 与 (rs)q 等价

练习 可符号化为：┐(P∧Q)→R 设命题 P：明天上午七点下雨； Q：明天上午七点下雪； R：我将去学校。 符号化下述语句： 如果明天上午七点不是雨夹雪，则我将去学校 如果明天上午七点不下雨并且不下雪，则我将去学校 如果明天上午七点下雨或下雪，则我将不去学校 明天上午我将雨雪无阻一定去学校 可符号化为：R (P∧Q∧R)∨(┐P∧Q∧R)∨ (P∧┐Q∧R)∨(┐P∧┐Q∧R) 或 ((P∧Q)∨(┐P∧Q)∨(P∧┐Q) ∨(┐P∧┐Q))∧R 可符号化为：┐(P∧Q)→R 可符号化为:(┐P∧┐Q)→R 可符号化为:(P∨Q)→┐R

1.1.7 系统规范(system specfication) 判断一致性 每条规范说明，就是一个命题 规范集合是一致的 全部规范都能够得到满足 全部对应命题真值都为真 例14

1.1.7 系统规范(system specfication) 每条规范是一个命题，所有规范应一致 存在一组命题的赋值，使得全部命题都为真 例15 p q p∨q ┐p p→q 1 1 1 0 0 1 0 0 1 例16 全 1 行

1.1.8 布尔搜索(boolean search) 搜索引擎：Google、Baidu 可视化逻辑运算符 布尔搜索表达式 北京 AND 四合居 AND 照片 OR 视频 北京 AND 四合居 AND (照片 OR 视频)

1.1.9 逻辑难题(puzzle) 示例 P9 例18, 例19 思考 P13 33

1.1.10 逻辑运算和位运算 二进制位：0/1真/假 布尔变量 位(bit)表示

1.1.10 逻辑运算和位运算 C语言的位运算(bit operation) 与：&、或：|、非：^、异或：- 位串运算 逐位进行

1.1.10 逻辑运算和位运算 练习：P12 19 !p p && q p || q ( p || q ) && ( !p || !q ) 逻辑运算符 符号 C 语言中的逻辑表达式 Negation(否定) p Conjunction(合取) pq Disjunction(析取) pq Exclusive or(异或) pq Conditional(蕴涵) pq Biconditional(等值) pq !p p && q p || q ( p || q ) && ( !p || !q ) if (p) q; ( p && q ) || ( !p && !q)

小结 进展 不足 原子命题：表示陈述句中的最小成分 运算符：表示命题之间的逻辑关系 命题＋运算符：可以表示任意的陈述句 命题＋运算符＋优先级：能确定任意陈述句的真假 不足 无法确定两个命题之间是否存在联系 无法从陈述的已有事实推出合理的未知结论