離散數(shù)學(xué)及其應(yīng)用課件：命題邏輯

命題邏輯1.1

命題邏輯的基本概念1.2命題公式及其賦值1.3命題公式的等值演算1.4命題公式的范式1.5命題邏輯推理理論1.6命題邏輯在計(jì)算機(jī)學(xué)科中的應(yīng)用

1.1-命題邏輯的基本概念

1.1.1

-命題的概念定義1.1

能夠判斷真假的陳述句稱作命題。由命題的定義,可得到如下結(jié)論:(1)判斷一個(gè)句子是否為命題,要滿足兩個(gè)條件:首先,這個(gè)句子必須為陳述句;其次,這個(gè)句子必須有唯一的真值。也就是說,如果一個(gè)句子是疑問句、感嘆句、祈使句等,或者這個(gè)句子的真假值不確定,那么這個(gè)句子肯定不是命題。

(2)對于一個(gè)命題,如果表達(dá)的意思為真,則稱其為真命題;如果表達(dá)的意思為假,則稱其為假命題。在日常生活中,約定用1表示真命題,用0表示假命題。

例1.1

判斷下列句子是否為命題。若是命題,判斷是真命題還是假命題。

(1)北京是中華人民共和國的首都。

(2)雪是黑的。

(3)今天天氣真好啊!

(4)昨天張麗爬長城去了。

(5)1+1=0。

(6)我正在說謊。

(7)請進(jìn)!

(8)宇宙中有外星人的存在。

(9)你好嗎?

(10)x大于y,其中x和y是任意的兩個(gè)數(shù)。

解(1)是命題,而且是真命題。

(2)是命題,而且是假命題。

(3)是感嘆句,所以不是命題。

(4)是命題,真假由實(shí)際情況確定。

(5)是命題,而且是假命題。

(6)不是命題。原因:如果“我正在說謊”為真,則說明我說的是真話,因而(6)的真值應(yīng)為假,這樣就產(chǎn)生了矛盾;反之,如果“我正在說謊”為假,則說明我說的是假話,因而(6)的真值應(yīng)為真,同樣也產(chǎn)生了矛盾。因此,(6)既不能為真,也不能為假,故不是命題。類似(6)這樣由真推出假,由假又能推出真,從而既不能為真又不能為假的句子稱為悖論。悖論不是命題。

(7)是祈使句,所以不是命題。

(8)是命題,雖然由人類現(xiàn)有的知識無法判斷此句話是真還是假,但這句話的真假是客觀存在的,所以是命題。

(9)是疑問句,所以不是命題。

(10)不是命題,因?yàn)楫?dāng)x=2,y=3時(shí),“x大于y”是錯(cuò)誤的;當(dāng)x=3,y=2時(shí),“x大于y”是正確的。真值不唯一,所以不是命題。

定義1.2僅由一個(gè)主語和一個(gè)謂語組成的肯定句,稱為簡單命題或原子命題。

定義1.3由簡單命題通過聯(lián)結(jié)詞復(fù)合而成的新命題,稱為復(fù)合命題。

1.1.2命題的表示

一個(gè)簡單命題可以用任何字母或帶下標(biāo)的字母來表示。本書約定用小寫字母p,q,r,…或帶下標(biāo)的小寫字母pi,qi,ri,…表示簡單命題,并且用1表示真命題,用0表示假命題。例如:

p:我是一名大學(xué)生。

q:我是一名中學(xué)生。

r1:我是一名小學(xué)生。

例1.2下面句子哪些是命題,哪些是簡單命題或復(fù)合命題。如果是復(fù)合命題,說出是由哪些簡單命題組成的。

(1)我是黨員。

(2)我不但喜歡唐詩,而且喜歡宋詞。

(3)如果你去,我則不去。

(4)趙東不喜歡唱歌。

(5)x+y>5。

解(1)是簡單命題,即只有一個(gè)主語和一個(gè)謂語,不能再進(jìn)行分解。

(2)是復(fù)合命題,由兩個(gè)簡單命題p和q組成,其中p:我喜歡唐詩,q:我喜歡宋詞。

(3)是復(fù)合命題,由兩個(gè)簡單命題p和q組成,其中p:你去,q:我去。

(4)是復(fù)合命題,由一個(gè)簡單命題p組成,其中p:趙東喜歡唱歌。

(5)不是命題,因?yàn)楫?dāng)x、y取不同值時(shí),真值不同。

定義1.4簡單命題是命題邏輯中最基本的研究單位,其真值是確定的,又稱其為命題常項(xiàng)或命題常元。

如例1.2中的(1)為簡單命題。

定義1.5將真值可以變化的陳述句稱為命題變項(xiàng)或命題變元。

如例1.2中的(5)雖然不是命題,但當(dāng)給定x、y的值后,其真值也就確定了。

注意命題變項(xiàng)不是命題,命題常項(xiàng)和命題變項(xiàng)就如同是初等數(shù)學(xué)中的常量和變量一樣。

例1.3將下列命題符號化。

(1)3不是偶數(shù)。

(2)2是素?cái)?shù)和偶數(shù)。

(3)李芳學(xué)過英語和日語。

(4)如果角A和角B是對頂角,則角A等于角B。

解先找到每個(gè)命題中的簡單命題,并將其符號化,然后加上聯(lián)結(jié)詞。

(1)設(shè)p:3是偶數(shù),則原命題可符號化為“非p”。

(2)設(shè)p:2是素?cái)?shù),q:2是偶數(shù),則原命題可符號化為“p和q”。

