全套電子課件：離散數(shù)學(xué)導(dǎo)論

1、 離 散 數(shù) 學(xué) 導(dǎo) 論離散數(shù)學(xué)是研究離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)模型的數(shù)學(xué)分支的統(tǒng)稱。是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心基礎(chǔ)課程。 計(jì)算機(jī)求解問題的基本模式: 實(shí)際問題 數(shù)學(xué)建模 算法設(shè)計(jì) 編程實(shí)現(xiàn) 前 言第一章 命題演算及其 形式系統(tǒng)第二章 謂詞演算及其 形式系統(tǒng)*第三章 消 解 原 理第五章 關(guān) 系 第六章 函 數(shù) 第七章 基 數(shù)第八章 圖 第九章 特 殊 圖 第十章 代數(shù)結(jié)構(gòu)通論第十一章 群、環(huán)、域第十二章 格與布爾代數(shù)離散數(shù)學(xué)導(dǎo)論第一篇 數(shù)理邏輯第二篇 集合論 第四章 集合及其運(yùn)算第三篇 圖 論第四篇 抽象代數(shù) 第 一 篇 數(shù) 理 邏 輯數(shù)理邏輯（mathematical logic）是用數(shù)

2、學(xué)的方法來研究人類推理過程的一門數(shù)學(xué)學(xué)科。 又稱符號邏輯、現(xiàn)代邏輯。 其顯著特征是符號化和形式化，即把邏輯所涉及的“概念、判斷、推理”用符號來表示，用公理體系來刻劃, 并基于符號串形式的演算來描述推理過程的一般規(guī)律。 邏輯演算四個分支：公理集合論、證明論、模型論和遞歸論。 第 一 章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.2 重 言 式1.3 范式* 1.4 命題演算形式系統(tǒng)第一章 命題演算及其形式系統(tǒng) 1.1.1 命題1.1.2 聯(lián)結(jié)詞1.1.3 命題公式及其真值表1.1.4 語句的形式化 第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.2.1 重言式概念1.2.2 邏輯等價式

3、和邏輯蘊(yùn)涵式1.2.3 對偶原理第一章 命題演算及其形式系統(tǒng)1.2 重 言 式1.3.1 析取范式和合取范式1.3.2 主析取范式與主合取范式1.3.3 聯(lián)結(jié)詞的擴(kuò)充與歸約第一章 命題演算及其形式系統(tǒng)1.3 范式1.4.1 證明、演繹和推理1.4.2 命題演算形式系統(tǒng)PC1.4.3 自然推理系統(tǒng)ND 第一章 命題演算及其形式系統(tǒng)* 1.4 命題演算形式系統(tǒng)第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞 1.1.1 命題 我們把對確定的對象作出判斷的陳述句稱作命題（propositions or statements） 當(dāng)判斷正確或符合客觀實(shí)際時， 稱該命題真（true）， 否則稱該命題假（

4、false）。 第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞 1.1.1 命題 通常把不含有邏輯聯(lián)結(jié)詞的命題稱為原子命題或原子（atoms） 把由原子命題和邏輯聯(lián)結(jié)詞共同組成的命題稱為復(fù)合命題（compositive propositions or compound statements）第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.2 聯(lián)結(jié)詞否定詞“并非”合取詞“并且”析取詞“或” 蘊(yùn)涵詞“如果，那么” 雙向蘊(yùn)涵詞“當(dāng)且僅當(dāng)”第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.2 聯(lián)結(jié)詞 否定詞（negation ）“并非”（not ），用符號“ ”表示。 p p 0

5、 1 1 0可用表1.1來規(guī)定否定詞“”的意義: p讀作“并非p”或“非p”。第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.2 聯(lián)結(jié)詞 合取詞（ conjunction ）“并且”（and ），用符號“”表示。 可用表1.2來規(guī)定合取詞“”的意義： p q p q 0 0 1 1 0 1 0 1 0 0 0 1pq讀作“p并且q”或“p且q” 第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.2 聯(lián)結(jié)詞 析取詞（disjunction）“或”（or ） 用符號“ ”表示。 可用表1.3來規(guī)定析取詞“”的意義：pq讀作“p或者q”、“p或q”。 p q p q 0 0 1 1

6、 0 1 0 1 0 1 1 1第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.2 聯(lián)結(jié)詞 蘊(yùn)涵詞（implication)“如果，那么”（ifthen），用符號“ ”表示。 可用表1.5來規(guī)定該蘊(yùn)涵詞“ ”的意義： p q p q 0 0 1 1 0 1 0 1 1 1 0 1pq中的p稱為蘊(yùn)涵前件，q稱為蘊(yùn)涵后件。 第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.2 聯(lián)結(jié)詞 雙向蘊(yùn)涵詞(two-way-implication)“當(dāng)且僅當(dāng)”（if and only if），用符號“ ”表示。 可用表1.6來規(guī)定該雙向蘊(yùn)涵詞“ ”的意義： p q p q 0 0 1 1 0

7、 1 0 1 1 0 0 1pq讀作“p雙向蘊(yùn)涵q”，“p當(dāng)且僅當(dāng)q”，“p等價于q”。 第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.3 命題公式及其真值表命題常元 命題公式 指派 弄真與弄假真值表（truth table） 命題變元第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.3 命題公式及其真值表 我們把表示具體命題及表示常命題的p，q，r，s等與f，t統(tǒng)稱為命題常元（proposition constants）。 命題變元（proposition variable）是以“真、假”或“1，0”為取值范圍的變元，它未指出符號所表示的具體命題 。第一章 命題演算及其形

8、式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.3 命題公式及其真值表 以下三條款規(guī)定了命題公式（proposition formula） 的意義： （1）命題常元和命題變元是命題公式，也稱為原子公式或原子。（2）如果A，B是命題公式，那么（A），（AB）， （AB），（AB），（AB）也是命題公式。（3）只有有限步引用條款（1），（2）所組成的符號串 是命題公式。定義1.1第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.3 命題公式及其真值表 對任意給定的命題變元p1,pn的一種取值狀況，稱為指派或賦值（assignments） ，用字母，等表示 當(dāng)A對取值狀況 為真時，稱指派弄真A或是A的成

