math-chap2-2.離散數(shù)學(xué)-謂詞邏輯

1、多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,1,第二章,謂詞邏輯,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,2,主要內(nèi)容,謂詞邏輯的基本概念謂詞公式謂詞邏輯等值式謂詞邏輯推理,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,3,命題邏輯的不足之處,命題邏輯研究的對象為命題(為一個完整的陳述句)，對于原子命題不可分。例魚兒離不開水。鯽魚是魚。所以鯽魚離不開水。簡單命題之間

2、的內(nèi)在聯(lián)系需要通過進(jìn)一步分析原子命題中主、謂等之間的關(guān)系。個體謂詞量詞,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,4,個體,定義：可以獨(dú)立存在的客觀實(shí)體稱為個體。具體事物抽象概念例小王和小明是同學(xué)。a能被2整除。x是有理數(shù)。個體常項(xiàng)：表示具體或特定的個體，常用字母a,b,c...表示；個體變項(xiàng)：表示抽象或泛指的個體，常用字母x,y,z...表示；個體域：個體變項(xiàng)的取值范圍，也稱論域。全總個體

3、域：宇宙間一切事物組成的個體域。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,5,謂詞,定義：刻畫個體具有的性質(zhì)或個體之間關(guān)系的詞。謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系的謂詞。謂詞變項(xiàng)：表示抽象的或泛指的謂詞。謂詞符號通常用大寫字母表示。例：F：...和...是同學(xué)。G：...能被...整除。H：...是有理數(shù)。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,6,謂詞,元數(shù)：謂詞中包含的個體變項(xiàng)數(shù)

4、。含n個個體變項(xiàng)的謂詞稱為n元謂詞。0元謂詞：不帶個體變項(xiàng)的謂詞。命題均可以表示成0元謂詞。例：4=3+1如果2是素?cái)?shù)，則3是素?cái)?shù)。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,7,量詞,定義：表示個體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞。全稱量詞：一切的、所有的、每一個、任意的、都...。符號化為“?”。表示個體域里的所有個體關(guān)系。存在量詞：存在、有一個、有的、至少有一個...。符號化為“?”。表示個體域里有的個

5、體關(guān)系。例所有人都需要呼吸空氣。有的人沒來上課。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,8,量詞,量詞需要注意個體域的問題。在不同的個體域內(nèi)，命題的真值可能不同。例：存在x，使得x+3=2。個體域?yàn)樽匀粩?shù)個體域?yàn)檎麛?shù)特性謂詞：將某類個體從個體域中區(qū)分出來的謂詞。M(x)：x是人；F(x)：x是魚；Z(x)：x是整數(shù)。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,9,命題符號化

6、,明確命題個體域，分別找出個體常項(xiàng)、個體變項(xiàng)、量詞和謂詞；按照命題的意思用邏輯聯(lián)結(jié)詞將其組合；注意：引入特性謂詞時，全稱量詞的特性謂詞作為命題的前提引入，而存在量詞的特性謂詞作為命題的合取項(xiàng)引入；多個量詞同時出現(xiàn)，需要注意量詞的順序不能隨意顛倒。例：并非所有的人都愛看電視。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,10,一階謂詞的例,火車比汽車跑得快。有理數(shù)可以表示成分?jǐn)?shù)。有的女孩不喜歡穿裙子。,多

