文章目录

一、命题逻辑基本概念
二、等值演算
三、主合取 ( 析取 ) 范式
四、推理演算
- 1、附加律
- 2、化简律
- 3、假言推理
- 4、拒取式
- 5、析取三段论
- 6、假言三段论
- 7、等价三段论
- 8、构造性两难

参考博客 :

【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )
【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表可满足式矛盾式重言式 )
【数理逻辑】命题逻辑 ( 等值演算 | 幂等律 | 交换律 | 结合律 | 分配律 | 德摩根律 | 吸收率 | 零律 | 同一律 | 排中律 | 矛盾律 | 双重否定率 | 蕴涵等值式 … )
【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 )
【数理逻辑】命题逻辑 ( 命题逻辑推理 | 推理的形式结构 | 推理定律 | 附加律 | 化简律 | 假言推理 | 拒取式 | 析取三段论 | 假言三段论 | 等价三段论 | 构造性两难 )
【数理逻辑】命题逻辑 ( 命题逻辑推理正确性判定 | 形式结构是永真式 - 等值演算 | 从前提推演结论 - 逻辑推理 )

一、命题逻辑基本概念

命题逻辑基本概念

命题逻辑联结词
真值表
命题逻辑类型 : 可满足式 , 永真式 , 永假式 ;

1 . 命题公式组成 :

① 单个命题变元 / 命题常元是命题公式 ;

② 如果

$A$ 是命题公式 , 则

(

)

(\lnot A)

$(\neg A)$ 也是命题公式 ;

③ 如果

A,B

$A, B$ 是命题公式 , 则

(

∧

)

(

∨

)

(

→

)

(

↔

)

(A \land B) , (A \lor B), (A \to B), (A \leftrightarrow B)

$(A \land B), (A \lor B), (A \to B), (A \leftrightarrow B)$ 也是命题公式 ;

④ 有限次应用 ① ② ③ 形成的符号串是命题公式 ; ( 无限次不行 )

2 . 联结词 :

原子命题 :

p , q , r

$p, q, r$ 表示原子命题 , 又称为简单命题 ;

真 :
假 :

否定联结词 : $\lnot$
$\neg$
合取联结词 : $\land$
$\land$ ,

p

∧

q

p \land q

$p \land q$ ,

p

q

pq

$p q$ 同真, 结果才为真 , 其余情况为假 ;
析取联结词 : $\lor$
$\lor$ ,

p

∨

q

p \lor q

$p \lor q$ ,

p

q

pq

$p q$ 同假, 结果才为假 , 其余情况为真 ;
蕴涵联结词 : $\to$
$\to$ ,

p

→

q

p \to q

$p \to q$ ,

p

p

$p$ 真

q

q

$q$ 假, 结果才为假 , 其余情况为真 ;
等价联结词 : $\leftrightarrow$
$\leftrightarrow$ ,

p

↔

q

p \leftrightarrow q

$p \leftrightarrow q$ ,

p

q

pq

$p q$ 真值相同时为真 , 表示等价成立 ,

p

q

pq

$p q$ 真值相反时为假 , 等价不成立 ;

联结词优先级 :

“

\lnot

$\neg$ ” 大于 “

∧

∨

\land , \lor

$\land, \lor$ ” 大于 “

→

↔

\to, \leftrightarrow

$\to, \leftrightarrow$ ”

∧

∨

\land , \lor

$\land, \lor$ 优先级相同 ;

→

↔

\to, \leftrightarrow

$\to, \leftrightarrow$ 优先级相同 ;

3 . 命题逻辑类型 :

可满足式 : 真值表中 , 至少有一个结果为真 , 可以都为真 ;

矛盾式 ( 永假式 ) : 所有的真值都为假 ;

可满足式与矛盾式 , 是二选一的 , 复合命题要么是可满足式 , 要么是矛盾式 ;

重言式 ( 永真式 ) 是可满足式的一种 ;

4 . 简单命题形式化 :

参考 : 复合命题与命题符号化

定义命题 : 使用

p,q

$p, q$ 代表真假必居其一的陈述句 ;

使用联结词 : 然后使用联结词联结这些

p,q

$p, q$ 命题 ;

