屈婉玲離散數(shù)學(xué)第四章課件

主要內(nèi)容一階邏輯命題符號(hào)化個(gè)體詞、謂詞、量詞一階邏輯命題符號(hào)化一階邏輯公式及其解釋一階語(yǔ)言合式公式合式公式的解釋永真式、矛盾式、可滿足式第四章一階邏輯基本概念1主要內(nèi)容第四章一階邏輯基本概念14.1一階邏輯命題符號(hào)化

個(gè)體詞——所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體

個(gè)體常項(xiàng)：具體的事務(wù)，用a,b,c表示

個(gè)體變項(xiàng)：抽象的事物，用x,y,z表示

個(gè)體域(論域)——個(gè)體變項(xiàng)的取值范圍有限個(gè)體域，如{a,b,c},{1,2}無(wú)限個(gè)體域，如N,Z,R,…全總個(gè)體域——由宇宙間一切事物組成24.1一階邏輯命題符號(hào)化個(gè)體詞——所研究對(duì)象中可以獨(dú)立存謂詞謂詞——表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞

謂詞常項(xiàng)如,F(a)：a是人

謂詞變項(xiàng)如,F(x)：x具有性質(zhì)F

n（n1）元謂詞一元謂詞(n=1)——表示性質(zhì)多元謂詞(n2)——表示事物之間的關(guān)系

如,L(x,y)：x與y有關(guān)系L，L(x,y)：xy，…0元謂詞——不含個(gè)體變項(xiàng)的謂詞,即命題常項(xiàng)或命題變項(xiàng)3謂詞謂詞——表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞3量詞量詞——表示數(shù)量的詞

全稱量詞:表示所有的.

x:對(duì)個(gè)體域中所有的x如,xF(x)表示個(gè)體域中所有的x具有性質(zhì)F

xyG(x,y)表示個(gè)體域中所有的x和y有關(guān)系G

存在量詞:表示存在,有一個(gè).x:個(gè)體域中有一個(gè)x

如,xF(x)表示個(gè)體域中有一個(gè)x具有性質(zhì)F

xyG(x,y)表示個(gè)體域中存在x和y有關(guān)系G

xyG(x,y)表示對(duì)個(gè)體域中每一個(gè)x都存在一個(gè)y使得

x和y有關(guān)系GxyG(x,y)表示個(gè)體域中存在一個(gè)x使得對(duì)每一個(gè)y,

x和y有關(guān)系G4量詞量詞——表示數(shù)量的詞4實(shí)例1例1用0元謂詞將命題符號(hào)化(1)墨西哥位于南美洲(2)是無(wú)理數(shù)僅當(dāng)是有理數(shù)(3)如果2>3，則3<4解：在命題邏輯中：(1)p,p為墨西哥位于南美洲（真命題）(2)p→q,其中,p：是無(wú)理數(shù)，q：是有理數(shù).是假命題(3)pq,其中，p：2>3，q：3<4.是真命題5實(shí)例1例1用0元謂詞將命題符號(hào)化解：在命題邏輯中：5實(shí)例1解答在一階邏輯中：(1)F(a)，其中，a：墨西哥，F(xiàn)(x)：x位于南美洲.(2)F()G(),其中，F(xiàn)(x)：x是無(wú)理數(shù)，G(x)：x是有理數(shù)(3)F(2,3)G(3,4)，其中，F(xiàn)(x,y)：x>y，G(x,y)：x<y6實(shí)例1解答在一階邏輯中：6實(shí)例2例2在一階邏輯中將下面命題符號(hào)化(1)人都愛(ài)美(2)有人用左手寫字個(gè)體域分別為(a)D為人類集合(b)D為全總個(gè)體域解(a)(1)xG(x),G(x)：x愛(ài)美(2)xG(x),G(x)：x用左手寫字

(b)F(x)：x為人，G(x)：x愛(ài)美

(1)x(F(x)G(x))