7、媒體中心 莊伯金 bjzhuang@bupt.edu.cn,11,謂詞公式,謂詞公式的符號集個體常項(xiàng)：a,b,c,...個體變項(xiàng)：x,y,z,...函數(shù)符號：f,g,h,...謂詞符號：F,G,H,...量詞：?, ?;聯(lián)結(jié)詞符號：¬,∧,∨,→,?;括號：),(,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,12,謂詞公式,謂詞公式的項(xiàng)的遞歸定義個體常項(xiàng)和個體變項(xiàng)是項(xiàng)；若f(x1,x2,..

8、.,xn)是任意的n元函數(shù)，t1,t2,...,tn是任意n個項(xiàng)，則f(t1,t2,...,tn)是項(xiàng)；所有的項(xiàng)都由有限次使用上述兩條規(guī)定得到。原子公式：設(shè)R(x1,x2,...,xn)是符號集上任意n元謂詞，t1,t2,...,tn是符號集的任意n個項(xiàng)，則稱R(t1,t2,...,tn)為原子公式。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,13,合式公式,定義(1)原子公式是合式公式；(2)若A是合式公式

9、，則(¬A)也是合式公式(3)若A，B是合式公式，則(A∧B)，(A∨B)，(A→B)，(A?B)也是合式公式；(4)若A是合式公式，則?xA，?xA也是合式公式；(5)只有有限次的應(yīng)用(1)-(4)得到的符號串才是合式公式。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,14,約束變項(xiàng)及自由變項(xiàng),定義： ?xF，?xF中，x稱為指導(dǎo)變項(xiàng)，F(xiàn)稱為相應(yīng)量詞的轄域。轄域中x的所有出現(xiàn)稱為約束出現(xiàn)，x稱為約束變

10、項(xiàng)，F(xiàn)中不是約束出現(xiàn)的其他變項(xiàng)稱為自由變項(xiàng)。例?x F(x)→?y G(x,y)?x(F(x,y)∧?y(G(x,y))?x?y(F(x,y)∧G(y,z))∨H(x,y)閉式：若合式公式中無自由出現(xiàn)的個體變項(xiàng)，則稱A為封閉的公式，簡稱閉式。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,15,變項(xiàng)替換規(guī)則,變項(xiàng)替換的目的：為了避免個體變項(xiàng)的混淆。規(guī)則約束變項(xiàng)換名規(guī)則：將量詞轄域中出現(xiàn)的某個約束變項(xiàng)及其對應(yīng)

11、的指導(dǎo)變項(xiàng)改成公式中未出現(xiàn)的個體變項(xiàng)符號，其余部分不變。自由變項(xiàng)代替規(guī)則：將公式中某自由變項(xiàng)用原公式中未出現(xiàn)過的某個個體變項(xiàng)符號代替，且處處代替。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,16,謂詞公式的解釋,定義：為使公式成為真值確定的命題而指定的有關(guān)規(guī)定，稱為謂詞公式的一個解釋。解釋I的組成特定的個體域DD中一部分特定元素D上每個函數(shù)變項(xiàng)所取得的具體函數(shù)D上每個謂詞變項(xiàng)所取的具體謂詞例： ?x(F

12、(f(x))→G(x)),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,17,謂詞公式的分類,謂詞公式的分類：如果A在任何解釋下都為真，則稱A為永真式（邏輯有效式）。如果A在任何解釋下都為假，則稱A為永假式（矛盾式）。若至少存在一組A的解釋使A為真，則稱A為可滿足式。代換實(shí)例：設(shè)A0是含命題變項(xiàng)p1,p2,...,pn的命題公式，A1,A2,...,An是n個謂詞公式。用Ai代換A0中的每一個pi，所得的公式A稱

13、為A0的代換實(shí)例。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,18,謂詞公式的定理,定理：命題公式中的重言式的代換實(shí)例在謂詞公式中為邏輯有效式；命題公式中的矛盾式的代換實(shí)例是謂詞公式中仍為矛盾式。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,19,謂詞邏輯等值式,等值式的定義：設(shè)謂詞邏輯中任意兩個公式A和B，若A?B是是邏輯有效式，則稱A與B為等值式。記作A?B。原命題等值式的代換實(shí)例都是等值

14、式。消去量詞等值式：設(shè)個體域D＝{a1,a2,...,an}?xA(x)?A(a1)∧A(a2)∧...∧A(an)?xA(x)?A(a1)∨A(a2)∨...∨A(an)量詞否定等值式¬?xA(x) ??x¬A(x) ¬?xA(x) ??x¬A(x),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,20,謂詞邏輯等值式,量詞轄域擴(kuò)張和伸縮等值式?x(A(x)∨B)??

15、xA(x)∨B ?x(A(x)∨B)??xA(x)∨B?x(A(x)∧B)??xA(x)∧B?x(A(x)∧B)??xA(x)∧B?x(A(x)→B)??xA(x)→B?x(A(x)→B)??xA(x)→B?x(B→A(x))?B→?xA(x)?x(B→A(x))?B→?xA(x),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,21,謂詞邏輯等值式,量詞分配等值式?x(A(x)∧B(x))??xA(x)∧

16、?xB(x)?x(A(x)∨B(x))??xA(x)∨?xB(x)量詞交換等值式?x?yA(x,y) ??y?xA(x,y) ? x?yA(x,y) ??y?xA(x,y),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,22,前束范式,定義：設(shè)A為謂詞邏輯公式，若A具有形式Q1x1Q2x2...QnxnB，其中Qi 為?或? ，B為不含量詞的公式。存在定理：任何謂詞邏輯公式都存在與之等值的前束范式。,前束范式,

17、例：?xF(x)→?xG(x)(?xF(x,y)→?yG(y))→?xH(x,y),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,23,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,24,作業(yè)(1),P53 2.1 (2)(3)(4) P53 2.2 (2)(3)P53 2.3 (3)(4)P54 2.5 (1),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,25,作業(yè)(