離散數(shù)學(xué)一階邏輯命題符號化

1、離散數(shù)學(xué)數(shù)理邏輯2/26第四章 一階邏輯基本概念n一階邏輯命題符號化一階邏輯命題符號化n一階邏輯公式及解釋一階邏輯公式及解釋3/26一階邏輯的引入n在命題邏輯中在命題邏輯中, 命題是最基本的單位命題是最基本的單位, 對簡單命題不再進(jìn)行分對簡單命題不再進(jìn)行分解解, 不關(guān)心命題中個體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系不關(guān)心命題中個體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系. 這就使這就使得它難以描述和證明一些常見的推理得它難以描述和證明一些常見的推理. 因此因此, 需要對命題進(jìn)行需要對命題進(jìn)行細(xì)化細(xì)化, 建立更為精細(xì)的邏輯推理體系建立更為精細(xì)的邏輯推理體系.n例如例如: 邏輯學(xué)中著名的三段論邏輯學(xué)中著名的三段論:n凡偶

2、數(shù)都能被凡偶數(shù)都能被2整除整除. 6是偶數(shù)是偶數(shù). 所以所以, 6能被能被2整除整除.這個推理是數(shù)學(xué)中的真命題這個推理是數(shù)學(xué)中的真命題, 是正確的是正確的, 但在命題邏輯中卻無但在命題邏輯中卻無法判斷其正確性法判斷其正確性, 用用p,q,r分別表示以上三個命題分別表示以上三個命題.則得到推理的形式結(jié)構(gòu)為則得到推理的形式結(jié)構(gòu)為: (pq)r由于上式不是重言式由于上式不是重言式, 因而不能由它判斷推理的正確性因而不能由它判斷推理的正確性. 原因原因在于各命題的在于各命題的內(nèi)在聯(lián)系內(nèi)在聯(lián)系沒有表示出來沒有表示出來.n為了克服命題邏輯的局限性為了克服命題邏輯的局限性, 應(yīng)該將原子命題再細(xì)分應(yīng)該將原子命

3、題再細(xì)分, 分析出分析出個體詞個體詞, 謂詞和量詞謂詞和量詞, 以便達(dá)到表達(dá)出命題的內(nèi)在聯(lián)系和命題以便達(dá)到表達(dá)出命題的內(nèi)在聯(lián)系和命題之間的邏輯關(guān)系之間的邏輯關(guān)系. 這就是一階邏輯所研究的內(nèi)容這就是一階邏輯所研究的內(nèi)容.4/264.1 一階邏輯命題符號化n謂詞邏輯命題符號化的三個基本要素謂詞邏輯命題符號化的三個基本要素: 個體詞個體詞, 謂詞謂詞, 量詞量詞.1. 個體詞個體詞: 研究對象中可以獨(dú)立存在的研究對象中可以獨(dú)立存在的具體的或抽象的具體的或抽象的客體客體.例如例如: 小王小王, 小張小張, 馬列主義馬列主義, 3, 北京等都可做為個體詞北京等都可做為個體詞.注注: (1) 表示表示具體

4、或特定具體或特定客體的個體詞稱為客體的個體詞稱為個體常項(xiàng)個體常項(xiàng), 一般用小一般用小寫字母寫字母 a, b, c, 表示表示; (2)表示表示抽象或泛指抽象或泛指的個體詞稱為的個體詞稱為個體變項(xiàng)個體變項(xiàng), 一般用小寫字母一般用小寫字母 x, y, z, 表示表示.個體變項(xiàng)的個體變項(xiàng)的取值范圍取值范圍稱為稱為個體域個體域 (或論域或論域). 個體域可以是有個體域可以是有限集合限集合, 如如1,2,3或或a,b,c, 也可以是無限集合也可以是無限集合, 如自然數(shù)集合如自然數(shù)集合N或?qū)崝?shù)集合或?qū)崝?shù)集合R. 由宇宙間一切事物組成的個體域稱為由宇宙間一切事物組成的個體域稱為全總個全總個體域體域.5/26

