离散数学课程中主范式求解问题的教学研究

【摘要】《离散数学》是我国工科高校教学体系中的核心基础课程之一。其中，命题逻辑部分里利用真值表求解命题公式的主范式又是课程的重点内容之一。目前常见的离散数学教材对该部分的讲解均缺乏原理性的介绍，使得学生理解起来有一定的难度。本文基于命题公式与真值表的等价性，介绍了利用真值表求解命题公式的主范式的原理，为该部分内容教学的深化和系统化提供了較好的参考。

【关键词】离散数学 真值表 主合取范式 主析取范式

【中图分类号】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-），男，汉族，江苏南通人，讲师，博士，研究方向为计算机应用技术。