(2)x(F(x)G(x))1.引入特性謂詞F(x)2.(1),(2)是一階邏輯中兩個(gè)“基本”公式7實(shí)例2例2在一階邏輯中將下面命題符號(hào)化解(a)實(shí)例3例3在一階邏輯中將下面命題符號(hào)化(1)正數(shù)都大于負(fù)數(shù)(2)有的無(wú)理數(shù)大于有的有理數(shù)解注意：題目中沒(méi)給個(gè)體域，一律用全總個(gè)體域(1)令F(x)：x為正數(shù)，G(y)：y為負(fù)數(shù),L(x,y)：x>yx(F(x)y(G(y)L(x,y)))或者xy(F(x)G(y)L(x,y))(2)令F(x)：x是無(wú)理數(shù)，G(y)：y是有理數(shù)，L(x,y)：x>y

x(F(x)y(G(y)L(x,y)))或者

xy(F(x)G(y)L(x,y))8實(shí)例3例3在一階邏輯中將下面命題符號(hào)化解注意：題目中沒(méi)實(shí)例4例4在一階邏輯中將下面命題符號(hào)化(1)沒(méi)有不呼吸的人(2)不是所有的人都喜歡吃糖解(1)F(x):x是人,G(x):x呼吸x(F(x)G(x))x(F(x)G(x))(2)F(x):x是人,G(x):x喜歡吃糖x(F(x)G(x))x(F(x)G(x))9實(shí)例4例4在一階邏輯中將下面命題符號(hào)化解(1)F(x實(shí)例5例5設(shè)個(gè)體域?yàn)閷?shí)數(shù)域,將下面命題符號(hào)化(1)對(duì)每一個(gè)數(shù)x都存在一個(gè)數(shù)y使得x<y(2)存在一個(gè)數(shù)x使得對(duì)每一個(gè)數(shù)y都有x<y解L(x,y):x<y(1)xyL(x,y)注意:與不能隨意交換顯然(1)是真命題,(2)是假命題(2)xyL(x,y)10實(shí)例5例5設(shè)個(gè)體域?yàn)閷?shí)數(shù)域,將下面命題符號(hào)化解4.2一階邏輯公式及解釋定義4.1設(shè)L是一個(gè)非邏輯符集合,由L生成的一階語(yǔ)言L的字母表包括下述符號(hào)：非邏輯符號(hào)(1)個(gè)體常項(xiàng)符號(hào)：a,b,c,…,ai,bi,ci,…,i

1(2)函數(shù)符號(hào)：f,g,h,…,fi,gi,hi,…,i

1(3)謂詞符號(hào)：F,G,H,…,Fi,Gi,Hi,…,i

1邏輯符號(hào)(4)個(gè)體變項(xiàng)符號(hào)：x,y,z,…,xi,yi,zi,…,i

1(5)量詞符號(hào)：,(6)聯(lián)結(jié)詞符號(hào)：,,,,

(7)括號(hào)與逗號(hào)：(,),，114.2一階邏輯公式及解釋定義4.1設(shè)L是一個(gè)非邏輯符集一階語(yǔ)言L

的項(xiàng)與原子公式定義4.2

L的項(xiàng)的定義如下：(1)個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng).(2)若(x1,x2,…,xn)是任意的n元函數(shù)，t1,t2,…,tn是任意的

n個(gè)項(xiàng)，則(t1,t2,…,tn)是項(xiàng).(3)所有的項(xiàng)都是有限次使用(1),(2)得到的如,a,x,x+y,f(x),g(x,y)等都是項(xiàng)定義4.3設(shè)R(x1,x2,…,xn)是L

的任意n元謂詞，t1,t2,…,tn

是L

的任意n個(gè)項(xiàng)，則稱R(t1,t2,…,tn)是L

的原子公式.如，F(xiàn)(x,y),F(f(x1,x2),g(x3,x4))等均為原子公式12一階語(yǔ)言L的項(xiàng)與原子公式定義4.2L的項(xiàng)的定義如下定義4.4

L

