【摘要】《離散數(shù)學(xué)》是我國工科高校教學(xué)體系中的核心基礎(chǔ)課程之一。其中，命題邏輯部分里利用真值表求解命題公式的主范式又是課程的重點內(nèi)容之一。目前常見的離散數(shù)學(xué)教材對該部分的講解均缺乏原理性的介紹，使得學(xué)生理解起來有一定的難度。本文基于命題公式與真值表的等價性，介紹了利用真值表求解命題公式的主范式的原理，為該部分內(nèi)容教學(xué)的深化和系統(tǒng)化提供了較好的參考。

【關(guān)鍵詞】離散數(shù)學(xué) 真值表 主合取范式 主析取范式

【中圖分類號】G64 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2017）17-0131-01

《離散數(shù)學(xué)》在我國各工科高校的教學(xué)體系中均處于核心基礎(chǔ)課程的地位，特別是在計算機(jī)專業(yè)課程體系中扮演著重要角色。命題邏輯部分是該課程的重要組成部分。而在命題邏輯中利用真值表求解命題公式（以下簡稱公式）的主析取范式和主合取范式又是這個部分的重點和難點之一。目前，在我國各高校主要采用的《離散數(shù)學(xué)》教材中，對這個問題的講解均以如何根據(jù)真值表一步一步求出主范式的操作性說明為主，基本上沒有提及其后的原理性內(nèi)容[1]，這樣就對學(xué)生的理解造成了一定的困難。在筆者的教學(xué)過程中，各屆學(xué)生在課后對此均有一定的疑問。

針對這一普遍存在的問題，本文對利用真值表求解公式的主范式的原理進(jìn)行詳細(xì)說明，以期給教學(xué)者提供相關(guān)的教學(xué)參考。

1.由真值表如何列寫對應(yīng)的公式

由公式列寫真值表在每本離散數(shù)學(xué)教材中均有詳細(xì)說明，給出一個公式，總能夠列寫其真值表。下面考慮該問題的逆命題——已知真值表，能否寫出其對應(yīng)的公式呢？答案是肯定的。下面以一個例子說明。

例：按下述的真值表列寫其對應(yīng)的公式

A的真值依賴于P、Q的真值。從表中可見，A取“1”有2種可能，只要一種情況成立，則A為“1”。顯然，這里是“析取”的語義，由此可得：

A=case1∨case2

case1： P=0 Q=0，即？劭P∧？劭Q 為真；

case2： P=0 Q=1，即？劭P∧Q 為真。

綜上可得A=（？劭P∧？劭Q）∨（？劭P∧Q）。

那么，上述做法能保證為真值為“0”的行也成立嗎？答案是肯定的。因為上述表達(dá)式已經(jīng)涵蓋了這兩個極小項為1時變量取值的全部情況，對于其他兩種變量取值情況，由極小項的性質(zhì)，肯定二者真值均為0，則析取后亦為0。

至此，可以得到與真值表等價的公式。

另一方面，從表中可見，A取“0”有2種可能，只要一種情況成立，則A為“0”。顯然，這里是“合取”的語義，由此可得：

A=case3∧case4

case3： P=1 Q=0，即？劭P∨Q 為真；

case4： P=1 Q=1，即？劭P∨？劭Q 為真；

綜上可得A=（？劭P∨Q）∧（？劭P∨？劭Q）。

那么，上述做法能保證為“1”的行也成立嗎？答案是肯定的。因為上述表達(dá)式已經(jīng)涵蓋了這兩個極大項為0時變量取值的全部情況，對于其他兩種變量取值情況，由極大項的性質(zhì)，肯定二者真值均為1，則合取后亦為1。

至此，也可以得到與真值表等價的另一個公式。

2.由真值表求公式的主范式

（1）求主析取范式

由上文的結(jié)論，已知真值表求公式的主析取范式，就是按照公式真值為1的情況列寫極小項，并保證其真值為1，然后將各極小項析取起來，即得主析取范式。對上例而言，即是（？劭P∧？劭Q）∨（？劭P∧Q）。

（2）求主析取范式

由上文的結(jié)論，已知真值表求公式的主合取范式，就是按照公式真值為0的情況列寫極大項，并保證其真值為0，然后將各極大項合取起來，即得主合取范式。對上例而言，即是（？劭P∨Q）∧（？劭P∨？劭Q）。

至此，由真值表求公式的主范式的步驟背后的原理就已經(jīng)交待清楚了。經(jīng)過幾屆學(xué)生的教學(xué)，普遍反映較好，類似問題在考試中出錯的情況也有較大降低。

3.結(jié)論

《離散數(shù)學(xué)》的教學(xué)中，在命題邏輯部分利用真值表求解命題公式的主析取范式和主合取范式是課程的重點和難點之一。本文討論了由真值表求與之等價的命題公式的原理，并以此出發(fā)，解釋了如何利用真值表求解主范式的步驟，為離散數(shù)學(xué)中命題邏輯部分教學(xué)的深化打下了良好的基礎(chǔ)。

參考文獻(xiàn)：

[1]離散數(shù)學(xué). 胡新啟（編著）. 武漢大學(xué)出版社. 湖北，2007.

作者簡介：

李凡（1972.2-），男，漢族，江蘇南通人，講師，博士，研究方向為計算機(jī)應(yīng)用技術(shù)。