逻辑代数与集合理论的融合教学

熊小兵

摘要：文章在对逻辑问题进行代数建模的基础上，阐释了集合理论和逻辑代数的内在联系，对集合和逻辑代数的基本理论做了对比分析，同时也对相关的问题做了探讨，说明了逻辑代数和集合理论融合教学的切实可行性。

关键词：集合;命题;逻辑;逻辑代数

中图分类号：G642        文献标识码：A

文章编号：1009-3044（2022）18-0120-03

开放科学（资源服务）标识码（OSID）：

计算机相关专业一般都有两门必修基础课程：离散数学和数字逻辑。离散数学的一个重点章节是布尔代数，数字逻辑的一个重点章节是逻辑代数。实际上，布尔代数就是逻辑代数，二者只是采用了不同的表述形式而已。

数字逻辑是计算机硬件技术的重要基础，学好数字逻辑的基础是先学好逻辑代数。逻辑代数的本质是用代数的方法研究逻辑问题，即逻辑问题的代数化。遗憾的是，绝大多数学生在中学时代几乎没有系统地学习过逻辑问题的基础理论。如何在短时间内学好逻辑代数就是学生面临的一个挑战。

一般来说，效率最高的学习方法应该是利用曾经学过并且已经掌握的知识来帮助我们学习并掌握新的知识，也就是主动充分利用学习迁移规律。

中学数学中学习过的集合及其基础理论就是可以利用的对象。

逻辑问题实际上就是命题的真假及其相互关系的问题。逻辑代数的基本公理、定理、公式和集合理论的相关内容惊人相似。为说明这种相似性，首先有必要通过命题沟通集合的基本运算和基本逻辑运算之间的关系，在此基础上，集合问题就变成了逻辑问题。

1 逻辑问题的代数模型

逻辑问题实际上就是命题的真假及其相互关系的问题，逻辑代数的实质就是用代数的方法来研究逻辑问题，这就需要为逻辑问题建立一个代数模型。

定义1：命题的真假可以用常量1（表示“真”）和0（表示“假”）来表示，称为逻辑常量。

定义2：命题本身可以用变量（常用大写字母）来表示，称为逻辑变量。

逻辑变量的值就是命题的真假，即逻辑常量。值恒为1的逻辑变量代表的就是永真命题，而值恒为0的逻辑变量代表的就是永假命题。

设A和B为任意的两个命题，利用A和B可以构造一些新的命题。

定义3：命题“A与B”为“真”当且仅当A和B同时为“真”，称为A和B的“与”命题，简称“与”。

定义4：命题“A或B”为“假”当且仅当A和B同时为“假”，称为A和B的“或”命题，简称“或”。

定义5：命题“非A”为“真”当且仅当A为“假”，称为A的“非”命题，简称“非”。

定义3～5实际上就是规定了命题之间的3种基本运算关系，也就是逻辑变量之间的3种基本运算：与、或、非，及其运算规则。

在数字逻辑中，习惯上用[A?B]或[AB]表示A和B的“与”，即“A与B”;[A+B]表示A和B的“或”，即“A或B”;[A]表示A的“非”，即“非A”。

基于上述运算规则，可以归纳总结出逻辑问题的代数模型，也就是逻辑代数的公理系统。

逻辑代数的公理系统[1-3]：对任意的逻辑变量[A]、[B]、[C]，以及逻辑常量1和0，有：

交换律： [A?B=B?A]、[A+B=B+A]

结合律： [（A?B）?C=A?（B?C）]、[（A+B）+C=A+（B+C）]

分配律： [A?（B+C）=A?B+A?C]、

[A+B?C=（A+B）（A+C）]

0-1律： [A+1=1]，[A?1=A];[A+0=A]，[A?0=0];

互补律： [A+A=1]，[A?A=0]

2 集合与命题

设：[U]为全集，[Φ]为空集，[A]和[B]是[U]的任意两个子集，[x∈U]。

由集合[U]可以确定命题[P：x∈U]，命题[P：x∈U]永远成立，可以用逻辑常量1（真）来表达。

