离散数学模拟习题与解析 (6)(2)

离散数学试卷（六）

则 a?a?b?b?a?b b?a ③传递性：a?b,b?c则： a?c?(a?b)?ca?b即a?b?a?a?(b?c) 结合律?a?b b?c即b?c?b?a a?b即a?b?a?a?c

（2）?x,y?L在L中存在{x,y}的下（上）确界

设x,y?L则：x?y?inf{x,y}

事实上：x?(x?y)?(x?x)?y?x?y ?x?y?x同理可证:x?y?y

若{x , y }有另一下界c，则c?(x?y)?(c?x)?y?c?y?c

?c?x?y ?x?y是{x , y }最大下界，即x?y?inf{x,y}

同理可证上确界情况。 四、14% 解：函数表为：

x1x2 x3 E(x1,x2,x3) 0 0 0 0 1 1 1 1 析取范式：

0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1

E(x1,x2,x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3) 40

离散数学试卷（六）

合取范式：E(x1,x2,x3)?(x1?x?2?x3)?(x1?x2?x3)?(x1?x2?x3)

五、10%

解： 用库斯克（Kruskal）算法求产生的最优树。算法为：

w(v1,v7)?1w(v7,v2)?4w(v7,v3)?9w(v3,v4)?3w(v4,v5)?17w(v1,v6)?23选e1?v1v7选e2?v7v2选e3?v7v3选e?v3v4选e?v4v5选e?v1v6

结果如图：

树权C(T)=23+1+4+9+3+17=57（万元）即为总造价

41

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学模拟习题与解析 (6)(2)在线全文阅读。