Post

谓词逻辑

Posted
By lreverse
11 min read
谓词逻辑

将原子命题进一步细化，进而表示个体与总体的内在联系和数量关系

基本概念

  • 个体：研究领域中可以独立存在的具体或抽象的概念
  • 谓词：刻画个体的性质及事物关系的词
    • 作用在个体，产生一个命题
    • 一元谓词：包含一个参数的谓词，表示一元关系 $P(x)$
    • 多元谓词：包含多个参数的谓词，表示多元关系 $P(x_1,x_2,…,x_n)$
  • 函词：对个体进行某种交换
    • 作用在个体，产生另一个个体
    • $f(x)$
  • 函数：在个体域上定义，只能作用在个体上
  • 量词
    • 全称量词 $\forall$
      • $\forall x$ 表示定义域中的所有个体
      • $\forall x P(x)$ 表示定义域中的所有个体具有性质P
    • 存在量词 $\exists$
      • $\exists x$ 表示定义域中存在一个或若干个个体
      • $\exists x P(x)$ 表示定义域中存在一个个体或若干个体具有性质P
    • 量词否定等值式
      • $\neg(\forall x P(x)) \equiv \exists x \neg P(x)$
      • $\neg(\exists x P(x)) \equiv \forall x \neg P(x)$
  • 辖域：紧接于量词之后被量词作用的谓词公式
  • 指导变元：量词后面的变元
  • 约束变元：在一个量词的辖域中与该量词的指导变元相同的变元
  • 自由变元：不受全称量词或存在量词约束的变量符号

项

  • 是描述对象的逻辑表达式，被递归定义：
  1. 个体常项和个体变项是项
  2. 若$f(x_1, x_2, ···, x_n)$是$n$元函数符号，$t_1, t_2, ···, t_n$是项，则$f(t_1, t_2, ···, t_n)$是项
  3. 有限次数地使用上述规则产生的符号串是项

原子公式

  • 若$P(x_1, x_2, ···, x_n)$是$n$元谓词，$t_1, t_2, ···, t_n$是项，则称$P(t_1, t_2, ···, t_n)$是原子谓词公式，简称原子公式

合式公式

  1. 命题常项、命题变项、原子公式是合式公式
  2. 若$A、B$是合式公式，则$\neg A, A\wedge B, A\vee B, A\rightarrow B, B\rightarrow A, A\leftrightarrow B$都是合式公式
  3. 若$A$是合式公式，$x$是个体变项，则$(\exists x) A(x)$和$(\forall x) A(x)$也是合式公式
  4. 有限次数地使用上述规则构成的表达式是合式公式

examples：

  1. Tom不仅喜欢踢足球，还喜欢打篮球：$Like(Tom, Football)\wedge Like(Tom, Basketball)$
  2. Tom的所有同学都喜欢他：$(\forall x)(Classmate(Tom, x)\rightarrow Like(x, Tom))$
  3. 一个人是华侨，当且仅当他在国外定居并且具有中国国籍：$(\forall x)(OverseasChinese(x)\leftrightarrow (Overseas(x)\wedge Chinese(x)))$

改名规则

  • 换名规则
    • 将某量词辖域中出现的某个约束变元以及对应的指导变元更改为本辖域中没有出现过的个体变元符号，公式其它部分不变，谓词公式的等价性不变
    • $\forall x P(x,y) \equiv \forall u P(u,y)$
  • 代替规则
    • 将某量词辖域中出现的某个自由变元的所有出现用本辖域中未曾出现过的某个个体变元符号代替，谓词公式的等价性不变
    • $\forall x P(x,y) \equiv \forall x P(x,z)$

谓词公式的解释

  • 前提：Ｄ是谓词公式P的非空个体域
    • 为每个n元谓词指派一个从$D^n$到${F,T}$的映射，则称这些指派为P在D上的一个解释
  • 谓词公式的永真性
    • 如果谓词公式P对非空个体域D上的任一解释都取得真值T，则称P在D上是永真的
    • 如果P在任何非空个体域上都是永真的，则称P是永真
  • 谓词公式的可满足性
    • 对于谓词公式P，如果至少存在D上的一个解释，使公式P在此解释下的真值为T，则称公式P在D上是可满足的
  • 谓词公式的永假性
    • 如果谓词公式P对非空个体域D上的任一解释都取真值F，则称P在D上是永假的
    • 如果P在任何非空个体域上均是永假的，则称P永假
  • 谓词公式的等价性
    • 设P与Q是D上的两个谓词公式，若对D上的任意解释，P与Q都有相同的真值，则称P与Q在D上是等价的
    • 如果D是任意非空个体域，则称P与Q是等价的，记作$P\Leftrightarrow Q$
  • 永真蕴含式
    • 对谓词公式P和Q，如果$P\rightarrow Q$永真，则称P 永真蕴含Q，且称Q为P 的逻辑结论，P为Q的前提，记作$P\Rightarrow Q$

