離散數(shù)學(xué)中命題邏輯的應(yīng)用研究

楊井榮，李思莉

(成都理工大學(xué) 工程技術(shù)學(xué)院 計(jì)算機(jī)科學(xué)系，四川 樂山 614007)

0 引 言

計(jì)算機(jī)算法的實(shí)現(xiàn)不僅依靠硬件，還必須依靠那些能夠讓硬件運(yùn)行下來的各種編制的程序軟件。計(jì)算機(jī)硬件是由很多邏輯電路所組成的，而邏輯電路是建立在布爾代數(shù)的命題邏輯的基礎(chǔ)上的，命題邏輯運(yùn)算就可以變成布爾代數(shù)的演算[1]?？梢?，計(jì)算機(jī)硬件與邏輯之間的這種關(guān)聯(lián)直接導(dǎo)致計(jì)算機(jī)軟件與邏輯之間存在密不可分的聯(lián)系。編程的過程也是算法形成的過程，算法是在計(jì)算機(jī)功能的基礎(chǔ)上完成的[2]?，F(xiàn)實(shí)中，計(jì)算機(jī)的操作是在基本的邏輯運(yùn)算基礎(chǔ)上生成算法，并最終用這些基本的運(yùn)算元來代替的計(jì)算完成的[3]。

命題邏輯是現(xiàn)代邏輯較簡單、較基本的組成部分,它不考慮把命題分析成個體詞、謂詞和量詞等非命題成分的組合,只研究由命題和命題聯(lián)結(jié)詞構(gòu)成的復(fù)合命題，特別是研究命題聯(lián)結(jié)詞的邏輯性質(zhì)和推理規(guī)律[4]。命題邏輯分為經(jīng)典命題邏輯和非經(jīng)典命題邏輯,后者如構(gòu)造邏輯、模態(tài)邏輯等邏輯系統(tǒng)中的命題邏輯部分[4]。歷史上最早研究命題邏輯的是古希臘斯多阿學(xué)派的哲學(xué)家，現(xiàn)代對命題邏輯的研究始于19世紀(jì)中葉的G.布爾，G.弗雷格則于1879年建立了第一個經(jīng)典命題邏輯的演算系統(tǒng)[5]。命題邏輯是研究關(guān)于命題如何通過一些邏輯連接詞構(gòu)成更復(fù)雜的合理以及邏輯推理的方法[6]。

1 命題邏輯在計(jì)算機(jī)語言中的運(yùn)用

邏輯推理和判斷方面的問題,用常規(guī)的方法很難或者根本無法求解出來,這個時候就理所當(dāng)然地想到使用計(jì)算機(jī)編程求解。使用語言編程不一定就能夠輕易地解決問題,還涉及到解決問題的算法設(shè)計(jì)問題。因此算法的設(shè)計(jì)就是解決各種問題的核心和關(guān)鍵。通過詳述若干有關(guān)邏輯推理和判斷問題的推理過程有助于設(shè)計(jì)出更高效的算法[7-8]。

1.1 推理問題

例：一個宿舍里有A、B、C、D、E五人，現(xiàn)在調(diào)查這些人的畢業(yè)去向問題。

(1)A與B中必有一個人出國；

(2)若A出國，則C不出國；

(3)若D出國，則E也出；

(4)若D不出國，則C出國；

(5)E不出國。

解：對簡單命題進(jìn)行形式化。A：A出國；B：B出國；C：C出國；D：D出國；E：E出國。

形式化前提：A∨B，A→┐C，D→E，┐D→C，┐E

求解過程如下：

(1)┐E 前提引入

(2)D→E 前提引入

(3)┐D (1)(2)拒取式

(4)┐D→C 前提引入

(5)C (3)(4)假言推理

(6)A→┐C 前提引入

(7)┐A (5)(6)拒取式

(8)A∨B 前提引入

(9)B (7)(8)析取三段論

也就是說，B出國。

