前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >谓词逻辑

谓词逻辑

作者头像
yhlin
发布2023-02-27 17:01:42
1.1K0
发布2023-02-27 17:01:42
举报
文章被收录于专栏:yhlin's blog

谓词

def:

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

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

应用

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

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

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

其中: * A(x) 为一元谓词;H(x,y) 为二元谓词 * A(a) 为一元谓词常项;H(a,b) 为二元谓词常项

## 引入量词 >

> \forall" : 任意的 x > * 存在量词:符号 "\exists" : 存在这样的 x

** 例 2:** 用谓词逻辑将下列命题符号化: <1> 所有的偶数均能够被 2 整除。 设 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): xy 快 则命题符号化为:\forall x(F(x)\rightarrow \exists y(G(y)\wedge H(x,y))

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

> ⚠️总结:不难发现 > * 全称量词 "\rightarrow > * 存在量词 "\exists" 后加 \wedge

> \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})

其中: *

> AB 是任意两个谓词公式,如果 A\rightarrow B 是重言式,称 AB 等价,记为: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> \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))

### 前束范式

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

** 例 4:** 求谓词公式的前束范式 <1> \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> \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))

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-01-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 谓词
  • 应用
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档