离散数学试卷（六）
则 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