5、謂詞2. 謂詞謂詞: 用來刻劃個體詞的性質(zhì)或個體詞之間相互關(guān)系的詞用來刻劃個體詞的性質(zhì)或個體詞之間相互關(guān)系的詞.例如例如: (1) 在命題在命題“ 是無理數(shù)是無理數(shù)”中中, “是無理數(shù)是無理數(shù)”是謂詞是謂詞.(2) 在命題在命題“x 是有理數(shù)是有理數(shù)”中中, “是有理數(shù)是有理數(shù)”是謂詞是謂詞.(3) 在命題在命題“小王與小李同歲小王與小李同歲”中中, “與與同歲同歲”是謂詞是謂詞.(4) 在命題在命題“x與與y具有關(guān)系具有關(guān)系L”中中, “與與具有關(guān)系具有關(guān)系L”是謂詞是謂詞.注注 常用大寫字母常用大寫字母F, G, H 等來表示謂詞等來表示謂詞. 表示表示具體具體性質(zhì)或關(guān)系的謂詞稱為性質(zhì)或關(guān)

6、系的謂詞稱為謂詞常項(xiàng)謂詞常項(xiàng); 表示表示抽象或泛指抽象或泛指的性質(zhì)或關(guān)系的謂詞稱為的性質(zhì)或關(guān)系的謂詞稱為謂詞變項(xiàng)謂詞變項(xiàng). F(a): 表示個體常項(xiàng)表示個體常項(xiàng)a具有性質(zhì)具有性質(zhì)F (F是謂詞常項(xiàng)或變項(xiàng)是謂詞常項(xiàng)或變項(xiàng)); F(x): 表示個體變項(xiàng)表示個體變項(xiàng)x具有性質(zhì)具有性質(zhì)F (F同上同上); F(a,b): 表示個體常項(xiàng)表示個體常項(xiàng)a, b具有關(guān)系具有關(guān)系F (同上同上); F(x,y): 表示個體變項(xiàng)表示個體變項(xiàng) x, y具有關(guān)系具有關(guān)系F (同上同上) .一般地一般地, 用用P(x1,x2,xn)表示含表示含n(n1)個個體變項(xiàng)個個體變項(xiàng)x1,x2,xn 的的n元謂詞元謂詞. 它可看

7、成以個體域?yàn)槎x域它可看成以個體域?yàn)槎x域, 以以0,1為值域的為值域的n元函數(shù)關(guān)系元函數(shù)關(guān)系.當(dāng)當(dāng)P取常項(xiàng)取常項(xiàng), 且且(x1,x2,xn)取定常項(xiàng)取定常項(xiàng)(a1,a2,an)時時, P(a1,a2,an)是一個命是一個命題題.6/26謂詞續(xù)不含不含個體變項(xiàng)的謂詞稱為個體變項(xiàng)的謂詞稱為0元謂詞元謂詞.例如例如 F(a), G(a,b), P(a1,a2,an)等等. 當(dāng)當(dāng)F, G, P等為謂詞常項(xiàng)時等為謂詞常項(xiàng)時, 0元謂詞即為命題元謂詞即為命題. 因此因此, 命題可看作特殊的謂詞命題可看作特殊的謂詞.例例 用用0元謂詞將下列命題符號化元謂詞將下列命題符號化, 并討論它們的真值并討論它們的真

8、值.(1) 只有當(dāng)只有當(dāng)2是素數(shù)時是素數(shù)時, 4才是素數(shù)才是素數(shù);(2) 如果如果5大于大于4, 則則4大于大于6.解解 (1) 設(shè)一元謂詞設(shè)一元謂詞F(x): x是素數(shù)是素數(shù); 個體常項(xiàng)個體常項(xiàng): a: 2；b: 4.則命題可符號化則命題可符號化: F(b) F(a).因?yàn)樵撎N(yùn)含式前件為假因?yàn)樵撎N(yùn)含式前件為假, 故命題為真故命題為真.(2) 設(shè)二元謂詞設(shè)二元謂詞G(x,y): x大于大于y. 個體常項(xiàng)個體常項(xiàng): a: 4; b: 5; c: 6.則命題可符號化為則命題可符號化為: G(b,a) G(a,c).由于由于G(b,a)為真為真, 而而G(a,c)為假為假, 故命題為假故命題為假.7