1.2 如何分工

例：在一所高中，學(xué)校每天安排四個人分別打掃學(xué)校操場，教學(xué)樓，辦公樓以及食堂這四個地方的衛(wèi)生。在某個周一，輪到了甲，乙，丙，丁四個人打掃衛(wèi)生。但是，學(xué)校監(jiān)督人員在進(jìn)行例行衛(wèi)生檢查時發(fā)現(xiàn)這四個地方的衛(wèi)生都不合格，所以學(xué)校要調(diào)查清楚他們之間的分工情況。當(dāng)學(xué)校在向?qū)W生調(diào)查他們彼此間的分工時，得到了如下的事實(shí)：

(1)我在給老師送作業(yè)時，看到打掃辦公樓的不是同學(xué)丙也不是同學(xué)甲；

(2)打掃教學(xué)樓的肯定是甲和丙中的一個；

(3)如果丁在打掃食堂，那么在辦公樓里打掃的那個人應(yīng)該是甲；

(4)我在食堂吃早飯時，看到打掃食堂的是丁和乙中的一個；

(5)如果乙在打掃食堂，我可以確定打掃教學(xué)樓的就是我朋友甲了。

請根據(jù)以上事實(shí)，確定甲乙丙丁四人分別應(yīng)負(fù)責(zé)哪個地方衛(wèi)生？

解：對簡單命題進(jìn)行形式化。

p：甲打掃辦公樓；q：丙打掃辦公樓；

r：甲打掃教學(xué)樓；s：丙打掃教學(xué)樓；

t：丁打掃食堂；u：乙打掃食堂。

m：乙打掃辦公樓；n：丁打掃辦公樓

形式化前提：┐p∧┐q，(r∧┐s)∨(┐r∧s)，t→p，t∨u，u→r，p∨q∨m∨n，p→┐q，r→┐s，t→┐u，p→┐r，q→┐s，u→┐m 。

求解過程如下：

(1)t→p 前提引入

(2)u→r 前提引入

(3)t∨u 前提引入

(4)p∨r (1)(2)構(gòu)造性二難

(5)┐p∧┐q 前提引入

(6)┐p (5)化簡

(7)┐q (5)化簡

(8)r (4)(6)析取三段論

(9)r→┐s 前提引入

(10)┐s (8)(9)析取三段論

(11)t→p 前提引入

(12)┐t (6)(11)拒取式

(13)t∨u 前提引入

(14)u (12)(13)析取三段論

(15)u→┐m 前提引入

(16)┐m (14)(15)假言推理

(17)p∨q∨m∨n 前提引入

(18)n (17)(5)(8)(16)析取三段論

(19)r∧u∧n (8)(14)(18)合取引入所以，甲打掃教學(xué)樓(r)，乙打掃食堂(u)，丁打掃辦公樓(n)，丙打掃操場。

其實(shí)，這類問題通過表格的形式(見表1)，用窮舉法可以非?？焖俚厍蠼鈁9]。

表1 窮舉法求解分工問題

由表1知：甲打掃教學(xué)樓；乙打掃食堂；丙打掃操場；丁打掃辦公樓。

1.3 邏輯學(xué)家的推理

例：有一邏輯數(shù)學(xué)家誤入某個部落，他被拘于牢，酋長意欲放行，他對邏輯學(xué)家說：“今有兩門(A、B)，一為生門，一為死門，你可以開啟任意一門。為協(xié)助你離開，今加派兩名戰(zhàn)士(甲、乙)，負(fù)責(zé)回答你提出的任何問題。惟可慮者，此兩戰(zhàn)士中一名天性誠實(shí)，一名說謊成性，今后生死由你自己選擇?！盵10]

邏輯學(xué)家沉思片刻，走到A門前，問戰(zhàn)士甲：“戰(zhàn)士乙將判斷A門為死門，對嗎”？戰(zhàn)士甲回答“對”。邏輯學(xué)家開A門從容而去。

試用真值表及范式說明理由。

解：簡單命題形式化。

p：戰(zhàn)士乙(不妨假設(shè)為誠實(shí)人)判斷A門是死門

q：戰(zhàn)士甲(不妨假設(shè)為說謊人)對戰(zhàn)士甲的判斷(q=┐p)

r：A門是生門(r=┐p)

根據(jù)題意可得真值如表2所示。

表2 生死門真值表

即戰(zhàn)士甲的回答是“是”時，A門是生門，邏輯學(xué)家可從A門離去；

當(dāng)戰(zhàn)士甲的回答是“否”時，A門是死門，邏輯學(xué)家從B門離去。

1.4 程序下載

例：設(shè)有一個在Internet上下載新聞的程序[11]，為避免程序產(chǎn)生死循環(huán)和重復(fù)下載同一個新聞條目，程序必須根據(jù)下述4個條件對給定的一個新聞條目判斷是否執(zhí)行下載任務(wù)：

條件一：該新聞條目在程序的前一次執(zhí)行中已下載，用命題符號E表示；

條件二：該新聞條目在程序的本次執(zhí)行中已下載，用命題符號N表示；

條件三：該新聞條目是一個動態(tài)更新的新聞條目，用命題符號D表示；

條件四：該新聞條目已過期，程序需要重新下載，用命題符號Q表示。

執(zhí)行下載任務(wù)的規(guī)劃是：

(1)該新聞條目在程序的前一次執(zhí)行中未下載，則不論其其他條件如何，一定執(zhí)行下載。┐E→A

(2)如果是一條動態(tài)新聞，并且該新聞條目在程序的本次執(zhí)行中沒有下載，則執(zhí)行下載，否則不執(zhí)行下載；D∧┐N→A

(3)如果新聞條目在程序的前一次執(zhí)行中已下載，并且該新聞條目在程序的本次執(zhí)行中沒有下載，那么：如果是一個過期的新聞條目，則執(zhí)行下載，否則不執(zhí)行下載。

通過命題邏輯中所學(xué)的知識，設(shè)計(jì)一個真值表，判斷程序是否應(yīng)該執(zhí)行程序[12]。

解：其對應(yīng)的真值表如表3所示。

表3 程序下載真值表

1.5 人員錄取方案

例：某公司要從3名應(yīng)聘人A、B、C中錄取1～2名進(jìn)行簽約。根據(jù)面試情況，錄取時要滿足以下條件：

(1)若錄取A，則也錄取C。

(2)若錄取B，則不錄取C。

(3)若不錄取C，則同時錄取A與B。

請用命題邏輯推斷可能的錄取方案[13]。

解：對簡單命題進(jìn)行形式化。A：錄取A；B：錄取B；C：錄取C。

則形式化前提：A→C，B→┐C，┐C→A∧B。

則G=(A→C)∧(B→┐C)∧(┐C→A∧B)，則G的真值表如表4所示。

表4 人員錄取真值表

續(xù)表4

從真值表可以看出，有兩種錄取方式：A不錄取，B不錄取，C錄??；A錄取，B不錄取，C錄取。

1.6 排隊(duì)論的應(yīng)用

例:設(shè)A、B、C、D共4個人進(jìn)行百米競賽，觀眾甲、乙、丙對比賽的結(jié)果進(jìn)行預(yù)測[14]。甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每個人的預(yù)測結(jié)果都各對一半。試問實(shí)際名次如何(假設(shè)無并列者)？

解：設(shè)Ai表示A第i名，Bi表示B第i名，Ci表示C第i名，Di表示D第i名，i=1,2,3,4。

則根據(jù)題意，有：

(C1∧┐B2)∨(┐C1∧B2)?1

(1)

(C2∧┐D3)∨(┐C2∧D3)?1

(2)

(A2∧┐D4)∨(┐A2∧D4)?1

(3)

因?yàn)檎婷}的合取仍為真命題，所以：

