離散數(shù)學(xué) 第7章 謂詞邏輯

1、離 散 數(shù) 學(xué)第3編 數(shù)理邏輯第七章第七章 謂詞邏輯謂詞邏輯7.1 謂詞的概念及表示 一、命題的構(gòu)成 原子命題是由主語(yǔ)和謂語(yǔ)兩部分構(gòu)成的。 主語(yǔ)個(gè)體詞 主語(yǔ)的取值范圍稱為個(gè)體域 個(gè)體(客體)常用a、b、c等表示。 謂語(yǔ)表述客體的性質(zhì)和客體間關(guān)系的詞。 謂語(yǔ)(謂詞)常用A(x)、B(x)、P(x,y)等表示。 謂詞不是命題，只有當(dāng)謂詞中的變項(xiàng)取定具體的個(gè)體值時(shí)才是命題。 所以，A(a)、B(a)、F(a,b)等才是命題。一、命題函數(shù)1簡(jiǎn)單命題函數(shù) 表示一般謂詞的式子如A(x)、P(x,y)，稱為簡(jiǎn)單命題函數(shù)。2。復(fù)合命題函數(shù) 有限個(gè)簡(jiǎn)單命題函數(shù)和聯(lián)結(jié)詞 組成的表達(dá)式稱為復(fù)合命題函數(shù)。3。命題函數(shù)

2、本身不是命題，只有命題函數(shù)中的變?cè)〉锰囟ǖ闹岛蟛攀敲}。 ,7.2 命題函數(shù)與量詞 二、量詞表達(dá)個(gè)體在個(gè)體域中取值情況的詞稱為量詞。量詞有全稱量詞和存在量詞兩種。 1。全稱量詞 表示個(gè)體的取值情況為“所有的”、“每一個(gè)”等。特性謂詞后面用 聯(lián)結(jié)。例如，命題：所有的素?cái)?shù)都是整數(shù)，符號(hào)化為：A(x):x是素?cái)?shù)，H(x):x是整數(shù)，2。存在量詞 表示個(gè)體的取值情況為“存在某個(gè)”、“至少有一個(gè)”等。特性謂詞后面用 聯(lián)結(jié)。例如，命題：有的素?cái)?shù)是偶數(shù)，符號(hào)化為：A(x):x是素?cái)?shù)，M(x):x是偶數(shù)，)()()(xHxAx)()()(xMxAx2000年1月選擇題1 = 2006年1月填空題7 設(shè)F(x

3、):x是鳥(niǎo)，G(x):x會(huì)飛，命題“鳥(niǎo)都會(huì)飛”符號(hào)化為 。 A） B） C） D）再如課本P.42 (B) 1設(shè)A(x):x是人，B(x):x犯錯(cuò)誤，命題“沒(méi)有不犯錯(cuò)誤的人”可符號(hào)化為 。解：原命題的意思是：不存在不犯錯(cuò)誤的人。符號(hào)化為：)()()(xGxFx)()()(xGxFx)()()(xGxFx)()()(xGxFx)()()(xBxAxB三、多個(gè)量詞的使用 包含有多個(gè)個(gè)體的命題，可能會(huì)對(duì)不同的個(gè)體使用不同的量詞。對(duì)這樣的命題符號(hào)化時(shí)要注意：1。量詞的順序不能改變，否則會(huì)改變命題的含義。2。特性謂詞后面的聯(lián)結(jié)符通常由括號(hào)最前面的量詞決定。例如， 2000年7月填空題6設(shè)N(x):x是自

4、然數(shù)，H(x,y):y是x的后繼數(shù)，命題“每個(gè)自然數(shù)都有后繼數(shù)”可符號(hào)化為 。解：),()()()()(yxHxBxAyx),()()()()(yxHxBxAyx),()()()()(yxHyNyxNx2000年7月選擇題2 設(shè)個(gè)體域?yàn)檎麛?shù)，下列公式中真值為1的是 A） B） C） D）解：各答案的意義是：任取一個(gè)x和任取一個(gè)z，都滿足x+z=0任取一個(gè)x，存在一個(gè)t，滿足x+t=0存在一個(gè)y，對(duì)于任取的一個(gè)z，滿足y+z=0不存在這樣的u，v，滿足u+v=0A) 正確答案為B)0)()(zxzx)0)()(txtx)0)()(zyzy)0)()(vuvu7.3 謂詞公式的翻譯與解釋一、謂詞公

5、式 1。原子公式 若 是n元函數(shù)， 是個(gè)體變?cè)?，則 是原子命題公式。 2。合式公式 原子公式是合式公式， 若A、B是合式公式，則 也是合式公式， 若A是合式公式，x是A中出現(xiàn)的變?cè)?，則 也是合式公式， 有限次地使用構(gòu)成的公式是合式公式。),(21nxxxPnxxx,21),(21nxxxP)(),(),(BABAA)(),(BABAAxAx)( ,)(一、變?cè)?在合式公式 中， x：指導(dǎo)變?cè)?，A：量詞 的轄域。 若A中有x，則x稱為約束變?cè)?若A中無(wú)x，則x稱為自由變?cè)?。例如?中， x是約束變?cè)?，約束出現(xiàn)2次， y是自由變?cè)?的轄域是 ，即約束變?cè)竺胬ㄌ?hào)內(nèi)的式子是轄域。 量詞只對(duì)轄域中

