離散數(shù)學(xué)習(xí)題課

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

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

3、1, a2, , ak 結(jié)論：結(jié)論：b 熟練掌握判斷推理是否正確的方法（如真值表法、熟練掌握判斷推理是否正確的方法（如真值表法、構(gòu)造證明法構(gòu)造證明法等）等） 牢記牢記各條推理定律（內(nèi)容與名稱）各條推理定律（內(nèi)容與名稱） 掌握附加前提證明法及歸謬法掌握附加前提證明法及歸謬法 1已知命題公式a 中含 3 個命題變項p, q, r，并知道它的成真賦值為001, 010, 111, 求 a 的主析取范式和主合取范式. 答案 a 的主析取范式為 m1 m2 m7 a 的主合取范式為 m0 m3 m4 m5 m6 二、練習(xí)題二、練習(xí)題2在以下各聯(lián)結(jié)詞集中各求一個公式與在以下各聯(lián)結(jié)詞集中各求一個公式與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、設(shè)計一個符合如下要求的室內(nèi)照明控制線路：在房間的、設(shè)計一個符合如下要求的室內(nèi)照明控制線路：在房間的門外、門內(nèi)及床頭分別裝有控制同一個電燈門外、門內(nèi)及床頭分別裝有控制同一個電燈f f的的3 3個開關(guān)個開關(guān)a a、b b、c c，當(dāng)且僅當(dāng)一個開關(guān)

5、的搬鍵向上或，當(dāng)且僅當(dāng)一個開關(guān)的搬鍵向上或3 3個開關(guān)的搬鍵向上時電個開關(guān)的搬鍵向上時電燈亮。證明燈亮。證明f f的邏輯關(guān)系可表示為的邏輯關(guān)系可表示為a a (b(b c)c)。分析：設(shè)分析：設(shè)a、b、c分別表示分別表示3個開關(guān)狀態(tài)的命題變項，且開個開關(guān)狀態(tài)的命題變項，且開關(guān)的搬鍵向上時對應(yīng)的命題變項的真值為關(guān)的搬鍵向上時對應(yīng)的命題變項的真值為1，開關(guān)的搬鍵向，開關(guān)的搬鍵向下時對應(yīng)的命題變項的真值為下時對應(yīng)的命題變項的真值為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 結(jié)論：p （2） 前提：qr, pr 結(jié)論：qp 解 （1）答案：不正確）答案：不正確 驗證答案，需將推理形式結(jié)構(gòu)改為另一種形式驗證答案，需將推理形式結(jié)構(gòu)改為另一種形式 ( pq ) q p (* *) 只需證明只需證明 (* *)不是重言式不是重言式 方法一方法一 等值演算等值演算 ( pq) q p (p q) q) p ( p q) q p

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