1.命题逻辑.ppt

离散数学 兰州大学网络教育学院 什么是离散数学 离散数学是计算机专业的一门重要基础课 它所研究的对象是离散数量关系和离散结构数学结构模型 离散数学课程主要介绍离散数学的各个分支的基本概念 基本理论和基本方法 这些概念 理论以及方法大量地应用在数字电路 编译原理 数据结构 操作系统 数据库系统 算法的分析与设计 人工智能 计算机网络等专业课程中 课程概况 第一部分数理逻辑第一章命题演算及其形式系统第二章谓词演算及其形式系统第二部分集合论第三章集合第四章关系第五章函数第六章集合的基数 课程概况 第三部分图论第七章图的基本概念第八章一些特殊的图第九章树参考书目 离散数学 北京大学出版社耿素云 屈婉玲 方新贵编著 离散数学 离散数学学习指导 山东大学出版社杨杰于忠文编著 第一部分数理逻辑 数理逻辑是用数学上的形式化方法研究逻辑推理过程和规律的一种理论 它引入了一套形式化的符号体系 规定了一些规则 从而使推理在形式上像代数演算一样简单 因此数理逻辑又称为符号逻辑 数理逻辑和电子计算机的发展密切相关 在开关线路 机器证明 自动化系统 编译理论及算法设计等方面得到了广泛的应用 数理逻辑 第1章命题演算及其形式系统 1 1命题与联结词1 1 1命题定义在数理逻辑中 凡是能判断真假的陈述句称为命题 例 1 雪是白的 2 陈胜 吴广起义那天杭州下雨 3 x y 34 昨天下午我一边看书 一边听录音机 6 今天天气多好啊 7 星期二下午开会吗 命题 表示 命题通常用大写英文字母A B P Q 或小写英文字母p q r 或用带下标的英文字母表示 例如p 雪是黑的 命题具有一个 值 称为真值 如果一个命题是真的 则它的真值为真 用 T 或 1 来表示 如果一个命题是假的 则它的真值为假 用 F 或 0 来表示 表示命题的字母称为命题标识符 例如上述的p就是标识符 如果一个命题标识符表示确定的命题 则称为命题常量 如果命题标识符只用于标志命题的位置 则称为命题变元 因为命题变元可以表示任意命题没有确定的真假值 所以命题变元不是命题 命题分为两大类 由一个不能再分解的简单陈述句构成的简单命题 或叫原子命题 例如雪是黑的 由两个或两个以上的原子命题用逻辑联结词构成的复合命题 例如昨天下午我一边看书 一边听录音机 命题标识符命题的分类 1 1 2联结词 复合命题是由原子命题和联结词构成 因此 联结词是复合命题的重要组成部分 须对数理逻辑中使用的联结词作出严格定义并符号化 常用的联结词有5个 分别称为否定 合取 析取 蕴涵和等值 并分别用符号 表示 1 否定定义设p是命题 复合命题 非p 称为p的否定式 记作 读作 的否定 或 非 联结词否定 例 雪是白的 并非雪是白的 雪不是白的 我们都是好学生 并非我们都是好学生 我们不都是好学生 错误 我们都不是好学生 注意 对量化命题的否定 除了对动词进行否定外 同时对量化词也要加以否定 2 合取定义设 为两个命题 则复合命题 且 称作 与 的合取 记作 读作 与 的合取 与 且 等 合取 当且仅当 和 的真值均为 1 时 的真值为 1 否则 其真值为 0 相当于 并且 既 又 等 例 a P 王华的成绩很好Q 王华的品德很好则 王华的成绩很好并且品德很好 b P 我们去种树Q 房间里有一台电视机则 我们去种树与房间里有一台电视机 注意 在日常生活中 合取词应用在二个有关系的命题之间 而在逻辑学中 合取词可以用在二个毫不相干的命题之间 3 析取定义设 为二个命题 则复合命题 或 称作 与 的析取 记作 读作 或 当且仅当 均为 0时 为 0 否则 其真值为 1 相当于 或者 例 P 今晚我看书Q 今晚我去看电影则 今晚我看书或者去看电影 析取 注意 区分 可兼或 与 不可兼或 可兼或即 P和Q均为 1 时 P Q为 1 例 灯泡有故障或开关有故障 今天下雨或打雷 以上例句均为可兼或 不可兼或中两个析取命题事实上不可能同时为真 即 当P和Q均为 1 时 则P Q为 0 例 人固有一死 或重于泰山 或轻于鸿毛 他乘火车去北京或乘飞机去北京 以上两句均为 不可兼或 4 蕴涵 单条件 定义设 为二个命题 复合命题 如果 则 记作 称为条件命题 读作 如果 则 蕴含 是 的充分条件 当 为 1 为 0时 则 为 0 否则 均为 1 称为蕴涵前件 条件 称为蕴涵后件 结论 蕴涵 例 a P 天气好Q 我去接你P Q 如果天气好 那么我去接你 注意 当天气好时 我去接了你 这时诺言P Q真 我没有去接你 则诺言P Q假 当天气不好时 我不论接你与否均未食言 此时认为P Q均为真 b P 2 2 5Q 雪是黑的P Q 如果2 2 5 那么雪是黑的 注意 在讨论数学问题和逻辑问题时 b 是一个有意义的命题 且据定义其真值为真 通常称 a 为形式条件命题 前提和结果有某种形式和内容上的联系 b 为实质条件命题 前提和结果可以有联系 也可以没有联系 只要满足单条件命题的定义 5 双向蕴涵 双条件 定义设 为二个命题 则复合命题 当且仅当 记作 称为双条件命题 读作 当且仅当 等值于 是 的充分必要条件 双向蕴涵 当 和 的真值相同时 的真值为 1 否则 为 0 例 ABC是等腰三角形 ABC有两只角相等 ABC是等腰三角形当且仅当 ABC中有两只角相等 命题联结词小结 五个联结词的含义与日常生活中的联结词的含义大致相同 或 分为可兼或 和不可兼或 异或 除 为一元运算外 其余四个均为二元运算 分为形式条件和实质条件命题 当前件为 0 时 不论后件怎样 则单条件命题的真值均为 1 命题联结词是命题或命题之间的联结词 而不是名词之间 动词之间和数字之间的联结词 命题联结词小结 以上介绍了五种常用的联结词及其相应的复合命题形式 数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算 为此 首先要把推理所涉及到的各命题符号化 将命题符号化的步骤如下 1 找出各原子命题 分别符号化 2 找出各联结词 把原子命题逐个联结起来 命题符号化 例 将下列命题符号化 1 我和他既是兄弟又是同学 P 我和他是兄弟 Q 我和他是同学可表示为P Q 2 张三和李四是朋友 张三和李四是朋友是一个简单句 可表示为P 3 我和他之间至少有一个要去边疆 P 我去边疆 Q 他去边疆可表示为P Q 4 只有一个角是直角的三角形才是直角三角形 P 三角形的一个角是直角 Q 三角形是直角三角形可表示为 P Q 5 老王或小李中有一个去上海出差 P 老王去上海出差 Q 小李去上海出差可表示为P Q 或 P Q P Q 或 P Q P Q 6 如果他不来 那么他或者是生病了 或者是不在本地 P 他来 Q 他生病 R 他在本地可表示为 P Q R 7 风雨无阻 我去上学 P 天刮风 Q 天下雨 R 我去上学可表示为 P Q R P Q R P Q R P Q R 1 1 3命题公式及其真值表 命题公式 由命题变元 命题常元 联结词以及括号组成的符号串 定义命题公式可按下述法则来生成 1 命题常元和命题变元都是命题公式 也称为原子公式或原子 2 若 是命题公式 则 均为命题公式 3 当且仅当有限次使用 所生成的符号串才是命题公式 命题公式 命题符号化要注意以下几个方面 1 要善于确定原子命题 不要把一个概念硬拆成几个概念 2 要善于识别自然语言中的联结词 有时被省略 例如 风雨无阻 我去上学 可理解为 不论是否刮风 是否下雨 我都去上学 3 否定词的位置要放准确 4 需要的括号不能省略 5 命题的符号化形式未必是唯一的 例如 P Q P Q R P Q R P都是命题公式 而 P P 都不是命题公式为使公式的表示更加简练 我们作如下约定 1 公式最外层括号一律可省 2 联结词的结合优先次序为 表示 与 同级 3 同级联结词在没有括号表示起结合状况时 则按从左到右的次序运算 例如 P Q R Q S 所表示的公式是 P Q R Q S 设A是命题公式 A1是A的一部分 并且A1也是公式 则A1称为公式A的子公式 如对公式A P Q R Q S 则P P Q R Q S 及Q R Q S 都是A的子公式 而Q R 虽然是公式A的一部分 但不是公式 所以不是A的子公式 定义设p是一个命题公式 p1 pn是出现在p中的所有命题变元 对p1 pn指定一组真值称为对p的一个指派 若指定的一种指派使p的值为真 则称这组值为成真指派 若指定的一种指派使p的值为假 则称这组值为成假指派 含有n个命题变元的命题公式 共有2n组指派 子公式指派 真值表 将命题公式p在其所有指派下取得的值列成的表 称为p的真值表 构造真值表的步骤如下 1 找出给定命题公式中所有的命题变元 列出所有可能的赋值 2 按照从低到高的顺序写出命题公式的各层次 3 对应每个赋值 计算命题公式各层次的值 直到最后计算出整个命题公式的值 真值表 例 构造命题公式 的真值表 1 2重言式 1 2 1重言式概念定义如果一个命题公式在它的各种指派情况下 其取值均为真 则该公式称为重言式 或永真式 如果一个命题公式在它的各种指派情况下 其取值均为假 则该公式称为永假式 或矛盾式 既不是永真式 又不是永假式 则称此命题公式是可满足式 讨论 永真式的否定为永假式 永假式的否定为永真式 二个永真式的析取 合取 蕴含 等价均为永真式 重言式 1 2 2逻辑等价式和逻辑蕴涵式 定义如果对两个命题公式 和 不论作何指派 它们真值均相同 则称 是逻辑等价的或说 等价于 记作 说明 为等价关系符 表示 和 有等价关系 不是命题公式 为等价联结词 运算符 为命题公式 则 也为一命题公式 逻辑等价 定理 的充要条件是 为永真式 证明 充分性 为永真式 即 有相同的真值 所以 必要性 即 有相同的真值表 所以 为永真式 由定理可知 1 2 若 则 3 若 C 则 以下是一些重要的逻辑等价式 其中P Q R表示任意命题公式 1 双重否定律 2 幂等律 3 交换律 4 结合律 5 分配律 重要的逻辑等价式 6 德摩根律 7 吸收律 8 蕴含律 9 等价律 10 零律 11 同一律 12 互补律 13 输出律 14 归缪律 15 逆反律 定义当且仅当命题公式 是一个永真式时 称 蕴涵 记作 说明 读作 逻辑蕴含 永真蕴含 能推得 是关系符 不为命题公式 由定理可知 1 若 且 则 2 若 则 3 若A B A A B B 则A B 逻辑蕴涵 定理 的充分必要条件是 且 证明 若 则 为一永真式由等价律 且 也为一永真式即 且 成立反之 且 则 也成立此定理把 和 之间建立了相应的关系 以下是一些重要的逻辑蕴含式 1 2 3 4 5 6 7 8 9 P 10 11 12 13 重要的逻辑蕴涵式 定理设A为永真式 p为A中命题变元 A B p 表示将A中p的所有出现全部代换为公式B后所得的命题公式 称为A的一个代入实例 那么A B p 亦为永真式 该定理称为代入原理 RS 例 1 设 Q 若用 代换 中的 得 Q 是 的代换实例而 Q 不是B的代换实例 2 的代换实例有 等所以 一个命题公式的代换实例有无限个 代入原理 定理设A为一命题公式 C为A的子公式 且C D 若将A中子公式C的某些 未必全部 出现替换为D后得到公式B 那么A B 该定理称为替换原理 RR 证明逻辑等价式和逻辑蕴涵式的方法 真值表法 为证A B A B 可用真值表证明A B A B永真 对指派进行讨论 为证A B 只要证明任意使A为真的指派都能使B为真 或任意使B为假的指派都使A为假 为证A B 可用此法同时证明A B B A 利用已知永真式及代入 替换原理进行推演 替换原理证明等价式和蕴涵式的方法 例 证明 证明 1 真值表法由真值表知 为永真式 2 对指派进行讨论设a是使 为假的任一指派 即a 0 从而a P a Q 0 即任一使 为假的指派都能使P为假 原命题得证 3 利用永真式等推演 1 例 证明对任意命题公式A B C 有 A B C A C B C 证明 A B C 蕴涵律 A B C 德摩根律 A B C 分配律 A C B C 蕴涵律 A C B C 例 证明 为一永真式 证明 原式 它是 永真式 的代换实例 永真式的代换实例仍为永真式 1 2 3对偶原理 定义对于仅含有联结词 的命题公式A 若用 代换 代换 代换 代换 后得到公式A 则称A 是A的对偶 或A和A 是互为对偶的 例如A A 讨论定义 若命题公式中有联结词 则必须把其化成由联结词 组成的等价的命题公式 然后求它的对偶式 在写对偶式时 原命题公式中括号不能省去 必须按优先级的次序写上括号 并在求其对偶式时仍将保留括号 对偶原理 例如 对偶式写成 而不能写成 定理 德摩根推广定理 设A和A 为对偶式 P1 P2 Pn是出现在A和A 中的所有原子命题变元 于是有 P1 P2 Pn A P1 P2 Pn 1 P1 P2 Pn A P1 P2 Pn 2 证明 由德摩根定理 和 不难看出 一个命题公式的否定等价于它的对偶式 且把变元的否定代替每一个变元 德摩根推广定理 定理若二个命题公式互为等价 则它们的对偶式也互为等价 亦即若 则A B 成立 证明 已知 为任一命题公式 且 要证明A B 设 P1 P2 Pn是出现在 和 中的原子命题变元 由 即 P1 P2 Pn P1 P2 Pn P1 P2 Pn P1 P2 Pn 定理 由德摩根推广定理 P1 P2 Pn P1 P2 Pn P1 P2 Pn P1 P2 Pn 为永真式 永真式的代换实例仍为永真式 所以用 Pi代换A 和B 中的Pi 1 i n 则得 P1 P2 Pn P1 P2 Pn 即为 P1 P2 Pn P1 P2 Pn 结论 若一个命题公式等价于一个永真式 则该公式一定为永真式 若一个永真的命题公式永真蕴含一个命题公式 则此命题公式一定也为永真式 若一个永假的命题公式永真蕴含一个命题公式 则该公式可能是永真式 永假式或可满足的 结论 1 3范式 把命题公式化为一种标准的形式 称此标准形式为范式 1 3 1合取范式和析取范式定义一个命题公式称为合取范式 当且仅当它具有形式 A1 A2 An n 1 其中A1 A2 An都是由命题变元及其否定所组成的析取式 例如 P Q R R P 范式合取范式 定义一个命题公式称为析取范式 当且仅当它具有形式 A1 A2 An n 1 其中A1 A2 An都是由命题变元及其否定所组成的合取式 例如 P Q R R P 例 求 R P的合取范式和析取范式解 1 合取范式 R P R P 消去第一个 R P 消去第二个 R P 内移 析取范式 R P 内移 R P 消去 P R P 对 分配 R P 2 析取范式前几步同合取范式 在 1 中第6步用 对 分配即可得析取范式 原式 R P R R P 对 分配 P R 吸收律 任一命题可化为与其等价的合取范式或析取范式 步骤如下 1 消去公式中的联结词 和 化为 化为 2 利用德摩根定律将否定联结词 向内深入 使之只作用于命题变元 且 P P 3 利用分配律 将公式进一步化为所需要的范式 注意 一个公式的合取范式或析取范式都不是唯一的 另一方面 一个公式的合取范式或析取范式又可能是同一的 求合取范式与析取范式的步骤 1 3 2主析取范式和主合取范式 定义 个命题变元的合取式中 若每个变元及其否定并不同时存在 且二者之一只出现一次且仅出现一次 则称此合取式为极小项 例 对二个命题变元讲 极小项有22 4个 即 对三个命题变元讲 极小项有23 8个 即 推广到一般 个命题变元构成的不同极小项有2n个 使得每个极小项为真的赋值仅有一个 极小项 定义对给定的命题公式来讲 仅含有极小项的析取的等价式称为给定命题公式的主析取范式 定理在真值表中 一个公式的真值为 T 或1 的指派所对应的极小项的析取 即为此公式的主析取范式 说明 1 只要命题公式不是永假式 则一定可以根据该命题公式的真值表直接写出其主析取范式 其方法是找出该公式为 1 的行 对应写出极小项的析取式 且一定是唯一的 2 若命题公式是含有n个变元的永真式 则它的主析取范式一定含有2n个极小项 主析取范式 3 若二个命题公式对应的主析取范式相同 则此二个命题公式一定是等价的 4 命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为 1 的个数 例 求 的主析取范式 则可直接写出各命题公式的主析取范式 直接求命题公式主析取范式的方法 分四步 将命题公式化为与其等价的析取范式 除去永假项 合并合取式中相同项 例 变为最简析取范式 利用添变元的方法 将所有合取式变为极小项 合并相同的极小项变为一项 例 求 的主析取范式解 原式 1 化为析取范式 2 消去永假项 变为最简析取范式 求主析取范式的步骤 T 3 添项 4 合并相同最小项例 证明 证明方法是写出二个命题公式的主析取范式 看其是否相同 主析取范式相同 有 定义在 个变元的析取式中 若每个变元与其否定并不同时存在 且二者之一出现一次且仅出现一次 则称这种析取式为极大项 例 有二个变元 的极大项有22 4个 有 个变元 则有2n个极大项 极大项 定义在真值表中 一个公式的真值为F的指派所对应的极大项的合取 即为此公式的主合取范式 定理在真值表中真值为 或0 的个数等于主合取范式中极大项的个数 讨论 与命题公式等价的主合范式中极大项的个数等于其真值表中真值为 0 的个数 由真值表找极大项的方法 将表中值为 0 的对应真值指派中 把变元写成否定 把变元的否定写成变元 只要命题公式不是永真式 则一定可以写出对应与其等价的唯一的主合取范式 若命题公式为含有 个变元的永假式 则主合取范式包含了2n个极大项的合取式 主合取范式 可用主合取范式判定二个命题公式是否等价 已知一个命题公式的主析取范式 则一定可以直接写出与其等价的主合取范式来 反之也行 例 主析取范式 主合取范式 对应于有 个变元的命题公式 则一定有 主析范式极小项数 主合范式极大项数 2n例 求出 的主合取范式 直接写出其主合取范式 极大项 直接求命题公式主合取范式的方法 1 化为与命题公式等价的合取范式 2 除去真值为 1 的析取项和除去析取项中相同变元且只保留一个 变为最简合取式 3 添项 使析取项均变为极大项 例如 为二个变元 即 F 4 合并相同的极大项 保留一项 例 求 的主合取范式解 原式 蕴涵律 分配律 分配率 添项主范式排序 列 的唯一性 极小项及其编码对于有 个变元的命题公式 最多可有2n个极小项 用m0 m1 m2n 1来表示 例如 下面列出三个变元 且 的位置已排定 则 主范式排序的唯一性极小项及其编码 例 设一命题公式有五个变元 P0 P1 P2 P3 P4 次序已定 则必可写出25 32个极小项 下列出m 11 十和m 18 十的极小项表示 即 m 11 十 m 01011 二 P0 P1 P2 P3 P4 m 18 十 m 10010 二 P0 P1 P2 P3 P4 通过上例归纳出求极小项m i 十的方法 a 把 i 十变换成等价的 J0 J1 Jn 1 二 b 由二进制写出其对应的极小项 例 求 的编码表达式 设 次序已定 解 原式 m 001 二 m 011 二 m 111 二 m 110 二 m 1 十 m 3 十 m 7 十 m 6 十 m1 m3 m7 m6 1 3 6 7 极大项及其编码用M0 M1 M2n 1表示 个变元的命题公式的极大项 求极大项的方法 a 把 i 十变换成等价的 J0 J1 Jn 1 二 b 由二进制数写出其对应的极大项 极大项及其编码 例 求 的极大项编码表示 设 次序已定 解 原式 M 000 二 M 010 二 M 100 二 101 二 M 0 十 M 2 十 M 4 十 M 5 十 M0 M2 M4 M5 0 2 4 5极大项和极小项编码约定刚好相反 从上例中 1 3 6 7 0 2 4 5 1 3 3联结词的扩充与归约其它命题联结词 1 不可兼或 异或 a 定义 见真值表 b 符号 记作 读作 异或 其它命题联结词 c 异或的性质 主析取范式 主合取范式 交换律 结合律 对 可分配的 若 则有 2 与非 a 定义 见真值表 b 符号 记作 读作 与 的否定 或 与非 c 性质 不可结合的 不可结合的 3 或非 a 定义 见真值表 b 符号 读作 或非 或 或 的否定 c 性质 交换律 不可结合的 不可结合的 由 和 中的性质可见 和 是互为对偶的 4 蕴含否定 a 定义 见真值表 PQ P Q b 符号 c c c 定义一个联结词集合 用其中的联结词构成的式子足以把一切命题公式等价的表达出来 则称此联结词集合为全功能联结词集合 定义设有一联结词集合 若 用 中的联结词构成的等价式能表达任何一个命题公式 删除 中的任一联结词 从而形成一个新的联结词集合 至少有一个命题公式 不能用 中的联结词构成的等价式来表示 则称A为最小全功能联结词集合 均为全功能联结词集合 且均是最小全功能联结词集合 全功能联结词集合 例 用上述最小全功能联结词集合中的联结词单一表达下述命题公式 c c 1 4命题逻辑的推理理论 简言之 推理就是从前提推出结论的过程 前提是指已知的命题公式 结论是从前提出发 应用推理规则推出的命题公式 这样的推导过程称为演绎 或者叫形式证明 若推理的每一步所得结论都是根据推理规则得到的 则称结论是有效的 证明的有效与否与前提的真假无关 结论是否有效也与它自身的真假无关 若所有前提均为真 则经过有效证明所得到的结论也是真的 并称证明是合理的 所得结论为合理的结论 在数理逻辑中 我们只关心证明和结论是否有效 而不关心它是否合理 命题逻辑的推理理论 1 4 1推理概念 定义设A1 A2 An B是命题公式 如果A1 A2 An B是永真式 则称从前提A1 A2 An推出结论B的推理有效 并称B是A1 A2 An的逻辑结论 记作A1 A2 An B说明 1 设A1 A2 An B中出现n个命题变元 对任一组赋值 0或1 i 1 2 n 前提和结论有以下4种 推理概念 A1 A2 An为0 B为0 A1 A2 An为0 B为1 A1 A2 An为1 B为0 A1 A2 An为1 B为1 由定义可知 只要不出现 推理就有效 因此判别结论的有效性 就是判别是否会出现 中的情况 2 推理有效 并不能保证结论B一定为真 可见这与数学中的推理证明是不同的 1 4 2证明结论有效的方法 1 真值表法 2 等值演算法 3 主析取范式法 4 构造证明法 5 间接证明法 1 真值表法定义给定二个命题公式 和 当且仅当 是一个永真式 才可以说 是从 推导出来的 或称 是前提 的有效结论 定义设H1 H2 Hm 都是命题公式 当且仅当H1 H2 Hm 才可以说 是前提集合 H1 H2 Hm 的有效结论 证明结论有效的方法真值表法 真值表法的主要依据是 的真值表定义 若 当且仅当 为永真式 首先 将推理过程符号化 得到相应前提A1 An和结论B 再利用真值表证明A1 A2 An B是否为真 例 如果天气凉快 小王就不去游泳 天气凉快 所以小王没去游泳 解 设P 天气凉快Q 小王去游泳上述语句可符号化为 P Q 前提 P Q 结论 推理的形式结构 P Q 列出真值表 如下 真值表最后一列全为1 是永真式 所以推理是有效的 2 等值演算法将推理过程符号化 得到推理形式结构A1 A2 An B利用等值公式演算 证明A1 A2 An B为永真式 则推理正确 等值演算法 例 下午小王或者去看电影或去游泳 他没去看电影 所以他去游泳了 解 设P 小王下午去看电影Q 小王下午去游泳前提 P Q P结论 Q推理形式结构 P Q P Q由等值演算法 得 P Q P Q P Q P Q P Q P Q P P Q P Q Q P Q 1 P Q P Q为永真式 所以推理有效 3 主析取范式法将推理过程符号化 得到推理形式结构A1 A2 An B若A1 A2 An B的全体极小项的主析取范式为永真 则推理有效 例 如果我上街 我必去新华书店 我没有上街 所以我没去新华书店 解 设P 我上街Q 我去新华书店前提 P Q P结论 Q推理形式结构 P Q P Q 主析取范式法 P Q P Q P Q P Q P Q P Q P Q Q Q P Q P Q Q Q P P P Q P Q P Q P Q P Q P Q P Q 因为主析取范式中缺少一个极小项 P Q 所以 Q不是 P Q P的有效推理 4 构造证明法 构造证明法就是构造一个命题公式序列 它的每项或是所给的前提 或是由前提应用推理定理或推理规则得出的结论 而序列的最后一项是所要证明的结论 推理规则的依据是常用的永真蕴含式和等价公式 有 1 A A B 附加 2 A B A 化简 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 前提引入规则 在证明的任何步骤上 都可以引入前提 P规则 2 结论引入规则 在证明的任何步骤上 所得的结论都可以作为后续证明的前提引用 T规则 3 置换规则 在证明的任何步骤上 命题公式的子公式