的合式公式定義如下：(1)原子公式是合式公式.(2)若A是合式公式，則(A)也是合式公式(3)若A,B是合式公式，則(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式，則xA,xA也是合式公式(5)只有有限次地應(yīng)用(1)—(4)形成的符號(hào)串才是合式公式.合式公式簡(jiǎn)稱公式如,F(x),F(x)G(x,y),x(F(x)G(x))xy(F(x)G(y)L(x,y))等都是合式公式一階語(yǔ)言L

的公式13定義4.4L的合式公式定義如下：一階語(yǔ)言L的公式13封閉的公式定義4.5在公式xA和xA中，稱x為指導(dǎo)變?cè)珹為相應(yīng)量詞的轄域.在x和x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項(xiàng)均稱為是自由出現(xiàn)的.例如，x(F(x,y)G(x,z))，x為指導(dǎo)變?cè)?F(x,y)G(x,z))為x的轄域，x的兩次出現(xiàn)均為約束出現(xiàn)，y與z均為自由出現(xiàn)又如,x(F(x,y,z)y(G(x,y)H(x,y,z))),x中的x是指導(dǎo)變?cè)?轄域?yàn)?F(x,y,z)y(G(x,y)H(x,y,z))).y中的y是指導(dǎo)變?cè)?轄域?yàn)?G(x,y)H(x,y,z)).x的3次出現(xiàn)都是約束出現(xiàn),y的第一次出現(xiàn)是自由出現(xiàn),后2次是約束出現(xiàn),z的2次出現(xiàn)都是自由出現(xiàn)14封閉的公式定義4.5在公式xA和xA中，稱x封閉的公式定義4.6若公式A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為封閉的公式，簡(jiǎn)稱閉式.例如，xy(F(x)G(y)H(x,y))為閉式，而x(F(x)G(x,y))不是閉式15封閉的公式定義4.6若公式A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則公式的解釋定義4.7設(shè)L

是L生成的一階語(yǔ)言,L的解釋I由4部分組成：(a)非空個(gè)體域DI.(b)

對(duì)每一個(gè)個(gè)體常項(xiàng)符號(hào)aL,有一個(gè)DI,稱

為a在I

中的解釋.(c)對(duì)每一個(gè)n元函數(shù)符號(hào)fL,有一個(gè)DI上的n元函數(shù),稱

為f在I中的解釋.(d)對(duì)每一個(gè)n元謂詞符號(hào)FL,有一個(gè)DI上的n元謂詞常項(xiàng),稱

為F在I中的解釋.設(shè)公式A,取個(gè)體域DI,把A中的個(gè)體常項(xiàng)符號(hào)a、函數(shù)符號(hào)f、謂詞符號(hào)F分別替換成它們?cè)贗中的解釋、、,稱所得到的公式A為A在I下的解釋,或A在I下被解釋成A.16公式的解釋定義4.7設(shè)L是L生成的一階語(yǔ)言,L的解實(shí)例例6給定解釋I如下：(a)個(gè)體域D=R(b)(c)(d)

寫出下列公式在I下的解釋,并指出它的真值.(1)xF(f(x,a),g(x,a))

x(x+0=x0)真(2)xy(F(f(x,y),g(x,y))F(x,y))xy(x+y=xyx=y)假(3)xF(g(x,y),a)x(xy=0)真值不定,不是命題17實(shí)例例6給定解釋I如下：x(x+0=x0公式的類型定理4.1閉式在任何解釋下都是命題注意:不是閉式的公式在解釋下可能是命題,也可能不是命題.定義4.8若公式A在任何解釋下均為真,則稱A為永真式(邏輯有效式).若A在任何解釋下均為假,則稱A為矛盾式(永假式).若至少有一個(gè)解釋使A為真,則稱A為可滿足式.幾點(diǎn)說(shuō)明：永真式為可滿足式，但反之不真判斷公式是否是可滿足的(永真式,矛盾式)是不可判定的18公式的類型定理4.1閉式在任何解釋下都是命題18代換實(shí)例定義4.9設(shè)A0是含命題變項(xiàng)p1,p2,…,pn的命題公式，A1,A2,…,An是n個(gè)謂詞公式，用Ai

(1in)處處代替A0中的pi，所得公式A稱為A0的代換實(shí)例.例如，F(xiàn)(x)G(x),xF(x)yG(y)等都是pq的代換實(shí)例.定理4.2重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式.19代換實(shí)例定義4.9設(shè)A0是含命題變項(xiàng)p1,p2,…實(shí)例例7判斷下列公式中，哪些是永真式，哪些是矛盾式？(1)xF(x)(xyG(x,y)xF(x))重言式p(qp)的代換實(shí)例，故為永真式.(2)(xF(x)yG(y))yG(y)矛盾式(pq)q的代換實(shí)例，故為永假式.(3)x(F(x)G(x))解釋I1:個(gè)體域N,F(x):x>5,G(x):x>4,公式為真解釋I2:個(gè)體域N,F(x):x<5,G(x):x<4,公式為假結(jié)論:非永真式的可滿足式20實(shí)例例7判斷下列公式中，哪些是永真式，哪些是矛盾式？重言第四章習(xí)題課主要內(nèi)容個(gè)體詞、謂詞、量詞一階邏輯命題符號(hào)化一階語(yǔ)言L

項(xiàng)、原子公式、合式公式公式的解釋量詞的轄域、指導(dǎo)變?cè)€(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn)、閉式、解釋公式的類型永真式(邏輯有效式)、矛盾式(永假式)、可滿足式21第四章習(xí)題課主要內(nèi)容21基本要求準(zhǔn)確地將給定命題符號(hào)化理解一階語(yǔ)言的概念深刻理解一階語(yǔ)言的解釋熟練地給出公式的解釋記住閉式的性質(zhì)并能應(yīng)用它深刻理解永真式、矛盾式、可滿足式的概念,會(huì)判斷簡(jiǎn)單公式的類型22基本要求準(zhǔn)確地將給定命題符號(hào)化22練習(xí)11.在分別取個(gè)體域?yàn)?a)D1=N

