3．設p，q 的真值為0，r，s的真值為1，則
的真值4．公式的主合取正規化為
5．若解釋i的論域d僅包含乙個元素，則在i下真值為
1. 在自然推理系統p中構造下面推理的證明：只要a曾到過受害者房間並且11點以前沒離開，a就是**嫌犯。
a曾到過受害者房間。 如果a在11點以前離開，看門人會看見他。看門人沒有看見他。
所以，a是**嫌犯。
設p：a到過受害者房間，q：a在11點以前離開，r：a是**嫌犯，s：看門人看見過a
則前提 結論
證明① 前提引入
前提引入
拒取式前提引入
合取引入
⑥ 前提引入
假言推理
2．設a=，r為aa上的二元關係,〈a，b〉，〈c，d〉aa ,〈a，b〉r〈c，d〉a + b = c + d，證明r為等價關係。
a+b=a+b
∴r∴r是自反的
任意的,∈a×a
設r，則a+b=c+d
∴c+d=a+b ∴r
∴r是對稱的
任意的,,∈a×a
若r,r
則a+b=c+d,c+d=x+y
∴a+b=x+y ∴r
∴r是傳遞的
∴r是 a×a上的等價關係
3證明：迴圈群的任何子群必定也是迴圈群。
設是迴圈群,g=(a)，設是的子群。且，則存在最小正整數m，使得：，對任意，必有
故： 即：，所以，任m使的最小正整數，且，所以r=0即：這說明s中任意元素是的乘冪。 所以是以為生成元的迴圈群。
4設有a、b、c、d、e、f、g七個人，他們分別會講的語言如下：a：英，b：
漢、英，c：英、西班牙、俄，d：日、漢，e：
德、西班牙， f：法、日、俄，g：法、德，能否將這七個人的座位安排在圓桌旁，使得每個人均能與他旁邊的人交談？
用a,b,c,d,e,f,g 7個結點表示7個人，若兩人能交談可用一條無向邊鏈結，所得無向圖為此圖中的hamilton迴路即是圓桌安排座位的順序。hamilton迴路為a b d f g e c a。
離散數學 複習
第1章命題邏輯 本章重點 命題與聯結詞，公式與解釋，真值表，公式的型別及判定,主 析取 合取 正規化，命題邏輯的推理理論.一 重點內容 1.命題 命題表述為具有確定真假意義的陳述句。命題必須具備二個條件 其一，語句是陳述句 其二，語句有唯一確定的真假意義.2.六個聯結詞及真值表 否定聯結詞，p是命題...
離散數學複習
例題1 設是群，是的子群，在g上定義關係r r 證明 r是集合g上的等價關係。證明 即證明r為自反 對稱和傳遞關係。1 證自反 是子群，則h中必然存在么元，設為e。則ag，eh，a a e，所以 r，所以，r為自反關係。2 證對稱 a,bg,若r，則hh，a b h，因為是子群，則h必然具有逆元h ...
離散數學複習指導
第一部分數理邏輯 第七章二元關係 9.1二元運算及其性質 11.1格的定義與性質 第五部分圖論 命題邏輯 一至三章 1 求命題公式的真值表 知識 p7表1.1 例題 p9例1.8 2等值演算 知識 p17基本等值式 例題 p19例2.3 3 判斷公式的型別 知識 p10定義1.10 例題 用真值表法...