由集合[Φ]可以确定命题[P：x∈Φ]，命题[P：x∈Φ]永远为假，可以用逻辑常量0（假）来表达。

由集合[A]可以确定命题[P：x∈A]，命题[P：x∈A]可能为真或假，可以直接用逻辑变量[A]来表示。

由补集[A]可以确定命题[P：x∈A]，命题[P：x∈A]可能为真或假，可以用逻辑变量[A]的“非”[A]来表达。

由交集[A?B]可以确定命题[P：x∈A?B]，命题[P：x∈A?B]可能为真或假。

定律：命题[P：x∈A?B]可以用逻辑变量[A]和[B]的“与”运算[A?B]来表达。

证明：[P：x∈A?B?P：x∈A and x∈B][?P：x∈A and P：x∈B][?A?B]

由并集[A?B]可以确定命题[P：x∈A?B]，命题[P：x∈A?B]可能为真或假。

定律：命题[P：x∈A?B]可以用逻辑变量[A]和[B]的“或”运算[A+B]来表达。

证明：[P：x∈A?B?P：x∈A or x∈B?A：x∈A or B：x∈B?A+B]

以上建立了集合和命题之间的联系，以及集合的3种基本运算（交、并、补）和命题的3种基本运算（即逻辑运算：与、或、非）之间的联系。

3 集合的基本理论和逻辑代数的基本理论

将集合看成命题时，集合的很多运算规律也适用于命题。

设[U]为全集，[A]、[B]、[C]是[U]的任意子集，同时也用[A]、[B]、[C]表示任意的逻辑变量，以下是集合理论[4]-[5]和逻辑代数的基本定律[1-3]之间的对比分析。

交换律 对集合有：[A?B=B?A]、[A?B=B?A];

对逻辑变量有：[A?B=B?A]、[A+B=B+A]

结合律 对集合有：

[（A?B）?C=A?（B?C）]、[（A?B）?C=A?（B?C）]

对逻辑变量有：

[（A?B）?C=A?（B?C）]、[（A+B）+C=A+（B+C）]

分配律 对集合有：

[A?（B?C）=A?B?A?C]、[A?（B?C）=（A?B）?（A?C）]

对逻辑变量有：[A?（B+C）=A?B+A?C]、[A+B?C=（A+B）（A+C）]

0-1律 对集合有：[A?U=U]，[A?U=A];[A?Φ=A]，[A?Φ=Φ];

对逻辑变量有：[A+1=1]，[A?1=A];[A+0=A]，[A?0=0];

互补律 对集合有：[A?A=U]，[A?A=Φ];对逻辑变量有：[A+A=1]，[A?A=0]

在此基础上，可以很容易得到集合理论和逻辑代数的其他常用定律：

定律1 对全集和空集有：[Φ?Φ=Φ]，[Φ?U=Φ]，[U?Φ=Φ]，[U?U=U]

[Φ?Φ=Φ]，[Φ?U=U]，[U?Φ=U]，[U?U=U]

[U=Φ]，[Φ=U]

对逻辑常量有：[0?0=0]，[0?1=0]，[1?0=0]，[1?1=1];[0+0=0]，

[0+1=1]，[1+0=1]，[1+1=1]，[1=0]，[0=1]

定律2 对集合有：[A?A=A]，[A?A=A];对逻辑变量有：[A?A=A]，[A+A=A]

定律3 对集合有：[A?A?B=A]，[A?（A?B）=A]

对逻辑变量有：[A+A?B=A]，[A（A+B）=A]

定律4 对集合有：[A?A?B=A?B]，[A?（A?B）=A?B]

对逻辑变量有：[A+A?B=A+B]，[A（A+B）=A?B]

定律5 对集合有：[A=A];对逻辑变量有：[A=A]

定律6 对集合有：[A?B=A?B]，[A?B=A?B]

对逻辑变量有：[A?B=A+B]，[A+B=A?B]

定律7 对集合有：

[A?B?A?B=A]，[（A?B）?（A?B）=A]

对逻辑变量有：[A?B+A?B=A]，[（A+B）（A+B）=A]

定律8 对集合有：

[A?B?A?C?B?C=A?B?A?C]