9、真賦值，記為(A) = 1；反之稱指派弄假A或是A的成假賦值，記為 (A) = 0。 第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.3 命題公式及其真值表 對一切可能的指派,公式A的取值可能用下表來描述，這個表稱為真指表（truth table） p q r qr p(qr)(p(qr) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 11111000100001110第一章 命題演算及其形式系統(tǒng) 1.1 命題與聯(lián)結(jié)詞1.1.4 語句的形式化 語句形式化主要是以下幾個方面： 要準(zhǔn)確確定原子命題，并將其形式化

10、。 要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識別自然語言中的聯(lián)結(jié)詞（有時它們被省略），否定詞的位置要放準(zhǔn)確。 必要時可以進(jìn)行改述，即改變原來的敘述方式，但要保證表達(dá)意思一致。 需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦可不省略。 要注意語句的形式化未必是唯一的。第一章 命題演算及其形式系統(tǒng)1.2 重 言 式1.2.1 重言式概念定義1.2重言式 不可滿足式 可滿足式 第一章 命題演算及其形式系統(tǒng)1.2 重 言 式1.2.1 重言式概念 對命題公式A，如果對A中命題變元的一切指派均弄真A，則A稱為重言式（tautology），又稱永真式. 如果至少有一個指派弄真A，則A稱為可滿足式（s

11、atisfactable formula or contingency）。第一章 命題演算及其形式系統(tǒng)1.2 重 言 式1.2.1 重言式概念 如果對A中命題變元的一切指派均弄假A，則稱A為不可滿足式或矛盾式（contradiction or absurdity）或永假式 。第一章 命題演算及其形式系統(tǒng)1.2 重 言 式1.2.2 邏輯等價式和邏輯蘊(yùn)涵式 當(dāng)命題公式AB為重言式時，稱A邏輯等價于B，記為A B，它又稱為邏輯等價式（logically equivalent or equivalent）。定義1.3當(dāng)命題公式AB為重言式時，稱A邏輯蘊(yùn)涵B，記為A B，它又稱為邏輯蘊(yùn)涵式(logic

12、ally implication)。定義1.4第一章 命題演算及其形式系統(tǒng)1.2 重 言 式1.2.2 邏輯等價式和邏輯蘊(yùn)涵式性質(zhì)： 定理1.1 （1）AB當(dāng)且僅當(dāng) AB （2）A B當(dāng)且僅當(dāng) AB （3）若AB，則BA （4）若AB，BC，則AC （5）若A B，則B A （6）若A B，B C，則A C （7）若A B，AA，BB，則A B第一章 命題演算及其形式系統(tǒng)1.2 重 言 式1.2.2 邏輯等價式和邏輯蘊(yùn)涵式 設(shè)A為永真式，p為A中命題變元，A(B/p)表示將A中p的所有出現(xiàn)全部代換為公式B后所得的命題公式（稱為A的一個代入實(shí)例），那么A(B/p)亦為永真式。定理1.2-代入原理

13、（rule of substitution），簡記為RS第一章 命題演算及其形式系統(tǒng)1.2 重 言 式1.2.2 邏輯等價式和邏輯蘊(yùn)涵式 設(shè)A為一命題公式，C為A的子公式（A的一部分，且自身為一公式）， 且CD。若將A中子公式C的某些（未必全部）出現(xiàn)替換為D后得到公式B， 那么A B。 定理1.3-替換原理（rule of replacement ），簡記為RR第一章 命題演算及其形式系統(tǒng)1.2 重 言 式1.2.3 對偶原理 設(shè)公式A僅含聯(lián)結(jié)詞 ，A*為將A中符號，t，f分別改換為，f，t后所得的公式，那么稱A*為A的對偶（dual）。定義1.5第一章 命題演算及其形式系統(tǒng)1.2 重 言 式

14、1.2.3 對偶原理 定理1.4 設(shè)公式A中僅含命題變元p1,pn，及聯(lián)結(jié)詞，那么 AA*(p1/p1, pn/pn)對偶原理定理1.5設(shè)A，B為僅含聯(lián)結(jié)詞，和命題變元p1,pn的命題公式，且滿足A B，那么有B* A*。進(jìn)而當(dāng)A B時有A* B*。常把B* A*，A* B*稱為A B和A B的對偶式。第一章 命題演算及其形式系統(tǒng)1.3 范式1.3.1 析取范式和合取范式 文字(letters)：指命題常元、變元及它們的否定，前者又稱正文字，后者則稱負(fù)文字。析取子句(disjunctive clauses)：指文字或若干文字的析取。合取子句(conjunctive clauses)：指文字或若

15、干文字的合取?；パa(bǔ)文字對(complemental pairs of letters) ：指形如L，L（L為文字）的一對字符。第一章 命題演算及其形式系統(tǒng)1.3 范式1.3.1 析取范式和合取范式 定義1.6 命題公式A稱為公式A的析取范式（disjunctive normal form），如果 （1）AA （2）A為一合取子句或若干合取子句的析取。定義1.7 命題公式A稱為公式A的合取范式（conjunctive normal form）如果 （1）AA （2）A為一析取子句或若干析取子句的合取。第一章 命題演算及其形式系統(tǒng)1.3 范式1.3.2 主析取范式與主合取范式 定義1.8設(shè)A為恰含

16、命題變元p1,pn的公式。 公式A,稱為A的主析（合）取范式（majordisjunctive（conjunctive）normal form）， 如果A,是A的析（合）取范式，并且其每個 合（析）取子句中p1,pn均恰出現(xiàn)一次。第一章 命題演算及其形式系統(tǒng)1.3 范式1.3.3 聯(lián)結(jié)詞的擴(kuò)充與歸約 定義1.9 稱n元聯(lián)結(jié)詞h是用m 個聯(lián)結(jié)詞g1, g2, gm 可表示的，如果 h(p1, p2,. . ., pn ) A而A中所含聯(lián)結(jié)詞僅取自g1, g2,. . ., gm。第一章 命題演算及其形式系統(tǒng)1.3 范式1.3.3 聯(lián)結(jié)詞的擴(kuò)充與歸約 定義1.10當(dāng)聯(lián)結(jié)詞組g1, g2,. . .

17、, gm可表示所有一元、二元聯(lián)結(jié)詞時，稱其為完備聯(lián)結(jié)詞組（complete group of connectives）。第一章 命題演算及其形式系統(tǒng)* 1.4 命題演算形式系統(tǒng)1.4.1 證明、演繹和推理 定義1.11 公式序列A1, A2, , Am稱為Am的一個證明（proof），如果Ai(1 i m) 或者是公理，或者由Aj1 , Ajk (j1,jki)用推理規(guī)則推得。當(dāng)這樣的證明存在時，稱Am為系統(tǒng)的定理（theorems），記為*Am, ( 為所討論的系統(tǒng)名),或簡記為Am 。第一章 命題演算及其形式系統(tǒng)* 1.4 命題演算形式系統(tǒng)1.4.1 證明、演繹和推理 定義1.12 設(shè)為一

18、公式集合。公式序列A1,A2,Am稱為Am的以為前提的演繹（diduction），如果Ai(1im)或者是 中公式，或者是公理，或者由Aj1,Ajk(j1,jki)用推理規(guī)則導(dǎo)出。當(dāng)有這樣的演繹時，Am稱為 的演繹結(jié)果，記為 *Am, ( 為所討論的系統(tǒng)名)，或簡記為Am。稱 和 的成員為Am的前提(hypothesis)。第一章 命題演算及其形式系統(tǒng)* 1.4 命題演算形式系統(tǒng)1.4.2 命題演算形式系統(tǒng)PC定理1.6 （合理性，sondness）若公式A是系統(tǒng)PC的定理，則A為永真式。若A是公式集 的演繹結(jié)果，那么A是 的邏輯結(jié)果。即 若PC A，則 A .若 PC A，則 A .定理1.

19、7 PC是一致的，即沒有公式A使得PC A與PCA同時成立。第一章 命題演算及其形式系統(tǒng)* 1.4 命題演算形式系統(tǒng)1.4.2 命題演算形式系統(tǒng)PC定理1.8 （完備性，completeness）若公式A永真，則A必為PC的定理；若公式A是公式集 的邏輯結(jié)果，那么A必為 的演繹結(jié)果。即若 A，那么 PC A . 若 A，那么 PC A .第一章 命題演算及其形式系統(tǒng)* 1.4 命題演算形式系統(tǒng)1.4.2 命題演算形式系統(tǒng)PC定理1.9 （演繹定理）對任意公式集 和公式A，B，AB當(dāng)且僅當(dāng) A B（當(dāng) = 時，AB當(dāng)且僅當(dāng)A B，或A B）第一章 命題演算及其形式系統(tǒng)* 1.4 命題演算形式系統(tǒng)

20、1.4.2 命題演算形式系統(tǒng)PC定理1.10 （歸謬定理）對任何公式集 和公式A，B ,若 A B， A B，那么 A 。定理1.11 （窮舉定理）對任何公式集，公式A，B，若A B，A B，則 B。第一章 命題演算及其形式系統(tǒng)* 1.4 命題演算形式系統(tǒng)1.4.3 自然推理系統(tǒng)ND 定理1.12 如果公式A是PC的定理，那么A也必定是ND的定理。 即PC A蘊(yùn)涵ND A。 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.2 謂詞演算永真式2.3 謂詞公式的前束范式 2.4 一階謂詞演算形式系統(tǒng) 第二章 謂詞演算及其形式系統(tǒng) 2.1.1 個體2.1.2 謂詞2.1.3 量詞2.1.4

21、謂詞公式及語句的形式化 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.2.3 兩個原理與兩個規(guī)則2.2.1 謂詞公式的真值規(guī)定 第二章 謂詞演算及其形式系統(tǒng)2.2 謂詞演算永真式 2.4.1 一階謂詞演算形式系統(tǒng)FPC 2.4.2 一階謂詞演算的自然推理系統(tǒng) FND2.4.3 含等詞的一階謂詞演算自然推 理系統(tǒng) 第二章 謂詞演算及其形式系統(tǒng)2.4 一階謂詞演算形式系統(tǒng) 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.1 個體常元 個體 個體域 全總域 變元 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.1 個體 確定的個體常用a，b，c等到小寫字母或字母串表

22、示。a，b，c等稱為常元（constants）。 不確定的個體常用字母x，y，z，u，v，w等來表示。它們被稱為變元（variables）。 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.1 個體 謂詞演算中把一切討論對象都稱為個體，它們可以是客觀世界中的具體客體，也可以是抽象的客體，諸如數(shù)字、符號等。 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.1 個體 謂詞演算中把討論對象個體的全體稱為個體域（domain of individuals），常用字母D表示，并約定任何D都至少含有一個成員。 當(dāng)討論對象遍及一切客體時，個體域特稱為全總域（universe），用字母

23、U表示。 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.2 謂詞謂詞的元數(shù) 謂詞命名式 謂詞填式 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.2 謂詞 通常把謂詞所攜空位的數(shù)目稱為謂詞的元數(shù)。 含空位的寫法有一個明顯的缺點(diǎn)，可讀性差。因此常用變元來代替空位，它們被稱為謂詞命名式，簡稱謂詞。當(dāng)謂詞的空位上填入個體后，便產(chǎn)生一個關(guān)于該個體的語句，這時它被稱為謂詞填式 。 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.3 量詞量詞（quantifiers）指數(shù)量詞“所有”和“有”，分別用符號 （全稱量詞) 和 （存在量詞)來表示。 第二章 謂詞演算及其形式