(3)設(shè)p:李芳學(xué)過英語,q:李芳學(xué)過日語,則原命題可符號化為“p和q”。

(4)設(shè)p:角A和角B是對頂角,q:角A等于角B,則原命題可符號化為“如果p,則q”。

1.1.3命題聯(lián)結(jié)詞

2.合取聯(lián)結(jié)詞“∧”

定義1.7設(shè)有兩個(gè)命題p和q,則由“p和q”組成的復(fù)合命題稱作p和q

的合取式,記為“p∧q”,讀作“p合取q”。其中,“∧”是合取聯(lián)結(jié)詞。

p∧q的真值定義為:p∧q為真當(dāng)且僅當(dāng)p和q同時(shí)為真,或者p∧q為假當(dāng)且僅當(dāng)p和q同時(shí)為假。p∧q的真值表如表1-2所示。

例1.4將下列命題符號化。

(1)吳穎既用功又聰明。

(2)吳穎不僅用功而且聰明。

(3)吳穎雖然聰明,但不用功。

(4)張輝與王麗都是三好生。

(5)張輝與王麗是同學(xué)。

解(1)設(shè)p:吳穎用功,q:吳穎聰明,則原命題可符號化為p∧q。

(2)設(shè)p:吳穎用功,q:吳穎聰明,則原命題可符號化為p∧q。

(3)設(shè)p:吳穎用功,q:吳穎聰明,則原命題可符號化為p∧q。

(4)設(shè)p:張輝是三好生,q:王麗是三好生,則原命題可符號化為p∧q。

(5)因?yàn)樵}就是簡單命題,所以只要設(shè)p:張輝和王麗是同學(xué),即原命題可符號化為p。

3.析取聯(lián)結(jié)詞“∨”

定義1.8設(shè)有兩個(gè)命題p和q,則由“p或q”組成的復(fù)合命題稱作p和q的析取式,記為“p∨q”,讀作“p析取q”。其中,“∨”是析取聯(lián)結(jié)詞。

p∨q的真值定義為:p∨q為真當(dāng)且僅當(dāng)p和q至少有一個(gè)為真,或者p∨q為假當(dāng)且僅當(dāng)p和q同時(shí)為假。p∨q的真值表如表1-3所示。

例1.5將下列命題符號化。

(1)王曉芳愛唱歌或愛聽音樂。

(2)2或3是素?cái)?shù)。

(3)這趟火車4點(diǎn)半開或5點(diǎn)半開。

(4)小元元只能拿蘋果或梨中的一個(gè)。

(5)王小紅生于2012年或2013年。

(6)今晚九點(diǎn),中央電視一臺播放電視劇《雍正王朝》或轉(zhuǎn)播足球比賽。

4.蘊(yùn)涵聯(lián)結(jié)詞“→”

定義1.9設(shè)有兩個(gè)命題p和q,則由“若p,則q”組成的復(fù)合命題稱作p和q的蘊(yùn)涵式,記為“p→q”,讀作“p蘊(yùn)涵q”。其中,“→”是蘊(yùn)涵聯(lián)結(jié)詞,p為蘊(yùn)涵式的

前件,q為蘊(yùn)涵式的后件。

p→q的真值定義為:p→q為假當(dāng)且僅當(dāng)p為真q為假時(shí)。p→q的真值表如表1-4所示。

p→q所表達(dá)的關(guān)系為:p是q的充分條件,或者q是p的必要條件。漢語中表示“p→q”的是因果關(guān)系,具體的表述方法有“如果p,則q”“只要p,就q”“若p,就q”“p僅當(dāng)q”“只有q,才p”“除非q,才p”“除非q,否則非p”等。

在使用聯(lián)結(jié)詞“→”時(shí),要特別注意以下幾點(diǎn):

(1)“只有q,才p”“除非q,才p”“除非q,否則非p”是三種“逆向蘊(yùn)涵”,表達(dá)的意思還是“p→q”,這里一定要注意q是p的必要條件。

(2)蘊(yùn)涵聯(lián)結(jié)詞有兩種表示意思:第一種為內(nèi)容聯(lián)結(jié),即兩個(gè)命題之間有條件關(guān)系或因果關(guān)系;第二種為形式聯(lián)結(jié),即兩個(gè)命題之間沒有條件關(guān)系或因果關(guān)系,只是通過條件聯(lián)結(jié)詞將兩個(gè)命題聯(lián)結(jié)在一起,沒有考慮內(nèi)容上的聯(lián)結(jié),如“如果太陽從東方升起,則4+2=6”,從其形式上只是表示條件聯(lián)結(jié),就其內(nèi)容而言,無實(shí)質(zhì)性關(guān)系。

例1.6將下列命題符號化。

(1)只要天冷,小王就穿羽絨服。

(2)如果4+4=8,則雪是黑色的。

(3)只有2<1,才有3>2。

(4)除非a能被2整除,a才能被4整除。

(5)如果天氣持續(xù)干旱,植物就會死亡。

(6)除非天下大雨,否則他不乘班車上班。

解(1)設(shè)p:天冷,q:小王穿羽絨服,則原命題可符號化為p→q。

(2)設(shè)p:4+4=8,q:雪是黑色的,則原命題可符號化為p→q。

(3)設(shè)p:2<1,q:3>2,則原命題可符號化為q→p。

(4)設(shè)p:a能被2整除,q:a能被4整除,則原命題可符號化為q→p。

(5)設(shè)p:天氣持續(xù)干旱,q:植物死亡,則原命題可符號化為p→q。

(6)設(shè)p:天下大雨,q:他乘班車上班,則原命題可符號化為q→p。

5.等價(jià)聯(lián)結(jié)詞“?”

定義1.10設(shè)有兩個(gè)命題p和q,則由“p當(dāng)且僅當(dāng)q”組成的復(fù)合命題稱作p和q的等價(jià)式,記為“p?q”,讀作“p當(dāng)且僅當(dāng)q”。其中,“?”是等價(jià)聯(lián)結(jié)詞,又稱雙條件聯(lián)結(jié)詞。

p?q的真值定義為:p?q為真當(dāng)且僅當(dāng)命題p和q的真值相同時(shí),或者p?q為假當(dāng)且僅當(dāng)p和q的真值不相同時(shí)。

p?q的真值表如表1-5所示。

例1.7將下列命題符號化。

(1)你可以坐飛機(jī)當(dāng)且僅當(dāng)你買機(jī)票了。

(2)四邊形是平行四邊形當(dāng)且僅當(dāng)它的對邊平行。

(3)x能夠被2整除等價(jià)于x是偶數(shù)。

(4)如果天不下雨,則我去看足球比賽;否則我不去看足球比賽。

解(1)設(shè)p:你坐飛機(jī),q:你買機(jī)票,則原命題可符號化為p?q。

(2)設(shè)p:四邊形是平行四邊形,q:四邊形的對邊平行,則原命題可符號化為p?q。

(3)設(shè)p:x能夠被2整除,q:x是偶數(shù),則原命題可符號化為p?q。

(4)設(shè)p:天下雨,q:我看足球比賽,則原命題可符號化為p?q。

前面介紹了5種聯(lián)結(jié)詞,它們之間運(yùn)算的優(yōu)先級由以下方式確定:

(1)5種聯(lián)結(jié)詞運(yùn)算的優(yōu)先級從高到低依次為、∧、∨、→,?。

(2)沒有括號時(shí)按上述先后順序執(zhí)行。

(3)相同運(yùn)算符按從左至右順序執(zhí)行。

例1.8設(shè)p:2是無理數(shù),q:3是奇數(shù),r:蘋果是方的,s:太陽繞地球轉(zhuǎn),判斷復(fù)合命題p→q?r∧s∨p是真命題還是假命題。

解先確定命題p、q、r、s的真值,即真值分別為1、1、0、0;再由聯(lián)結(jié)詞優(yōu)先級順序可得p→q?r∧s∨p的最終取值為0。

例1.9試將下列命題符號化。

(1)如果Halen學(xué)習(xí)離散數(shù)學(xué),那么她會找到好工作。

(2)小沈和小王是夫妻倆,他們都很自私。

(3)天黑了,前面山中有狼,因此他決定留下來。

(4)當(dāng)且僅當(dāng)整數(shù)a能被2整除時(shí),a才是偶數(shù)。

(5)如果今天沒有課外作業(yè),那么我去看望小張或小李。

(6)如果沒有老王和老李幫助我,我是完不成這個(gè)任務(wù)的。

6.異或聯(lián)結(jié)詞“⊕”

定義1.11-設(shè)有兩個(gè)命題p和q,則由“p和q中恰有一個(gè)成立”組成的復(fù)合命題稱作p和q的異或(又稱“排斥或”),記為“p⊕q”,讀作“p異或q”。其中,“⊕”是異或聯(lián)結(jié)詞。

p⊕q的真值定義為:p⊕q為真當(dāng)且僅當(dāng)p和q恰有一個(gè)為真時(shí)。p⊕q的真值表如表1-6所示,并且有p⊕q等價(jià)于(p∧q)∨(p∧q)。

7.與非聯(lián)結(jié)詞“↑”

定義1.12設(shè)有兩個(gè)命題p和q,則由“p與q的否定”組成的復(fù)合命題稱作p和q的與非式,記為“p↑q”,讀作“p與非q”。其中,“↑”是與非聯(lián)結(jié)詞。

p↑q的真值定義為:p↑q為真當(dāng)且僅當(dāng)p和q不同時(shí)為真時(shí)。p↑q的真值表如表1-7所示,并且有p↑q等價(jià)于(p∧q)。

8.或非聯(lián)結(jié)詞“↓”

定義1.13設(shè)有兩個(gè)命題p和q,則由“p或q的否定”組成的復(fù)合命題稱作p和q的或非式,記為“p↓q”,讀作“p或非q”。其中,“↓”是或非聯(lián)結(jié)詞。

p↓q的真值定義為:p↓q為真當(dāng)且僅當(dāng)p和q同時(shí)為假時(shí)。p↓q的真值表如表1-8所示,并且有p↓q等價(jià)于(p∨q)。

1.1.4聯(lián)結(jié)詞完備集

定義1.14令S是一個(gè)聯(lián)結(jié)詞集合,若對于任何一個(gè)公式均可以用S中的聯(lián)結(jié)詞來表示,就稱集合S為聯(lián)結(jié)詞完備集。

1.1.3節(jié)介紹了8種聯(lián)結(jié)詞,分別是、∧、∨、→、?、⊕,↑、↓。這8種聯(lián)結(jié)詞組成的集合S={,∧,∨,→,?,⊕,↑,↓}必定是一個(gè)聯(lián)結(jié)詞完備集,但卻不是最小完備集,因?yàn)榧蟂中存在冗余聯(lián)結(jié)詞,即某一個(gè)聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞所表示。比如,“↑”聯(lián)結(jié)詞根據(jù)定義1.12可由“、∧”兩個(gè)聯(lián)結(jié)詞代替,因此“↑”是冗余聯(lián)結(jié)詞。而“”聯(lián)結(jié)詞卻不能由其他聯(lián)結(jié)詞來代替,因此類似“”這樣的聯(lián)結(jié)詞稱為獨(dú)立聯(lián)結(jié)詞。

定義1.15若S是一個(gè)聯(lián)結(jié)詞完備集,且S中不含冗余聯(lián)結(jié)詞,則稱這樣的集合S為最小完備集。

1.2命題公式及其賦值1.2.1

命題公式的概念定義1.16當(dāng)使用聯(lián)結(jié)詞集{￢,∧,∨,?,?}時(shí),其遞歸定義如下:(1)單個(gè)命題常項(xiàng)或變項(xiàng)是公式;(2)如果P是公式,則P是公式;(3)如果P、Q是公式,則P∧Q、P∨Q、P?Q、P?Q都是公式;(4)當(dāng)且僅當(dāng)有限次地應(yīng)用(1)~(3)所得到的符號串是合式公式(或公式)。

定義1.17對于一個(gè)合式公式,可以用下面的方法定義它的層:

(1)若公式A是單個(gè)的命題變項(xiàng),則稱A為0層公式。

(2)若存在以下情況,則稱A是n+1(n≥0)層公式:

①A=B,B是n層公式;

②A=B∧C,其中B、C分別為i層和j層公式,且n=max(i,j);

③A=B∨C,其中B、C的層次及n同②;

④A=B→C,其中B、C的層次及n同②;

⑤A=B?C,其中B、C的層次及n同②。

例1.10判斷下列公式是幾層公式。

(1)p→(p∨q)

(2)(p∧(p→q))→q

(3)((p→q)∧(r→s))→((p∧r)→(q∧s))

解判斷一個(gè)公式的層數(shù),可以根據(jù)對應(yīng)聯(lián)結(jié)詞的優(yōu)先級情況,按照優(yōu)先級從高到低逐層計(jì)算,最終得到原公式是幾層公式。根據(jù)這種思想可知(1)為2層公式,(2)為3層公式,(3)為3層公式。

定義1.18把用自然語言描述的命題轉(zhuǎn)變成命題邏輯中的符號形式,稱為命題的翻譯。

將一個(gè)命題翻譯成一個(gè)合式公式,要先找到命題中所有的簡單命題,然后將簡單命題符號化為p,q,r,…或者帶下標(biāo)的pi,qi,ri,…,最后使用聯(lián)結(jié)詞和必要的括號將這些簡單命題聯(lián)結(jié)起來。

例1.11

假如上午不下雨,我就去看電影,否則就在家里讀書或看報(bào)。

解通過分析,可知原命題中的簡單命題有

p:上午下雨

q:我去看電影

r:我在家里讀書

s:我在家里看報(bào)

則該命題被翻譯為公式:

例1.12居里夫人是波蘭人,她是一個(gè)偉大的科學(xué)家,由于她對科學(xué)事業(yè)作出了巨大的貢獻(xiàn),因此她被授予諾貝爾獎(jiǎng)。

解通過分析,可知原命題中的簡單命題有

p:居里夫人是波蘭人

q:居里夫人是一個(gè)偉大的科學(xué)家

r:居里夫人對科學(xué)事業(yè)作出了巨大的貢獻(xiàn)

s:居里夫人被授予諾貝爾獎(jiǎng)

則該命題被翻譯為公式:

例1.13如果明天上午不是雨夾雪,那么我必去學(xué)校。

解通過分析,可知原命題中的簡單命題有

p:明天上午下雨

q:明天上午下雪

r:我去學(xué)校

則該命題被翻譯為公式:

1.2.2命題公式的解釋

定義1.19設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的全部命題變項(xiàng),如果指定p1,p2,…,pn

的一組真值,則稱這組真值為公式A的一個(gè)解釋或賦值或指派,記作I。

定義1.20若指定的一組賦值使公式A的真值為1,則稱這組賦值是A的成真賦值;若指定的一組賦值使公式A的真值為0,則稱這組賦值是A的成假賦值。

例1.14設(shè)有公式A=(￢

p∧q)→r,判斷公式A共有幾種賦值情況,分別是什么,哪些是成真賦值,哪些是成假賦值。

解由于公式A中有3個(gè)命題變項(xiàng):p、q和r,因此共有8種賦值情況,分別為000、001、010、011、100、101、110和111,其中成真賦值有000、001、011、100、101、110和111,成假賦值有010。

1.2.3命題公式的類型

定義1.21

設(shè)A為任一命題公式,如果A在所有賦值下取值均為真,則稱A是永真式或重言式;如果A在所有賦值下取值均為假,則稱A是永假式或矛盾式;如果至少存在一種賦值使公式A取值為真,則稱A是可滿足式。

注意(1)重言式一定是可滿足式,反之不真。

(2)若公式A是可滿足式,且它至少存在一個(gè)成假賦值,則稱A為非永真式(重言式)的可滿足式。

(3)判斷公式類型的方法有兩種:真值表法和等值演算法

定理1.1

任何兩個(gè)重言式的合取或析取,仍然是一個(gè)重言式。

證明設(shè)A和B為兩個(gè)重言式,則給A和B任意賦值,總有A為1且B為1,所以A∧B和A∨B也都為重言式。

定理1.2一個(gè)重言式,對同一分量用任何合式公式置換,其結(jié)果仍為一個(gè)重言式。

證明由于重言式的真值與分量的取值無關(guān),因此對同一分量以任何合式公式置換后,重言式的真值仍為1。例如,公式((p∨s)∧r)∨((p∨s)∧r)為重言式,對其分量(p∨s)∧r用任何的合式公式置換后,最終形成的公式仍然為重言式。

1.2.4真值表

定義1.22將公式A在其所有賦值下所取得的真值列成一個(gè)表,稱為A的真值表。構(gòu)造真值表的方法如下:

(1)找出公式A中的全部命題變項(xiàng),并按一定的順序排列成p1,p2,…,pn(若無下標(biāo),則按字典序排列)。

(2)列出A的2n個(gè)賦值,賦值從00…0開始,按二進(jìn)制遞加順序依次寫出各賦值,直到11…1為止(或從11…1開始,按二進(jìn)制遞減順序?qū)懗龈髻x值,直到00…0為止)。

(3)按照優(yōu)先級從高到低依次寫出公式的各個(gè)層次。

(4)根據(jù)賦值依次計(jì)算各層次公式的真值并最終計(jì)算出A的真值。

例1.15求￢(p→q)∧q的真值表。

解由真值表的構(gòu)造方法,可寫出真值表,如表1-9所示。

例1.16利用真值表,判斷下列公式的類型,并求出哪些賦值是成真賦值,哪些賦值是成假賦值。

(1)p→q

(2)(p∧q)→r

(3)q∨(p→q)

解(1)p→q的真值表如表1-10所示

(2)￢(p∧q)→r的真值表如表1-11所示。

(3)￢

q∨(p→q)的真值表如表1-12所示。

1.3命題公式的等值演算

1.3.1

等值式定義1.23設(shè)A和B是兩個(gè)合式公式,若A?B是永真式,則稱A和B是等值的,記為A?B。定理1.3設(shè)A、B、C是任意的合式公式,則有(1)A?A。(2)若A?B,則B?A。(3)若A?B且B?C,則A?C。

定理1.4設(shè)A、B、C是公式,則下述等值式成立:

注意以上等值式中的A、B代表任意的合式公式,比如蘊(yùn)涵等值式A→B?￢A∨B中的A和B可以換成一個(gè)具體的合式公式p和q,這樣就形成了一個(gè)具體的等值式:p→q?￢p∨q;或者A和B也可以換成合式公式p∧q和q→r,則又形成了另外一個(gè)具體的等值式:(p∧q)→(q→r)?￢(p∧q)∨(q→r)。還需要注意的是:“等值”的意思是,兩個(gè)公式在任意賦值下真值都是一樣的,而不是說兩個(gè)公式完全“相等”

例1.17證明(￢p∧q)?p∨q成立。

證明由定義1.23可知,只需證明￢(p∧q)?(￢p∨￢q)為永真式即可。

1.3.2等值演算法

1.等值演算法

定理1.5設(shè)f(A)是一個(gè)含有子公式A的命題公式,f(B)是用公式B置換了f(A)中的子公式A后得到的公式,如果A?B,那么f(A)?f(B)。

注意以上置換規(guī)則是一種等值演算的方法,即等值演算的每一步都是用與原公式中的子公式(可以是公式本身)等值的公式來置換該子公式,從而保證置換前后的公式是等值的。

2.等值演算法應(yīng)用舉例

1)證明兩個(gè)公式等值

此應(yīng)用見例1.18。

2)判斷命題公式的類型

給定一個(gè)命題公式,先利用等值演算法對命題公式進(jìn)行簡化,若最終能簡化為1,說明該公式與1等值,則該公式為重言式;同理,若最終簡化為0,說明該公式與0等值,則該公式為矛盾式;若簡化的結(jié)果為另一個(gè)命題公式,則該公式為非重言式的可滿足式。

注意對于非重言式的可滿足式來說,由于((p∧q)∨(p∧￢

q))∧r與p∧r等值,而等值的定義就是在所有賦值下兩個(gè)公式的真值一模一樣,因此可以通過對p∧r賦值,得到原式((p∧q)∨(p∧￢

q))∧r的成真賦值和成假賦值。由于p∧r的成真賦值只有一個(gè):11,因此可以得到原式((p∧q)∨(p∧￢

q))∧r的成真賦值有兩個(gè):101和111,其余賦值都為成假賦值。

1.4命題公式的范式

1.4.1

析取范式與合取范式1.對偶式定義1.24在僅含有聯(lián)結(jié)詞、∧、∨的命題公式A中,將聯(lián)結(jié)詞∧換成∨,將∨換成∧,如果A中含有真值1或0,就將1換成0,0換成1,所得的命題公式A*稱為A的對偶式。

定理1.10設(shè)A和A*互為對偶式,p1,p2,…,pn

是出現(xiàn)在A和A*中的所有命題變項(xiàng),若將A和A*寫成n元函數(shù)形式,則有

(1)￢A(p1,p2,…,pn)?A*(￢p1,￢p2,…,￢

pn)

(2)￢A(￢p1,￢p2,…,￢pn)?A*(p1,p2,…,pn)

證明該定理的證明使用德·摩根定律即可,證明過程略。

2.簡單析取式與簡單合取式

定義1.25由任意多個(gè)單個(gè)命題變項(xiàng)或其否定組成的析取式(合取式),稱為簡單析取式(簡單合取式)。簡單析取式(簡單合取式)又稱基本和(基本積)。

