數(shù)理邏輯和集合論復(fù)習(xí)提綱2014

1、數(shù)理邏輯復(fù)習(xí)提綱2014.12.第1章 命題邏輯的基本概念 1.2 命題聯(lián)結(jié)詞及真值表u 聯(lián)結(jié)詞的優(yōu)先順序?yàn)椋郝?lián)結(jié)詞的優(yōu)先順序?yàn)椋?, , , , 1.3 合式公式u 合法性判斷合法性判斷(P7-8)1.4 重言式u 公式的類型及它們之間的關(guān)系公式的類型及它們之間的關(guān)系(P8)1.5 命題形式化第2章 命題邏輯的等值和推理演算 2.2 等值公式 (P15-18)u 會(huì)運(yùn)用常用等值公式證明兩個(gè)公式是否相等、會(huì)運(yùn)用常用等值公式證明兩個(gè)公式是否相等、判斷公式的類型判斷公式的類型2.3 命題公式與直值表的關(guān)系u 會(huì)按真值表列出命題公式會(huì)按真值表列出命題公式 AB = A B PQ=(P Q) (QP)

2、=(P Q) ( PQ)=(PQ) ( P Q) (A B) = AB (A B) = AB第2章 命題邏輯的等值和推理演算 2.4 聯(lián)結(jié)詞的完備集u n元命題公式的個(gè)數(shù)，元命題公式的個(gè)數(shù)，連結(jié)詞連結(jié)詞( 、 )的性質(zhì)的性質(zhì)2.5 對(duì)偶式定理2.5.1-2.5.6 2.6 范式u 求主析求主析(合合)取范式和成真、成假賦值及應(yīng)用取范式和成真、成假賦值及應(yīng)用2.8 基本的推理公式（P31: -）2.9 推理演算u 常用推理規(guī)則常用推理規(guī)則, 直接證明法、附加前提證明法直接證明法、附加前提證明法2.10 歸結(jié)推理法第4章 謂詞邏輯的基本概念 4.2 函數(shù)和量詞u 量詞及使用，量詞及使用，自由變?cè)?/p>

3、約束變?cè)杂勺冊(cè)?、約束變?cè)?.3 合式公式（合法性判斷）4.4 自然語句的形式化（與作業(yè)結(jié)合復(fù)習(xí)）4.5 有限域下公式(x)P(x)、(x)P(x)的表示法u 有限論域下公式的表示法有限論域下公式的表示法u 在域在域1,2上的量化公式、解釋上的量化公式、解釋第5章 謂詞邏輯的等值和推理演算 5.1 否定型等值式（P69-70: 證明）證明）5.2 量詞分配等值式（P71-73: 證明）證明）u量詞對(duì)量詞對(duì)、 和和的分配律的分配律 u量詞量詞 對(duì)對(duì)的分配律，量詞的分配律，量詞 對(duì)對(duì)的分配律的分配律5.3 范式 (前束范式、含詞Skolem標(biāo)準(zhǔn)形)5.4 基本的推理公式(證明方法，P77-78:

4、-)5.5 推理演算u與與量詞有關(guān)的推理規(guī)則和命題推理量詞有關(guān)的推理規(guī)則和命題推理規(guī)則規(guī)則5.6 謂詞邏輯的歸結(jié)推理法第9章 集 合9.1 集合的概念和表示方法(N,Z,Q,R)9.2 集合間的關(guān)系和特殊集合u 集合間關(guān)系的謂詞表示集合間關(guān)系的謂詞表示9.3 集合的運(yùn)算u 集合運(yùn)算的謂詞表示集合運(yùn)算的謂詞表示, 冪集、笛卡兒積冪集、笛卡兒積9.4 集合的文氏圖表示9.5 集合運(yùn)算的性質(zhì)和證明(9.5.3除外)9.6 有限集合的基數(shù)包含排斥原理及應(yīng)用u 會(huì)運(yùn)用集合運(yùn)算的性質(zhì)證明有關(guān)集合運(yùn)算的命題成會(huì)運(yùn)用集合運(yùn)算的性質(zhì)證明有關(guān)集合運(yùn)算的命題成立與否、進(jìn)行化簡(jiǎn)，定理證明主要在立與否、進(jìn)行化簡(jiǎn)，定理證

