2011年自考離散數學第一章命題演算
瀏覽
收藏
本章的重點是命題概念及其表示、命題公式化簡、主范式及其互化、P規則、T規則以及CP規則。難點是推理理論及應用。
一、命題概念(領會)
學習本章首先要深刻理解命題的概念。理解原子命題與復合命題的關系，在了解復合命題的基礎上，理解聯結詞的定義。
命題：具有唯一真值的陳述句稱為命題，又簡稱語句。注意，這里有兩個條件，首先它是一個陳述句，其次，它具有唯一的一個真值。
真值：就是語句為真或假的性質。一個語句的真值可以為真也可以為假。真值不是說該語句的值必為真。
任一命題必有其真值，也稱這個命題的值。既然是命題了，那它必有一個確定的真值，不管這個真值為真還是為假。當一個陳述句能夠分辯其值的真假時(也就是說，總可以肯定是其中的某一個)，它就是命題，即使我們不知道它是真還是假。
另外要理解命題常量、命題變元及指派的含義。
復合命題就是一些原子命題經過一些聯結詞復合而成的命題。常用的聯結詞有：(1)否定、(2)合取、(3)析取、(4)條件、(5)雙條件
復合命題與聯系詞是密切相關的，不包含聯結詞的命題就是原子命題，至少包含一個聯結詞的命題才是復合命題。
復合命題的真值只取決于構成它們的各原子命題的真值，而與它們的內容含義無關。對聯結詞所聯結的兩原子命題之間有無關系無關。(這一條很重要，因為一個命題用自然語言表達時，我們往往會受到自然邏輯的影響，比如"我如果不上班，那么天下雨"這種命題，在自然的邏輯里，是不成立的，一個人不上班怎么會導致天下雨呢? 但是在這里，這個復合命題的值實際上是由兩個原子命題的真值決定的，與它的含義無關，這個復合命題是|P->Q ,前一個原子命題的真值為假，后一命題值為真，根據條件的定義，這個復合命題值為真)
∧、∨、←→具有對稱性，|、→無對稱性，(教材提示，也可用iff表示雙向箭頭←→，由于字符集的限制，本網頁在表示否定關聯詞時用"|"，請在書寫時注意規范寫法。對稱性是指真值表中復合命題的真值與原子命題的真值之間的關系。)
命題公式與命題不同，在一個由命題標識符組成的式子中，如果標識符表示確定的命題，則該式就是命題。如果標識符只表示命題的位置，可由任何命題代替，則該式子就為命題公式。命題變元P用特定命題替代時，稱為對P的指派。轉自環 球 網 校edu24ol.com
不是所有由命題變元、聯結詞及有關括號組成的字符串都能成為命題公式。要成為一個命題公式(合式公式)，應當符合規定。這個規定是：
(1)單個命題變元本身是一個合式公式。
(2)如果A是合式公式，那么|A是合式公式。
(3)如果A和B是合式公式，那么(A∧B)、(A∨B)、(A→B)和(A←→B)都是合式公式。
(4)當且僅當有限次地應用(1)(2)(3)所得到的包含命題變元、聯結詞和圓括號的符號串是合式公式。
總的理解就是說，單個命題變元是合式公式，由合式公式作為命題變元，有限次地運用聯結詞及括號組成的符串才能是合式公式。即命題公式，簡稱公式。
命題變元只有進行指派后才可能確定其所在命題公式的真值。當一個命公式中的所有命題變元用一組真值指定后，就稱為對命題公式的指派。想一想，什么是真指派、什么是假指派? 這個比較簡單。
一個命題的真值表應該列出其所有指派的取值情況。一般來說，由n個命題變元組成的命題公式共有2n種真值情況。
聯結詞的簡化，按照兩個等價的命題公式，可以看到一個有較多聯結詞的公式可以簡化為含有一個聯結詞的公式。這里有兩個等值公式應當記一下：
(|P∨Q)<=>(P→Q)
我們要弄清什么是"重言式(永真式)"、什么是"矛盾式(永假式)"以及"可滿足式"。這其中涉及到指派及命題公式的取值，容易理解。
課本中表1.3.6列出的常用的命題公式等價定理應該記住的.
二、等價變換(簡單應用)
當兩個合式公式中相應變元的任一種真值指派情況下，這兩個公式的真值均相同，則這兩個合式公式是等價的。可以相互置換。
有兩個命題公式A、B，A<=>B，當且僅當A←→B為一重言式(永真式)。這是什么意思呢? 就是說，如果有兩個命題A、B，只有在命題公式(A←→B)(雙條件式)的值是永真的時候，這兩個命題才是等價的。
蘊含式又稱永真條件式。永真條件式更清楚地表達了它的定義，就是一個條件式P→Q，當且僅當它是重言式時，就稱P蘊含Q (P=>Q)。什么時候P→Q不是蘊含式呢? 很明顯，當P為真、Q為假時，它不是一個蘊含式。
蘊含式有四個性質：轉自環 球 網 校edu24ol.com
(1) 對任意公式A,有A=>A，即公式蘊含本身。
(2) 對任意公式A，B和C，若A=>B、B=>C 則 A=>C。
(3) 對任意公式A，B和C，若A=>B、A=>C 則 A=>(B∧C)
證明如下：
如果A的值為T，由A→B、A→C為重言式可得B為T、C為T，此時B∧C為T。
如果A的值為F，則無論B、C為T或F，A→(B∧C)為T，所以A→(B∧C)是重言式，即A=>(B∧C)。
(4) 對任意公式A，B和C，若A=>C、B=>C 則 (A∨B)=>C
證明如下：
如果A的真值為T，由A→C為重言式可得C為T，此時不論B為何值，(A∨B)為T，(A∨B)->C為T。
若B為T，由B→C為重言式可得C為T，此時不論A為何值，(A∨B)為T，(A∨B)->C為T。
若A和B均為F，則不論C為何值，(A∨B)→C為T。所以(A∨B)=>C。
設P、Q為任意兩個命題公式，P<=>Q的充分必要條件是P=>Q，Q=>P.就是說，若要證明兩個命題公式等價，只要證明兩個公式互相蘊含。反過來，如果兩個公式是互為蘊含的，那么，這兩個公式是等價的。
同樣，第14頁的表1.4.1也應記住。
三、最小聯結詞組與范式：(簡單應用)
通過等價變換，我們可以把帶→、←→ 的公式全部化成只帶 {|、∧}或只帶{|、∨}的命題公式，這種只帶此兩種聯結詞的公式就是標準形式，即范式。
注意,單獨的|、∧、∨及{∨、∧}都不能是命題公式的最小聯結詞組。只有{|、∧}、{|、∨}是命題公式的最小聯結詞組。
范式根據其形式的不同又分為合取范式和析取范式。注意合取范式并不是只帶|和∧的公式。它要求各個子公式均是由命題變元及其否定組成的析取式。而析取范式則恰恰相反。
由n個命題變元(不是命題公式)組成的合取式，就稱為布爾合取或小項，其中每個變元與它的否定不能同時存在，但兩者必須出現(其中之一)且僅出現一次。就是說每個變元或其否定必在一個小項內出現。
小項的三個性質為：
(1)每個小項具有一個相應編碼，當該編碼與其真實指派相同時，該小項真值為T。其余各種指派情況下均為F。轉自環 球 網 校edu24ol.com
(2)任意兩個不同小項的合取式永假。因為每個小項有唯一不同的編碼，當指派與一個小項的編碼相同時，必與另一個小項的編碼不同，所以總有一個小項為假。
(3)全體小項的析取式為永真。因為在任一指派情況下，總有一個小項為真。
主析取范式是對應于原命題公式而言的，它是原命題公式的一個等價公式，而且僅由小項的析取所組成。那么要最直接地找到一個命題公式的主析取范式，就可以應用真值表，一個使公式真值為T的指派所對應的小項的析取就是此公式的主析取范式。
有了小項，則有大項(布爾析取),大項與小項定義的不同之處就是把合取變成了析取。
在真值表中一個公式的值為F的指派所對應的大項的合取，即為此公式的合取范式。對于任意含有n個命題變元的非永真命題公式A，其合取范式是唯一的。
下面我們將小項與大項作一對比，以利記憶。
小項(布爾合取)
大項(布爾析取)
定義
n個命題變元的合取式
n個命題變元的析取式
形式
P∧Q，P∧|Q，|P∧Q，|P∧|Q，
P∨Q，P∨|Q，|P∨Q，|P∨|Q，
主范式
命題變換得主析取范式
命題變換為主合取范式
真值表法求主范式
公式真值為T的指派所對應的小項的析取
公式真值為F的指派所對應的大項的合取
主范式形式
m00∨m01∨m02 (Σ0，1，2...)
小項的m用小寫，析取就是相當于連加M00∧M01∧M02 (Π0，1，2..)
大項的M用大寫，合取就相當于連乘
記憶
變元合取是小項；
小項尖尖頭朝上；
公式值真對主析；
析取小項換命題。變元析取好大項，
大項寬寬口朝天。
公式值假對大項，
合取大項主合范。
對課本中的例題應認真學習掌握。
1.6 推理理論(簡單應用)轉自環 球 網 校edu24ol.com
推理就是把一些假設前提作為T，并使用一些公論的規則，得到另外的命題形成結論，這種過程很有意思，大偵探福爾摩斯就是深諳此道的人，如果我們學會了推理，那么在做一些智力題時是很有幫助的，就象是本章最后的那幾道題，一般人要翻來覆去考慮很久，看看我們能不能用公式來解開它。
對于推理理論，主要要掌握的是判別有效結論的過程也就是論證過程。
有真值表法、主范式方法、等值演算法和構造論證法。其中構造論證法是本節的重點。
使用構造論證法，首先要確定推理定律及等值定律，也就是我們前面學過的定律及公式可以直接應用的，其次是要確定已知的前提，假設其值為真。推理過程就是一系列命題公式序列，其中每個命題公式或者是已知的前提，或者是由某些前提應用推理規則得到的結論。那么常用的推理規則有：
(1)P規則：前提引入規則，就是在證明的任何步驟上都可以引入前提。
(2)T規則：結論引入規則，就是在證明的任何步驟上證明的結論都可以為后續證明的前提。
(3)轉換規則：也是T規則，就是可以在證明的任何步驟上進行命題公式的等值替換。
還有一個定理就是CP規則： 若H1∧H2∧...Hn∧R=>C,則H1∧H2∧...Hn=>R→C
這些內容相當抽象，除了認真仔細地做習題外，光這么看是無法掌握的，所以我們要好好地做完習題。
最新資訊
- 歷年整理！2025年10月自考《毛概》簡答題常考重點，附考前預測100題2025-09-24
- 歷年匯總！2025年10月《馬原》高頻考點及備考資料2025-09-23
- 重點！2025年10月自考《習概(15040)》常考簡答題匯總2025-09-22
- 臨考沖刺！2025年10月自考考試題型、評分標準確定，速領沖刺資料包2025-09-22
- 常考！2025年10月自考《英語二》高頻考點+必背知識點2025-09-22
- 2025年10月自考開考科目清單公布！新版教材這樣買才不會錯2025-09-21
- 倒計時！2025年10月自考考前沖刺，這些資料必須有2025-09-20
- 重點收藏！2025年10月自考《中國近代史綱要》歷史事件時間點梳理2025-09-19
- 考生必看！2025年10月自考《中國近代史綱要》必背考點2025-09-19
- 重點收藏！2025年10月自考《習概(15040)》歷年高頻簡答題匯總2025-09-19
打卡人數