24、系統(tǒng)2.1 個體、謂詞和量詞2.1.3 量詞約束變元 自由變元 轄域 一階謂詞演算 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.3 量詞 可以取值代入的變元則稱為自由變元（free variables）。 不可以取值代入的變元則稱為約束變元（free variables）。當(dāng)量詞用于一謂詞或復(fù)合的謂詞表達(dá)式式，該謂詞或復(fù)合的謂詞表達(dá)式稱為量詞的轄域（domains of quantifiers） 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.3 量詞 當(dāng)限定量詞的指導(dǎo)變元為個體變元（不用命題變元、謂詞、函數(shù)變元 - 分別以命題、謂詞、函數(shù)為值的變元）時，謂詞演算又

25、稱為一階謂詞演算（first order predicate calculus）。 第二章 謂詞演算及其形式系統(tǒng)2.1 個體、謂詞和量詞2.1.4 謂詞公式及語句的形式化 定義2.1 以下條款規(guī)定的符號串稱為謂詞公式（ predicate forrmula），簡稱公式。 （1）謂詞填式是公式，命題常元是公式 （看作零元謂詞）。 （2）如果A，B是公式，x為任一變元， 那么(A)， (AB)，(xA)，(x A)（當(dāng)使用五個聯(lián)結(jié)詞時 還有(AB)，(AB)，(AB)）都是公式。 （3）只有有限步使用（1），（2）條款 所形成的符號串是公式。 第二章 謂詞演算及其形式系統(tǒng)2.2 謂詞演算永真式2.

