x本科数理逻辑-命题.ppt

1 主析取范式1 极小项在含有n个命题变项的简单合取式中 若每个命题变项和它的否定式不同时出现 而二者之一必出现且仅出现一次 称这样的简单合取式极小项 极小项与所含变元的个数有关2 主析取范式设由n个命题变项构成的析取范式中所有的简单合取式都是极小项 则称该析取范式为主析取范式 p q r p q r p r q r p q r p q r p q r p q r 该公式的真值表3 公式的主析取范式中的极小项所对应的赋值均为成真赋值 也是该公式的全部成真赋值 由真值表得出 公式的主析取范式包含全部极小项 则该公式为重言式 复习 主析取范式 由极小项的析取构成极小项的成真赋值可以使公式的真值为真故极小项的成真赋值即为公式的成真赋值公式的主析取范式中极小项的个数与其真值表中赋值为真的个数相同 且是全部成真赋值 一个命题公式的主析取范式表示是存在唯一的 公式 p q r p q r p q r p q r m1 m3 m7主析取范式 pqr p q r000000110100011100010101001111 返回 2 主析取范式的确定方法 1 等值演算法a 先确定公式的析取范式b 将简单合取式化为极小项 不断合取所缺变元的永真式 c 将相同极小项去掉 p q r2 真值表法列出公式的真值表将真值表中真值为真的相应赋值所对应的极小项进行析取 3 主合取范式1 极大项 在含有n个命题变项的简单析取式中 若每个命题变项和它的否定式不同时出现 而二者之一必出现且仅出现一次 称这样的简单析取式极大项 2 极大项与所含变元的个数有关三个变元的所有极大项为 p q r p q r p q r p q r M0 0 0 0 M1 0 0 1 M2 0 1 0 M3 0 1 1 p q r p q r p q r p q rM4 1 0 0 M5 1 0 1 M6 1 1 0 M7 1 1 1 3 n个变元的所有极大项共有2n4 主合取范式设由n个命题变项构成的合取范式中所有的简单合取式都是极大项 则称该合取范式为主合取范式 例 p q r p r q r p q r p q r p q r p q r p q r 该公式的真值表注 该式的极大项所对应的赋值均为该公式的成假赋值 也是该公式的全部成假赋值 可从真值表得出 4 主合取范式的确定方法 1 等值演算法a 先确定公式的合取范式b 将简单析取式化为极大项 通过不断析取所缺变元的永假式 c 将相同极大项去掉2 真值表法列出公式的真值表将真值表中真值为假的相应赋值所对应的极大项进行合取3 利用主析取范式与主合取范式的关系若已知公式A的主析取范式首先写出 A的主析取范式 从全部极小项去掉A式包含的极小项得到 对 A的主析取范式取否定可得到A的主合取范式例 已知A的主析取范式为A p q r m0 m1 m3 m5 m7从真值表更易看出 A m2 m4 m6A A m2 m4 m6 5 主合取范式 由极大项的合取构成极大项的成假赋值可以使公式的真值为假故极大项的成假赋值即为公式的成假赋值公式的主合取范式中极大项的个数与其真值表中赋值为假的个数相同 且是全部成假赋值 一个命题公式的主合取范式表示是存在唯一的 公式 p q r p q r p q r p q r p q r p q r M0 M2 M4 M5 M6主合取范式 pqr p q r000000110100011100010101001111 返回 5 主析取范式与主合取范式的应用a 确定公式的全部成假赋值 利用主合取范式 确定公式的全部成真赋值 利用主析取范式 A p q M0 M3 p q p q 全部成假赋值为 0 0 与 1 1 b 判断公式的类型若公式的主合取范式包含所含变元的全部极大项则该公式为永假式若公式的主合取范式包含所含变元的若干极大项则该公式为可满足式c 判断两个公式是否等值例判断 p q r与 p q r是否等值 p q r m1 m3 m4 m5 m7 p q r m0 m1 m2 m3 m4 m5 m7故不等值 2 3联接词的完备集一 联接词的扩充1 异或联接词 P q p q p q 2 与非联接词定义设p q为两个命题 复合命题 p与q的否定式 称作p q的与非式 记作p q 符号 称作与非联结词 p q为真当且仅当p与q不同时为真 p q p q 3 或非联接词定义设p q为两个命题 复合命题 p或q的否定式 称作p q的或非式 记作p q符号 或非联结词 p q为真当且仅当p与q同时为假 p q p q 4 几种连接词相互的关系 1 p p p p p p p p p p 2 p q p q p q p q p q 3 p q p q p q p q p q 4 p q p q p q p q 5 p q p q p q p p q q 6 a P Q P Q b P Q P Q 二 联接词的完备集1 定义设S是一个联结词集合 如果任何n n 1 元公式都可以由仅含S中的联结词构成的等值公式表示 则称S是联结词完备集 可验证s0 2 冗余的联接词如果某个联接词可用功能完备集中的其他连接词所表示 则称该连接词为冗余的连接词s0中的 均为冗余的连接词s1 是否还含有冗余的连接词 s2 将公式 p q r在s2下表示3 极小功能完备集 若联结词完备集中不含冗余的连接词s3 将 p r q在s3下表示s4 将 p r q在s4下均为极小功能完备集将公式 p r s p 在极小功能完备集s5 中表示特别地s5 s6 均为联接词的极小功能完备集将 p q r在s5下 一 推理的有效性1 推理的合法性在任何论证中 倘若认定前提是真的 从前提推导出结论的论证又是遵守了逻辑推理规则 则会公认此种结论是真的 这种论证称为合法的论证 在通常的论证中 主要是关心其论证的合法性 2 推理的有效性在数理逻辑中情况则有所不同 这里集中注意于推理规则的研究 依据这些规则由前提集合中推导出结论来 不管各前提的真值如何 由符号组成的 从前提的集合出发 依据公认的逻辑规则推导出来的任何结论 都称为有效的结论 这种论证称为有效的论证 在确定论证的有效性时 前提的真值不起任何作用 也就是说 在数理逻辑中 仅仅关注于论证的有效性 而无需关心其合法性 第三章命题逻辑的推理理论 设p x是偶数 q x2是偶数看以下四个推理1 如果x是偶数 则x2是偶数且x是偶数 推出x2是偶数前提 p q p推出结论q2 如果x是偶数 则x2是偶数且x2是偶数 推出x是偶数前提 p q q推出结论p3 如果x是偶数 则x2是偶数且x不是偶数 推出x2不是偶数前提 p q p推出结论 q4 如果x是偶数 则x2是偶数且x2不是偶数 推出x不是偶数前提 p q q推出结论 p 从常规的逻辑上不论p q表示何种意义1 和4 的推理均为合乎逻辑的 正确的 2 推理是错误的 肯定后件的逻辑错误3 推理是错误的 否定前件的逻辑错误推理的有效性即为 不论符号表示何种意义 真值如何 推理均为正确的 返回 返回 二 有效推理1 推理的形式结构设A A1 A2 A3 Am 由A推出B的推理的形式结构记为A B蕴涵式表示为 A1 A2 Am B2 推理有效形式结构的定义 设A1 A2 A3 Am B是命题公式 若对A1 A2 A3 Am B中出现的任意一组赋值 或A1 A2 Am为假 或A1 A2 Am为真时 B也为真 则称由前提集合A1 A2 A3 Am推出B的推理是有效的或是正确的 称B是前提集合 A1 A2 A3 Am 的有效结论 记为 A1 A2 A3 Am B即 A1 A2 Am B 注 1 由前提集合A1 A2 A3 Am推出B的推理是否是有效的与前提集合各命题公式的次序无关 2 由推理形式A1 A2 Am B取得真值的几种情况 a A1 A2 Am真值为F B为Fb A1 A2 Am真值为F B为Tc A1 A2 Am真值为T B为Fd A1 A2 Am真值为T B为T当取得a b d 三种情况均称为有效推理3 由推理有效的定义可得出 推理有效 推理正确 并不能保证结论B一定为真推理有效 推理正确 与结论B的真值无关推理有效 推理正确 是指推理过程是合乎逻辑的 即 只要前提集合是真的 那么结论一定是真的 3 推理形式结构的另外等价形式 定理 由前提集合A1 A2 A3 Am推出B的推理是有效的或是正确的当且仅当 A1 A2 Am B为重言式 永真式 从开始的例来验证 设p x是偶数 q x2是偶数看以下四个推理1 如果x是偶数 则x2是偶数且x是偶数 推出x2是偶数前提 p q p推出结论q2 如果x是偶数 则x2是偶数且x2是偶数 推出x是偶数前提 p q q推出结论p3 如果x是偶数 则x2是偶数且x不是偶数 推出x2不是偶数前提 p q p推出结论 q4 如果x是偶数 则x2是偶数且x2不是偶数 推出x不是偶数前提 p q q推出结论 p 从常规的逻辑上不论p q表示何种意义1 和4 的推理均为合乎逻辑的 正确的 2 推理是错误的 肯定后件的逻辑错误3 推理是错误的 否定前件的逻辑错误推理的有效性即为 不论符号表示何种意义 真值如何 推理均为正确的 返回 返回 4 用真值表方法来判断推理的有效性从定义可得出 将各前提公式及其结论B列出真值表方法1 从所有前提公式均为真的相应行中看对应的结论B是否全为真如果全为真 则结论B是前提集合的有效结论2 从所有结论B为假相应行中看对应的前提各公式是否至少有一个为假如果成立 则结论B是前提集合的有效结论3 15 周一 结束5 用定义来判断推理的有效性将前提集合的各公式合取作为前件 结论B为后件组成蕴涵式用等值演算方法 T为重言蕴涵式主析取范式方法 所含变元的全部极小项的析取 二 推理定律将一些经过验证为推理有效的重言蕴涵式作为定律 例 前提公式 A1 A2 结论B 真值表为PQP Q PA1 A2B 001110011111100000111001可知A1 A2不是B的有效结论例 前提公式A1 A2 结论B 真值表为PQP QPA1 A2B 001000011111100100111111可知A1 A2是B的有效结论 返回 例 设前提集合为A1 p q A2 q r 结论B r qA1 A2 B p q q r r q p r不是永真式 m1 m3 m4 m5 m6 m7所以前提集合为A1 p q A2 q r不是B r q的有效结论例 设前提集合为A1 p q A2 q结论B pA1 A2 B p q q p 1永真式 m0 m1m2 m3所以前提集合为A1 p q A2 q是B的有效结论即 p q q B成立 返回 1 附加式 A A BB A B2 化简式A B AA B B3 假言推理 A B A B4 拒取式 A B B A5 析取三段论 A B B A6 假言三段论 A B B C A C 7 等价三段论 A B B C A C 8 构造性二难 A B C D A C B D 另外对于前面所给出的若干等值式 A B A B相当于 A B A B T相当于 A B A B T且 A B A B T则A B A B且 A B A B9 一个等值式相当于对应两个推理定律 设p x是偶数 q x2是偶数看以下四个推理1 如果x是偶数 则x2是偶数且x是偶数 推出x2是偶数前提 p q p推出结论q2 如果x是偶数 则x2是偶数且x2是偶数 推出x是偶数前提 p q q推出结论p3 如果x是偶数 则x2是偶数且x不是偶数 推出x2不是偶数前提 p q p推出结论 q4 如果x是偶数 则x2是偶数且x2不是偶数 推出x不是偶数前提 p q q推出结论 p 从常规的逻辑上不论p q表示何种意义1 和4 的推理均为合乎逻辑的 正确的 2 推理是错误的 肯定后件的逻辑错误3 推理是错误的 否定前件的逻辑错误推理的有效性即为 不论符号表示何种意义 真值如何 推理均为正确的 返回 返回