左孝凌離散數(shù)學(xué)課件2.1謂詞概念與表示-2.2命題函數(shù)與量詞.ppt

離散數(shù)學(xué)(Discrete Mathematics),第二章 謂詞邏輯,2.1謂詞的概念與表示(Predicate and its expression) 2.2命題函數(shù)與量詞(Propositional functions & Quantifiers) 2.3謂詞公式與翻譯(Predicate formulae) 2.4變元的約束(Bound of variable) 2.5謂詞演算的等價式與蘊含式(Equivalences & implications of predicate calculus) 2.6前束范式(Prenex normal form) 2.7謂詞演算的推理理論(Inference theory of predicate calculus),著名的蘇格拉底三段論,所有的人都是要死的P， 蘇格拉底是人Q， 前提：P Q,所以蘇格拉底總是要死的R 結(jié)論：R,PQ R或,(P Q) R T,命題邏輯,R,所有的人都是要死的,前提：所有A都要B 蘇格拉底是人， 前提：C是A,所以蘇格拉底總是要死的 結(jié)論：C是要B,所有A都要B,C是A,謂詞邏輯,R,C要B,命題邏輯的局限性：,第二章 謂詞邏輯,原因：在命題邏輯中，命題是命題演算的基本單位，原子命題不再進(jìn)行分解，因而無法研究命題的內(nèi)部結(jié)構(gòu)、成分及命題之間的內(nèi)在聯(lián)系,因而不能將命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系反映出來。 解決辦法：將命題進(jìn)行分解。,2.1謂詞的概念與表示,原子命題,客體,謂詞,獨立存在的具體事物的或抽象的概念,刻畫客體的性質(zhì)、特征或關(guān)系,謂詞邏輯,人總是要死的,人,是要死的,客體,謂詞,在謂詞邏輯中，可將原子命題劃分為客體和謂詞兩部分,例如，電子計算機(jī)、李明、玫瑰花、黑板、實數(shù)、中國、思想、唯物主義等,是（個大學(xué)生） 大于 繞著轉(zhuǎn) 位于與之間,2.1謂詞的概念與表示,客體 謂詞 表示方法：謂詞用大寫字母，客體用小寫字母 例1、采用謂詞表示下列命題 1) 地球繞著太陽轉(zhuǎn)； 2）濟(jì)南位于北京與南京之間； 3）張三是大學(xué)生，李四是工人 解：1）設(shè)：L:繞著轉(zhuǎn)，a：地球；b：太陽 即，L(a，b) 2）設(shè)：L：位于與之間，a：濟(jì)南；b：北京；c：南京 即L(a，b，c) 3）設(shè)：A：是，a：張三，b：李四，s：大學(xué)生，w：工人 即A(a，s)，A(b,w),一、基本概念,2.1謂詞的概念與表示,n元謂詞 ：A是謂詞，a1，a2，an是客體的名稱，則A(a1，a2，an)是n元謂詞，這里n個客體需要插入固定的位置 例2、張三高于李四 解：H：高于，a：張三，b：李四 即H(a,b) 注：在多元謂詞表達(dá)式中，客體字母出現(xiàn)的先后次序與事先約定有關(guān),一般不可以隨意交換位置，如H(a,b) H(b,a),一、基本概念,8,定義：由一個謂詞H和n個客體變元組成的表達(dá)式H(x1, x2 , , xn)稱為n元簡單命題函數(shù). 客體變元：常用小寫英文字母x,y,z, 表示 客體常元：表示具體或特定的客體，常用小寫英文字母a,b,c, 表示 注： H(x1, x2 , , xn) 本身并不是一個命題.只有用特定的客體取代客體變元x,y,z后，它們才成為命題。 n元謂詞：即有n個客體變元的命題函數(shù). 當(dāng)n=0時,稱為0元謂詞，0元謂詞是一個命題.,2.2命題函數(shù)與量詞,二、命題函數(shù),比對： 1）命題邏輯中的命題變元A和命題常量（A：人是會死的） 2）謂詞邏輯中 命題函數(shù)H(x1, x2 , , xn) 將客體變元特別制定為客體常元后 H（a,b,c，）,9,復(fù)合命題函數(shù):由一個或幾個簡單命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式. 例3:若x的學(xué)習(xí)好,則x的工作好 設(shè)S(x):x學(xué)習(xí)好；W(x):x工作好， 則有 S(x) W(x) 另外：S(x)表示“x學(xué)習(xí)不是很好”。 S(x)W(x)表示“x的學(xué)習(xí)，工作都很好”。 例4:將下列命題用謂詞符號化. (1) 2是素數(shù)且是偶數(shù). (2) 如果2大于3,則2大于4. (3) 如果張明比李民高, 李民比趙亮高,則張明比趙亮高.,2.2命題函數(shù)與量詞,二、命題函數(shù),10,解:(1) 設(shè)F(x): x是素數(shù). G(x): x是偶數(shù). 則命題符號化為： F(2)G(2) (2) 設(shè)L(x,y) ：x大于y. 則命題符號化為： L(2,3) L(2,4) (3) 設(shè) H(x,y): x比y高. a:張明 b:李民 c：趙亮 則命題符號化為： H(a,b)H(b ,c)H(a,c) 另：H(a,b)表示“張明不比李民長得高”。,2.2命題函數(shù)與量詞,11,個體域：在命題函數(shù)中，客體變元的論述范圍稱作個體域。 全總個體域:把各種個體域綜合在一起作為論述范圍的域（所有個體域的并）稱為全總個體域。 說明： 1)命題函數(shù)不是一個命題，只有其中的個體變元用特定個體或個體常元替代時，才能成為一個命題。 2)但是客體變元在哪些范圍內(nèi)取特定的值，對命題函數(shù)是否成為命題及命題的真值極有影響。,2.2命題函數(shù)與量詞,二、命題函數(shù),P57-例4 R(x)表示“x是個大學(xué)生” 如果x的討論范圍為某大學(xué)里班級的學(xué)生，則R(x)是永真式。 如果x的討論范圍為某中學(xué)里班級的學(xué)生，則R(x)是永假式。 如果x的討論范圍為一個劇場中的觀眾，觀眾中有大學(xué)生也有非大學(xué)生，那么，對某些觀眾，R(x)為真，對另一些觀眾，R(x)為假。,若x，y，z 地面上的房子，且P(x,y)：x距離y 10米，則這個式子表示“x距離y10米且y距離z10米則x距離z10米”。這個命題的真值將由x，y，z的具體位置而定，它可能為T，也可能為F。,P57-例5,若x，y，z R（實數(shù)），且P(x,y)：x小于y，則這個式子表示“若x小于y且y小于z，則x小于z”。這是一永真式。,若 x，y，z 人，且P(x,y)解釋為：x為y的兒子，則這個式子表示“若x為y的兒子且y是z的兒子則x是z的兒子”。這是一個永假式。,P(x,z),一元謂詞P（x）表示客體的性質(zhì)；n（n 2）元謂詞表示客體之間的關(guān)系。 n元謂詞P（x1，x2，xn）是以客體變元的個體域為定義域，以0,1(F,T)為值域的n元函數(shù)。 n元謂詞不是命題，只有將其中的客體變元替換為n個客體常元才能成為命題。 例：A(x,y):x y 當(dāng)a=3，b=4時，A(a，b)：3 4 為T 當(dāng)a=5，b=1時，A(a，b)：5 1 為F 當(dāng)a=2時，A(2，y)不是命題。 當(dāng)n=0時，稱為0元謂詞，是命題 命題函數(shù)是否能成為命題及命題的真值與客體變元的取值范圍有關(guān)。,說明,15,量詞：全稱量詞()和存在量詞() 1.全稱量詞：用來表達(dá)“一切”、“所有”、“凡”、“每一個”、“任意”等詞，用符號“” 表示， 表示對個體域里的所有個體 ()表示個體域里的所有個體具有性質(zhì)F. 符號“”稱為存在量詞.,2.2命題函數(shù)與量詞,三、量詞,16,P58-例：在謂詞邏輯中將下列命題符號化. （1）凡是人都呼吸。 （2）每個學(xué)生都要參加考試。 (3) 任何整數(shù)或是正的或是負(fù)的。 解: (1) 當(dāng)個體域為人類集合時： 令F(x): x呼吸。則（1）符號化為xF(x) 當(dāng)個體域為全總個體域時： 令M(x): x是人。則（1）符號化為 x(M(x) F(x).,2.2命題函數(shù)與量詞,17,(2) 當(dāng)個體域為全體學(xué)生的集合時： 令P(x): x要參加考試。則（2）符號化為xP(x). 當(dāng)個體域為全總個體域時： 令S(x): x是學(xué)生。則（2）符號化為 x(S(x) P(x). (3) 當(dāng)個體域為全體整數(shù)的集合時： 令P(x): x是正的。N(x): x是負(fù)的。則（3）符號化為 x(P(x)N(x) . 當(dāng)個體域為全總個體域時： 令I(lǐng)(x): x是整數(shù)。則（3）符號化為 x(I(x)(P(x)N(x).,2.2命題函數(shù)與量詞,18,2.存在量詞:用來表達(dá)“有一個”、“有的”、“存在著”、“至少有一個”、 “存在一些”等詞，用符號“” 表示 表示存在個體域里的個體， ()表示存在個體域里的個體具有性質(zhì)F. 符號“”稱為存在量詞. 例4：在謂詞邏輯中將下列命題符號化. （1）一些數(shù)是有理數(shù)。 （2）有些人活百歲以上。,三、量詞,2.2命題函數(shù)與量詞,19,解: (1)令Q(x): x是有理數(shù)。則（1）符號化為Q(x)。 （2）當(dāng)個體域為人類集合時： 令G(x): x活百歲以上。則（2）符號化為xG(x)。 當(dāng)個體域為全總個體域時： 令M(x): x是人。則（2）符號化為 x(M(x) G(x),2.2命題函數(shù)與量詞,20,3.特性謂詞:限定客體變元變化范圍的謂詞，稱作特性謂詞。 例：“有些人沒有來上課” 要求：1）個體域為全總個體域，2）個體域為人 解： 1）設(shè)M(x)：x是人，C(x)：x沒來上課 則命題符號化為：（x）(M(x) C(x) 2)設(shè)C(x)：x沒來上課 則命題符號化為：（x）C(x) 這里M(x)稱作特性謂詞，用來限定客體的取值范圍,三、量詞,2.2命題函數(shù)與量詞,21,如果沒有給出個體域，都應(yīng)該以全總個體域為個體域。 引入特性謂詞后，使用全稱量詞與存在量詞符號化的形式是不同的，一般： 全稱量詞(x)：特性謂詞作為條件式的前件 例：所有的人都是要呼吸的 M(x)：x是人 H(x):x要呼吸 命題符號化為： (x)(M(x) H(x). 存在量詞（x） ：特性謂詞作為合取項 例：有些人沒有來上課 M(x)：x是人 C(x):x沒來上課 命題符號化為： （x）(M(x) C(x),量詞使用小結(jié),2.2命題函數(shù)與量詞,22,多個量詞同時出現(xiàn)時，不能任意顛倒次序 例：“對任意的x,存在y, 使得x+y=5”, 個體域為R, 則該命題符號化為: (x)(y)H(x,y).其中H(x,y): x+y=5. 為真 而 (y)(x)H(x,y)表示“某個（些）數(shù)y與任意其 他數(shù)的和為5” 完全不同的命題，真值為假 使一個命題函數(shù)成為命題，有兩種方法： 對客體變元進(jìn)行指派。 如：P(x)：x是素數(shù)，則P(5)為T,P(4)為F 對命題函數(shù)進(jìn)行量化 如：P(x)：x是素數(shù)，則：（x）P(x)為T, （ x）P(x)為F,量詞使用小結(jié),2.2命題函數(shù)與量詞,23,練習(xí),例6：在謂詞邏輯中將下列命題符號化. （1）所有的人都長頭發(fā)。 （2）有的人吸煙。 （3）沒有人登上過木星。 （4）清華大學(xué)的學(xué)生未必都是高素質(zhì)的。,24,解：令 M(x): x是人。（特性謂詞） （1） 令F(x): x長頭發(fā)。則符號化為： （x）(M