9、/26量詞的引入n有了個體詞和謂詞的概念之后有了個體詞和謂詞的概念之后, 有些命題還是不能準(zhǔn)確有些命題還是不能準(zhǔn)確地符號化地符號化. 以前面所討論的三段論為例以前面所討論的三段論為例: 令令 P(x): x是偶數(shù)是偶數(shù). S(x) : x能被能被2整除整除. a: 6.符號化為符號化為: (1) P(x)S(x) (2)P(a) (3)S(a) 我們知道我們知道, “凡偶數(shù)都能被凡偶數(shù)都能被2整除整除.”是一個真命題是一個真命題, 而而“P(x)S(x)” 不是一個命題不是一個命題. 原因是原因是“P(x)S(x)”沒沒有把命題有把命題 中中“凡凡”的意思表示出來的意思表示出來. 即缺少表示個

10、體常項(xiàng)或變項(xiàng)的數(shù)量關(guān)系的詞即缺少表示個體常項(xiàng)或變項(xiàng)的數(shù)量關(guān)系的詞. 所以還要所以還要引入量詞的概念引入量詞的概念.8/26量詞量詞量詞: 表示個體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞表示個體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞.量詞只有兩個量詞只有兩個: 全稱量詞全稱量詞, 存在量詞存在量詞.(1) 全稱量詞全稱量詞: 表示表示“全部全部”含義的詞含義的詞. 全稱量詞符號化為全稱量詞符號化為“ ”.a. 常用語中常用語中“全部全部”, “所有的所有的”, “一切一切”, “每一個每一個”, “任何任何”, “任意的任意的”, “凡凡”, “都都”等詞都是全稱量詞等詞都是全稱量詞.b. x F(x)表示個體域里所有

11、個體都有性質(zhì)表示個體域里所有個體都有性質(zhì)F.(2) 存在量詞存在量詞: 表示表示“存在存在”含義的詞含義的詞. 存在量詞符號化為存在量詞符號化為“ ”. a. 常用詞中常用詞中“存在存在”, “有一個有一個”, “有的有的”, “至少有一個至少有一個”等詞都等詞都是存在量詞是存在量詞.b. x F(x)表示個體域中存在個體具有性質(zhì)表示個體域中存在個體具有性質(zhì) F. 例例: 凡偶數(shù)都能被凡偶數(shù)都能被2整除整除. 可符號化為可符號化為: x(P(x)S(x)是真命題是真命題, 其中其中x不再起變元的作用不再起變元的作用, 它被全稱量詞它被全稱量詞 限制住了限制住了, 這時我們稱這時我們稱 x 被量

12、化了被量化了.9/26一階邏輯中命題符號化例例 個體域?yàn)閭€體域?yàn)槿祟惣先祟惣? 將下面兩個命題符號化將下面兩個命題符號化:(1) 凡是人都要呼吸凡是人都要呼吸; (2) 有的人用左手寫字有的人用左手寫字.解解令令 F(x): x 呼吸呼吸; G(x): x 用左手寫字用左手寫字. 則則 (1) x F(x); (2) x G(x)。例例 上例中上例中, 將個體域改為將個體域改為全總個體域全總個體域, 兩命題的符號化形式如何兩命題的符號化形式如何?解解令令 F(x): x呼吸呼吸; G(x): x用左手寫字；用左手寫字；M(x) : x是人是人.則則: (1) x (M(x) F(x); (

13、2) x (M(x) G(x). 特性謂詞特性謂詞: 從全總個體域中分離出一個集合從全總個體域中分離出一個集合, 定義的謂詞定義的謂詞. 在不同個體域中在不同個體域中, 同一個命題的符號化形式可能不同同一個命題的符號化形式可能不同.一般地一般地, 對全稱量詞對全稱量詞, 特性謂詞應(yīng)作為蘊(yùn)含式的前件特性謂詞應(yīng)作為蘊(yùn)含式的前件.一般地一般地, 對存在量詞對存在量詞, 特性謂詞應(yīng)作為合取式的一項(xiàng)特性謂詞應(yīng)作為合取式的一項(xiàng). 同一個命題同一個命題, 在不同個體域中的真值也可能不同在不同個體域中的真值也可能不同.如果問題中沒有指明個體域時如果問題中沒有指明個體域時, 默認(rèn)為默認(rèn)為全總體域全總體域.10/

14、26一階邏輯中命題符號化續(xù) 當(dāng)當(dāng)F是謂詞常項(xiàng)時是謂詞常項(xiàng)時, xF(x)是個命題是個命題, 如果把個體域中的任如果把個體域中的任何一個個體何一個個體a代入代入, F(a)都為真都為真, 則則 xF(x)為真為真; 否則否則 xF(x)為為假假. 當(dāng)當(dāng)F是謂詞常項(xiàng)時是謂詞常項(xiàng)時, xF(x)是個命題是個命題, 如果個體域中存在一如果個體域中存在一個個體個個體a使使F(a) 為真為真, 則則 xF(x)為真為真; 否則否則 xF(x)為假為假.例例在個體域限制為在個體域限制為(a)和和(b)條件時條件時, 將下列命題符號化將下列命題符號化, 并給出它并給出它們的真值們的真值. (1) 對于任意的對

15、于任意的x, 均有均有x2-3x+2=(x-1)(x-2)(2) 存在存在x, 使得使得x+5=3其中其中(a)個體域?yàn)閭€體域?yàn)镈1=N (b)個體域?yàn)閭€體域?yàn)镈2=R解解令令F(x): x2-3x+2=(x-1)(x-2) , G(x): x+5=3.則可符號化為則可符號化為(1) xF(x), (2) xG(x) .個體域?yàn)閭€體域?yàn)?a)時時, (1)是真命題是真命題, (2)是假命題是假命題;個體域?yàn)閭€體域?yàn)?b)時時, (1)與與(2)都是真命題都是真命題.11/26一階邏輯中命題符號化續(xù)例例 將下列命題符號化將下列命題符號化, 并討論其真值并討論其真值.(1) 實(shí)數(shù)都能寫成整數(shù)之比實(shí)

