离散数学(3) 谓语逻辑

在之前的两节课中我们讲了逻辑和逻辑等价。我们懂得怎么找命题的真值,知道怎么判断命题的真假;我们也知道怎么通过逻辑等价将命题简化,以及找到相等的命题。但是命题逻辑依然有它的局限性。今天我们学习一种新的逻辑表达式,谓词逻辑(predicate logic),它可以帮助我们表达更多命题逻辑不能表达的东西。

命题逻辑的局限

命题逻辑没办法表达命题之间一些特定类型的关系。比如说

  1. “不是所有的鸟都会飞”和“有些鸟不会飞”等同

  2. “不是所有的整数都是偶数”和“一些整数不是偶数”等同

另外,在计算机科学和数学领域,命题逻辑无法表示所有的断言:比如说当一个命题中出现未知的变量的时候或者拥有量词的时候。

解决办法?

上述的不足都能用谓词逻辑来补充。

实际上,谓词逻辑仅补充了两个概念到命题逻辑中。

  1. 谓词 (predicates)

  2. 量词(quantifiers)

谓词

定义: A predicate is a logical statement that depends on one or more variables (not necessarily boolean variables). It describes a property of objects, or a $brelationship among objects represented by the variables.

举个例子

"x 大于 3“

在这个命题中,x是主语(subject)–命题描述的对象;"大于3"是他的谓语,用于描述主语。如果x没有被赋值的话,整个命题是没有意义的。

现在我们把这个谓词命题用符号表示出来。我们首先用一个命题方程来代表这个命题

p(x) = "x 大于 3“

x代表的是命题的变量,p方程是一个谓语。当有变量赋值给x的时候方程就变成了一个命题。

如:

p(10)

该命题为真。

多个变量呢?

Q(x, y, z) = x^2 + y^2 + z^2

Q(3,4,5) 为真; Q(2,2,3)为假。

量词

一个谓词可以通过加入变量变成一个命题,当然,我们也有别的办法将谓词变成命题 – 量词化。

量词都有哪些呢?

>所有,许多,一些,少数,没有…

我们研究两种量词。

假设变量的范围是全班的学生

所有学生都是人

当所有变量都适用的时候,我们说它是一个全称量化(universal quantifier);

没有 一个学生在睡觉

只有部分变量适用于该情况的时候,我们说它是一个存在量化(existential quantifier)

划重点: 只有有x代入公式都为真的时候,P(x)为真才为真。我们用 \forall_ xP(x) 来表示全称量化,读作"所有x".

举个全称量化的例子:

x的范围是历届美国总统

p(x): x是个男生

\forall_xP(x) : 所有历届美国总统都是男生

说白了,其实 \forall_xP(x) = P(奥巴马) \wedge P(特朗普) \wedge P(华盛顿)…

举个纯在量化的例子:

x的范围是历届美国总统

P(x): x是白种人

\exists_xP(x): 至少一个美国总统是白种人。

说白了,其实 \forall_xP(x) = P(奥巴马) \vee P(特朗普) \vee P(华盛顿)…

2 个赞