下载掌阅APP，畅读海量书库
立即打开
在谓词公式中，要确定其真值，需要指定个体域，要对谓词变元和个体变元赋以确定的值，要给函数符号指定具体的函数。因此对谓词公式的解释要复杂得多。下面给出谓词公式的一个解释的概念。
定义2.3.1 谓词逻辑中公式 A 的一个解释（或赋值） I 由如下四部分组成：
1）非空的个体域集合 D ；
2） A 中的每个常量符号，指定 D 中的某个特定的元素；
3） A 中的每个 n 元函数符号，指定 D n 到 D 的某个特定的函数；
4） A 中的每个 n 元谓词符号，指定 D n 到{0,1}的某个特定的谓词。
例2.3.1 给定解释 I 如下：
1）个体域为实数集合 ℝ；
2）元素 a =0；
3） N 中特定的函数 f （ x , y ）= x-y ；
4） N 中特定的谓词 F （ x , y ）： x < y 。
在解释 I 下，求下列公式的真值。
1）∀ xF （ f （ a ， x ）， a ）
2）
3）∀ x ∀ y ∀ z （ F （ x ， y ）→ F （ f （ x ， z ）， f （ y ， z ）））
4）∀ x ∃ yF （ x ， f （ f （ x ， y ）， y ））
5）∀ xF （ x ， f （ x ， a ））→ F （ x ， y ）
解 1）∀ xF （ f （ a ， x ）， a ）⇔∀ x （ f （ a ， x ）＜ a ）⇔∀ x （ a-x ＜ a ）⇔∀ x （0 -x ＜0）⇔∀ x （0＜ x ）⇔0。
2）
。
3）∀ x ∀ y ∀ z （ F （ x ， y ）→ F （ f （ x ， z ）， f （ y ， z ）））⇔∀ x ∀ y ∀ z （（ x ＜ y ）→（ f （ x ， z ）＜ f （ y ， z ）））⇔∀ x ∀ y ∀ z （（ x ＜ y ）→（ x-z ＜ y-z ））⇔∀ x ∀ y ∀ z （（ x ＜ y ）→（ x ＜ y ））⇔1。
4）∀ x ∃ yF （ x ， f （ f （ x ， y ）， y ））⇔∀ x ∃ y （ x ＜ f （ f （ x ， y ）， y ））⇔∀ x ∃ y （ x ＜（ f （ x ， y ） -y ））⇔∀ x ∃ y （ x ＜（ x-y-y ））⇔∀ x ∃ y （ x ＜ x -2 y ）⇔1。
5）∀ xF （ x ， f （ x ， a ））→ F （ x ， y ）⇔∀ x （ x ＜（ x -0））→（ x ＜ y ）⇔∀ x （ x ＜ x ）→（ x ＜ y ）⇔1，因为蕴含式的前件为假。
◀
定理2.3.1 封闭的谓词公式在任何解释下都变成命题。
证明 略。
◀
不是闭式的谓词公式在某些解释下也可能变成命题，如例2.3.1中的公式5）不是闭式，但在解释 I 下是真命题。
定义2.3.2 设 A 是一个谓词公式。如果 A 在任何解释下的真值恒为真，则称 A 为 永真式 （或 逻辑有效式 ）；如果 A 在任何解释下的真值恒为假，则称该谓词公式为 永假式 （或 矛盾式 ）；如果至少存在一个解释使 A 的真值为真，则称 A 为 可满足式 。
例2.3.2 判定公式 ∀ y ∃ xA （ x ， y ）←→∃ x ∀ yxA （ x ， y ）的类型。
解 设个体域为自然数集合，令 A （ x ， y ）表示 xy = y 。因为对任何自然数 y ，均存在自然数 x ，使得 xy = y ，所以∀ y ∃ xA （ x ， y ）在该解释下的真值为1，而此时∃ x ∀ yA （ x ， y ）的真值也为1，因为存在一个自然数 x ，使得对所有的自然数 y ，都有 xy = y 。因而在此解释下∃ x ∀ yA （ x ， y ）←→∀ y ∃ xA （ x ， y ）的真值为1。
再设个体域为自然数集合， A （ x ， y ）表示 x ＞ y 。因为对任何自然数 y ，均存在自然数 x ，使得 x ＞ y ，所以∀ y ∃ xA （ x ， y ）在该解释下的真值为1，而此时∃ x ∀ yA （ x ， y ）的真值为0，因为不存在一个自然数 x ，使得对所有的自然数 y ，都有 x ＞ y 。因而在此解释下∃ x ∀ yA （ x ， y ）←→∀ y ∃ xA （ x ， y ）的真值为0。
因此公式∀ y ∃ xA （ x ， y ）←→∃ x ∀ yA （ x ， y ）不是永真式，是可满足式。
◀
谓词公式没有像命题公式那样的真值表。判定一个谓词公式为永真式，当论述域是无限集时，要求在任何解释下谓词公式的真值均为1，这是不可能的。目前，还没有可行的算法判定一个谓词公式的类型，只能对一些特殊的谓词公式进行判断。
对于一些特殊的谓词公式，如果它是永真式或矛盾式，则可以采用分析法或公式法进行证明，如果它是可满足式，则要通过举例说明，给出两种解释，一种解释使其为真，另一种解释使其为假。
定义2.3.3 设 A 0 是含命题变元 p 1 ， p 2 ， p 3 ，…， p n 的命题公式， A 1 , A 2 ,…， A n 是 n 个谓词公式，用 A i （1≤ i ≤ n ）代替 A 0 中的 p i ，所得公式 A 称为 A 0 的 代换实例 。
如 F （ x ）→ G （ y ）、∀ xF （ x ）→∃ xF （ x ）都是 p → q 的代换实例。
定理2.3.2 命题公式中永真式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。
证明 略。
◀
例2.3.3 判断下列公式是永真式还是矛盾式。
1）∃ x （ A （ x ）→ B （ x ））←→（∀ xA （ x ）→∃ xB （ x ））
2）（∃ xA （ x ）→∃ xB （ x ））→∃ x （ A （ x ）→ B （ x ））
3）
；
解
因此有∃ x （ A （ x ）→ B （ x ））←→（∀ xA （ x ）→∃ xB （ x ））⇔1
所以∃ x （ A （ x ）→ B （ x ））←→（∀ xA （ x ）→∃ xB （ x ））为永真式。
所以（∃ xA （ x ）→∃ xB （ x ））→∃ x （ A （ x ）→ B （ x ））是永真式。
3）因为
，而
是
的代换实例，所以
是矛盾式。
◀