16、數(shù)都能寫成整數(shù)之比; (2)有的素數(shù)是偶數(shù)有的素數(shù)是偶數(shù);(3) 沒有人登上過木星沒有人登上過木星; (4)在美國留學(xué)的學(xué)生未必都是亞洲人在美國留學(xué)的學(xué)生未必都是亞洲人.解解 (1) 令令M(x): x 為實(shí)數(shù)為實(shí)數(shù) ; F(x): x能寫成整數(shù)之比能寫成整數(shù)之比. 則則 x (M(x) F(x)不是不是 x (M(x) F(x)假命題假命題(2) 令令M(x): x 為素數(shù)為素數(shù); G(x): x為偶數(shù)為偶數(shù). 則則 x (M(x)G(x)不是不是 x (M(x) G(x)真命題真命題(3) 令令M(x): x 是人是人; H(x): x登上過木星登上過木星. 則則 x (M(x)H(x)真

17、命題真命題(4) 令令F(x): x是在美國留學(xué)的學(xué)生是在美國留學(xué)的學(xué)生; G(x): x是亞洲人是亞洲人. 則則 x (F(x) G(x)真命題真命題12/26n 元謂詞的符號化 ( n 2 )例例 將下列命題符號化將下列命題符號化(1) 兔子比烏龜跑得快兔子比烏龜跑得快;(2) 有的兔子比所有的烏龜跑得快有的兔子比所有的烏龜跑得快;(3) 并不是所有的兔子都比烏龜跑得快并不是所有的兔子都比烏龜跑得快;(4) 不存在跑得同樣快的兩只兔子不存在跑得同樣快的兩只兔子.解解 令令F(x): x是兔子是兔子; G(y): y是烏龜是烏龜; H(x,y): x比比y跑得快跑得快; L(x,y): x與

18、與 y跑得同樣快跑得同樣快. 則則:(1) 任意一個兔子任意一個兔子x : x 比任意一個烏龜跑得快比任意一個烏龜跑得快 x (F(x) y (G(y) H(x,y) );(2) 存在一個兔子存在一個兔子 x : x 比任意一個烏龜跑得快比任意一個烏龜跑得快 x ( F(x) y (G(y) H(x,y) );(3) (1)的否定的否定 存在一個兔子存在一個兔子 x : 存在一個烏龜存在一個烏龜 y : x不比不比y跑得快跑得快 x (F(x) y (F(y) L(x,y) ).;(4) “存在一個兔子存在一個兔子 x : 存在另一個兔子存在另一個兔子 y : x與與y跑得同樣快跑得同樣快”

19、的否定的否定 x (F(x) y(F(y) L(x,y) ).13/26注1. 分析命題中表示性質(zhì)和關(guān)系的謂詞分析命題中表示性質(zhì)和關(guān)系的謂詞, 分別符號化為一元和分別符號化為一元和n元謂詞元謂詞(n2).2. 根據(jù)命題的實(shí)際意義選用全稱量詞或存在量詞根據(jù)命題的實(shí)際意義選用全稱量詞或存在量詞. 3. 一般來說一般來說, 多個量詞在一起時多個量詞在一起時, 其順序不能隨意調(diào)換其順序不能隨意調(diào)換.例如例如: “對任意對任意x, 都存在都存在y, 使使x+y=10”這一命題這一命題, 可符號化為可符號化為 x y ( x+y =10 ) , 它不能改寫為它不能改寫為 y x ( x+y =10 ) .

20、練習(xí)練習(xí) 函數(shù)函數(shù)f(x)在在x=a處極限為處極限為bn任給小正數(shù)任給小正數(shù), 則存在正數(shù)則存在正數(shù) , 使得使得當(dāng)當(dāng)0|x-a|時時, |f(x)-b|0, 存在存在0, 使得使得當(dāng)當(dāng)0|x-a|時時, |f(x)-b|0 (0 x(|x-a|f(x)-b|)14/264.2一階邏輯公式及解釋非邏輯符號非邏輯符號: 個體詞常項(xiàng)符號個體詞常項(xiàng)符號, 函數(shù)符號和謂詞符號函數(shù)符號和謂詞符號邏輯符號邏輯符號: 個體詞變項(xiàng)符號個體詞變項(xiàng)符號, 量詞符號量詞符號, 聯(lián)結(jié)詞符號和括號與逗號聯(lián)結(jié)詞符號和括號與逗號n定義定義 設(shè)設(shè)L是一個非邏輯符號是一個非邏輯符號, 由由L生成的生成的一階語言一階語言L的字母

21、表的字母表包括下述符號如下包括下述符號如下:非邏輯符號非邏輯符號(1) L中的中的個體常項(xiàng)符號個體常項(xiàng)符號: a, b, c, ; ai , bi , ci , , i1(2) L中的中的函詞符號函詞符號: f, g, h, ; fi , gi , hi , , i1(3) L中的中的謂詞符號謂詞符號: F,G, H,; Fi ,Gi , Hi , i1邏輯符號邏輯符號(4) 個體變項(xiàng)符號個體變項(xiàng)符號: x, y, z, ; xi , yi , zi , i1(5) 量詞符號量詞符號: , .(6) 聯(lián)結(jié)詞符號聯(lián)結(jié)詞符號: , , .(7) 逗號與括號逗號與括號: , , ( ) .15/26

22、項(xiàng)與原子公式n定義定義 一階語言一階語言L 的項(xiàng)的項(xiàng)定義如下定義如下:(1) 個體常項(xiàng)符號個體常項(xiàng)符號和和個體變項(xiàng)符號個體變項(xiàng)符號是是項(xiàng)項(xiàng);(2) 若若 (x1, x2 ,xn) 是是n元函詞符號元函詞符號, t1,t2,tn 是是n個個項(xiàng)項(xiàng), 則則 (t1,t2,tn )是是項(xiàng)項(xiàng).(3) 所有的項(xiàng)都是有限次使用所有的項(xiàng)都是有限次使用(1), (2)得到的得到的n定義定義 設(shè)設(shè)R(x1,x2,xn)是一階語言是一階語言L中的中的n元謂詞符號元謂詞符號. t1,t2,tn 是是L 的的n個個項(xiàng)項(xiàng), 則稱則稱 R(t1,t2,tn )是是F 的的原子原子公式公式16/26合式公式n定義定義 一階語

23、言一階語言L 中的中的合式公式合式公式 (也稱為謂詞公式或也稱為謂詞公式或公式公式) 定義如下定義如下:(1) 原子公式是合式公式原子公式是合式公式;(2) 若若A是合式公式是合式公式, 則則 (A)也是合式公式也是合式公式;(3) 若若A, B 是合式公式是合式公式, 則則(AB), (AB), (AB), (AB)也是合式公式也是合式公式;(4) 若若A是合式公式是合式公式, 則則 xA, xA也是合式公式也是合式公式;(5) 只有有限次應(yīng)用只有有限次應(yīng)用 (1)(4) 構(gòu)成的符號串才是合式公式構(gòu)成的符號串才是合式公式.n定義定義 在公式在公式 xA 和和 xA中中, 稱稱 x 為為指導(dǎo)變

24、元指導(dǎo)變元, A為相為相應(yīng)量詞的應(yīng)量詞的轄域轄域. 在在 x 和和 x 的轄域中的轄域中, x的所有出現(xiàn)都的所有出現(xiàn)都稱為稱為約束出現(xiàn)約束出現(xiàn), A中不是約束出現(xiàn)的其它變項(xiàng)都稱為中不是約束出現(xiàn)的其它變項(xiàng)都稱為自由出現(xiàn)自由出現(xiàn).17/26轄域n例例 指出下列公式中的指導(dǎo)變元指出下列公式中的指導(dǎo)變元, 各量詞的轄域各量詞的轄域, 自由出現(xiàn)和約自由出現(xiàn)和約束出現(xiàn)的個體變項(xiàng)束出現(xiàn)的個體變項(xiàng):(1) x(F(x,y) G(x,z);(2) x(F(x) G(y) y(H(x)L(x,y,z). 解解(1) 指導(dǎo)變元指導(dǎo)變元: x; 量詞量詞 的轄域的轄域: A=(F(x,y) G(x,z);在在A 中中

25、, x是約束出現(xiàn)是約束出現(xiàn); y, z是自由出現(xiàn)是自由出現(xiàn).(2) 前件量詞前件量詞 的指導(dǎo)變元的指導(dǎo)變元: x; 后件量詞后件量詞 的指導(dǎo)變元的指導(dǎo)變元: y.量詞量詞 的轄域的轄域: (F(x)G(y), 其中其中x是約束出現(xiàn)是約束出現(xiàn), y 是自由出現(xiàn)是自由出現(xiàn).量詞量詞 的轄域的轄域: (H(x)L(x,y,z) ), 其中其中 y是約束出現(xiàn)是約束出現(xiàn), 而而x, z 是是自由出現(xiàn)自由出現(xiàn).18/26閉式定義定義 設(shè)設(shè)A是任意的公式是任意的公式, 若若A中中不含自由出現(xiàn)不含自由出現(xiàn)的個體變項(xiàng)的個體變項(xiàng), 則稱則稱A為封閉的公為封閉的公式式, 簡稱簡稱閉式閉式.例如例如 x y H(x,

26、y), x y(F(x)F(y)L(x,y), x(F(x) G(x)F(a) G(a) 例例 將下列兩個公式中的變項(xiàng)指定為常項(xiàng)使其成為命題將下列兩個公式中的變項(xiàng)指定為常項(xiàng)使其成為命題:(1) x(F(x)G(x)(2) x y(F(x)F(y)G(x,y)H(f(x,y),g(x,y)解解 (1)個體域個體域 F(x) G(x) 命題命題 真值真值 全總?cè)?x是人是人 x是黃種人是黃種人 所有人都是黃種人所有人都是黃種人0 實(shí)數(shù)實(shí)數(shù) x是自然數(shù)是自然數(shù) x是整數(shù)是整數(shù) 所有自然數(shù)都是整數(shù)所有自然數(shù)都是整數(shù)1(2) 兩個兩個2元函詞變項(xiàng)元函詞變項(xiàng), 一個一個1元謂詞變項(xiàng)元謂詞變項(xiàng), 兩個兩個

27、2元謂詞變項(xiàng)元謂詞變項(xiàng). 個體域個體域 F(x) G(x, y) H(x, y) f(x, y) g(x, y) 全總?cè)?x是實(shí)數(shù)是實(shí)數(shù) xy xy x2+y2 2xy命題命題: 對于任意的對于任意的x, y, 若若x與與y都是實(shí)數(shù)且都是實(shí)數(shù)且xy, 則則x2+y22xy. 真值為真真值為真.19/26解釋n在前面例子中對各種變項(xiàng)的指定也稱為對它們的在前面例子中對各種變項(xiàng)的指定也稱為對它們的解釋解釋, 是先是先給出公式再對它們進(jìn)行解釋給出公式再對它們進(jìn)行解釋, 也可以先給出解釋也可以先給出解釋, 再去解釋各再去解釋各種公式種公式. n定義定義 對公式對公式A指定其中個體域的范圍指定其中個體域

28、的范圍, 并指定其中謂詞的具并指定其中謂詞的具體含義使其成為命題體含義使其成為命題, 稱為對公式稱為對公式A的一個的一個解釋解釋.n定義定義 設(shè)設(shè)L是由是由L生成的一階語言生成的一階語言, L的的解釋的的解釋I 由下面由下面4部分組部分組成成:n非空個體域非空個體域DI.n對每一個個體常項(xiàng)符號對每一個個體常項(xiàng)符號aL, 有一個有一個aDI, 稱稱a為為a在在I中的解中的解釋釋.n對每一個對每一個n元函詞符號元函詞符號fL, 有一個有一個DI上的上的n元函數(shù)元函數(shù)f: DIn DI, 稱稱f為為f在在I中的解釋中的解釋.n對每一個對每一個n元謂詞符號元謂詞符號FL, 有一個有一個DI上的上的n元

29、謂詞常項(xiàng)元謂詞常項(xiàng)F, 稱稱F為為F在在I中的解釋中的解釋.20/26例n例例 給定解釋給定解釋I如下如下:n個體域個體域D=N.na=0.nf(x,y)=x+y, g(x,y)=xy.nF(x,y): x=y.寫出下列公式在寫出下列公式在I下的解釋下的解釋, 并指出哪些公式為真并指出哪些公式為真? 哪些為假哪些為假? 哪些真值不能確定哪些真值不能確定?(1) F(f(x,y), g(x,y); 解解: 公式解釋為公式解釋為:“x+y= xy”不是命題不是命題; 真值不確定真值不確定 (2) F(f(x,a), y) F(g(x, y),z);解解: 公式解釋為公式解釋為: “(x+0=y)

30、(xy=z)”不是命題不是命題; 真值不確定真值不確定 (3) F(g(x,y), g(y,z); 解解: 公式解釋為公式解釋為: “xyyz”不是命題不是命題; 真值不確定真值不確定21/26例續(xù)(4) xF(g(x, y), z) ;解解:公式解釋為公式解釋為: “ x (xy = yz)”不是命題不是命題; 真值不確定真值不確定(5) x F(g(x, a),x);解解:公式解釋為公式解釋為: “ x (x0=x)”假命題假命題(6) x F(g(x, a),x) F(x,y) ; 解解:公式解釋為公式解釋為: “ x (x0 = x)(x=y)”真命題真命題(前件為假前件為假)22/2

31、6例續(xù)(7) x y(F(f(x,a),y) F(f(y,a), x) ;解解:公式解釋為公式解釋為: “ x y (x+0=y)(y+0=x)”真命題真命題(8) x y z F(f(x,y),z); 解解:公式解釋為公式解釋為: “ x y z(x+y=z)”真命題真命題 (9) x F(f(x,x),g(x,x) ; 解解:公式解釋為公式解釋為: “ x(x+x = xx)真命題真命題23/26公式類型n定理定理 閉式在任何解釋下都可變成命題閉式在任何解釋下都可變成命題.n定義定義 設(shè)設(shè)A為一個公式為一個公式, 若若A在任何解釋下均為真在任何解釋下均為真, 則稱則稱A為為永永真式真式(或

32、邏輯有效式或邏輯有效式); 若若A在任何解釋下均為假在任何解釋下均為假, 則稱則稱A為為永假式永假式(或邏輯矛盾式或邏輯矛盾式);若至少存在一個解釋使若至少存在一個解釋使A為真為真, 則稱則稱A為為可滿足式可滿足式.n定義定義 設(shè)設(shè)A0 是含命題變項(xiàng)是含命題變項(xiàng)p1 , p2, pn 的命題公式的命題公式, A1, A2 , , An 是是n個謂詞公式個謂詞公式. 用用Ai (1in)處處代替處處代替A0 中的中的pi, 所得公式所得公式A 稱為稱為A0 的的代換實(shí)例代換實(shí)例.n例如例如 F(x)G(x), x F(x) y G(y) 等都是等都是pq的代換實(shí)例的代換實(shí)例.n定理定理 重言式重言式的代換實(shí)例都是的代換實(shí)例都是永真式永真式, 矛盾式矛盾式的代換實(shí)例都是的代換實(shí)例都是矛盾式矛盾式.24/26公式類型示例例例 判斷下列公式中判斷下列公式中, 哪些是永真式哪些是永真式, 哪些是永假式哪些是永假式?(1) x (F(x) G(x);