离散数学的谓词逻辑详解

“存在x， ┐ P(x)是真”
如: “有些有理数是整数。” 令Ｉ(x）：x是整数， 设x的个体域为有理数集合，则命题可表示为： x I(x）
2016/6/10 15
4. 论 域
含有量词的命题的表达式的形式，与论域有关。用量词量化 后的命题，其值也与论域有关。 例 1 x（x=0) 若论域为整数集，则此命题值为真， 若论域为正整数集，则命题的值为假。
2016/6/10
28
变元的约束
令 P（x， y）：“ x<y ”， Q（x）：x是有理数； F（x）：x可以表示为分数。 判断下列式子那些是命题函数，那些是命题？ 例1 ：
P(x， y) P(x， y)∧Q(x) Q(x) → F(x) x（Q(x)→ F(x)) x Q(x)→ F(x)
为了方便，引入全总个体域，记为：U，简称全域: 定义:宇宙间所有的个体聚集在一起所构成的集合称为全域。
2016/6/10
16
特性谓词
后面的讨论中，除特殊说明外，均使用全域。而对个 体变化的真正取值范围，用特性谓词加以限制。
一般地，对全称量词，特性谓词作蕴含的前件引入；而 对存在量词，特性谓词常作为合取项引入。
2016/6/10 12
3. 量词
使用前面介绍的概念，还不足以表达日常生活中的 各种命题。 例如： “ 所有的正整数都是素数 ” “ 有些正整数是素数 ” 两种量词: 全称量词和存在量词.
2016/6/10
13
全称量词:
1.全称量词 ： （任意，所有） x: “对一切x”，“对所有的x”， “对任一x”
定义：一个n元函词即是一个论域Ｄ上的一个n元函数．
2016/6/10
10
概念的讨论
变元在谓词中的次序直接影响了谓词的取值 。 如:设谓词P(x，y)为“x比y高”， 设张三为170cm，李四为180cm. 则: P(李四，张三)为真命题。 P(张三，李四)为假命题.
2016/6/10
11
命题的符号化
2016/6/10
5
1.谓词与个体词
将简单命题分解成个体与谓词这样两个组成部分。谓词，通 常是用来描述个体的性质或特征，或者个体之间的关系。谓 词逻辑，是命题逻辑的扩充与发展 。 例1：下面两个命题 1. 张华是学生 2. 李明是学生
a: 张华 b:李明 H：是学生 ，则 H（x）:x是学生
1，2可分别表示成 H(a) ，H(b). 这样表示就揭示了两命题间有相同的谓语这一特征。
如： x P(x) ┐ x P(x) x ┐ P(x)
“对一切x，P(x)是真” “并非对一切x，P(x)是真” “对一切x， ┐ P(x) 是真”


