谓词逻辑

谓词

$def:$

  • 个体词:可独立存在的客体
  • 谓词:用来说明个体的性质或个体间的关系

如: 小明是个小学生
其中,小明 就是个体词,是个小学生 就是谓词, 说明了客体的性质。
再如: $6$ 大于 $5$
其中 6 与 5 为个体词,大于 为谓词,说明了客体间的关系。


应用

例1: 写命题的谓词表达式:

<1> 小明是个小学生
设 $A(x)$:$x$ 为小学生,$a$:小明
则命题符号化为:$A(a)$

<2> $6$ 大于 $5$
设 $H(x,y)$:$x$ 大于 $y$, $a:6,b:5$
则命题符号化为:$H(a,b)$

其中:

  • $A(x)$ 为一元谓词; $H(x,y)$ 为二元谓词
  • $A(a)$ 为一元谓词常项; $H(a,b)$ 为二元谓词常项

引入量词

$def:$ 个体域:个体变动的取值范围(类似于函数的定义域)

$def:$ 量词: 表示个体之间数量关系的词

  • 全称量词:符号 “ $\forall$ “ : 任意的 $x$
  • 存在量词:符号 “ $\exists$ “ : 存在这样的 $x$

例2: 用谓词逻辑将下列命题符号化:

<1> 所有的偶数均能够被 2 整除。
设 $A(x)$: $x$ 为偶数, $B(x)$: $x$ 能被 2 整除
则命题符号化为:$\forall x(A(x)\rightarrow B(x))$

<2> 有一些人登上过月球。
设 $A(x)$: $x$ 为人, $B(x)$: $x$ 登上过月球
则命题符号化为:$\exists x (A(x)\wedge B(x))$

<3> 每列火车都比某些汽车快。
设 $F(x)$: $x$ 是火车, $G(x)$: $x$ 是汽车,$H(x,y)$: $x$ 比 $y$ 快
则命题符号化为:$\forall x(F(x)\rightarrow \exists y(G(y)\wedge H(x,y))$

<4> 没有不犯错的人
设 $A(x)$ : $x$ 为人, $B(x)$: $x$ 犯过错
则命题符号化为:$\neg \exists x(A(x)\wedge \neg B(x))$

⚠️总结:不难发现

  • 全称量词 “ $\forall$ “ 后加 $\rightarrow$
  • 存在量词 “ $\exists$ “ 后加 $\wedge$

$def:$

  • 量词的指导变元:$\forall /\exists + (x,y,z,…)$
  • 量词的辖域: 量词的作用范围 $\forall /\exists x + (D)$, $D$ 即为辖域
  • 变元由可分为:约束变元、自由变元

对于下述公式:
$$
\forall \color{red}{x}\exists \color{blue}{y} (P(\color{red}{x},\color{blue}{y})\wedge Q(\color{blue}{y},z)) \wedge \exists \color{green}{x}R(\color{green}{x},\color{yellow}{y})
$$
其中:

  • $\color{red}{x},\color{blue}{y}$ 的辖域为:$(P(\color{red}{x},\color{blue}{y}) \wedge Q(\color{blue}{y},z))$
  • $\color{green}{x}$ 的辖域为:$R(\color{green}{x},\color{yellow}{y})$
  • $\color{red}{x},\color{blue}{y},\color{green}{x}$ 为约束变元
  • $\color{yellow}{y},z$ 为自由变元

$def:$ 设 $A$ 和 $B$ 是任意两个谓词公式,如果 $A\rightarrow B$ 是重言式,称 $A$ 与 $B$ 等价,记为:$A\Leftrightarrow B$

⭐️需要熟记的等价式:

  1. 命题逻辑中的等价式的代换实例是谓词逻辑中的等值式
    如:$A\rightarrow B \Leftrightarrow \neg A\vee B$ 相当于 $P(x)\rightarrow Q(x)\Leftrightarrow \neg P(x)\vee Q(x)$; 且 $\neg (A\wedge B)\Leftrightarrow \neg A\vee \neg B$ 相当于 $\neg(\exists xP(x)\wedge \forall xQ(x))\Leftrightarrow \neg \exists xP(x)\vee \neg \forall xQ(x)$

  2. 量词否定转换
    $\neg \forall xP(x) \Leftrightarrow \exists x\neg P(x)$
    $\neg \exists xP(x) \Leftrightarrow \forall x\neg P(x)$

  3. 量词辖域的扩张和收缩、
    $\forall x(A(x)\wedge \exists y B(y))\Leftrightarrow \forall xA(x) \wedge \exists y B(y)$ 收缩

  4. 量词分配律
    $\color{red}{\forall} x(A(x)\color{red}{\wedge} B) \Leftrightarrow \forall xA(x) \wedge \forall x B(x)$
    $\color{green}{\exists} x(A(x)\color{green}{\vee} B) \Leftrightarrow \exists xA(x) \vee \exists x B(x)$
    ⚠️这里要注意的是只有当全称量词与合取符号,存在量词与析取符号两种情况时分配律才有效。

例3: 设个体域 $D = { a,b,c }$, 消去谓词公式中的量词

<1> $\exists xF(x) \rightarrow \forall yG(y)$
消去后:$F(a)\vee F(b)\vee F(c) \rightarrow G(a)\wedge G(b) \wedge G(c)$

<2> $\forall x\forall y(F(x)\rightarrow G(y))$
$\Leftrightarrow \forall x(F(x)\rightarrow \forall yG(y))$
$\Leftrightarrow \forall x(\neg F(x) \vee \forall y G(y))$
$\Leftrightarrow \forall x\neg F(x) \vee \forall yG(y)$; (x 辖域收缩)
$\Leftrightarrow \neg \exists xF(x)\vee \forall yG(y)$;(量词否定转换)
$\Leftrightarrow \exists xF(x)\rightarrow \forall yG(y)$;(等价式)
$\Leftrightarrow (F(a)\vee F(b)\vee F(c))\rightarrow (G(a)\wedge G(b)\wedge G(c))$

前束范式

$def:$ 一个谓词公式 $A$ , 若具有形式 $Q_1x_1Q_2x_2Q_3x_3 \cdots Q_nx_nM$ 其中每个$Q_i$ 为量词 $(\forall / \exists)$, $M$ 为不含量词的公式,则称 $A$ 为前束范式

例4: 求谓词公式的前束范式

<1> $\neg \forall x(F(x)\rightarrow G(x))$
$\Leftrightarrow \exists x\neg(F(x)\rightarrow G(x))$
或 $\Leftrightarrow \exists x\neg (\neg F(x)\vee G(x))$
或 $\Leftrightarrow \exists x(F(x)\wedge G(x))$

<2> $\forall xF(x)\wedge \forall y G(y)$
$\Leftrightarrow \forall x \forall y(F(x)\wedge G(y))$
$\Leftrightarrow \forall xF(x)\wedge \forall x G(x)$ 换名规则
$\forall x(F(x)\wedge G(x))$


# Math

温馨提示,此处可能会出现广告

评论


Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×

😏

📷

✍️