(1)∧(2)

?((C1∧┐B2)∨(┐C1∧B2))∧((C2∧┐D3)∨(┐C2∧D3))

?((C1∧┐B2)∧(C2∧┐D3))∨((C1∧┐B2)∧(┐C2∧D3))∨((┐C1∧B2)∧(C2∧┐D3))∨((┐C1∧B2)∧(┐C2∧D3))

?(C1∧┐B2∧C2∧┐D3)∨(C1∧┐B2∧┐C2∧D3)∨(┐C1∧B2∧C2∧┐D3)∨(┐C1∧B2∧┐C2∧D3)

由于C1和C2不可能同時成立，因此(C1∧┐B2∧C2∧┐D3)?0

由于B2和C2不可能同時成立，由于(┐C1∧B2∧C2∧┐D3)?0,所以(1)∧(2)?(C1∧┐B2∧┐C2∧D3)∨(┐C1∧B2∧┐C2∧D3)?1

(4)

(3)∧(4)

?((A2∧┐D4)∨(┐A2∧D4))∧((C1∧┐B2∧┐C2∧D3)∨(┐C1∧B2∧┐C2∧D3))

?(A2∧┐D4∧C1∧┐B2∧┐C2∧D3)∨(A2∧┐D4∧┐C1∧B2∧┐C2∧D3)∨(┐A2∧D4∧C1∧┐B2∧┐C2∧D3)∨(┐A2∧D4∧┐C1∧B2∧┐C2∧D3)

由于A2和B2不可能同時成立，因此(A2∧┐D4∧┐C1∧B2∧┐C2∧D3)?0

由于D3和D4不可能同時成立，因(┐A2∧D4∧C1∧┐B2∧┐C2∧D3)?0

由于D3和D4不可能同時成立，因(┐A2∧D4∧┐C1∧B2∧┐C2∧D3)?0

所以(3)∧(4)?(A2∧┐D4∧C1∧┐B2∧┐C2∧D3)?1

綜上，知：A第二，B第四，C第一，D第三。

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

密碼鎖問題。

例：為了安全，很多民宅或商鋪門上都會安裝帶有報警器的密碼鎖?，F(xiàn)有一種密碼鎖，工作原理如下：鎖的控制電路中有三個按鈕A，B，C和—個報警裝置。當(dāng)三個按鈕同時按下，或只有A，B兩鈕按下，或只有A，B中之一按下時，鎖被打開；當(dāng)不符合上述開鎖信號時，電鈴發(fā)響報警。請?jiān)O(shè)計(jì)出合理的方案來達(dá)到這種效果[15]。

解：用真值表法(見表5)來解決這個問題。令開鎖信號G=(A∧B∧C)∨(A∧B)∨(A∨B)。

表5 密碼鎖問題真值表

據(jù)表5，得：

開鎖信號G=Π(0，1)=(A∨B∨C)∧(A∨B∨┐C)；

報警信號F=(┐A∧┐B∧┐C)∨(┐A∧┐B∧C)。

3 結(jié)束語

命題邏輯在計(jì)算機(jī)和人工智能領(lǐng)域有廣泛的應(yīng)用[16]。該文主要通過推理問題、分工問題、程序下載問題、排隊(duì)論問題、人員錄取問題和密碼鎖問題論述命題邏輯的應(yīng)用[17-19]。

總之，在計(jì)算機(jī)科學(xué)的應(yīng)用中不論是硬件設(shè)計(jì)還是軟件設(shè)計(jì)都離不開邏輯學(xué)的應(yīng)用[20]，邏輯學(xué)在計(jì)算機(jī)科學(xué)和人工智能領(lǐng)域都占有基礎(chǔ)性地位[21]?，F(xiàn)代邏輯學(xué)與計(jì)算機(jī)科學(xué)與技術(shù)相互融合將進(jìn)一步推動計(jì)算機(jī)技術(shù)的發(fā)展[22]。