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

第四章

一階邏輯基本概念蘇格拉底三段論所有的人都是要死的。蘇格拉底是人。所以，蘇格拉底是要死的。試證明此推理。解：令p:所有的人都是要死的,q:蘇格拉底是人,r:蘇格拉底是要死的，則前提：p，q結(jié)論：r推理的形式結(jié)構(gòu)：p

ù

q

?

r說明：命題邏輯能夠解決的問題是有局限性的。第1頁命題邏輯的局限性在命題邏輯中,研究的基本單位是簡單命題,對簡單命題不再進行分解,并且不考慮命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系。一階邏輯所研究的內(nèi)容為了克服命題邏輯的局限性,將簡單命題再細(xì)分,分析出個體詞、謂詞和量詞,以期達(dá)到表達(dá)出個體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系?！?.1一階邏輯命題符號化§4.2一階邏輯公式及解釋§5.1一階邏輯等值式與置換規(guī)則§5.2一階邏輯前束范式第2頁第四章

一階邏輯基本概念個體詞謂詞量詞一階邏輯命題符號化第3頁§4.1一階邏輯命題符號化§4.1一階邏輯命題符號化引例小王是一名大二學(xué)生。小李是一名大二學(xué)生。3是奇數(shù)。小王與小李是好朋友。如果5>4,則4>6。x是奇數(shù)。x與y具有關(guān)系L。所有的大學(xué)生都會講英語。(9)有的大學(xué)生會講法語。三個基本要素:個體詞,謂詞,量詞。第4頁一、個體詞1、定義：研究對象中可以獨立存在的具體或抽象的客體。如：小王，小李，3，5，6，x，y。2、分類：個體常項：具體或特定的客體，用a,b,c,…表示。個體變項：抽象或泛指的客體，用x,y,z,…表示。3、個體域(論域)：個體變項的取值范圍通，常用D表示。有限個體域，如{a,b,c},{1,2}無限個體域，如N,Z,R,…4.全總個體域：由宇宙間一切事物組成的個體域。注：題目中未明確說明時，指的是全總個體域。第5頁二、謂詞第6頁1、定義：表示個體詞性質(zhì)或相互之間關(guān)系的詞。2.表示：常用大寫英文字母F,G,H,…表示引例中：(1)小王是一名大二學(xué)生。設(shè)a:小王，“是一名大二學(xué)生”是謂詞,記為F。與 好朋友”是謂詞,記為H,則命題符號化為F(a)。(4)小王與小李是好朋友。設(shè)a:小王，b:小李“，命題符號化為H(a,b)。(6)x是奇數(shù)。x是個體變項,“命題符號化為G(x)。是奇數(shù)”是謂詞,記為G,二、謂詞第7頁3、分類謂詞常項：表示具體性質(zhì)或關(guān)系的謂詞。如:F：“ 是一名大二學(xué)生”，G：“ 與 好朋友”。 謂詞變項：表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞。如:“x與y具有關(guān)系L。”中的關(guān)系L。4、n(n 1)元謂詞：含n個個體變項的謂詞。一元謂詞(n=1)：表示性質(zhì)，如F(x)；多元謂詞(n 2)：表示事物之間的關(guān)系如，H(x,y)。5.0元謂詞：不含個體變項的謂詞，如F(a),G(3),H(a,b)。例1將下列命題在一階邏輯中用0元謂詞符號化,并討論真值。第8頁(1)只有2是素數(shù)，4才是素數(shù)。(2)如果5大于4，則4大于6。解:(1)設(shè)F(x):x是素數(shù)，命題符號化為F(4)?F(2)，命題為真。(2)設(shè)G(x,y):x大于y，命題符號化為G(5,4)?G(4,6)，命題為假。三、量詞1、定義：表示個體常項或變項之間數(shù)量關(guān)系的詞。如：“所有的大學(xué)生都會講英語。”中“所有的”。“有的大學(xué)生會講法語?！敝小坝械摹薄?.全稱量詞 ：表示所有的，一切的，每一個，任意…◆x說明:xF(x)表示個體域中所有的x具有性質(zhì)F；x yG(x,y)表示個體域中所有的x和y有關(guān)系G。第9頁如:設(shè)個體域:大學(xué)生，F(xiàn)(x):x會講英語，G(x,y):x和y年齡相同。則xF(x)表示所有的大學(xué)生都會講英語。yG(x,y)表任示意兩個大學(xué)生年齡相同。三、量詞3.存在量詞 ：表示存在，有一個，有的，至少有一個…如：設(shè)個體域：大學(xué)生，F(xiàn)(x):x會講法語，則xF(x)表示有的大學(xué)生會講法語。說明： xF(x)表示個體域中有一個x具有性質(zhì)F。如：設(shè)個體域:R，G(x,y):x<y，下列各式表示的含義為？x yG(x,y),表示存在兩個實數(shù)x和y使得x<y。x yG(x,y),表示對每一個數(shù)x都存在一個數(shù)y使得x<y。x yG(x,y)表示存在一個數(shù)x使得對每一個數(shù)y都有x<y。說明： x yG(x,y)和 x yG(x,y)表示的含義不同！第10頁四、符號化xF(x)xG(x)(1)

