離散結(jié)構(gòu)及應(yīng)用-ALL

1、離散結(jié)構(gòu)與應(yīng)用湖北經(jīng)濟(jì)學(xué)院湖北經(jīng)濟(jì)學(xué)院 軟件工程系軟件工程系第1部分 數(shù)理邏輯第1章 命題邏輯第2章 一階邏輯第1章 命題邏輯這章是以“命題”為中心，主要討論： 1、命題的表示、命題的演算 2、命題演算中的公式，及其應(yīng)用 3、命題邏輯推理1.1 1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 命題是一個(gè)能確定是真的或是假的判斷。（判命題是一個(gè)能確定是真的或是假的判斷。（判斷都是用陳述句表示）斷都是用陳述句表示） 判斷一個(gè)語句是否為命題，首先看是否為陳述句，再看其真值是否唯一。 例：判定下面這些句子哪些是命題。例：判定下面這些句子哪些是命題。 2是個(gè)素?cái)?shù)。 雪是黑色的。 2017年人類將到達(dá)火星。 如果 ab

2、且bc，則ac。 x+yb、bc、ac)構(gòu)成的復(fù)合命題。1.1 1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 復(fù)合命題：是用“聯(lián)結(jié)詞”將原子命題聯(lián)結(jié)起來構(gòu)成的。定義了六個(gè)邏輯聯(lián)結(jié)詞： (1) 否定： (2) 合取： 并且 (3) 析?。?可兼取的或者 (4) 異或： 不可兼取的或 （教程未提） (5) 蘊(yùn)涵： 如果。，那么。 (6) 等價(jià)：1.1 1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 P Q PQ PQ PQ PQ F F F F T T F T F T T F T F F T F F T T T T T T1.1 1.1 命題與聯(lián)結(jié)詞（課題練習(xí)）命題與聯(lián)結(jié)詞（課題練習(xí)） 已知PQ為T，則P為( )，Q為(

3、)。 已知PQ為F，則P為( )，Q為( )。 已知P為F，則PQ為( )。 已知P為T，則PQ為( )。 已知PQ為T，且P為F ，則Q為( )。 已知PQ為F，則P為( )，Q為( )。 已知P為F，則PQ為( )。 已知Q為T，則PQ為( )。1.1 1.1 命題與聯(lián)結(jié)詞（課題練習(xí)）命題與聯(lián)結(jié)詞（課題練習(xí)） 已知 PQ為F，則P為( )， Q為( )。 已知P為T，PQ為T，則Q為( )。 已知Q為T, PQ為T，則P為( )。 已知PQ為T，P為T , 則Q為( ). 已知PQ為F，P為T , 則Q為( ). PP 的真值為( ). PP 的真值為( )。1.2 1.2 命題公式及符號(hào)

4、化命題公式及符號(hào)化 常值命題：常值命題：即是我們前面所說的命題。它有具體含義 (真值)。 例如：“3是素?cái)?shù)?！本褪浅Ｖ得}。 命題變?cè)好}變?cè)河么髮懙挠⑽淖帜溉鏟、Q等表示任何命題。稱這些字母為命題變?cè)?對(duì)命題變?cè)髦概蓪?duì)命題變?cè)髦概? (給命題變?cè)粋€(gè)解釋給命題變?cè)粋€(gè)解釋) )：將一個(gè)常值命題賦予命題變?cè)倪^程，或者是直接賦給命題變?cè)嬷怠癟”或“F”的過程。 注意：注意：命題變?cè)旧聿皇敲}，只有給它一個(gè)解釋，才變成命題。1.2 1.2 命題公式及符號(hào)化命題公式及符號(hào)化 合式公式合式公式 ( wff ) (well formed formulas) ( wff ) (well f

5、ormed formulas)：對(duì)計(jì)算機(jī)而言，最方便的定義方式就是構(gòu)造性的（或遞歸性的），即用簡單的原子命題變?cè)吐?lián)結(jié)詞，通過有限步構(gòu)造出新的復(fù)合命題來。因此，我們給出下面的定義： 見教程 P6/定義1.10 注意：注意：這個(gè)定義是遞歸的。(1)是遞歸的基礎(chǔ)，由(1)開始，使用(2)、(3)規(guī)則，可以得到任意的合式公式。1.2 1.2 命題公式及符號(hào)化命題公式及符號(hào)化 對(duì)每個(gè)命題變?cè)梢杂袃蓚€(gè)真值(T,F)被指派，所以有n個(gè)命題變?cè)拿}公式 A(P1,P2,Pn) 的真值表有2n行。 為有序地列出A(P1,P2,Pn)的真值表，可將F看成0、T看成1，按二進(jìn)制數(shù)次序列表。如A(P,Q)的真值

6、表可按照如下次序指派：00(FF)，01(FT)，10(TF)，11(TT) A(P,Q,R)的真值表可按照如下次序指派： 0 1 2 3 4 5 6 7000 001 010 011 100 101 110 111FFF FFT FTF FTT TFF TFT TTF TTT1.2 1.2 命題公式及符號(hào)化命題公式及符號(hào)化命題符號(hào)化定義： 用命題公式的符號(hào)串來表示給定的命題。命題符號(hào)化的方法： 1.首先要明確給定命題的含義。 2.對(duì)于復(fù)合命題，找聯(lián)結(jié)詞，用聯(lián)結(jié)詞斷句，分解出各個(gè)原子命題。 3.設(shè)原子命題符號(hào)，并用邏輯聯(lián)結(jié)詞聯(lián)結(jié)原子命題符號(hào)，構(gòu)成給定命題的符號(hào)表達(dá)式。1.2 1.2 命題公式及

7、符號(hào)化命題公式及符號(hào)化例 如果小張與小王都不去，則小李去。 P：小張去。 Q：小王去。 R：小李去。 該命題可寫成： (PQ)R 如果小張與小王不都去，則小李去。 該命題可寫成： (PQ)R 也可以寫成： (PQ)R1.2 1.2 命題公式及符號(hào)化命題公式及符號(hào)化重言式(矛盾式)定義定義：A(P1,P2,Pn) 是含有命題變?cè)狿1,P2, Pn的命題公式，如不論對(duì)P1, P2 , , Pn作任何指派，都使得A(P1,P2, Pn) 為真(假)，則稱之為重言式(矛盾式), 也稱之為永真式 (永假式)。重言式的證明方法證明方法： 方法1：列真值表。 方法2：公式的等價(jià)變換，化簡成“T”。 方法3：