参考博客 :

【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )
【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表可满足式矛盾式重言式 )

二、等值演算

等值式概念 :

A , B

$A, B$ 是两个命题公式 , 如果

↔

A \leftrightarrow B

$A \leftrightarrow B$ 是永真式 , 那么

A,B

$A, B$ 两个命题公式是等值的 , 记做

⇔

A \Leftrightarrow B

$A \Leftrightarrow B$ ;

等值演算置换规则 :

$A$ 和

$B$ 两个命题公式 , 可以互相代替 , 凡是出现

$A$ 的地方都可以替换成

$B$ , 凡是出现

$B$ 的地方都可以替换成

$A$ ;

基本运算规律 :

1. 幂等律 : $\Leftrightarrow A \lor A A⇔A∨A , A ⇔ A ∧ A A \Leftrightarrow A \land A$
$A \Leftrightarrow A \land A$
2. 交换律 : $\lor B \Leftrightarrow B \lor A A∨B⇔B∨A , A ∧ B ⇔ B ∧ A A \land B \Leftrightarrow B \land A$
$A \land B \Leftrightarrow B \land A$
3. 结合律 : $\lor B ) \lor C \Leftrightarrow A \lor (B \lor C) (A∨B)∨C⇔A∨(B∨C) , ( A ∧ B ) ∧ C ⇔ A ∧ ( B ∧ C ) (A \land B ) \land C \Leftrightarrow A \land (B \land C)$
$(A \land B) \land C \Leftrightarrow A \land (B \land C)$
4. 分配律 : $\lor (B \land C) \Leftrightarrow ( A \lor B ) \land ( A \lor C ) A∨(B∧C)⇔(A∨B)∧(A∨C) , A ∧ ( B ∨ C ) ⇔ ( A ∧ B ) ∨ ( A ∧ C ) A \land (B \lor C) \Leftrightarrow ( A \land B ) \lor ( A \land 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 ¬(A∨B)⇔¬A∧¬B , ¬ ( A ∧ B ) ⇔ ¬ A ∨ ¬ B \lnot ( A \land B ) \Leftrightarrow \lnot A \lor \lnot B$
$\neg (A \land B) \Leftrightarrow \neg A \lor \neg B$
- 有了与 ( $\land ∧ ) 非 ( ¬ \lnot ¬ ) , 就可以表示或 ( ∨ \lor ∨ )$
- 有了或 ( $\lor ∨ ) 非 ( ¬ \lnot ¬ ) , 就可以表示与 ( ∧ \land ∧ )$
6. 吸收率 :
- 前者将后者吸收了 : $\lor ( A \land B ) \Leftrightarrow A$
  $A \lor (A \land B) \Leftrightarrow A$
- 后者将前者吸收了 : $\land ( A \lor B ) \Leftrightarrow A$
  $A \land (A \lor B) \Leftrightarrow A$ ;

0

,

1

0 , 1

$0, 1$ 相关的运算律 :

7. 零律 : $\lor 1 \Leftrightarrow 1 A∨1⇔1 , A ∧ 0 ⇔ 0 A \land 0 \Leftrightarrow 0$
$A \land 0 \Leftrightarrow 0$
- 与零元进行运算结果是零元 ;
8. 同一律 : $\lor 0 \Leftrightarrow A A∨0⇔A , A ∧ 1 ⇔ A A \land 1 \Leftrightarrow A$
$A \land 1 \Leftrightarrow A$
- 与单位元进行运算结果是其本身
9. 排中律 : $\lor \lnot A \Leftrightarrow 1$
$A \lor \neg A \Leftrightarrow 1$
10. 矛盾律 : $\land \lnot A \Leftrightarrow 0$
$A \land \neg A \Leftrightarrow 0$

对偶原理适用于上述运算律 , 将两边的

∧

,

∨

\land , \lor

$\land, \lor$ 互换 , 同时

0

,

1

0 ,1

$0, 1$ 互换 , 等价仍然成立 ;

等价蕴含运算规律 :

11. 双重否定率 : $\lnot \lnot A \Leftrightarrow A$
$\neg \neg A \Leftrightarrow A$
12. 蕴涵等值式 : $\to B \Leftrightarrow \lnot A \lor B$
$A \to B \Leftrightarrow \neg A \lor B$
- 替换蕴含联结词 : 蕴含联结词 $\to → 不是必要的 , 使用 ¬ , ∨ \lnot , \lor ¬,∨ 两个联结词可以替换蕴含联结词 ;$
13. 等价等值式 : $\leftrightarrow B \Leftrightarrow ( A \to B ) \lor ( B \to A )$
$A \leftrightarrow B \Leftrightarrow (A \to B) \lor (B \to A)$
- 双箭头 ( 等价联结词 ) 可以理解成重分必要条件
- $\to B A→B ( 蕴含联结词 ) 理解成 A A A 是 B B B 的充分条件 , B B B 是 A A A 的必要条件$
- $\to A B→A ( 蕴含联结词 ) 理解成 B B B 是 A A A 的充分条件 , A A A 是 B B B 的必要条件$
- 替换等价联结词 : 等价联结词 $\leftrightarrow ↔ 不是必要的 , 使用 → , ∨ \to , \lor →,∨ 两个联结词可以替换等价联结词 ;$
14. 等价否定等值式 : $\leftrightarrow B \Leftrightarrow \lnot A \leftrightarrow \lnot B$
$A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B$
15. 假言易位 ( 逆否命题 ) : $\to B \Leftrightarrow \lnot B \to \lnot A$
$A \to B \Leftrightarrow \neg B \to \neg A$
16. 归谬论 ( 反证法 ) : $\to B ) \land ( A \to \lnot B ) \Leftrightarrow \lnot A$
$(A \to B) \land (A \to \neg B) \Leftrightarrow \neg A$
- 这是反证法的原理 , 由 $\lnot B ¬B , B B B 和 ¬ B \lnot B ¬B 是矛盾的 , 则 A A A 是错的 , ¬ A \lnot A ¬A 是对的 ;$