(b)D2=R(c)D3為全總個(gè)體域的條件下,將下面命題符號(hào)化，并討論真值(1)對(duì)于任意的數(shù)x，均有解設(shè)G(x):(a)xG(x)(b)xG(x)(c)又設(shè)F(x):x是實(shí)數(shù)

x(F(x)G(x))真真假23練習(xí)11.在分別取個(gè)體域?yàn)榻庠O(shè)G(x):(b)xG練習(xí)1(續(xù))解設(shè)H(x)：x+7=5(a)xH(x)(2)存在數(shù)x，使得x+7=5(b)xH(x)(c)又設(shè)F(x)：x為實(shí)數(shù)

x(F(x)H(x))本例說(shuō)明：不同個(gè)體域內(nèi)，命題符號(hào)化形式可能不同（也可能相同），真值可能不同（也可能相同）.真真假24練習(xí)1(續(xù))解設(shè)H(x)：x+7=5(2)存在數(shù)練習(xí)22.在一階邏輯中將下列命題符號(hào)化(1)大熊貓都可愛(ài)(2)有人愛(ài)發(fā)脾氣(3)說(shuō)所有人都愛(ài)吃面包是不對(duì)的設(shè)F(x):x為大熊貓，G(x):x可愛(ài)x(F(x)G(x))

設(shè)F(x):x是人，G(x):x愛(ài)發(fā)脾氣x(F(x)G(x))設(shè)F(x):x是人，G(x):x愛(ài)吃面包

x(F(x)G(x))或x(F(x)G(x))25練習(xí)22.在一階邏輯中將下列命題符號(hào)化(2)有人愛(ài)發(fā)脾練習(xí)2(4)沒(méi)有不愛(ài)吃糖的人(5)任何兩個(gè)不同的人都不一樣高(6)不是所有的汽車都比所有的火車快設(shè)F(x):x是人，G(x):x愛(ài)吃糖x(F(x)G(x))或x(F(x)G(x))設(shè)F(x):x是人,H(x,y),x與y相同,L(x,y):x與y一樣高x(F(x)y(F(y)H(x,y)L(x,y)))或xy(F(x)F(y)H(x,y)L(x,y))設(shè)F(x):x是汽車,G(y):y是火車,H(x,y):x比y快xy(F(x)G(y)H(x,y))或xy(F(x)G(y)H(x,y))26練習(xí)2(4)沒(méi)有不愛(ài)吃糖的人(5)任何兩個(gè)不同的人練習(xí)3x(2x=x)假3.給定解釋I如下:(a)個(gè)體域D=N(b)=2(c)(d)說(shuō)明下列公式在I下的涵義,并討論真值(1)xF(g(x,a),x)(2)xy(F(f(x,a),y)F(f(y,a),x))xy(x+2=yy+2=x)假27練習(xí)3x(2x=x)假3.給定解釋練習(xí)3(3)xyzF(f(x,y),z)(5)xF(f(x,x),g(x,x))(4)xyzF(f(y,z),x)xyz(y+z=x)假xyz(x+y=z)真x(x+x=xx)真(3),(4)說(shuō)明與不能隨意交換28練習(xí)3(3)xyzF(f(x,y),z)(5)x練習(xí)44.證明下面公式既不是永真式，也不是矛盾式:(1)x(F(x)G(x))(2)xy(F(x)G(y)H(x,y))解釋1:D1=N,F(x):x是偶數(shù),G(x):x是素?cái)?shù),真解釋2:D2=N,F(x):x是偶數(shù),G(x):x是奇數(shù),假解釋1:D1=Z,F(x):x是正數(shù),G(x):x是負(fù)數(shù),H(x,y):x>y

