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