定理1.11

簡單析取式和簡單合取式有如下性質(zhì):

(1)簡單析取式為重言式,當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)及其否定。

(2)簡單合取式為矛盾式,當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)及其否定。

3.范式

定義1.26由有限個(gè)簡單合取式構(gòu)成的析取式,稱為析取范式;由有限個(gè)簡單析取式構(gòu)成的合取式,稱為合取范式。

定理1.12析取范式和合取范式有如下性質(zhì):

(1)一個(gè)析取范式為矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡單合取式為矛盾式。

(2)一個(gè)合取范式為重言式當(dāng)且僅當(dāng)它的每個(gè)簡單析取式為重言式。

定理1.13對于任何命題公式A都存在與其等值的析取范式和合取范式。

證明對于任一命題公式A,首先使用基本等值式消去A中除￢、∧、∨外的其他聯(lián)結(jié)詞,然后將公式中的￢都消去或移到命題變項(xiàng)之前,最后使用結(jié)合律或者分配律等將公式化為與之等值的析取范式或合取范式。(注意:這也是求給定公式的析取范式與合取范式的方法。)

1.4.2主析取范式與主合取范式

1.主析取范式

定義1.27若n個(gè)命題變項(xiàng)組成的簡單合取式中,每個(gè)命題變項(xiàng)及其否定恰好出現(xiàn)一個(gè)且僅出現(xiàn)一次,而且命題變項(xiàng)或其否定按字母順序或下標(biāo)排序,則稱這樣的合取式為極小項(xiàng)。

極小項(xiàng)具有如下性質(zhì):

(1)每一個(gè)極小項(xiàng)當(dāng)其成真賦值與記法下標(biāo)所對二進(jìn)制相同時(shí),其真值為1,在其余2n-1種賦值下其真值均為0。

(2)任意兩個(gè)不同的極小項(xiàng)的合取式永假。

(3)全體極小項(xiàng)的析取式永為真。

定義1.28對于給定的命題公式,如果可以等值為僅由若干個(gè)極小項(xiàng)的析取組成的式子,則該等值式稱為原公式的主析取范式,記為∑(r1,r2,…),其中r1,r2,…為極小項(xiàng)對應(yīng)的下標(biāo)。

2.主合取范式

定義1.29若n個(gè)命題變項(xiàng)組成的簡單析取式中,每個(gè)命題變項(xiàng)及其否定恰好出現(xiàn)一個(gè)且僅出現(xiàn)一次,而且命題變項(xiàng)或其否定按字母順序或下標(biāo)排序,則稱這樣的析取式為極大項(xiàng)。

極大項(xiàng)具有如下性質(zhì):

(1)每一個(gè)極大項(xiàng)當(dāng)其成假賦值與記法下標(biāo)所對二進(jìn)制相同時(shí),其真值為0,在其余2n-1種賦值下其真值均為1。

(2)任意兩個(gè)不同的極大項(xiàng)的析取式永真。

(3)全體極大項(xiàng)的合取式永為假。

定義1.30對于給定的命題公式,如果可以等值為僅由若干個(gè)極大項(xiàng)的合取組成的式子,則該等值式稱為原公式的主合取范式,記為∏(r1,r2,…),其中r1,r2,…為極大項(xiàng)對應(yīng)的下標(biāo)。

3.主范式的求解方法

1)真值表法

在真值表中,一個(gè)公式的每個(gè)成真賦值(成假賦值)都對應(yīng)于該公式的一個(gè)極小項(xiàng)(極大項(xiàng)),在真值表中找出所有的成真賦值(成假賦值),以這些成真賦值(成假賦值)所對的十進(jìn)制數(shù)作為下標(biāo)的極小項(xiàng)(極大項(xiàng))的析取(合取)形成的式子即為原公式的主析取范式(主合取范式)。

2)等值演算法

第一步,將給定命題公式化成析取范式(合取范式)。

第二步,若析取范式(合取范式)中某個(gè)簡單合取式(簡單析取式)中不含命題變項(xiàng)pi,則用排中律(矛盾律)補(bǔ)進(jìn)該變項(xiàng),從而使得該簡單合取式(簡單析取式)中含有全部的命題變項(xiàng),然后使用分配律使該簡單合取式(簡單析取式)與補(bǔ)進(jìn)的變項(xiàng)結(jié)合,最終形成的式子均為極小項(xiàng)(極大項(xiàng))。

第三步,用冪等律將重復(fù)出現(xiàn)的項(xiàng)化簡為一次出現(xiàn)。

第四步,按極小項(xiàng)(極大項(xiàng))的下標(biāo)從小到大排列,并用∑(∏)表示。

注意在使用真值表法或等值演算法求主范式時(shí),根據(jù)例1.23發(fā)現(xiàn)最終求出的主析取范式與主合取范式對應(yīng)的極小項(xiàng)和極大項(xiàng)的個(gè)數(shù)之和正好等于2n(n為公式中含有的命題變項(xiàng)的個(gè)數(shù)),而且極大項(xiàng)與極小項(xiàng)的下標(biāo)是互補(bǔ)的(從0開始到2n-1結(jié)束),為此今后在求主范式時(shí),只要先求出公式的主析取范式,那么主合取范式可以直接得到,或是先求出公式的主合取范式,那么主析取范式也可以直接得到。

1.4.3主范式的應(yīng)用

1.求命題公式的成真賦值和成假賦值

若公式A含有n個(gè)命題變項(xiàng),對應(yīng)的主析取范式有n1

