Name: Password: Sign in

[Lecture 3] 谓词与量词

1 谓词

有一类语句含有未知量,我们无法判断其真假,例如:

x=y+3

这类语句只有在未知量给定的时候才构成命题。因而对于这样一类语句,它们含有主语(xy),我们将其产生布尔值的函数称作 「谓词」 ,表明主语会有怎样的性质。我们用 P(x,y) 表示语句 「x=y+3」,其中 P命题函数,一旦 xy 被赋予值,P(x,y) 就变成了命题,例如下面这个例子:

A(x) 表示语句 「计算机 x 正在遭受入侵者攻击」,如果校园中只有 「CS2」和 「MATH1」被入侵者攻击,那么我们可以推断:

  • A(CS1) 为 F
  • A(CS2) 为 T
  • A(MATH1) 为 T

P(x,y) 一样,命题函数可以接受多个值,形为 P(x1,x2,...,xn) 的命题函数 P 称为 「n 元谓词

2 量词

2.1 量化

量化即谓词在一定范围内成立的程度。

日常语言中有「许多」,「一些」可以被用于量化,在这里我们主要讨论两种量化:「全称量化」与「存在量化」。量化是除谓词之外另一种产生产生命题的方式。处理谓词与量词的逻辑领域为 谓词演算

2.2 全称量词、存在量词与其他量词

  • 全称量词 (任何):一个谓词在所考虑的每一对象都为 T 即为 全称量化;符号 xP(x) 表示命题「P(x) 在其论域内所有值为 T」;如果存在 x 使得 P(x) 为 F,那么该对象为 xP(x)反例
  • 存在量词 (存在):一个谓词在所考虑中的一个或多个对象为 T 即为 存在量化;符号 xP(x) 表示命题「P(x) 在其论域内存在一个元素 x 使得 P(x) 为 T」
  • 唯一量词 ! (有且只有一个) :只存在唯一一个对象使得 P(x) 成立
  • 约束论域量词 : 量词后有一个必须满足的条件,对于全称量化约束 x<0(x2>0),表明「对每个小于 0 的实数 x,则 x2>0」,该命题与 x(x<0x2>0) 等价;存在量化约束 x>0(x2=2)x(x>0x2=2) 等价

例如,令 P(x)x2<0,那么:

  • xP(x) 为 F,因为存在 x=0 使得 P(x) 为 F;x=0xP(x) 的一个反例
  • xP(x) 为 T,只需要举出类似于 x=1x=2 则论域内存在元素使得 P(x) 为 T

又如,论域内为不超过 3 的正整数,P(x)x2<10,讨论 xP(x) ,需要列举出所有的的元素:x={1,2,3},判断所有的命题 P(1)P(3),那么 xP(x) 与和取等价:

xP(x)P(1)P(2)P(3)

推而广之,即如果论域内元素可数(如 x1, x2, …, xn),那么 xP(x) 与论域内所有命题的和取式等价:

xP(x)P(x1)P(x2)...P(xn)

类似的道理,xP(x) 与论域内所有命题的析取式等价:

xP(x)P(x1)P(x2)...P(xn)

(量词 优先级高于所有逻辑运算符。)

2.3 涉及量词的逻辑等价

如果两个涉及量词的语句对于所有的谓词与个体论域都有相同的真值,那么它们等价。

例如对于

x(P(x)Q(x))xP(x)xQ(x)

要证明其正确性,首先证明:

x(P(x)Q(x))xP(x)xQ(x)T

  • 假设 x(P(x)Q(x)) 为真
  • 从而对于任意 a 在论域内, P(a) 为真且 Q(a) 为真
  • xP(x)xQ(x) 为真
  • 上述即 x(P(x)Q(x))xP(x)xQ(x) 为真

然后证明:

xP(x)xQ(x)x(P(x)Q(x))T

  • 假设 xP(x)xQ(x) 为真
  • 从而对于任意 a 在论域内,有 P(a) 为真且 Q(a) 为真
  • x(P(x)Q(x)) 为真
  • 上述即 xP(x)xQ(x)x(P(x)Q(x)) 为真

所以:

x(P(x)Q(x))xP(x)xQ(x)T

x(P(x)Q(x))xP(x)xQ(x) 等价,可以在和取上分配全称量词。

类似的,有 x(P(x)Q(x))xP(x)xQ(x),即可以在析取上分配存在量词。

2.4 否定量化

要得到语句「班上所有人都修过微积分课」的否定,只需要举出班上存在有人没有修过微积分的反例就行,上述结论可以归结为:

¬xP(x)x¬P(x)

类似的,我们同样可以得到结论:

¬P(x)x¬P(x)

量词的否定即量词的 De Morgan 定律,如果论域中的元素为有限个 x1,x2,...xn,那么很明显:

¬xP(x)¬(P(x1)P(x2)...P(xn))

由之前对 De Morgan 定律的讨论,有:

¬xP(x)¬P(x1)¬P(x2)...¬P(xn)

注意到上式的右边即 x¬P(x)

类似的道理可以证明 ¬P(x)x¬P(x)

3 翻译带有谓词与量词的语句

区别于 1.4 中谈到的,此时句子的成分中含有谓词与量词,考虑下面这个句子:

这个班上有人去过墨西哥。

翻译的方式不唯一,假设 x 是班上的学生, M(x) 表示 「x 去过墨西哥」,那么上述句子可以翻译为:

xM(x)

以上的论域限定在班上的学生,如果论域扩展到所有人,并且假设 S(x) 表示 「x 在这个班上」,那么上述语句同样可以写为:

x(S(x)M(x))

4 Prolog

Prolog(Programming in Logic) 是 20 世纪 70 年代一种使用谓词逻辑进行推理的程序语言,它主要由 Prolog 事实Prolog 规则 两类语句构成。

例如我们想构建一套教师与学生注册课程的程序:

Prolog 事实

instructor(chan, math273)
instructor(patel, ee222)
instructor(grossman, cs301)
enrolled(kevin, math273)
enrolled(kyles, ee222)
enrolled(kyles, cs301)
enrolled(kiko, math273)
enrolled(kiko, cs301)

(上面的事实我们没有使用大写字母,在 Prolgo 中使用大写字母表示变量)

Prolog 规则

teaches(P, S): -instructor(P, C), enrolled(S, C)

即如果学生 s 与老师 p 都注册了同一门课程 c 那么他们构成 teaches 规则,teaches(p, s) 为真

使用问答查询,例如:

? enrolled(kyles, cs301)

yes

查询学生注册课程,例如:

? enrolled(X, cs301)

kyles
kiko

生成的 Prolog 规则同样支持查询:

? teaches(X, kyles)

patel
grossman
Copyright (c) 2014-2016 Kyles Light.
Powered by Tornado.
鄂 ICP 备 15003296 号