離散數(shù)學(xué)形成性考核作業(yè)4離散數(shù)學(xué)綜合練習(xí)書(shū)面作業(yè)?一、集合論部分（一）集合的基本概念1.集合的定義：集合是由一些確定的、互不相同的對(duì)象所組成的整體。例如，集合\(A=\{1,2,3,4\}\)，其中\(zhòng)(1\)、\(2\)、\(3\)、\(4\)就是集合\(A\)的元素。2.集合的表示方法列舉法：將集合中的元素一一列舉出來(lái)，寫在花括號(hào)內(nèi)。如上述集合\(A\)就是用列舉法表示的。描述法：通過(guò)描述元素所具有的共同性質(zhì)來(lái)表示集合。例如，集合\(B=\{x|x\)是大于\(0\)小于\(5\)的整數(shù)\(\}\)，這種表示方法明確了集合中元素滿足的條件。（二）集合的運(yùn)算1.并集：設(shè)\(A\)、\(B\)是兩個(gè)集合，則\(A\)與\(B\)的并集\(A\cupB=\{x|x\inA\)或\(x\inB\}\)。例如，\(A=\{1,2,3\}\)，\(B=\{3,4,5\}\)，那么\(A\cupB=\{1,2,3,4,5\}\)。2.交集：\(A\)與\(B\)的交集\(A\capB=\{x|x\inA\)且\(x\inB\}\)。對(duì)于上述例子，\(A\capB=\{3\}\)。3.差集：\(A\)與\(B\)的差集\(AB=\{x|x\inA\)且\(x\notinB\}\)。所以\(AB=\{1,2\}\)，\(BA=\{4,5\}\)。4.補(bǔ)集：設(shè)\(U\)是全集，\(A\subseteqU\)，則\(A\)的補(bǔ)集\(\overline{A}=UA=\{x|x\inU\)且\(x\notinA\}\)。例如，若\(U=\{1,2,3,4,5,6\}\)，\(A=\{1,2,3\}\)，那么\(\overline{A}=\{4,5,6\}\)。（三）集合間的關(guān)系1.包含關(guān)系：若集合\(A\)的每一個(gè)元素都是集合\(B\)的元素，則稱\(A\)包含于\(B\)，記作\(A\subseteqB\)。例如，\(A=\{1,2\}\)，\(B=\{1,2,3\}\)，則\(A\subseteqB\)。2.相等關(guān)系：如果\(A\subseteqB\)且\(B\subseteqA\)，那么稱集合\(A\)與\(B\)相等，記作\(A=B\)。比如\(A=\{x|x\)是偶數(shù)且\(1\ltx\lt5\}\)，\(B=\{2,4\}\)，則\(A=B\)。二、數(shù)理邏輯部分（一）命題邏輯1.命題的定義：具有確定真假意義的陳述句稱為命題。例如，"北京是中國(guó)的首都"是真命題，"地球是方的"是假命題。2.命題聯(lián)結(jié)詞否定聯(lián)結(jié)詞：\(\neg\)，如命題\(p\)："今天是晴天"，則\(\negp\)表示"今天不是晴天"。合取聯(lián)結(jié)詞：\(\land\)，命題\(p\)："小李會(huì)唱歌"，\(q\)："小李會(huì)跳舞"，\(p\landq\)表示"小李會(huì)唱歌且會(huì)跳舞"。析取聯(lián)結(jié)詞：\(\lor\)，\(p\)："小王是大學(xué)生"，\(q\)："小王是運(yùn)動(dòng)員"，\(p\lorq\)表示"小王是大學(xué)生或運(yùn)動(dòng)員"。蘊(yùn)含聯(lián)結(jié)詞：\(\to\)，\(p\)："如果天下雨"，\(q\)："地會(huì)濕"，\(p\toq\)表示"如果天下雨，那么地會(huì)濕"。等價(jià)聯(lián)結(jié)詞：\(\leftrightarrow\)，\(p\)："三角形三邊相等"，\(q\)："三角形三角相等"，\(p\leftrightarrowq\)表示"三角形三邊相等當(dāng)且僅當(dāng)三角形三角相等"。3.命題公式的真值表：通過(guò)對(duì)命題公式中命題變?cè)牟煌≈到M合，計(jì)算命題公式的真值，列出的表格稱為真值表。例如，對(duì)于命題公式\(p\lor\negp\)，其真值表如下：|\(p\)|\(\negp\)|\(p\lor\negp\)||::|::|::||\(0\)|\(1\)|\(1\)||\(1\)|\(0\)|\(1\)|4.命題公式的類型重言式（永真式）：真值表中最后一列全為\(1\)的命題公式。如\(p\lor\negp\)。矛盾式（永假式）：真值表中最后一列全為\(0\)的命題公式。如\(p\land\negp\)?？蓾M足式：真值表中最后一列至少有一個(gè)\(1\)的命題公式。例如\(p\landq\)，當(dāng)\(p=1\)，\(q=1\)時(shí)為真，其他情況為假，它是可滿足式。（二）謂詞邏輯1.謂詞與量詞謂詞：用來(lái)刻畫(huà)個(gè)體詞性質(zhì)或個(gè)體詞之間關(guān)系的詞。例如，"\(x\)是整數(shù)"，這里"是整數(shù)"就是一個(gè)謂詞，可記為\(P(x)\)。量詞全稱量詞：\(\forall\)，表示"對(duì)于所有的"。例如，\(\forallxP(x)\)表示"對(duì)于所有的\(x\)，\(x\)是整數(shù)"。存在量詞：\(\exists\)，表示"存在某個(gè)"。比如\(\existsxQ(x)\)表示"存在某個(gè)\(x\)，\(x\)是偶數(shù)"。2.謂詞公式的翻譯：將自然語(yǔ)言中的語(yǔ)句翻譯成謂詞公式。例如，"所有的人都要呼吸"，設(shè)\(M(x)\)：\(x\)是人，\(H(x)\)：\(x\)要呼吸，則可翻譯為\(\forallx(M(x)\toH(x))\)。三、圖論部分（一）圖的基本概念1.圖的定義：圖\(G\)由頂點(diǎn)集\(V\)和邊集\(E\)組成，記為\(G=(V,E)\)。例如，\(V=\{v_1,v_2,v_3\}\)，\(E=\{(v_1,v_2),(v_2,v_3)\}\)，這就是一個(gè)簡(jiǎn)單的圖。2.頂點(diǎn)的度數(shù)：與頂點(diǎn)\(v\)關(guān)聯(lián)的邊的數(shù)目，記為\(d(v)\)。在上述圖中，\(d(v_1)=1\)，\(d(v_2)=2\)，\(d(v_3)=1\)。3.圖的分類無(wú)向圖：邊沒(méi)有方向的圖。有向圖：邊有方向的圖。例如，\(V=\{v_1,v_2\}\)，\(E=\{(v_1,v_2)\}\)是無(wú)向邊，若\(E=\ltv_1,v_2\gt\)則是有向邊。（二）圖的連通性1.通路與回路通路：圖中頂點(diǎn)與頂點(diǎn)之間的邊的序列。例如，在圖\(G\)中，從\(v_1\)經(jīng)過(guò)\((v_1,v_2)\)到\(v_2\)，這就是一條通路?；芈罚浩瘘c(diǎn)和終點(diǎn)相同的通路。比如從\(v_1\)出發(fā)，經(jīng)過(guò)\((v_1,v_2)\)，\((v_2,v_3)\)，\((v_3,v_1)\)回到\(v_1\)，這就是一個(gè)回路。2.連通圖：若圖中任意兩個(gè)頂點(diǎn)之間都存在通路，則稱該圖是連通圖。例如，一個(gè)沒(méi)有孤立頂點(diǎn)且任意兩點(diǎn)都能通過(guò)邊相連的圖就是連通圖。（三）圖的應(yīng)用1.最短路徑問(wèn)題：在實(shí)際生活中，比如城市交通網(wǎng)絡(luò)中，求兩個(gè)城市之間的最短路線?？梢允褂玫辖芩固乩惴▉?lái)解決。例如，對(duì)于一個(gè)簡(jiǎn)單的交通圖，通過(guò)該算法可以找到從一個(gè)城市到另一個(gè)城市的最短路徑及最短距離。2.網(wǎng)絡(luò)流問(wèn)題：在物流配送等網(wǎng)絡(luò)中，要確定如何合理分配資源，使流量最大?？梢酝ㄟ^(guò)福特富爾克森算法等進(jìn)行求解。例如，在一個(gè)運(yùn)輸網(wǎng)絡(luò)中，利用該算法可以找到貨物從起點(diǎn)到終點(diǎn)的最大運(yùn)輸量及最優(yōu)運(yùn)輸方案。四、代數(shù)結(jié)構(gòu)部分（一）代數(shù)系統(tǒng)的定義1.運(yùn)算的定義：設(shè)\(A\)是一個(gè)非空集合，從\(A\timesA\)到\(A\)的一個(gè)映射稱為\(A\)上的一個(gè)二元運(yùn)算。例如，在整數(shù)集合\(Z\)上，加法運(yùn)算\(+\)就是一個(gè)二元運(yùn)算，對(duì)于任意的\(a,b\inZ\)，\(a+b\inZ\)。2.代數(shù)系統(tǒng)的組成：一個(gè)非空集合\(A\)以及定義在\(A\)上的若干個(gè)運(yùn)算\(f_1,f_2,\cdots,f_n\)所組成的系統(tǒng)稱為代數(shù)系統(tǒng)，記為\((A,f_1,f_2,\cdots,f_n)\)。比如\((Z,+)\)就是一個(gè)代數(shù)系統(tǒng)，其中\(zhòng)(Z\)是整數(shù)集，\(+\)是加法運(yùn)算。（二）群的定義與性質(zhì)1.群的定義：設(shè)\((G,\cdot)\)是一個(gè)代數(shù)系統(tǒng)，其中\(zhòng)(G\)是非空集合，\(\cdot\)是\(G\)上的二元運(yùn)算，如果滿足以下條件：封閉性：對(duì)于任意的\(a,b\inG\)，有\(zhòng)(a\cdotb\inG\)。結(jié)合律：對(duì)于任意的\(a,b,c\inG\)，有\(zhòng)((a\cdotb)\cdotc=a\cdot(b\cdotc)\)。單位元存在：存在\(e\inG\)，使得對(duì)于任意的\(a\inG\)，有\(zhòng)(a\cdote=e\cdota=a\)。逆元存在：對(duì)于任意的\(a\inG\)，存在\(a^{1}\inG\)，使得\(a\cdota^{1}=a^{1}\cdota=e\)。則稱\((G,\cdot)\)是一個(gè)群。例如，整數(shù)加法群\((Z,+)\)，滿足上述群的定義。2.群的性質(zhì)消去律：若\(a\cdotb=a\cdotc\)，則\(b=c\)；若\(b\cdota=c\cdota\)，則\(b=c\)。群中方程有唯一解：對(duì)于群\((G,\cdot)\)中的方程\(a\cdotx=b\)和\(y\cdota=b\)，在\(G\)中都有唯一解。（三）環(huán)與域的概念1.環(huán)的定義：設(shè)\((R,+,\cdot)\)是一個(gè)代數(shù)系統(tǒng)，如果滿足：\((R,+)\)是一個(gè)阿貝爾群（加法交換群）。\((R,\cdot)\)是一個(gè)半群，即滿足結(jié)合律。乘法對(duì)加法滿足分配律，即對(duì)于任意的\(a,b,c\inR\)，有\(zhòng)(a\cdot(b+c)=a\cdotb+a\cdotc\)和\((b+c)\cdota=b\cdota+c\cdota\)。則稱\((R,+,\cdot)\)是一個(gè)環(huán)。例如，整數(shù)環(huán)\((Z,+,\cdot)\)，其中加法和乘法滿足上述環(huán)的定義。2.域的定義：設(shè)\((F,+,\cdot)\)是一個(gè)環(huán)，如果\((F\setminus\{0\},\cdot)\)是一個(gè)阿貝爾群，則稱\((F,+,\cdot)\)是一個(gè)域。例如，有理數(shù)域\((Q,+,\cdot)\)，其中\(zhòng)(Q\)是有理數(shù)集，加法和乘法運(yùn)算滿足域的定義。五、綜合練習(xí)題目及解答（一）集合論題目1.已知\(A=\{a,b,c,d\}\)，\(B=\{c,d,e\}\)，求\(A\cupB\)，\(A\capB\)，\(AB\)，\(BA\)。解答：\(A\cupB=\{a,b,c,d,e\}\)（將\(A\)和\(B\)中的所有元素合并在一起，去除重復(fù)元素）。\(A\capB=\{c,d\}\)（\(A\)和\(B\)中共同的元素）。\(AB=\{a,b\}\)（屬于\(A\)但不屬于\(B\)的元素）。\(BA=\{e\}\)（屬于\(B\)但不屬于\(A\)的元素）。2.設(shè)全集\(U=\{1,2,3,4,5,6,7,8\}\)，\(A=\{2,4,6\}\)，\(B=\{1,3,5,7\}\)，求\(\overline{A}\)，\(\overline{B}\)，\(\overline{A\cupB}\)，\(\overline{A\capB}\)。解答：\(\overline{A}=UA=\{1,3,5,7,8\}\)（全集中不屬于\(A\)的元素）。\(\overline{B}=UB=\{2,4,6,8\}\)（全集中不屬于\(B\)的元素）。\(A\cupB=\{1,2,3,4,5,6,7\}\)，則\(\overline{A\cupB}=\{8\}\)（全集中不屬于\(A\cupB\)的元素）。\(A\capB=\varnothing\)，所以\(\overline{A\capB}=U=\{1,2,3,4,5,6,7,8\}\)（全集中不屬于空集的元素就是全集本身）。（二）數(shù)理邏輯題目1.求命題公式\((p\landq)\to\negr\)的真值表。解答：|\(p\)|\(q\)|\(r\)|\(p\landq\)|\(\negr\)|\((p\landq)\to\ne