離散數(shù)學復習知識點

1、復習知識點：第1章1 命題、真命題、假命題2 命題符號化（連接詞）設(shè)P：天下大雨，Q：他在室內(nèi)運動，命題“除非天下大雨，否則他不在室內(nèi)運動”可符合化為（D）A B CD設(shè)P：只有你通過了大學英語六級考試，Q：你是英語專業(yè)的學生，R：你可以選修這門課程。命題“只有你通過了大學英語六級考試而且不是英語專業(yè)的學生，才可以選修這門課程”( B )A B CD3 什么是命題公式4 命題公式的等價式5 利用邏輯等價關(guān)系證明下面的等價關(guān)系證明：6 用真值表法求命題公式的主析取范式和主合取范式7 符號化以下語句，并推證結(jié)論的有效性。有些學生相信所有的老師，任何一個學生都不相信騙子，所以老師都不是騙子。解：設(shè)論

2、述域為全總個體域，S(x)：x是學生，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)場以及詢問了認證之后，得到以下事實：（1） 是營業(yè)員甲或營業(yè)員乙作案。（2） 如果是甲作案，則案發(fā)在非營業(yè)時間。（3） 如果乙提供的證詞可信，則案發(fā)時貨柜未上鎖。（4） 如果乙提供的證詞不可信，則案發(fā)在營業(yè)時間。（5） 貨柜在案發(fā)時上鎖了。偵查員推斷是營業(yè)

3、員乙作案，請用命題邏輯判斷該推斷是否正確。解：設(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（9）T8，E（10）QT7，9，I所以，第2章8 謂詞的定義、量詞包括：9 什么是謂詞公式10 謂詞公式的自由變元、約束變元、轄域11 自然語句的符號化：比如：所有的狼都吃人，設(shè)T(x)表示為x是狼，C(x)表示為x吃人。12 判斷什么是前束范式，是前束范式，是前束范式13 證明證明：第3章1.集合的元素、集合的基數(shù)、集合的子集、集合

4、的運算空集的問題（空集的基數(shù)、空集與集合的子集、真子集的關(guān)系）冪集的問題（集合冪集的求法，冪集的基數(shù)）下面那個命題是不正確的是（ A ）ABCD下面那個命題是不正確的是（ A ）ABCD下列命題中不正確的是（）A.xx-xB.xx-xC.A=xx,則xA且xAD.A-B=A=B設(shè)P=x|(x+1)24，Q=x|x2+165x,則下列選項正確的是（）A.PQB.PQC.QPD.Q=P設(shè)A=a,a，下列命題錯誤的是（ B ）Aar(A)Bar(A)Car(A)Dar(A)在0（ D ）之間寫上正確的符號。A=B C D判斷下列命題哪個為真?（C）A空集只是非空集合的子集B空集是任何集合的真子集C

5、A-B=B-AA=B D若A的一個元素屬于B，則A=B判斷下列命題哪幾個正確？（ B ）A若ABAC，則BCBa, b=b, aCr（AB）r（A）r（B），（r(S)表示S的冪集）D若A為非空集，則AAA成立設(shè)A=a, b， B=c。求下列集合：（1）A0, 1B； （2）B2A； （3）(AB)2； （4）r (A)A。解：（1）A0, 1B=, , , ；（2）B2A=, ；（3）(AB)2=, , , ；（4）r (A)A=, , , , , , , 。關(guān)系1. 設(shè)A=a,b,c，則A上的二元關(guān)系有 23*3 或512 個 。2. 集合A=1, 2, , 10上的關(guān)系R=：x+y=10

6、, x, yA，則R 的性質(zhì)為（B）A自反的 B對稱的 C傳遞的，對稱的 D傳遞的設(shè)A=, 1, 1, 3, 1, 2, 3，則A上包含關(guān)系“”的哈斯圖為（C）A BCD集合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，

7、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ù)？為什么？ A234B2471012解：，則的關(guān)系

8、圖為：的關(guān)系矩陣為 關(guān)系不是到的函數(shù)，因為元素2，4的象不唯一逆關(guān)系也不是到的函數(shù)因為元素7的象不存在下列函數(shù)是雙射的為（A）。Af : ZE , f (x) = 2x Bf : NNN, f (n) =nCf : RZ , f (x) = x Df : 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 BC D設(shè)函數(shù)，都是單射，則（ A ）A是單射 B是滿射 C是雙射 D既非單射又非滿射設(shè)函數(shù)，都是滿射，

9、則（ B ）A是單射 B是滿射 C是雙射 D既非單射又非滿射設(shè)是自然數(shù)集上的函數(shù),，則，關(guān)系F=,是函數(shù) （對 ）關(guān)系F=,是函數(shù) （錯 ）設(shè)圖G的鄰接矩陣為則G的邊數(shù)為( B )A6 B5 C4 D3已知圖G的鄰接矩陣為 ，則G有（ D ） A5點，8邊 B6點，7邊 C6點，8邊 D5點，7邊設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是 ( D ) 圖四 A（a）是強連通的 B（b）是強連通的C（c）是強連通的 D（d）是強連通的在自然數(shù)集N上，運算 C 是不可結(jié)合的。Aa*b=a+b+3 Ba*b=mina,b Ca*b=a+2b Da*b=ab(mod 3)Q是有理集，（其中*為普通乘法）不能構(gòu)成（ A ）。A群 B獨異點 C半群 D交換半群設(shè)是個含幺半群，則對任意的有，其中是幺元.試證明是個阿貝爾群.證明: 首先來證明是個群（只需證明每個元素均可逆），由條件知，對任意的元素，有，所以.其次，來證明運算可交換.對任意的，所以 .因此，是個阿貝爾群.有理數(shù)集中的定義如下： （1）是半群嗎？是可交換的嗎？ （2）求單位元. （3）中是否有可逆元？若有，指出哪些是可逆元，并指出其逆元是什么？解:（1），因 ，是半群.因，故*是可交換的.(2)設(shè)為其單位元，則應(yīng)有: ，即，由的任意性，有.所以單位元為0.（3）設(shè)是可逆的，