离散数学教程PPT课件

高等学校21世纪教材 电子教案 离散数学 人民邮电出版社 2020 4 6 1 第一章命题逻辑 命题逻辑 也称命题演算 记为Ls 它与谓词逻辑构成数理逻辑的基础 而命题逻辑又是谓词逻辑的基础 数理逻辑是用数学方法即通过引入表意符号研究推理的学问 因此 数理逻辑又名为符号逻辑 命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系 退出 1 1命题与联结词1 2命题变元和合式公式1 3公式分类与等价公式1 4对偶式与蕴涵式1 5联结词的扩充与功能完全组1 6公式标准型 范式1 7公式的主范式1 8命题逻辑的推理理论 1 1命题与联结词 命题的概念 所谓命题 是指具有非真必假的陈述句 而疑问句 祈使句和感叹句等因都不能判断其真假 故都不是命题 命题仅有两种可能的真值 真和假 且二者只能居其一 真用1或T表示 假用0或F表示 由于命题只有两种真值 所以称这种逻辑为二值逻辑 命题的真值是具有客观性质的 而不是由人的主观决定的 如果一陈述句再也不能分解成更为简单的语句 由它构成的命题称为原子命题 原子命题是命题逻辑的基本单位 命题分为两类 第一类是原子命题 原子命题用大写英文字母P Q R 及其带下标的Pi Qi Ri 表示 第二类是复合命题 它由原子命题 命题联结词和圆括号组成 命题联结词 定义1 1 1设P表示一个命题 由命题联结词l和命题P连接成lP 称lP为P的否定式复合命题 lP读 非P 称l为否定联结词 lP是真 当且仅当P为假 lP是假 当且仅当P为真 否定联结词 l 的定义可由表1 1 1表示之 由于否定 修改了命题 它是对单个命题进行操作 称它为一元联结词 定义1 1 2设P和Q为两个命题 由命题联结词 将P和Q连接成P Q 称P Q为命题P和Q的合取式复合命题 P Q读做 P与Q 或 P且Q 称 为合取联结词 当且仅当P和Q的真值同为真 命题P Q的真值才为真 否则 P Q的真值为假 合取联结词 的定义由表1 1 2表示之 定义1 1 3设P和Q为两个命题 由命题联结词 把P和Q连接成P Q 称P Q为命题P和Q的析取式复合命题 P Q读做 P或Q 称 为析取联结词 当且仅当P和Q的真值同为假 P Q的真值为假 否则 P Q的真值为真 析取联结词 的定义由表1 1 3表示之 由定义可知 析取联结词表示 可兼和 不可兼和 另有别的联结词定义之 与合取联结词一样 使用析取联结词时 也不要求两命题间一定有任何关系 有关例子就不再给出了 定义1 1 4设P和Q为两个命题 由命题联结词 把P和Q连接成P Q 称P Q为命题P和Q的条件式复合命题 简称条件命题 P Q读做 P条件Q 或者 若P则Q 称 为条件联结词 当P的真值为真而Q的真值为假时 命题P Q的真值为假 否则 P Q的真值为真 条件联结词 的定义由表1 1 4表示之 在条件命题P Q中 命题P称为P Q的前件或前提 命题Q称为P Q的后件或结论 条件命题P Q有多种方式陈述 如果P 那么Q P仅当Q Q每当P P是Q的充分条件 Q是P的必要条件 等 在日常生活中 用条件式表示前提和结论之间的因果或实质关系 如例1 1 4中的 这种条件式称为形式条件命题 然而在命题逻辑中 一个条件式的前提并不要求与结论有任何关系 这种条件式称为实质条件命题 采用实质条件式作定义 不单是出于 善意推断 主要是因为前提与结论间有无因果和实质关系难以区分 而且实质条件式已包含了形式条件式 更便于应用 定义1 1 5令P Q是两个命题 由命题联结词 把P和Q连接成P Q 称P Q为命题P和Q的双条件式复合命题 简称双条件命题 P Q读做 P当且仅当Q 或 P等价Q 称 为双条件联结词 当P和Q的真值相同时 P Q的真值为真 否则 P Q的真值为假 双条件联结词 的定义由表1 1 5表示之 在本节结束时 应强调指出的是 复合命题的真值只取决于各原子命题的真值 而与它们的内容 含义无关 与原子命题之间是否有关系无关 理解和掌握这一点是至关重要的 请读者认真去领会 1 2命题变元和合式公式 命题变元 在命题逻辑中 命题又有命题常元和命题变元之分 一个确定的具体的命题 称为命题常元 一个不确定的泛指的任意命题 称为命题变元 显然 命题变元不是命题 只有用一个特定的命题取代才能确定它的真值 真或假 这时也说对该命题变元指派真值 命题常元和命题变元均可用字母P等表示 由于在命题逻辑中并不关心具体命题的涵义 只关心其真值 因此 可以形式地定义它们如下 定义1 2 1以真或1 假或0为其变域的变元 称为命题变元 真或1 假或0称为命题常元 2 合式公式 通常把含有命题变元的断言称为命题公式 但这没能指出命题公式的结构 因为不是所有由命题变元 联结词和括号所组成的字符串都能成为命题公式 为此常使用归纳定义命题公式 以便构成的公式有规则可循 由这种定义产生的公式称为合式公式 定义1 2 2单个命题变元和命题常元称为原子命题公式 简称原子公式 定义1 2 3合式公式是由下列规则生成的公式 单个原子公式是合式公式 若A是一个合式公式 则 lA 也是一个合式公式 若A B是合式公式 则 A B A B A B 和 A B 都是合式公式 只有有限次使用 和 生成的公式才是合式公式 当合式公式比较复杂时 常常使用很多圆括号 为了减少圆括号的使用量 可作以下约定 规定联结词的优先级由高到低的次序为 l 相同的联结词按从左至右次序计算时 圆括号可省略 最外层的圆括号可以省略 为了方便计 合式公式也简称公式 公式真值表 定义1 2 4对于公式中命题变元的每一种可能的真值指派 以及由它们确定出的公式真值所列成的表 称为该公式的真值表 定义1 2 5如果B是公式A中的一部分 且B为公式 则称B是公式A的子公式 用归纳法不难证明 对于含有n个命题变元的公式 有2n个真值指派 即在该公式的真值表中有2n行 为方便构造真值表 特约定如下 命题变元按字典序排列 对每个指派 以二进制数从小到大或从大到小顺序列出 若公式较复杂 可先列出各子公式的真值 若有括号 则应从里层向外层展开 最后列出所求公式的真值 4 命题的符号化 把一个用文字叙述的命题相应地写成由命题标识符 联结词和圆括号表示的合式公式 称为命题的符号化 符号化应该注意下列事项 确定给定句子是否为命题 句子中连词是否为命题联结词 要正确地表示原子命题和适当选择命题联结词 命题符号化是很重要的 一定要掌握好 在命题推理中常常最先遇到的就是符号化一个问题 解决不好 等于说推理的首要前提没有了 1 3公式分类与等价公式 公式分类 定义1 3 1设A为任意公式 则 对应每一个指派 公式A均相应确定真值为真 称A为重言式 或永真式 对应每一个指派 公式A均相应确定真值为假 称A为矛盾式 或永假式 至少存在一个指派 公式A相应确定真值为真 称A为可满足式 由定义可知 重言式必是可满足式 反之一般不真 重点将研究重言式 它最有用 因为它有以下特点 重言式的否定是矛盾式 矛盾式的否定是重言式 这样只研究其一就可以了 两重言式的合取式 析取式 条件式和双条件式等都仍是重言式 于是 由简单的重言式可构造出复杂的重言式 由重言式使用公认的规则可以产生许多有用等价式和蕴涵式 判定给定公式是否为永真式 永假式或可满足式的问题 称为给定公式的判定问题 在Ls中 由于任何一个命题公式的指派数目总是有限的 所以Ls的判定问题是可解的 其判定方法有真值表法和公式推演法 等价公式 定义1 3 2设A和B是两个命题公式 如果A B在其任意指派下 其真值都是相同的 则称A和B是等价的 或逻辑相等 记作A B 读作A等价B 称A B为等价式 显然 若公式A和B的真值表是相同的 则A和B等价 因此 验证两公式是否等价 只需做出它们的真值表即可 在这里 请读者注意 和 的区别与联系 区别 是逻辑联结词 属于目标语言中的符号 它出现在命题公式中 不是逻辑联结词 属于元语言中的符号 表示两个命题公式的一种关系 不属于这两个公式的任何一个公式中的符号 联系 可用下面定理表明之 定理1 3 1A B当且仅当A B是永真式 有时也称A B是永真双条件式 等价式有下列性质 自反性 即对任意公式A 有A A 对称性 即对任意公式A和B 若A B 则B A 传递性 即对任意公式A B和C 若A B B C 则A C 基本等价式 命题定律在判定公式间是否等价 有一些简单而又经常使用的等价式 称为基本等价式或称命题定律 牢固地记住它并能熟练运用 是学好数理逻辑的关键之一 读者应该注意到这一点 现将这些命题定律列出如下 1 双否定 A A 2 交换律 A B B A A B B A A B B A 3 结合律 A B C A B C A B C A B C A B C A B C 4 分配律 A B C A B A C A B C A B A C 5 德 摩根律 A B A B A B A B 6 等幂律 A A A A A A 7 同一律 A T A A F A 8 零律 A F F A T T 9 吸收律 A A B A A A B A 10 互补律 A A F 矛盾律 A A T 排中律 11 条件式转化律 A B A B A B B A 12 双条件式转化律 A B A B B A A B A B A B A B 13 输出律 A B C A B C 14 归谬律 A B A B A 上面这些定律 即是通常所说的布尔代数或逻辑代数的重要组成部分 它们的正确性利用真值表是不难给出证明的 代入规则和替换规则在定义合成公式时 已看到了逻辑联结词能够从已知公式形成新的公式 从这个意义上可把逻辑联结词看成运算 除逻辑联结词外 还要介绍 代入 和 替换 它们也有从已知公式得到新的公式的作用 因此有人也将它们看成运算 这不无道理 而且在今后讨论中 它的作用也是不容忽视的 1 代入规则定理1 3 2在一个永真式A中 任何一个原子命题变元R出现的每一处 用另一个公式代入 所得公式B仍是永真式 本定理称为代入规则 2 替换规则定理1 3 3设A1是合式公式A的子公式 若A1 B1 并且将A中的A1用B1替换得到公式B 则A B 称该定理为替换规则 满足定理1 3 3条件的替换 称为等价替换 代入和替换有两点区别 代入是对原子命题变元而言的 而替换可对命题公式实行 代入必须是处处代入 替换则可部分替换 亦可全部替换 1 4对偶式与蕴涵式 对偶式在上节介绍的命题定律中 多数是成对出现的 这些成对出现的定律就是对偶性质的反映 即对偶式 利用对偶式的命题定律 可以扩大等价式的个数 也可减少证明的次数 定义1 4 1在给定的仅使用联结词 和 的命题公式A中 若把 和 互换 F和T互换而得到一个命题公式A 则称A 为A的对偶式 显然 A也是A 的对偶式 可见A与A 互为对偶式 定理1 4 1 对偶定理 设A和A 互为对偶式 P1 P2 Pn是出现A和A 中的原子命题变元 则 A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn 表明 公式A的否定等价于其命题变元否定的对偶式 表明 命题变元否定的公式等价于对偶式之否定 定理1 4 2设A和B为两个命题公式 若A B则A B 有了等价式 代入规则 替换规则和对偶定理 便可以得到更多的永真式 证明更多的等价式 使化简命题公式更为方便 蕴涵式定义1 4 2设A和B是两个命题公式 若A B是永真式 则称A蕴涵B 记作A B 称A B为蕴涵式或永真条件式 符号 和 的区别与联系类似于 和 的关系 区别 是逻辑联结词 属于对象语言中的符号 是公式中的符号 而 不是联结词 属于元语言中的符号 表示两个公式之间的关系 不是两公式中符号 联系 A B成立 其充要条件A B是永真式 蕴涵式有下列性质 自反性 即对任意公式A 有A A 传递性 即对任意公式A B和C 若A B B C 则A C 对任意公式A B和C 若A B A C 则A B C 对任意公式A B和C 若A C B C 则A B C 这些性质的正确性 请读者自己验证 下面给出等价式与蕴涵式之间的关系 定理1 4 3设A和B是两命题公式 A B的充要条件是A B且B A 蕴涵式证明方法除真值表外 还有两种方法 前件真导后件真方法设公式的前件为真 若能推导出后件也为真 则条件式是永真式 故蕴涵式成立 因为欲证A B 即证A B是永真式 对于A B 除在A取真和B取假时 A B为假外 余下A B皆为真 所以 若A B的前件A为真 由此可推出B亦为真 则A B是永真式 即A B 后件假导前件假方法设条件式后件为假 若能推导出前件也为假 则条件式是永真式 即蕴涵式成立 因为若A B的后件B取假 由此可推出A取假 即推证了 B A 又因A B B A 故A B成立 1 5联结词的扩充与功能完全组 联结词的扩充定义1 5 1设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的真值确定 当且仅当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 P Q的真值由P和Q的真值确定 当且仅当P和Q的真值不同时 P Q为 否则P Q为 双条件非 又常称为 异或 也常用符号 表示之 上面4个联结词构成的复合命题 其真值表如下 由表可知 P Q P Q P Q P Q P Q P Q P Q P Q 与非 或非和异或的性质与非 或非以及异或在计算机科学中是经常使用的3个联结词 因此 掌握它们的性质是十分必要的 令P Q和R是原子命题变元 与非的性质 a P Q Q P b P P P c P Q P Q P Q d P P Q Q P Q 或非的性质 a P Q Q P b P P P c P Q P Q P Q d P P Q Q P Q从上述的性质可知 联结词 和 可分别用联结词 或者 取代 读者可以自行验证 和 都不满足结合律 异或的性质 a P Q Q P b P Q R P Q R c P Q R P Q P R d P P F F P P T P P e 若P Q R 则Q R P P P Q 且P Q R F 以上所有性质 用真值表或命题定律都是不难证明的 至此 已有了9个联结词 是否还需要扩充呢 事实上 两上命题变无P和Q 与9个联结词一共可构成类命题公式 如下表示之 从列表可知 除命题常元F T及命题变元本身外 命题联结词一共有9个就够了 为了方便 可规定其优先级 由高到低次序为 等 联结词功能完全组已知有9个联结词就够用了 能不能少呢 若能少 表明有些联结词的逻辑功能可由其他联结词替代 事实上 也确实如此 因为有下列等价式 P Q P Q P Q P Q P Q P Q P Q P Q 可见 扩充的4个联结词 和 能由原有5个联结词分别替代之 又由命题定律 P Q P Q Q P P Q P QP Q P Q P Q P Q 可知 原有5个联结词 和 又能由联结词组 或 取代 那么 究竟最少用几个联结词 就是说 用最少的几个联结词就能等价表示所有的命题公式 或者说 用最少的几个联结词就能替代所有联结词的功能 这便是所要定义的联结词功能完全组 定义1 5 2称G为联结词功能完全组 如果G满足下列两条件 由G中联结词构成的公式能等价表示任意命题公式 G中的任一联结词不能用其余下联结词等价表示 可以证明 都是联结词功能完全组 而 都不是联结词功能完全组 但为了表示方便 仍经常使用联结词组 1 6公式标准型 范式 简单合取式与简单析取式定义1 6 1在一公式中 仅由命题变元及其否定构成的合取式 称该公式为简单合取式 其中每个命题变元或其否定 称为合取项 定义1 6 2在一公式中 仅由命题变元及其否定构成的析取式 称该公式为简单析取式 其中每个命题变元或其否定 称为析取项 例如 公式P Q P Q和 P Q P等都是简单合取式 而P Q和 P为相应的简单合取式的合取项 公式P Q P Q P Q P等都是简单析取式 而P Q和 P为相应简单析取式的析取项 注意 一个命题变元或其否定既可以是简单合取式 也可是简单析取式 如例中P Q等 定理1 6 1简单合取式为永假式的充要条件是 它同时含有某个命题变元及其否定 定理1 6 2简单析取式为永真式的充要条件是 它同时含有某个命题变元及其否定 析取范式与合取范式定义1 6 3一个命题公式A称为析取范式 当且仅当A可表为简单合取式的析取 即A Ai 其中Ai为简单合取式 i 1 2 n 定义1 6 4一个命题公式A称为合取范式 当且仅当A可表为简单析取式的合取 即A Ai 其中Ai为简单析取式 1 i n 定理1 6 3对于任何一命题公式 都存在与其等价的析取范式和合取范式 求范式算法 使用命题定律 消去公式中除 和 以外公式中出现的所有联结词 使用 P P和德 摩根律 将公式中出现的联结词 都移到命题变元之前 利用结合律 分配律等将公式化成析取范式或合取范式 范式的应用利用析取范式和合取范式可对公式进行判定 定理1 6 4公式A为永假式的充要条件是A的析取范式中每个简单合取式至少包含一个命题变元及其否定 定理1 6 5公式A为永真式的充要条件是A的合取范式中每个简单析取式至少包含一个命题变元及其否定 范式不唯一性 1 7公式的主范式 范式基本解决了公式的判定问题 但由于范式不唯一性 对识别公式间是否等价带来一定困难 而公式的主范式解决了这个问题 下面将分别讨论主范式中的主析取范式和主合取范式 主析取范式 1 小项的概念和性质定义1 7 1在含有n个命题变元的简单合取式中 若每个命题变元与其否定不同时存在 而二者之一出现一次且仅出现一次 则称该简单合取式为小项 或布尔积 例如 两个命题变元P和Q 其构成的小项有P Q P Q P Q和 P Q 而三个命题变元P Q和R 其构成的小项有P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R 可以证明 n个命题变元共形成2n个小项 如果将命题变元按字典序排列 并且把命题变元与1对应 命题变元的否定与0对应 则可对2n个小项依二进制数编码 记为mi 其下标i是由二进制数转化的十进制数 用这种编码所求得2n个小项的真值表 可明显地反映出小项的性质 表1 7 1和表1 7 2分别给出了2个命题变元P和Q 3个命题变元P Q和R的小项真值表 从表1 7 1 表1 7 2可看出 小项有如下性质 a 没有两个小项是等价的 即是说各小项的真值表都是不同的 b 任意两个不同的小项的合取式是永假的 mi mj i j c 所有小项之析取为永真 mi d 每个小项只有一个解释为真 且其真值1位于主对角线上 2 主析取范式定义与存在定理定义1 7 2在给定公式的析取范式中 若其简单合取式都是小项 则称该范式为主析取范式 定理1 7 1任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式 3 主析取范式的求法主析取范式求法有两种 真值表法和公式化归法 定理1 7 1的证明已给出了用真值表求主析取范式的方法 而公式化归法给出如下 a 把给定公式化成析取范式 b 删除析取范式中所有为永假的简单合取式 c 用等幂律化简简单合取式中同一命题变元的重复出现为一次出现 如P P P d 用同一律补进简单合取式中未出现的所有命题变元 如Q 则P P Q Q 并用分配律展开之 将相同的简单合取式的多次出现化为一次出现 这样得到了给定公式的主析取范式 4 主析取范式的惟一性定理1 7 2任意含n个命题变元的非永假命题公式 其主析取范式是惟一的 主合取范式 1 大项的概念和性质定义1 7 3在n个命题变元的简单析取式中 若每个命题变元与其否定不同时存在 而二者之一必出现一次且仅出现一次 则称该简单析取式为大项 或布尔和 例如 由两个命题变元P和Q 构成大项有P Q P Q P Q P Q 三个命题变元P Q和R 构成P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R 能够证明 n个命题变元共有2n个大项 如果将n个命题变元排序 并且把命题变元与 对应 命题变元的否定与 对应 则可对2n个大项按二进制数编码 记为Mi 其下标i是由二进制数化成的十进制数 用这种编码所求的2n个大项的真值表 能直接反映出大项的性质 表1 7 3给出了2个命题变元P和 构成所有大项的真值表 类似可给出 个命题变元 和 的所有大项的真值表 留给读者完成 从表1 7 3可看出大项的性质 a 没有两个大项是等价的 b 任何两个不同大项之析取是永真的 即Mi Mj i j c 所有大项之合取为永假 即Mi d 每个大项只有一个解释为假 且其真值0位于主对角线上 2 主合取范式的定义与其存在定理定义1 7 4在给定公式的合取范式中 若其所有简单析取式都是大项 称该范式为主合取范式 定理1 7 3任意含有n个命题变元的非永真命题公式A 都存在与其等价的主合取范式 定理1 7 4任意含n个命题变元的非永真命题公式A 其主合取范式是唯一的 上述两定理的证明 类似于定理1 7 1和定理1 7 2 主合取范式的求法也有两种 类似于主析取范式的求法 主析取范式与主合取范式之间的关系由于主范式是由小项或大项构成 从小项和大项的定义 可知两者有下列关系 mi Mi Mi mi因此 主析取范式和主合取范式有着 互补 关系 即是由给定公式的主析取范式可以求出其主命取范式 设命题公式A中含有n个命题变元 且A的主析取范式中含有k个小项 则 A的主析取范式中必含有2n k个小项 不妨含为 即 A 于是 A A 由此可知 从A的主析取范式求其主合取范式的步骤为 a 求出A的主析取范式中设有包含的小项 b 求出与 a 中小项的下标相同的大项 c 做 b 中大项之合取 即为A的主合取范式 例如 P Q Q m1 m3 则 P Q Q M0 M2 主范式的应用利用主范式可以求解判问题或者证明等价式成立 1 判定问题根据主范式的定义和定理 也可以判定含n个命题变元的公式 其关键是先求出给定公式的主范式 其次按下列条件判定之 a 若A 或A可化为与其等价的 含2n个小项的主析取范式 则A为永真式 b 若A 或A可化为与其等价的 含2n个大项的主合取范式 则A为永假式 c 若A不与 或者 等价 且又不含2n个小项或者大项 则A为可满足的 2 证明等价式成立由于任一公式的主范式是唯一的 所以将给定的公式求出其主范式 若主范式相同 则给定两公式是等价的 1 8命题逻辑的推理理论 在逻辑学中 把从前题 又叫公理或假设 出发 依据公认的推理规则 推导出一个结论 这一过程称为有效推理或形式证明 所得结论叫做有效结论 这里最关心的不是结论的真实性而是推理的有效性 前提的实际真值不作为确定推理有效性的依据 但是 如果前提全是真 则有效结论也应该真而绝非假 在数理逻辑中 集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理 与这些规则有关的理论称为推理理论 提请注意 必须把推理的有效性和结论的真实性区别开 有效的推理不一定产生真实的结论 产生真实结论的推理过程未必一定是有效的 再说 有效的推理中可能包含假的前提 而无效的推理却可能包含真的前提 可见 推理的有效性是一回事 前提与结论的真实与否是另一回事 所谓推理有效 指它的结论是它的前提的合乎逻辑的结果 也即 如果它的前提都为真 那么所得结论也必然为真 而并不是要求前提或结论一定为真或为假 如果推理是有效的话 那么不可能它的前提都为真时而它的结论为假 推理的基本概念和推理形式推理也称论证 它是指由已知命题得到新的命题的思维过程 其中已知命题称为推理的前提或假设 推得的新命题称为推理的结论 在数理逻辑中 前提H是一个或者n个命题公式H1 H2 Hn 结论是一个命题公式C 由前提到结论的推理形式可表为H1 H2 Hn C 其中符号 表示推出 可见 推理形式是命题公式的一个有限序列 它的最后一个公式是结论 余下的为前提或假设 定义1 8 1如果存在H1 H2 Hn C的一个指派 使得每个Hi 1 i n 为真而C为假推理形式H1 H2 Hn C是无效的 否则 推理是有效的 此时称C是H1 H2 Hn的有效结论 或称C是从前提H1 H2 Hn逻辑推出的结论 定理1 8 1推理形式H1 H2 Hn C是有效的 当且仅当命题公式 H1 H2 Hn C是永真式 亦即 H1 H2 Hn C 推理规则在数理逻辑中 从前提推导出结论 要依据事先提供的公认的推理规则 它们是 规则 也称前提引入规则 在推导过程中 前提可视需要引入使用 规则 也称结论引入规则 在推导过程中 前面已导出的有效结论都可作为后续推导的前提引入 此外 在从前提推出的结论为条件式时 还需要下面规则 规则 也称条件证明引入规则 若推出有效结论为条件式R C时 只需将其前件R加入到前提中作为附加前提且再去推出后件C即可 规则的正确性可由下面定理得到保证 定理1 8 2若H1 H2 Hn R C 则H1 H2 Hn R C 推理定律在推理过程中 除使用推理规则后 还需要使用许多条推理定律 这些定律可由以前讲过的命题定律 蕴涵式及运用定理1 8 1而得到 下面只给出了由蕴涵式得出的推理定律 它们是 1 P Q P 2 P Q Q 3 P P Q 4 P P Q 5 Q P Q 6 P Q P 7 P Q Q 8 P P Q Q 9 Q P Q P 10 P P Q Q 11 P Q Q R P R 12 P Q Q R P R 13 P Q R S P R Q S 14 P Q R S P R Q S特别当Q S时 有 P Q R