1、數(shù)理邏輯與集合論復習提綱第1章 命題邏輯的基本概念 1.1 命題1.2 命題聯(lián)結詞及真值表1.3 合式公式1.4 重言式（三類公式的關系：P8）1.5 命題形式化1.6 波蘭表達式第2章 命題邏輯的等值和推理演算 2.1 等值定理2.2 等值公式2.4 聯(lián)結詞的完備集PQ = (PQ)， PQ = (PQ)2.5 對偶式2.6 范式2.7 推理形式（重言蘊涵的幾個結果：P31）2.8 基本的推理公式（(1)-(11):P31）2.9 推理演算2.10 歸結推理法會運用等值式證明兩個公式是否相等、判斷公式的類型求命題公式的對偶式、(主)析取范式、(主)合取范式及用途常用推理規(guī)則、直接證明法、附加

2、前提證明法、歸結法第4章 謂詞邏輯的基本概念 4.1 謂詞和個體詞4.2 函數(shù)和謂詞4.3 合式公式（合法性判斷）4.4 自然語句的形式化（與作業(yè)結合復習）4.5 有限域下公式(x)P(x)、(x)P(x)的表示法在1,2上的量化公式、解釋謂詞的定義，謂詞邏輯與命題邏輯的關系自由變元、約束變元及量詞的轄域第5章 謂詞邏輯的等值和推理演算 5.1 否定型等值式（證明）5.2 量詞分配等值式（證明）5.4 基本的推理公式(證明方法，(1)-(10):P77-78)5.5 推理演算(UI,EI,UG,EG和命題推理規(guī)則)5.6 謂詞邏輯的歸結推理法量詞否定等值式、量詞轄域收縮和擴張等值式、量詞分配等

3、值式、消去量詞等值式第9章 集 合9.1 集合的概念和表示方法9.2 集合間的關系和特殊集合9.3 集合的運算9.4 集合的圖形表示法9.5 集合運算的性質和證明(9.5.3不包括)9.6 有限集合的基數(shù)包含排斥原理及應用（作業(yè)）會運用集合運算的性質證明有關集合運算的命題成立與否、進行化簡，定理證明主要在9.5.1，9.5.4，而9.5.2只要記住結論第10章 關 系10.1 二元關系重要關系(、E、I、L、D、)10.2 關系矩陣和關系圖10.3 關系的逆、合成、限制和象10.4 關系的性質(性質判斷和證明)10.5 關系的閉包10.6 等價關系和劃分( 會求商集、類、劃分并會證明)10.7

4、 相容關系和覆蓋( 會求類并會證明)10.8 偏序關系(會畫哈斯圖，求特殊元素)對稱閉包、自反閉包和傳遞閉包的定義和構造方法第11章 函 數(shù)11.1 函數(shù)11.2 函數(shù)的合成和函數(shù)的逆第12章 集合的基數(shù)12.2 集合的等勢12.3 有限集合與無限集合12.4 集合的基數(shù)試題結構卷面一. 選擇題（10%）二. 填空題（20%）三. 判斷題（10%）四. 運算題（20%）五. 證明題（20%）六. 應用題（20%）各章內容比例第一、二章 命題邏輯 (20%)第四、五章 謂詞邏輯 (20%)第九章 集合 (20%)第十章 關系 (25%)第十一章 函數(shù) (10%)第十二章 集合的基數(shù) (5%)數(shù)理

5、邏輯試題樣卷一. 選擇題（10%）1設S、T、M為任意集合，則下列命題中，命題真值是真的是 。A 是的子集B. 若ST= ，則S=T C若ST=E，則ST D. 若ST=SM，則T=M二. 填空題：（20%）1、 公式 (pq) r 的成真賦值是_數(shù)理邏輯試題樣卷四. 運算題：（20%） 1.用等值演算法判斷公式q(pq)的類型 解 q(pq) q(pq) （蘊涵等值式） q(pq) （德摩根律） p(qq) （交換律，結合律） p0 （矛盾律） 0 （零律） 由最后一步可知，該式為矛盾式. 2.計算集合A= ，的冪集解：P(A)=P(, ) = , , , , 數(shù)理邏輯試題樣卷三.判斷題（1

