左孝凌離散數(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變?cè)募s束(Bound of variable) 2.5謂詞演算的等價(jià)式與蘊(yùn)含式(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謂詞的概念與表示,原子命題,客體,謂詞,獨(dú)立存在的具體事物的或抽象的概念,刻畫客體的性質(zhì)、特征或關(guān)系,謂詞邏輯,人總是要死的,人,是要死的,客體,謂詞,在謂詞邏輯中，可將原子命題劃分為客體和謂詞兩部分,例如，電子計(jì)算機(jī)、李明、玫瑰花、黑板、實(shí)數(shù)、中國(guó)、思想、唯物主義等,是（個(gè)大學(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個(gè)客體需要插入固定的位置 例2、張三高于李四 解：H：高于，a：張三，b：李四 即H(a,b) 注：在多元謂詞表達(dá)式中，客體字母出現(xiàn)的先后次序與事先約定有關(guān),一般不可以隨意交換位置，如H(a,b) H(b,a),一、基本概念,8,定義：由一個(gè)謂詞H和n個(gè)客體變?cè)M成的表達(dá)式H(x1, x2 , , xn)稱為n元簡(jiǎn)單命題函數(shù). 客體變?cè)撼Ｓ眯懹⑽淖帜竫,y,z, 表示 客體常元：表示具體或特定的客體，常用小寫英文字母a,b,c, 表示 注： H(x1, x2 , , xn) 本身并不是一個(gè)命題.只有用特定的客體取代客體變?cè)獂,y,z后，它們才成為命題。 n元謂詞：即有n個(gè)客體變?cè)拿}函數(shù). 當(dāng)n=0時(shí),稱為0元謂詞，0元謂詞是一個(gè)命題.,2.2命題函數(shù)與量詞,二、命題函數(shù),比對(duì)： 1）命題邏輯中的命題變?cè)狝和命題常量（A：人是會(huì)死的） 2）謂詞邏輯中 命題函數(shù)H(x1, x2 , , xn) 將客體變?cè)貏e制定為客體常元后 H（a,b,c，）,9,復(fù)合命題函數(shù):由一個(gè)或幾個(gè)簡(jiǎn)單命題函數(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:將下列命題用謂詞符號(hào)化. (1) 2是素?cái)?shù)且是偶數(shù). (2) 如果2大于3,則2大于4. (3) 如果張明比李民高, 李民比趙亮高,則張明比趙亮高.,2.2命題函數(shù)與量詞,二、命題函數(shù),10,解:(1) 設(shè)F(x): x是素?cái)?shù). G(x): x是偶數(shù). 則命題符號(hào)化為： F(2)G(2) (2) 設(shè)L(x,y) ：x大于y. 則命題符號(hào)化為： L(2,3) L(2,4) (3) 設(shè) H(x,y): x比y高. a:張明 b:李民 c：趙亮 則命題符號(hào)化為： H(a,b)H(b ,c)H(a,c) 另：H(a,b)表示“張明不比李民長(zhǎng)得高”。,2.2命題函數(shù)與量詞,11,個(gè)體域：在命題函數(shù)中，客體變?cè)恼撌龇秶Q作個(gè)體域。 全總個(gè)體域:把各種個(gè)體域綜合在一起作為論述范圍的域（所有個(gè)體域的并）稱為全總個(gè)體域。 說明： 1)命題函數(shù)不是一個(gè)命題，只有其中的個(gè)體變?cè)锰囟▊€(gè)體或個(gè)體常元替代時(shí)，才能成為一個(gè)命題。 2)但是客體變?cè)谀男┓秶鷥?nèi)取特定的值，對(duì)命題函數(shù)是否成為命題及命題的真值極有影響。,2.2命題函數(shù)與量詞,二、命題函數(shù),P57-例4 R(x)表示“x是個(gè)大學(xué)生” 如果x的討論范圍為某大學(xué)里班級(jí)的學(xué)生，則R(x)是永真式。 如果x的討論范圍為某中學(xué)里班級(jí)的學(xué)生，則R(x)是永假式。 如果x的討論范圍為一個(gè)劇場(chǎng)中的觀眾，觀眾中有大學(xué)生也有非大學(xué)生，那么，對(duì)某些觀眾，R(x)為真，對(duì)另一些觀眾，R(x)為假。,若x，y，z 地面上的房子，且P(x,y)：x距離y 10米，則這個(gè)式子表示“x距離y10米且y距離z10米則x距離z10米”。這個(gè)命題的真值將由x，y，z的具體位置而定，它可能為T，也可能為F。,P57-例5,若x，y，z R（實(shí)數(shù)），且P(x,y)：x小于y，則這個(gè)式子表示“若x小于y且y小于z，則x小于z”。這是一永真式。,若 x，y，z 人，且P(x,y)解釋為：x為y的兒子，則這個(gè)式子表示“若x為y的兒子且y是z的兒子則x是z的兒子”。這是一個(gè)永假式。,P(x,z),一元謂詞P（x）表示客體的性質(zhì)；n（n 2）元謂詞表示客體之間的關(guān)系。 n元謂詞P（x1，x2，xn）是以客體變?cè)膫€(gè)體域?yàn)槎x域，以0,1(F,T)為值域的n元函數(shù)。 n元謂詞不是命題，只有將其中的客體變?cè)鎿Q為n個(gè)客體常元才能成為命題。 例：A(x,y):x y 當(dāng)a=3，b=4時(shí)，A(a，b)：3 4 為T 當(dāng)a=5，b=1時(shí)，A(a，b)：5 1 為F 當(dāng)a=2時(shí)，A(2，y)不是命題。 當(dāng)n=0時(shí)，稱為0元謂詞，是命題 命題函數(shù)是否能成為命題及命題的真值與客體變?cè)娜≈捣秶嘘P(guān)。,說明,15,量詞：全稱量詞()和存在量詞() 1.全稱量詞：用來表達(dá)“一切”、“所有”、“凡”、“每一個(gè)”、“任意”等詞，用符號(hào)“” 表示， 表示對(duì)個(gè)體域里的所有個(gè)體 ()表示個(gè)體域里的所有個(gè)體具有性質(zhì)F. 符號(hào)“”稱為存在量詞.,2.2命題函數(shù)與量詞,三、量詞,16,P58-例：在謂詞邏輯中將下列命題符號(hào)化. （1）凡是人都呼吸。 （2）每個(gè)學(xué)生都要參加考試。 (3) 任何整數(shù)或是正的或是負(fù)的。 解: (1) 當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)： 令F(x): x呼吸。則（1）符號(hào)化為xF(x) 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令M(x): x是人。則（1）符號(hào)化為 x(M(x) F(x).,2.2命題函數(shù)與量詞,17,(2) 當(dāng)個(gè)體域?yàn)槿w學(xué)生的集合時(shí)： 令P(x): x要參加考試。則（2）符號(hào)化為xP(x). 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令S(x): x是學(xué)生。則（2）符號(hào)化為 x(S(x) P(x). (3) 當(dāng)個(gè)體域?yàn)槿w整數(shù)的集合時(shí)： 令P(x): x是正的。N(x): x是負(fù)的。則（3）符號(hào)化為 x(P(x)N(x) . 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令I(lǐng)(x): x是整數(shù)。則（3）符號(hào)化為 x(I(x)(P(x)N(x).,2.2命題函數(shù)與量詞,18,2.存在量詞:用來表達(dá)“有一個(gè)”、“有的”、“存在著”、“至少有一個(gè)”、 “存在一些”等詞，用符號(hào)“” 表示 表示存在個(gè)體域里的個(gè)體， ()表示存在個(gè)體域里的個(gè)體具有性質(zhì)F. 符號(hào)“”稱為存在量詞. 例4：在謂詞邏輯中將下列命題符號(hào)化. （1）一些數(shù)是有理數(shù)。 （2）有些人活百歲以上。,三、量詞,2.2命題函數(shù)與量詞,19,解: (1)令Q(x): x是有理數(shù)。則（1）符號(hào)化為Q(x)。 （2）當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)： 令G(x): x活百歲以上。則（2）符號(hào)化為xG(x)。 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令M(x): x是人。則（2）符號(hào)化為 x(M(x) G(x),2.2命題函數(shù)與量詞,20,3.特性謂詞:限定客體變?cè)兓秶闹^詞，稱作特性謂詞。 例：“有些人沒有來上課” 要求：1）個(gè)體域?yàn)槿倐€(gè)體域，2）個(gè)體域?yàn)槿?解： 1）設(shè)M(x)：x是人，C(x)：x沒來上課 則命題符號(hào)化為：（x）(M(x) C(x) 2)設(shè)C(x)：x沒來上課 則命題符號(hào)化為：（x）C(x) 這里M(x)稱作特性謂詞，用來限定客體的取值范圍,三、量詞,2.2命題函數(shù)與量詞,21,如果沒有給出個(gè)體域，都應(yīng)該以全總個(gè)體域?yàn)閭€(gè)體域。 引入特性謂詞后，使用全稱量詞與存在量詞符號(hào)化的形式是不同的，一般： 全稱量詞(x)：特性謂詞作為條件式的前件 例：所有的人都是要呼吸的 M(x)：x是人 H(x):x要呼吸 命題符號(hào)化為： (x)(M(x) H(x). 存在量詞（x） ：特性謂詞作為合取項(xiàng) 例：有些人沒有來上課 M(x)：x是人 C(x):x沒來上課 命題符號(hào)化為： （x）(M(x) C(x),量詞使用小結(jié),2.2命題函數(shù)與量詞,22,多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能任意顛倒次序 例：“對(duì)任意的x,存在y, 使得x+y=5”, 個(gè)體域?yàn)镽, 則該命題符號(hào)化為: (x)(y)H(x,y).其中H(x,y): x+y=5. 為真 而 (y)(x)H(x,y)表示“某個(gè)（些）數(shù)y與任意其 他數(shù)的和為5” 完全不同的命題，真值為假 使一個(gè)命題函數(shù)成為命題，有兩種方法： 對(duì)客體變?cè)M(jìn)行指派。 如：P(x)：x是素?cái)?shù)，則P(5)為T,P(4)為F 對(duì)命題函數(shù)進(jìn)行量化 如：P(x)：x是素?cái)?shù)，則：（x）P(x)為T, （ x）P(x)為F,量詞使用小結(jié),2.2命題函數(shù)與量詞,23,練習(xí),例6：在謂詞邏輯中將下列命題符號(hào)化. （1）所有的人都長(zhǎng)頭發(fā)。 （2）有的人吸煙。 （3）沒有人登上過木星。 （4）清華大學(xué)的學(xué)生未必都是高素質(zhì)的。,24,解：令 M(x): x是人。（特性謂詞） （1） 令F(x): x長(zhǎng)頭發(fā)。則符號(hào)化為： （x）(M