26、2.1 謂詞公式的真值規(guī)定 定義2.2給定個體域D及公式A中各謂詞符號的解釋I，如果A中個體變元x1 ,xn分別取值u1 ,un時A真，則稱A在u1 ,un處真；當(dāng)x1 ,xn無論取D中怎樣的個體u1 ,un, A在u1 ,un處均真，則稱A在解釋I下真。 第二章 謂詞演算及其形式系統(tǒng)2.2 謂詞演算永真式2.2.1 謂詞公式的真值規(guī)定 定義2.3給定個體域D，若公式A在每一解釋I下均真，那么稱A在D上永真。若公式A對任何個體域D均有D上永真，則稱A為永真式，或稱A永真（valid）。 定義2.4公式A稱為可滿足的，如果對某一個體域、某一解釋和變元的某一取值狀況，A在此處取值真。公式A不可滿足

27、時也稱A為永假式。 第二章 謂詞演算及其形式系統(tǒng)2.2 謂詞演算永真式2.2.3 兩個原理與兩個規(guī)則 定義2.5設(shè)謂詞公式A中含自由變元x，設(shè)t為一個體項(xiàng)，且t中無自由變元為A中的約束變元，那么稱t是在A中對x可代入的。 第二章 謂詞演算及其形式系統(tǒng)2.2 謂詞演算永真式2.2.3 兩個原理與兩個規(guī)則 定理2.1（代入原理）若A是永真式，那么對A中變元可代入的代入實(shí)例都是永真式。 定理2.2（替換原理）設(shè)A，D為謂詞公式，C為A的子公式， 且CD。若B為將A中子公式C的某些出現(xiàn)（未必全部）替換為D后所得的公式，那么AB。 第二章 謂詞演算及其形式系統(tǒng)2.2 謂詞演算永真式2.2.3 兩個原理與

28、兩個規(guī)則 定義2.6設(shè)A為僅含聯(lián)結(jié)詞 ，的謂詞公式，A*為將A中符號，t，f， , 分別換為，f，t, ， 后所得的公式，那么稱A*為A的對偶式。 第二章 謂詞演算及其形式系統(tǒng)2.2 謂詞演算永真式2.2.3 兩個原理與兩個規(guī)則 定理2.3（改名原理）若公式A中無自由變元y，那么， xA(x) yA(y) , xA(x) yA(y) 第二章 謂詞演算及其形式系統(tǒng)2.3 謂詞公式的前束范式 定義2.7公式A稱為公式A的前束范式（prenex normal forms），如果AA，且A形如 Q1x1QnxnB其中Q1，Qn為量詞 或 ，B中無量詞，且僅含聯(lián)結(jié)詞，B稱為母式。當(dāng)B為合取（析?。┓妒綍r

