对《离散数学》课程集合状态成员表法的探索与思考

Exploration and Reflection on the Member Table Method of Set States in the Course of “Discrete Mathematics”

摘要: 《离散数学》是理工科大学生的专业核心课程，而集合论是《离散数学》的基础部分。集合论中的集合代数包含的内容多，其中求一个集合的幂集、证明两个集合相等是非常重要的内容。怎样掌握这些知识点，是许多学生十分关心的问题。本文给出了解决上述问题的通用方法以及集合状态成员表法，并将通用方法与集合状态成员表法进行了对比，分别给出了他们的优劣性。集合状态成员表法是解决相关问题的一种简单的方法，希望本文的研究对学生掌握相关知识点起到一定的促进作用。

Abstract: “Discrete Mathematics” is the core course of science and engineering college students, and set theory is the fundamental part of “Discrete Mathematics”. The set algebra in set theory contains a lot of content, among which finding the power set of a set and proving that two sets are equal is a very important content. How to master these knowledge points is a concern for many students. This article provides general methods and a set state member table method to solve the above problems, compares the general method with the set state member table method and presents their advantages and disadvantages. The set state member table method is a simple way to solve related problems. It is hoped that this study will play a certain promoting role in helping students master relevant knowledge points.

1. 引言

离散数学是计算机科学、信息技术和数学的一个重要分支，它在计算机科学、信息技术、人工智能、控制理论等领域具有广泛的应用。集合论不仅是离散数学的基础部分，还是数论、概率论与数理统计、集合代数、拓扑学等其他数学分支的基础。集合论中，集合的幂集和集合相等是两个重要的内容，大量学者对这两个方面进行了研究。

鱼先锋等人[1]首先给出了集合子集特征向量函数、集合子集特征向量的特征函数和集合子集特征函数的定义。其次，给出了集合幂集特征矩阵的概念来研究集合幂集特征矩阵的性质。最后，将幂集特征矩阵应用到自动生成集合幂集和命题公式真值表。

郑艳梅等人[2]首先根据集合论与数理逻辑、图论的关系，说明了集合论是表示工具。其次，由于二元关系始于集合中的元素，产生于元素之间，本身即定义在集合之上，所以只有正确理解集合、元素的概念，才能准确地认识二元关系，说明了集合论是讨论关系的根基。最后在代数系统中，集合以及集合间的运算是以代数系统的一个应用实例形式而存在，说明了集合论是代数系统的应用实例。

鱼先锋等人[3]先利用特征向量表示集合和集合子集，再根据特征向量写出幂集的所有元素，0对应集合中该位置元素不在当前幂集元素中，1对应集合中该位置元素在当前幂集元素中，从而得到用特征向量表示的幂集。并且，给出了求幂集特征向量的另一种算法，即递归生成集合幂集。

段景辉[4]利用命题演算排中律和矛盾律思想，以及结合了命题公式真值表方法，提出了集合成员表的构造方法。集合成员表法是基于命题公式的真值表而提出的，类似命题公式的真值表。首先，考虑一个元素可能属于的集合的每一种组合，用1表示元素属于一个集合，用0表示元素不属于一个集合；然后，确定不同集合的个数，从而确定成员表的行数。这种方法形式简单、易于掌握，更重要的是它揭示了集合恒等式与命题公式恒等式之间的逻辑特性。

赵登科[5]提出了两个集合相等的证明方法，即两个集合相等，当且仅当它们有完全相同的集合成员表。应用命题逻辑中的一种构造真值表的方法来构造集合成员表，结合二进制下的逻辑运算，可有效地解决这个问题。集合有一种重要性质——确定性：一个元素是否属于一个集合是完全确定的。如果我们把集合中的元素看作集合的成员，那么，作为一个成员要么在集合中，要么不在集合中，两者必取其一。其举例说明了运用具有独特结构的集合成员表法能够证明集合等式是否成立。

闫浮[6]说明了集合成员表法与主析取范式(最小项的析取)的一致性。集合成员表法是指集合可以用集合的极小项表示，由集合极小项构成的并式称为集合范式。我们可以看到这几种方法都可以得到结论，但是如果使用集合成员表法，则非常方便于计算机操作，所以设计的软件采用集合成员表法进行证明。

