離散數(shù)學(xué)期末總復(fù)習(xí)

期末考試的題型：一、選擇題：10題*2分二、填空題：5題*2分三、計(jì)算題：5題*9分四、證明題：2題*8分五、綜合題：1題:9分第一局部

1、命題指真假唯一的陳述句?！?〕否認(rèn)“┐〞2、5個(gè)邏輯聯(lián)結(jié)詞及其真值表〔2〕合取“∧〞0001(3)析取“∨〞0111〔4〕蘊(yùn)含“→〞1101只要p,就有q.p→qP僅當(dāng)q.只有p,才q.除非p,才有q.除非p,否那么沒有q.p→qq→pq→pq→p〔5〕等價(jià)“〞10013、真值表(大題)pqr010000100101100110101111011例1

寫出真值表.0000011111110011111014.定義(1)假設(shè)A在它的任何賦值下均為真,那么稱A為重言式或永真式;(2)假設(shè)A在它的任何賦值下均為假,那么稱A為矛盾式或永假式;(3)假設(shè)A不是矛盾式,那么稱A是可滿足式.5.主析取范式與主合取范式〔大題〕相關(guān)知識(shí)點(diǎn)：〔1〕、等值式分配律A

(B

C)

(A

B)

(A

C),A

(B

C)

(A

B)

(A

C)蘊(yùn)涵等值式A

B

A

B假言易位A

B

B

A〔2〕、析取范式與合取范式文字——命題變項(xiàng)及其否認(rèn)的總稱例如：p,q,r,

p,

q,

r…例如：p,

q,p

q,p

q

r,…例如：p,

q,p

q,p

q

r,…簡單合取式——有限個(gè)文字構(gòu)成的合取式簡單析取式——有限個(gè)文字構(gòu)成的析取式析取范式——由有限個(gè)簡單合取式組成的析取式例如：p,

p

q,p

q,(p

q)(p

q

r)(q

r)合取范式——由有限個(gè)簡單析取式組成的合取式例如：p,p

q,

p

q,(p

q)

p(p

q

r)范式——析取范式與合取范式的總稱〔3〕、主析取范式與主合取范式在含有n個(gè)命題變項(xiàng)的簡單合取式〔簡單析取式〕中，假設(shè)每個(gè)命題變項(xiàng)和它的否認(rèn)式恰好出現(xiàn)且僅出現(xiàn)一次，而且命題變項(xiàng)和它的否認(rèn)式按下標(biāo)從小到大或按字典順序排列，稱這樣的簡單合取式〔簡單析取式〕為極小項(xiàng)(極大項(xiàng)).每個(gè)極小項(xiàng)只有一個(gè)成真賦值，用m表示；每個(gè)極大項(xiàng)只有一個(gè)成假賦值，用M表示。用mi表示第i個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示.用Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示.mi〔Mi〕稱為極小項(xiàng)〔極大項(xiàng)〕的名稱.主析取范式——由極小項(xiàng)構(gòu)成的析取范式主合取范式——由極大項(xiàng)構(gòu)成的合取范式

(2)假設(shè)某個(gè)Bj既不含pi,又不含pi,那么將Bj展開成BjBj(pipi)(Bjpi)(Bjpi)重復(fù)這個(gè)過程,直到所有簡單合取式都是長度為n的極小項(xiàng)為止(3)消去重復(fù)出現(xiàn)的極小項(xiàng),即用mi代替mimi(4)將極小項(xiàng)按下標(biāo)從小到大排列(1)求A的析取范式A

=B1

B2

…

Bs,其中Bj是簡單合取式j(luò)=1,2,…,s求公式主析取范式的步驟:設(shè)公式A含命題變項(xiàng)p1，p2，…，pn例2(1)求公式A=(p

q)∨r的主析取范式解(p

q)

(p

q)

(

r

r)

(p

q

r)

(p

q

r)

m6

m7r

(

p

p)

(

q

q)

r

(

p

q

r)

(

p

q

r)

(p

q

r)

(p

q

r)

m1

m3

m5

m7所以A=(p

q)∨r

m1

m3

m5

m6

m7求公式的主合取范式的步驟:設(shè)公式A含命題變項(xiàng)p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是簡單析取式j(luò)=1,2,…,s(2)假設(shè)某個(gè)Bj既不含pi,又不含pi,那么將Bj展開成BjBj(pipi)(Bjpi)(Bjpi)重復(fù)這個(gè)過程,直到所有簡單析取式都是長度為n的極大項(xiàng)為止(3)消去重復(fù)出現(xiàn)的極大項(xiàng),即用Mi代替MiMi(4)將極大項(xiàng)按下標(biāo)從小到大排列例3〔2〕求公式A=(pq)∨r的主合取范式A=(p

q)∨rp

r

(p

r)

(q

r)

(p

q

r)

(p

q

r)

p

(q

q)

r

M0

M2q

r

(p

p)

q

r

M0

M4

(p

q

r)

(

p

q

r)

A=(p

q)∨r

M0

M2