如: “ 所有人都是要死的”
设x的个体域为全体人的集合，则可表示为 x D(x)
2016/6/10 14
存在量词:
2. 存在量词： （存在） x: “存在x“、 ”某些x“、 ”至少有一x” 如： x P(x) ┐x P(x) 样” x ┐ P(x) “存在x， P(x)是真” “存在x， P(x)是真，并非这
2. 当取x的个体域为全域时，必须引入一个特性谓词将
“人”从全域中分离出来。 （1）对所有个体而言，如果它是人，则它是要死的。 （2）存在着个体，它是人并且它不怕死． 于是令 M（x）：x是人。 （1） x（M(x)→D(x)) （2） x (M（x）∧ ┐G（x））
2016/6/10
19
命题符号化(翻译)：
（1）原子是合式公式； （2）若A是合式公式，则(﹁A)也是合式公式； （3）若A，B是合式公式，则(A∧B)， (A∨B)， (A→B)， (AB)也是合式公式； （4）若A是合式公式，x是A中的变量符号， 则xA, xA也是合式公式 . （5）只有有限次地使用（1）—（4）所生成的符号串 才是合式公式。
2016/6/10 23
（3）凡是实数均能比较大小。 若令R（x）：x是实数；G（x，y)：x与y可比较大小.
则该命题可表示为： 例6 将苏格拉底三段论进行符号化：
令：Ｍ(x)：x是人 Ｄ(x): x要死 则
2016/6/10
24
量化断言与命题的关系
(1)如果论述域是有限的，不妨设论述域是{1，2，3}，则 x P(x)P(1)∧P(2)∧P(3) x P(x) P(1)∨P(2)∨P(3) (2) 如果论述域是可数无限，例如自然数集合，我们可以这 样理解： (x)P(x) P(1)∧P(2)∧P(3)… (x)P(x) P(1)∨P(2)∨P(3)… (3)如果论述域不可数无限，则无法表达。
则有 : xy( P( x) P( y) z( L( z) T ( x, y, z) u( L(u)
2016/6/10
T ( x, y, u) E(u, z)))).
22
例5
将下列命题符号化(使用全域)。 (1) 发光的并非都是金子
令：P（x）：x发光；G（x）：x是金子。 则该命题可表示为 ： （2）所有运动员都钦佩某些教练。 令：P（x）：x是运动员；T（x）：x是教练；Q （x，y）：x钦佩y。 则该命题可表示为 ：
2016/6/10
25
练习
任何金属都可以溶解在某种液体中. 令J(x):x是金属; E(x):x是液体;
S(x，y):x可以溶解在y中，
则可以表示为: x( J ( x) y( E( y) S ( x, y)));
2016/6/10
26
原子与公式
设P(x1，…xn)是n元谓词，则称其为为原子公式，或 简称原子． 谓词公式，简称为公式，其递归定义为：
2016/6/10 7
命题函数与命题
例: 令P(x)表示x为质数，则P(x)为一元谓词。 令 H(x，y)表示“x高于y”,则 H(x，y)为二元谓词。 则：H(张三，李四) 表示“张三高于李四”，是命题。 注意： P(x.y), H(x，y)为命题函数. P(2)与 H(张三，李四)才是命题。 谓词中如果有n个变元则称为n元谓词. n元谓词反映了个体 之间的n元关系.
将汉语(或其他自然语言)语句翻译成逻辑表 达式，这在数学、逻辑编程、人工智能、软 件工程以及许多其他学科中都是一项重要的 任务。翻译的目的是生成简单而有用的逻辑 表达式。
命题符号化：
例１：没有不犯错误的人 令H（x）： x是人， M（x）： x犯错误
则有: (x( H ( x) M ( x))) x( H ( x) M ( x)).
2016/6/10
29
自由变元与约束变元
[定义] 紧接于量词之后最小的子公式称为量词的辖 域．(量词的辖域是紧接其后的公式，除非辖域是个 原子公式，否则应在公式的两侧插入圆括号。)
在谓词公式中，在量词x、x的辖域内x 的一切出现 叫约束出现，这样的x，称为约束变元。 [定义] 在谓词公式中，若x的出现不是约束出现，则 称变元x的出现是自由出现。自由出现的变元x，称为 自由变元。
但是，在命题逻辑中无法得到正确性的反应:
P∧QR 不是重言式！ 命题逻辑不能正确反映此三段论的推理过程。这 是命题逻辑的局限性!
2016/6/10
3
原
因
在命题逻辑中无法将简单命题之间的内在联系反映出来。 命题逻辑中描述的上述三段论，即P∧Q→R，使R与命题P、 Q无关的独立命题。 但是，实际上R与命题P、Q是有关系的，只是这种关系 在命题逻辑中得不到反映。
2016/6/10
32
有关公式中变元改名的两条规则：
1.约束变元改名规则： 将谓词公式中出现的约束变元 改为另一个约束变元。此改名必须在量词辖域内各 处以及该量词符号中进行，且改成的新约束变元要 与改名区域中的其它变元有区别。
公式xP( x, y ) Q( x, z ), 将x改成u, 得uP(u, y ) Q( x, z )
2016/6/10 27
前面各命题符号化的结果都是合式公式。 对于一个谓词，如果其中每一个变量都在一个量词的 作用之下，则它就不再是命题函数而是一个命题了。
但是，这种命题和命题逻辑中的命题还是有区别的。 因为这种命题中毕竟还有变量，尽管这种变量和命题 函数中的变量有所不同。因此，有必要区分这些变量。
例1:武汉位于重庆与上海之间.
解:用个体词a，b，c分别表示武汉，重庆和上海， 谓词P(x，y，z)表示x位于y与z之间， 则该命题表示为:P(a，b，c).
例2：如果王英坐在李红的后面，则王英比李红高.
解：令 a:王英;b:李红;P(x，y):x坐在y的后面; G(x，y):x比y高. 则该命题表示为：P(a，b)G(a，b).
谓 词 逻 辑
2016/6/10
1
命题逻辑的局限性
苏格拉底三段论： P：所有的人都是要死的。 Q：苏格拉底是人 。 R：所以苏格拉底要死 。
凭直觉知道这个结论是真的，推理是有效的。但是，借 助命题演算的推理理论，却不能推导出这个结论（无法 证明它的正确性）。Why ?
2016/6/10 2
此三段论的论断显然正确。
2016/6/10
17
பைடு நூலகம்
例
(1)
“所有的人都是要死的。”
(2)
“有的人不怕死。”
1.当x的个体域为全体人组成的集合时，符号化上述命题。 解: 令D（x）：x是要死的，令G（x）：x怕死。 则（1）可表示为: x D(x)。 （2）可表示为: x ┐G(x)。
2016/6/10 18
论域为全域时
2016/6/10
30
例3 指出下列各公式中的量词辖域及自由变元和约 束变元。
１．x y((P(x)∧Q(y))→zR(z))
y y
解: y((P(x)∧Q(y))→zR(z)) 是 x 的辖域。 (P(x)∧Q(y))→zR(z) 是y 的辖域.