第10讲谓词逻辑等值式

如 F(x)G(x), xF(x)yG(y)是pq的代换实例 定理 重言式的代换实例都是重言式，矛盾式的代 换实例都是矛盾式.
26
实例
例 判断下列公式的类型 (1) ∀xF(x)→∃xF(x)；
设I为任意的解释，若∀xF(x)为假，则 ∀xF(x)→∃xF(x)为真. 若∀xF(x)为真，则∃xF(x)也为 真，所以∀xF(x)→∃xF(x)恒为真. 是逻辑有效式. (2) ∀xF(x)→(∀x∃yG(x,y)→∀xF(x))； 重言式p→(q→p) 的代换实例，是逻辑有效式.

7
基本概念 —谓词：0元谓词
例 将命题“2是素数且是偶数”用0元谓词 符号化 设F(x)：x是素数； G(x)：x是偶数；a: 2 则F(a)G(a)表示“2是素数且是偶数” F(a)和G(a)都是0元谓词，不仅如此 F(a)G(a)也是0元谓词， F(x)G(x)是一个1 元谓词，表示x既是素数又是偶数这一性质. 以个体常元a代入x，从而消去个体变元，便 得到0元谓词F(a)G(a)
10
例 (续 )
(2) 2 是无理数仅当 3是有理数 在命题逻辑中, 设 p： 2 是无理数，q： 3 是有理数. 符号化为 p q 在谓词逻辑中, 设F(x): x是无理数, G(x): x是有理数 符号化为 F ( 2 ) G( 3 ) (3) 如果2>3，则3<4 在命题逻辑中, 设 p：2>3，q：3<4. 符号化为 pq 在谓词逻辑中, 设 F(x,y)：x>y，G(x,y)：x<y, 符号化为 F(2,3)G(3,4)
基本概念 ——谓词：元数
谓词的元数: 谓词中包含的个体的个数， 例如 F(x,y,z)含有三个个体，其元数为3 一元谓词: 表示事物的性质或状态，如F(苏) 多元谓词 (n元谓词, n2): 表示事物之间的 关系. 例如 L(x,y)表示x与y有L关系， 若L表示…大于…，则L(x,y)表示x>y， 若 L 表示 …是 … 的妻子，则 L( 圆 , 又 ) 表示 高圆圆是赵又廷的妻子. n 元谓词规定了 n个个体的顺序，不可随意颠 倒 . 例如 L(圆,又)不能写L(又,圆)

谓词逻辑的等值演算Equivalent Calculus in Predicate Logic天下乌鸦一般黑F(x)：x 是乌鸦G(x,y)：x与y一般黑原语句可表示成(∀x)(∀y)(F(x)∧F(y)⇒G(x,y))或者~(∃x)(∃y)(F(x)∧F(y)∧~G(x,y))⏹设A, B是两个谓词公式，若A⇔B 是普遍有效的公式，则称A与B等值，记作A ≡B。

⏹类似于命题逻辑，两个谓词公式A, B等值当且仅当在任何解释下，A 和B的真值都相同。

⏹谓词逻辑的等值演算仍是以基本等值式为基础，应用等值演算规则，逐步推演⏹谓词逻辑中的基本等值式主要分两类：⏹其一是从命题公式移植来的等值式，即命题逻辑中基本等值式的代换实例⏹如(∀x)F(x)⇒(∃y)G(y) ≡~(∀x)F(x)∨(∃y)G(y)⏹另一类是谓词逻辑所特有的等值式，与量词有关⏹（消去量词等值式）⏹设论域D={a1, a2, …, a m}是有限集合，则有⏹(∀x)A(x) ≡A(a1)∧A(a2)∧…∧A(a m)⏹(∃x)A(x) ≡A(a1)∨A(a2)∨…∨A(a m)例设论域D = {a, b, c}，消去下面公式中的量词：(1) ∀x(F(x)⇒G(x))≡(F(a)⇒G(a))∧(F(b)⇒G(b))∧(F(c)⇒G(c))(2) ∃x∀yF(x,y)≡∃x(F(x,a)∧F(x,b)∧F(x,c))≡ (F(a,a)∧F(a,b)∧F(a,c))∨(F(b,a)∧F(b,b)∧F(b,c))∨(F(c,a)∧F(c,b)∧F(c,c))⏹（量词否定等值式/德·摩根律）⏹设A(x)是含x自由出现的公式，则~(∀x)A(x)≡(∃x)~A(x)~(∃x)A(x)≡(∀x)~A(x)当D = {a1, a2, …, a m} 时∀x A(x)≡A(a1)∧A(a2)∧…∧A(a m)，∃x A(x)≡A(a1)∨A(a2)∨…∨A(a m)~∀x A(x)≡~(A(a1)∧A(a2)∧…∧A(a m))≡ ~A(a1)∨~A(a2)∨…∨~A(a m)≡∃x ~A(x)（量词辖域收缩与扩张等值式）设A(x) 是含x自由出现的公式，谓词公式B中不含x的出现，则有∀x(A(x)∨B) ≡∀xA(x)∨B∀x(A(x)∧B) ≡∀xA(x)∧B∃x(A(x)∨B) ≡∃xA(x)∨B∃x(A(x)∧B) ≡∃xA(x)∧B⏹（量词分配等值式）设 A (x ), B (x ) 是含 x 自由出现的谓词公式，则有∀x (A (x )∧B (x )) ≡ ∀xA (x )∧∀xB (x ) ∃x (A (x )∨B (x )) ≡ ∃xA (x )∨∃xB (x )⏹注意：∀对∨不满足分配律，∃对∧不满足分配律 当 D = {a 1, a 2, …, a m } 时 ∀x A (x )≡A (a 1)∧A (a 2)∧…∧A (a m ), ∃x A (x )≡A (a 1)∨A(a 2)∨…∨A (a m )⏹设A(x, y)是含x, y自由出现的谓词公式，则有∀x∀y A(x, y) ≡∀y∀x A(x, y)∃x∃y A(x, y) ≡∃y∃x A(x, y)⏹这组等值式表明相同量词与排列的次序无关，但是对于不同量词，不能随意更换次序，即(∀x)(∃y)A(x, y) 与(∃y)(∀x)A(x, y) 不等值⏹谓词逻辑包括以下三条等值演算规则：⏹置换规则⏹设Φ(A)是含谓词公式A的公式，Φ(B)是用谓词公式B取代Φ(A)中的A（不一定是每一处）之后得到的谓词公式，若A≡B，则Φ(A)≡Φ(B)。

