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

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

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

### 以下是完备集：

*S*1​={¬,∧,∨} —— 否定、合取、析取

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

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

*S*4​={¬,∧} —— 否定、合取

*S*5​={¬,∨} —— 否定、析取

*S*6​={¬,→} —— 否定、蕴涵

*S*7​={↑} —— 与非（Sheffer 竖线）

*S*8​={↓} —— 或非（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)`