真解釋2:D2=Z,F(x):x是偶數(shù),G(x):x是奇數(shù),H(x,y):x>y

假29練習(xí)44.證明下面公式既不是永真式，也不是矛盾式:(1)練習(xí)55.證明下列公式為永真式:(1)(xF(x)yG(y))xF(x)yG(y)(2)x(F(x)(F(x)G(x)))(AB)AB的代換實(shí)例設(shè)I是任意的一個(gè)解釋,對(duì)每一個(gè)xDI,F(x)(F(x)G(x))恒為真30練習(xí)55.證明下列公式為永真式:(2)x(F(x)(主要內(nèi)容一階邏輯命題符號(hào)化個(gè)體詞、謂詞、量詞一階邏輯命題符號(hào)化一階邏輯公式及其解釋一階語(yǔ)言合式公式合式公式的解釋永真式、矛盾式、可滿足式第四章一階邏輯基本概念31主要內(nèi)容第四章一階邏輯基本概念14.1一階邏輯命題符號(hào)化

個(gè)體詞——所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體

個(gè)體常項(xiàng)：具體的事務(wù)，用a,b,c表示

個(gè)體變項(xiàng)：抽象的事物，用x,y,z表示

個(gè)體域(論域)——個(gè)體變項(xiàng)的取值范圍有限個(gè)體域，如{a,b,c},{1,2}無(wú)限個(gè)體域，如N,Z,R,…全總個(gè)體域——由宇宙間一切事物組成324.1一階邏輯命題符號(hào)化個(gè)體詞——所研究對(duì)象中可以獨(dú)立存謂詞謂詞——表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞

謂詞常項(xiàng)如,F(a)：a是人

謂詞變項(xiàng)如,F(x)：x具有性質(zhì)F

n（n1）元謂詞一元謂詞(n=1)——表示性質(zhì)多元謂詞(n2)——表示事物之間的關(guān)系

如,L(x,y)：x與y有關(guān)系L，L(x,y)：xy，…0元謂詞——不含個(gè)體變項(xiàng)的謂詞,即命題常項(xiàng)或命題變項(xiàng)33謂詞謂詞——表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞3量詞量詞——表示數(shù)量的詞

全稱量詞:表示所有的.

x:對(duì)個(gè)體域中所有的x如,xF(x)表示個(gè)體域中所有的x具有性質(zhì)F

xyG(x,y)表示個(gè)體域中所有的x和y有關(guān)系G

存在量詞:表示存在,有一個(gè).x:個(gè)體域中有一個(gè)x

如,xF(x)表示個(gè)體域中有一個(gè)x具有性質(zhì)F

xyG(x,y)表示個(gè)體域中存在x和y有關(guān)系G

xyG(x,y)表示對(duì)個(gè)體域中每一個(gè)x都存在一個(gè)y使得

x和y有關(guān)系GxyG(x,y)表示個(gè)體域中存在一個(gè)x使得對(duì)每一個(gè)y,

x和y有關(guān)系G34量詞量詞——表示數(shù)量的詞4實(shí)例1例1用0元謂詞將命題符號(hào)化(1)墨西哥位于南美洲(2)是無(wú)理數(shù)僅當(dāng)是有理數(shù)(3)如果2>3，則3<4解：在命題邏輯中：(1)p,p為墨西哥位于南美洲（真命題）(2)p→q,其中,p：是無(wú)理數(shù)，q：是有理數(shù).是假命題(3)pq,其中，p：2>3，q：3<4.是真命題35實(shí)例1例1用0元謂詞將命題符號(hào)化解：在命題邏輯中：5實(shí)例1解答在一階邏輯中：(1)F(a)，其中，a：墨西哥，F(xiàn)(x)：x位于南美洲.(2)F()G(),其中，F(xiàn)(x)：x是無(wú)理數(shù)，G(x)：x是有理數(shù)(3)F(2,3)G(3,4)，其中，F(xiàn)(x,y)：x>y，G(x,y)：x<y36實(shí)例1解答在一階邏輯中：6實(shí)例2例2在一階邏輯中將下面命題符號(hào)化(1)人都愛(ài)美(2)有人用左手寫字個(gè)體域分別為(a)D為人類集合(b)D為全總個(gè)體域解(a)(1)xG(x),G(x)：x愛(ài)美(2)xG(x),G(x)：x用左手寫字

(b)F(x)：x為人，G(x)：x愛(ài)美

(1)x(F(x)G(x))

(2)x(F(x)G(x))1.引入特性謂詞F(x)2.(1),(2)是一階邏輯中兩個(gè)“基本”公式37實(shí)例2例2在一階邏輯中將下面命題符號(hào)化解(a)實(shí)例3例3在一階邏輯中將下面命題符號(hào)化(1)正數(shù)都大于負(fù)數(shù)(2)有的無(wú)理數(shù)大于有的有理數(shù)解注意：題目中沒(méi)給個(gè)體域，一律用全總個(gè)體域(1)令F(x)：x為正數(shù)，G(y)：y為負(fù)數(shù),L(x,y)：x>yx(F(x)y(G(y)L(x,y)))或者xy(F(x)G(y)L(x,y))(2)令F(x)：x是無(wú)理數(shù)，G(y)：y是有理數(shù)，L(x,y)：x>y

x(F(x)y(G(y)L(x,y)))或者

xy(F(x)G(y)L(x,y))38實(shí)例3例3在一階邏輯中將下面命題符號(hào)化解注意：題目中沒(méi)實(shí)例4例4在一階邏輯中將下面命題符號(hào)化(1)沒(méi)有不呼吸的人(2)不是所有的人都喜歡吃糖解(1)F(x):x是人,G(x):x呼吸x(F(x)G(x))x(F(x)G(x))(2)F(x):x是人,G(x):x喜歡吃糖x(F(x)G(x))x(F(x)G(x))39實(shí)例4例4在一階邏輯中將下面命題符號(hào)化解(1)F(x實(shí)例5例5設(shè)個(gè)體域?yàn)閷?shí)數(shù)域,將下面命題符號(hào)化(1)對(duì)每一個(gè)數(shù)x都存在一個(gè)數(shù)y使得x<y(2)存在一個(gè)數(shù)x使得對(duì)每一個(gè)數(shù)y都有x<y解L(x,y):x<y(1)xyL(x,y)注意:與不能隨意交換顯然(1)是真命題,(2)是假命題(2)xyL(x,y)40實(shí)例5例5設(shè)個(gè)體域?yàn)閷?shí)數(shù)域,將下面命題符號(hào)化解4.2一階邏輯公式及解釋定義4.1設(shè)L是一個(gè)非邏輯符集合,由L生成的一階語(yǔ)言L的字母表包括下述符號(hào)：非邏輯符號(hào)(1)個(gè)體常項(xiàng)符號(hào)：a,b,c,…,ai,bi,ci,…,i