参考博客 : 【数理逻辑】命题逻辑 ( 等值演算 | 幂等律 | 交换律 | 结合律 | 分配律 | 德摩根律 | 吸收率 | 零律 | 同一律 | 排中律 | 矛盾律 | 双重否定率 | 蕴涵等值式 … )

三、主合取 ( 析取 ) 范式

1 . 极小项

极小项 : 极小项是一种简单合取式 ;

1.前提 ( 简单合取式 ) : 含有
$n$ 个命题变项的简单合取式 ;
2.命题变项出现次数 : 每个命题变项均以文字的形式在其中出现 , 且仅出现一次 ;
3.命题变项出现位置 : 第 $\leq i \leq n 1≤i≤n ) 个文字出现在左起第 i i$
$i$ 个位置 ;
- $n$ 是指命题变项个数 ;
4.极小项总结 : 满足上述三个条件的简单合取式 , 称为极小项 ;
5. $m_i mi 与 M i M_i$
$M_{i}$ 之间的关系 : ①

¬

m

i

⟺

M

i

\lnot m_i \iff M_i

$\neg m_{i} ⟺ M_{i}$ ②

¬

M

i

⟺

m

i

\lnot M_i \iff m_i

$\neg M_{i} ⟺ m_{i}$

每个命题按照指定顺序 , 且只出现一次的简单合取式 , 称为极小项 ;

极小项列出的是成真赋值 , 因为合取式只有一种情况成真 , 那就是全真 ;

2 . 极大项

关于极大项的说明 :

1.极大项个数 : $2^n$
$2^{n}$ 个极大项 ;
2.互不等值 : $2^n$
$2^{n}$ 个极大项均互不等值 ;
3.极大项 : $m_i mi 表示第 i i i 个极大项 , 其中 i i$
$i$ 是该极大项成假赋值的十进制表示 ;
4.极大项名称 : 第 $M_i$
$M_{i}$ ;
5. $m_i mi 与 M i M_i$
$M_{i}$ 之间的关系 : ①

¬

m

i

⟺

M

i

\lnot m_i \iff M_i

$\neg m_{i} ⟺ M_{i}$ ②

¬

M

i

⟺

m

i

\lnot M_i \iff m_i

$\neg M_{i} ⟺ m_{i}$