8、用公式的主析取范式。1.2 1.2 命題公式及符號(hào)化命題公式及符號(hào)化例如，證明 (P(PQ)Q 為重言式。 P Q PQ P(PQ) (P(PQ)QF F T F TF T T F TT F F F T T T T T T1.3 1.3 等值演算（定義）等值演算（定義） 定義：定義：A、B 是含有命題變?cè)?P1,P2, Pn 的命題公式，如不論對(duì) P1, P2 , , Pn 作任何指派，都使得 A 和 B 真值相同，則稱之為 A與B 等值，記作AB。 例如：PQ P Q Q P 定義：定義：根據(jù)已知等值式，推演出另一些等值式的過程稱為 等值演算等值演算。1.3 1.3 等值演算（重要的等值公式

9、等值演算（重要的等值公式1 1） 雙重否定律，對(duì)合律 P P 冪等律 PP P PP P 結(jié)合律 P(QR) (PQ)R P(QR) (PQ)R 交換律 PQQP PQQP 分配律 P(QR)(PQ)(PR) P(QR)(PQ)(PR) 吸收律 P(PQ)P P(PQ)P1.3 1.3 等值演算（重要的等值公式等值演算（重要的等值公式2 2）德-摩根定律 (PQ) PQ (PQ) PQ 同一律 P0 P P1 P 零律 P1 1 P0 0 互補(bǔ)律 PP 1 PP 0 PQ PQ PQQP PQ (PQ)(QP) 等價(jià)等值式 PQ (PQ)(PQ) PQ (PQ) (PQ ) 1.3 1.3 等

10、值演算（和集合公式關(guān)系）等值演算（和集合公式關(guān)系） 對(duì)合律 AA A表示A的絕對(duì)補(bǔ)集 冪等律 AAA AAA 結(jié)合律 A(BC)(AB)C A(BC)(AB)C交換律 ABBA ABBA分配律 A(BC)(AB)(AC) A(BC)(AB)(AC)1.3 1.3 等值演算（和集合公式關(guān)系）等值演算（和集合公式關(guān)系） 吸收律 A(AB)A A(AB)A 德-摩根定律 (AB)AB (AB)AB 同一律 AA AEA E表示全集 零律 AEE A 否定律 AAE AA1.3 1.3 等值演算（判斷等值方法）等值演算（判斷等值方法） 方法方法1 1：用列真值表。 方法方法2 2：用公式的等價(jià)變換。(

11、即置換定律) 置換定律: A是一個(gè)命題公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，則AB。 應(yīng)用置換定律以及前面列出的等價(jià)公式可以對(duì)給定公式進(jìn)行等價(jià)變換。1.3 1.3 等值演算（等值判斷例）等值演算（等值判斷例）例. 求證 (PQ)(PQ) P 證明： (PQ)(PQ) (PQ)(PQ) (蘊(yùn)涵等值式) (PQ)(PQ) (摩根定律) (PQ)(PQ) (對(duì)合律) P(QQ) (分配律) PT (互補(bǔ)律) P (同一律)1.3 1.3 等值演算（等值化簡例）等值演算（等值化簡例）例.化簡 (PQ)(P(PQ) 解 原公式 (PQ)(PP)Q) (蘊(yùn)涵等值 結(jié)合

12、) (PQ)(PQ) (對(duì)合律 冪等律) (PQ)(QP) (交換律) (PQ)Q)P (結(jié)合律) QP (吸收律)1.3 1.3 等值演算（性質(zhì)）等值演算（性質(zhì)） 1). 自反性：任何命題公式A，有AA。 2). 對(duì)稱性：若 AB，則BA 3). 傳遞性：若 AB 且 BC，則 AC 4). 如果A(P1,P2,Pn) B(P1,P2,Pn)，則A(P1, P2, Pn) B(P1, P2, Pn) 1.4 1.4 范式（定義，合取式，析取式）范式（定義，合取式，析取式） 范式就是命題公式形式的規(guī)范形式。這里約定在范式中只含有聯(lián)結(jié)詞 、 和 。 合取式：合取式：是用“”聯(lián)結(jié)命題變?cè)}變?cè)?

13、或 變?cè)姆褡冊(cè)姆穸ǘ?構(gòu)成的式子。 析取式：析取式：是用“”聯(lián)結(jié) 命題變?cè)}變?cè)?或 變?cè)淖冊(cè)姆穸ǚ穸?構(gòu)成的式子。1.4 1.4 范式（定義，合取范式，析取范式）范式（定義，合取范式，析取范式）合取范式：合取范式：公式 A 如果寫成如下形式： A1 A2 . An (n1) ，每個(gè)Ai (i=1,2,n)都是是析取式 ，稱之為 A 的合取范式合取范式。析取范式：析取范式：公式 A 如果寫成如下形式： A1 A2 . An (n1) ，每個(gè)Ai (i=1,2,n)都是是合取式 ，稱之為 A 的析取范式析取范式。1.4 1.4 范式（范式（求求 合取范式，析取范式）合取范式，析取范式）

14、1 1、先用相應(yīng)的公式去掉 和 。2 2、用 對(duì)偶式性質(zhì)對(duì)偶式性質(zhì) 或 摩根定律摩根定律 將 后移到命題變?cè)啊? 3、用分配律分配律、冪等律冪等律 等公式進(jìn)行整理。1.5 1.5 推理演算推理演算推理推理就是根據(jù)一個(gè)或幾個(gè)已知的判斷得出一個(gè)新的判斷的思維過程。稱這些已知的判斷為前提。得到的新的判斷為前提的有效結(jié)論。實(shí)際上，推理的過程就是證明重言蘊(yùn)含式 的過程，即令 H1，H2，Hn 是已知的命題公式(前提)，若有 H1 H2 . Hn C則稱C是H1，H2，Hn的有效結(jié)論，簡稱結(jié)論。1.X 1.X 小結(jié)小結(jié)命命 題題原子命題原子命題復(fù)合命題復(fù)合命題聯(lián)結(jié)詞聯(lián)結(jié)詞命題公式命題公式永真式永真式永真

15、蘊(yùn)涵式永真蘊(yùn)涵式等價(jià)公式等價(jià)公式范式范式命題邏輯推理命題邏輯推理直接推理直接推理間接推理間接推理?xiàng)l件論證條件論證反證法反證法析取析取合取合取主析取主析取主合取主合取第2章 一階邏輯這章是以“謂詞”為中心，主要討論： 1、命題中的謂詞、量詞 2、謂詞公式及翻譯、等價(jià)式 3、謂詞推理演算2.1 2.1 謂詞概念（個(gè)體）謂詞概念（個(gè)體） 定義：定義：能夠獨(dú)立存在的事物，稱之為個(gè)體，也稱之為客體。它可以是具體的，也可以是抽象的事物。通常用小寫英文字母a、b、c、.表示。例如，小張、小李、8、a、沈陽、社會(huì)主義等等都是個(gè)體個(gè)體。 定義：定義：用小寫英文字母x、y、z.表示任何個(gè)體，則稱這些字母為個(gè)體變項(xiàng)

