文章目录
参考博客 :
一、 命题逻辑基本概念
命题逻辑基本概念
- 命题逻辑联结词
- 真值表
- 命题逻辑类型 : 可满足式 , 永真式 , 永假式 ;
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 ;
基本运算规律 :
A \Leftrightarrow A \lor A ,
A \Leftrightarrow A \land AA \lor B \Leftrightarrow B \lor A ,
A \land B \Leftrightarrow B \land A(A \lor B ) \lor C \Leftrightarrow A \lor (B \lor C) ,
(A \land B ) \land C \Leftrightarrow A \land (B \land C)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 )新运算规律 :
\lnot ( A \lor B ) \Leftrightarrow \lnot A \land \lnot B ,
\lnot ( A \land B ) \Leftrightarrow \lnot A \lor \lnot B- 6. 吸收率 : A \lor ( A \land B ) \Leftrightarrow AA \land ( A \lor B ) \Leftrightarrow A
;
0 , 1 相关的运算律 :
A \lor 1 \Leftrightarrow 1 ,
A \land 0 \Leftrightarrow 0A \lor 0 \Leftrightarrow A ,
A \land 1 \Leftrightarrow AA \lor \lnot A \Leftrightarrow 1A \land \lnot A \Leftrightarrow 0对偶原理适用于上述运算律 , 将两边的
\land , \lor 互换 , 同时
0 ,1 互换 , 等价仍然成立 ;
等价蕴含运算规律 :
\lnot \lnot A \Leftrightarrow AA \to B \Leftrightarrow \lnot A \lor BA \leftrightarrow B \Leftrightarrow ( A \to B ) \lor ( B \to A )A \leftrightarrow B \Leftrightarrow \lnot A \leftrightarrow \lnot BA \to B \Leftrightarrow \lnot B \to \lnot A( A \to B ) \land ( A \to \lnot B ) \Leftrightarrow \lnot A参考博客 : 【数理逻辑】命题逻辑 ( 等值演算 | 幂等律 | 交换律 | 结合律 | 分配律 | 德摩根律 | 吸收率 | 零律 | 同一律 | 排中律 | 矛盾律 | 双重否定率 | 蕴涵等值式 … )
三、 主合取 ( 析取 ) 范式
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 . 极大项
关于 极大项 的 说明 :
n 个 命题变元 会 产生
2^n 个 极大项 ;
2^n 个极大项 均 互不等值 ;
m_i 表示 第
i 个极大项 , 其中
i 是该极大项 成假赋值 的 十进制表示 ;
i 个极大项 , 称为
M_i ;
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 , 要么产生污染 , 要么忍受贫穷
参考博客 : 【数理逻辑】命题逻辑 ( 命题逻辑推理 | 推理的形式结构 | 推理定律 | 附加律 | 化简律 | 假言推理 | 拒取式 | 析取三段论 | 假言三段论 | 等价三段论 | 构造性两难 )