每个命题按照指定顺序 , 且只出现一次的简单析取式 , 称为极小项 ;

极大项列出的是成假赋值 , 因为析取式只有一种情况成假 , 那就是全假 ;

3 . 主合取 ( 析取 ) 范式

① 列出要求主合取 ( 析取 ) 范式的真值表 ;

p , q , r

$p, q, r$ 三个命题真值从

0,0,0

$0, 0, 0$ 到

1,1,1

$1, 1, 1$ , 有

2^3 = 8

$2^{3} = 8$ 列 , 每一列分别对应

∼

m_0 \sim m_8

$m_{0} \sim m_{8}$ 极小项 ,

∼

M_0 \sim M_8

$M_{0} \sim M_{8}$ 极大项 ;

② 主析取范式 ( 取极小项 ) : 真值表中的真值为

$1$ 的列取极小项 ; 极小项成真赋值 ; 根据极小项下标与成真赋值可以列出极小项的命题公式 ;

③ 主合取范式 ( 取极大项 ) : 真值表中的真值为

$0$ 的列取极大项 ; 极大项成假赋值 ; 根据极大项下标与成假赋值可以列出极大项的命题公式

4 . 总结 :

极小项 : 合取式 , 成真赋值 , 计算时取真值表真列 ;

极大项 : 析取式 , 成假赋值 , 计算时取真值表假列 ;

四、推理演算

推理的形式结构

前提 :

⋯

A_1 , A_2 , \cdots , A_k

$A_{1}, A_{2}, \dots, A_{k}$

结论 :

$B$

推理的形式结构为 :

(

∧

⋯

∧

)

→

(A_1 \land A_2 \land \cdots \land A_k) \to B

$(A_{1} \land A_{2} \land \dots \land A_{k}) \to B$

推理定律 :

A,B

$A, B$ 是两个命题 , 如果

→

A \to B

$A \to B$ 是永真式 , 那么

⇒

A \Rightarrow B

$A \Rightarrow B$ ;

1、附加律

附加律 :

⇒

(

∨

)

A \Rightarrow (A \lor B)

$A \Rightarrow (A \lor B)$

根据 推理定律 ,

→

(

∨

)

A \to (A \lor B)

$A \to (A \lor B)$ 蕴含式是永真式 ;

前提 :

$A$

结论 :

∨

A \lor B

$A \lor B$

$A$ 是对的 , 那么

∨

A \lor B

$A \lor B$ 也是对的 , 后者是在前者基础上附加了一个

$B$ ;

2、化简律

化简律 :

(

∧

)

⇒

( A \land B ) \Rightarrow A

$(A \land B) \Rightarrow A$ ,

(

∧

)

⇒

( A \land B ) \Rightarrow B

$(A \land B) \Rightarrow B$

根据 推理定律 ,

(

∧

)

→

( A \land B ) \to A

$(A \land B) \to A$ ,

(

∧

)

→

( A \land B ) \to B

$(A \land B) \to B$ 蕴含式是永真式 ;

前提 :

∧

A \land B

$A \land B$

结论 :

$A$ 或

$B$

∧

A \land B

$A \land B$ 是对的 , 那么

$A$ 或

$B$ 也是对的 , 后者是在前者基础上进行了化简 ;

3、假言推理

假言推理 :

(

→

)

∧

⇒

( A \to B ) \land A \Rightarrow B

$(A \to B) \land A \Rightarrow B$

根据 推理定律 ,

(

→

)

∧

→

( A \to B ) \land A \to B

$(A \to B) \land A \to B$ 蕴含式是永真式 ;

前提 :

→

A \to B

$A \to B$ ,

$A$

结论 :

$B$

这是个典型的小三段论 ;

4、拒取式

拒取式:

(

→

)

∧

⇒

( A \to B ) \land \lnot B \Rightarrow \lnot A

$(A \to B) \land \neg B \Rightarrow \neg A$

根据 推理定律 ,

(

→

)

∧

→

( A \to B ) \land \lnot B \to \lnot A

$(A \to B) \land \neg B \to \neg A$ 蕴含式是永真式 ;

前提 :

→

A \to B

$A \to B$ ,