6、的指導(dǎo)變?cè)行?。AxAx)()(和 ,),()()(yxGxFx),()(yxGxFx7.4 變?cè)募s束2001年7月選擇題2 表達(dá)式中 的轄域是（ ）。 A） B） C） D）2004年1月選擇題3 設(shè)個(gè)體域是整數(shù)集，P：下面4個(gè)命題中為真的是 ( ) (A) P是真命題 (B) P是假命題 (C) P是謂詞公式，但不是命題 (D) P不是謂詞公式 )(),()()(),()(zzQyxRyzQyxPx),(yxP)(),(zQyxP),(yxR),(),(yxRyxPx)()()(xyxyxyxBB二、換名規(guī)則和代入規(guī)則 在同一個(gè)合式公式中，一個(gè)變?cè)瓤赡芗s束出現(xiàn)，又可能自由出現(xiàn)。為避免混

7、淆，可采用換名的辦法使約束情況更加清楚。 1。換名規(guī)則對(duì)約束變?cè)獡Q名 把公式中量詞的指導(dǎo)變?cè)捌漭犛蛑械脑撟冊(cè)獡Q成公式中沒(méi)有出現(xiàn)的新變?cè)渌糠植蛔儭?2。代入規(guī)則對(duì)自由變?cè)獡Q名 把公式中的自由變?cè)霉街袥](méi)有出現(xiàn)的新變?cè)娲?，并且處處替代?公式經(jīng)換名和代入后，公式的意義不應(yīng)當(dāng)改變。2005年7月化簡(jiǎn)解答題13 將謂詞公式中的約束變?cè)獡Q名。（請(qǐng)按約束變?cè)霈F(xiàn)的順序，使用字母 等）解： ),()()()(),()()()(zxSzxRxzxQxRxPxtswvu,),()()()(),()()()(zxSzxRxzxQxRxPx),()()()(),()()()(wxSwvRvzuQuRu

8、Pu7.5 謂詞的等值演算一、解釋或賦值 對(duì)謂詞公式中的個(gè)體變?cè)?、函?shù)變項(xiàng)、謂詞變?cè)弥付ǖ某ｍ?xiàng)去替代，所得到的結(jié)果稱為對(duì)謂詞公式的一個(gè)解釋或賦值 I 。消去量詞的規(guī)則： 在有限個(gè)體域下，可按下列規(guī)則消去量詞。 例如：,21naaaD)()()()()(21naAaAaAxAx)()()()()(21naAaAaAxAx2001年1月填空題6 設(shè)個(gè)體域 ,公式 消去量詞可化為 。2003年1月填空題8 設(shè)個(gè)體域D1,2,那么謂詞公式消去量詞后的等值式 。2005年1月填空題7 設(shè)個(gè)體域 ，公式消去量詞為 。 )()()()(yGyxFx,cbaD )()()()()()(cGbGaGcFbFa

9、F)()(yyBxxA)2() 1 ()2() 1 (BBAA,baD ),()(yxyHxGx),(),()(),(),()(bbHabHbGbaHaaHaG二、謂詞公式的分類(lèi) 在給定的解釋下，謂詞公式的值稱為謂詞公式的真值。真值可以為1，也可以為0。 如果個(gè)體域有限，求謂詞公式的真值，可以消去量詞，把函數(shù)值代入謂詞，即可求出。 如果謂詞公式在任何解釋下都為真，稱為永真式，在任何解釋下都為假，稱為永假式或矛盾式，若至少有一個(gè)解釋下為真稱為可滿足式。 要判斷一個(gè)謂詞公式是永真式還是永假式，是較困難的。簡(jiǎn)單公式當(dāng)然一眼就可看出，稍復(fù)雜一點(diǎn)就只能通過(guò)下面所講的等值演算法化簡(jiǎn)。如公式等值于1，則為永

10、真式；如公式等值于0，則為永假式。例1，已知解釋 I 如下： 解：2)3(, 3)2()3(,2)2(, 3 , 2) 1 (ffaD3 , 2, 1),(, 1)3(, 0)2()4(jijiQPP的真值和求)(,()(),()(afxQxfPxaxQxPx),()(axQxPx)(,()(afxQxfPx010) 11 () 10()2 , 3()3()2 , 2()2(QPQP)2(, 3()3()2(, 2()2(fQfPfQfP)3 , 3()2()3 , 2()3(QPQP101) 10() 11 (三、謂詞公式的等值演算 謂詞公式在等值演算下，可以有不同的表現(xiàn)形式其中特別要記住的

11、有： )()()()(xBxAxxBxAx)()()()(xBxAxxxBxxA),(),(yxxAyyxyAx)()()()(xxBxxAxxBxxA)()(),()(xAxxxAxAxxxA)()()()(xBxAxxxBxxA)()()()(yBxAyxxxBxxA)()()()(yBxAyxxxBxxA),(),(yxxAyyxyAx2000年1月化簡(jiǎn)解答題12 通過(guò)等值演算說(shuō)明下列等值式成立：解：)()()()()()()(xQxxPxxQxPx)()()(xQxPx)()()()(xQxxPx)()()(xQxPx)()()()(xQxxPx)()()()(xQxxPx7.6 前束

12、范式一、前束范式 前束范式是指所有的量詞都在最前面的謂詞公式。例如， 和是前束范式， 就不是前束范式。 任何一個(gè)謂詞公式都可以通過(guò)等值演算，將其化為前束范式，而且所得到的結(jié)果不是唯一的。 怎樣把謂詞公式化為與之等值的前束范式呢？方法可以分解成下面這五個(gè)步驟，而且應(yīng)當(dāng)嚴(yán)格地按照這五步的順序進(jìn)行，不能顛倒。)()(yGxPyx)(),(xQzyxPzyx)()(yyGxxF利用等值變換消去聯(lián)結(jié)詞將聯(lián)結(jié)詞 移到原子謂詞公式之前3. 對(duì)于公式中變?cè)嗤牟糠?，看能否用等值演算化?jiǎn)合并4. 用換名規(guī)則或代入規(guī)則，使所有約束變?cè)姆?hào)均不相同，約束變?cè)c自由變?cè)惨貌煌姆?hào)5. 將 等移到公式的最左邊

