【正文】 ={（1，1），（3，1），（3，2），（4，3）} ={（2，1），（4，3）} 解： R1和R2的關(guān)系圖略。 由關(guān)系圖可知，R1是等價關(guān)系。R1不同的等價類有兩個，即{a，b}和{c，d}。由于R2不是自反的，所以R2不是等價關(guān)系。解 ：（1） 真值表P Q216。P P217。216。P （P217。216。P）171。Q0 01 0 10 11 0 01 00 0 11 10 0 0 因此公式（1）為可滿足。（2） 真值表P QP174。Q 216。（P174。Q） 216。（P174。Q）217。Q0 01 0 00 11 0 01 00 1 01 11 0 0 因此公式（2）為恒假。 （3） 真值表P Q RP174。Q Q174。R P174。R （（P174。Q）217。（Q174。R））174。（P174。R）0 0 0 1 1 1 10 0 1 1 1 1 10 1 0 1 0 1 10 1 1 1 1 1 11 0 0 0 1 0 11 0 1 0 1 1 11 1 0 1 0 0 11 1 1 1 1 1 1 因此公式（3）為恒真。 4. 解： $x（F（x）218。G（x）） 219。 （F（2）218。G（2））218。（F（3）218。G（3））218。（F（6）218。G（6）） 219。 （1218。0）218。（1218。0）218。（0218。1） 219。 1 5. 解： V1 V31 2① ② ④ ⑤U 2 3 V V2 ③ 1 V4 從U到V的最短路為U→V1→V2→V4→V3→V。最短路權(quán)值為9。 圖中圓圈中的數(shù)字為使用迪克斯特拉算法添加邊的次序。解： （（A200。B200。C）199。（A200。B））（（A200。（BC））199。A）=（A200。B） A （利用兩次吸收律） =（A200。B）199。~ A =（A199。~ A）200。（B199。~ A） = f200。（B199。~ A）= B A 解： R={（1，1），（1，2），（1，3），（2，1），（2，2），（3，1）} R的關(guān)系圖為 1 1 2 2 3345關(guān)系矩陣MR= 1 1 11 1 01 0 00 0 00 0 0 解： （A，163。）的哈斯圖為： e b c d a a為A的極小元，也是最小元； e為A的極大元，也是最大元。 解： 216。（P218。Q）171。（P217。Q）219。（216。（P218。Q）174。（P217。Q））217。（（P217。Q）174。216。（P218。Q））219。（（P218。Q）218。（P217。Q））217。（（216。P218。216。Q）218。（216。P217。216。Q）））219。（P218。Q）217。（216。P218。216。Q）上面結(jié)果為合取范式。利用217。對218。分配得：（P218。Q）217。（216。P218。216。Q） 219。（P217。216。P）218。（P217。216。Q）218。（Q217。216。P）218。（Q217。216。Q） 219。（P217。216。Q）218。（Q217。216。P）上面結(jié)果為析取范式。解： xy（F（x，y）174。F（f（x），f（y）））219。 x（（F（x，2）174。F（f（x），f（2）））217。（F（x，3）174。F（f（x），f（3））））219。 （F（2，2）174。F（f（2），f（2）））217。（F（2，3）174。F（f（2），f（3）））217。（F（3，2）174。F（f（3），f（2）））217。（F（3，3）174。F（f（3），f（3））） 219。（0174。1）217。（0174。1）217。（1174。0）217。（1174。0） 219。 0 1解：首先將本題用權(quán)圖來描述，于是求解此題便成為求權(quán)圖中的最優(yōu)支撐樹問題， 按克魯斯卡爾算法，下圖為求解最優(yōu)支撐樹的過程： （a） （b） （c） （d） （e） 連接5個城市的造價最低的鐵路網(wǎng)總造價為24（百萬元）。 （四）證明題 證明： 證明： （1） 規(guī)則P（2） 規(guī)則P（3） 規(guī)則Q，根據(jù)（1）、（2）和基本蘊涵式（12）（4） 規(guī)則P（5） 規(guī)則Q，根據(jù)（3）、（4）和基本蘊涵式（11） （6） 規(guī)則P（7） 規(guī)則Q，根據(jù)（5）、（6）和基本蘊涵式（12）（8） 規(guī)則P（9） 規(guī)則Q，根據(jù)（7）、（8）和基本蘊涵式（10） 證明： （AB）C=（A199。~B）199。~C = A199。（~B199。~C） = A199。~（B200。C） = A（B200。C） 證明： xy（F（x）174。G（y））=x（F（x）174。y G（y）） = x（216。F（x）218。y G（y）） = x（216。F（x））218。y G（y） = 216。$xF（x）218。y G（y） = $xF（x）174。yG（y）25