離散數學課程中主范式求解問題的教學研究

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

【關鍵詞】離散數學 真值表 主合取范式 主析取范式

【中圖分類號】G64 【文獻標識碼】A 【文章編號】2095-3089（2017）17-0131-01

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

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

1.由真值表如何列寫對應的公式

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

例：按下述的真值表列寫其對應的公式

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”的行也成立嗎？答案是肯定的。因為上述表達式已經涵蓋了這兩個極小項為1時變量取值的全部情況，對于其他兩種變量取值情況，由極小項的性質，肯定二者真值均為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”的行也成立嗎？答案是肯定的。因為上述表達式已經涵蓋了這兩個極大項為0時變量取值的全部情況，對于其他兩種變量取值情況，由極大項的性質，肯定二者真值均為1，則合取后亦為1。

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

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

（1）求主析取范式

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

（2）求主析取范式

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

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

3.結論

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

參考文獻：

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

作者簡介：

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