第四章 谓词逻辑的基本概念

谓词和个体词

谓词

• 约定：
  • 小写字母表示命题
  • 大写字母表示谓词
• 定义：谓词是给定的个体域到集合 \(\{\mathrm{T},\mathrm{F}\}\) 上的一个映射。
  • 一元谓词：在一个命题里，如果主词只有一个，这时表示该主词性质或属性的词便称作谓词。这是一元（目）谓词，以 \(P(x),Q(x),\cdots\) 表示.
  • 多元谓词：在一个命题里，如果主词多于一个，那么表示这几个主词间的关系的词称作谓词。这是多元谓词，以 \(P(x,y),Q(x,y),R(x,y,z),\cdots\) 表示
• 一般地说谓词 \(P(x),Q(x,y)\) 是命题形式而不是命题
  • 因为这里没有指定谓词符号 \(P,Q\) 的含义，即它们是谓词变项。
  • 仅当谓词变项取定为某个谓词常项，并且个体词取定为个体常项时，命题形式才化为命题
  • 谓词的真值依赖于个体变元的论域

个体词

• 个体词(主词)
  • 个体词是一个命题里表示思维对象的词
  • \(P(张三)\) 中的张三是个体词或称个体常项
  • 谓词 \(P(x)\) 中的变量 \(x\) 为个体变项或个体变元
• n 项(目、元)谓词
  • 有 \(n\) 个个体的谓词 \(P(x_{1}, \ldots, x_{n})\) 称 \(n\) 项(目、元)谓词
  • 如果 \(P\) 是已赋有确定含义的谓词，就称为谓词常项
  • 如果 \(P\) 表示任一谓词时，就称为谓词变项
• 个体域
  • 将个体变项的变化范围称为个体域或论域，以 \(D\) 表示
  • 论域是重要的概念，同一谓词在不同论域下的描述形式可能不同，所取的真假值也可能不同
• 约定
  • 谓词逻辑的个体域除明确指明外，都认为是包括一切事物的一个最广的集合
  • 谓词变项的变化范围，不做特别声明时，指一切关系或一切性质的集合

谓词逻辑与命题逻辑

• 可认为谓词逻辑是命题逻辑的推广，命题逻辑是谓词逻辑的特殊情形
  • 因为任一命题都可通过引入具有相应含义的谓词(个体词视为常项)来表示
  • 或认为一个命题是没有个体变元的零元谓词
• 命题逻辑中的很多概念、规则都可推广到谓词逻辑中延用
  • 如联结词可照搬到谓词逻辑，无需再做说明
  • 有的等值式推理式也可移植到谓词逻辑
  • 然而谓词逻辑里出现了个体变元，谓词、量词等概念，特别是个体论域常是无限域，加大了处理难度
  • 最简单又深刻的例子：在命题逻辑里一个公式不难判定它是否是重言式，真值表法是能行的方法。然而 在谓词逻辑里就没有一般的能行算法来判定任一公式是不是普遍有效的（或称定理、永真式）

函数和量词

函数

• 定义：函数是某个体域（不必是实数）到另一个体域的映射。
  • 不同于谓词：将个体映射为真假值
  • 函数并不单独使用，是嵌入在谓词中
• 约定：函数符号用小写字母表示。

量词

• 定义：用来表示个体数量的词是量词，可看作是对个体词所加的限制、约束的词。
• 量词仅作用于 个体变元 ，不允许量词作用于 命题变项 和 谓词变项。

全称量词 \(\forall\)

• 符号 \((\forall x)\)
  • 读作所有的 \(x\) 或任一 \(x\)，一切 \(x\)。
  • 而 \(\forall\) 就是 全称量词 ，它所约束的个体是 \(x\)。
• 定义：命题 \((\forall x) P(x)\) 当且仅当对论域中的所有 \(x\) 来说，\(P(x)\) 均为真时方为真。
• 性质：\((\forall x) P(x)=\mathrm{F}\) 成立，当且仅当有一个 \(x_{0} \in D\)，使 \(P\left(x_{0}\right)=\mathrm{F}\)

存在量词 \(\exists\)

• 符号 \((\exists x)\)
  • 读作至少有一个 \(x\) 或存在一个 \(x\) 或有某些 \(x\)。
  • 而 \(\exists\) 就是对个体词起约束作用的 存在量词 ，所约束的变元是 \(x\)。
• 定义：命题 \((\exists x) Q(x)\) 当且仅当在论域中至少有一个 \(x_{0}\)，\(Q\left(x_{0}\right)\) 为真时方为真。
• 性质：从而 \((\exists x) Q(x)=F\)，当且仅当对所有的 \(x \in D\) 都有 \(Q(x)=F\)。

约束变元和自由变元

