一、范式 1、的主合取范式為 。2、 利用主析取范式，求公式的類型。 解、 它無成真賦值，所以為矛盾式。3、 求命題公式(PQ)(PR)的主合取范式。 解：(PQ)(PR)（(PQ)(PR)）（(PR)(PQ)）（(PQ)(PR)）（(PR)(PQ)）(PQ)(PR)(PR)（QP）（QR）(PQR)(PQR)（PQR）（PQR）M1M3M4M54、 設命題公式G = (PQ)(Q(PR), 求G的主析取范式。 G = (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(QP)(QR)= (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)= (PQR)(PQR)(PQR)(PQR)(PQR)= m3m4m5m6m7 = S(3, 4, 5, 6, 7).5、 通過求主析取范式判斷下列命題公式是否等價：(1) G = (PQ)(PQR) (2) H = (P(QR)(Q(PR) G(PQ)(PQR)(PQR)(PQR)(PQR)m6m7m3 (3, 6, 7)H = (P(QR)(Q(PR)(PQ)(QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m6m3m7 (3, 6, 7) G,H的主析取范式相同，所以G = H.6、用等值演算法和真值表法判斷公式的類型。 （1）等值演算法（2）真值表法P QA1 1111111 0010010 1100010 011111所以A為重言式。7、設命題A1，A2的真值為1，A3，A4真值為0，求命題的真值。（5分）8、公式的主合取范式是 二、推理證明1、敘述并證明蘇格拉底三段論解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號化：F（x）：x是一個人。G（x）：x要死的。A：蘇格拉底。命題符號化為x（F（x）G（x），F（a）G（a）證明：（1）x(F(x)G(x) P（2）F(a)G(a) T(1),US（3）F(a) P（4）G(a) T(2)(3),I2、設論域D=a , b , c，求證：。 3、用反證法證明。 4、用CP規則證明。 5、演繹推理：所有的有理數都是實數，所有的無理數也是實數，虛數不是實數。因此，虛數既不是有理數，也不是無理數。6、利用形式演繹法證明：AB, CB, CD蘊涵AD。(1) AD(附加)(2) ABP(3) BQ(1)(2)(4) CBP(5) BCQ(4)(6) CQ(3)(5)(7) CDP(8) DQ(6)(7)(9) ADD(1)(8)所以 AB, CB, CD蘊涵AD.7、P（附加前提）TIPTITITIPTICP8、P（附加前提）USPUSTIUGCP9、所有的舞蹈者都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度。證明：設P(x)：x 是個舞蹈者； Q(x) ：x很有風度； S(x)：x是個學生； a：王華上述句子符號化為：前提：、 結論： 3分PPUSTI TITITIEG10、符號化語句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結論。解： 證明：PESTITIPUSTITEUSUSTIUG11、符號化語句：“有些病人相信所有的醫生，但是病人都不相信騙子，所以醫生都不是騙子”。并推證其結論 解：F(x)：x是病人，G(x)：x是醫生，H(x)：x是騙子，L(x,y)：x相信y符號化：前提：結論：PESTITIPUSTITEUSUSTIUG3、 集合1、已知A、B、C是三個集合，證明A(BC)=(AB)(AC)證明：x A（BC） x Ax（BC） x A（xBxC）（ x AxB）（x AxC） x（AB）x AC x（AB）（AC） A（BC）=（AB）（AC）2、1設 （N：自然數集，E+ 正偶數） 則 0，1，2，3，4，6； 。3、A，B，C表示三個集合，文圖中陰影部分的集合表達式為 A B C 。4、= 。5、集合的冪集= 。并搜集為 ，交搜集為 6、 4、 二元關系1、 設A=2，3，4，5，6上的二元關系，則R= , （列舉法）。R的關系矩陣MR= 。2、設集合A= a ,b , c , d 上關系R= , , , 要求 1、寫出R的關系矩陣和關系圖。（4分） 2、用矩陣運算求出R的傳遞閉包。（6分）； 關系圖2、 t (R)= , , , , , , , , 。3、設R和S是集合Aa, b, c, d上的關系，其中R(a, a),(a, c),(b, c),(c, d), S(a, b),(b, c),(b, d),(d, d).(1) 試寫出R和S的關系矩陣；(2) 計算RS, RS, R1, S1R1. 解、 (1) (2)RS(a, b),(c, d),RS(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d), R1(a, a),(c, a),(c, b),(d, c),S1R1(b, a),(d, c). 4、設Aa，b，c，d，R是A上的二元關系，且R，求r(R)、s(R)和t(R)。解 r(R)RIA，s(R)RR-1，R2，R3，R4，R2t(R)，5、設R是集合A = a, b, c, d. R是A上的二元關系, R = (a,b), (b,a), (b,c), (c,d),(1) 求出r(R), s(R), t(R)；(2) 畫出r(R), s(R), t(R)的關系圖.(1) r(R)RIA(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R)RR1(a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R)RR2R3R4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)；(2)關系圖:6、已知A=1,2,3,4,5和R=,，求r(R)、s(R)和t(R)。解：r(R)=,s(R)=,t(R)=,7、集合上的關系，寫出關系矩陣，畫出關系圖并討論R的性質。 解： R的關系圖為 R是自反、對稱的。8、設A=，1，1，3，1，2，3則A上包含關系“”的哈斯圖為9、設S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“”為S上整除關系，問：（1）偏序集的Hass圖如何？（2）若，求的極小元、最小元、極大元、最大元，上界，上確界，下界，下確界=,，,covS=, ,10、設A=1，2，3，4，5，A上的偏序關系為求A的子集3，4，5和1，2，3，的上界，下界，上確界和下確界，極大、極小元，最大最小元。11、集合上的偏序關系為整除關系。設，試畫出的哈斯圖，并求A，B，C的最大元素、極大元素、下界、上確界。 解：的哈斯圖為集合最大元極大元下界上確界A無24，36無無B12126，2，312C66無612、設集合A1, 2, 4, 6, 8, 12，R為A上整除關系。(1) 畫出半序集(A,R)的哈斯圖；(2) 寫出A的最大元，最小元，極大元，極小元；(3) 寫出A的子集B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.解 (1) (2) 無最大元，最小元1，極大元8, 12; 極小元是1.(3) B無上界，無最小上界。下界1, 2; 最大下界2.13、設集合A1, 2, 3, 4, 6, 8, 9, 12，R為整除關系。（1）畫出半序集(A,R)的哈斯圖；（2）寫出A的子集B = 3,6,9,12的上界，下界，最小上界，最大下界；（3）寫出A的最大元，最小元，極大元，極小元。 (1)(2) B無上界，也無最小上界。下界1, 3; 最大下界是3.(3) A無最大元，最小元是1，極大元8, 12, 90+; 極小元是1.14、設A=a,b,c,d，A上的二元關系R=,，求R所誘導的等價關系，并求出等價關系中各元素的等價類。15、設X=1,2,3,4,5，X上的關系R= , , , , ，求R所誘導的等價關系，劃分等價類并求秩16、設A=1，2，3，4，S=1，2，3，4，為A的一個劃分，求1）由S導出的等價關系。2）求五、圖論1、已知：D=，V=1,2,3,4,5，E=,，求D的鄰接距陣A和可達距陣P。解：D的鄰接距陣A和可達距陣P如下：01010111110010011111A=00011P=11111000000000010000111112、給定圖G如圖所示，（1）G中長度為4的路有幾條？其中有幾條回路？（2）寫出G的可達矩陣。3、如下圖所示的賦權圖表示某七個城市及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。解： 用庫斯克（Kruskal）算法求產生的最優樹。算法略。結果如圖：樹權C(T)=23+1+4+9+3+17=57即為總造價。4、求圖的可達性矩陣，并求圖的強分圖，弱分圖，單向分圖 5、下圖所示帶權圖中最優投遞路線并求出投遞路線長度（郵局在D點）。 圖中奇數點為E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF復制道路EG、GF，得圖G，則G是歐拉圖。由D開始找一條歐拉回路：DEGFGEBACBDCFD。道路長度為：35+8+20+20+8+40+30+50+19+6+12+10+23=2816、求帶權圖G中的最優投遞路線。郵局在v1點。解：圖中有4個奇數結點，（1） 求任兩結點的最短路再找兩條道路使得它們沒有相同的起點和終點，且長度總和最短：（2） 在原圖中復制出，設圖G，則圖G中每個結點度數均為偶數的圖G存在歐拉回路，歐拉回路C權長為43。7、已知二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案：二叉樹形態 8、畫出與下圖所示的森林相對應的二叉樹，并指出森林中的葉子結點在二叉樹中具有什么特點。已知有向圖G如下所示，根據迪杰斯特拉算法求頂點v0到其他頂點的最短距離。（給出求解過程）答案：終點從v0到各終點的d值和最短路徑的求解過程i=1i=2i=3i=4v112 (v0,v1)12 (v0,v1)7 (v0,v4,v1)v24 (v0,v2)v39 (v0,v3)8 (v0,v2,v3)7 (v0,v4,v3)7 (v0,v4,v3)v45 (v0,v4)5 (v0,v4)vjv2v4v1v3sv0,v2v0,v4v0,v4,v1v0,v4,v36、已知圖G如下所示，根據Prim算法，構造最小生成樹。（要求給出生成過程）答案：prim算法求最小生成樹如下：已知圖G如下，根據克魯斯卡爾算法求圖G的一棵最小生成樹。（要求給出構造過程）答案：kruskal算法的最小生成樹 12、已知圖G如下所示，求從頂點a到其余各頂點的最短路徑。（給出求解過程）543223356abdfce答案：終點最短路徑求解過程b6