赵佳等人[7]针对离散数学中的数理逻辑与集合论部分知识的教学与实践进行了探讨，从科研工作、上机操作、注重趣味性、类比学习等方面提出了如何增加课堂互动，以提高学生的学习主动性。

申华等人[8]探讨了离散数学中数理逻辑与集合论的数学本质以及内在联系，提出教学过程中把握数学本质，结合其应用性，能有效提高教学效果。

郭丽君[9]提出了通过使用关系矩阵计算方法实现对等价关系的判定，既使得判定工作具有很好的可计算性，也具有更高的科学性，同时也为进一步利用计算机编程辅助手段判断关系的性质、判断关系是否为等价关系提供了可靠的理论依据。

基于以上研究，本文阐述了集合状态成员表法在求集合幂集和证明集合相等两方面的思想及构造。研究了其在求集合幂集和证明集合相等两方面的应用，同时在求集合幂集方面比较了集合状态成员表法与定义法，在证明集合相等方面比较了集合状态成员表法与命题演算法、谓词公式法、等式置换法，对比了它们的优劣性。通过对比可以更进一步地促进学生对求集合幂集和证明集合相等知识点的掌握。

2. 集合幂集的集合状态成员表法的思想及其构造

本章首先阐述集合幂集的定义、性质，然后给出集合状态成员表法在求集合幂集方面的思想及构造，最后把求解集合幂集的定义法与集合状态成员表法进行对比，分别给出他们的优劣性。

2.1. 集合幂集的定义及性质

定义1 [10]：设A为集合，把A的全体子集构成的集合称作A的幂集，记作$P\left(A\right)$ 。幂集的符号化表示为：

$P\left(A\right)=\left\{x|x\subseteq A\right\}$ (1)

性质：若集合A的元素的个数为n，则$P\left(A\right)$ 的元素的个数为2ⁿ。

证明 集合A的零元子集有$C_n^0$ 个，一元子集有$C_n^1$ 个，…，m元子集有$C_n^m$ 个，…，n元子集有$C_n^n$ 个，子集总数为：

$C_n^0+C_n^1+C_n^2+\cdots +C_n^n=2^n$ ，

故$P\left(A\right)$ 的元素的个数为2ⁿ。

例1 设集合$A=\left\{1,2\right\}$ ，求集合A的幂集。

解方法一：定义法

根据幂集定义可得：

$P\left(A\right)=\left\{\varnothing ,\left\{1\right\},\left\{2\right\},\left\{1,2\right\}\right\}$

例2 设集合$A=\left\{a,b,c\right\}$ ，求集合A的幂集。

解方法一：定义法

根据幂集定义可得：

$P\left(A\right)=\left\{\varnothing ,\left\{a\right\},\left\{b\right\},\left\{c\right\},\left\{a,b\right\},\left\{a,c\right\},\left\{b,c\right\},\left\{a,b,c\right\}\right\}$ .

2.2. 集合幂集的集合状态成员表法的思想及其构造和实例对比分析

集合状态成员表类似于命题公式的真值表。集合幂集的集合状态成员表法的思想及其构造如下：

① 集合状态成员表法在求集合幂集方面的思想

首先，设A为集合，集合B是集 合A的子集，用1表示元素x属于集合B，用0表示元素x不属于集合B，其中元素x属于A。

其次，根据元素x是否属于集合B，给出集合B的所有结果。

最后，根据定义1可知集合B的所有结果构成的集合就是集合A的幂集。

② 集合状态成员表法在求集合幂集方面的构造

首先，确定集合A中元素的个数n，那么集合状态成员表就有${\text{2}}^n+\text{1}$ 行、$n+\text{1}$ 列，其中第一行是表头，分别是n个集合元素和1个集合B。

其次，由于集合A有n个元素，故第2行到${\text{2}}^n+\text{1}$ 行分别是2ⁿ种赋值情况，从$00\cdots 0$ 开始，按照二进制加法，每次加1，直至$\text{11}\cdots \text{1}$ 为止。

然后，根据用1表示元素x属于集合B，用0表示元素x不属于集合B，写出集合B在不同赋值情况下的结果。

最后，把集合B的所有结果构成一个集合，该集合就是集合A的幂集。

为了进一步掌握集合幂集的集合状态成员表法的思想及其构造，下面利用集合状态成员表法求解例1和例2。

例1 设集合$A=\left\{1,2\right\}$ ，求集合A的幂集。

解方法一：集合状态成员表法

设集合B为集合A的子集，$x\in \left\{a,b,c\right\}$ ，用1表示元素x属于集合B，用0表示元素x不属于集合B，则利用集合状态成员表法可得集合B在不同赋值情况下的结果如表1所示。

Table 1. Set state member table of example 1

表1. 例1的集合状态成员表

a	b	B
0	0
0	1	{2}
1	0	{1}
1	1	{1, 2}

由于集合B是集合A的子集，根据集合幂集定义可知：

$B=P\left(A\right)=\left\{\varnothing ,\left\{1\right\},\left\{2\right\},\left\{1,2\right\}\right\}$

例2 设集合$A=\left\{a,b,c\right\}$ ，求集合A的幂集。

解方法一：集合状态成员表法

设集合B为集合A的子集，$x\in \left\{a,b,c\right\}$ ，用1表示元素x属于集合B，用0表示元素x不属于集合B，则利用集合状态成员表可得集合B的求值情况如表2所示。

由于集合B是集合A的子集，根据集合幂集定义可知：

$B=P\left(A\right)=\left\{\varnothing ,\left\{a\right\},\left\{b\right\},\left\{c\right\},\left\{a,b\right\},\left\{a,c\right\},\left\{b,c\right\},\left\{a,b,c\right\}\right\}$ .

通过例1和例2可知，定义法和集合状态成员表法求解幂集结果一致。幂集求解的定义法和集合状态成员表法的优劣性如表3所示。

Table 2. Set state member table of example 2

表2. 例2的集合状态成员表

a	b	c	B
0	0	0
0	0	1	{c}
0	1	0	{b}
0	1	1	{b, c}
1	0	0	{a}
1	0	1	{a, c}
1	1	0	{a, b}
1	1	1	{a, b, c}

Table 3. Advantages and disadvantages of definition method and set state member table method

表3. 定义法与集合状态成员表法的优缺点

	优点	缺点
定义法	集合元素较少时，幂集求解过程简单。	集合元素比较多时， 幂集求解过程中容易缺失元素。
集合状态成员表法	可以列出一个集合的全部子集， 进而保证幂集元素的不缺失。	集合元素比较多时，列真值表比较麻烦。

3. 证明集合相等及集合状态成员表法的思想及其构造

本章首先阐述集合相等的定义，然后利用命题演算法、谓词公式法、等式置换法，最后利用集合状态成员表法来证明集合相等，并比较它们的优劣性。

3.1. 集合相等的定义及命题演算法、谓词公式法、等式置换法

定义2 [10]：设A、B为两个集合，如果$A\subseteq B$ ，且$B\subseteq A$ ，则称A与B相等，记作$A=B$ 。即：

$\begin{array}{l}A=B\iff A\subseteq B\wedge B\subseteq A\\ \iff \forall x\left(x\in A\to x\in B\right)\wedge \forall x\left(x\in B\to x\in A\right)\\ \iff \forall x\left(x\in A\leftrightarrow x\in B\right)\end{array}$ (2)

根据定义2以及离散数理逻辑及集合论内容，证明两个集合相等的方法有命题演算法、谓词公式法、等式置换法三种。

1) 命题演算法

命题演算法证明集合相等的基本思想是互为子集，即：

欲证：$A=B$ 。

即证：$A\subseteq B$ 且$B\subseteq A$ 。

即证：对任意的x，$x\in A\Rightarrow x\in B$ ，且$x\in B\Rightarrow x\in A$ 。

上述过程可以合并为：对$\forall x,x\in A\iff x\in B$ 。

2) 谓词公式法

命题演算法证明集合相等的基本思想是把集合用谓词法进行表示，利用命题逻辑基本等值式模式[10]进行证明。

3) 等式置换法

命题演算法证明集合相等的基本思想是利用已知的集合运算律[10]进行证明。

下面分别利用上述三种方法证明两个集合相等。