5、明主要在9.5.1，9.5.4，而而9.5.2只要記住結(jié)論只要記住結(jié)論n 證明證明 X Y命題演算法命題演算法包含傳遞法包含傳遞法等價(jià)條件法等價(jià)條件法反證法反證法并交運(yùn)算法并交運(yùn)算法n 證明證明 X=Y命題演算法命題演算法等式代入法等式代入法反證法反證法運(yùn)算法運(yùn)算法第10章 關(guān)系n10.1 二元關(guān)系 u 重要重要關(guān)系關(guān)系(、E、I I、L、D、 )，定義域和值域，定義域和值域n10.2 關(guān)系矩陣和關(guān)系圖n10.3 關(guān)系的運(yùn)算u 逆逆、合成合成、限制和象、限制和象u 逆、合成運(yùn)算的性質(zhì)逆、合成運(yùn)算的性質(zhì)(P166-167)n10.4 關(guān)系的性質(zhì)u 性質(zhì)的謂詞定義、判斷、證明、充要條件性質(zhì)的謂詞定

6、義、判斷、證明、充要條件u 性質(zhì)運(yùn)算后的保持性性質(zhì)運(yùn)算后的保持性第10章 關(guān)系n 10.5 關(guān)系的閉包u 閉包的定義、性質(zhì)和構(gòu)造方法閉包的定義、性質(zhì)和構(gòu)造方法n 10.6 等價(jià)關(guān)系和劃分u 等價(jià)等價(jià)關(guān)系的定義、判斷和證明關(guān)系的定義、判斷和證明u 會(huì)會(huì)求商集求商集、等價(jià)類、等價(jià)類、劃分劃分n 10.7 相容關(guān)系和覆蓋u 相容關(guān)系相容關(guān)系的定義、判斷和的定義、判斷和證明，會(huì)求最大相容類證明，會(huì)求最大相容類n 10.8 偏序關(guān)系u 偏序、擬序、全序關(guān)系偏序、擬序、全序關(guān)系的定義、判斷和的定義、判斷和證明證明u 會(huì)畫會(huì)畫哈斯圖，特殊哈斯圖，特殊元素，鏈、反鏈元素，鏈、反鏈試題結(jié)構(gòu)卷面卷面一一. 選擇題

7、（選擇題（20%）二二. 填空題（填空題（20%）三三. 計(jì)算題計(jì)算題（20%）四四. 證明題（證明題（20%）五五. 應(yīng)用題（應(yīng)用題（20%）各章內(nèi)容比例第一、二章 命題邏輯 (25%)第四、五章 謂詞邏輯 (25%)第九章 集合 (20%)第十章 關(guān)系 (30%)數(shù)理邏輯試題樣題一. 選擇題（20%）1設(shè)A、B、C為任意集合，則下列命題中，是真命題是 。A若若A B=A C，則，則B=CB. 若若 AB = ，則，則A=B C若若A B=A C，則，則B=C D. 二二. 填空題填空題：（20%）1、 公式 (PQ) R的成真賦值是_數(shù)理邏輯試題樣題三. 計(jì)算題：（20%） 1.用等值演算

8、法判斷公式Q(PQ)的類型 解：解：Q(PQ) Q ( P Q) Q (P Q) P (Q Q) P F F 由最后一步可知，該式為由最后一步可知，該式為矛盾式矛盾式. . 2.計(jì)算集合A= ，的冪集n 解：解：P(A)=P(, ) =, , , , 數(shù)理邏輯試題樣題四四. 證明題（證明題（20%） 證明證明 A=B C=D A C=B D n 證：證： 任取任取 A C x A y C x B y D B D 數(shù)理邏輯試題樣題五.應(yīng)用題：（20%）證明: “金屬都是導(dǎo)電體, 銅是金屬，所以銅是導(dǎo)電體?！苯饨猓毫盍?F(x): x是是金屬金屬, G(x): x是導(dǎo)電體是導(dǎo)電體, a:銅銅 前提：前提： x(F(x)G(x)，F(xiàn)(a) 結(jié)論：結(jié)論：G(a) 證明