# 离散数学4.1-谓词基本概念

## **一、基本元件**

| **元件** | **符号** | **说明** | **例子** |
| --- | --- | --- | --- |
| **个体词** | a, b, c... | 代表具体对象（常元） | a：小明 |
| **个体变元** | x, y, z... | 代表任意对象 | x 表示论域中任一元素 |
| **谓词** | P(x), Q(x,y)... | 表示性质或关系 | P(x)：x是学生； L(x,y)：x喜欢y |
| **量词** | ∀, ∃ | 修饰个体范围 | ∀x（所有x）； ∃x（存在x） |
| **连接词** | ¬, ∧, ∨, →, ↔ | 命题逻辑五件套 | 组合谓词形成复合公式 |

其中最重要的两个：

∀：全称量词，表示所有取值，如全部、所有等

∃：存在量词，表示部分取值，如有些、部分、一些等

## **二、论域（个体域）**

**定义：** 量词所讨论的对象的全体集合。

**符号化的第一步永远是确定论域。**

*   论域不明确，公式无意义。
    
*   常见论域：所有人、所有自然数、全班同学等。
    

## **三、符号化核心法则**

#### **法则一：全称量词 ∀ 搭配蕴含 →**

#### **法则二：存在量词 ∃ 搭配合取 ∧**

> 例题1：
> 
> 句子： 所有的猫都怕老鼠。
> 
> 推导过程：
> 
> 1.  定论域： 所有动物（或所有事物）
>     
> 2.  定谓词：
>     
>     *   C(x)：x 是猫
>         
>     *   P(x)：x 怕老鼠
>         
> 3.  判量词： “所有的” → 全称量词 ∀
>     
> 4.  套模板： 全称用 →
>     
> 5.  答案：∀x (C(x) → P(x))
>     

> 例题2：
> 
> 句子： 有些学生逃课了。
> 
> 考点： ∃ 搭配 ∧
> 
> 推导过程：
> 
> 1.  定论域： 所有人
>     
> 2.  定谓词：
>     
>     *   S(x)：x 是学生
>         
>     *   T(x)：x 逃课了
>         
> 3.  判量词： “有些” → 存在量词 ∃
>     
> 4.  套模板： 存在用 ∧  
>     `∃x (S(x) ∧ T(x))`
>     

## **四、特殊句式：“只有……才……”**

这是最容易混淆的地方，要写成`B→A`

举例：**只有年满 18 岁，才有选举权。**

**分析：**

*   A：年满 18 岁
    
*   B：有选举权
    

**逻辑关系：**

*   “年满18岁”是“有选举权”的必要条件。
    
*   没满 18 岁 → 一定没选举权（¬A → ¬B）✅
    
*   有选举权 → 一定年满 18 岁（B → A）✅
    
*   但年满 18 岁 ⇏ 一定有选举权（可能有其他条件，如未被剥夺政治权利）
    

**符号化：**  
`∀x (有选举权(x) → 年满18(x))`

## 五、辖域、约束出现与自由出现

### **一、辖域**

### **定义**

**辖域** 是量词的作用范围。在一个公式中，量词后面的**最短子公式**就是该量词的辖域。

### **判断辖域的方法**

量词 `∀x` 或 `∃x` 出现后，紧跟它的那个子公式（通常用括号界定）就是它的辖域。  

**例题 1：基本辖域判断**

**公式：** `∀x P(x) → Q(x)`

∀x后的`P（x）`就是辖域

**例题 2：括号改变辖域**

**公式：** `∀x (P(x) → Q(x))`

`∀x` 后面紧跟的是括号 `(P(x) → Q(x))`，所以整个括号内的公式都是 `∀x` 的辖域。

**例题 3：嵌套量词的辖域**

**公式：** `∀x (P(x) → ∃y L(x,y))`

同理：`∀x` 的辖域：整个 `(P(x) → ∃y L(x,y))`

*   `∃y` 的辖域：`L(x,y)`
    

### 二、**约束出现与自由出现**

### **定义**

| **概念** | **定义** |
| --- | --- |
| **约束出现** | 变元 x 出现在量词 `∀x` 或 `∃x` 的辖域内，且被该量词约束 |
| **自由出现** | 变元 x 的出现没有被任何量词 ∀x 或 ∃x 所约束 |
| **指导变元** | 量词 `∀x` 或 `∃x` 中紧跟量词的那个变元（如 `∀x` 中的 x） |

### **核心判断法则**

> **一个变元的出现是否约束，看它是否在对应量词的辖域内。**

  
**例题**

指出下列各公式中的指导变元、各量词的辖域、自由出现以及约束出现的个体变项。

> （1）∀x(F(x,y)→G(x,z))
> 
> *   量词 ∀
>     
>     *   指导变元：x
>         
>     *   辖域：F(x,y)→G(x,z)
>         
> *   变元出现情况
>     
>     *   约束出现：x（共 2 次）
>         
>     *   自由出现：y、z（各 1 次）
>         

> （2）∀x(F(x)→G(y))→∃y(H(x)∧L(x,y,z))
> 
> ① 全称量词 ∀
> 
> *   指导变元：x
>     
> *   辖域：F(x)→G(y)
>     
> *   辖域内变元：x 约束出现，y 自由出现
>     
> 
> ② 存在量词 ∃
> 
> *   指导变元：y
>     
> *   辖域：H(x)∧L(x,y,z)
>     
> *   辖域内变元：y 约束出现，x,z 自由出现
>     
> 
> 整体所有变元统计
> 
> *   x：约束出现 1 次，自由出现 2 次
>     
> *   y：自由出现 1 次，约束出现 1 次
>     
> *   z：自由出现 1 次
>     

## 六、谓词公式分类定义

设 A 为一阶逻辑公式：

1.  **永真式（逻辑有效式）**
    
    若公式 A 在任意解释、任意赋值下取值均为真，则称 A 为永真式（逻辑有效式）。
    
2.  **矛盾式（永假式）**
    
    若公式 A 在任意解释、任意赋值下取值均为假，则称 A 为矛盾式（永假式）。
    
3.  **可满足式**
    
    至少存在一组解释与赋值，能使公式 A 的取值为真，则称 A 是可满足式。
    

## 七、补充注释

多个量词连用时，**量词顺序一般不可随意调换**。

例：`∀x∃y`和`∃y∀x` 含义不等价，不能互换。

例题：

设论域D={a,b}，与公式∃xA(x)等价的命题公式是（）

解题思路：

量词消去规则（有限论域）

`∃x`对应逻辑 “或”，所以`∃xA(x)⟺A(a)∨A(b)`

答案为`A(a)∨A(b)`

所以绑定关系：

`∃x`和`∨`

`∀x`和`∧`