離散數學習題課

1、第一章第一章 習題課習題課一、一、 本章的主要內容及要求本章的主要內容及要求 1 基本內容基本內容 等值式與等值演算等值式與等值演算 基本的等值式（基本的等值式（24個公式）個公式） 主析取與主合取范式主析取與主合取范式 聯結詞全功能集聯結詞全功能集 判斷推理是否正確的不同方法判斷推理是否正確的不同方法真值表法真值表法等值演算法等值演算法 主析取范式法主析取范式法 構造證明法構造證明法2. 要求要求 深刻理解等值式的概念深刻理解等值式的概念 牢記基本等值式的名稱及內容牢記基本等值式的名稱及內容 了解簡單析取式、簡單合取式、析取范式、合取范式了解簡單析取式、簡單合取式、析取范式、合取范式的概念的

2、概念 深刻理解極小項、極大項的概念、名稱及下角標與成深刻理解極小項、極大項的概念、名稱及下角標與成真、成假賦值的關系，并理解主析取范式與極小項的真、成假賦值的關系，并理解主析取范式與極小項的關系關系 熟練掌握求主范式的方法（真值表）熟練掌握求主范式的方法（真值表） 熟練掌握熟練掌握用公式的主范式求公式的成真、成假賦值及用公式的主范式求公式的成真、成假賦值及判斷公判斷公式的類型及簡單應用式的類型及簡單應用 會將任何公式化成任何聯結詞完備集中的公式會將任何公式化成任何聯結詞完備集中的公式 理解并記住推理形式結構的如下形式：理解并記住推理形式結構的如下形式： (a1 a2 ak)b 前提：前提： a

3、1, a2, , ak 結論：結論：b 熟練掌握判斷推理是否正確的方法（如真值表法、熟練掌握判斷推理是否正確的方法（如真值表法、構造證明法構造證明法等）等） 牢記牢記各條推理定律（內容與名稱）各條推理定律（內容與名稱） 掌握附加前提證明法及歸謬法掌握附加前提證明法及歸謬法 1已知命題公式a 中含 3 個命題變項p, q, r，并知道它的成真賦值為001, 010, 111, 求 a 的主析取范式和主合取范式. 答案 a 的主析取范式為 m1 m2 m7 a 的主合取范式為 m0 m3 m4 m5 m6 二、練習題二、練習題2在以下各聯結詞集中各求一個公式與在以下各聯結詞集中各求一個公式與a=

4、q a= q 等值。等值。 (1) , (2) , (3) , (4) (5) 解解: (1)aq qq 滿足要求滿足要求(1) (2)a( q) q 滿足要求滿足要求(3) (3)a( q q) 滿足要求滿足要求(2) (4)a q q (q q) (q q) 滿足要求滿足要求(4) (5)a qq (q q) (q q) 滿足要求滿足要求(5)3 3、設計一個符合如下要求的室內照明控制線路：在房間的、設計一個符合如下要求的室內照明控制線路：在房間的門外、門內及床頭分別裝有控制同一個電燈門外、門內及床頭分別裝有控制同一個電燈f f的的3 3個開關個開關a a、b b、c c，當且僅當一個開關

5、的搬鍵向上或，當且僅當一個開關的搬鍵向上或3 3個開關的搬鍵向上時電個開關的搬鍵向上時電燈亮。證明燈亮。證明f f的邏輯關系可表示為的邏輯關系可表示為a a (b(b c)c)。分析：設分析：設a、b、c分別表示分別表示3個開關狀態(tài)的命題變項，且開個開關狀態(tài)的命題變項，且開關的搬鍵向上時對應的命題變項的真值為關的搬鍵向上時對應的命題變項的真值為1，開關的搬鍵向，開關的搬鍵向下時對應的命題變項的真值為下時對應的命題變項的真值為0，于是有：，于是有：f ( a b c)( a b c) (a b c) (a b c) ( a ( b c) (b c) (a ( b c) (b c) ( a (b

6、c ) (a ( b c) (b c) ( a (b c ) (a (b c) ( b c) ( a (b c ) (a (b c ) a (b c) 4 用不同的方法驗證下面推理是否正確 . 對于正確的推理還要給出證明. （1） 前提：pq, q 結論：p （2） 前提：qr, pr 結論：qp 解 （1）答案：不正確）答案：不正確 驗證答案，需將推理形式結構改為另一種形式驗證答案，需將推理形式結構改為另一種形式 ( pq ) q p (* *) 只需證明只需證明 (* *)不是重言式不是重言式 方法一方法一 等值演算等值演算 ( pq) q p (p q) q) p ( p q) q p

7、( p q) ( q q) p p q 易知易知10是成假賦值，故是成假賦值，故(* *)不是重言式，所以推理不正確不是重言式，所以推理不正確. 方法二方法二 主析取范式法主析取范式法 經過演算后可知經過演算后可知 (* *) m0 m1 m3 未含未含 m2, 故故(* *)不是重言式不是重言式. 方法三方法三 真值表法真值表法 (* *)的真值表為的真值表為: : p q ( pq) q p 0 0 0 1 1 0 1 1 1 1 0 1 結論（不正確）是對的結論（不正確）是對的 方法四方法四 直接觀察出直接觀察出 10 是成假賦值是成假賦值 解（解（2）答案：推理正確）答案：推理正確 方法一方法一 真值表法（自己做）真值表法（自己做） 方法二方法二 等值演算法（自己做）等值演算法（自己做） 方法三方法三 主析取