數(shù)理邏輯中范式推算的程序化研究與實(shí)現(xiàn)

楊劍蘭，周青

（昆明醫(yī)科大學(xué)海源學(xué)院，云南 昆明650106)

0 引言

離散數(shù)學(xué)是研究有離散結(jié)構(gòu)的系統(tǒng)的學(xué)科，譬如，繪制一條直線段的墨水痕跡并非連續(xù)，而是由有限多個離散的點(diǎn)組成，這與人類一貫的認(rèn)知不同。而當(dāng)計(jì)算機(jī)打印這條線段時(shí)就是以打點(diǎn)的方式打印出來的[1]，因此離散數(shù)學(xué)思想與計(jì)算機(jī)工作原理密切關(guān)聯(lián)，并且更加符合萬事萬物本身的底層特性。其中數(shù)理邏輯部分是用符號的方法研究關(guān)于命題推理、證明等的問題。丘成桐曾說：“大道至簡，是對數(shù)學(xué)之美的歸納，最簡單的數(shù)學(xué)，從1=1開始，到1+1=2，1+2=3，不停推導(dǎo)下去。人類通過這種方式，認(rèn)識到自然數(shù)，從而有了數(shù)學(xué)”[2]。因此，在數(shù)理邏輯中“邏輯”是一種形式語言，用于表示能得出結(jié)論的信息，邏輯問題可轉(zhuǎn)變?yōu)橛煞柵c連接詞構(gòu)成的命題公式，并且進(jìn)一步轉(zhuǎn)換為等價(jià)的標(biāo)準(zhǔn)范式，通過標(biāo)準(zhǔn)范式可輕易實(shí)現(xiàn)排除錯誤的邏輯關(guān)系、找到符合問題本身邏輯的命題狀態(tài)，快速達(dá)到實(shí)現(xiàn)推理和證明出準(zhǔn)確結(jié)論。

本文針對求解命題公式的主析取范式與主合取范式，在真值表法基礎(chǔ)上，分析解釋了構(gòu)造析?。ê先。┓妒綍r(shí)以成真（假）指派反推對應(yīng)?。ù螅╉?xiàng)的原因，并結(jié)合計(jì)算機(jī)語言程序設(shè)計(jì)將該解法從理論求解遷移至計(jì)算機(jī)工具求解，給出了程序設(shè)計(jì)的具體流程和代碼，從而更好地實(shí)踐“以解決問題為導(dǎo)向掌握和運(yùn)用工具”學(xué)習(xí)模式以及幫助學(xué)習(xí)者建立定理自動化證明的認(rèn)知，進(jìn)一步理解人工智能基礎(chǔ)。

1 范式

在布爾邏輯中，主析取范式與主合取范式是邏輯公式的標(biāo)準(zhǔn)規(guī)范化，其中主析取范式是由各個所涉及命題變元的合取子句即最小項(xiàng)的析?。恢骱先》妒绞怯筛鱾€所涉及命題變元的析取子句即最大項(xiàng)的合取。作為規(guī)范形式，它們在自動定理證明中發(fā)揮作用，在邏輯問題中將局面直觀展現(xiàn)以更清晰地推出結(jié)論。比如，以下邏輯謎題：A，B，C，D 四人中要派兩人去參加教學(xué)比賽，按下述三個條件有幾種派法？如何派？

1) 若A去，則C和D中要去一人；

2) B和C不能都去；

3) C去則D留下。

將命題A，B，C，D 分別表示A 參加、B 參加、C 參加、D參加，則該邏輯謎題轉(zhuǎn)換為命題公式：

(A→((C∧?D)∨(?C∧D)))∧?(B∧C)∧(C→?D)，進(jìn)一步轉(zhuǎn)化為等價(jià)主析取范式并刪去與題意矛盾的項(xiàng)目后得到：(?A∧B∧?C∧D)∨(A∧?B∧?C∧D)∨(A∧?B∧C∧?D)，故派法為：B∧D，或A∧D，或A∧C。共三種派法。

2 計(jì)算機(jī)程序化