6、0%）設S、T為任意集合， 若ST= ，則S=T 。（）五. 證明題（20%） 證明 A=B C=D AC=BD 證： 任取 AC xA yC xB yD BD 數(shù)理邏輯試題樣卷六.應用題：（20%） 證明蘇格拉底三段論: “人都是要死的, 蘇格拉底是人，所以蘇格拉底是要死的.” 令 F(x): x是人, G(x): x是要死的, a: 蘇格拉底 前提：x(F(x)G(x)，F(xiàn)(a) 結論：G(a) 證明： F(a) 前提引入 x(F(x)G(x) 前提引入 F(a)G(a) UI G(a) 假言推理 考試和答疑安排考試時間：18周星期五(12月31日)，8:00-10:00AM考試地點：34

7、0402答疑安排： 18周星期三(12月29日)，3:00-5:00答疑地點：31號樓3樓教師休息室數(shù)理邏輯樣卷一、單選題（共10分）1下列命題公式中，是重言式的是_。 A (p q) q B. (p q) (p q) C. pq D. p q2設A、B、C、D為任意集合，下面命題為真的是_。AA(BC)(AB)(AC)B. 若AB，則有A BC. (AB)= AB D. (A B)= A B3在關于二元關系性質的敘述中，正確的是_。A. 若關系R、S具有自反性，則RS一定有自反性；B. 存在既是對稱的也是反對稱的關系C. 若R、S是傳遞的，則RS也是傳遞的；D. 若R、S是自反的，則RS也是

8、自反的。4含有3個元素的集合共有_種不同的劃分. A. 4 B. 10 C. 5 D. 65設A、B為任意集合，下面命題為真的是_。AP(A)P(B)=P(AB) B. P(AB)=P(A)P(B)P(A-B)=P(A)-P(B) 若A-B= ，則B A數(shù)理邏輯樣卷8下列一階謂詞公式中，是邏輯有效式的是_。x(F(x) G(x) xF(x) xF(x)C. (F(x,y) R(x,y) R(x,y) D. xyF(x,y) xyF(x,y) 9設 f：BC, g：AB. 則下面命題是錯誤的是_。 A. 若 fg是滿射.則f 是滿射的 B. 若 fg是單射.則g是單射的 C. 若 fg是雙射.則

9、f 是單射的， g 是滿射的。 D. 若 fg是雙射.則 g是單射的， f 是滿射的。10下列關系的性質中，等價關系不具備的是_。 A自反的 B. 反對稱的 C. 傳遞的 D. 對稱的6設A、B是集合，右圖的文氏圖的陰影部分的區(qū)域可用_表達式表示A. AB B. AB A-B D. (AB)-(AB) 7集合A和B定義如下，則它們之間滿足_關系。 A=x|xRx2+x-2=0, B=y|yQy2+y-2=0 AA=B BBA CAB DAB數(shù)理邏輯樣卷二、填空題（共20分）1設p、q的真值為0；r的真值為1，則命題公式：p (qr)的真值是_。2設論域為1,2，一元謂詞定義為F(x): x2,

10、 G(x): x=0，則 (x)(F(x)G(x) 的真值為_。3設P(x)：x是正整數(shù)，Q(x)：x是偶數(shù)，R(x)：x是奇數(shù)，則公式： (x)(P(x) (Q(x)R(x)翻譯成自然語句為: _。4設A=a, b, c，則A的全部子集共有_個，A的冪集P(A)共有_個元素。 5在偏序關系的哈斯圖中，最大元素是_，極小元素是_。數(shù)理邏輯樣卷二、填空題（共20分）6兩個集合A和B相等(A=B)用謂詞形式可定義為：_。7已知集合C定義為： C=x|x Z 3x6 ，則集合C中的元素為：C=_。8. 若|A|=n，則A上共有_ 個不同的具有自反性的二元關系。9用聯(lián)系詞表示公式 P Q_。10對集合

11、A1,2,3，R是A上的關系，如 右圖所示，列出它所具有的性質：_。數(shù)理邏輯樣卷三判斷題（10分）1對非空集合A上的關系R，若R是自反的，則s(R)是自反的。（ ）2對A上的關系R1和R2，若R1和R2是自反的，則R1R2也是自反的。（ ）3對任意的集合A、B，若 P(A) P(B)，則 AB （ ）4集合A上的等價關系與劃分是一一對應的。（ ）5集合的最小元就是它的極小元；（ ）6已知：f(x)=2x+1， 則f 既不是單射也不是滿射。（ ）7若關系R是等價關系，則它必是相容關系。 （ ）8實數(shù)R與自然數(shù)N是不等勢的。（ ）9任給二元函數(shù)f , 它的逆f 1一定是二元函數(shù)關系。（ ）10對公

12、式A和B，若AB永真，必有A-B-也永真。（ ）數(shù)理邏輯樣卷四運算題（20分）1求命題公式： (PQ)R 的主析取范式和成真賦值。2. 已知A=1,2,3 ，B=1,4，求AB、A-B、AB和P(AB)。3. 設A=a, b, c, d，R=, , ，求R的自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)。4. 設f,g,h均為R-R的函數(shù)，f(x)=x+3, g(x)=2x+1, h(x)=x/2, 求gf, gh, gfh數(shù)理邏輯樣卷五證明題（共20分）1用等值演算法證明等值式： PQ = P (P Q)2. 設q為命題變項，與個體變元x無關，證明： (x)(P(x)q) = (x)P(x) q3.設 A=1,2,3,4,5,6,7,8, A上的關系 R如下定義： R = | x,yAxy(mod 3) 證明：R是一個等價關系。4使用推理規(guī)則證明： P(QR)，SP, Q S R數(shù)理邏輯樣卷六應用題（共20分）1. 甲、乙、丙、丁四人參加考試，有人問他們，誰的成績最好，甲說：“不