常见的等价式

  • 双重否定律
    • $\neg\neg P \Leftrightarrow P$
  • 交换律
    • $P\vee Q \Leftrightarrow Q\vee P$
    • $P\wedge Q \Leftrightarrow Q\wedge P$
  • 结合律
    • $(P\vee Q)\vee R \Leftrightarrow P\vee (Q\vee R)$
    • $(P\wedge Q)\wedge R \Leftrightarrow P\wedge (Q\wedge R)$
  • 分配律
    • $P\vee (Q\wedge R) \Leftrightarrow (P\vee Q)\wedge (P\vee R)$
    • $P\wedge (Q\vee R) \Leftrightarrow (P\wedge Q)\vee (P\wedge R)$
  • 狄摩根定律
    • $\neg(P\vee Q) \Leftrightarrow \neg P \wedge \neg Q$
    • $\neg(P\wedge Q) \Leftrightarrow \neg P \vee \neg Q$
  • 吸收律
    • $P\vee (P\wedge Q) \Leftrightarrow P$
    • $P \wedge (P\vee Q) \Leftrightarrow P$
  • 补余律
    • $P\vee \neg P \Leftrightarrow T$
    • $P\wedge \neg P \Leftrightarrow F$
  • 连词化归律
    • $P\rightarrow Q \Leftrightarrow \neg P \vee Q$
    • $P \leftrightarrow Q \Leftrightarrow (P\rightarrow Q)\wedge (Q\rightarrow P)$
  • 量词转换律
    • $\neg (\exists x) P \Leftrightarrow (\forall x)(\neg P)$
    • $\neg (\forall x)P \Leftrightarrow (\exists x)(\neg P)$
  • 量词分配律
    • $(\forall x)(P\wedge Q) \Leftrightarrow (\forall x)P \wedge (\forall x)Q$
    • $(\exists x)(P\vee Q) \Leftrightarrow (\exists x)P \vee (\exists x)Q$

常见的永真蕴含式

  • 化简式
    • $P\wedge Q \Rightarrow P$
    • $P \wedge Q \Rightarrow Q$
  • 附加式
    • $P \Rightarrow P \vee Q$
    • $Q \Rightarrow P \vee Q$
  • 析取三段论
    • $\neg P, P\vee Q \Rightarrow Q$
  • 假言推理
    • $P, P\rightarrow Q \Rightarrow Q$
  • 拒取式
    • $\neg Q, P\rightarrow Q \Rightarrow \neg P$
  • 假言三段论
    • $P\rightarrow Q, Q\rightarrow R \Rightarrow P\rightarrow R$
  • 二难推理
    • $P\vee Q, P\rightarrow R, Q\rightarrow R \Rightarrow R$
  • 全称固化
    • $(\forall x)P(x) \Rightarrow P(y)$
    • $y$是个体域中的任一个体，依此可消去谓词公式中的全称量词
  • 存在固化
    • $(\exists x)P(x) \Rightarrow P(y)$
    • $y$是个体域中某一可以使$P(y)$为真的个体，依此可消去谓词公式中的存在量词

置换与合一

置换

在不同谓词公式中，往往会出现谓词名相同但其个体不同的情况，此时推理过程是不能直接进行匹配的，需要先进行置换

  • 置换是形如$\{t_1/x_1, t_2/x_2, …, t_n/x_n\}$的有限集合
    • 其中$t_1, t_2,…, t_n$是项，$x_1, x_2, …, x_n$是互不相同的变元
    • $t_i/x_i$表示用$t_i$替换$x_i$，并且$t_i$与$x_i$不能相同，$x_i$不能循环地出现在另一个$t_i$中
  • 设$\theta = \{t_1/x_1, t_2/x_2, …, t_n/x_n\}$是一个置换，F是一个谓词公式，把公式F中出现的所有$x_i$替换成$t_i$，得到一个新的公式G
    • G为F在置换$\theta$下的例示，记作$G=F\theta$
  • 置换的合成

合一

寻找相对变量的置换，使两个或多个谓词公式一致

  • 若有公式集$F=\{F_1, F_2,…,F_n\}$，若存在一个置换$\theta$
    • 使$F_1\theta=F_2\theta=…=F_n\theta$
    • 则称$\theta$是$F$的一个合一，称$F_1, F_2, …, F_n$是可合一的
    • 一般情况下，一个公式集的合一不是唯一的
  • 最一般合一（mgu）
    • 设$\sigma$是谓词公式集F的一个合一，如果对F的任意一个合一$\theta$都存在一个置换$\lambda$，使得$\theta = \sigma · \lambda$
      • 则称$\sigma$是一个最一般合一
  • mgu的求取算法
    • 差异集

子句集

定义

  • 文字：原子（谓词）公式及其否定
  • 子句：若干个文字的一个析取式
    • 空子句：不含任何文字的子句，记为$\lambda$或$NIL$
  • 子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。

前束范式

  • 设F是一个谓词公式，如果其中的所有量词均非否定出现在公式的最前面，而它们的辖域为整个公式，则称F为前束范式
    • $(Q_1x_1)(Q_2x_2)…(Q_nx_n) M(x_1,x_2,…,x_n)$
    • 其中$Q_i\in {\forall, \exists}$，$M(x_1,x_2,…,x_n)$中不含有任何量词

子句集的化简

  • 在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集 $(\forall x)((\forall y)P(x,y) \rightarrow \neg(\forall y)(Q(x,y)\rightarrow R(x,y)))$
Course, 数理逻辑
This post is licensed under CC BY 4.0 by the author.