例3 证明$A-\left(B\cup C\right)=\left(A-B\right)\cap \left(A-C\right)$ 。

证明方法一：命题演算法

任取x，$x\in A-\left(B\cup C\right)$

$\begin{array}{l}\iff x\in A\wedge x\notin \left(B\cup C\right)\\ \iff x\in A\wedge x\in ~\left(B\cup C\right)\\ \iff x\in A\wedge \neg \left(x\in \left(B\cup C\right)\right)\\ \iff x\in A\wedge \neg \left(x\in B\vee x\in C\right)\\ \iff x\in A\wedge \neg \left(x\in B\right)\wedge \neg \left(x\in C\right)\\ \iff \left(x\in A\wedge \neg \left(x\in B\right)\right)\wedge \left(x\in A\wedge \neg \left(x\in C\right)\right)\\ \iff \left(x\in A\wedge x\in ~B\right)\wedge \left(x\in A\wedge x\in ~C\right)\\ \iff \left(x\in A\wedge x\notin B\right)\wedge \left(x\in A\wedge x\notin C\right)\\ \iff \left(x\in A-B\right)\wedge \left(x\in A-C\right)\\ \iff x\in \left(\left(A-B\right)\cap \left(A-C\right)\right),\end{array}$

因此，得$A-\left(B\cup C\right)=\left(A-B\right)\cap \left(A-C\right)$ 。

方法二：谓词公式法

$\begin{array}{l}A-\left(B\cup C\right)=\left\{x|x\in A\wedge x\notin \left(B\cup C\right)\right\}\\ =\left\{x|x\in A\wedge x\in ~\left(B\cup C\right)\right\}\\ =\left\{x|x\in A\wedge \neg \left(x\in \left(B\cup C\right)\right)\right\}\\ =\left\{x|x\in A\wedge \neg \left(x\in B\vee x\in C\right)\right\}\\ =\left\{x|x\in A\wedge \neg \left(x\in B\right)\wedge \neg \left(x\in C\right)\right\}\\ =\left\{x|\left(x\in A\wedge \neg \left(x\in B\right)\right)\wedge \left(x\in A\wedge \neg \left(x\in C\right)\right)\right\}\\ =\left\{x|\left(x\in A\wedge x\in ~B\right)\wedge \left(x\in A\wedge x\in ~C\right)\right\}\\ =\left\{x|\left(x\in A\wedge x\notin B\right)\wedge \left(x\in A\wedge x\notin C\right)\right\}\\ =\left\{x|\left(x\in A-B\right)\wedge \left(x\in A-C\right)\right\}\\ =\left\{x|x\in \left(\left(A-B\right)\cap \left(A-C\right)\right)\right\}.\end{array}$

方法三：等式置换法

$\begin{array}{l}A-\left(B\cup C\right)=A\cap ~\left(B\cup C\right)\\ =A\cap \left(~B\cap ~C\right)\\ =A\cap \left(~B\cap ~C\right)\\ =\left(A\cap ~B\right)\cap \left(A\cap ~C\right)\\ =\left(A-B\right)\cap \left(A-C\right).\end{array}$

3.2. 证明集合相等及集合状态成员表法的思想及其构造和实例对比分析

集合状态成员表法在证明集合相等方面的思想及构造如下：

① 集合状态成员表法在证明集合相等方面的思想

首先，用1表示元素x属于一个集合，用0表示元素x不属于一个集合。

其次，证明在所有的赋值情况下，集合等式两边的集合组合的赋值情况是一样的。

② 集合状态成员表法在证明集合相等方面的构造

首先，确定集合等式两边集合组合的不同集合的个数n，那么集合状态成员表就有${\text{2}}^n+\text{1}$ 行，其中第一行是表头。

其次，根据集合等式确定等式左边集合组合的集合运算符个数s，等式右边集合组合的集合运算符个数t，那么集合状态成员表的列数大于n小于等于$n+s+t$ (当集合等式左右两边没有相同的运算时，集合状态成员表的列数等于$n+s+t$ 。否则，集合状态成员表的列数大于n小于$n+s+t$ )。

然后，根据等式左右两边的集合组合的运算符的优先顺序，分别列出等式左右两边的集合组合的运算层次，放于集合状态成员表的第一行表头的各列。