[（A?B）（A?C）（B?C）=（A?B）（A?C）]

对逻辑变量有：[A?B+A?C+B?C=A?B+A?C]

[（A+B）（A+C）（B+C）=（A+B）（A+C）]

4 其他集合和逻辑问题

1）差集问题

由差集[A-B=A?B]可以确定命题[P：x∈A?B]，命题[P：x∈A?B]可以用逻辑表达式[AB]来表示。

2）集合的包含关系与命题的蕴含关系

集合的包含关系[A?B]可以确定命题[P：A→B]，命题[P：A→B]可以用逻辑表达式[A+B=AB]来表示。

3）相等问题

对逻辑变量有：[A=B?A⊙B=1?AB+AB=1]

类似地，对集合有：[A=B?A?B?A?B=U]

分析：[A=B?A?B?A?B=A?A=U]

[A?B?A?B=U?B?（A?B?A?B）=B]

[?B?A?B?B?A?B=B]

[?A?B?Φ=B]

[?A?B=B]

[?B?A]

同理，[A?B]。故[A=B]

4）不等问题

对逻辑变量有：[A≠B?A⊕B=1?AB+AB=1]

类似地，对集合有：[A≠B and A=B?A?B?A?B=U]

分析：[A≠B and A=B?A?B?A?B=U]

[A?B?A?B=U?A?B?A?B=Φ]

[?（A?B）?（A?B）=Φ]

[?A?B?A?B=Φ]

[A?B=Φ and A?B=Φ]

[?A≠B and A=B]

5）集合的划分

对逻辑变量有：

[1=ABC+ABC+ABC+ABC+ABC+ABC+ABC+ABC]

[0=（A+B+C）（A+B+C）（A+B+C）（A+B+C）    ?（A+B+C）（A+B+C）（A+B+C）（A+B+C）]

对集合有：

[U=A?B?C?A?B?C?A?B?C?A?B?C   ?A?B?C?A?B?C?A?B?C?A?B?C]

[Φ=（A?B?C）?（A?B?C）?（A?B?C）?（A?B?C）   ?（A?B?C）?（A?B?C）?（A?B?C）?（A?B?C）]

6）集合表达式的标准式

对任意的逻辑表达式[F]，[F]可以转换成基本与或式、最简与或式以及标准与或式，也可以转换成基本或与式、最简或与式以及标准或与式。

例如：[F（A，B，C）=ABC+AC][=AB+C+AC]

[=ABC+ABC+ABC+ABC+ABC+ABC]

[=ABC+ABC+ABC+ABC+ABC+ABC]

类似地，对任意的集合运算表达式[F]，[F]也有类似的形式，可以称为基本交并式、最简交并式、标准交并式，以及基本并交式、最简并交式、标准并交式。或者，借用离散数学中布尔代数的相关术语，分别称为析取式、合取式[6]。

例如：

5 结语

基于上述分析，在数字逻辑课程的逻辑代数部分教学过程中可以利用学习迁移规律，将学生在中学时代就已经初步接触过的集合论的有关理论（重点是集合的运算规律）迁移到逻辑代数的教学中来，帮助大家快速掌握逻辑代数。

此外，为了提高学生学习逻辑代数的效率和效果，还可以考虑借力差不多同时开设的离散数学中的布尔代数理论。在讲授逻辑代数之初可以告诉学生，在学习过程中，可以将数字逻辑的逻辑代数部分和离散数学的布尔代数部分结合起来学习，互相参照，以此提高学习效率，增强学习效果！

参考文献：

[1] 陈光梦.数字逻辑基础[M].2版.上海：复旦大学出版社，2007.

[2] 何建新，高胜东.数字逻辑设计基础[M].北京：高等教育出版社，2012.

[3] 康磊，李润洲.数字电路设计及Verilog HDL实现[M].2版.西安：西安电子科技大学出版社，2019.

[4] 张峰.集合论基础教程[M].北京：清华大学出版社，2021.

[5] 刘坤起.集合论基础[M].北京：电子工业出版社，2014.

[6] 刘铎.离散数学及应用[M].2版.北京：清华大学出版社，2018.

【通联编辑：王力】