离散数学discrete2C

7 命题逻辑的推理理论 命题逻辑的推理理论就是利用命题逻辑公式研究什么是有效的推理 推理是从前提出发推出结论的思维过程 前提是已知的命题公式 结论是从前提出发 应用推理规则推出的命题公式 如果前提是真命题 从前提出发推出结论的推理过程严格遵守推理规则 则推出的结 论也是真命题 在命题逻辑中 不注重前提和结论的真假性 而关心从前提推出结论的推理过程的正 确性 即主要研究推理的规则 定义 1 35 称蕴涵式 A1 A2 Ak B 为推理的形式结构 A1 A2 Ak为推理的 前提 B 为推理的结论 若 A1 A2 Ak B 为永真式 则称从前提 A1 A2 Ak推出结 论 B 的推理正确 或说有效 B 是 A1 A2 Ak的逻辑结论或称有效结论 否则称推理 不正确 若从前提 A1 A2 Ak推出结论 B 的推理正确 则记为 A1 A2 Ak B 直观地看 A1 A2 Ak B 就是说 如果 A1 A2 Ak都正确 则 B 也正确 判断推理是否正确就是验证相应的蕴涵式是否是永真式 其方法包括 使用真值表 等值演算法 求主析取范式法 例子 1 12 教材 p39 例 1 23 要点 将各种命题符号化 然后使用上述各种方法判 断相应的蕴涵式是否是永真式 定义 1 36 证明是一个描述推理过程的命题公式序列 A1 A2 An 其中的每个命 题公式或者是已知的前提 或者是由某些前提应用推理规则得到的结论 满足这样条件的 公式序列 A1 A2 An称为结论 An的证明 在证明中常用的推理规则有 3 条 1 前提引入规则 在证明的任何步骤都可以引入已知的前提 2 结论引入规则 在证明的任何步骤都可以引入这次已经得到的结论作为后续证明 的前提 3 置换规则 在证明的任何步骤上 命题公式中的任何子公式都可用与之等值的公 式置换 得到证明的公式序列的另一公式 使用命题逻辑公式进行推理还有其他一些推理规则 这些规则建立在下面一些推理定 律上 定理 1 37 推理定律是命题逻辑的一些永真蕴涵式 重要的推理定律有 1 附加律 A A B 或称为析取的引入 2 化简律 A B A A B B 或称为合取的消除 3 假言推理 A B A B 或称为分离规则 4 拒取式 A B B A 5 析取三段论 A B B A 6 假言三段论 A B B C A C 或称为传递规则 7 等价三段论 A B B C A C 8 构造性二难 A B C D A C B D 注解 1 这些推理定律都是永真式 可用判断命题公式是否是永真式的方法加以证明 2 这些推理定律之间不是独立的 其中一些定律可从另外一些定律推出 正如我们 在命题演算系统中所讨论的 最基本的定律应该命题演算的公理及分离规则 对于上面给 出的这些定律 最重要的是附加律 分离规则 传递规则 拒取式等 正如教材 p44 的例 1 24 所证明的 构造性二难规则可使用传递规则 置换规则等证明 而拒取式与析取三段 论实际上等价 因为 A B A B 那么根据拒取式有 A B B A 而 A A 3 实际上这些推理定律中的符号 A B C 可代表任意公式 即将推理定律中某个符 号的所有出现用另外一个命题公式代入 那么得到的也是永真式 这个规则可称为代入规 则 注意代入规则与置换规则不同 定理 1 38 根据定理 1 37 的推理定律得到 在证明中可使用以下一些推理规则 1 假言推理规则 分离规则 若有 A B 和 A 则可得到 B 注意证明是命题公 式的序列 因此这里的意思是 如果序列中出现 A B 和 A 则可在该序列中添加公式 B 或换句话 按照证明的意思就是 如果有前提 A B 和 A 则可得到结论 B 2 附加规则 若有 A 则可得到 A B 3 化简规则 若有 A B 则可得到 A 也可得到 B 4 拒取式规则 若有 A B 和 B 则可得到 A 5 假言三段论 传递规则 若有 A B 及 B C 则可得到 A C 6 析取三段论规则 若有 A B 和 B 则可得到 A 7 构造性二难规则 若有 A B C D 和 A C 则可得到 B D 8 合取引入规则 若有 A 和 B 则可得到 A B 注解 1 假言推理规则就是最常用的推理方法 例如 如果天下雨 A 地就是湿的 B 现在天下雨 所以地是湿的 2 附加规则 化简规则及合取引入规则的直观含义很简单 3 拒取式规则就是通常所使用的反证法 即从 A 可推出 B 但如果我们已经有了 B 的否定 B 作为前提 那么我们就有理由相信 A 是成立的 例如 如果天下雨地就是湿 的 A B 但现在地没有湿 B 所以天没有下雨 A 4 假言三段论表明推理的传递性 也是常用的一种三段论 亚里斯多德的 工具论 中共总结出 24 中三段论的形式 例如 如果天下雨 A 路就会很难走 B 路很难走 我上学就会迟到 C 所以如果天下雨我上学就会迟到 5 析取三段论本质上与拒取式一致 但在逻辑上通常称为选言推理 或者更通俗地 称为排除法 例如 今天我要么去开会 A 要么去上课 B 我不去上课 B 所以我去开 会 A 实际上这里假定前提 A B 已罗列了所有可能情况 因为这只是一种推理模式 因 此这种假定是合理的 具有一般性 6 构造性二难推理是析取三段论的推广 例如如果派小王参加比赛 A 我们就可得到 第一名 B 如果派小张参加比赛 C 就可得到第三名 D 我们要么派小王去比赛 要么派 小张去比赛 所以我们不是得到第一名就是得到第三名 一种极端的二难推理形式是 有 A B 和 A B 那么就可得到 B 因为 A A 是永真的 例子 1 13 教材 p44 例 1 24 该例子的前提和结论都是符号化的命题公式 如何从 前提构造地证明结论没有固定的程式 这里也很难从结论到推到前提 需要敏锐的直觉和 丰富的经验 例子 1 14 教材 p45 例 1 25 该例子需要先将命题符号化 教材 p46 的附加前提证明法相当于下面的演绎定理 定理 1 39 演绎定理 A1 A2 Ak A B 当且仅当 A1 A2 Ak A B 利用演绎定理 许多命题公式 特别是蕴涵式的证明可得到简化 我们可将蕴涵式的 前件作为前提引入来进行证明 例子 1 15 教材 p46 例 1 26 该例子需要先将命题符号化 要证明的结论是一个蕴 涵式 可将蕴涵式的前件作为已知的前提来构造蕴涵式的后件的证明 例子 1 16 验证下述推理是否正确 或者逻辑学难学 或者有少数学生不喜欢它 如果数学容易学 那么逻辑学并不难学 因此如果许多学生喜欢逻辑 那么数学并不难学 解答 先将命题符号化 首先抽取的基本命题包括 A 逻辑学难学B 有少数学生不喜欢逻辑学C 数学容易学 则前提是 A B C A 要证明的结论是 B C 可进行如下的验证 1 B 按照演绎定理 引入结论的前件 B 作为前提 2 A B 已知的前提 3 A 1 和 2 及析取三段论 4 C A 已知的前提 5 C 3 和 4 及拒取式 得到结论的后件 因此从前提可有效地推出结论 因此整个推理正确 归谬法是反证法的推广 特别适合结论是否定式的时候 它基于下述定理 定理 1 40 A1 A2 Ak B 当且仅当 A1 A2 Ak B 是永真式 或者说 A1 A2 Ak B 当且仅当 A1 A2 Ak B 是矛盾式 例子 1 17 教材 p48 的例 1 27 最后给出一些综合的例子 例子 1 18 教材 p57 的例 1 35 例子 1 19 构造下列推理的证明 前提 A B B C A D D 结论 C A B 解答 根据合取引入规则 因为已经有前提 A B 所以只要推出结论 C 即可 1 A D 已知的前提 2 D 已知的前提 3 A 拒取式 4 A B 已知的前提 5 B 析取三段论 6 B C 已知的前提 7 C 分离规则 作业 教材 p63 64 的 23 24 25 二 一阶逻辑 First order Logic 1 概述 一阶逻辑讨论的内容与命题逻辑类似 一阶逻辑又称为谓词逻辑 Predicate Logic 为什么要引入一阶逻辑 因为简单命题需要进一步分析 才能更好地反映现实世界 中人们所使用的推理模式 一阶逻辑的基本概念 个体 函数 谓词 量词 在一阶逻辑中符号化命题 一阶逻辑公式及其解释 赋值 一阶逻辑公式的等值演算与范式 一阶逻辑公式的推理理论 使用一阶逻辑公式进行推理 2 一阶逻辑的基本概念 命题逻辑中 命题是最基本的单位 不再分解 不再考虑命题内部各成份之间的关系 这样忽略了命题本身的丰富内含 使得有些直觉上很正确的推理在命题逻辑中无法描述 定义 2 1 一阶逻辑中 命题被分解为个体和谓词两部分 个体 individuals 是指可 独立存在的客体 可以是一个具体的事物 也可以是一个抽象的概念 而谓词 predication 是用来刻划个体词的性质及事物关系的词 注解 1 一阶逻辑建立在命题逻辑之上 当命题逻辑中的命题具有丰富的内含时 需要一 阶逻辑公式来符号化它 2 命题是陈述句 在自然语言中 通常陈述句有主语 谓语和宾语 主语和宾语都 可能是个体 而谓语及其相连的宾语通常被看成是谓词 参考书中的例子 3 在一阶逻辑中还可描述对个体所进行的某种变换 即引入所谓函词 例如命题 的平方是非负数 其中 是一个体 的平方也是一个体 它通过对 做某种操作 变换 而得到 为了刻划 这种变换 引入所谓函词的概念 4 函词与谓词不同 函词作用在个体上 而产生另一个个体 而谓词作用在个体上 之后产生的是一个命题 例如上面命题中 的平方 是函词 而 是非负数 则是一 个谓词 的平方 是一个体 而 的平方是非负数 则是一个命题 5 所谓的个体常项是表示具体或特定的个体的个体词 而个体变项是表示抽象或泛 指的个体词 个体变项的取值范围称为个体域 后面看到当个体域不同时 一阶逻辑公式 的含义不同 为了使公式有一致的含义 可引入一个全总域 表示宇宙间所有个体所组成 的域 在某些情况下 全总域也可指所讨论的问题范围内的所有个体 6 表示具体性质或关系的词称为谓词常项 表示抽象性质或关系的词称为谓词变项 7 在一阶逻辑中 谓词变项和谓词常项的区别并不重要 正如在命题逻辑中 命题 常项和命题变项的区别不重要一样 这是因为在一阶逻辑中不能对谓词做某些变换 操作 或者说在一阶逻辑上不能在谓词集合上定义函数 但在个体域上可定义函数 因此个体常 项与个体变项的区别显得比较重要 8 实际上 所谓一阶逻辑的 一阶 的含义就是指其中的函数只能作用在个体上 或者说其中的变量只能代表取值于个体 如果允许函数作用在谓词上 则变成二阶或高阶 进一步允许函数作用在函数本身上 逻辑 9 可以说 一阶逻辑一个很重要的特点是在个体域上引入了变量 个体变量既可作 为谓词作用的对象也可作为函数作用的对象 一阶逻辑中的阶的含义在某种意义上是指个 体处于 0 阶 而对个体的判断 即命题 处于一阶 一阶逻辑中的函数作用于 0 阶的个体 而得到个体 而谓词作用于个体得到处于一阶的命题 10 谓词可包含的个体变项个数称为谓词的元数 例如 是非负数 是一元谓词 而 和 是好朋友 是二元谓词 通常来说 二元以上的谓词比较少见 而且通常可用 二元谓词来表示 例子 2 1 分析命题中的个体和谓词 并将命题在一阶逻辑中符号化 教材例 2 1 定义 2 2 在一阶逻辑中用量词 quantifier 来刻划参与判断的个体的数量 对于谓词 所作用的个体数量 一阶逻辑只关心两种情况 一种情况是谓词作用个体域中所有的个体 这时用全称量词 universal quantifier 使用符号 来刻划 一种情况是谓词作用个体域中某 些个体 这时用存在量词 existential quantifier 使用符号 来刻划 注解 1 一阶逻辑中 不关心个体的具体数量 而只关心谓词是作用于个体域中的所有个 体 还是某些个体 显然如果谓词不作用于个体域中任何个体 则可用存在量词再加上否 定来表示 2 在一阶逻辑中量词只限制被谓词所作用的个体的数量 它不限制被函数作用的个 体数量 实际上函数总是存在自己的定义域和值域 它可作用域在定义域中的任意个体 3 量词与个体域总是联系在一起的 因此使用不同的个体域 同一命题可能在一阶 逻辑中有不同的符号化形式 但总可使所有的个体变量的个体域为全总域 并通过引入合 适的特性谓词来从全总域中分离出可使用量词限制的合适个体域来 教材 p70 页的例子 注意所谓全总域 有时可认为讨论范围内的所有个体所组成的集合 4 量词是有顺序的 不能将量词的顺序随意颠倒 教材 p71 页的说明 实际上 谓 词中的个体变项也是有顺序的 例如 比 跑得快 表示为 F x y 即 x 比 y 跑得快 显然 x 和 y 不能随意颠倒 例子 2 2 在一阶逻辑中将命题符号化 教材例 2 2 例 2 3 例 2 4 例 2 5 例子 2 3 将下列命题符号化 1 凡是有理数都可写成分数 2 教室里有同学在讲话 3 对于任意的 x y 都存在唯一的 z 使得 x y z 4 在我们班中 并非所有同学都能取得优秀成绩 5 有一个整数大于其他每个整数 6 任给 0 存在 0 如果 x a 则 f x b y 6 符号化为 0 0 x a f x b 例子 2 4 将下列命题符号化 1 每一个有理数都是实数 2 某些实数是有理数 3 不是没一个实数都是有理数 4 存在偶素数 5 会叫的狗未必会咬人 6 每个人的外祖母都是他母亲的母亲 7 任何自然数的后继数必大于零 8 有些液体能溶解任何金属 9 任何金属均可溶解于某种液体中 10 没有不犯错误的人 11 小莉是非常聪明和美丽的 12 小李是一个田径运动员 解答 请同学们下载后 先思考 课堂上讲解 例子 2 5 将下列公式翻译成自然语言 并确定其真值 这里假定个体域是正整数 1 x y G x y 其中 G x y 表示 x y y 2 x y F x y 其中 F x y 表示 x y y 3 x y H x y 其中 H x y 表示 x y x 4 x y L x y 其中 L x y 表示 x y x 5 x y M x y 其中 M x y 表示 x y 1 6 x y N x y 其中 N x y 表示 y 2 x 解答 请同学们下载后 先思考 课堂上讲解 例子 2 6 给定下述谓词 请把下列公式翻译成自然语言 P x x 是素数E x x 是偶数 Q x x 是奇数N x y x 可以整除 y 1 P 5 2 E 2 P 2 3 x N 2 x E x 4 x E x N x 6 5 x E x N 2 x 6 x E x y N x y E y 7 x P x y Q y N y x 8 x Q x y E y N y x 解答 请同学们下载后 先思考 课堂上讲解 作业 教材 p101 102 的 1 2 3 一阶逻辑公式及解释 每个系统有它自己的符号表 由这些符号表所构成的某些符号串是该系统中的语言 也是我们所研究的目标语言 定义 2 3 一阶逻辑语言的符号包括 1 个体常项 通常用排在前面的小写字母表示 a b c ai bi ci 2 个体变项 通常用排在后面的小写字母表示 x y z xi yi zi 3 函数符号 通常用排在中间的小写字母表示 f g h fi gi hi 4 谓词符号 通常用排在中间的大写字母表示 F G H Fi Gi Hi 5 量词符号 全称量词 存在量词 6 联结符号 7 辅助符号 逗号 注解 1 上述符号可分为两大类 一类是非逻辑符号 包括个体常项 函数符号 谓词符 号等 一类是逻辑符号 包括个体变项 量词符号 联结符号 辅助符号等 2 在命题逻辑只有逻辑符号 而没有任何非逻辑符号 命题逻辑中的命题常项和命 题变量的区分是非本质的 对于命题逻辑本身来说没有什么意义 正如在一阶逻辑中 谓 词常项和谓词变项的区分也是非本质的 对于一阶逻辑来说没有什么意义 但个体常项和 个体变项的区分是本质的 对于一阶逻辑来说有重要的意义 3 一阶逻辑中的逻辑符号对于将一阶逻辑应用于任何问题时都是通用的 不变的 而其中的非逻辑符号则在不同的应用问题 或者说不同的讨论范围 中有所不同 可以变 化 因此一阶逻辑语言的表达能力是非常强的 它可通过采用不同的非逻辑符号来增强自 己的表达能力 定义 2 4 一阶逻辑语言的项 term 递归定义为 1 个体常项和个体变项是项 2 若 f x1 x2 xn 是 n 元函数 t1 t2 tn是 n 个项 则 f t1 t2 tn 是项 3 一阶逻辑语言的所有项都通过有限次使用上述两步生成 定义 2 5 一阶逻辑语言的合式公式 well formed formula 递归定义为 1 若 F x1 x2 xn 是 n 元谓词 t1 t2 tn是 n 个项 则 F x1 x2 xn 是合式公式 此类合式公式称为原子公式 2 若 A B 是合式公式 则 A A B A B A B A B 也是合式公式 3 若 A 是合式公式 则 x A x A 也是合式公式 4 一阶逻辑语言的所有都通过有限次使用上述步骤生成 通常用 r s t ri si ti 等表示项 而用 A B C Ai Bi Ci 表示合式公式 注解 1 一阶逻辑语言的合式公式随着采用不同的非逻辑符号而不同 但对于不同的非逻 辑符号采用相同的方式构造公式 一旦非逻辑符号确定之后 则一阶逻辑公式也就确定下 来了 所以可以说一阶逻辑公式是某个非逻辑符号集生成的语言 2 虽然说采用不同的非逻辑符号可生成不同的一阶逻辑公式 但所有一阶逻辑公式 的逻辑符号是相同的 而我们在这里对一阶逻辑的讨论只是讨论这些逻辑符号的性质 而 与非逻辑符号无关 则我们的讨论对于任意的非逻辑符号生成的一阶逻辑公式都是成立的 3 一阶逻辑语言的直观意义容易理解 符号表 相当与英语的字母表 项 相当 于单词或词组 它们不表达完整的判断 还只是代表个体 而 公式 则代表完整的句子 而其中的函数符号用来构造复杂的个体 项 谓词符号则用来构造最原子的公式 4 在定义 2 5 的 4 中 没有要求个体变项 x 一定要出现在合式公式 A 中 因此下述 符号串都是合式公式 x F x y z F x y 5 可通过假设联结符号及量词之间的优先级而去掉一些括号 使得公式的书写更为 简洁 约定 1 公式的最外层括号可省略 2 联结词 的优先级高于 而 高于 高于 高于 所以公式 F x y Q y z F y z G y x Q x z F y z 表示 F x y Q y z F y z G y x Q x z F y z 但通常在书写 时也不可将所有的括号省略 应该既比较简洁 又比较容易理解 例如上述公式可写成 F x y Q y z F y z G y x Q x z F y z 由于一阶逻辑语言的公式比较复杂 其中的括号比较多 请注意讲究书写的方法 3 A1 A2 An 1 An表示 A1 A2 An 1 An 4 量词的优先级高于任何联结符号 所以 x A x A 可分别写成 xA xA 但要注意明确量词的辖域 下面定义什么是辖域 定义 2 6 称公式 x A 中的 A 为量词 x 的辖域 scope 称公式 x A 中的 A 为量 词 x 的辖域 称变元 x 在公式 A 中的某处出现是约束出现 如果该出现处于量词 x 或 x 的辖域内 或者就是量词中的 x 若 x 在公式 A 中的某处出现不是约束出现 则此出现 称为自由出现 例子 2 7 教材 p76 的例 2 6 指出下列公式中 各量词的辖域以及变元的自由出 现和约束出现 1 x F x y z yG x y 2 xF x y G x y 3 x y F x G y H x y 解答 1 量词 x 的辖域为 F x y z yG x y 而量词 y 的辖域为 G x y 变元的自 由出现和约束出现分别为 x F x y z y G x y 约束 约束 自由 自由 约束 约束 约束 2 量词 x 的辖域为 F x y 变元的自由出现和约束出现分别为 x F x y G x y 约束 约束 自由 自由 自由 3 量词 x 的辖域为 y F x G y H x y 量词 y 的辖域为 F x G y H x y 变元的自由出现和约束出现分别为 x y F x G y H x y 约束 约束 约束 约束 约束 约束 定义 2 7 设变元 x 在公式 A 中出现 如果 x 在 A 中的所有出现都是约束出现 则 称 x 为 A 的约束变元 bounded variable 否则称 x 为 A 的自由变元 free variable 注解 1 变元 x 在公式 A 中可同时有约束出现和自由出现两种情况 而只有当 x 的所有出 现都是约束出现时 称 x 为 A 的约束变元 2 为了明确起见 我们通常在用字母 A B C 表示一阶逻辑公式时 同时列出该 公式中的自由变元 而写成 A x1 x2 xn 等 表示公式 A 中的所有自由变元皆在 x1 x2 xn中 3 为了清晰起见 通常运用换名规则和替换规则使得公式 A 满足下列条件 1 所有变元在公式 A 中要么自由出现 要么约束出现 不要既有自由出现 又有约 束出现 2 所有量词后面采用的约束变元互不相同 量词后面的约束变元只在它的辖域里有 意义 处于其辖域以外的同名变元与该约束变元实际上无关 所以不同量词采用不同约束 变元是可以的 而且也是必要的 进一步变元的辖域实际上是可嵌套的 例如对于公式 x F x x G x F x 其中量词 x 的辖域为 F x x G x F x 而量词 x 的辖域为 G x F x 实际上在 子公式 G x F x 中的 x 被量词 x 约束 而不是被量词 x 约束 实际上 上述公式等价于 x F x y G y F y 在使用一阶逻辑公式符号化命题时 要小心地选择变元