【数理逻辑】命题逻辑的等值演算与推理演算 ( 命题逻辑 |
您所在的位置:网站首页 › 如果p那么q等值于 › 【数理逻辑】命题逻辑的等值演算与推理演算 ( 命题逻辑 |
文章目录一、 命题逻辑基本概念二、 等值演算三、 主合取 ( 析取 ) 范式四、 推理演算1、附加律2、化简律3、假言推理4、拒取式5、析取三段论6、假言三段论7、等价三段论8、构造性两难 参考博客 : 【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表 可满足式 矛盾式 重言式 )【数理逻辑】命题逻辑 ( 等值演算 | 幂等律 | 交换律 | 结合律 | 分配律 | 德摩根律 | 吸收率 | 零律 | 同一律 | 排中律 | 矛盾律 | 双重否定率 | 蕴涵等值式 … )【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 )【数理逻辑】命题逻辑 ( 命题逻辑推理 | 推理的形式结构 | 推理定律 | 附加律 | 化简律 | 假言推理 | 拒取式 | 析取三段论 | 假言三段论 | 等价三段论 | 构造性两难 )【数理逻辑】命题逻辑 ( 命题逻辑推理正确性判定 | 形式结构是永真式 - 等值演算 | 从前提推演结论 - 逻辑推理 )一、 命题逻辑基本概念命题逻辑基本概念 命题逻辑联结词真值表命题逻辑类型 : 可满足式 , 永真式 , 永假式 ;1 . 命题公式 组成 : ① 单个 命题变元 / 命题常元 是命题公式 ; ② 如果 A是命题公式 , 则 (\lnot A)也是命题公式 ; ③ 如果 A,B是命题公式 , 则 (A \land B) , (A \lor B), (A \to B), (A \leftrightarrow B)也是命题公式 ; ④ 有限次 应用 ① ② ③ 形成的符号串 是命题公式 ; ( 无限次不行 ) 2 . 联结词 : 原子命题 : p , q , r表示 原子命题 , 又称为 简单命题 ; 真 : 1表示 命题真值 为真 ; 假 : 0表示 命题真值 为假 ; 联结词 : 上一篇博客 【数理逻辑】谓词逻辑 ( 个体词 | 个体域 | 谓词 | 全称量词 | 存在量词 | 谓词公式 | 习题 ) 三. 联结词 章节讲解了联结词 ; 否定联结词 : \lnot合取联结词 : \land, p \land q, pq同真, 结果才为真 , 其余情况为假 ; 析取联结词 : \lor, p \lor q, pq同假, 结果才为假 , 其余情况为真 ; 蕴涵联结词 : \to, p \to q, p真 q假, 结果才为假 , 其余情况为真 ; 等价联结词 : \leftrightarrow, p \leftrightarrow q, pq真值相同时为真 , 表示等价成立 , pq真值相反时为假 , 等价不成立 ; 联结词优先级 : “ \lnot” 大于 “ \land , \lor” 大于 “ \to, \leftrightarrow” \land , \lor优先级相同 ; \to, \leftrightarrow优先级相同 ; 3 . 命题逻辑类型 : 可满足式 : 真值表中 , 至少有一个结果为真 , 可以都为真 ; 矛盾式 ( 永假式 ) : 所有的真值都为假 ; 可满足式 与 矛盾式 , 是 二选一 的 , 复合命题 要么是 可满足式 , 要么是 矛盾式 ; 重言式 ( 永真式 ) 是可满足式的一种 ; 4 . 简单命题形式化 : 参考 : 复合命题 与 命题符号化 定义命题 : 使用 p,q代表真假必居其一的陈述句 ; 使用联结词 : 然后使用联结词联结这些 p,q命题 ; 参考博客 : 【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表 可满足式 矛盾式 重言式 )二、 等值演算等值式概念 : A , B是两个命题公式 , 如果 A \leftrightarrow B是永真式 , 那么 A,B两个命题公式是等值的 , 记做 A \Leftrightarrow B; 等值演算置换规则 : A和 B两个命题公式 , 可以 互相代替 , 凡是出现 A的地方都可以替换成 B, 凡是出现 B的地方都可以替换成 A; 基本运算规律 : 1. 幂等律 : A \Leftrightarrow A \lor A, A \Leftrightarrow A \land A2. 交换律 : A \lor B \Leftrightarrow B \lor A, A \land B \Leftrightarrow B \land A3. 结合律 : (A \lor B ) \lor C \Leftrightarrow A \lor (B \lor C), (A \land B ) \land C \Leftrightarrow A \land (B \land C)4. 分配律 : A \lor (B \land C) \Leftrightarrow ( A \lor B ) \land ( A \lor C ), A \land (B \lor C) \Leftrightarrow ( A \land B ) \lor ( A \land C )新运算规律 : 5. 德摩根律 : \lnot ( A \lor B ) \Leftrightarrow \lnot A \land \lnot B, \lnot ( A \land B ) \Leftrightarrow \lnot A \lor \lnot B6. 吸收率 : 前者将后者吸收了 : A \lor ( A \land B ) \Leftrightarrow A后者将前者吸收了 : A \land ( A \lor B ) \Leftrightarrow A; 0 , 1相关的运算律 : 7. 零律 : A \lor 1 \Leftrightarrow 1, A \land 0 \Leftrightarrow 08. 同一律 : A \lor 0 \Leftrightarrow A, A \land 1 \Leftrightarrow A9. 排中律 : A \lor \lnot A \Leftrightarrow 110. 矛盾律 : A \land \lnot A \Leftrightarrow 0对偶原理适用于上述运算律 , 将两边的 \land , \lor互换 , 同时 0 ,1互换 , 等价仍然成立 ; 等价蕴含运算规律 : 11. 双重否定率 : \lnot \lnot A \Leftrightarrow A12. 蕴涵等值式 : A \to B \Leftrightarrow \lnot A \lor B13. 等价等值式 : A \leftrightarrow B \Leftrightarrow ( A \to B ) \lor ( B \to A )14. 等价否定等值式 : A \leftrightarrow B \Leftrightarrow \lnot A \leftrightarrow \lnot B15. 假言易位 ( 逆否命题 ) : A \to B \Leftrightarrow \lnot B \to \lnot A16. 归谬论 ( 反证法 ) : ( A \to B ) \land ( A \to \lnot B ) \Leftrightarrow \lnot A参考博客 : 【数理逻辑】命题逻辑 ( 等值演算 | 幂等律 | 交换律 | 结合律 | 分配律 | 德摩根律 | 吸收率 | 零律 | 同一律 | 排中律 | 矛盾律 | 双重否定率 | 蕴涵等值式 … ) 三、 主合取 ( 析取 ) 范式1 . 极小项 极小项 : 极小项 是 一种 简单合取式 ; 1.前提 ( 简单合取式 ) : 含有 n个 命题变项 的 简单合取式 ; 2.命题变项出现次数 : 每个命题变项 均 以 文字 的 形式 在其中出现 , 且 仅出现 一次 ;3.命题变项出现位置 : 第 i( 1 \leq i \leq n) 个文字出现在 左起 第 i个位置 ; n是指命题变项个数 ; 4.极小项总结 : 满足上述三个条件的 简单合取式 , 称为 极小项 ;5.m_i与 M_i之间的关系 : ① \lnot m_i \iff M_i② \lnot M_i \iff m_i每个命题 按照指定顺序 , 且 只出现一次 的 简单合取式 , 称为极小项 ; 极小项列出的是成真赋值 , 因为合取式只有一种情况成真 , 那就是全真 ; 2 . 极大项 关于 极大项 的 说明 : 1.极大项个数 : n个 命题变元 会 产生 2^n个 极大项 ; 2.互不等值 : 2^n个极大项 均 互不等值 ; 3.极大项 : m_i表示 第 i个极大项 , 其中 i是该极大项 成假赋值 的 十进制表示 ; 4.极大项名称 : 第 i个极大项 , 称为 M_i; 5.m_i与 M_i之间的关系 : ① \lnot m_i \iff M_i② \lnot M_i \iff m_i每个命题 按照指定顺序 , 且 只出现一次 的 简单析取式 , 称为极小项 ; 极大项列出的是成假赋值 , 因为析取式只有一种情况成假 , 那就是全假 ; 3 . 主合取 ( 析取 ) 范式 ① 列出要求 主合取 ( 析取 ) 范式 的真值表 ; p , q , r三个命题真值从 0,0,0到 1,1,1, 有 2^3 = 8列 , 每一列分别对应 m_0 \sim m_8极小项 , M_0 \sim M_8极大项 ; ② 主析取范式 ( 取极小项 ) : 真值表中的真值为 1的列 取 极小项 ; 极小项 成真赋值 ; 根据极小项下标与成真赋值可以列出极小项的命题公式 ; ③ 主合取范式 ( 取极大项 ) : 真值表中的真值为 0的列 取 极大项 ; 极大项 成假赋值 ; 根据极大项下标与成假赋值可以列出极大项的命题公式 4 . 总结 : 极小项 : 合取式 , 成真赋值 , 计算时取真值表 真 列 ; 极大项 : 析取式 , 成假赋值 , 计算时取真值表 假 列 ; 参考博客 : 【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 ) 四、 推理演算推理的形式结构 前提 : A_1 , A_2 , \cdots , A_k结论 : B推理的形式结构为 : (A_1 \land A_2 \land \cdots \land A_k) \to B推理定律 : A,B是两个命题 , 如果 A \to B是永真式 , 那么 A \Rightarrow B; 1、附加律附加律 : A \Rightarrow (A \lor B)根据 推理定律 , A \to (A \lor B)蕴含式 是 永真式 ; 前提 : A结论 : A \lor BA是对的 , 那么 A \lor B也是对的 , 后者是在前者基础上附加了一个 B; 2、化简律化简律 : ( A \land B ) \Rightarrow A, ( A \land B ) \Rightarrow B根据 推理定律 , ( A \land B ) \to A, ( A \land B ) \to B蕴含式 是 永真式 ; 前提 : A \land B结论 : A或 BA \land B是对的 , 那么 A或 B也是对的 , 后者是在前者基础上进行了化简 ; 3、假言推理假言推理 : ( A \to B ) \land A \Rightarrow B根据 推理定律 , ( A \to B ) \land A \to B蕴含式 是 永真式 ; 前提 : A \to B, A结论 : B这是个典型的小三段论 ; 4、拒取式拒取式: ( A \to B ) \land \lnot B \Rightarrow \lnot A根据 推理定律 , ( A \to B ) \land \lnot B \to \lnot A蕴含式 是 永真式 ; 前提 : A \to B, \lnot B结论 : \lnot A可以理解为是反证法 ; 5、析取三段论析取三段论 : ( A \lor B ) \land \lnot A \Rightarrow B, ( A \lor B ) \land \lnot B \Rightarrow A根据 推理定律 , ( A \lor B ) \land \lnot A \to B, ( A \lor B ) \land \lnot B \to A蕴含式 是 永真式 ; 前提 : A \lor B, \lnot A结论 : B(A \lor B)是正确的 , 其中 A是错误的 , 那么 B肯定是正确的 ; (A \lor B)是正确的 , 其中 B是错误的 , 那么 A肯定是正确的 ; 警察破案常用推理方式 , 逐一排除嫌疑人 ; 6、假言三段论假言三段论 : ( A \to B ) \land ( B \to C ) \Rightarrow ( A \to C )根据 推理定律 , ( A \to B ) \land ( B \to C ) \to ( A \to C )蕴含式 是 永真式 ; 前提 : A \to B, B \to C结论 : A \to C7、等价三段论等价三段论: ( A \leftrightarrow B ) \land ( B \leftrightarrow C ) \Rightarrow ( A \leftrightarrow C )根据 推理定律 , ( ( A \leftrightarrow B ) \land ( B \leftrightarrow C ) ) \to ( A \leftrightarrow C )蕴含式 是 永真式 ; 前提 : A \leftrightarrow B, B \leftrightarrow C结论 : A \leftrightarrow C8、构造性两难等价三段论: ( A \to B ) \land ( C \to D ) \land ( A \lor C ) \Rightarrow ( B \lor D )根据 推理定律 , ( ( A \to B ) \land ( C \to D ) \land ( A \lor C ) ) \to ( ( B \lor D ) )蕴含式 是 永真式 ; 前提 : A \to B, C \to D, A \lor C结论 : B \lor D理解方式 : A是发展经济 , B是污染 C是不发展经济 , D是贫穷 A \lor B要么发展经济 , 要么不发展经济 结果是 B \lor D, 要么产生污染 , 要么忍受贫穷 参考博客 : 【数理逻辑】命题逻辑 ( 命题逻辑推理 | 推理的形式结构 | 推理定律 | 附加律 | 化简律 | 假言推理 | 拒取式 | 析取三段论 | 假言三段论 | 等价三段论 | 构造性两难 ) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |