自考離散數(shù)學(xué)命題演算筆記

《自考離散數(shù)學(xué)命題演算筆記》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、自考離散數(shù)學(xué)命題演算筆記本章的重點(diǎn)是命題概念及其表示、命題公式化簡(jiǎn)、主范式及其互化、P規(guī)則、T規(guī)則以及CP規(guī)則。難點(diǎn)是推理理論及應(yīng)用。一、命題概念(領(lǐng)會(huì))學(xué)習(xí)本章首先要深刻理解命題的概念。理解原子命題與復(fù)合命題的關(guān)系，在了解復(fù)合命題的基礎(chǔ)上，理解聯(lián)結(jié)詞的定義。命題：具有唯一真值的陳述句稱為命題，又簡(jiǎn)稱語(yǔ)句。注意，這里有兩個(gè)條件，首先它是一個(gè)陳述句，其次，它具有唯一的一個(gè)真值。真值：就是語(yǔ)句為真或假的性質(zhì)。一個(gè)語(yǔ)句的真值可以為真也可以為假。真值不是說(shuō)該語(yǔ)句的值必為真。任一命題必有其真值，也稱這個(gè)命題的值。既然是命題了，那

2、它必有一個(gè)確定的真值，不管這個(gè)真值為真還是為假。當(dāng)一個(gè)陳述句能夠分辯其值的真假時(shí)(也就是說(shuō)，總可以肯定是其中的某一個(gè))，它就是命題，即使我們不知道它是真還是假。另外要理解命題常量、命題變?cè)爸概傻暮x。復(fù)合命題就是一些原子命題經(jīng)過(guò)一些聯(lián)結(jié)詞復(fù)合而成的命題。常用的聯(lián)結(jié)詞有：(1)否定、(2)合取、(3)析取、(4)條件、(5)雙條件復(fù)合命題與聯(lián)系詞是密切相關(guān)的，不包含聯(lián)結(jié)詞的命題就是原子命題，至少包含一個(gè)聯(lián)結(jié)詞的命題才是復(fù)合命題。復(fù)合命題的真值只取決于構(gòu)成它們的各原子命題的真值，而與它們的內(nèi)容含義無(wú)關(guān)。對(duì)聯(lián)結(jié)詞所聯(lián)結(jié)的兩

3、原子命題之間有無(wú)關(guān)系無(wú)關(guān)。(這一條很重要，因?yàn)橐粋€(gè)命題用自然語(yǔ)言表達(dá)時(shí)，我們往往會(huì)受到自然邏輯的影響，比如"我如果不上班，那么天下雨"這種命題，在自然的邏輯里，是不成立的，一個(gè)人不上班怎么會(huì)導(dǎo)致天下雨呢?但是在這里，這個(gè)復(fù)合命題的值實(shí)際上是由兩個(gè)原子命題的真值決定的，與它的含義無(wú)關(guān)，這個(gè)復(fù)合命題是

4、P->Q,前一個(gè)原子命題的真值為假，后一命題值為真，根據(jù)條件的定義，這個(gè)復(fù)合命題值為真)∧、∨、←→具有對(duì)稱性，

5、、→無(wú)對(duì)稱性，(教材提示，也可用iff表示雙向箭頭←→，由于字符集的限制，本網(wǎng)頁(yè)在表示否定關(guān)聯(lián)詞時(shí)用"

6、"，請(qǐng)

7、在書寫時(shí)注意規(guī)范寫法。對(duì)稱性是指真值表中復(fù)合命題的真值與原子命題的真值之間的關(guān)系。)命題公式與命題不同，在一個(gè)由命題標(biāo)識(shí)符組成的式子中，如果標(biāo)識(shí)符表示確定的命題，則該式就是命題。如果標(biāo)識(shí)符只表示命題的位置，可由任何命題代替，則該式子就為命題公式。命題變?cè)狿用特定命題替代時(shí)，稱為對(duì)P的指派。不是所有由命題變?cè)?、?lián)結(jié)詞及有關(guān)括號(hào)組成的字符串都能成為命題公式。要成為一個(gè)命題公式(合式公式)，應(yīng)當(dāng)符合規(guī)定。這個(gè)規(guī)定是：(1)單個(gè)命題變?cè)旧硎且粋€(gè)合式公式。(2)如果A是合式公式，那么

8、A是合式公式。(3)如果A和B是合式公式，

9、那么(A∧B)、(A∨B)、(A→B)和(A←→B)都是合式公式。(4)當(dāng)且僅當(dāng)有限次地應(yīng)用(1)(2)(3)所得到的包含命題變?cè)?、?lián)結(jié)詞和圓括號(hào)的符號(hào)串是合式公式?？偟睦斫饩褪钦f(shuō)，單個(gè)命題變?cè)呛鲜焦?，由合式公式作為命題變?cè)?，有限次地運(yùn)用聯(lián)結(jié)詞及括號(hào)組成的符串才能是合式公式。即命題公式，簡(jiǎn)稱公式。命題變?cè)挥羞M(jìn)行指派后才可能確定其所在命題公式的真值。當(dāng)一個(gè)命公式中的所有命題變?cè)靡唤M真值指定后，就稱為對(duì)命題公式的指派。想一想，什么是真指派、什么是假指派?這個(gè)比較簡(jiǎn)單。一個(gè)命題的真值表應(yīng)該列出其所有指派的取值情況。一

10、般來(lái)說(shuō)，由n個(gè)命題變?cè)M成的命題公式共有2n種真值情況。聯(lián)結(jié)詞的簡(jiǎn)化，按照兩個(gè)等價(jià)的命題公式，可以看到一個(gè)有較多聯(lián)結(jié)詞的公式可以簡(jiǎn)化為含有一個(gè)聯(lián)結(jié)詞的公式。這里有兩個(gè)等值公式應(yīng)當(dāng)記一下：(

11、P∨Q)<=>(P→Q)我們要弄清什么是"重言式(永真式)"、什么是"矛盾式(永假式)"以及"可滿足式"。這其中涉及到指派及命題公式的取值，容易理解。課本中表1.3.6列出的常用的命題公式等價(jià)定理應(yīng)該記住的.二、等價(jià)變換(簡(jiǎn)單應(yīng)用)當(dāng)兩個(gè)合式公式中相應(yīng)變?cè)娜我环N真值指派情況下，這兩個(gè)公式的真值均相同，則這兩個(gè)合式公式是等價(jià)的。可以

12、相互置換。有兩個(gè)命題公式A、B，A<=>B，當(dāng)且僅當(dāng)A←→B為一重言式(永真式)。這是什么意思呢?就是說(shuō)，如果有兩個(gè)命題A、B，只有在命題公式(A←→B)(雙條件式)的值是永真的時(shí)候，這兩個(gè)命題才是等價(jià)的。蘊(yùn)含式又稱永真條件式。永真條件式更清楚地表達(dá)了它的定義，就是一個(gè)條件式P→Q，當(dāng)且僅當(dāng)它是重言式時(shí)，就稱P蘊(yùn)含Q(P=>Q)。什么時(shí)候P→Q不是蘊(yùn)含式呢?很明顯，當(dāng)P為真、Q為假時(shí)，它不是一個(gè)蘊(yùn)含式。蘊(yùn)含式有四個(gè)性質(zhì)：(1)對(duì)任意公式A,有A=>A，即公式蘊(yùn)含本身。(2)對(duì)任意公式A，B和C，若A=>B、B=>C則A

13、=>C。(3)對(duì)任意公式A，B和C，若A=>B、A=>C則A=>(B∧C)證明如下：如果A的值為T，由A→B、A→C為重言式可得B為T、C為T，此時(shí)B∧C為T。如果A的值為F，則無(wú)論B、C為T或F，A→(B∧C)為T，所以A→(B∧C)是重言式，即A=>(B∧C)。(4)對(duì)任意公式A，B和C，若A=>C、B=>C則(A∨B)=>C