16、個(gè)體變項(xiàng)（客體變?cè)?注意：注意：個(gè)體變項(xiàng)本身不是個(gè)體。2.1 2.1 謂詞概念（謂詞）謂詞概念（謂詞） 定義：定義：一個(gè)大寫英文字母后邊有括號(hào)，括號(hào)內(nèi)是若干個(gè)個(gè)體變項(xiàng)個(gè)體變項(xiàng)，用以表示客體的屬性或者客體之間的關(guān)系，稱之為 謂詞謂詞。如果括號(hào)內(nèi)有n個(gè)個(gè)體變項(xiàng)個(gè)體變項(xiàng)，稱該謂詞為 n n元謂詞元謂詞。 例如： S(x): S(x):表示表示x x是大學(xué)生。是大學(xué)生。 一元謂詞一元謂詞 G(x,y) G(x,y)：表示：表示 xy xy。 二元謂詞二元謂詞 B(x,y,z) B(x,y,z)：表示：表示x x在在y y與與z z之間。之間。 三元謂詞三元謂詞2.1 2.1 謂詞概念（謂詞理解）謂

17、詞概念（謂詞理解） 謂詞本身并不是不是命題，只有謂詞的括號(hào)內(nèi)填入足夠的客體，才變成命題。例如 a表示小張，b表示小李，則 S(a) 表示小張是大學(xué)生。S(b)表示小李是大學(xué)生。 (7,3)表示:。 如果c表示錦州，d表示沈陽，e表示山海關(guān)， B(c,d,e)表示：錦州在沈陽與山海關(guān)之間。 這時(shí) S(a)S(a)、S(b)S(b)、G(7,3)G(7,3)、B(c,d,e) B(c,d,e) 才是命題。才是命題。2.1 2.1 謂詞概念（命題函數(shù)）謂詞概念（命題函數(shù)） 定義：定義：n元謂詞P(x1,x2,xn)稱之為簡單命題函數(shù)。規(guī)定：當(dāng)命題函數(shù)P(x1,x2,xn)中 n=0 時(shí)，即0元謂詞，

18、表示不含有個(gè)體變項(xiàng)的謂詞，它本身就是一個(gè)命題變?cè)?定義：定義：將若干個(gè)簡單命題函數(shù)簡單命題函數(shù)用邏輯聯(lián)結(jié)詞聯(lián)結(jié)起來，構(gòu)成的表達(dá)式，稱之為復(fù)合命題函數(shù)。簡單命題函數(shù)與復(fù)合命題函數(shù)統(tǒng)稱為命題函數(shù)命題函數(shù)。2.1 2.1 謂詞概念（命題函數(shù)例）謂詞概念（命題函數(shù)例） 例如，給定簡單命題函數(shù)： A(x)：x 身體好， B(x)：x 學(xué)習(xí)好， C(x)：x 工作好， 復(fù)合命題函數(shù) A(x) ( B(x) C(x) ) 表示：如果 x 身體不好，則 x 的學(xué)習(xí)與工作都不好。2.1 2.1 謂詞概念（量詞）謂詞概念（量詞） 例如在“有些人是大學(xué)生”，“所有事物都是發(fā)展變化的?！敝校?“有些有些”,“”,

19、“所有的所有的” ”,就是對(duì)客體量化的詞。 定義：定義：在命題中表示對(duì)客體數(shù)量化的詞，稱之為量詞量詞。 (1). (1). 存在量詞：存在量詞：記作記作 ，表示，表示“ “至少一個(gè)至少一個(gè)” ”、“ “一些一些” ”、“ “某些某些” ”、“ “有些有些” ”等。等。 (2). (2). 全稱量詞：全稱量詞：記作記作 ，表示，表示“ “任何一個(gè)任何一個(gè)” ”、“ “每個(gè)每個(gè)” ”、“ “一切一切” ”、“ “所有的所有的” ”、“凡是凡是”、“任任意的意的”等。等。2.1 2.1 謂詞概念（量詞解析）謂詞概念（量詞解析） 量詞后邊要有一個(gè)個(gè)體變項(xiàng)，用以指明對(duì)哪個(gè)個(gè)體變項(xiàng)量化，可稱之為指導(dǎo)變項(xiàng)。

