離散數(shù)學(xué)復(fù)習(xí)１

離散數(shù)學(xué)復(fù)習(xí)類型一、填空題二、判斷題三、綜合題

第一部分

基本知識(shí)點(diǎn)：聯(lián)結(jié)詞，命題公式的類型，極小項(xiàng)，極大項(xiàng)，成真賦值（成假賦值），基本等值式，推理定律，符號(hào)化（命題、謂詞）1、求命題公式的兩種主范式（重點(diǎn)3元）2、構(gòu)造命題公式序列證明（正確推理的證明方法）另外，還需掌握真值表法、等值演算法、主范式法

第二部分基本知識(shí)點(diǎn)：集合（含關(guān)系）的運(yùn)算，冪集，二元關(guān)系及性質(zhì)，等價(jià)關(guān)系，劃分，偏序關(guān)系，哈斯圖，函數(shù)及性質(zhì)1、構(gòu)造給定集合上的等價(jià)關(guān)系、偏序關(guān)系2、判定一關(guān)系是否是函數(shù)？若是，問函數(shù)具有哪些性質(zhì)？

第四部分基本知識(shí)點(diǎn)：簡(jiǎn)單圖，子圖，Kn,n階有向完全圖，可圖化，同構(gòu)，路徑，圈，連通圖（強(qiáng)連通圖，弱連通圖），割點(diǎn)，橋，二部圖，鄰接矩陣，歐拉圖、哈密頓圖，無向樹，最小生成樹，根數(shù)，最優(yōu)二叉樹1、作出K4的生成子圖（非同構(gòu)）2、作出三階有向完全圖的生成子圖（非同構(gòu)）3、作出滿足一定條件的歐拉圖、哈密頓圖4、作出滿足一定條件的無向樹、最小生成樹、最優(yōu)2叉樹5、利用鄰接矩陣求一有向圖中兩頂點(diǎn)之間的通路、回路數(shù)二、判斷題１、命題都是陳述句２、命題公式包括矛盾式和可滿足式兩類３、命題是０元謂詞，０元謂詞是命題４、命題公式等值就是同真值５、任一命題公式都存在唯一的兩種范式６、任一謂詞公式都存在唯一的前束范式７、含n個(gè)命題變?cè)乃忻}公式的主析取范式最多有有限種，并且為

８、命題之間的等值關(guān)系是等價(jià)關(guān)系(偏序關(guān)系)10、任意一個(gè)命題公式的賦值不是成真賦值就是成假賦值11、真值表是表示命題公式的一種方式12、任意一個(gè)命題公式的層數(shù)都為正整數(shù)13、同一個(gè)命題公式可能既是析取范式又是合取范式14、同一個(gè)命題公式可能既是主析取范式又是主合取范式（A=p）15、一個(gè)命題公式有唯一的極小項(xiàng)并且有唯一的極大項(xiàng)16、一個(gè)正確的推理其結(jié)論未必是真命題17、推理定律對(duì)應(yīng)的公式都是永真式18、封閉的公式在一確定解釋下，其真值是唯一的19、同一個(gè)命題符號(hào)化后的形式可能不唯一１、集合是二元關(guān)系，二元關(guān)系是集合２、集合可以表示函數(shù)３、二元關(guān)系是函數(shù)，函數(shù)是二元關(guān)系４、非空集上一個(gè)關(guān)系可能既是自反關(guān)系又是反自反關(guān)系５、一個(gè)關(guān)系可能既是對(duì)稱關(guān)系又是反對(duì)稱關(guān)系６、一個(gè)關(guān)系可能既是等價(jià)關(guān)系又是偏序關(guān)系1、圖分為簡(jiǎn)單圖和多重圖2、歐拉(哈密頓)圖都是連通圖3、歐拉圖都是哈密頓圖4、哈密頓圖都是歐拉圖5、半歐拉圖都是半哈密頓圖6、半哈密頓圖都是半歐拉圖7、任一個(gè)有限圖都可以用矩陣、圖形和集合表示8、圖分為歐拉圖和半歐拉圖9、圖分為哈密頓圖和半哈密頓圖10、樹都是連通圖11、任一棵樹都是自己生成樹12、任一連通圖都有生成樹13、含n個(gè)頂點(diǎn)，n-1條邊的圖一定是生成樹14、一棵樹的余樹不一定是樹15、可圖化的非負(fù)整數(shù)列在同構(gòu)的意義下，非負(fù)整數(shù)列與圖不一定是一一對(duì)應(yīng)的16、邊帶權(quán)的無向（連通）圖一定有最小生成樹

17、根樹的頂點(diǎn)分為分支點(diǎn)和樹葉18、最優(yōu)2叉樹一定是2叉正則樹19、含t片樹葉的最優(yōu)2叉樹一定含有t-1個(gè)分支點(diǎn)20、含t片樹葉并且樹葉帶權(quán)的2叉樹一定存在最優(yōu)2叉樹21、一歐拉圖不一定是一半歐拉圖。（）22、在集合表達(dá)式中，關(guān)系運(yùn)算優(yōu)先于集合運(yùn)算。（

）23、在圖論中，平凡圖是一棵樹。