\lnot B

$\neg B$

结论 :

\lnot A

$\neg A$

可以理解为是反证法 ;

5、析取三段论

析取三段论 :

(

∨

)

∧

⇒

( A \lor B ) \land \lnot A \Rightarrow B

$(A \lor B) \land \neg A \Rightarrow B$ ,

(

∨

)

∧

⇒

( A \lor B ) \land \lnot B \Rightarrow A

$(A \lor B) \land \neg B \Rightarrow A$

根据 推理定律 ,

(

∨

)

∧

→

( A \lor B ) \land \lnot A \to B

$(A \lor B) \land \neg A \to B$ ,

(

∨

)

∧

→

( A \lor B ) \land \lnot B \to A

$(A \lor B) \land \neg B \to A$ 蕴含式是永真式 ;

前提 :

∨

A \lor B

$A \lor B$ ,

\lnot A

$\neg A$

结论 :

$B$

(

∨

)

(A \lor B)

$(A \lor B)$ 是正确的 , 其中

$A$ 是错误的 , 那么

$B$ 肯定是正确的 ;

(

∨

)

(A \lor 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) \Rightarrow (A \to C)$

根据 推理定律 ,

(

→

)

∧

(

→

)

→

(

→

)

( A \to B ) \land ( B \to C ) \to ( A \to C )

$(A \to B) \land (B \to C) \to (A \to C)$ 蕴含式是永真式 ;

前提 :

→

A \to B

$A \to B$ ,

→

B \to C

$B \to C$

结论 :

→

A \to C

$A \to C$

7、等价三段论

等价三段论:

(

↔

)

∧

(

↔

)

⇒

(

↔

)

( A \leftrightarrow B ) \land ( B \leftrightarrow C ) \Rightarrow ( A \leftrightarrow C )

$(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) \land (B \leftrightarrow C)) \to (A \leftrightarrow C)$ 蕴含式是永真式 ;

前提 :

↔

A \leftrightarrow B

$A \leftrightarrow B$ ,

↔

B \leftrightarrow C

$B \leftrightarrow C$

结论 :

↔

A \leftrightarrow C

$A \leftrightarrow C$

8、构造性两难

等价三段论:

(

→

)

∧

(

→

)

∧

(

∨

)

⇒

(

∨

)

( 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) \Rightarrow (B \lor D)$

根据 推理定律 ,

(

→

)

∧

(

→

)

∧

(

∨

)

→

(

∨

)

( ( A \to B ) \land ( C \to D ) \land ( A \lor C ) ) \to ( ( B \lor D ) )

$((A \to B) \land (C \to D) \land (A \lor C)) \to ((B \lor D))$ 蕴含式是永真式 ;

前提 :

→

A \to B

$A \to B$ ,

→

C \to D

$C \to D$ ,

∨

A \lor C

$A \lor C$

结论 :

∨

B \lor D

$B \lor D$

理解方式 :

$A$ 是发展经济 ,

$B$ 是污染

$C$ 是不发展经济 ,

$D$ 是贫穷

∨

A \lor B

$A \lor B$ 要么发展经济 , 要么不发展经济
结果是

∨

B \lor D

$B \lor D$ , 要么产生污染 , 要么忍受贫穷

【数理逻辑】命题逻辑的等值演算与推理演算 ( 命题逻辑 | 等值演算 | 主合取 ( 析取 ) 范式 | 推理演算 ) ★★

文章目录

一、命题逻辑基本概念

二、等值演算

三、主合取 ( 析取 ) 范式

四、推理演算

1、附加律

2、化简律

3、假言推理

4、拒取式

5、析取三段论

6、假言三段论

7、等价三段论

8、构造性两难

相关推荐

一个分享Java & Python知识的社区

文章目录

一、 命题逻辑基本概念

二、 等值演算

三、 主合取 ( 析取 ) 范式

四、 推理演算

1、附加律

2、化简律

3、假言推理

4、拒取式

5、析取三段论

6、假言三段论

7、等价三段论

8、构造性两难

相关推荐

一个分享Java & Python知识的社区

一、命题逻辑基本概念

二、等值演算

三、主合取 ( 析取 ) 范式

四、推理演算