x(M(x)

?

F(x))(2)x(M(x)

G(x))特性謂詞例2在一階邏輯中將下面命題符號化。(1)人都愛美。(2)有人用左手寫字。個體域分別為:(a)D為人類集合(b)D為全總個體域解:(a)設(shè)F(x):x愛美，G(x):x用左手寫字，則(b)設(shè)F(x):x愛美,G(x):x用左手寫字,M(x):x是人,則說明:不同的個體域，命題符號化形式可能不同（也可能相同）。第11頁特性謂詞 在全總個體域中,表示具體個體域的謂詞。特性謂詞加入時遵循的原則全稱量詞(存在量詞(x),特性謂詞作為蘊涵式前件加入。x),特性謂詞作為合取項加入。對于宇宙間的所有個體都是人并且愛美。x(M(x) G(x))表示:存在宇宙間的個體，若這個個體是人，則他用左手寫字。如例2

(1)人都愛美。

(2)有人用左手寫字。個體域

(b)

D為全總個體域第12頁解:設(shè)F(x):x愛美，G(x):x用左手寫字，M(x):x是人，則(1)注:

?

x(M(x)x(M(x)?F(x)) (2) x(M(x) G(x))F(x))表示:例3在個體域限制為(a)和(b)條件時,將下列命題符號化,并求真值。對于任意的x，均有x2-3x+2=(x-1)(x-2)。存在x，使得x+5=3。其中(a)個體域N (b)個體域R解:(a)設(shè)F(x):x2-3x+2=(x-1)(x-G2()x，):x+5=3。則符號化為:xF(x)，真值為:1。符號化為:xG(x)，真值為:0。(b)符號化同(a)，真值為:1。說明:不同的個體域，命題真值可能不同（也可能相同）。第13頁例4在一階邏輯中將下面命題符號化。(1)所有的人長著黑頭發(fā)。(2)有的人登上過月球。(3)沒有人登上過木星。(4)在美國留學(xué)的學(xué)生未必都是亞洲人。全總個體域第14頁解:(1)設(shè)M(x):x是人F，(x):x長著黑頭發(fā)。符號化為x(M(x)?F(x))。設(shè)M(x):x是人，G(x):x登上過月球。符號化為x(M(x) G(x))。令M(x):x是人，H(x):x登上過木星。符號化為﹁ x(M(x) H(x))。令F(x):x是在美國留學(xué)的學(xué)生，G(x):x是亞洲人。符號化為﹁ x(F(x)?G(x))。例5在一階邏輯中將下面命題符號化。第15頁兔子比烏龜跑得快。有的兔子比有的烏龜跑得快。有的兔子比所有的烏龜跑得快。所有的兔子比有的烏龜跑得快。解:設(shè)F(x):x是兔子,G(y):y是烏龜,H(x,y):x比y跑得快,(1)xx

(F(x)y(F(x)(y(G(y)

H(x,y)))或G(y)

H(x,

y))(2)x

(F(x)(y(F(y)

H(x,y)))或xy(F(x)F(y)

H(x,

y))(3)x(F(x)y(G(y)

H(x,

y)))(4)x(F(x)y(G(y)

H(x,

y)))例5在一階邏輯中將下面命題符號化。第16頁并不是所有的兔子都比烏龜跑得快。不存在跑的同樣快的兩只兔子。解:設(shè)F(x):x是兔子,G(y):y是烏龜,H(x,y):x比y跑得快,L(x,y):