1(2)函數(shù)符號(hào)：f,g,h,…,fi,gi,hi,…,i

1(3)謂詞符號(hào)：F,G,H,…,Fi,Gi,Hi,…,i

1邏輯符號(hào)(4)個(gè)體變項(xiàng)符號(hào)：x,y,z,…,xi,yi,zi,…,i

1(5)量詞符號(hào)：,(6)聯(lián)結(jié)詞符號(hào)：,,,,

(7)括號(hào)與逗號(hào)：(,),，414.2一階邏輯公式及解釋定義4.1設(shè)L是一個(gè)非邏輯符集一階語(yǔ)言L

的項(xiàng)與原子公式定義4.2

L的項(xiàng)的定義如下：(1)個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng).(2)若(x1,x2,…,xn)是任意的n元函數(shù)，t1,t2,…,tn是任意的

n個(gè)項(xiàng)，則(t1,t2,…,tn)是項(xiàng).(3)所有的項(xiàng)都是有限次使用(1),(2)得到的如,a,x,x+y,f(x),g(x,y)等都是項(xiàng)定義4.3設(shè)R(x1,x2,…,xn)是L

的任意n元謂詞，t1,t2,…,tn

是L

的任意n個(gè)項(xiàng)，則稱R(t1,t2,…,tn)是L