最后，由于集合等式两边集合组合的不同集合的个数是n，那么集合状态成员表就有2ⁿ种赋值情况，分别计算2ⁿ种赋值情况下集合状态成员表各列的真值。根据所得集合等式两边两个集合组合的真值一样，证明两个集合是相等的。

由集合的运算以及集合状态成员表思想，可得~A、$A\cap B$ 、$A\cup B$ 、$A-B$ 、$A\oplus B$ 的状态成员表(见表4)。

Table 4. State member table of the basic operation of the set

表4. 集合基本运算的状态成员表

A	B	~A	$A\cap B$	$A\cup B$	$A-B$	$A\oplus B$
0	0	1	0	0	0	0
0	1	1	0	1	0	1
1	0	0	0	1	1	1
1	1	0	1	1	0	0

为了进一步掌握证明集合相等的集合状态成员表法的思想及其构造，下面利用集合状态成员表法及表4求解例3。

例3 证明$A-\left(B\cup C\right)=\left(A-B\right)\cap \left(A-C\right)$ 。

证明 方法四：集合状态成员表法

作集合$A-\left(B\cup C\right)$ 和$\left(A-B\right)\cap \left(A-C\right)$ 的成员表，如表5所示。

Table 5. Set state member table of example 3

表5. 例3的集合状态成员表

A	B	C	$B\cup C$	$A-\left(B\cup C\right)$	$A-B$	$A-C$	$\left(A-B\right)\cap \left(A-C\right)$
0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	0	1	1	1	1
1	0	1	1	0	1	0	0
1	1	0	1	0	0	1	0
1	1	1	1	0	0	0	0

根据表5可知$A-\left(B\cup C\right)$ 和$\left(A-B\right)\cap \left(A-C\right)$ 的赋值情况完全一样，所以$A-\left(B\cup C\right)=\left(A-B\right)\cap \left(A-C\right)$ 。

通过例3可知，命题演算法、谓词公式法、等式置换法和集合状态成员表法求解幂集的结果一致。集合相等常用的方法，即命题演算法、谓词公式法、等式置换法和集合状态成员表法的优劣性如表6所示。

Table 6. Advantages and disadvantages of propositional algorithm, predicate formula method, equality replacement method and set state member table method

表6. 命题演算法、谓词公式法、等式置换法与集合状态成员表法的优缺点

	优点	缺点
命题演算法	证明逻辑严谨	需要熟记命题逻辑的16组基本等值式模式， 集合等式两边集合形式复杂时，证明过程很长。
谓词公式法	推理逻辑严谨	需要熟记命题逻辑的16组基本等值式模式， 集合等式两边集合形式复杂时，证明过程很长。
等式置换法	利用已知等值式证明集合相等， 简化证明过程。	需要熟记集合运算律， 有些集合运算律的证明不能用等式置换法。
集合状态成员表法	表4 简单且易懂，只需熟记， 不需要记基本等值式模式和集合运算律	集合元素比较多时，列真值表比较麻烦。

4. 结论

论文研究了利用定义法和集合状态成员表法求解集合的幂集。定义法求解过程简单，但是部分学生求解过程中容易缺失元素。集合状态成员表法的思想及构造核心是真值表法，真值表法可以列出一个集合的全部子集，进而可以保证幂集元素的不缺失。

论文研究了利用命题演算法、谓词公式法、等式置换法和集合状态成员表法证明两个集合相等。命题演算法、谓词公式法、等式置换法需要学生熟记命题等值式模式和集合运算律。如果命题等值式模式和集合运算律不熟悉，上述三种方法证明集合相等将会很困难。集合状态成员表法只需列真值表，故相对命题演算法、谓词公式法、等式置换法而言，集合状态成员表法简单且易懂。

通过历年的离散数学期末考试可以看出，有4%的学生使用了集合状态成员表法证明集合相等，提高了此类题型的得分情况以及期末考试的及格率，对学生掌握集合代数知识有一定的促进作用。

集合代数只是集合论的内容之一，集合论还包括二元关系和函数。后期将研究集合状态成员表在二元关系和函数中的应用。

NOTES

^*通讯作者。