2.1 范式連結(jié)詞與程序邏輯運(yùn)算符

通過命題公式的等價(jià)轉(zhuǎn)換，任何連結(jié)詞都可轉(zhuǎn)換為：?（取反），∧（合取），∨（析?。┤N最為基本和簡單的連結(jié)關(guān)系，在主析取范式和主合取范式中，規(guī)定只能含有以上三種連結(jié)詞，并且每個符號右邊須緊跟單個命題變元。在計(jì)算機(jī)Java 程序中有三個基本的邏輯運(yùn)算符與該三個連結(jié)詞對應(yīng)，如表1。

表1 命題連結(jié)詞與對應(yīng)的Java語言邏輯運(yùn)算符

當(dāng)命題公式中含有→（蘊(yùn)含），?（當(dāng)且僅當(dāng)）連結(jié)詞時(shí)，根據(jù)連結(jié)詞邏輯性質(zhì)特征，可得出對應(yīng)的程序語句，如設(shè)置前提為P，后件為Q，則P→Q真值符合以下規(guī)律：if(!P){(P→Q)=true;}；if(Q){(P→Q)=true;}。P?Q真值符合以下規(guī)律：if(P){if(Q){(P?Q)=true;}}else{ if(!Q){(P?Q)=true;} }。

2.2 真值表法求主析?。ê先。┓妒?/h3>

n 表示命題變元數(shù)量，求解主析取范式與主合取范式，利用真值表法可歸為以公式成真或成假賦值反推所對應(yīng)的包含n 個命題變元的各個小項(xiàng)組mi的真值指派問題，為方便觀察公式成真和成假時(shí)各命題變元的真假狀態(tài)，范式需包含對所有命題變元的規(guī)范整理，在構(gòu)造主析取范式時(shí)：結(jié)合析取式的特征，能夠使析取式成假的真值指派條件較為苛刻，只有一組m0∨m1∨...mi在等價(jià)于F 時(shí)可使所有構(gòu)成析取范式的小項(xiàng)為假，但此時(shí)對應(yīng)的滿足為假的小項(xiàng)組太多，為2n-1組，過于煩瑣。如命題公式(?P∧Q)∨?R，其真值表如表2。

表2 命題公式(?P∧Q)∨?R真值表

當(dāng)(?P∧Q)∨?R 為0，對應(yīng)的P，Q，R 真值指派有3組，為序號②，⑥, ⑧，如：此時(shí)序號②對應(yīng)表3。

表3 (?P∧Q)∨?R為0時(shí)對應(yīng)的P，Q，R真值指派組②

此時(shí)為1的小項(xiàng)唯有?P∧?Q∧R，其余可構(gòu)造出真值為0的小項(xiàng)23-1=7項(xiàng)，運(yùn)算量大效率低下；

而當(dāng)(?P∧Q)∨?R 為1，對應(yīng)的P，Q，R 真值指派有5 組，為序號①，③, ④，⑤，⑦，如：此時(shí)序號①對應(yīng)表4。

表4 (?P∧Q)∨?R為1時(shí)對應(yīng)的P，Q，R真值指派組①

根據(jù)P、Q、R 三個命題變元的真值指派0、0、0，只可構(gòu)造出真值為1的小項(xiàng)1項(xiàng)，即?P∧?Q∧?R，除此之外剩余小項(xiàng)23-1=7項(xiàng)為0，運(yùn)算量小效率高。

因此在構(gòu)造主析取范式時(shí)，采取其真值表中公式成真指派時(shí)所對應(yīng)的最小項(xiàng)的析取式，可反推此時(shí)至少有一組所包含的小項(xiàng)值為真，由此精準(zhǔn)構(gòu)造唯一一組對應(yīng)的小項(xiàng)，將公式所有成真指派時(shí)對應(yīng)的各個唯一小項(xiàng)析取，就能更高效地得到值為真的主析取范式。在構(gòu)造主合取范式時(shí)：結(jié)合合取式的特征：能夠使合取式成真的真值指派條件較為苛刻，只有一組，在該組真值賦值下，可使所有構(gòu)成合取范式的大項(xiàng)為真，才能滿足使合取范式為真，但大項(xiàng)為真對應(yīng)的大項(xiàng)組太多，為2n-1組，過于煩瑣，因此在構(gòu)造主析取范式時(shí)，采取其真值表中成假指派所對應(yīng)的最大項(xiàng)的合取式。可反推此時(shí)至少有一組所包含的大項(xiàng)值為假，由此精準(zhǔn)構(gòu)造唯一一組對應(yīng)的大項(xiàng)，將公式所有成假指派時(shí)對應(yīng)的各個唯一大項(xiàng)合取，就能更高效地得到值為假的主合取范式。

基于上述原因，得出定理：

1) 一個公式的真值為T(1) 的指派所對應(yīng)的小項(xiàng)的析取即為此公式的主析取范式[3]；

2) 一個公式的真值為F(0) 的指派所對應(yīng)的大項(xiàng)的合取即為此公式的主合取范式[3]。

3 用計(jì)算機(jī)程序求解命題公式的主析取（合?。┓妒?/h2>

3.1 算法思想

1) 統(tǒng)計(jì)命題公式的變元數(shù)量n，利用多重for循環(huán)給出所有n個變元所有真值指派2n個組合；

2) 使用數(shù)組保存所有命題變元真值指派下公式的真值；

3) 根據(jù)定理，構(gòu)造主析?。ê先。┓妒?。

3.2 對應(yīng)程序思路

1) 將用戶輸入的中綴表達(dá)式進(jìn)行for 循環(huán)將公式中的字符遍歷，并轉(zhuǎn)換為逆波蘭表達(dá)式用棧來存儲；

2) 在逆波蘭表達(dá)式中判斷命題變元的數(shù)量；

3) 將n 個命題變元共2n個真值組存儲在數(shù)組中，循環(huán)遍歷輸出真值表；

4) 求主析?。ê先。┓妒綍r(shí)：當(dāng)命題公式真值為1(0) 時(shí)對應(yīng)的變元的合?。ㄎ鋈。┙Y(jié)果即?。ù螅╉?xiàng)應(yīng)為成真（假），根據(jù)小（大）項(xiàng)性質(zhì)，應(yīng)讓每一個對應(yīng)的變元當(dāng)前值改造為真（假），則若對應(yīng)變元值為0(1) 輸出此變元的非（變元），否則直接輸出變元（變元的非），變元與變元之間用合?。ㄎ鋈。┻B結(jié)詞連結(jié)，項(xiàng)與項(xiàng)之間用析?。ê先。┞?lián)結(jié)詞連接。

程序核心代碼如下：

3.3 上機(jī)驗(yàn)證

求解命題公式(?P∧Q)∨?R的主析?。ê先。┓妒?/p>

在IDEA下運(yùn)行結(jié)果正確，如圖1：

圖1 Java程序運(yùn)行結(jié)果

4 結(jié)束語

符號主義人工智能的思維對應(yīng)于人類的演繹式思維[4]，而邏輯演繹的符號形式化即數(shù)理邏輯，主析?。ê先。┓妒阶鳛閿?shù)理邏輯中極為有價(jià)值的命題公式呈現(xiàn)方式，將包含多個命題變元的公式以滿足解讀規(guī)范的標(biāo)準(zhǔn)連結(jié)了各個命題變元與連結(jié)詞。求解主析?。ê先。┓妒降姆椒ㄓ姓嬷当矸ㄒ约暗戎笛菟惴?，其中真值表法對應(yīng)的求解過程更貼合計(jì)算機(jī)對離散量處理的方式，同時(shí)，人類智能本身就是在各個層次上使用符號，如抽象思維、邏輯、語言，因此符號人工智能研究在某種意義上就是對人類理性思維的研究[5]，理解真值表法的求解思路并轉(zhuǎn)換為對應(yīng)的程序語言對培養(yǎng)人類自身計(jì)算思維與認(rèn)識人工智能都有很大的幫助。