的原子公式.如，F(xiàn)(x,y),F(f(x1,x2),g(x3,x4))等均為原子公式42一階語(yǔ)言L的項(xiàng)與原子公式定義4.2L的項(xiàng)的定義如下定義4.4

L

的合式公式定義如下：(1)原子公式是合式公式.(2)若A是合式公式，則(A)也是合式公式(3)若A,B是合式公式，則(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式，則xA,xA也是合式公式(5)只有有限次地應(yīng)用(1)—(4)形成的符號(hào)串才是合式公式.合式公式簡(jiǎn)稱公式如,F(x),F(x)G(x,y),x(F(x)G(x))xy(F(x)G(y)L(x,y))等都是合式公式一階語(yǔ)言L

的公式43定義4.4L的合式公式定義如下：一階語(yǔ)言L的公式13封閉的公式定義4.5在公式xA和xA中，稱x為指導(dǎo)變?cè)珹為相應(yīng)量詞的轄域.在x和x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項(xiàng)均稱為是自由出現(xiàn)的.例如，x(F(x,y)G(x,z))，x為指導(dǎo)變?cè)?F(x,y)G(x,z))為x的轄域，x的兩次出現(xiàn)均為約束出現(xiàn)，y與z均為自由出現(xiàn)又如,x(F(x,y,z)y(G(x,y)H(x,y,z))),x中的x是指導(dǎo)變?cè)?轄域?yàn)?F(x,y,z)y(G(x,y)H(x,y,z))).y中的y是指導(dǎo)變?cè)?轄域?yàn)?G(x,y)H(x,y,z)).x的3次出現(xiàn)都是約束出現(xiàn),y的第一次出現(xiàn)是自由出現(xiàn),后2次是約束出現(xiàn),z的2次出現(xiàn)都是自由出現(xiàn)44封閉的公式定義4.5在公式xA和xA中，稱x封閉的公式定義4.6若公式A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為封閉的公式，簡(jiǎn)稱閉式.例如，xy(F(x)G(y)H(x,y))為閉式，而x(F(x)G(x,y))不是閉式45封閉的公式定義4.6若公式A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則公式的解釋定義4.7設(shè)L

是L生成的一階語(yǔ)言,L的解釋I由4部分組成：(a)非空個(gè)體域DI.(b)

對(duì)每一個(gè)個(gè)體常項(xiàng)符號(hào)aL,有一個(gè)DI,稱

為a在I

中的解釋.(c)對(duì)每一個(gè)n元函數(shù)符號(hào)fL,有一個(gè)DI上的n元函數(shù),稱

為f在I中的解釋.(d)對(duì)每一個(gè)n元謂詞符號(hào)FL,有一個(gè)DI上的n元謂詞常項(xiàng),稱

為F在I中的解釋.設(shè)公式A,取個(gè)體域DI,把A中的個(gè)體常項(xiàng)符號(hào)a、函數(shù)符號(hào)f、謂詞符號(hào)F分別替換成它們?cè)贗中的解釋、、,稱所得到的公式A為A在I下的解釋,或A在I下被解釋成A.46公式的解釋定義4.7設(shè)L是L生成的一階語(yǔ)言,L的解實(shí)例例6給定解釋I如下：(a)個(gè)體域D=R(b)(c)(d)

寫出下列公式在I下的解釋,并指出它的真值.(1)xF(f(x,a),g(x,a))

