離散數(shù)學(xué)復(fù)習(xí)知識點

復(fù)習(xí)知識點：第1章命題、真命題、假命題命題符號化（連接詞）設(shè)P：天下大雨，Q：他在室內(nèi)運動，命題“除非天下大雨，否則他不在室內(nèi)運動”可符合化為（D）A．B．C．D．設(shè)P：只有你通過了大學(xué)英語六級考試，Q：你是英語專業(yè)的學(xué)生，R：你可以選修這門課程。命題“只有你通過了大學(xué)英語六級考試而且不是英語專業(yè)的學(xué)生，才可以選修這門課程”(B)A． B．C． D．什么是命題公式命題公式的等價式利用邏輯等價關(guān)系證明下面的等價關(guān)系證明：用真值表法求命題公式的主析取范式和主合取范式符號化以下語句，并推證結(jié)論的有效性。有些學(xué)生相信所有的老師，任何一個學(xué)生都不相信騙子，所以老師都不是騙子。解：設(shè)論述域為全總個體域，S(x)：x是學(xué)生，T(x)：x是老師，P(x)：x是騙子，L(x,y)：x相信y。將前提和結(jié)論符號化為 （1）P（2） T1，ES（3） T2，I（4） T2，I（5） T4，US（6） P（7） T6，US（8） T3,7，I（9） T8，US（10） T9，E（11） T5,10，I（12） T11，UG偵查員在調(diào)查了某珠寶店的珠寶失竊案現(xiàn)場以及詢問了認(rèn)證之后，得到以下事實：是營業(yè)員甲或營業(yè)員乙作案。如果是甲作案，則案發(fā)在非營業(yè)時間。如果乙提供的證詞可信，則案發(fā)時貨柜未上鎖。如果乙提供的證詞不可信，則案發(fā)在營業(yè)時間。貨柜在案發(fā)時上鎖了。偵查員推斷是營業(yè)員乙作案，請用命題邏輯判斷該推斷是否正確。解：設(shè)P：甲作案；Q：乙作案；R：發(fā)在營業(yè)時間；S乙的證詞可信；T：案發(fā)時貨柜未上鎖。 由題意可知，前提為：，，，， 推理過程： （1） P （2） P （3） T1，2，I （4） P （5）R T3，4，I （6） P （7） T5，6，I （8） P C． D．集合A上的等價關(guān)系的三個性質(zhì)是自反性、對稱性和傳遞性。集合A上的偏序關(guān)系的三個性質(zhì)是自反性、反對稱性和傳遞性。A上的偏序關(guān)系的Hasse圖如下。（1）下列哪些關(guān)系式成立：ab，ba，ce，ef，df，cf；（2）分別求出下列集合關(guān)于的極大（小）元、最大（?。┰?、上（下）界及上（下）確界（若存在的話）：（a）A；（b）{b,d}；（c）{b,e}；（d）{b,d,e}。解：（1）ba，ce，df，cf成立；（2）（a）的極大元為a,e,f，極小元為c；無最大元，c是最小元；無上界，下界是c；無上確界，下確界是c。（b）的極大元為b,d，極小元為b,d；無最大元和最小元；上界是e，下界是c；上確界是e，下確界是c。（c）的極大元為e，極小元為b；最大元是e，b是最小元；上界是e，下界是b；上確界是e，下確界是b。（d）的極大元為e，極小元為b,d；最大元是e，無最小元；上界是e，下界是c；上確界是e，下確界是c。設(shè)A={2，3，4}，B={2，4，7，10，12}從A到B的關(guān)系，試給出的關(guān)系圖和關(guān)系矩陣，并說明此關(guān)系及其逆關(guān)系是否為函數(shù)？為什么？A234B24A234B2471012的關(guān)系矩陣為關(guān)系不是到的函數(shù)，因為元素2，4的象不唯一逆關(guān)系也不是到的函數(shù)因為元素7的象不存在．下列函數(shù)是雙射的為（A）。A．f:ZE,f(x)=2x B．f:NNN,f(n)=<nC．f:RZ,f(x)=[x] D．f:ZN,f(x)=|x|（注：Z—整數(shù)集，E—偶數(shù)集，N—自然數(shù)集，R—實數(shù)集）設(shè)分別為整數(shù)集，自然數(shù)集，偶數(shù)集，則下列函數(shù)是雙射的為（A）A．:,B．:,C．:,D．:,設(shè)，則下列關(guān)系中能構(gòu)成到函數(shù)的是（C）A．B．C．D．設(shè)函數(shù)，都是單射，則（A）A．是單射B．是滿射C．是雙射D．既非單射又非滿射設(shè)函數(shù)，都是滿射，則（B）A．是單射B．是滿射C．是雙射D．既非單射又非滿射設(shè)是自然數(shù)集上的函數(shù),，則，．關(guān)系F={<x1,y1>,<x2,y2>,<x3,y2>}是函數(shù)（對）關(guān)系F={<x1,y1>,<x1,y2>}是函數(shù)（錯）設(shè)圖G的鄰接矩陣為 則G的邊數(shù)為(B)．A．6B．5C．4D．已知圖G的鄰接矩陣為，則G有（D）．A．5點，8邊B．6點，7邊C．6點，8邊D．5點，7邊設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是(D)．圖四A．（a）是強連通的B．（b）是強連通的C．（c）是強連通的D．（d）是強連通的在自然數(shù)集N上，運算C是不可結(jié)合的。A．a(chǎn)*b=a+b+3B．a(chǎn)*b=min{a,b}C．a(chǎn)*b=a+2bD．a(chǎn)*b=a·b(mod3)Q是有理集，<Q,*>（其中*為普通乘法）不能構(gòu)成（A）。A．群 B．獨異點 C．半群 D．交換半群設(shè)是個含幺半群，則對任意的有，其中是幺元.試證明是個阿貝爾群.證明:首先來證明是個群（只需證明每個元素均可逆），由條件知，對任意的元素，有，所以.其次，來證明運算可交換.對任意的，所以.因此，是個阿貝爾群.有理數(shù)集中的定義如下：（1）是半群嗎？是可交換的嗎？（2）求單位元.（3）中是否有可逆元？若有，指出哪些是可逆元，并指出其逆元是什么？解:（1），因，是半群.因，故*是可交換的.(2)設(shè)為其單位元，則應(yīng)有:，即，由的任意性，有.所以單位元為0.（3）設(shè)是可逆的，其逆元為，則應(yīng)有：，所以當(dāng)時，有逆元，其逆元為：，當(dāng)時，沒有逆元.設(shè)是群，則，則(a*b