【文章內(nèi)容簡(jiǎn)介】 1. 設(shè)R 是集合A上的二元關(guān)系，如果關(guān)系R同時(shí)具有 性、對(duì)稱性和 性，則稱R是等價(jià)關(guān)系。2. 命題公式G=（P217。Q）174。R，則G共有 個(gè)不同的解釋；把G在其所有解釋下所取真值列成一個(gè)表，稱為G的 ；解釋（216。P，Q，216。R）或（0，1，0）使G的真值為 。3. 設(shè)G=（P，L）是圖，如果G是連通的，并且 ，則G是樹。如果根樹T的每個(gè)點(diǎn)v最多有兩棵子樹，則稱T為 。[單項(xiàng)選擇題]（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）1. 由集合運(yùn)算定義，下列各式正確的有（ ）。A． X205。X200。Y 2. 設(shè)R1，R2是集合A={a，b，c，d}上的兩個(gè)關(guān)系，其中R1={（a，a），（b，b），（b，c），（d，d）}，R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，則R2是R1的（ ）閉包。A．自反 B．對(duì)稱 C．傳遞 D．以上都不是3. 設(shè)G是由5個(gè)頂點(diǎn)組成的完全圖，則從G中刪去（ ）條邊可以得到樹。A．4 B．5 C．6 D．10[計(jì)算題]1. 化簡(jiǎn)下式：（ABC）200。（（AB）199。C）200。（A199。BC）200。（A199。B199。C）2. 通過(guò)求主析取范式判斷下列命題公式是否等值。（1）（P217。Q）218。（216。P217。Q217。R）；（2）（P218。（Q217。R））217。（Q218。（216。P217。R））；3. 求圖中A到其余各頂點(diǎn)的最短路徑，并寫出它們的權(quán)。 B 7 C 1 2 A 2 5 3 D4 6 E 1 F[證明題]1. 利用基本等價(jià)式證明下面命題公式為恒真公式。（（P174。Q）217。（Q174。R））174。（P174。R）2. 用形式演繹法證明：{P174。Q， R174。S，P218。R }蘊(yùn)涵Q218。S。試題答案及評(píng)分標(biāo)準(zhǔn)[填空題] 自反；傳遞 8；真值表；1 無(wú)回路；二叉樹[單項(xiàng)選擇題]（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中） A B C[計(jì)算題]1. 解： （ABC）200。（（AB）199。C）200。（A199。BC）200。（A199。B199。C）=（A199。~B199。~C）200。（A199。~B199。C）200。（A199。B199。~C）200。（A199。B199。C） =（（A199。~B）199。（~C200。C））200。（（A199。B）199。（~C200。C）） =（（A199。~B）199。E）200。（（A199。B）199。E） E為全集 =（A199。~B）200。（A199。B） = A199。（~B200。B） = A199。E = A 2. 解： （P217。Q）218。（216。P217。Q217。R）219。（P217。Q217。（216。R218。R））218。（216。P217。Q217。R）219。（P217。Q217。216。R）218。（P217。Q217。R）218。（216。P217。Q217。R）219。 m6218。m7218。m3 219。 m3218。m6218。m7 （P218。（Q217。R））217。（Q218。（216。P217。R））219。（P217。Q） 218。（Q217。R）218。（P217。216。P217。R）218。（216。P217。 Q 217。R） （分配律）219。（P217。Q217。（216。R218。R）） 218。（（216。P218。P）217。Q217。R）218。（216。P217。 Q 217。R）219。（P217。Q217。216。R） 218。（P217。Q217。R） 218。（216。P217。Q217。R）218。（P217。Q217。R）218。（216。P217。 Q 217。R）219。 m6218。m7218。m3218。m7218。m3219。 m3218。m6218。m7 由此可見(jiàn) （P217。Q）218。（216。P217。Q217。R）219。 （P218。（Q217。R））217。（Q218。（216。P217。R））3. 解： A到B的最短路徑為AB，權(quán)為1；A到E的最短路徑為ABE，權(quán)為3；A到F的最短路徑為ABEF，權(quán)為4；A到C的最短路徑為ABEFC，權(quán)為7；A到D的最短路徑為ABEFCD，權(quán)為9。[證明題]1. 證明： （（P174。Q）217。（Q174。R））174。（P174。R） 219。（（216。P218。Q）217。（216。Q218。R））174。（216。P218。R） 219。216。（（216。P218。Q）217。（216。Q218。R））218。（216。P218。R）219。（P217。216。Q）218。（Q217。216。R）218。216。P218。R 219。（（P217。216。Q）218。216。P ）218。（（Q217。216。R）218。R）219。（1217。（216。Q218。216。P ））218。（（Q218。R）217。1）219。 216。Q218。216。P218。Q218。R 219。 （216。Q218。Q） 218。216。P 218。R219。 1 218。216。P 218。R219。 1 2. 證明：（1） P218。R 規(guī)則P （2） 216。R174。P 規(guī)則Q ，根據(jù)（1） （3） P174。Q 規(guī)則P （4） 216。R 174。Q 規(guī)則Q，根據(jù)（2）（3） （5） 216。Q174。R 規(guī)則Q，根據(jù)（4） （6） R174。S 規(guī)則P （7） 216。Q174。S 規(guī)則Q，根據(jù)（5）（6）（8） Q218。S 規(guī)則Q ，根據(jù)（7） 三、 綜合練習(xí)及解答（一）填空題集合的表示方法有兩種： 法和 法。請(qǐng)把“大于3而小于或等于7的整數(shù)集合”用任一種集合的表示方法表示出來(lái)A={ }。 A，B是兩個(gè)集合，A={1，2，3，4}，B={2，3，5}，則BA= ，r（B）r（A）= ，r（B）的元素個(gè)數(shù)為 。 設(shè)，則從A到B的所有映射是 。 設(shè)命題公式，則使公式G為假的解釋是 、 和 。設(shè)G是完全二叉樹，G有15個(gè)點(diǎn)，其中8個(gè)葉結(jié)點(diǎn)，則G的總度數(shù)為 ，分枝點(diǎn)數(shù)為 。全集E={1，2，3，4，5}，A={1，5}，B={1，2，3，4}，C={2