x(x+0=x0)真(2)xy(F(f(x,y),g(x,y))F(x,y))xy(x+y=xyx=y)假(3)xF(g(x,y),a)x(xy=0)真值不定,不是命題47實(shí)例例6給定解釋I如下：x(x+0=x0公式的類型定理4.1閉式在任何解釋下都是命題注意:不是閉式的公式在解釋下可能是命題,也可能不是命題.定義4.8若公式A在任何解釋下均為真,則稱A為永真式(邏輯有效式).若A在任何解釋下均為假,則稱A為矛盾式(永假式).若至少有一個(gè)解釋使A為真,則稱A為可滿足式.幾點(diǎn)說(shuō)明：永真式為可滿足式，但反之不真判斷公式是否是可滿足的(永真式,矛盾式)是不可判定的48公式的類型定理4.1閉式在任何解釋下都是命題18代換實(shí)例定義4.9設(shè)A0是含命題變項(xiàng)p1,p2,…,pn的命題公式，A1,A2,…,An是n個(gè)謂詞公式，用Ai

(1in)處處代替A0中的pi，所得公式A稱為A0的代換實(shí)例.例如，F(xiàn)(x)G(x),xF(x)yG(y)等都是pq的代換實(shí)例.定理4.2重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式.49代換實(shí)例定義4.9設(shè)A0是含命題變項(xiàng)p1,p2,…實(shí)例例7判斷下列公式中，哪些是永真式，哪些是矛盾式？(1)xF(x)(xyG(x,y)xF(x))重言式p(qp)的代換實(shí)例，故為永真式.(2)(xF(x)yG(y))yG(y)矛盾式(pq)q的代換實(shí)例，故為永假式.(3)x(F(x)G(x))解釋I1:個(gè)體域N,F(x):x>5,G(x):x>4,公式為真解釋I2:個(gè)體域N,F(x):x<5,G(x):x<4,公式為假結(jié)論:非永真式的可滿足式50實(shí)例例7判斷下列公式中，哪些是永真式，哪些是矛盾式？重言第四章習(xí)題課主要內(nèi)容個(gè)體詞、謂詞、量詞一階邏輯命題符號(hào)化一階語(yǔ)言L

項(xiàng)、原子公式、合式公式公式的解釋量詞的轄域、指導(dǎo)變?cè)?、個(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn)、閉式、解釋公式的類型永真式(邏輯有效式)、矛盾式(永假式)、可滿足式51第四章習(xí)題課主要內(nèi)容21基本要求準(zhǔn)確地將給定命題符號(hào)化理解一階語(yǔ)言的概念深刻理解一階語(yǔ)言的解釋熟練地給出公式的解釋記住閉式的性質(zhì)并能應(yīng)用它深刻理解永真式、矛盾式、可滿足式的概念,會(huì)判斷簡(jiǎn)單公式的類型52基本要求準(zhǔn)確地將給定命題符號(hào)化22練習(xí)11.在分別取個(gè)體域?yàn)?a)D1=N

(b)D2=R(c)D3為全總個(gè)體域的條件下,將下面命題符號(hào)化，并討論真值(1)對(duì)于任意的數(shù)x，均有解設(shè)G(x):(a)xG(x)(b)xG(x)(c)又設(shè)F(x):x是實(shí)數(shù)

x(F(x)G(x))真真假53練習(xí)11.在分別取個(gè)體域?yàn)榻庠O(shè)G(x):(b)xG練習(xí)1(續(xù))解設(shè)H(x)：x+7=5(a)xH(x)(2)存在數(shù)x，使得x+7=5(b)xH(x)(c)又設(shè)F(x)：x為實(shí)數(shù)

x(F(x)H(x))本例說(shuō)明：不同個(gè)體域內(nèi)，命題符號(hào)化形式可能不同（也可能相同），真值可能不同（也可能相同）.真真假54練習(xí)1(續(xù))解設(shè)H(x)：x+7=5(2)存在數(shù)練習(xí)22.在一階邏輯中將下列命題符號(hào)化(1)大熊貓都可愛(ài)(2)有人愛(ài)發(fā)脾氣(3)說(shuō)所有人都愛(ài)吃面包是不對(duì)的設(shè)F(x):x為大熊貓，G(x):x可愛(ài)x(F(x)G