1.1.3 謂詞與量詞

1、7/18/2022 9:06 PM11.1.3 謂詞與量詞 Predicates and Quantifiers7/18/2022 9:06 PM2前兩節(jié)介紹的命題與命題演算是命題邏輯的內(nèi)容，其基本組成單位是原子命題。一般地，原子命題作為具有真假意義的句子至少由主語和謂語兩部分組成。例如，電子商務(wù)是計(jì)算機(jī)技術(shù)的一個(gè)應(yīng)用系統(tǒng)，這里“電子商務(wù)”是主語，而“是”是謂語。當(dāng)主語改變?yōu)椤半娮诱?wù)”時(shí)就得到新的原子命題：電子政務(wù)是計(jì)算機(jī)技術(shù)的一個(gè)應(yīng)用系統(tǒng)。7/18/2022 9:06 PM3由此可知，主語是獨(dú)立存在的個(gè)體，而謂語用來描述該個(gè)體的性質(zhì)或個(gè)體間的關(guān)系，這里我們稱其為謂詞。用P表示謂詞“是”。則

2、P（電子商務(wù)）或P（電子政務(wù)）分別等值于前述兩個(gè)命題的表達(dá)。將個(gè)體用變量（稱為個(gè)體變量）x推廣，則P（x）表示：x是計(jì)算機(jī)技術(shù)的一個(gè)新的應(yīng)用系統(tǒng)。這時(shí)該語句就不是一個(gè)命題，而是一個(gè)命題函數(shù)。 7/18/2022 9:06 PM4定義 一個(gè)謂詞P連同相關(guān)的n（n0）個(gè)個(gè)體變量組成的表達(dá)式稱為n元謂詞（n-predicate），記P（x1, x2, , xn），其中n是該表達(dá)式中不同個(gè)體變量的數(shù)目。n元謂詞也稱簡單命題函數(shù)，將簡單命題函數(shù)視為命題，按1.1.1節(jié)定義10得到的遞歸定義的表達(dá)式稱為復(fù)合命題函數(shù)。簡單命題函數(shù)和復(fù)合命題函數(shù)，統(tǒng)稱為命題函數(shù)（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當(dāng)n1時(shí)，通常P給出了xi (i=1, 2, , n)之間的關(guān)系。例如，P(x, y, z)表示x位于y與z之間，是一個(gè)三元謂詞。與x, y, z分別用構(gòu)件層、表現(xiàn)層、總線層代入時(shí)得到命題：構(gòu)件層位于表現(xiàn)層與總線層之間，其命值真值為T。再如將杭州、南京、北京代入，則得到：杭

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

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

7、sal quantifier），表示為“對任意的”、“所有的”、“對每一個(gè)”等等。 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元謂詞是一個(gè)謂詞公式；（2）若A是謂詞公式，則（A）也是謂詞公式；（3）若A，B是謂詞公式，則（AB）、（AB）、（AB）、（AB）也是謂詞公式；（4）若A是謂詞公式且含有未被量化的個(gè)體變量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進(jìn)一