離散數(shù)學(xué)知識點(diǎn)整理

1、離散數(shù)學(xué)一、邏輯和證明1.1命題邏輯命題：是一個(gè)可以判斷真假的陳述句。聯(lián)接詞：∧、∨、→、?、。記住“p僅當(dāng)q”意思是“如果p，則q”，即p→。記住“q除非p”意思是“p→q”。會考察條件語句翻譯成漢語。構(gòu)造真值表pqp∧qp∨qp→qp?qp⊙qpTTTTTTFFTFFTFFTFFTFTTFTTFFFFTTFT1.2語句翻譯系統(tǒng)規(guī)范說明的一致性是指系統(tǒng)沒有可能會導(dǎo)致矛盾的需求，即若pq無論取何值都無法讓復(fù)合語句為真，則該系統(tǒng)規(guī)范說明是

2、不一致的。1.3命題等價(jià)式邏輯等價(jià)：在所有可能情況下都有相同的真值的兩個(gè)復(fù)合命題，可以用真值表或者構(gòu)造新的邏輯等價(jià)式。證邏輯等價(jià)是通過p推導(dǎo)出q，證永真式是通過p推導(dǎo)出T。邏輯等價(jià)式p∧T?pp∨F?p恒等律p∧F?Fp∨T?T支配律p∧p?p冪等律(P)?p雙否律p∧q?q∧p交換律(p∧q)∧r?p∧(q∧r)結(jié)合律p∨(q∧r)?(p∨q)∧(p∨r)p∧(q∨r)?(p∧q)∨(p∧r)分配律(p∧q)?p∨q(p∨q)?p∧q

3、德摩根律德摩根律p∨(p∧q)?pP∧(p∨q)?p吸收律p∧p?Fp∨p?T否定律條件命題等價(jià)式p→q?p∨qp→q?q→pp∨q?p→qp∧q?(p→q)(p→q)?p∧q(p→q)∧(p→r)?p→(q∧r)p∧qp∨qp∨rq∨r(p∨q)∧(p∨r)→(q∨r)消解律量化推理規(guī)則?xP(x)P(c)全稱實(shí)例P(c)，任意c?P(x)全稱引入?xP(x)P(c)，對某個(gè)c存在實(shí)例P(c)，對某個(gè)c?xP(x)存在引入命題和量化命

4、題的組合使用。二、集合、函數(shù)、序列、與矩陣2.1集合∈說的是元素與集合的關(guān)系，?說的是集合與集合的關(guān)系。常見數(shù)集有N=0123...，Z整數(shù)集，Z正整數(shù)集，Q有理數(shù)集，R實(shí)數(shù)集，R正實(shí)數(shù)集，C復(fù)數(shù)集。A和B相等當(dāng)僅當(dāng)?x(x∈A?x∈B)；A是B的子集當(dāng)僅當(dāng)?x(x∈A→x∈B)；A是B的真子集當(dāng)僅當(dāng)?x(x∈A→x∈B)∧?x(x?A∧x∈B)。冪集：集合元素的所有可能組合，肯定有?何它自身。如?的冪集就是?，而?的冪集是?，?。笛卡

5、爾積：AB，結(jié)果是序偶，其中的一個(gè)子集叫一個(gè)關(guān)系。帶量詞和集合符號如?x∈R（x20）是真的，則所有真值構(gòu)成真值集。集合恒等式名稱(A∪B)=A∩B(A∩B)=A∪B德摩根律A∪(A∩B)=AA∩(A∪B)=A吸收律2.3函數(shù)考慮A→B的函數(shù)關(guān)系，定義域、陪域（實(shí)值函數(shù)、整數(shù)值函數(shù)）、值域、像集（定義域的一個(gè)子集在值域的元素集合）。一對一或者單射：B可能有多余的元素，但不重復(fù)指向。映上或者滿射：B中沒有多余的元素，但可能重復(fù)指向。一一對