資源描述：
《筆記離散數(shù)學(xué).docx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、離散數(shù)學(xué)復(fù)習(xí)筆記數(shù)理邏輯邏輯：以研究人的思維形式及思維規(guī)律為目的的一門學(xué)科數(shù)理邏輯：利用數(shù)學(xué)符號來協(xié)助推理的一門形式邏輯學(xué)命題：能表達(dá)判斷并具有確定真值的陳述句真值：每個命題都具有的一個值，要么為真，要么為假，不能隨著環(huán)境變化原子命題：不能再分解的命題復(fù)合命題：由原子命題符號及聯(lián)結(jié)詞組成的有意義的命題表達(dá)式否定非P合取P而且Q?析取P可兼或Q排斥析取P不可兼或Q單條件若P則Q雙條件P當(dāng)且僅當(dāng)Q命題公式：滿足特定條件的合法的命題表達(dá)式分量：命題公式中的原子命題翻譯：將自然語言轉(zhuǎn)化為數(shù)理邏輯語言真值表：對一個命題公式而言，將對于其分量的各種可能的真值指派匯聚成的表兩個命題等價：對兩個命題公式
2、A,B,若對于AB中的所有命題變元P1P2..對天安門的任一組真值指派A，B相同對應(yīng)的行的真值相同，則稱A與B等價等價定律：交換律，結(jié)合律，分配律，摩根律，否定律，同一律重言式：永真式，無論對命題變元作何種真值指派，它都等價于T的命題公式永假式：無論對命題變元作何種真值指派，它都等價于F的命題公式用一個命題公式代替重言式中同一個分量，依然為重言式蘊含式：若A->B永真則稱A蘊含B，記做A=>B原命題等價于它的逆否命題三個性質(zhì)：傳遞性，A=>BA=>CA=>(B^C)，A=>BC=>BAvC=>B有效結(jié)論：H1，H2、、、、Hn，C為一組命題公式，若H1^H2^...^Hn=>C,稱C
3、是一組條件下的有效結(jié)論三種方法：真值表法，直接證法，間接證法其他連接詞：條件否定，與非，或非規(guī)范命題表達(dá)式：只含非且或合取范氏：當(dāng)且僅當(dāng)具有A1^A2^...^An形式，A1，A2...An都是命題變元或其否定組成的析取式析取范式：當(dāng)且僅當(dāng)具有A1vA2v...vAn形式，A1，A2...An都是命題變元或其否定組成的合取式一個命題公式的合取范氏或析取范氏并不是唯一的n個命題變元的合取式，稱作布爾合取或小項，其中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次P^QP^非Q一般n個命題變元共有2^n個小項n個命題變元的析取式，稱作布爾析取或大項，其中每個變元與它的否定不能同時存
4、在，但兩者必須出現(xiàn)且僅出現(xiàn)一次PvQPv非Q主析取范式：對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則稱該等價式為原式的主析取范式主合取范式：對于給定的命題公式，如果有一個等價公式，它僅由大項的合取所組成，則稱該等價式為原式的主合取范式集合論集合：滿足一定特征的對象的全體擴(kuò)張原則：兩個集合相等，當(dāng)且僅當(dāng)他們有相同的元素抽象原則：任給一個集合U和一個性質(zhì)P，存在一個集合A，使得A的各個元素恰好是U的具有性質(zhì)P的那些成員集合表示：列舉法，特征法冪集：對給定的集合A，稱以A的全體子集為元素的集合為A的冪集集合的基數(shù)：
5、A
6、元素的個數(shù)無限集合：元素個數(shù)能與某個真子集一一對應(yīng)的
7、集合序偶：有序的二元數(shù)組笛卡爾積：稱A*B={
8、x屬于A且y屬于B}二元關(guān)系：以序偶作為元素的集合即關(guān)系xRy，關(guān)系前域指x，關(guān)系值域指y，關(guān)系域是前域和值域的并集。兩集合A與B的笛卡爾積的任一子集，稱為A到B的一個關(guān)系，若A=B，則稱該子集為A上的一個關(guān)系關(guān)系表示：集合表示法，關(guān)系矩陣法，關(guān)系圖表示法關(guān)系性質(zhì)：自反關(guān)系（x屬于X，屬于R），反自反關(guān)系（x屬于X，不屬于R）【存在既不反自反也不自反的關(guān)系】對稱性x，y屬于X，且屬于R，則屬于R，反對稱關(guān)系x屬于X，y屬于X，且屬于R，屬于R，則x=y【存在既對
9、稱又反對稱的關(guān)系，存在既不對稱又不反對稱的關(guān)系】傳遞性x,y,z屬于X，且都屬于R，則屬于R復(fù)合關(guān)系:屬于R,屬于S，則屬于R復(fù)合S逆關(guān)系:{
10、屬于R,x屬于X,y屬于Y}閉包運算：通過往已知關(guān)系中添加序偶讓它達(dá)到某種要求的運算，叫閉包運算覆蓋：A為非空集合，S={s1,s2...sm}其中Si屬于A，且S的并集為A，則S是A的一個覆蓋劃分：若對一個覆蓋而言，S任意兩個子集的交集為空，則稱S是A的一個劃分注：兩劃分的交叉劃分也是原集合A的一個劃分交叉劃分是原兩劃分的加細(xì)等價關(guān)系：同時具備自反，對稱和傳遞三個性
11、質(zhì)的關(guān)系即等價關(guān)系等價類：A上的等價關(guān)系R，A中的任意a，x屬于A，屬于R，為元素a生成的R等價類商集：若R是A上的一個等價關(guān)系，則稱以A的所有等價類為元素的集合為A關(guān)于R的商集，為A/R定理：A上的一個等價關(guān)系R確定了A的一個劃分A/RA上的一個劃分也能確定A上的一個等價關(guān)系A(chǔ)上的兩個等價關(guān)系R1，R2，則成立A/R1=A/R2等價于R1=R2A上的等價關(guān)系與劃分是一一對應(yīng)的相容關(guān)系：給定集合A上的關(guān)系r，若r是自反的、