29、，A稱為A的前束合?。ㄎ鋈。┓妒?。 第二章 謂詞演算及其形式系統(tǒng) 定理2.4 （前束范式定理） 對任意謂詞公式均可作出其前束范式，進(jìn)而作出其前束合取范式或前束析取范式。2.3 謂詞公式的前束范式 第二章 謂詞演算及其形式系統(tǒng)2.4 一階謂詞演算形式系統(tǒng) 2.4.1 一階謂詞演算形式系統(tǒng)FPC 定義2.8設(shè)x1,xn是公式A中的所有自由變元，那么公式x1xnA(或x1xnA(x1,xn)稱為A的全稱封閉式（generalization clusure）。 第二章 謂詞演算及其形式系統(tǒng)2.4 一階謂詞演算形式系統(tǒng) 2.4.1 一階謂詞演算形式系統(tǒng)FPC 定理2.5對任意公式A，變元x，若 A，則

30、x A 。 全稱推廣規(guī)則 定理2.6對任何公式集 ，公式A和變元x，x不是 中任一公式的自由變元，那么，若 A，則 x A。 第二章 謂詞演算及其形式系統(tǒng)2.4 一階謂詞演算形式系統(tǒng) 2.4.1 一階謂詞演算形式系統(tǒng)FPC 定理2.7（存在消除定理） 設(shè)A，B為任意公式，變元x是公式A、但不是公式B的自由變元，那么當(dāng)， x A(x) , A(x) B同時成立時，應(yīng)有 B 。 定理2.6（推廣的存在消除定理） 設(shè) 為一公式集，A，B為任意公式，變元x是A的自由變元，但不是 中任一公式的自由變元那么當(dāng) x A(x) ， A(x) B同時成立時，應(yīng)有 B 。 第二章 謂詞演算及其形式系統(tǒng)2.4 一階

31、謂詞演算形式系統(tǒng)2.4.2 一階謂詞演算的自然推理系統(tǒng)FND-消除規(guī)則 -消除規(guī)則-引入規(guī)則 -引入規(guī)則 第二章 謂詞演算及其形式系統(tǒng)2.4 一階謂詞演算形式系統(tǒng)2.4.3 含等詞的一階謂詞演算自然推理系統(tǒng) 定理2.9對任意項(xiàng)t1，t2，t3，有（ 表示FNDE ）。 （a） t1 = t2 t2 = t1 （b） t1 = t2 t2 = t3 t1 = t3 * 第 三 章 消 解 原 理3.1 斯柯倫標(biāo)準(zhǔn)形3.2 命題演算消解原理3.3 謂詞演算消解原理*第三章 消 解 原 理3.1.1 斯柯倫標(biāo)準(zhǔn)形3.1.2 子句集及其可滿足性*第三章 消 解 原 理3.1 斯柯倫標(biāo)準(zhǔn)形3.3.1 代

32、換及一致化3.3.2 謂詞演算消解原理 *第三章 消 解 原 理3.3 謂詞演算消解原理*第三章 消 解 原 理3.1 斯柯倫標(biāo)準(zhǔn)形3.1.1 斯柯倫標(biāo)準(zhǔn)形對任意只含自由變元x, y1,yn的公式A(x, y1,yn)，xA(x, y1,yn)可滿足，當(dāng)且僅當(dāng)A(f(y1,yn), y1,yn)可滿足。這里f為一新函數(shù)符號；當(dāng)n=0時，f 為新常元。定理3.1 （斯柯倫定理）*第三章 消 解 原 理3.1 斯柯倫標(biāo)準(zhǔn)形3.1.1 斯柯倫標(biāo)準(zhǔn)形 設(shè)公式A的前束范式為B。C是利用 斯柯倫常元和斯柯倫函數(shù)消去B中量詞 （稱斯柯倫化）后所得的合取范式，那么稱 C為A的斯柯倫標(biāo)準(zhǔn)形 （Skolem no

33、rmal form）。定義3.1 *第三章 消 解 原 理3.1 斯柯倫標(biāo)準(zhǔn)形3.1.2 子句集及其可滿足性定義3.2 子句集S稱為可滿足的，如果存在一個個體域和一種解釋，使S中的每一個子句均為真，或使得S中的每一個子句至少有一個文字為真。否則稱S為不可滿足的。*第三章 消 解 原 理3.2 命題演算消解原理 設(shè)C是C1，C2的消解結(jié)果，那么C是C1和C2的邏輯結(jié)果。定理3.2*第三章 消 解 原 理3.2 命題演算消解原理 設(shè)S為一子句集，稱C是S的消解結(jié)果，如果存在一個子句序列C1，C2 ，,Cn（=C），使Ci(i=1,2, ,n)或者是S中子句，或者是Ck，Cj (k,j i)的消解結(jié)

34、果。該序列稱為由S導(dǎo)出的C的消解序列。當(dāng)是S的消解結(jié)果時，稱該序列為S的一個否證（refutation）。定義3.3*第三章 消 解 原 理3.2 命題演算消解原理 如果子句集S有一個否證，那么S是不可滿足的。定理3.3 *第三章 消 解 原 理3.3 謂詞演算消解原理3.3.1 代換及一致化 形如t1/v1, t2/v2, , tn/vn的有窮集合稱為一個代換（substitution），其中v1, vn為任意變元，t1,tn為任意個體項(xiàng)，但tivi(i=1,2, ,n)。當(dāng)代換為一空集合時，稱為空代換。代換用小寫希臘字母表示，空代換記為，“對任意公式或項(xiàng)X作代換”記為X，其意為對X中變元v

35、1,v2, vn分別作代入t1,tn，即 X= X(t1/v1, t2/v2, , tn/vn) 對于空代換有X= X。定義3.4 *第三章 消 解 原 理3.3 謂詞演算消解原理3.3.1 代換及一致化 設(shè)=t1/x1,tn/xn, =s1/y1,sm/ym是兩個代換，與的合成，記為，指如下所得的代換： 從 t1/x1,tn/xn, s1/y1,sm/ym 中刪去 （1）si/yi，當(dāng)yi恰為x1,xn之一 （2）ti/xi，當(dāng)ti=xi。定義3.5 *第三章 消 解 原 理3.3 謂詞演算消解原理3.3.1 代換及一致化 代換 稱為表達(dá)式集合X1 , , Xn的一致化（unifier），如

36、果使 X1 = = Xn 。定義3.6*第三章 消 解 原 理3.3 謂詞演算消解原理3.3.2 謂詞演算消解原理 消解原理 這一過程表示：先對C1，C2作代換，使L1與 L2（或 L1和L2）一致化，然后再消解掉L1和L2，其余文字的析取便是C1，C2的消解結(jié)果。 第 四 章 集 合 及 其 運(yùn) 算4.1 集合的基本概念4.2 集合運(yùn)算4.3 集合的歸納定義及 歸納法證明第四章 集合及其運(yùn)算4.1.1集合及其元素 4.1.2 外延公理、概括公理和正規(guī)公理4.1.3 子集合第四章 集合及其運(yùn)算4.1 集合的基本概念4.2.1 并、交、差、補(bǔ)運(yùn)算4.2.2 冪集運(yùn)算和廣義并、交運(yùn)算*第四章 集合

37、及其運(yùn)算4.2 集合運(yùn)算4.3.1集合的歸納定義4.3.3 歸納法證明4.3.2 自然數(shù)的集合論定義第四章 集合及其運(yùn)算4.3 集合的歸納定義及 歸納法證明第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.1集合及其元素 組成集合的對象稱為集合的成員（member）或元素（elements）。 集合是一些確定的、作為整體識別的、互相區(qū)別的對象的總體。第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.1集合及其元素 集合的規(guī)定方式有三種：（l）列舉法 （2）描述法 （3）歸納法 第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.1集合及其元素 空集和只含有有限多個元素的集合稱為有限集（finit

38、e sets），否則稱為無限集（infinite sets）。有限集合中元素的個數(shù)稱為基數(shù)（cardinality）集合A的基數(shù)表示為 A。定義41第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.2 外延公理、概括公理和正規(guī)公理外延公理 概括公理 抽象原理 羅素悖論 正規(guī)公理 第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.2 外延公理、概括公理和正規(guī)公理 兩個集合 A和 B相等當(dāng)且僅當(dāng)它們具有相同的元素。即對任意集合A，B, A=B x(xAxB) 外延公理 第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.2 外延公理、概括公理和正規(guī)公理 對任意個體域，任一謂詞公式都確定一個以該域中的

39、對象為元素的集合。即對給定個體域U，對任意謂詞公式P(x)，存在集合S，使得 Sx xUP(x)概括公理 第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.2 外延公理、概括公理和正規(guī)公理 對任意謂詞公式P(x)，均存在集合S，使得 S = xP(x)抽象原理 考慮謂詞xx據(jù)抽象原理；有集合B，使 Bxxx 羅素悖論 第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.2 外延公理、概括公理和正規(guī)公理不存在集合A1，A2, A3，使得 A3 A2 A1正規(guī)公理 第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.3 子集合 集合A稱為集合B的子集合（或子集，subsets），如果A的每一個元素都是

40、B的元素，即 x(xAxB)定義4.2 第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.3 子集合 對任意集合A，B，AB當(dāng)且僅當(dāng)A B且B A 。 對任意集合A，A U。 設(shè)A，B，C為任意集合，若A B,B C，則A C。定理41定理42定理43第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.3 子集合 對任何集合A， A。即空集是任意集合的子集。 空集是唯一的 定理44定理45 設(shè) A 為一有限集合，A n，那么 A的子集個數(shù)為2n。 定理46第四章 集合及其運(yùn)算4.1 集合的基本概念4.1.3 子集合集合 A稱為集合 B的真子集，如 AB且AB?！癆是B的真子集”記為AB 定義43

41、第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.1 并、交、差、補(bǔ)運(yùn)算 設(shè)A，B，C為任意集合，那么 （1）AAA AAA （冪等律） （2）AB = BA AB = BA （交換律） （3）A（BC）=（AB）C A（BC）=（AB）C （結(jié)合律） （4）AA， AU=A （同一律） （5）A=， AU = U （零一律） （6）A(BC)=(AB)(AC) A(BC)=(AB)(AC) （分配律） （7）A（AB）= A， A（AB）= A （吸收律）定理47第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.1 并、交、差、補(bǔ)運(yùn)算 對任意集合 A，B，C， （l） A - BAB （2）A - A，

42、 A - A， A U = （3）A - (BC)(A - B)(A - C) A - (BC)(A - B)(A - C）定理48第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.1 并、交、差、補(bǔ)運(yùn)算對任意集合A，B（1） AA （雙重否定律） （2） U , U （補(bǔ)余律）（3） AAU , AA （互否律） （4）(AB)A B (AB)A B （德摩根律）定理49第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.1 并、交、差、補(bǔ)運(yùn)算 對任意集合A , B , C , D， （1）A AB，B AB （2）AB A AB B。 （3）A - B A （4）A B, A - B = ,AB = B

43、 , AB = A 四個命題等價。 （5）若A B,則B A定理410第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.1 并、交、差、補(bǔ)運(yùn)算對任意集合A，B若它們滿足 （l）ABU （2）AB 那么BA定理411第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.2 冪集（求冪？）運(yùn)算和廣義并、交運(yùn)算* 對任意集合 A，(A)稱為A的冪集（Power set）定義為 (A)x | xA 即A的全體子集構(gòu)成A的冪集。此種運(yùn)算稱為集合A的求冪運(yùn)算。 定義 4.5 第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.2 冪集（求冪？）運(yùn)算和廣義并、交運(yùn)算* 設(shè)A,B為任意集合, AB當(dāng)且僅當(dāng)(A) (B) 。 定理41

44、2第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.2 冪集（求冪？）運(yùn)算和廣義并、交運(yùn)算*若集合C的每個元素都是集合，則稱C為集合族（collections）。若集合族C可表示為 C =Sd|d D則稱 D為集合族的標(biāo)志集（index set）。定義46第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.2 冪集（求冪？）運(yùn)算和廣義并、交運(yùn)算* 對任意集合A和集合族C，有 定理413第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.2 冪集（求冪？）運(yùn)算和廣義并、交運(yùn)算*對任意集合A和集合族C，有定理414第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.2 冪集（求冪？）運(yùn)算和廣義并、交運(yùn)算*對任意集合族C有定理4

45、15第四章 集合及其運(yùn)算4.2 集合運(yùn)算4.2.2 冪集（求冪？）運(yùn)算和廣義并、交運(yùn)算*定理4.16 對任意集合 A:第四章 集合及其運(yùn)算4.3 集合的歸納定義及歸納法證明4.3.1集合的歸納定義（1）基礎(chǔ)條款（2）歸納條款（3）終極條款 條款（l），（2）又稱歸納定義的完備性條款，它們必須保證毫無遺漏地產(chǎn)生出待定義集合的全部成員；條款（3）又稱歸納定義的純粹性條款，它保證整個定義過程所規(guī)定的集合只包括滿足要求的那些對象。集合的歸納定義的組成第四章 集合及其運(yùn)算4.3 集合的歸納定義及歸納法證明4.3.1集合的歸納定義 通常把一個非空符號集合稱為字母表，常用表示之定義 4.9（l）稱空集 為自

46、然數(shù)，記為0。 （2）稱A為集合A的直接后繼，如果 AA A第四章 集合及其運(yùn)算4.3 集合的歸納定義及歸納法證明定義4.10 歸納定義自然數(shù)集N：（1）基礎(chǔ)條款：N 。（2）歸納條款：如果xN ， 則x= x x N。（3）終極條款（略）4.3.2 自然數(shù)的集合論定義第四章 集合及其運(yùn)算4.3 集合的歸納定義及歸納法證明4.3.3 歸納法證明 數(shù)學(xué)歸納法的基本模式（第一數(shù)學(xué)歸納法）起始于任意自然數(shù)n0的歸納證明模式第四章 集合及其運(yùn)算4.3 集合的歸納定義及歸納法證明4.3.3 歸納法證明起始于多個值的歸納證明模式允許有參變數(shù)的歸納證明模式第四章 集合及其運(yùn)算4.3 集合的歸納定義及歸納法證

47、明4.3.3 歸納法證明第二數(shù)學(xué)歸納法證明模式 第 五 章 關(guān) 系 5.1 有序組與集合的笛卡兒積 5.2 關(guān)系 5.4 序關(guān)系 5.3 等價關(guān)系第五章 關(guān) 系 5.2.4 關(guān)系特性閉包 5.2.1 關(guān)系的基本概念 5.2.2 關(guān)系的基本運(yùn)算 5.2.3 關(guān)系的基本特性第五章 關(guān) 系 5.2 關(guān)系 5.3.1 等價關(guān)系 5.3.2 劃分與等價關(guān)系第五章 關(guān) 系 5.3 等價關(guān)系5.4.1 序關(guān)系和有序集 5.4.2 良基性與良序集，完備序集5.4.3 全序集、良序集的構(gòu)造第五章 關(guān) 系 5.4 序關(guān)系第五章 關(guān) 系 5.1有序組與集合的笛卡兒積 設(shè)a，b為任意對象，稱集合a，a , b為二元有

48、序組，或序偶（ordered pairs），簡記為。稱a為的第一分量，稱b為第二分量。定義5.1 第五章 關(guān) 系 5.1有序組與集合的笛卡兒積 對任意序偶 , , = 當(dāng)且僅當(dāng)ac且b = d 。 定理5.1 遞歸定義n元序組 =a1，a1 , a2 = , an 定義5.2 第五章 關(guān) 系 5.1有序組與集合的笛卡兒積對任意對象a1，an，b1，bn， = 當(dāng)且僅當(dāng) a1 = b1 ，an= bn定理5.2 第五章 關(guān) 系 5.1有序組與集合的笛卡兒積 對任意集合 A1，A2 , ，An， （1） A1 A2，稱為集合A1 , A2的笛卡兒積 (Cartesian product)，定義為

49、A1 A2=x u v(x = u A1vA2) = u A1vA2 （2）遞歸地定義 A1 A2 An A1 A2 An= (A1 A2 An-1 ) An 當(dāng)A1 = A2 = =An =A時， A1 A2 An簡記為An 定義5.3第五章 關(guān) 系5.1有序組與集合的笛卡兒積對任意集合A1，A2 , ，An， A1 A2 An= a1 A1an An 定理5. 3第五章 關(guān) 系 5.1有序組與集合的笛卡兒積設(shè)A, B, C為任意集合，*表示 ，或 運(yùn)算，那么 A(B * C)(A B)*(A C) (B * C) A( B A)*(C A)定理5.4第五章 關(guān) 系 5.1有序組與集合的笛卡

50、兒積對任意有限集合A1，An，有: A1 AnA1 An ( 為數(shù)乘運(yùn)算)定理5.5 定理5.6 對任意非空集合A，B，第五章 關(guān) 系 5.2 關(guān)系 5.2.1 關(guān)系的基本概念 R稱為集合A1 ， A2 ， An-1到An上的n元關(guān)系（n-ary relations）,如果R是A1 A2 An-1的一個子集。當(dāng)A1A2An-1An時，也稱R為A上n元關(guān)系。當(dāng)n = 2時，稱R為A1到A2的二元關(guān)系。n元關(guān)系也可視為A1 A2 An-1到An的二元關(guān)系。定義5.4 第五章 關(guān) 系5.2 關(guān)系 5.2.1 關(guān)系的基本概念 AB, 稱為A到B的空關(guān)系。 AB AB ，稱AB 為A到B的全關(guān)系。 EA

51、=|xA,稱為A上相等關(guān)系。幾個特殊的二元關(guān)系第五章 關(guān) 系 5.2 關(guān)系 5.2.1 關(guān)系的基本概念 設(shè)R為A到B的二元關(guān)系。 （1）用xRy表示 R，意為x，y有R關(guān)系， x Ry表示R。 定義5.5 （2）稱 Dom（R）為關(guān)系R的定義域（domain）， Dom（R）=x|xAy(R) （3）稱 Ran（R）為關(guān)系 R的值域（range）， Ran（R）y| y Bx(R) （4）稱A為R的前域，B為R的陪域。第五章 關(guān) 系 5.2 關(guān)系 5.2.2 關(guān)系的基本運(yùn)算 稱關(guān)系R和S相等，如果R與S有相同的前域和陪域，并且 xy(xRyxSy)定義5.6 設(shè)R是A到B的關(guān)系，R的逆關(guān)系或逆

52、 （converse）是B到A的關(guān)系，記為R， 規(guī)定為 R= xRy 定義5.7 第五章 關(guān) 系 5.2 關(guān)系 5.2.2 關(guān)系的基本運(yùn)算 設(shè)R和S都是A到B的二元關(guān)系，為 , , - 運(yùn)算，那么 （1） R= R （2） R= R （3）(RS)= RS （4）R S當(dāng)且僅當(dāng) R S 定理5.7第五章 關(guān) 系 5.2 關(guān)系 5.2.2 關(guān)系的基本運(yùn)算 設(shè)R為A到B的二元關(guān)系，S為B到C的二元關(guān)系，那么RS為A到C的二元關(guān)系，稱為關(guān)系R與S的合成（compositions），定義為 RS=xAzCy(yBxRyyRz) 定義5.8 第五章 關(guān) 系 5.2 關(guān)系 5.2.2 關(guān)系的基本運(yùn)算 設(shè)E

53、A ,EB為集合A，B上的相等關(guān)系，R AB，那么 （1） EAR = REB = R （2） R = R = 定理5.8 第五章 關(guān) 系 5.2 關(guān)系 5.2.2 關(guān)系的基本運(yùn)算設(shè)R , S , T 均為A上二元關(guān)系，那么 （1）R ( S T) = (R S) (RT) （2）(S T)R = (SR) ( TR) （3）R(S T) (RS) (RT) （4）(S T)R (SR) ( TR) （5）R ( S T) = (R S)T （6）(RS ) =S R定理5.9 第五章 關(guān) 系5.2 關(guān)系 5.2.2 關(guān)系的基本運(yùn)算設(shè)R為A上二元關(guān)系，m，n為自然數(shù)，那么 （l） Rm RnR

54、m+n （2）(Rm)nRmn 定理5.10 設(shè)集合A的基數(shù)為n , R是A上二元關(guān)系，那么存在自然數(shù)i,j使得 0 i j ，RiRj。定理5.11 第五章 關(guān) 系 5.2 關(guān)系 5.2.2 關(guān)系的基本運(yùn)算第五章 關(guān) 系 5.2 關(guān)系 5.2.2 關(guān)系的基本運(yùn)算第五章 關(guān) 系 5.2 關(guān)系 5.2.2 關(guān)系的基本運(yùn)算設(shè)A=a1 , am，B=b1 , bm，C=c1 , cp,RAB，SB C，MR=rijmn為R的關(guān)系矩陣，MSsijnp 為S的關(guān)系矩陣。那么，合成關(guān)系RS的關(guān)系矩陣MRStij為一mp矩陣，其各分量tij可如下求取 定理5.12第五章 關(guān) 系 5.2 關(guān)系 5.2.3 關(guān)

55、系的基本特性 設(shè)R是A上的二元關(guān)系。（1）稱R是自反的（reflexive），如果對任意xA，均有xRx 。即, R自反當(dāng)且僅當(dāng) x(xAxRx) （2）稱R是反自反的（irreflexive）,如果對任意xA，xRx均不成立即, R反自反當(dāng)且僅當(dāng) x(xAxRx)（3）稱R是對稱的（symmetic），如果對任意x,yA，xRy蘊(yùn)涵yRx。即，R對稱當(dāng)且僅當(dāng) xy(x,yAxRyyRx) 定義5.9 （4）稱R是反對稱的（antisymmetric）,如果對任意x,yA，xRy且yRx蘊(yùn)涵xy。即, R反對稱當(dāng)且僅當(dāng)xy(x,yAxRyyRxx = y)（5）稱R是傳遞的（transitiv

56、e），如果對任意x,y,zA ，xRy且yRz蘊(yùn)涵xRz 。即, R傳遞當(dāng)且僅當(dāng) xyz(x,y,zAxRyyRzxRz)第五章 關(guān) 系 5.2 關(guān)系 5.2.3 關(guān)系的基本特性 定義5.9 第五章 關(guān) 系 5.2 關(guān)系 5.2.3 關(guān)系的基本特性設(shè)R為A上二元關(guān)系。 （1） R自反當(dāng)且僅當(dāng)EA R 。 （2） R反自反當(dāng)且僅當(dāng)EA R （3） R對稱當(dāng)且僅當(dāng)R R 。 （4） R反對稱當(dāng)且僅當(dāng)R R EA 。 （5） R傳遞當(dāng)且僅當(dāng)R2 R 。定理5.13第五章 關(guān) 系 5.2 關(guān)系 5.2.3 關(guān)系的基本特性設(shè)R1，R2均為A上二元關(guān)系。（1）五大特性對交運(yùn)算均封閉。即若R1，R2有五大

57、特性之一，則R1 R2仍有此性質(zhì)。（2）自反、反自反、對稱性對并運(yùn)算封閉。（3）反自反、對稱、反對稱性對差運(yùn)算封閉。（4）對稱性對補(bǔ)運(yùn)算封閉。（5）五大特性對求逆運(yùn)算均封閉。（6）自反性對合成運(yùn)算封閉，其他四大特性對合成運(yùn)算 均不封閉。定理5.14第五章 關(guān) 系 5.2 關(guān)系 5.2.4 關(guān)系特性閉包設(shè)R是集合A上二元關(guān)系，稱R 為R的自反閉包（對稱閉包，傳遞閉包），如果R滿足：（1）R是自反（對稱的，傳遞的）。（2）RR。（3）對任意A上關(guān)系R ，若R 滿足（1）和（2）， 則R R定義5.10 第五章 關(guān) 系 5.2 關(guān)系 5.2.4 關(guān)系特性閉包設(shè)R是集合A上的二元關(guān)系，那么 （1）r(

58、R) = EAR （2）s(R) = RR （3） 定理5.15 t()= Rii=1 第五章 關(guān) 系 5.2 關(guān)系 5.2.4 關(guān)系特性閉包設(shè)R是集合A上任一關(guān)系，那么（1）R自反當(dāng)且僅當(dāng)R = r(R)。（2）R對稱當(dāng)且僅當(dāng)R = s(R)。（3）R傳遞當(dāng)且僅當(dāng)R = t(R)。 定理 5.16 第五章 關(guān) 系 5.2 關(guān)系 5.2.4 關(guān)系特性閉包設(shè)R是集合A上任一二元關(guān)系，那么 （1）如果R是自反的，那么s(R)和t(R)都是自反的。 （2）如果R是對稱的，那么r(R)和t(R)都是對稱的。 （3）如果R是傳遞的，那么r(R)是傳遞的。 定理5.17第五章 關(guān) 系 5.2 關(guān)系 5.2

59、.4 關(guān)系特性閉包設(shè)R為集合A上的任一二元關(guān)系，那么（1）rs(R)sr(R)（2）rt(R)tr(R)（3）st(R) ts(R)定理5.18第五章 關(guān) 系 5.2 關(guān)系 5.2.4 關(guān)系特性閉包設(shè)R為A上二元關(guān)系A(chǔ)=n，那么定理5.19 t()= Rii=1n 第五章 關(guān) 系 5.2 關(guān)系 *5.2.5 特殊關(guān)系運(yùn)算 設(shè)R為一n元關(guān)系，P為一n元謂詞公式，那么關(guān)系R在P上的限定，表示為RP，確定為 RP=RP(x1,xn) 限定運(yùn)算（restriction） 第五章 關(guān) 系 5.2 關(guān)系 *5.2.5 特殊關(guān)系運(yùn)算 設(shè)R為一n元關(guān)系，A為1,2,n上的一個k元素序列i1,ik。以下記為x,

60、 pi(x) = xi (i=1,2,n)。那么關(guān)系R在A上的投影，表示為RA，確定為 RA= xR 投影運(yùn)算（projection） 第五章 關(guān) 系 5.2 關(guān)系 *5.2.5 特殊關(guān)系運(yùn)算 設(shè)R為一n元關(guān)系，S為一m元關(guān)系，那么R和S依據(jù)條件P的連接，記為RPS，確定為 RPS=xRySP(x1,xn,y1,ym )連接運(yùn)算（joint） 第五章 關(guān) 系 5.2 關(guān)系 *5.2.5 特殊關(guān)系運(yùn)算 設(shè)R為一n元關(guān)系，S為一m元關(guān)系，mn, 那么，R除以S的商，記為RS，確定為 RS=tt*SR除運(yùn)算（quotient） 第五章 關(guān) 系 5.3 等價關(guān)系 5.3.1 等價關(guān)系 稱集合A上關(guān)系R