Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,1
1.3 谓词与量词
Predicates and Quantifiers
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,2
前两节介绍的命题与命题演算是命题逻辑的内容，其基本组成单位是原子命题。一般地，原子命题作为具有真假意义的句子至少由主语和谓语两部分组成。
例如,电子商务是计算机技术的一个应用,这里“电子商务”是主语，
而“是 ……” 是谓语。当主语改变为“电子政务”时就得到新的原子命题：
电子政务是计算机技术的一个应用 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,3
由此可知，主语是独立存在的 个体 /值 /Value，而谓语用来描述该个体的性质或个体间的关系，这里我们称其为 谓词
/Predicate。用 P表示谓词“是 ……” 。则 P（电子商务）或 P
（电子政务）分别等值于前述两个命题的表达。将个体用变量
（称为 个体变量 ） x推广，则 P（ x）表示,x是计算机技术的一个新的应用 。这时该语句就不是一个命题，而是一个命题函数。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,4
定义 一个谓词 P连同相关的 n（ n≥0）个个体变量组成的表达式称为 n元谓词 （ n-predicate），记 P（ x1,x2,…,x n），其中 n是该表达式中不同个体变量的数目。 n元谓词也称 简单命题函数,将简单命题函数视为命题，按 1.1节定义 10得到的递归定义的表达式称为 复合命题函数 。简单命题函数和复合命题函数，统称为 命题函数 （ proposition function）。
DEFINITION 1,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,5
EXAMPLE 1
Let P(x) denote the statement "x > 3." What are
the truth values of P(4) and P(2)?
P (4) =,T.
P (2) =,F,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,6
EXAMPLE 2
Let Q(x,y) denote the statement "x = y + 3."
What are the truth values of the propositions
Q(1,2) and Q(3,0)?
Q(1,2)=,F.
Q(3,0)=,T.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,7
EXAMPLE 3
R(x,y,z),x+y=z
What are the truth values of the propositions
R(1,2,3) and R(0,0,1)?
R(1,2,3)=.T,
R(0,0,1)=.F.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,8
当 n>1时,通常 P给出了 xi(i=1,2,…,n)之间的关系 。
例如,P(x,y,z)表示 x位于 y与 z之间,是一个三元谓词 。
与 x,y,z分别用构件层,表现层,总线层代入时得到命题：构件层位于表现层与总线层之间,其命值真值为 T。 再如将杭州,
南京,北京代入,则得到：杭州位于南京和北京之间,真值为 F。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,9
为了进一步讨论命题函数 P(x)的真值情况,首先需要指定个 体 变 量 x 可 选 择 的 范 围,即 个 体 域 （ universe of
discourse,or domain） 。 每一个个体变量 x都有自己的个体域 。 如果没有特别指定的个体域,则缺省为一个 全个体域
（ total universe of discourse） 即任意个体均可以作为常量对 x代入 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,10
在指定个体变量 x的个体域后,该个体域中的每个个体 a代入到 P(x)中的所有 x,就对应一个可以判定真假意义的命题
P(a)。 不同的个体代入后所对应的命题真值可能不同,也可能相同 。
例如,P(x)表示为
x2–1=(x–1)(x+1) x指定的个体域为全体整数,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,11
则对任意整数 i，
i2–1=(i–1)(i+1)
恒成立 。 也就是说,该命题函数的真值无论用什么个体代入总是对应为 T。 此类命题函数的真值描述通过一个称为全称量词的特殊符号来量化 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,12
定义 2 命题函数 P(x)的 全称量化 （ universal quanification）
是一个按如下规则确定真值的命题：如果对每一个个体 a代入得到的 P(a)均为 T。 则该命题为 T。 记为 VxP(x)。 这里 V是 全称量词 （ universal quantifier）,表示为,对任意的,,,所有的,,,对每一个,等等 。
DEFINITION 2,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,13
DEFINITION 2,
The universal quantification of P(x) is the proposition
“P(x) is true for all values of x in the universe of
discourse.”
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,14
EXAMPLE 5
Express the statement
"Every student in this class has studied calculus"
as a universal quantification.
It can be written as
xP(x) or x (S(x)→ P(x))
P(x) = "x has studied calculus."
S(x) = "x is in this class."
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,15
EXAMPLE 8
What is the truth value of V x P(x),where P(x) is the
statement "x2 < 10" and the universe of discourse consists of
the positive integers not exceeding 4?
x P(x)=P(1) ∧ P(2) ∧ P(3) ∧ P(4) =,F.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,16
定义 3 命 题 函 数 P(x) 的 存 在 量 化 （ existential
quantification） 是一个按如下规则确定真值的命题：如果个体域中存在一个个体 a代入后得到 P(a)为 T,则该命题为 T,否则为 F 。 记?或? 。 这里?称为 存在量词 （ existential
quantification） 。 表示为,有一个,,,某些,,,某个,
等等 。
DEFINITION 3,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,17
DEFINITION 3,
The existential quantification of P(x) is the
proposition
“There exists an element x in the universe of
discourse such that P(x) is true.”
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,18
EXAMPLE 9
Let P(x) denote the statement "x > 3." What is the truth
value of the quantification x P(x),where the universe of
discourse is the set of real numbers?
Since "x>3" is true,for instance,when x=4 the
existential quantification of P(x),which is xP(x)
is true.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,19
EXAMPLE 10
Let Q(x) denote the statement "x = x + 1." What is the
truth value of the quantification xQ(x),where the universe
of discourse is the set of real numbers?
.F.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,20
EXAMPLE 11
What is the truth value of x P(x) where P(x) is the
statement "x2 > 10" and the universe of discourse consists
of the positive integers not exceeding 4?
x P(x)
=P(1) ∨ P(2)∨ P(3)∨ P(4)
=,T.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,21
Table1
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,22
定义 4 谓词公式定义为
（ 1） n元谓词是一个谓词公式；
（ 2） 若 A是谓词公式,则 （?A ） 也是谓词公式；
（ 3） 若 A,B是谓词公式,则 （ A∨ B）,（ A∧ B）,
（ A→ B）,（ AB） 也是谓词公式；
（ 4） 若 A是谓词公式且含有未被量化的个体变量 x,则
VxA(x),?XA(x)也是谓词公式 。
（ 5） 有限次地使用 （ 1） ~（ 4） 所得到的也是谓词公式 。
DEFINITION 4,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,23
EXAMPLE 12
Translate the statement
x (C(x)∨ y(C(y)∧ F(x,y)))
into English,where C(x) is "x has a computer," F(x,y) is "x
and y are friends," and the universe of discourse for both x
and y is the set of all students in ZJU.
The statement says that for every student x in ZJU x
has a computer or there is a student y such that y has a
computer and x and y are friends,In other words,every
student in ZJU has a computer or has a friend who has
a computer,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,24
EXAMPLE 13
Translate the statement
x y z(((F(x,y)∧ F(x,z)∧ (y≠z))→ F(y,z)))
into English,where F(a,b) means a and b are friends and
the universe of discourse for x,y,and z is the set of all
students in your school.
This statement says that there is a student x such that for
all students y and all students z other than y,if x and y are
friends and x and z are friends,then y and z are not
friends,In other words,there is a student none of whose
friends are also friends with each other.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,25
EXAMPLE 15
Express the statements "Some student in this class has
visited Mexico" and "Every student in this class has visited
either Canada or Mexico" using quantifiers.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,26
EXAMPLE 16
Express the statement "Everyone has exactly
one best friend" as a logical expression.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,27
EXAMPLE 17
Express the statement "If somebody is female and is a
parent,then this person is someone's mother" as a logical
expression.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,28
EXAMPLE 18
Use quantifiers to express the statement "There is a
woman who has taken a flight on every airline in the world."
P(w,f),w has taken a f.
Q(f,a),f is a flight on a,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,29
EXAMPLE 19
(Calculus required) Express the definition of a
limit using quantifiers.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,30
EXAMPLE 20
Consider the following statements,The first two are
called premises and the third is called the conclusion,The
entire set is called an argument.
"All lions are fierce."
"Some lions do not drink coffee."
"Some fierce creatures do not drink coffee."
Let P(x),Q(x),and R(x) be the statements "x is a lion," "x is
fierce," and "x drinks coffee," respectively,Assuming that the
universe of discourse is the set of all creatures,express the
statements in the argument using quantifiers and P(x),Q(x),
and R(x).
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,31
EXAMPLE 21
Consider the following statements,of which the first three
are premises and the fourth is a valid conclusion.
"All hummingbirds are richly colored."
"No large birds live on honey."
"Birds that do not live on honey are dull in color."
"Hummingbirds are small."
Let P(x),Q(x),R(x),and S(x) be the statements "x is a
hummingbird," "x is large," "x lives on honey," and "x is richly
colored," respectively,Assuming that the universe of discourse is
the set of all birds,express the statements in the argument using
quantifiers and P(x),Q(x),R(x),and S(x).
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,32
EXAMPLE 22
Let Q(x,y) denote "x + y = 0." What are the truth values
of the quantifications y x Q(x,y) and x y Q(x,y)?
"There is a real number y such
that for every real number x,
Q(x,y) is true."
No matter what value of y is
chosen,there is only one value of
x for which x + y = 0,Since there
is no real number y such that x + y
= 0 for all real numbers x,the
statement is false.
"For every real number
x there is a real number y
such that Q(x,y) is true."
Given a real number x,
there is a real number y
such that x + y = 0; namely,
y =－ x,Hence,the
statement is true.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,33
EXAMPLE 23
Let Q(x,y,z) be the statement "x + y = z." What
are the truth values of the statements
x y zQ(x,y,z) and z x y Q(x,y,z)?
"For all real numbers x and
for all real numbers y there
is a real number z such that
x + y = z,"
the statement is true.
"There is a real number
z such that for all real
numbers x and for all
real numbers y it is true
that x + y = z,"
the statement is false.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,34
Table2
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,35
NEGATIONS
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,36
Table3
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,37
变量的约束（ BINDING VARIABLES）
1,自由变量（ Free Variable）
2,约束变量（ Bound Variable）
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,38
进一步的思考一、谓词公式的分类二、谓词公式的等价演算三、谓词公式的标准化形式
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,39
进一步的思考一、谓词公式的分类与命题公式真值讨论类似,可以描述谓词公式在指定变量 （ 包含非量化的个体变量和谓词变量 ）
后的真值情况,进而划分出永真公式或永假公式 。
定理 1 两个谓词公式 A和 B等值与且仅当 A?B
是永真公式 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,40
进一步的思考二、谓词公式的等价演算在判断谓词公式等价的运算中,所有命题公式的基本等值定律均适用,不过此时的 A,B,C都是谓词公式 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,41
进一步的思考定理 2 （ 基本量词等值定律 ）
E14：量词分配律
Vx（ A(x)∧ B(x)）VxA(x)∧ VxB(x)
x(A(x)∨ B(x)）xA(x)∨?xB(x)
另两种情况的思考,V与 ∨,?与 ∧
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,42
E15：量词扩张 /收缩律
Vx(P∨ B(x))P∨ VxB(x)
Vx(P∧ B(x))P∧ VxB(x)
x(P∨ B(x))P∨? xB(x)
x(P∧ B(x))P∧?x B(x)
这里 A,B是任意包括个体变量 x的谓词公式,P是不包括个体变量 x的任意谓词公式 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,43
例 证明
x(A(x)→ B(x)) VxA(x)→?xB(x)
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,44
进一步的思考三、谓词公式的标准化形式
prenex normal form(PNF),前束范式前束合取范式前束析取范式
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,45
小 结一、从命题到命题函数
N元谓词个体、个体变量、个体域二、从命题公式到谓词公式存在量词、全称量词
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,46
练 习 题
From pp,33 9,21,35,48（ b）
b
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,1
1.3 谓词与量词
Predicates and Quantifiers
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,2
前两节介绍的命题与命题演算是命题逻辑的内容，其基本组成单位是原子命题。一般地，原子命题作为具有真假意义的句子至少由主语和谓语两部分组成。
例如,电子商务是计算机技术的一个应用,这里“电子商务”是主语，
而“是 ……” 是谓语。当主语改变为“电子政务”时就得到新的原子命题：
电子政务是计算机技术的一个应用 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,3
由此可知，主语是独立存在的 个体 /值 /Value，而谓语用来描述该个体的性质或个体间的关系，这里我们称其为 谓词
/Predicate。用 P表示谓词“是 ……” 。则 P（电子商务）或 P
（电子政务）分别等值于前述两个命题的表达。将个体用变量
（称为 个体变量 ） x推广，则 P（ x）表示,x是计算机技术的一个新的应用 。这时该语句就不是一个命题，而是一个命题函数。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,4
定义 一个谓词 P连同相关的 n（ n≥0）个个体变量组成的表达式称为 n元谓词 （ n-predicate），记 P（ x1,x2,…,x n），其中 n是该表达式中不同个体变量的数目。 n元谓词也称 简单命题函数,将简单命题函数视为命题，按 1.1节定义 10得到的递归定义的表达式称为 复合命题函数 。简单命题函数和复合命题函数，统称为 命题函数 （ proposition function）。
DEFINITION 1,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,5
EXAMPLE 1
Let P(x) denote the statement "x > 3." What are
the truth values of P(4) and P(2)?
P (4) =,T.
P (2) =,F,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,6
EXAMPLE 2
Let Q(x,y) denote the statement "x = y + 3."
What are the truth values of the propositions
Q(1,2) and Q(3,0)?
Q(1,2)=,F.
Q(3,0)=,T.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,7
EXAMPLE 3
R(x,y,z),x+y=z
What are the truth values of the propositions
R(1,2,3) and R(0,0,1)?
R(1,2,3)=.T,
R(0,0,1)=.F.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,8
当 n>1时,通常 P给出了 xi(i=1,2,…,n)之间的关系 。
例如,P(x,y,z)表示 x位于 y与 z之间,是一个三元谓词 。
与 x,y,z分别用构件层,表现层,总线层代入时得到命题：构件层位于表现层与总线层之间,其命值真值为 T。 再如将杭州,
南京,北京代入,则得到：杭州位于南京和北京之间,真值为 F。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,9
为了进一步讨论命题函数 P(x)的真值情况,首先需要指定个 体 变 量 x 可 选 择 的 范 围,即 个 体 域 （ universe of
discourse,or domain） 。 每一个个体变量 x都有自己的个体域 。 如果没有特别指定的个体域,则缺省为一个 全个体域
（ total universe of discourse） 即任意个体均可以作为常量对 x代入 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,10
在指定个体变量 x的个体域后,该个体域中的每个个体 a代入到 P(x)中的所有 x,就对应一个可以判定真假意义的命题
P(a)。 不同的个体代入后所对应的命题真值可能不同,也可能相同 。
例如,P(x)表示为
x2–1=(x–1)(x+1) x指定的个体域为全体整数,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,11
则对任意整数 i，
i2–1=(i–1)(i+1)
恒成立 。 也就是说,该命题函数的真值无论用什么个体代入总是对应为 T。 此类命题函数的真值描述通过一个称为全称量词的特殊符号来量化 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,12
定义 2 命题函数 P(x)的 全称量化 （ universal quanification）
是一个按如下规则确定真值的命题：如果对每一个个体 a代入得到的 P(a)均为 T。 则该命题为 T。 记为 VxP(x)。 这里 V是 全称量词 （ universal quantifier）,表示为,对任意的,,,所有的,,,对每一个,等等 。
DEFINITION 2,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,13
DEFINITION 2,
The universal quantification of P(x) is the proposition
“P(x) is true for all values of x in the universe of
discourse.”
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,14
EXAMPLE 5
Express the statement
"Every student in this class has studied calculus"
as a universal quantification.
It can be written as
xP(x) or x (S(x)→ P(x))
P(x) = "x has studied calculus."
S(x) = "x is in this class."
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,15
EXAMPLE 8
What is the truth value of V x P(x),where P(x) is the
statement "x2 < 10" and the universe of discourse consists of
the positive integers not exceeding 4?
x P(x)=P(1) ∧ P(2) ∧ P(3) ∧ P(4) =,F.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,16
定义 3 命 题 函 数 P(x) 的 存 在 量 化 （ existential
quantification） 是一个按如下规则确定真值的命题：如果个体域中存在一个个体 a代入后得到 P(a)为 T,则该命题为 T,否则为 F 。 记?或? 。 这里?称为 存在量词 （ existential
quantification） 。 表示为,有一个,,,某些,,,某个,
等等 。
DEFINITION 3,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,17
DEFINITION 3,
The existential quantification of P(x) is the
proposition
“There exists an element x in the universe of
discourse such that P(x) is true.”
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,18
EXAMPLE 9
Let P(x) denote the statement "x > 3." What is the truth
value of the quantification x P(x),where the universe of
discourse is the set of real numbers?
Since "x>3" is true,for instance,when x=4 the
existential quantification of P(x),which is xP(x)
is true.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,19
EXAMPLE 10
Let Q(x) denote the statement "x = x + 1." What is the
truth value of the quantification xQ(x),where the universe
of discourse is the set of real numbers?
.F.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,20
EXAMPLE 11
What is the truth value of x P(x) where P(x) is the
statement "x2 > 10" and the universe of discourse consists
of the positive integers not exceeding 4?
x P(x)
=P(1) ∨ P(2)∨ P(3)∨ P(4)
=,T.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,21
Table1
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,22
定义 4 谓词公式定义为
（ 1） n元谓词是一个谓词公式；
（ 2） 若 A是谓词公式,则 （?A ） 也是谓词公式；
（ 3） 若 A,B是谓词公式,则 （ A∨ B）,（ A∧ B）,
（ A→ B）,（ AB） 也是谓词公式；
（ 4） 若 A是谓词公式且含有未被量化的个体变量 x,则
VxA(x),?XA(x)也是谓词公式 。
（ 5） 有限次地使用 （ 1） ~（ 4） 所得到的也是谓词公式 。
DEFINITION 4,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,23
EXAMPLE 12
Translate the statement
x (C(x)∨ y(C(y)∧ F(x,y)))
into English,where C(x) is "x has a computer," F(x,y) is "x
and y are friends," and the universe of discourse for both x
and y is the set of all students in ZJU.
The statement says that for every student x in ZJU x
has a computer or there is a student y such that y has a
computer and x and y are friends,In other words,every
student in ZJU has a computer or has a friend who has
a computer,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,24
EXAMPLE 13
Translate the statement
x y z(((F(x,y)∧ F(x,z)∧ (y≠z))→ F(y,z)))
into English,where F(a,b) means a and b are friends and
the universe of discourse for x,y,and z is the set of all
students in your school.
This statement says that there is a student x such that for
all students y and all students z other than y,if x and y are
friends and x and z are friends,then y and z are not
friends,In other words,there is a student none of whose
friends are also friends with each other.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,25
EXAMPLE 15
Express the statements "Some student in this class has
visited Mexico" and "Every student in this class has visited
either Canada or Mexico" using quantifiers.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,26
EXAMPLE 16
Express the statement "Everyone has exactly
one best friend" as a logical expression.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,27
EXAMPLE 17
Express the statement "If somebody is female and is a
parent,then this person is someone's mother" as a logical
expression.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,28
EXAMPLE 18
Use quantifiers to express the statement "There is a
woman who has taken a flight on every airline in the world."
P(w,f),w has taken a f.
Q(f,a),f is a flight on a,
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,29
EXAMPLE 19
(Calculus required) Express the definition of a
limit using quantifiers.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,30
EXAMPLE 20
Consider the following statements,The first two are
called premises and the third is called the conclusion,The
entire set is called an argument.
"All lions are fierce."
"Some lions do not drink coffee."
"Some fierce creatures do not drink coffee."
Let P(x),Q(x),and R(x) be the statements "x is a lion," "x is
fierce," and "x drinks coffee," respectively,Assuming that the
universe of discourse is the set of all creatures,express the
statements in the argument using quantifiers and P(x),Q(x),
and R(x).
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,31
EXAMPLE 21
Consider the following statements,of which the first three
are premises and the fourth is a valid conclusion.
"All hummingbirds are richly colored."
"No large birds live on honey."
"Birds that do not live on honey are dull in color."
"Hummingbirds are small."
Let P(x),Q(x),R(x),and S(x) be the statements "x is a
hummingbird," "x is large," "x lives on honey," and "x is richly
colored," respectively,Assuming that the universe of discourse is
the set of all birds,express the statements in the argument using
quantifiers and P(x),Q(x),R(x),and S(x).
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,32
EXAMPLE 22
Let Q(x,y) denote "x + y = 0." What are the truth values
of the quantifications y x Q(x,y) and x y Q(x,y)?
"There is a real number y such
that for every real number x,
Q(x,y) is true."
No matter what value of y is
chosen,there is only one value of
x for which x + y = 0,Since there
is no real number y such that x + y
= 0 for all real numbers x,the
statement is false.
"For every real number
x there is a real number y
such that Q(x,y) is true."
Given a real number x,
there is a real number y
such that x + y = 0; namely,
y =－ x,Hence,the
statement is true.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,33
EXAMPLE 23
Let Q(x,y,z) be the statement "x + y = z." What
are the truth values of the statements
x y zQ(x,y,z) and z x y Q(x,y,z)?
"For all real numbers x and
for all real numbers y there
is a real number z such that
x + y = z,"
the statement is true.
"There is a real number
z such that for all real
numbers x and for all
real numbers y it is true
that x + y = z,"
the statement is false.
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,34
Table2
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,35
NEGATIONS
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,36
Table3
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,37
变量的约束（ BINDING VARIABLES）
1,自由变量（ Free Variable）
2,约束变量（ Bound Variable）
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,38
进一步的思考一、谓词公式的分类二、谓词公式的等价演算三、谓词公式的标准化形式
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,39
进一步的思考一、谓词公式的分类与命题公式真值讨论类似,可以描述谓词公式在指定变量 （ 包含非量化的个体变量和谓词变量 ）
后的真值情况,进而划分出永真公式或永假公式 。
定理 1 两个谓词公式 A和 B等值与且仅当 A?B
是永真公式 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,40
进一步的思考二、谓词公式的等价演算在判断谓词公式等价的运算中,所有命题公式的基本等值定律均适用,不过此时的 A,B,C都是谓词公式 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,41
进一步的思考定理 2 （ 基本量词等值定律 ）
E14：量词分配律
Vx（ A(x)∧ B(x)）VxA(x)∧ VxB(x)
x(A(x)∨ B(x)）xA(x)∨?xB(x)
另两种情况的思考,V与 ∨,?与 ∧
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,42
E15：量词扩张 /收缩律
Vx(P∨ B(x))P∨ VxB(x)
Vx(P∧ B(x))P∧ VxB(x)
x(P∨ B(x))P∨? xB(x)
x(P∧ B(x))P∧?x B(x)
这里 A,B是任意包括个体变量 x的谓词公式,P是不包括个体变量 x的任意谓词公式 。
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,43
例 证明
x(A(x)→ B(x)) VxA(x)→?xB(x)
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,44
进一步的思考三、谓词公式的标准化形式
prenex normal form(PNF),前束范式前束合取范式前束析取范式
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,45
小 结一、从命题到命题函数
N元谓词个体、个体变量、个体域二、从命题公式到谓词公式存在量词、全称量词
Predicates and Quantifiers
谓词与量词
7/31/2009 11:27 AM Deren Chen,ZheJiang Univ,46
练 习 题
From pp,33 9,21,35,48（ b）
b