個(gè)極小項(xiàng),主合取范式有n2個(gè)極大項(xiàng),其中n1+n2=2n,則這n

個(gè)極小項(xiàng)的下標(biāo)對應(yīng)的二進(jìn)制即為公式A的成真賦值,這n2個(gè)極大項(xiàng)的下標(biāo)對應(yīng)的二進(jìn)制即為公式A的成假賦值。

例如,例1.23中公式(1)的成真賦值為m2,對應(yīng)下標(biāo)的二進(jìn)制為10,成假賦值為M0、M1、M3,對應(yīng)下標(biāo)的二進(jìn)制為00、01、11;公式(2)的成真賦值為m1、m3、m6、m7,對應(yīng)下標(biāo)的二進(jìn)制為001、011、110、111,成假賦值為M0、M2、M4、M5,對應(yīng)下標(biāo)的二進(jìn)制為000、010、100、101。

2.判斷命題公式的類型

公式的類型分為永真式(重言式)、永假式(矛盾式)和非永真式(重言式)的可滿足式三種。當(dāng)公式的主范式給定后,通過主范式就可以確定公式的類型。

若公式A有n個(gè)命題變項(xiàng),其主析取范式由全部的極小項(xiàng)(2n個(gè))組成,則公式A必為永真式;若A的主合取范式由全部的極大項(xiàng)(2n個(gè))組成,則公式A必為永假式;若A的主析取范式中存在極小項(xiàng),并且主合取范式中存在極大項(xiàng),則A必為非永真式的可滿足式。

注意對于一個(gè)給定的公式,是使用等值演算法還是主范式法來判斷類型,要根據(jù)實(shí)際情況而定。例如,以上(1)(2)兩題是使用主范式法來判斷公式類型的,其實(shí)對于(1)(2)兩題直接使用等值演算法來判斷類型更加簡單,過程如下:

3.判斷兩命題是否等值

根據(jù)等值的定義可知,如果兩個(gè)公式A和B等值,那么

A和B必定存在相同的成真賦值和成假賦值。因此,如果A和B對應(yīng)的主析取范式和主合取范式完全一樣,那么A和B必定等值。相反,如果A和B對應(yīng)的主范式不一樣,則A和B必定不等值。

4.邏輯推理

例1.26張三說李四說謊,李四說王五說謊,王五說張三、李四都在說謊。判斷張三、李四、王五三人誰說真話、誰說假話。

解首先找到問題中的簡單命題,設(shè)

p:張三說真話

q:李四說真話

r:王五說真話

通過以上步驟,得到公式①對應(yīng)的主析取范式為￢

p∧q∧￢r,也就是可以得到題目中的邏輯推理的結(jié)論為:張三說假話,李四說真話,王五說假話。

1.5命題邏輯推理理論

1.5.1-推理的基本概念1.永真蘊(yùn)涵式定義1.31

設(shè)A、B是兩個(gè)合式公式,若A→B是永真式,則稱A永真(或重言)蘊(yùn)涵B,記作A?B,A?B為永真蘊(yùn)涵式。定理1.14設(shè)A、B為任意兩個(gè)命題公式,A?B的充要條件是A?B且B?A。

證明(必要性)若A?B,則A?B為永真式,因?yàn)锳?B?(A→B)∧(B→A),故A→B為1且B→A為1,即A?B,B?A成立。

(充分性)若A?B且B?A,則A→B為1且B→A為1,因此A?B為1,A?B為永真式,即A?B。

性質(zhì)1.1

設(shè)A、B、C為合式公式,若A?B且A是永真式,則B必是永真式。

性質(zhì)1.2若A?B,B?C,則A?C。

性質(zhì)1.3若A?B,A?C,則A?(B∧C)。

性質(zhì)1.4若A?B,C?B,則(A∨C)?B。

2.前提和結(jié)論

邏輯學(xué)的重要任務(wù)是研究人類的思維規(guī)律,能夠進(jìn)行有效的推理是人類智慧的重要體現(xiàn)。推理也稱論證,是指由已知的若干命題得到新命題的思維過程,其中已知命題稱為推

理的前提或假設(shè),推理得出的新命題稱為推理的結(jié)論。

定義1.32給定一組假設(shè)A1,A2,…,An和一個(gè)結(jié)論B,只需考察如下永真蘊(yùn)涵式是否成立:

若該永真蘊(yùn)涵式成立,則稱從合式公式A1∧A2∧…∧An推出B的推理是正確的(或有效的),稱A1,A2,…,An為推理的前提,B為由這些前提推出的有效結(jié)論,也稱為邏輯結(jié)論;若該永真蘊(yùn)涵式不成立,則推理不正確,稱B是A1,A2,…,An的謬誤結(jié)論。

1.5.2推理定律和推理規(guī)則

1.推理定律

2.推理規(guī)則

在推理證明的過程中,需要用到的推理規(guī)則如下:

(1)前提引入規(guī)則(P規(guī)則):在證明的任何時(shí)候都可以引入前提。

(2)結(jié)論引入規(guī)則(T規(guī)則):在證明的任何時(shí)候,已證明的結(jié)論都可以作為后續(xù)證明的前提。

(3)置換規(guī)則:在證明的任何時(shí)候,命題公式中的任何子命題公式都可以用與之等值的命題公式置換。此規(guī)則包含了全部等值式產(chǎn)生的推理定律。

(4)由推理定律導(dǎo)出的推理規(guī)則:由以上推理定律導(dǎo)出的推理規(guī)則如表1-20所示。