§3.5 前束范式
§3.6 谓词逻辑的推理
4
谓词与量词
个体词（individual）是一个命题里表示思维
对象的词，表示独立存在的具体或抽象的客体
具体的、确定的个体词称为个体常项，一般用
a, b, c 表示
抽象的、不确定的个体词称为个体变项，一般
用 x, y, z 表示
个体变项的取值范围称作个体域或论域
那么在解释2下该命题是真命题。

24
谓词公式及分类
类似于命题逻辑，也可以对谓词逻辑
公式进行分类：
设 A 为一个谓词公式，若 A 在任何解
释下真值均为真，则称 A 为普遍有效
的公式或逻辑有效式（logically valid
formula）
例
(x)
(P(x)∨P(x))
(x) P(x) P(y)
第三章 谓词逻辑
《离散数学及应用》
第三章 谓词逻辑
苏格拉底三段论：
凡是人都是要死的。
苏格拉底是人。
所以苏格拉底是要死的。
p∧q r
重言式？正确的推理？
2
第三章 谓词逻辑
为了克服命题逻辑的局限性，引入了
3
谓词和量词对原子命题和命题间的相
互关系做进一步的剖析，从而产生了
为谓词。这是一元（目）谓词，以
P(x), Q(x), …表示。
例
Human
(Socrates)
Mortal (Socrates)
7
谓词与量词
如果在命题里的个体词多于一个，那
么表示这几个个体词间的关系的词称
作谓词。这是多元（目）谓词，有 n
个个体的谓词 P(x1, …, xn) 称 n 元（目）

两种量词: 全称量词和存在量词.
全称量词:
1.全称量词 ： （任意，所有） x: “对一切x”，“对所有的x”， “对任一x”
如： x P(x) ┐ x P(x) x ┐ P(x)
“对一切x，P(x)是真” “并非对一切x，P(x)是真” “对一切x， ┐ P(x) 是真”
如: “ 所有人都是要死的”
于是令 M（x）：x是人。 （1） x（M(x)→D(x)) （2） x (M（x）∧ ┐G（x））
命题符号化(翻译)：
将汉语(或其他自然语言)语句翻译成逻辑表 达式，这在数学、逻辑编程、人工智能、软 件工程以及许多其他学科中都是一项重要的 任务。翻译的目的是生成简单而有用的逻辑 表达式。
命题符号化：
1.谓词与个体词
将简单命题分解成个体与谓词这样两个组成部分。谓词，通 常是用来描述个体的性质或特征，或者个体之间的关系。谓 词逻辑，是命题逻辑的扩充与发展 。
例1：下面两个命题 1. 张华是学生 2. 李明是学生
a: 张华 b:李明 H：是学生 ，则 H（x）:x是学生
1，2可分别表示成 H(a) ，H(b). 这样表示就揭示了两命题间有相同的谓语这一特征。
变元的约束
例1 ： 令 P（x， y）：“ x<y ”， Q（x）：x是有理数； F（x）：x可以表示为分数。
判断下列式子那些是命题函数，那些是命题？
P(x， y)
P(x， y)∧Q(x)
Q(x) → F(x) x（Q(x)→ F(x)) x Q(x)→ F(x)
自由变元与约束变元
[定义] 紧接于量词之后最小的子公式称为量词的辖 域．(量词的辖域是紧接其后的公式，除非辖域是个 原子公式，否则应在公式的两侧插入圆括号。)