• 自由变元：若 \(P(x)\) 表示 \(x\) 是有理数，这时的变元 \(x\) 不受任何量词约束，便称是自由的。
• 约束变元：而 \((\forall x) P(x)\) 中的两处出现的变元 \(x\) 都受量词 \(\forall\) 的约束，便称作约束变元，受约束的变元也称被量词量化了的变元。
• 例子：在命题形式 \((\forall x) P(x) \lor Q(y)\) 中，变元 \(x\) 是约束的，而变元 \(y\) 是自由的。

辖域

• 定义：量词所约束的范围称为量词的辖域
• 例子：
  • \((\forall x) R(x,y)\) 中，\(R(x,y)\) 是 \((\forall x)\) 的辖域
  • \((\exists x)((\forall y) P(x,y))\) 中
    • \(P(x,y)\) 是 \((\forall y)\) 的辖域
    • \((\forall y) P(x,y)\) 是 \((\exists x)\) 的辖域

变元易名规则

• 变元易名规则： \((\forall x) P(x) = (\forall y) P(y)\)
  • 注：\((\forall x)(P(x) \rightarrow Q(x,y)) \neq (\forall y)(P(y) \rightarrow Q(y,y))\)
• 因为在同一论域 \(D\) 上， 对一切 \(x\)， \(x\) 具有性质 \(P\)， 同对一切 \(y\)， \(y\) 具有性质 \(P\)， 除变元 \(x\) 和 \(y\) 的区别外并无差异， 从而 \((\forall x) P(x)\) 和 \((\forall y) P(y)\) 真值相同

合式公式

• 关注一阶谓词逻辑， 而不是高阶谓词逻辑
  • 限定在量词仅作用于个体变元
  • 不允许量词作用于命题变项和谓词变项
  • 也不讨论谓词的谓词
• 符号约定
  • 命题变项：\(p, q, r, \cdots\)
  • 个体变项：\(x, y, z, \cdots\)
  • 个体常项：\(a, b, c, \cdots\) 或者大写英文单词
  • 谓词变项：\(P, Q, R, \cdots\)
  • 谓词常项：大写英文字母, 如 \(GREAT\)
  • 函数：\(f, g, \cdots\) 或者小写英文单词
  • 五个联结词： \(\neg, \vee, \wedge, \rightarrow, \leftrightarrow\)
  • 两个量词： \(\forall, \exists\)
  • 小括号： \((, )\)
• 合式公式定义：
  1. 命题常项、命题变项和原子谓词公式（不含联结词的谓词）都是合式公式
  2. 如果 \(A\) 是合式公式，则 \(\neg A\) 也是合式公式
  3. 如果 \(A,B\) 是合式公式，而无变元 \(x\) 在 \(A,B\) 的一个中是约束的而在另一个中是是自由的，则 \((A \wedge B),(A \vee B),(A \rightarrow B),(A \leftrightarrow B)\) 也是合式公式（最外层括号可省略）
  4. 如果 \(A\) 是合式公式，而 \(x\) 在 \(A\) 中是自由变元，则 \((\forall x) A,(\exists x) A\) 也是合式公式
  5. 只有适合以上 \(4\) 条的才是合式公式

自然语句的形式化

常见自然语言的形式化

• “所有的……都是……”

  • 所有的有理数都是实数，其意思是说，对任一事物而言，如果它是有理数，那么它是实数。即对任一 \(x\) 而言，如果 \(x\) 是有理数，那么 \(x\) 是实数。

  • 若以 \(P(x)\) 表示 \(x\) 是有理数，\(Q(x)\) 表示 \(x\) 是实数，这句话的形式描述应为

    \[ (\forall x)(P(x) \rightarrow Q(x)) \]

• “有的……是”

  • 这句话的意思是说，存在一事物它是实数，而且是有理数。即有一个 \(x\)，\(x\) 是实数并且是有理数。、

  • 仍以 \(P(x)\) 表 \(x\) 是有理数，\(Q(x)\) 表示 \(x\) 是实数，这句话的形式描述应为

    \[ (\exists x)(Q(x) \wedge P(x)) \]

• “没有……是……”

  • 这句话有否定词，意思是对任一 \(x\) 而言，如果 \(x\) 是无理数，那么 \(x\) 不是有理数。

  • 若以 \(A(x)\) 表示 \(x\) 是无理数，\(B(x)\) 表示 \(x\) 是有理数，这句话的形式描述为

    \[ \neg(\exists x)(A(x) \wedge B(x)) \]

  • 也可以逻辑上等价的

    \[ \begin{aligned} (\forall x)(A(x) \rightarrow \neg B(x)) \\ (\forall x)(B(x) \rightarrow \neg A(x)) \end{aligned} \]

• “有的……不是……”

  • 这句话的意思是有的 \(x\)，它是实数而且不是有理数。

  • 若以 \(A(x)\) 表示 \(x\) 是实数，\(B(x)\) 表示 \(x\) 是有理数，那么这句话可形式描述为

    \[ (\exists x)(A(x) \wedge \neg B(x)) \]

