離散數(shù)學及其應用課件：命題邏輯

命題邏輯1.1

命題邏輯的基本概念1.2命題公式及其賦值1.3命題公式的等值演算1.4命題公式的范式1.5命題邏輯推理理論1.6命題邏輯在計算機學科中的應用

1.1-命題邏輯的基本概念

1.1.1

-命題的概念定義1.1

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

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

例1.1

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

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

(2)雪是黑的。

(3)今天天氣真好啊!

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

(5)1+1=0。

(6)我正在說謊。

(7)請進!

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

(9)你好嗎?

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

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

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

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

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

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

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

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

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

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

(10)不是命題,因為當x=2,y=3時,“x大于y”是錯誤的;當x=3,y=2時,“x大于y”是正確的。真值不唯一,所以不是命題。

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

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

1.1.2命題的表示

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

p:我是一名大學生。

q:我是一名中學生。

r1:我是一名小學生。

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

(1)我是黨員。

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

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

(4)趙東不喜歡唱歌。

(5)x+y>5。

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

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

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

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

(5)不是命題,因為當x、y取不同值時,真值不同。

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

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

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

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

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

例1.3將下列命題符號化。

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

(2)2是素數(shù)和偶數(shù)。

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

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

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

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

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

(3)設(shè)p:李芳學過英語,q:李芳學過日語,則原命題可符號化為“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è)有兩個命題p和q,則由“p和q”組成的復合命題稱作p和q

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

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

例1.4將下列命題符號化。

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

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

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

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

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

解(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)因為原命題就是簡單命題,所以只要設(shè)p:張輝和王麗是同學,即原命題可符號化為p。

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

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

p∨q的真值定義為:p∨q為真當且僅當p和q至少有一個為真,或者p∨q為假當且僅當p和q同時為假。p∨q的真值表如表1-3所示。

例1.5將下列命題符號化。

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

(2)2或3是素數(shù)。

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

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

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

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

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

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

前件,q為蘊涵式的后件。

p→q的真值定義為:p→q為假當且僅當p為真q為假時。p→q的真值表如表1-4所示。

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

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

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

(2)蘊涵聯(lián)結(jié)詞有兩種表示意思:第一種為內(nèi)容聯(lián)結(jié),即兩個命題之間有條件關(guān)系或因果關(guān)系;第二種為形式聯(lián)結(jié),即兩個命題之間沒有條件關(guān)系或因果關(guān)系,只是通過條件聯(lián)結(jié)詞將兩個命題聯(lián)結(jié)在一起,沒有考慮內(nèi)容上的聯(lián)結(jié),如“如果太陽從東方升起,則4+2=6”,從其形式上只是表示條件聯(lián)結(jié),就其內(nèi)容而言,無實質(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.等價聯(lián)結(jié)詞“?”

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

p?q的真值定義為:p?q為真當且僅當命題p和q的真值相同時,或者p?q為假當且僅當p和q的真值不相同時。

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

例1.7將下列命題符號化。

(1)你可以坐飛機當且僅當你買機票了。

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

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

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

解(1)設(shè)p:你坐飛機,q:你買機票,則原命題可符號化為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ōu)先級由以下方式確定:

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

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

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

例1.8設(shè)p:2是無理數(shù),q:3是奇數(shù),r:蘋果是方的,s:太陽繞地球轉(zhuǎn),判斷復合命題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學習離散數(shù)學,那么她會找到好工作。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2命題公式及其賦值1.2.1

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

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

(1)若公式A是單個的命題變項,則稱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))

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

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

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

例1.11

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

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

p:上午下雨

q:我去看電影

r:我在家里讀書

s:我在家里看報

則該命題被翻譯為公式:

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

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

p:居里夫人是波蘭人

q:居里夫人是一個偉大的科學家

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

s:居里夫人被授予諾貝爾獎

則該命題被翻譯為公式:

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

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

p:明天上午下雨

q:明天上午下雪

r:我去學校

則該命題被翻譯為公式:

1.2.2命題公式的解釋

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

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

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

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

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

解由于公式A中有3個命題變項: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是可滿足式,且它至少存在一個成假賦值,則稱A為非永真式(重言式)的可滿足式。

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

定理1.1

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

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

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

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

1.2.4真值表

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

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

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

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

(4)根據(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是兩個合式公式,若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代表任意的合式公式,比如蘊涵等值式A→B?￢A∨B中的A和B可以換成一個具體的合式公式p和q,這樣就形成了一個具體的等值式:p→q?￢p∨q;或者A和B也可以換成合式公式p∧q和q→r,則又形成了另外一個具體的等值式:(p∧q)→(q→r)?￢(p∧q)∨(q→r)。還需要注意的是:“等值”的意思是,兩個公式在任意賦值下真值都是一樣的,而不是說兩個公式完全“相等”

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

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

1.3.2等值演算法

1.等值演算法

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

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

2.等值演算法應用舉例

1)證明兩個公式等值

此應用見例1.18。

2)判斷命題公式的類型

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

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

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

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

q))∧r的成真賦值有兩個: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*中的所有命題變項,若將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由任意多個單個命題變項或其否定組成的析取式(合取式),稱為簡單析取式(簡單合取式)。簡單析取式(簡單合取式)又稱基本和(基本積)。

定理1.11

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

(1)簡單析取式為重言式,當且僅當它同時含有某個命題變項及其否定。

(2)簡單合取式為矛盾式,當且僅當它同時含有某個命題變項及其否定。

3.范式

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

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

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

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

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

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

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

1.主析取范式

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

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

(1)每一個極小項當其成真賦值與記法下標所對二進制相同時,其真值為1,在其余2n-1種賦值下其真值均為0。

(2)任意兩個不同的極小項的合取式永假。

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

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

2.主合取范式

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

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

(1)每一個極大項當其成假賦值與記法下標所對二進制相同時,其真值為0,在其余2n-1種賦值下其真值均為1。

(2)任意兩個不同的極大項的析取式永真。

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

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

3.主范式的求解方法

1)真值表法

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

2)等值演算法

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

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

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

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

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

1.4.3主范式的應用

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

若公式A含有n個命題變項,對應的主析取范式有n1

個極小項,主合取范式有n2個極大項,其中n1+n2=2n,則這n

個極小項的下標對應的二進制即為公式A的成真賦值,這n2個極大項的下標對應的二進制即為公式A的成假賦值。

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

2.判斷命題公式的類型

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

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

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

3.判斷兩命題是否等值

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

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

4.邏輯推理

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

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

p:張三說真話

q:李四說真話

r:王五說真話

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

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

1.5命題邏輯推理理論

1.5.1-推理的基本概念1.永真蘊涵式定義1.31

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

證明(必要性)若A?B,則A?B為永真式,因為A?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é)論

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

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

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

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

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

1.推理定律

2.推理規(guī)則

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

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

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

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

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

1.5.3命題邏輯推理方法

1.真值表法

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

例1.27判斷如下兩個推理是否正確。

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

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

r

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

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

2.公式演算法

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

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

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

1)直接證明法

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

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

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

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

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

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

1.6命題邏輯在計算機學科中的應用

1.6.1

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

方法如下:

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

運行結(jié)果

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

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

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

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

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

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

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

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