上海交大-离散数学之数理逻辑（1）.pptVIP

离散数学之数理逻辑（1） 上海交通大学软件学院 吴刚 2009年春 内容 什么是数理逻辑 命题逻辑 命题与命题联结词 命题变元与命题公式 重言式 什么是数理逻辑 用数学方法研究形式逻辑中推理（演绎）规律的一门学科 逻辑研究思维的内涵和外在表现，形式逻辑研究其外在表现的规律，形式逻辑的研究可以用演绎的方法和归纳的方法 数理逻辑包括证明论、模型论、递归论、公理集合论等四个分支 什么是数理逻辑 共性的东西是如何推理，如何演绎 公理化与形式化方法 特制的符号语言体系（数理逻辑通常也叫符号逻辑） 只有这样才能用数学的方法来研究形式逻辑的演绎 与计算机科学的关系 布尔电路：香农的硕士论文 计算理论：可计算性、Turing机、形式语言、自动机、计算复杂性 程序语义的验证 程序的自动生成与转换 SQL：等价于一阶逻辑 Prolog以逻辑演算为基础、LISP以λ演算为基础 …… Dijkstra的话 我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了，我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多错误，不少东西逻辑学家早就说了，可我不知道。要是我能年轻20岁的话我要回去学逻辑。 命题逻辑 数理逻辑中最简单、最基础的部分 以命题为对象，研究基于命题的符号逻辑体系及推理规律 什么是命题？ 能分辨真假的陈述句 不能分解成多个命题的命题，称为原子命题 命题的例子 命题 23 23 今天我们要点名 非命题 上课别说话（祈使句） 多好的学生啊！（感叹句） 你吃早饭了吗？（疑问句） 我这句话是假话（悖论） XY（无法确定真假） 命题的表示 一般用P、Q、R…表示命题 命题的真值用T和F表示，T表示命题为真，F表示命题为假 T、F也表示命题常量，T是永真命题、F为永假命题 复杂的命题怎么表达？ 原子命题： 期中考试张三考及格了 期中考试张三考了90分 复杂命题： 期中考试张三没有考及格. 期中考试张三和李四都考及格了. 期中考试张三和李四中有人考90分. 如果张三考了90分, 那么李四也考了90分. 张三考了90分当且仅当李四也考了90分. 命题联结词与复合命题 联结词 否定、合取、析取、蕴含、等价 ?、 ∧、 ∨、 →、 ? 异或、与非、或非、蕴含否定 由原子命题经各种联结词运算后得到的命题叫做复合命题 命题联结词 否定联结词（?） 命题P的否定命题“非P”表示为?P 其真值表为 命题联结词 合取联结词（∧） 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 其真值表为 命题联结词 与一般习惯用语的差别 两个实际中没有逻辑关系的命题在命题逻辑运算中是可以通过联结词形成新的复合命题的 联结词与日常用语中逻辑含义有差别 我拿着钢笔或拿着铅笔（相容的或） 析取 我在开小差或认真听课（不相容的或） 异或 联结词是命题的联结，而不是名词或形容词的联结 张三和李四是室友 原子命题 张三和李四都在认真听课 可看作两命题的合取 命题变元与命题公式 以T和F为其值域的变元称为命题变元，也可简称为命题，用P、Q、R…表示 命题公式（公式）：由命题变元、联结词和圆括弧组成，定义如下 （1）原子命题P是公式； （2）如果P是公式，则(?P)是公式； （3）如果P、Q是公式，则(P∧Q),(P∨Q), (P→Q),(P?Q)是公式 有限次使用上述规则所生成的也是公式 命题公式 命题公式的BNF (Bacus Normal Form): α ::= P | (? α) | (α ∨ β) | (α ∧ β) |(α → β) | (α ? β) P代表原子命题，α,β是命题公式 命题公式 命题公式 (?P)、(P∧(?Q))、(P ∨(?P)) (P ?(?P))、(P ∧(?P)) ((P ∧ Q) →(?(P ∨R))) 非命题公式 PQ→、(P?Q)、 (P∧→Q) (P ?(?P) 命题公式 去除括号的约定 最外层括号可省去 基础的5个联结词按否定、合取、析取、蕴含、等价的前后顺序进行联结，否定最强，等价最弱，凡符合此顺序的，括号可去掉 相同的联结词按从左到右的顺序结合，凡符合此顺序的，括号可去掉 例子：((P∧Q) →(?(P∨R)))可化简为 P∧Q → ?(P∨R) 命题的公式化 铁和氧能化合,