自然数集的形式描述

• 论域是自然数集，来形式化语句
  1. 对每个数，有且仅有一个相继后元
  2. 没有这样的数，\(0\) 是其相继后元
  3. 对除 \(0\) 而外的数，有且仅有一个相继前元（可将这三句话作为建立自然数集合的公理）
• 引入谓词 \(E(x,y)\) 表示 \(x=y\)，函数 \(f(x)\) 表示个体 \(x\) 的相继后元，即 \(f(x)=x+1\)。函数 \(g(x)\) 表示个体 \(x\) 的相继前元，即 \(g(x)=x-1\)
• 有且仅有：如果有两个，那么它们必然相等

• 形式化

  \[ \begin{aligned} &(\forall x)(\exists y)(E(y, f(x)) \wedge(\forall z)(E(z, f(x)) \rightarrow E(y, z)))\\ &(\forall x)(\neg E(x, 0) \rightarrow(\exists y)(E(y, g(x)) \wedge(\forall z)(E(z, g(x)) \rightarrow E(y, z))))\\ &\neg(\exists x) E(0, f(x)) \end{aligned} \]

谓词变元多次量化

\[ \begin{aligned} (\forall x)(\forall y) P(x, y)=(\forall x)((\forall y) P(x, y)) \\ (\forall x)(\exists y) P(x, y)=(\forall x)((\exists y) P(x, y))\\ (\exists x)(\forall y) P(x, y)=(\exists x)((\forall y) P(x, y)) \\ (\exists x)(\exists y) P(x, y)=(\exists x)((\exists y) P(x, y)) \end{aligned} \]

• 其中：
  • 第一个和第四个公式里的约束可交换
  • 第二个和第三个公式里的约束不可交换，存在依赖关系

论域为有限域时的公式表示法

• 约定论域限定为有限集，用 \(\{1,2,\cdots,k\}\) 来代表；

  \[ (\forall x)(P(x) \rightarrow Q(x)) \]

• 论域为有限域时，公式表示法：

  \[ \begin{aligned} (\forall x) P(x)=P(1) \wedge P(2) \wedge \cdots \wedge P(k) \\ (\exists x) P(x)=P(1) \vee P(2) \vee \cdots \vee P(k) \end{aligned} \]

• 严格意义上，无限域下，不是合式公式，谓词逻辑公式不能转换为命题逻辑公式

• 谓词公式的解释
  • 谓词公式的解释与论域，自由个体变元，命题变元，谓词变元，函数都有关系
  • 对谓词公式 \(I\) 的解释包括五个部分
    • 非空论域 \(D\)
    • 命题变元指派为 \(\{0,1\}\)
    • 对个体常元和（自由）个体变元指派为 \(D\) 中的元素
    • 对谓词指派为 \(D\) 上的谓词
    • 对函数指派为 \(D\) 上的函数

公式的普遍有效性和判定问题

• 公式的普遍有效性
  • 对一个谓词公式来说，如果在它的任一解释 \(I\) 下真值都为真，便称作普遍有效的
  • 对一个谓词公式来说，如果在它的某个解释 \(I\) 下真值为真，便称作可满足的
  • 对一个谓词公式来说，如果在它的任一解释 \(I\) 下真值均为假，便称作不可满足的
  • 有限域上一个公式的可满足性和普遍有效性依赖于个体域个体的个数且仅依赖于个体域个体的数目
    • 在某个含 \(k\) 个元素的 \(k\) 个体域上普遍有效（或可满足），则在任一 \(k\) 个体域上也普遍有效（或可满足）
    • 如果某公式在 \(k\) 个体域上普遍有效，则在 \(k-1\) 个体域上也普遍有效
    • 如果某公式在 \(k\) 个体域上可满足，则在 \(k+1\) 个体域上也可满足
• 判定问题：谓词逻辑的判定问题，指的是任一公式的普遍有效性。若说谓词逻辑是可判定的，就要给出一个能行方法，使得对任一谓词公式都能判断其是否普遍有效。
  • 结论：
    1. 谓词逻辑是不可判定的；
       • 对任一谓词公式而言，没有能行的方法判明它是否是普遍有效的
       • 并不排除谓词公式有子类是可判定的
       • 判定问题的困难在于个体域是个无穷集以及对谓词设定的任意性
    2. 只含一元谓词变元的公式是可判定的
    3. \(\left(\forall x_{1}\right) \cdots\left(\forall x_{n}\right) P\left(x_{1}, \cdots, x_{n}\right)\) 和 \(\left(\exists x_{1}\right) \cdots\left(\exists x_{n}\right) P\left(x_{1} \ldots x_{n}\right)\) 型公式，若 \(P\) 中无量词和其他自由变项时， 也是可判定的
    4. 个体域有穷时的谓词公式是可判定的