13、。)()()()(xAxxAx)()(KHHKHK,HKHKxx ,)()()()(xAxxAx2000年1月填空題7 謂詞公式 的前束范式是 解：2001年1月計(jì)算題14 求謂詞命題公式 的前束范式。解：)()()()(xQxxPx),()(yxyGxxF)()()(xQxPx)()()()()()()()(xQxxPxxQxxPx),()(yxyGxxF),()(yxyGxxF),()(yzyGxxF),()(yzGxFyx7.7 謂詞邏輯的推理理論 謂詞邏輯推理是命題邏輯推理的推廣和擴(kuò)充。一、推理規(guī)則 1. 全稱量詞消去規(guī)則(US規(guī)則) 已知 和個(gè)體常項(xiàng)c或個(gè)體變項(xiàng)y, 則有 2. 全稱量詞附加規(guī)則(UG規(guī)則) 已知個(gè)體變項(xiàng)y和 ，則有 3. 存在量詞消去規(guī)則(ES規(guī)則) 已知 ，則有 4. 存在量詞附加規(guī)則(EG規(guī)則) 已知個(gè)體常項(xiàng)c和 ，則有 。)()(xAx)()(xAx)(),(yAcA)()(xAx)(yA)(cA)(cA)()(xAx二、推理方法 1. 從前提出發(fā)，對(duì)于量詞 ，把轄域中的約束變?cè)钥梢栽趥€(gè)體域中任意取值的個(gè)體 y,z,s,t 等替代，需要時(shí)也可以用個(gè)體常量 a,b,c等替代，對(duì)于量詞 ，以個(gè)體常量 a,b,c 等替代。 2. 按命題邏輯的推理方法進(jìn)行推理，得出與結(jié)