20、 例如, x (讀作“任意 x”)， x (讀作“存在 x”)，其中的 x 就是量詞后的指導(dǎo)變項(xiàng)。 例例. .所有的自然數(shù)都是整數(shù)。 設(shè) N(x)：x是自然數(shù)。I(x)：x是整數(shù)。 此命題可以寫成 x(N(x)I(x)2.1 2.1 謂詞概念（量詞解析）謂詞概念（量詞解析）例例. .有些自然數(shù)是偶數(shù)。 設(shè) N(x)：x是自然數(shù), E(x)：x是偶數(shù)。 此命題可以寫成 x(N(x)E(x) 例例 3. 3.每個(gè)人都有一個(gè)生母。 設(shè) P(x): x是個(gè)人 M(x,y): y是x的生母。 此命題可以寫成 x(P(x) y(P(y)M(x,y)2.2 2.2 謂詞公式和符號(hào)化（定義）謂詞公式和符號(hào)化（

21、定義） 定義：定義：稱 n元謂詞 P(x1,x2,.,xn) 為 原子謂詞原子謂詞公式公式。 謂詞合式公式謂詞合式公式 (WFF，Well Formed Formulas)遞歸定義如教程 P23 頁定義2-6。 謂詞合式公式謂詞合式公式也叫也叫謂詞公式謂詞公式，簡稱，簡稱公式公式。 注意：為了方便，最外層括號(hào)可省略，但若注意：為了方便，最外層括號(hào)可省略，但若量詞后邊有括號(hào)，則括號(hào)不能省。在謂詞公式量詞后邊有括號(hào)，則括號(hào)不能省。在謂詞公式中，量詞作用范圍稱為量詞的作用域（轄域）。中，量詞作用范圍稱為量詞的作用域（轄域）。 2.2 2.2 謂詞公式和符號(hào)化（規(guī)則）謂詞公式和符號(hào)化（規(guī)則） 如果量詞

22、后邊只是一個(gè)原子謂詞公式只是一個(gè)原子謂詞公式時(shí)時(shí)，該量詞的轄域就是此原子謂詞公式。 如果量詞后邊是括號(hào)括號(hào)，則此括號(hào)所表示的區(qū)域就是該量詞的轄域。 如果多個(gè)量詞緊挨著出現(xiàn)，則后邊的量詞及后邊的量詞及其轄域其轄域 就是 前邊量詞的轄域前邊量詞的轄域。 2.2 2.2 謂詞公式和符號(hào)化（例題）謂詞公式和符號(hào)化（例題） 已知 P(x):xP(x):x是素?cái)?shù)是素?cái)?shù)，E(x):xE(x):x是偶數(shù)是偶數(shù)，O(x):xO(x):x是奇是奇數(shù)數(shù)，N(x,y):xN(x,y):x可以整除可以整除y y，將下列各式翻譯成自然語言。( x)(E(x)( y)(N(y,x)E(y)( x)(P(x)( y)(O(y

23、)N(y,x)( x)(O(x)( y)(E(y)N(y,x) 2.1 2.1 謂詞公式符號(hào)化（關(guān)于變項(xiàng)）謂詞公式符號(hào)化（關(guān)于變項(xiàng)）定義：定義：在謂詞公式中的個(gè)體變項(xiàng)可以分成兩種：受到量詞約束的受到量詞約束的，不受量詞約束的不受量詞約束的。例如： x(F(x,y)x(F(x,y) yP(y) Q(z) yP(y) Q(z) xA(x)xA(x) ，思考那些個(gè)體變項(xiàng)受約束，那些不受。定義：定義：如果個(gè)體變項(xiàng) x 在 x 或者 x 的轄域內(nèi)，則 x 在此轄域內(nèi)約束出現(xiàn)，并稱 x 在此轄域內(nèi)是 約束變項(xiàng)約束變項(xiàng)。否則 x 是自由出現(xiàn)，并稱 x是 自自由變項(xiàng)由變項(xiàng)。2.1 2.1 謂詞公式符號(hào)化（關(guān)于

24、變項(xiàng)）謂詞公式符號(hào)化（關(guān)于變項(xiàng)）對(duì)于約束變項(xiàng)和自由變項(xiàng)：對(duì)于約束變項(xiàng)和自由變項(xiàng)：(1).對(duì)約束變項(xiàng)用什么符號(hào)表示無關(guān)緊要。對(duì)約束變項(xiàng)用什么符號(hào)表示無關(guān)緊要。即 xA(x)xA(x)與 yA(y)yA(y)是一樣的。類似于積分與積分變項(xiàng)無關(guān)，即積分f(x)dxf(x)dx與f(y)dyf(y)dy 相同。(2).謂詞公式如無自由變項(xiàng)，就表示一個(gè)命題。謂詞公式如無自由變項(xiàng)，就表示一個(gè)命題。例如 A(x) A(x) 表示 x 是大學(xué)生。 xA(x) xA(x) 或者 xA(x) xA(x) 就命題，分別表示“有些人是大學(xué)生”和“所有人都是大學(xué)生”。2.1 2.1 謂詞公式符號(hào)化（關(guān)于論域）謂詞公式符

25、號(hào)化（關(guān)于論域）在謂詞演算中，命題的符號(hào)化比較復(fù)雜，命題命題的符號(hào)表達(dá)式與論域有關(guān)系。的符號(hào)表達(dá)式與論域有關(guān)系。例如：每個(gè)自然數(shù)都是整數(shù)每個(gè)自然數(shù)都是整數(shù)。如論域是自然數(shù)集合N，令 I(x)I(x)：x x是整數(shù)是整數(shù)，命題為 xI(x)xI(x)。 如果論域擴(kuò)大為全總個(gè)體域時(shí)，上述表達(dá)式表示“所有客體都是整數(shù)”，顯然是假命題。因此需要添加謂詞 N(x)N(x)：x x是自然數(shù)是自然數(shù)，命題的符號(hào)表達(dá)式為: x(N(x)I(x)x(N(x)I(x)2.1 2.1 謂詞公式符號(hào)化（關(guān)于論域）謂詞公式符號(hào)化（關(guān)于論域）再例如：有些大學(xué)生吸煙有些大學(xué)生吸煙。如果論域是大學(xué)生集合 S，令 A(x)A(

26、x)：x x吸煙吸煙，命題的符號(hào)表達(dá)式為 xA(x)xA(x)。如果論域擴(kuò)大為全總個(gè)體域時(shí)，上述表達(dá)式xA(x)表示“有些客體吸煙”，就不是表示此命題了，故需要添加謂詞 S(x)S(x)：x x是大學(xué)生是大學(xué)生，用于表明x的特性，命題的符號(hào)表達(dá)式為： x(S(x)A(x)x(S(x)A(x)2.1 2.1 謂詞公式符號(hào)化（關(guān)于論域）謂詞公式符號(hào)化（關(guān)于論域）可見命題的符號(hào)表達(dá)式與論域有關(guān)。當(dāng)論域擴(kuò)大時(shí)，需要添加用來表示客體特性的謂詞，稱此謂詞為特性謂詞特性謂詞。特性謂詞往往就是給定命題中量詞后邊的那個(gè)名詞。如上面兩個(gè)例子中的“所有自然數(shù)自然數(shù)”、“有些大學(xué)生大學(xué)生”。如果如果前邊是全稱量詞，特

27、性謂詞后邊是蘊(yùn)含聯(lián)結(jié)詞“”；如果如果前邊是存在量詞，特性謂詞后邊是合取聯(lián)結(jié)詞“”。2.2 2.2 謂詞公式和符號(hào)化（例題謂詞公式和符號(hào)化（例題B B）1. .所有大學(xué)生都喜歡一些歌星。所有大學(xué)生都喜歡一些歌星。令令S(x)S(x)：x x是大學(xué)生，是大學(xué)生，X(x)X(x)：x x是歌星，是歌星，L(x,y)L(x,y)：x x喜歡喜歡y y。 表達(dá)式為：表達(dá)式為： x(S(x)x(S(x) y(X(y)L(x,y) y(X(y)L(x,y) 2.2.沒有不犯錯(cuò)誤的人。沒有不犯錯(cuò)誤的人。此話就是此話就是“ “沒有人不犯錯(cuò)沒有人不犯錯(cuò)誤誤” ”，“ “沒有沒有” ”就是就是“ “不存在不存在”

28、”之意。之意。令令P(x)P(x)：x x是人，是人，F(xiàn)(x)F(x)：x x犯錯(cuò)誤，表達(dá)式為：犯錯(cuò)誤，表達(dá)式為： x(P(x)x(P(x)F(x) F(x) 或者或者 x(P(x)F(x)x(P(x)F(x)2.2 2.2 謂詞公式和符號(hào)化（例題謂詞公式和符號(hào)化（例題B B）3.3.如果一個(gè)人只是說謊話，那么他所說的每句如果一個(gè)人只是說謊話，那么他所說的每句話沒有一句是可以相信的。話沒有一句是可以相信的。 令令A(yù)(x)A(x)：x x是人，是人，B(x,y)B(x,y)：y y是是x x說的話，說的話， C(x):x C(x):x是謊話，是謊話，D(x)D(x)：x x是可以相信的是可以相信

29、的 命題的表達(dá)式為命題的表達(dá)式為: : x(A(x)(x(A(x)( y(B(x,y)C(y)y(B(x,y)C(y) z(B(x,z)D(z)z(B(x,z)D(z)2.3 2.3 等價(jià)式與前束范式（引）等價(jià)式與前束范式（引）在命題邏輯中，是通過對(duì)公式的命題變?cè)x值公式的命題變?cè)x值來討論永真式、永真蘊(yùn)含式及等價(jià)公式的。在謂詞演算中，也要討論一些重要的謂詞公式。但是由于謂詞公式中可能有 命題變?cè)?、個(gè)體變命題變?cè)?、個(gè)體變項(xiàng)項(xiàng)。對(duì)命題變?cè)x值比較容易，因?yàn)橹挥袃蓚€(gè)值可賦。而對(duì)個(gè)體變項(xiàng)作指派卻不那么簡單，因?yàn)檎撚蛑械膫€(gè)體可能有無限個(gè)。另外謂詞公式的真值還與論域有關(guān)。2.3 2.3 等價(jià)式（定義等價(jià)

30、式（定義1 1）定義：定義：若將給定的謂詞公式中的命題變?cè)么_定的命題代替，對(duì)公式中的 個(gè)體變項(xiàng)個(gè)體變項(xiàng) 用論域中的 個(gè)體個(gè)體 代替，這個(gè)過程就稱之為對(duì)謂詞公式作指派，或者稱之為對(duì)謂詞公式賦值謂詞公式賦值。定義：定義：給定謂詞公式 A，E 是其論域，如果不論對(duì)公式公式 A A 作任何賦值作任何賦值，都使得 A 的真值為真，則稱公式 A 在論域 E上 是永真式。2.3 2.3 等價(jià)式（定義等價(jià)式（定義2 2）定義：定義：給定謂詞公式 A、B，E是它們的論域，如果不論對(duì)公式A、B作任何賦值，都使得 A 與B 的真值相同 (或者說AB是永真式)，則稱公式 A 與 B 在論域 E上是等值的。記作AB

31、。例：例：I(x)：x是整數(shù)，N(x)：x是自然數(shù)，設(shè)論域E是自然數(shù)集合，公式 I(x) 與 N(x) 在E上是等值的。而公式 N(x)I(x) N(x)I(x) 與 N(x)I(x) N(x)I(x) 就是與論域無關(guān)的等值的公式，即即 N(x)I(x) N(x)I(x) N(x)I(x)N(x)I(x)。2.3 2.3 等價(jià)式（公式等價(jià)式（公式0 0）公式公式 0 0 ：可把公式看成一個(gè)命題變?cè)Ｔ诿}演算的永真式中，將同一個(gè)命題變?cè)?，用同一個(gè)謂詞公式代替，所得到也是永真式。即可將命題演算的等價(jià)公式推廣到謂詞演算中使用。例如：例如： x(A(x)B(x)x(A(x)B(x)x(A(x)B(x

32、)x(A(x)B(x)PQ PQ P PQ Q( xA(x)xA(x) xB(x)xB(x)xA(x)xA(x) xB(x)xB(x) 摩根定律摩根定律2.3 2.3 等價(jià)式（公式等價(jià)式（公式1 1）公式公式 1 1 ：一般地，設(shè)論域?yàn)閍1,a2,.,an，則 1. xA(x) A(a1)A(a2).A(an) 2. xB(x) B(a1)B(a2).B(an)有限個(gè)體域中量詞消去等值式有限個(gè)體域中量詞消去等值式例如：令例如：令A(yù)(x)A(x)：x x是整數(shù)，論域是是整數(shù)，論域是1,2,3,4,51,2,3,4,5，謂詞公式謂詞公式 xA(x) xA(x) 表示論域內(nèi)所有的客體都是整表示論域內(nèi)

33、所有的客體都是整數(shù)，顯然公式數(shù)，顯然公式 xA(x)xA(x)真值為真，因?yàn)檎嬷禐檎?，因?yàn)锳(1)A(1)、A(2)A(2)、A(3)A(3)、A(4)A(4)、A(5)A(5)都為真，于是有：都為真，于是有： xA(x)xA(x) A(1)A(2)A(3)A(4)A(5)A(1)A(2)A(3)A(4)A(5)2.3 2.3 等價(jià)式（公式等價(jià)式（公式2 2）公式公式 2 2 ：1. 1. xA(x)xA(x) x x A(x)A(x)2. 2. xA(x)xA(x) x x A(x)A(x)量詞否定等值式量詞否定等值式證明：證明：設(shè)論域?yàn)樵O(shè)論域?yàn)閍a1 1,a,a2 2,.,a,.,an n

34、 ，則，則 xA(x)xA(x) (A(a(A(a1 1)A(a)A(a2 2).A(a).A(an n) A(aA(a1 1) A(aA(a2 2).). A(aA(an n) )x x A(x)A(x) 類似可以證明另一個(gè)公式。類似可以證明另一個(gè)公式。2.3 2.3 等價(jià)式（公式等價(jià)式（公式3 3）公式公式 3 3 ：如果是個(gè)不含客體變?cè)绻莻€(gè)不含客體變?cè)獂 x的謂詞公式，的謂詞公式，且不在且不在 x x 和和 x x 的轄域內(nèi)，可以將放入的轄域內(nèi)，可以將放入 x x和和 x x 的轄域內(nèi)。即得如下公式：的轄域內(nèi)。即得如下公式：量詞轄域收縮擴(kuò)展等值式量詞轄域收縮擴(kuò)展等值式 1.1. xA

35、(x)BxA(x)Bx(A(x)B)x(A(x)B) 2.2. xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 3.3. xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 4.4. xA(x)BxA(x)Bx(x(x)B) (x)B) 2.3 2.3 等價(jià)式（公式等價(jià)式（公式4 4）公式公式 4 4 ： x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xB(x)xB(x) x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xB(x)xB(x)量詞分配等值式量詞分配等值式證明證明：設(shè)論域?yàn)椋涸O(shè)論域?yàn)閍a1 1,a,a2 2,.,a,.,an n ， x

36、(A(x)B(x)x(A(x)B(x)(A(a(A(a1 1)B(a)B(a1 1)(A(a)(A(a2 2)B)B(a(a2 2) (A(a(A(an n)B(a)B(an n)(A(a(A(a1 1)A(a)A(a2 2).A(a).A(an n) ) (B(a(B(a1 1)B(a)B(a2 2).B(a).B(an n)xA(x)xA(x) xB(x)xB(x)2.3 2.3 等價(jià)式（公式等價(jià)式（公式5 5）公式公式 5 5 ：在：在 A(x,y) A(x,y) 前有兩個(gè)量詞，如果兩個(gè)量詞是前有兩個(gè)量詞，如果兩個(gè)量詞是相同的，它們的次序是無關(guān)緊要，但是如果是不相同的，它們的次序是無關(guān)緊

37、要，但是如果是不同的，它們的次序就不可以隨便交換。同的，它們的次序就不可以隨便交換。多量詞等值式多量詞等值式例如例如：設(shè)：設(shè)A(x,y)A(x,y)表示表示“ “x+y=0 x+y=0” ”, ,論域：實(shí)數(shù)集合，論域：實(shí)數(shù)集合， x x yA(x,y)yA(x,y)表示表示“ “對(duì)于任意給定的一個(gè)實(shí)數(shù)對(duì)于任意給定的一個(gè)實(shí)數(shù)x,x,可可以找到一個(gè)以找到一個(gè)y,y,使得使得x+y=0 x+y=0” ”, ,這是一個(gè)為這是一個(gè)為“ “真真” ”的命題。的命題。而交換量詞后而交換量詞后 y y xA(x,y)xA(x,y) 表示表示“ “存在一個(gè)實(shí)數(shù)存在一個(gè)實(shí)數(shù)y,y,與任意給定的與任意給定的一個(gè)實(shí)數(shù)

38、一個(gè)實(shí)數(shù)x x之和都等于之和都等于0 0” ”, ,這是一個(gè)為這是一個(gè)為“ “假假” ”的命題。的命題。2.4 2.4 謂詞演算推理謂詞演算推理推理方法：推理方法： 直接推理、條件論證、反證法直接推理、條件論證、反證法所用公式：第所用公式：第1 1、2 2章的等值式和重言蘊(yùn)含式章的等值式和重言蘊(yùn)含式規(guī)則規(guī)則P P：代表引入前提代表引入前提 規(guī)則規(guī)則T T：代表得到結(jié)論代表得到結(jié)論四個(gè)規(guī)則新規(guī)則（四個(gè)規(guī)則新規(guī)則（USUS、ESES、EGEG、UGUG）：）：處理量處理量詞時(shí)，如推理要使用不含量詞的命題公式，應(yīng)詞時(shí)，如推理要使用不含量詞的命題公式，應(yīng)去掉量詞，如結(jié)論有量詞，還要添加量詞。去掉量詞，

39、如結(jié)論有量詞，還要添加量詞。2.4 2.4 謂詞演算推理（規(guī)則謂詞演算推理（規(guī)則 US US ）全稱指定規(guī)則全稱指定規(guī)則 US (Universal Specialization) US (Universal Specialization) 形式：形式： xA(x)xA(x)A(c)A(c) ( (其中其中c c是論域內(nèi)指定客體是論域內(nèi)指定客體) ) 含義：如果含義：如果 xA(x)xA(x)為真，則在論域內(nèi)為真，則在論域內(nèi)任何指任何指定定客體客體c c，都使得，都使得A(c)A(c)為真。為真。 作用：去掉全稱量詞。作用：去掉全稱量詞。 要求：要求：c c不是不是A(x)A(x)中的符號(hào)。中

40、的符號(hào)。2.4 2.4 謂詞演算推理（規(guī)則謂詞演算推理（規(guī)則 ES ES ）存在指定規(guī)則存在指定規(guī)則 ES (Existential Specialization) ES (Existential Specialization) 形式：形式： xA(x)xA(x)A(c)A(c) ( (其中其中c c是論域內(nèi)指定客體是論域內(nèi)指定客體) ) 含義：如果含義：如果 xA(x)xA(x)為真，則論域內(nèi)為真，則論域內(nèi)指定指定客體客體c c， 都使得都使得A(c)A(c)為真。為真。 作用：去掉存在量詞。作用：去掉存在量詞。 要求：要求： c c不是不是A(x)A(x)中的符號(hào)。中的符號(hào)。 用用ESES

41、指定的指定的客體客體c c不應(yīng)該是不應(yīng)該是在此之前在此之前用用USUS規(guī)則或者用規(guī)則或者用ESES規(guī)則所規(guī)則所指定的客體指定的客體c(c(即本次用即本次用ESES特指客體特指客體c c，不應(yīng)該是以，不應(yīng)該是以前特指的客體前特指的客體) )。2.4 2.4 謂詞演算推理（規(guī)則謂詞演算推理（規(guī)則 UGUG ）全稱推廣規(guī)則全稱推廣規(guī)則 UG (Universal Generalization) UG (Universal Generalization) 形式：形式： A(c)A(c)xA(x)xA(x) ( (其中其中c c是論域內(nèi)是論域內(nèi)任何任何指定客體指定客體) ) 含義：如果含義：如果在論域內(nèi)

42、在論域內(nèi)任何指定任何指定客體客體c c都都使使 得得A(c)A(c)為真，則為真，則 xA(x)xA(x)為真。為真。 作用：添加作用：添加全稱全稱量詞。量詞。 要求：要求：x x不是不是A(c)A(c)中的符號(hào)。中的符號(hào)。 c c一定是任意一定是任意的客體，否則不可的客體，否則不可全全 稱推廣稱推廣。2.4 2.4 謂詞演算推理（規(guī)則謂詞演算推理（規(guī)則 EGEG ）存在推廣規(guī)則存在推廣規(guī)則 EG (Existential Generalization) EG (Existential Generalization) 形式：形式： A(c)A(c)xA(x)xA(x) ( (其中其中c c是論

43、域內(nèi)指定客體是論域內(nèi)指定客體) ) 含義：如果含義：如果在論域內(nèi)在論域內(nèi)指定指定客體客體c c使得使得 A(c) A(c)為真，則為真，則 xA(x)xA(x)為真。為真。 作用：添加存在量詞。作用：添加存在量詞。 要求：要求：x x不是不是A(c)A(c)中的符號(hào)中的符號(hào)。2.4 2.4 謂詞演算推理（例題謂詞演算推理（例題 A A ）例例A. A. 所有金屬都導(dǎo)電。銅是金屬。所有金屬都導(dǎo)電。銅是金屬。 故銅導(dǎo)電。故銅導(dǎo)電。令令 M(x):x M(x):x是金屬。是金屬。C(x):xC(x):x導(dǎo)電。導(dǎo)電。a:a:銅。銅。符號(hào)化為：符號(hào)化為： x(M(x)C(x),M(a)x(M(x)C(x

44、),M(a)C(a)C(a) x(M(x)C(x)x(M(x)C(x)P P M(a)C(a) US M(a)C(a) US M(a) P M(a) P C(a) T C(a) T 2.4 2.4 謂詞演算推理（例題謂詞演算推理（例題 B B ）例例B. B. 所有自然數(shù)都是整數(shù)。有些數(shù)是自然數(shù)。所有自然數(shù)都是整數(shù)。有些數(shù)是自然數(shù)。因此有些數(shù)是整數(shù)。因此有些數(shù)是整數(shù)。令令A(yù)(x)A(x)表示表示x x是自然數(shù)，是自然數(shù)，B(x)B(x)表示表示x x是整數(shù)。是整數(shù)。 x(A(x)B(x)x(A(x)B(x)， xA(x) xA(x) xB(x)xB(x) xA(x) PxA(x) P A(c)

45、 ES A(c) ES x(A(x)B(x) Px(A(x)B(x) P A(c)B(c) US A(c)B(c) US B(c) T B(c) T xB(x) EG xB(x) EG 2.4 2.4 謂詞演算推理（例題謂詞演算推理（例題 B B 錯(cuò)誤解）錯(cuò)誤解）例例B B如果按下面方法推理，是否正確？如果按下面方法推理，是否正確？ x(A(x)B(x)x(A(x)B(x)， xA(x) xA(x) xB(x)xB(x) x(A(x)B(x) Px(A(x)B(x) P A(c)A(c)B(c) US B(c) US xA(x) PxA(x) P A(c)A(c) ES ES B(c) T B

46、(c) T xB(x) EG xB(x) EG 2.4 2.4 謂詞演算推理（注意事項(xiàng)）謂詞演算推理（注意事項(xiàng)）1 1. .注意使用注意使用ESES、USUS、EGEG、UGUG的限制條件。的限制條件。2 2. .對(duì)于同一個(gè)客體變?cè)?，既有帶?duì)于同一個(gè)客體變?cè)?，既有?也有帶也有帶 的前的前提，去量詞時(shí)，應(yīng)先去提，去量詞時(shí)，應(yīng)先去 后去后去 ，這樣，這樣才可以特才可以特指同一個(gè)客體指同一個(gè)客體 c. c.3. 3.去量詞時(shí)去量詞時(shí)，該量詞必須是公式的最左邊的量，該量詞必須是公式的最左邊的量詞，且此量詞的前邊詞，且此量詞的前邊無任何符號(hào)無任何符號(hào)，它的轄域作，它的轄域作用到公式末尾。用到公式末尾。

47、2.4 2.4 謂詞演算推理（注意事項(xiàng)例）謂詞演算推理（注意事項(xiàng)例）錯(cuò)誤的：錯(cuò)誤的： x xP(x)P(x) yQ(y) yQ(y) P P x xP(x)Q(b) P(x)Q(b) ES ESP(a)Q(b)P(a)Q(b) US US錯(cuò)誤的：錯(cuò)誤的： x xP(x)P(x) yQ(y)yQ(y) P PxP(x)xP(x) yQ(y) yQ(y) T T x x P(x)P(x) yQ(y) yQ(y) T T x x y(y( P(x)P(x)Q(y) Q(y) T T y(y( P(a)P(a)Q(y) Q(y) ESES P(a)P(a)Q(b)Q(b)ESES P(a) P(a)Q

48、(b) Q(b) T T2.4 2.4 謂詞演算推理（注意事項(xiàng)）謂詞演算推理（注意事項(xiàng)）下面的作法是錯(cuò)誤的：下面的作法是錯(cuò)誤的： 正確作法是：正確作法是： x xP(x) P P(x) P x xP(x) P P(x) P P(c) USP(c) US x x P(x) T(1) P(x) T(1) P(c) ES (2)P(c) ES (2)另：另：令令P(x,y):yP(x,y):y是是x x的的生母，生母， 是假命題是假命題. . x x y yP(x,y) P P(x,y) P x x y yP(x,y) PP(x,y) P x xP(x,c) ESP(x,c) ES y yP(a,y

49、) US P(a,y) US 2.4 2.4 謂詞演算推理（注意事項(xiàng)）謂詞演算推理（注意事項(xiàng)）4. 4. 添加量詞時(shí)添加量詞時(shí)，也要加在公式的最左邊，也要加在公式的最左邊，( (即新即新加的量詞前也無任何符號(hào)加的量詞前也無任何符號(hào)！) )且其轄域作用到且其轄域作用到公式的末尾。公式的末尾。 P(a)P(a)Q(b) Q(b) x xP(x)P(x)Q(b) UG Q(b) UG x xP(x)P(x) y yQ(y) EG Q(y) EG x(x(P(x)P(x)Q(b) UG Q(b) UG y y x x(P(x)(P(x)Q(y) EG Q(y) EG 2.4 2.4 謂詞演算推理（課堂

50、練習(xí)謂詞演算推理（課堂練習(xí) A A）證明下面推理的有效性：證明下面推理的有效性：“ “鳥都會(huì)飛。猴子都不鳥都會(huì)飛。猴子都不會(huì)飛。所以，猴子都不是鳥。會(huì)飛。所以，猴子都不是鳥。” ”設(shè)設(shè) B(x):x B(x):x是鳥；是鳥；F(x):xF(x):x會(huì)飛；會(huì)飛；M(x):xM(x):x是猴子。是猴子。即證明：即證明： x(B(x)F(x),x(B(x)F(x), x(M(x)x(M(x) F(x)F(x)x(M(x)x(M(x) B(x)B(x) 2.4 2.4 謂詞演算推理（課堂練習(xí)謂詞演算推理（課堂練習(xí) A A）證明：證明： x(B(x)F(x),x(B(x)F(x), x(M(x)x(M(

51、x) F(x)F(x)x(M(x)x(M(x) B(x)B(x) 證明：證明： x(B(x)F(x) x(B(x)F(x) B(a)F(a) B(a)F(a) x(M(x)x(M(x) F(x) F(x) M(a) M(a) F(a) F(a) F(a)F(a) B(a) B(a) M(a) M(a) B(a) B(a) x(M(x)x(M(x) B(x)B(x) 2.4 2.4 謂詞演算推理（課堂練習(xí)謂詞演算推理（課堂練習(xí) B B ）不認(rèn)識(shí)錯(cuò)誤的人，也不能改正錯(cuò)誤。有些誠實(shí)不認(rèn)識(shí)錯(cuò)誤的人，也不能改正錯(cuò)誤。有些誠實(shí)的人改正了錯(cuò)誤。所以有些誠實(shí)的人是認(rèn)識(shí)了的人改正了錯(cuò)誤。所以有些誠實(shí)的人是認(rèn)識(shí)了

52、錯(cuò)誤的人。錯(cuò)誤的人。設(shè)設(shè)A(x):xA(x):x是認(rèn)識(shí)錯(cuò)誤的人。是認(rèn)識(shí)錯(cuò)誤的人。 B(x):x B(x):x改正了錯(cuò)誤。改正了錯(cuò)誤。C(x):xC(x):x是誠實(shí)的人。是誠實(shí)的人。即證明：即證明： x(x( A(x)A(x) B(x)B(x)， x(C(x)B(x) x(C(x)B(x) x(C(x)A(x)x(C(x)A(x)2.4 2.4 謂詞演算推理（課堂練習(xí)謂詞演算推理（課堂練習(xí) B B）證明：證明： x(x( A(x)A(x) B(x)B(x)， x(C(x)B(x),x(C(x)B(x), x(C(x)A(x)x(C(x)A(x) x(C(x)B(x) x(C(x)B(x) C(c

53、)B(c) C(c)B(c) C(c) C(c) B(c) B(c) x(x( A(x)A(x) B(x) B(x) A(c)A(c) B(c) B(c) A(c) A(c) A(c) A(c) C(c)A(c) C(c)A(c) x(C(x)A(x) x(C(x)A(x) 2.4 2.4 謂詞演算推理（課堂練習(xí)謂詞演算推理（課堂練習(xí) B B）證明：證明： x(x( A(x)A(x) B(x)B(x)， x(C(x)B(x),x(C(x)B(x), x(C(x)A(x)x(C(x)A(x) x(C(x)B(x) x(C(x)B(x) P P C(c)B(c) C(c)B(c) ESES C(c

54、) C(c) T T B(c) B(c) T T x(x( A(x)A(x) B(x) B(x) P P A(c)A(c) B(c) B(c) USUS A(c) A(c) T T ，假言易位，假言易位 A(c) A(c) T T C(c)A(c) C(c)A(c) T T x(C(x)A(x) x(C(x)A(x) EG EG 2.4 2.4 謂詞演算推理（課堂練習(xí)謂詞演算推理（課堂練習(xí) C C）一些病人喜歡所有醫(yī)生。任何病人都不喜歡一些病人喜歡所有醫(yī)生。任何病人都不喜歡庸醫(yī)。所以沒有醫(yī)生是庸醫(yī)。庸醫(yī)。所以沒有醫(yī)生是庸醫(yī)。設(shè)設(shè): P(x):x: P(x):x是病人是病人, D(x):x, D

55、(x):x是醫(yī)生是醫(yī)生, , Q(x):x Q(x):x是庸醫(yī)是庸醫(yī), L(x,y): x, L(x,y): x喜歡喜歡y. y.即證明：即證明： x(P(x)x(P(x) y y(D(y)L(x,y)(D(y)L(x,y)， x(P(x)x(P(x) y(y(Q(y)Q(y) L(x,y) L(x,y) y(D(y)Q(y)y(D(y)Q(y)2.4 2.4 謂詞演算推理（課堂練習(xí)謂詞演算推理（課堂練習(xí) C C） x(P(x)x(P(x) y y(D(y)L(x,y)(D(y)L(x,y)， x(P(x)x(P(x) y(y(Q(y)Q(y) L(x,y) L(x,y) y(D(y)Q(y)

56、y(D(y)Q(y) x(P(x)x(P(x) y y(D(y)L(x,y) (D(y)L(x,y) P(a) P(a) y y(D(y)L(a,y) (D(y)L(a,y) P(a) P(a) y y(D(y)L(a,y) (D(y)L(a,y) x(P(x)x(P(x) y(y(Q(y)Q(y) L(x,y) L(x,y) P(a) P(a) y(y(Q(y)Q(y) L(a,yL(a,y2.4 2.4 謂詞演算推理（課堂練習(xí)謂詞演算推理（課堂練習(xí) C C） x(P(x)x(P(x) y y(D(y)L(x,y)(D(y)L(x,y)， x(P(x)x(P(x) y(y(Q(y)Q(y)

57、L(x,y) L(x,y) y(D(y)Q(y)y(D(y)Q(y) y(y(Q(y)Q(y) L(a,y) L(a,y) D(b)L(a,b) D(b)L(a,b) Q(b) Q(b) L(a,b) L(a,b) L(a,b) L(a,b) Q(b) Q(b) D(b) D(b) Q(b) Q(b) D(b)D(b) Q(b) Q(b) ( (D(b)Q(b) D(b)Q(b) y y ( (D(y)Q(y) D(y)Q(y) y y( (D(y)Q(y) D(y)Q(y) 第2部分 集合論第3章 集合第4章 關(guān)系第 3 章 集合以“集合”基本概念為基礎(chǔ)，討論： 1、集合相關(guān)概念 2、集合相

58、關(guān)運(yùn)算、定律 3、冪集、笛卡爾積等概念性質(zhì)3.1 3.1 集合概述（概念）集合概述（概念）集合集合定義：定義：是由確定的對(duì)象（客體）構(gòu)成的集體。用大寫的英文字母表示。這里所謂“確定”是指：論域內(nèi)任何客體，要么屬于這個(gè)集合，要么不屬于這個(gè)集合，是唯一確定的。元素元素定義：定義：集合中的對(duì)象，稱之為元素。 定義：定義：表示元素與集合的屬于關(guān)系。例如：N表示自然數(shù)集合，2N，而4.5不屬于N寫成 (4.5N)，或?qū)懗?4.5 N。3.1 3.1 集合概述（概念）集合概述（概念）這里對(duì)有限集合與無限集合只給出樸素的定義，以后再給出嚴(yán)格的形式定義。有限集合有限集合定義：定義：元素是有限個(gè)的集合。 如果A

59、是有限集合，用 |A|表示A中元素個(gè)數(shù)。例如，A=1,2,3，則 |A|=3。無限集合無限集合定義：定義：元素是無限個(gè)的集合。元素是無限個(gè)的集合。對(duì)無限集合的大小的討論，后續(xù)再進(jìn)行。3.1 3.1 集合概述（表示方法）集合概述（表示方法）列舉法：列舉法：將集合中的元素一一列出，寫在大括號(hào)內(nèi)。例如，N=1,2,3,4, A=a,b,c,d描述法：描述法：用句子(或謂詞公式或謂詞公式)描述元素的屬性。例如，B=x| x是偶數(shù) C=x|x是實(shí)數(shù)且2x5一般地，A=x|P(x)，其中，P(x)是描述元素 x 的特性的謂詞公式，如果論域內(nèi)客體 a 使得P(a)為真，則aA，否則 aA。3.1 3.1 集

60、合概述（表示方法）集合概述（表示方法） 集合中元素間次序無關(guān)緊要，但必須是可區(qū)集合中元素間次序無關(guān)緊要，但必須是可區(qū)分的。如分的。如A=a,b,c,aA=a,b,c,a，B=c,b,a,B=c,b,a,，A A等同等同B B。 對(duì)集合中的元素?zé)o任何限制，例如令對(duì)集合中的元素?zé)o任何限制，例如令 A= A=人，石頭，人，石頭，1 1，, B=, B=, 集合中的元素也可以是集合，例如：集合中的元素也可以是集合，例如：a a：王書記：王書記 a a：團(tuán)支部：團(tuán)支部( (只有一個(gè)書記只有一個(gè)書記) ) a a：分團(tuán)委：分團(tuán)委( (只有一個(gè)團(tuán)支部只有一個(gè)團(tuán)支部) ) a a：團(tuán)委：團(tuán)委 ( (只有一個(gè)分