1、7/18/2022 9:06 PM11.1.3 謂詞與量詞 Predicates and Quantifiers7/18/2022 9:06 PM2前兩節介紹的命題與命題演算是命題邏輯的內容，其基本組成單位是原子命題。一般地，原子命題作為具有真假意義的句子至少由主語和謂語兩部分組成。例如，電子商務是計算機技術的一個應用系統，這里“電子商務”是主語，而“是”是謂語。當主語改變為“電子政務”時就得到新的原子命題：電子政務是計算機技術的一個應用系統。7/18/2022 9:06 PM3由此可知，主語是獨立存在的個體，而謂語用來描述該個體的性質或個體間的關系，這里我們稱其為謂詞。用P表示謂詞“是”。則

2、P（電子商務）或P（電子政務）分別等值于前述兩個命題的表達。將個體用變量（稱為個體變量）x推廣，則P（x）表示：x是計算機技術的一個新的應用系統。這時該語句就不是一個命題，而是一個命題函數。 7/18/2022 9:06 PM4定義 一個謂詞P連同相關的n（n0）個個體變量組成的表達式稱為n元謂詞（n-predicate），記P（x1, x2, , xn），其中n是該表達式中不同個體變量的數目。n元謂詞也稱簡單命題函數，將簡單命題函數視為命題，按1.1.1節定義10得到的遞歸定義的表達式稱為復合命題函數。簡單命題函數和復合命題函數，統稱為命題函數（proposition function）。

3、DEFINITION 1. 7/18/2022 9:06 PM5EXAMPLE 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. 7/18/2022 9:06 PM6 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)

4、= .T.7/18/2022 9:06 PM7EXAMPLE 3 R(x,y,z): x+y=zWhat 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.7/18/2022 9:06 PM8當n1時，通常P給出了xi (i=1, 2, , n)之間的關系。例如，P(x, y, z)表示x位于y與z之間，是一個三元謂詞。與x, y, z分別用構件層、表現層、總線層代入時得到命題：構件層位于表現層與總線層之間，其命值真值為T。再如將杭州、南京、北京代入，則得到：杭

5、州位于南京和北京之間，真值為F。與n=0時（即0元謂詞），命題函數就對應一個命題。7/18/2022 9:06 PM9為了進一步討論命題函數P(x)的真值情況，首先需要指定個體變量x可選擇的范圍，即個體域（universe of discourse, or domain）。每一個個體變量x都有自己的個體域。如果沒有特別指定的個體域，則缺省為一個全個體域（total universe of discourse）即任意個體均可以作為常量對x代入。7/18/2022 9:06 PM10在指定個體變量x的個體域后，該個體域中的每個個體a代入到P(x)中的所有x，就對應一個可以判定真假意義的命題P(a)

6、。不同的個體代入后所對應的命題真值可能不同，也可能相同。例如,P(x)表示為x21=(x1)(x+1) x指定的個體域為全體整數， 7/18/2022 9:06 PM11則對任意整數i， i21=(i1)(i+1)恒成立。也就是說，該命題函數的真值無論用什么個體代入總是對應為T。此類命題函數的真值描述通過一個稱為全稱量詞的特殊符號來量化。7/18/2022 9:06 PM12定義2 命題函數P(x)的全稱量化（universal quanification）是一個按如下規則確定真值的命題：如果對每一個個體a代入得到的P(a)均為T。則該命題為T。記為VxP(x)。這里V是全稱量詞（univer

7、sal quantifier），表示為“對任意的”、“所有的”、“對每一個”等等。 DEFINITION 2. 7/18/2022 9:06 PM13DEFINITION 2. The universal quantification of P(x) is the proposition “P(x) is true for all values of x in the universe of discourse.”7/18/2022 9:06 PM14EXAMPLE 5 Express the statement Every student in this class has studied

8、calculusas 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.7/18/2022 9:06 PM15EXAMPLE 8 What is the truth value of V x P(x), where P(x) is the statement x2 3. What is the truth value of the quantification x P(x), where the u

9、niverse of discourse is the set of real numbers? Since x3 is true, for instance, when x=4 the existential quantification of P(x), which is xP(x) is true.7/18/2022 9:06 PM19EXAMPLE 10 Let Q(x) denote the statement x = x + 1. What is the truth value of the quantification xQ(x), where the universe of d

10、iscourse is the set of real numbers?.F.7/18/2022 9:06 PM20EXAMPLE 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.7/18/2022 9:06 PM21Table17/18/2022 9:06 PM22定義4 謂詞公式定義

11、為（1）n元謂詞是一個謂詞公式；（2）若A是謂詞公式，則（A）也是謂詞公式；（3）若A，B是謂詞公式，則（AB）、（AB）、（AB）、（AB）也是謂詞公式；（4）若A是謂詞公式且含有未被量化的個體變量x，則VxA(x)，XA(x)也是謂詞公式。（5）有限次地使用（1）（4）所得到的也是謂詞公式。DEFINITION 4. 7/18/2022 9:06 PM23EXAMPLE 12 Translate the statementx (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

12、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 f

13、riend who has a computer. 7/18/2022 9:06 PM24EXAMPLE 13 Translate the statement x y z(F(x,y)F(x,z)(yz) 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

14、 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.7/18/2022 9:06 PM25EXAMPLE 15 Express the statements Some student in this

15、class has visited Mexico and Every student in this class has visited either Canada or Mexico using quantifiers.7/18/2022 9:06 PM26EXAMPLE 16 Express the statement Everyone has exactly one best friend as a logical expression.7/18/2022 9:06 PM27EXAMPLE 17 Express the statement If somebody is female an

16、d is a parent, then this person is someones mother as a logical expression.7/18/2022 9:06 PM28EXAMPLE 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. 7/18/2022 9:06 PM29EXAMPLE 19 (C

17、alculus required) Express the definition of a limit using quantifiers.7/18/2022 9:06 PM30EXAMPLE 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.

18、 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).7/

19、18/2022 9:06 PM31EXAMPLE 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)

20、, 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).7/18/2022 9:06 PM32EXAMPLE 22

21、 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

22、 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.7/18/2022 9:06 PM33EXAMPLE 23 Let Q(x, y, z

23、) 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.7/18/2022 9:06 PM34Table27/18/2022 9:06 PM35NEGATIONS7/18/2022 9:06 PM36Table37/18/2022 9:06 PM37進一