M46.聯(lián)結(jié)詞完備集設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何n(n1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，那么稱S是聯(lián)結(jié)詞完備集.推論以下都是聯(lián)結(jié)詞完備集(1)S1={

,

,

,

}(2)S2={

,

,

,

,

}(3)S3={

,

}(4)S4={

,

}(5)S5={

,

}{,,,}不是聯(lián)結(jié)詞完備集,7.自然推理系統(tǒng)P〔大題〕

假言推理：A→BA∴B拒取式規(guī)那么：例4構(gòu)造推理的證明。(課本54頁18題)8、一階邏輯命題符號(hào)化例5

將下面兩個(gè)命題符號(hào)化:(1)凡人都呼吸.(2)有的人用左手寫字.解:令M(x):

是人；F(x):x呼吸；G(x):x用左手寫字.于是(1)，(2)的符號(hào)化形式分別為

(M(x)→F(x))(M(x)∧F(x))例6將以下命題符號(hào)化:

(1)有的兔子比所有的烏龜跑得快.

(2)并非兔子都比烏龜跑得快.解:令F(x):x是兔子.G(y):y是烏龜.H(x,y):x比y跑得快.這2個(gè)命題分別符號(hào)化為9、轄域、自由與約束

在公式

xA和

xA

中，稱x為指導(dǎo)變元，A為相應(yīng)量詞的轄域.在

x和

x的轄域中,x的所有出現(xiàn)都稱為約束出現(xiàn).A中不是約束出現(xiàn)的其他變項(xiàng)均稱為是自由出現(xiàn)的.例7指出以下各公式中的指導(dǎo)變元，各量詞的轄域，自由出現(xiàn)以及約束出現(xiàn)的個(gè)體變項(xiàng):x是指導(dǎo)變元.量詞

x的轄域是F(x,y)→G(x,z)其中，x是約束出現(xiàn)的.y和z均為自由出現(xiàn)的.

x(F(x,y)

G(x,z))定義設(shè)A,B為集合,A與B的差運(yùn)算定義如下:A–B＝{x|x∈A∧x?B}

E差

A

B由定義可知A–B＝A-(A∩B)

1、集合的運(yùn)算第二局部定義設(shè)A,B為集合,A與B的對稱差集A⊕B,定義為A⊕B={x|x∈A∪B∧x

A∩B}也可定義為A⊕B=(A-B)∪(B-A)也可定義為A⊕B=(A∪B)-(A∩B)E對稱差

A

B2、有窮集的計(jì)數(shù)〔大題〕例8某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球，6個(gè)會(huì)打網(wǎng)球的人都會(huì)打籃球或排球，求不會(huì)打球的人數(shù)。

藍(lán)排網(wǎng)解：24351055所以不會(huì)打球的人數(shù)是5個(gè)人。3、關(guān)系的運(yùn)算〔大題〕(1)R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域(domain)，記為domR。(2)R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域(range)，記作ranR。(3)R的定義域和值域的并集稱為R的域(field)，記作fldR。例如R={<1,2>,<1,3>,<2,4>,<4,3>},那么domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}〔4〕設(shè)F,G為二元關(guān)系，G對F的復(fù)合記作FG，其中FG=|<x,z>|y(<x,y>F<y,z>G)}例9

(課本131頁16題)4、冪運(yùn)算的性質(zhì)定理設(shè)R是A上的關(guān)系,假設(shè)存在自然數(shù)s,t(s<t)使得Rs=Rt,那么(1)對任何k∈N有Rs+k=Rt+k(2)對任何k,i∈N有Rs+kp+i=Rs+i,其中p=ts例10、假設(shè)R3=R7,試化簡R2023.解：由R3=R7可知p=7-3=4因此，2023=3+2023=3+4*502+2R2023=R3+2=R5.5、關(guān)系的性質(zhì)設(shè)R為A上的關(guān)系,1．自反性與反自反性(1)假設(shè)x(x∈A→<x,x>∈R),那么稱R在A上是自反的.(2)假設(shè)x(x∈A→<x,x>R),那么稱R在A上是反自反.2．對稱性與反對稱性(1)假設(shè)xy(x,y∈A∧<x,y>∈R→<y,x>∈R),那么稱R為A上對稱的關(guān)系.(2)假設(shè)xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),那么稱R為A上反對稱的關(guān)系.3．傳遞性假設(shè)xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),那么稱R是A上的傳遞關(guān)系.設(shè)R是非空集合A上的關(guān)系,R的自反〔對稱或傳遞〕閉包是A上的關(guān)系R,使得R滿足以下條件：〔1〕R是自反的〔對稱的或傳遞的〕〔2〕RR〔3〕對A上任何包含R的自反〔對稱或傳遞〕關(guān)系R有RR.一般將R的自反閉包記作r(R),對稱閉包記作s(R),傳遞閉包記作t(R).6、關(guān)系的閉包設(shè)R為非空集合上的關(guān)系.如果R是自反的、對稱的和傳遞的,那么稱R為A上的等價(jià)關(guān)系.7、等價(jià)關(guān)系〔大題〕A上的等價(jià)關(guān)系與A的集合劃分是一一對應(yīng)的.例11課本133頁36題〔1〕例12A＝{1,2,3}上等價(jià)關(guān)系有多少個(gè)？解如以下圖,做出A的所有劃分：123123123123123因此A＝{1,2,3}上等價(jià)關(guān)系有5個(gè).8、偏序關(guān)系〔1〕哈斯圖〔大題〕特點(diǎn)：〔1〕每個(gè)結(jié)點(diǎn)沒有環(huán); 〔2〕兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的上下表示，位置低的元素的順序在前,即：假設(shè)x<y,那么x畫在y的下層;〔3〕具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊.〔2〕最小元、最大元、極小元、極大元設(shè)<A,?>為偏序集,BA,y∈B.〔1〕假設(shè)x(x∈B→y?x)成立,那么稱y為B的最小元.〔2〕假設(shè)x(x∈B→x?y)成立,那么稱y為B