1.5.3命題邏輯推理方法

1.真值表法

根據(jù)推理正確與否的判斷,先找到前提以及結(jié)論中所有的命題變項(xiàng),然后在所有的賦值下,尋找前提的合取以及結(jié)論是否出現(xiàn)前真后假的情況,若出現(xiàn)了,則推理是錯(cuò)誤的,否則推理正確。

例1.27判斷如下兩個(gè)推理是否正確。

(1)(p→q)∧(q→r)∧p?r

(2)(p→q)∧(p∧r)?￢

r

解(1)前提與結(jié)論中出現(xiàn)的命題變項(xiàng)有3個(gè),分別為p,q和r,前提的合取與結(jié)論所對的真值表如表1-21所示。

(2)前提與結(jié)論中出現(xiàn)的命題變項(xiàng)有3個(gè),分別為p,q和r,且前提的合取與結(jié)論所對的真值表如表1-22所示。

2.公式演算法

根據(jù)永真蘊(yùn)涵式的定義1.31和推理的定義1.32可知,命題邏輯中的推理問題實(shí)質(zhì)上就是證明永真蘊(yùn)涵式成立的過程,為此可以使用類似等值演算的方法,通過置換從公式的左邊推演到公式的右邊。

3.推理規(guī)則演繹法

上面介紹的真值表法和永真蘊(yùn)涵式法雖然能夠證明推理的正確性,但是當(dāng)前提條件比較復(fù)雜時(shí),使用這兩種方法證明推理就顯得較為繁瑣了。為此,這里再介紹一種新的推理方法,其理論基礎(chǔ)為1.5.2節(jié)所介紹的前提引入規(guī)則、結(jié)論引入規(guī)則、置換規(guī)則以及推理定律。

1)直接證明法

使用直接證明法證明推理,先判斷前提中的公式是否可以使用已知推理定律,若可以,則得到一個(gè)新的公式,此新的公式可以作為后續(xù)證明的前提(結(jié)論引入規(guī)則),然后繼續(xù)引入前提中的公式(前提引入規(guī)則),判斷已經(jīng)存在的前提是否可以利用推理定律得到新的公式,…,這樣反復(fù)進(jìn)行,只要能推出最后的結(jié)論,則說明此推理是正確的,否則推理不正確。

注意例1.30的證明都是采用直接證明法證明的。要特別注意,在證明的過程中,如果前提中的公式之間不能直接使用推理定律得到新公式的,需要先將前提中的公式化簡或等值成其他新的公式(置換規(guī)則),然后再判斷新的公式和已有的前提是否可以使用推理定律。

例1.33使用附加前提證明法,先對下面的推理進(jìn)行符號化,然后證明其正確性。

如果王麗有新手機(jī),要么她發(fā)了獎(jiǎng)金,要么她向別人借了錢。王麗沒有向別人借錢。所以,王麗若沒有發(fā)獎(jiǎng)金,則她不會有新手機(jī)。

例1.35使用歸謬法,先對下面的推理進(jìn)行符號化,然后證明其正確性。

如果我考出好成績,那么我就去廈門旅游;如果我去廈門旅游,那么我就要買新電腦;如果我要買新電腦,我就去銀行取錢;但我沒去銀行取錢,所以我沒考出好成績。

1.6命題邏輯在計(jì)算機(jī)學(xué)科中的應(yīng)用

1.6.1

命題邏輯公式在計(jì)算機(jī)中的表示一個(gè)命題變項(xiàng)只有真、假兩個(gè)值,在計(jì)算機(jī)中可以用一個(gè)布爾變量來表示,利用布爾變量之間的邏輯運(yùn)算很容易計(jì)算任意命題公式的真值。大部分高級語言中有布爾型的數(shù)據(jù)類型,如C++或JAVA等編程語言。在C語言中不存在布爾型的數(shù)據(jù)類型,0即為假,非0即為真。但是,在C語言的頭文件中用來定義一種類似于C++中的BOOL變量。

方法如下:

運(yùn)行結(jié)果如圖1-1所示:圖1-1

運(yùn)行結(jié)果

例1.37C語言中的復(fù)雜邏輯表達(dá)式:p‖q&&r‖!q,當(dāng)給定p、q和r的值分別為0、0和1時(shí),求原表達(dá)式的最終取值。

解根據(jù)&&、‖和!的優(yōu)先級,以及與邏輯聯(lián)結(jié)詞∧、∨和的對應(yīng)關(guān)系,將原C語言表達(dá)式轉(zhuǎn)換為邏輯公式為:

p∨(q∧r)∨q,當(dāng)p、q、r取值為0、0、1時(shí),邏輯公式

p∨(q∧r)∨q的取值為1,即原C語言邏輯表達(dá)式p‖q&&r‖!q的值為1。

1.6.2命題邏輯在計(jì)算機(jī)硬件電路設(shè)計(jì)中的應(yīng)用

邏輯運(yùn)算又稱布爾運(yùn)算,它是用數(shù)學(xué)的方法解決或研究邏輯問題的工具,其使用1和0表示邏輯中的真和假,再加上與之相關(guān)的“與”、“或”、“非”等聯(lián)結(jié)詞,從而實(shí)現(xiàn)從復(fù)雜邏輯運(yùn)算到簡單的數(shù)值計(jì)算的轉(zhuǎn)化。

1.命題邏輯在開關(guān)電路中的應(yīng)用

在開關(guān)電路中,用聯(lián)結(jié)詞“合取”表示“串聯(lián)”電