交大數(shù)理邏輯數(shù)理邏輯和集合論復(fù)習(xí)提綱課件

《數(shù)理邏輯與集合論》復(fù)習(xí)提綱第1章命題邏輯的基本概念

1.1命題1.2命題聯(lián)結(jié)詞及真值表1.3合式公式1.4重言式（三類公式的關(guān)系：P8）1.5命題形式化1.6波蘭表達式第2章命題邏輯的等值和推理演算

2.1等值定理2.2等值公式2.4聯(lián)結(jié)詞的完備集PQ=(PQ)，PQ=(PQ)2.5對偶式2.6范式2.7推理形式（重言蘊涵的幾個結(jié)果：P31）2.8基本的推理公式（(1)-(11):P31）2.9推理演算2.10歸結(jié)推理法會運用等值式證明兩個公式是否相等、判斷公式的類型求命題公式的對偶式、(主)析取范式、(主)合取范式及用途常用推理規(guī)則、直接證明法、附加前提證明法、歸結(jié)法第5章謂詞邏輯的等值和推理演算

5.1否定型等值式（證明）5.2量詞分配等值式（證明）5.4基本的推理公式(證明方法，(1)-(10):P77-78)5.5推理演算(UI,EI,UG,EG和命題推理規(guī)則)5.6謂詞邏輯的歸結(jié)推理法量詞否定等值式、量詞轄域收縮和擴張等值式、量詞分配等值式、消去量詞等值式第9章集合9.1集合的概念和表示方法9.2集合間的關(guān)系和特殊集合9.3集合的運算9.4集合的圖形表示法9.5集合運算的性質(zhì)和證明(9.5.3不包括)9.6有限集合的基數(shù)包含排斥原理及應(yīng)用（作業(yè)）會運用集合運算的性質(zhì)證明有關(guān)集合運算的命題成立與否、進行化簡，定理證明主要在9.5.1，9.5.4，而9.5.2只要記住結(jié)論第10章關(guān)系10.1二元關(guān)系重要關(guān)系(、E、I、L、D、)10.2關(guān)系矩陣和關(guān)系圖10.3關(guān)系的逆、合成、限制和象10.4關(guān)系的性質(zhì)(性質(zhì)判斷和證明)10.5關(guān)系的閉包10.6等價關(guān)系和劃分(會求商集、類、劃分并會證明)10.7相容關(guān)系和覆蓋(會求類并會證明)10.8偏序關(guān)系(會畫哈斯圖，求特殊元素)對稱閉包、自反閉包和傳遞閉包的定義和構(gòu)造方法第11章函數(shù)11.1函數(shù)11.2函數(shù)的合成和函數(shù)的逆第12章集合的基數(shù)12.2集合的等勢12.3有限集合與無限集合12.4集合的基數(shù)《數(shù)理邏輯》試題樣卷一.選擇題（10%）1．設(shè)S、T、M為任意集合，則下列命題中，命題真值是真的是

。A．是的子集B.

若S－T=，則S=T

C．若~S∪T=E，則S∩T≠

D.

若S∪T=S∪M，則T=M二.填空題：（20%）1、公式(pq)r的成真賦值是______________《數(shù)理邏輯》試題樣卷四.運算題：（20%）1.用等值演算法判斷公式q(pq)的類型解q(pq)

q(pq)（蘊涵等值式）

q(pq)（德摩根律）

p(qq)（交換律，結(jié)合律）

p0（矛盾律）

0（零律）由最后一步可知，該式為矛盾式.2.計算集合A={，{}}的冪集解：P(A)=P({,{}})={,{},{{}},{,{}}}《數(shù)理邏輯》試題樣卷六.應(yīng)用題：（20%）證明蘇格拉底三段論:“人都是要死的,蘇格拉底是人，所以蘇格拉底是要死的.”令F(x):x是人,G(x):x是要死的,a:

蘇格拉底前提：x(F(x)G(x))，F(xiàn)(a)結(jié)論：G(a)證明：①F(a)前提引入②x(F(x)G(x))前提引入③F(a)G(a)②UI④G(a)①③假言推理考試和答疑安排考試時間：18周星期五(12月31日)，8:00-10:00AM考試地點：340402答疑安排：18周星期三(12月29日)，3:00-5:00答疑地點：31號樓3樓教師休息室《數(shù)理邏輯》樣卷一、單選題（共10分）1．下列命題公式中，是重言式的是____________。A．(pq)qB.(pq)(pq)C.p∧qD.pq2．設(shè)A、B、C、D為任意集合，下面命題為真的是____________。A．A－(B∪C)＝(A－B)∩(A－C)B.若AB，則有~A~BC.~(A∪B)=~A∪~BD.~(A∩B)=~A∩~B3．在關(guān)于二元關(guān)系性質(zhì)的敘述中，正確的是__________。A.若關(guān)系R、S具有自反性，則R∩S一定有自反性；B.存在既是對稱的也是反對稱的關(guān)系C.若R、S是傳遞的，則R∪S也是傳遞的；D.若R、S是自反的，則R－S也是自反的。4．含有3個元素的集合共有_______種不同的劃分.A.4B.10C.5D.65．設(shè)A、B為任意集合，下面命題為真的是__________。A．P(A)∪P(B)=P(A∪B)B.P(A∩B)=P(A)∩P(B)P(A-B)=P(A)-P(B)若A-B=

，則BA《數(shù)理邏輯》樣卷二、填空題（共20分）1．設(shè)p、q的真值為0；r的真值為1，則命題公式：p∨(q∧r)的真值是______________。2．設(shè)論域為{1,2}，一元謂詞定義為F(x):x>2,G(x):x=0，則(x)(F(x)→G(x))的真值為_________________。3．設(shè)P(x)：x是正整數(shù)，Q(x)：x是偶數(shù)，R(x)：x是奇數(shù)，則公式：(x)(P(x)→(Q(x)∨R(x))翻譯成自然語句為:_____________________。4．設(shè)A={a,b,c}，則A的全部子集共有________個，A的冪集P(A)共有________個元素。5．在偏序關(guān)系<P({a,b,c,d},R)>的哈斯圖中，最大元素是_______，極小元素是___________?！稊?shù)理邏輯》樣卷二、填空題（共20分）6．兩個集合A和B相等(A=B)用謂詞形式可定義為：_____________。7．已知集合C定義為：C={x|xZ3x6}，則集合C中的元素為：C=___________________。8.若|A|=n，則A上共有__________個不同的具有自反性的二元關(guān)系。9．用聯(lián)系詞↑表示公式P

Q＝________________________。10．對集合A＝{1,2,3}，R是A上的關(guān)系，如右圖所示，列出它所具有的性質(zhì)：___________________________________?！稊?shù)理邏輯》樣卷三．判斷題（10分）1．對非空集合A上的關(guān)系R，若R是自反的，則s(R)是自反的。（）2．對A上的關(guān)系R1和R2，若R1和R2是自反的，則R1°R2也是自反的。（）3．對任意的集合A、B，若P(A)

P(B)，則AB（）4．集合A上的等價關(guān)系與劃分是一一對應(yīng)的。

（）5．集合的最小元就是它的極小元；（）6．已知：f(x)=2x+1，則f既不是單射也不是滿射。（）7．若關(guān)系R是等價關(guān)系，則它必是相容關(guān)系。（）8．實數(shù)R與自然數(shù)N是不等勢的。（）9．任給二元函數(shù)f,它的逆f1一定是二元函數(shù)關(guān)系。（）10．對公式A和B，若A→B永真，必有A-→B-也永真。（）《數(shù)理邏輯》樣卷五．證明題（共20分）1．用等值演算法證明等值式：

PQ=P(PQ)2.設(shè)q為命題變項，與個體變元x無關(guān)，證明：(x)(P(x)∨q)=(x)P(x)∨q3.設(shè)A={1,2,3,4,5,6,7,8},A上的關(guān)系R如下定義：

R={<x,y>|x,y∈A∧x≡y(mod3)}

證明：R是一個等價關(guān)系。4．使用推理規(guī)則證明：

P(QR)，S∨P,Q

S

R《數(shù)理邏輯》樣卷六．應(yīng)用題（共20分）1.甲、乙、丙、丁四人參加