离散数学2.3-联结词的完备集

定义：S是一个联结词集合，若任一个命题公式都可以由s中的联结词表示出来命题公式与之等价，则称S是一个联结词完备集。

也就是说一个连接词集合，能表达出所有真值函数，称为完备集

以下是完备集：

S1​={¬,∧,∨} —— 否定、合取、析取

S2​={¬,∧,∨,→} —— 否定、合取、析取、蕴涵

S3​={¬,∧,∨,→,↔} —— 否定、合取、析取、蕴涵、等价

S4​={¬,∧} —— 否定、合取

S5​={¬,∨} —— 否定、析取

S6​={¬,→} —— 否定、蕴涵

S7​={↑} —— 与非（Sheffer 竖线）

S8​={↓} —— 或非（Peirce 箭头）

介绍一下↑（与非）和↓（或非）

一、与非 ↑

公式：p↑q  ⟺¬(p∧q)

tips：记忆技巧，中间连接符方向和箭头一致

真值规则：只有 p、q 全为 1 时，结果才是 0；其余情况全为 1

只用 ↑ 表示全部基础联结词（完备集）

否定：¬p  ⟺p↑p

推导：p↑p⟺¬(p∧p)⟺¬p

合取：p∧q  ⟺(p↑q)↑(p↑q)

推导：（定义） ：p↑q  ⟺¬(p∧q)

两边同时取否定 ：¬(p↑q)⟺¬¬(p∧q)⟺p∧q

已证  ：¬A  ⟺A↑A，令 A=p↑q，得

p∧q⟺(p↑q)↑(p↑q)

析取：p∨q  ⟺(p↑p)↑(q↑q)

推导：

德摩根律把 ∨ 转成 ∧ 和 ¬：p ∨ q ⇔ ¬(¬p ∧ ¬q)

右边恰好是 ↑ 的形式：¬(¬p ∧ ¬q) ⇔ ¬p ↑ ¬q

已知¬A ⇔ A ↑ A,带入得(p↑p)↑(q↑q)

蕴涵：p→q⟺p↑(q↑q)

蕴含等值式：p→q  ⟺¬p∨q

德摩根律：¬p∨q  ⟺¬(p∧¬q)

右边符合 ↑ 的形式：¬(p∧¬q)  ⟺p↑¬q

已证 ¬q  ⟺  q↑q¬q⟺q↑q，代入：p→q  ⟺p↑(q↑q)

二、或非 ↓

公式：p↓q  ⟺¬(p∨q)

tips：记忆技巧，中间连接符方向和箭头一致

真值规则：只有 p、q 全为 0 时，结果才是 1；其余情况全为 0

只用 ↓ 表示全部基础联结词（完备集）

否定：¬p⟺ p↓p

推导： p↓p⟺¬(p∨p)⟺¬p

合取：p∧q  ⟺(p↓p)↓(q↓q)

由德摩根律：

p∧q  ⟺¬(¬p∨¬q)

右边正是 ↓ 的形式：

¬(¬p∨¬q)  ¬p↓¬q

已证 ¬A  ⟺A↓A，代入 ¬p¬p 和 ¬q¬q：

p∧q ⟺(p↓p)↓(q↓q)

析取：p∨q  ⟺(p↓q)↓(p↓q)

p∨q⟺¬(p↓q)

再用否定式 ¬A ⟺A↓A，令 A=p↓q：

p∨q  ⟺(p↓q)↓(p↓q)

蕴涵：p → q ⇔ p ↑ (q ↑ q)

p→q  ⟺¬p∨q

用析取的 ↓ 表示（令 A=¬p,B=q）：

¬p∨q  ⟺(¬p↓q)↓(¬p↓q)

代入 ¬p⟺p↓p：

p→q  ⟺((p↓p)↓q)↓((p↓p)↓q)