離散數學中命題邏輯的應用研究

楊井榮，李思莉

(成都理工大學 工程技術學院 計算機科學系，四川 樂山 614007)

0 引 言

計算機算法的實現不僅依靠硬件，還必須依靠那些能夠讓硬件運行下來的各種編制的程序軟件。計算機硬件是由很多邏輯電路所組成的，而邏輯電路是建立在布爾代數的命題邏輯的基礎上的，命題邏輯運算就可以變成布爾代數的演算[1]。可見，計算機硬件與邏輯之間的這種關聯直接導致計算機軟件與邏輯之間存在密不可分的聯系。編程的過程也是算法形成的過程，算法是在計算機功能的基礎上完成的[2]。現實中，計算機的操作是在基本的邏輯運算基礎上生成算法，并最終用這些基本的運算元來代替的計算完成的[3]。

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

1 命題邏輯在計算機語言中的運用

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

1.1 推理問題

例：一個宿舍里有A、B、C、D、E五人，現在調查這些人的畢業去向問題。

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

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

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

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

(5)E不出國。

解：對簡單命題進行形式化。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 如何分工

例：在一所高中，學校每天安排四個人分別打掃學校操場，教學樓，辦公樓以及食堂這四個地方的衛生。在某個周一，輪到了甲，乙，丙，丁四個人打掃衛生。但是，學校監督人員在進行例行衛生檢查時發現這四個地方的衛生都不合格，所以學校要調查清楚他們之間的分工情況。當學校在向學生調查他們彼此間的分工時，得到了如下的事實：

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

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

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

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

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

請根據以上事實，確定甲乙丙丁四人分別應負責哪個地方衛生？

解：對簡單命題進行形式化。

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

r：甲打掃教學樓；s：丙打掃教學樓；

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)構造性二難

(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)合取引入所以，甲打掃教學樓(r)，乙打掃食堂(u)，丁打掃辦公樓(n)，丙打掃操場。

其實，這類問題通過表格的形式(見表1)，用窮舉法可以非常快速地求解[9]。

表1 窮舉法求解分工問題

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

1.3 邏輯學家的推理

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

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

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

解：簡單命題形式化。

p：戰士乙(不妨假設為誠實人)判斷A門是死門

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

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

根據題意可得真值如表2所示。

表2 生死門真值表

即戰士甲的回答是“是”時，A門是生門，邏輯學家可從A門離去；

當戰士甲的回答是“否”時，A門是死門，邏輯學家從B門離去。

1.4 程序下載

例：設有一個在Internet上下載新聞的程序[11]，為避免程序產生死循環和重復下載同一個新聞條目，程序必須根據下述4個條件對給定的一個新聞條目判斷是否執行下載任務：

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

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

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

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

執行下載任務的規劃是：

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

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

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

通過命題邏輯中所學的知識，設計一個真值表，判斷程序是否應該執行程序[12]。

解：其對應的真值表如表3所示。

表3 程序下載真值表

1.5 人員錄取方案

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

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

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

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

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

解：對簡單命題進行形式化。A：錄取A；B：錄取B；C：錄取C。

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

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

表4 人員錄取真值表

續表4

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

1.6 排隊論的應用

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

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

則根據題意，有：

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

(1)

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

(2)

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

(3)

因為真命題的合取仍為真命題，所以：

(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 命題邏輯在計算機電路設計中的應用

密碼鎖問題。

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

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

表5 密碼鎖問題真值表

據表5，得：

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

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

3 結束語

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

總之，在計算機科學的應用中不論是硬件設計還是軟件設計都離不開邏輯學的應用[20]，邏輯學在計算機科學和人工智能領域都占有基礎性地位[21]。現代邏輯學與計算機科學與技術相互融合將進一步推動計算機技術的發展[22]。