集合与命题逻辑

命题逻辑简介

集合、对称差以及命题逻辑是离散数学和计算机科学的核心内容。这些概念也深深融入了数据结构与算法之中。如果不理解这些关键概念，我们就无法继续前进。

我们已经在多种编程语言中见过集合的实现。同时我们也发现，集合本质上是一种陈述，就像我们在编程范式中使用“陈述”一词一样。

让我们用离散数学的方式写出一个偶数集合：

$A = \{2, 4, 6, 8\}$

我们可以将这个偶数集合读作一个陈述——它是一个偶数。在离散数学中，数值集合被视为不包含重复元素的离散数字的集合。然而，如果我们把“数字”换成“事物”，这个陈述就会具有另外一层含义。这一点我们稍后会详细讨论。

当两个不同的集合包含重复元素时，对称差可以迅速指出这些重复项。集合使用异或符号（XOR）来表示不相等，而这一布尔逻辑概念在每种编程语言中都有实现。

这正是命题逻辑发挥作用的地方。没有命题逻辑的支持，我们就无法计算两个集合之间的对称差。

命题逻辑研究的是由真值（true 和 false）所支配的陈述。这些真值被赋予陈述，以便单独分析或组合分析这些陈述。

这些离散数学概念不仅彼此关联，而且在编程范式中也以隐秘的方式相互支持。

我们知道，在 Java 集合框架中，集合是一种不允许包含重复元素的集合。它依次实现了数学集合抽象、对称差以及命题逻辑。

命题逻辑的概念在某些特殊情况下起着关键作用，例如当 Set 集合定义 equals 或 hashCode 操作的行为时。

举个例子，假设有两个集合。如果我们要比较它们，只有当两个集合包含相同的元素时才认为它们相等，这时我们就需要建模离散数学中的集合抽象、对称差以及命题逻辑。

$A = \{1, 5, 8, 9\} \text{ 且 } B = \{5, 9, 11, 45\} \\ A\text{ 的对称差 } B = \{1, 8, 11, 45\}$

在这里，数字 1、8、11 和 45 分别出现在两个集合中，但 5 和 9 同时存在于两个集合中。

我们不会在此深入展开细节，但必须理解：为何集合抽象的实现对于数据结构至关重要。

到目前为止，我们已经看到一些基于数值的集合实现。但集合也可以是事物的集合。事实上，从数学角度定义集合时，我们说集合是一类事物的集合。这些事物是什么？是具有共同属性的事物。

例如，我们可以有一个骑行装备的集合，如头盔、手套、护目镜、鞋子等。我们也可以把一个人的两只眼睛——左眼和右眼——看作一个集合。

集合的记号与集合抽象

我们已经学习过集合的记号，因此知道如何这样书写这两个例子：

$\{\text{头盔, 手套, 护目镜, 鞋子, ...}\} \\ \{\text{左眼, 右眼}\}$

在第一个例子中，我们使用了三个点，称为省略号。它表示骑行装备列表是无限的。而第二个例子恰好包含两个元素。

我们将前者称为无限集，后者称为有限集。

尽管集合抽象在数学上看似无用，但其语境非常重要。在许多情况下，集合可以成为构建复杂数学概念的基础，比如图论、抽象代数、线性代数、数论等。

此外，集合抽象也是数据结构的基础。

集合抽象具有一些独特的特性。当我们组织数据时，必须实现集合抽象的独特特征。所谓“组织数据”，指的是数据的创建、检索、修改和删除。在这些操作中，集合抽象的实现为我们提供了帮助。

集合中每个元素只能存在一次。这种集合不允许重复。特别地，这一特性使集合区别于 Java 集合框架中的其他类型。当我们设计数据结构时，可以据此进行规划。

我们可以存储唯一元素。由于集合抽象不关心顺序，我们可以在某些场景下利用这一特性。

HashSet 和 TreeSet 作为集合的例子

基于这些特性，我们可以存储不重复的离散元素，且无需担心元素的顺序。

虽然集合默认不关心顺序，但在某些情况下，我们实际上需要有序而非混乱。此时，我们可以使用通用集合实现 TreeSet。它根据元素的值来维护顺序。然而，TreeSet 的实现成本更高，速度比基于哈希表存储数据的 HashSet 更慢。但 HashSet 的实现并不保证迭代顺序。

下面我们来看这两种实现方式。

1import java.util.HashSet;
2import java.util.Set;
3import java.util.TreeSet;
4
5class Main {
6    public static void main(String[] args) {
7        int countingIntegers[] = {25, 44, 78, 1, 65, 3};
8        Set<Integer> hashSet = new HashSet<Integer>();
9        try {
10            for(int i = 0; i < 5; i++) {
11                hashSet.add(countingIntegers[i]);
12            }
13            System.out.println("HashSet 不排序： " + hashSet);
14
15            TreeSet sortedTreeSet = new TreeSet<Integer>(hashSet);
16            System.out.println("TreeSet 根据值进行排序：");
17            System.out.println(sortedTreeSet);
18        }
19        catch(Exception e) {}
20    }
21}

我们上面实现了 HashSet 和 TreeSet。从以下输出可以看出它们的区别：

1HashSet 不排序： [1, 65, 25, 44, 78]
2TreeSet 根据值进行排序：
3[1, 25, 44, 65, 78]

在上述 Java 代码中：

• 第 9 行：这里使用 try 语句捕获异常，并引导程序流程。

• 第 15 行：这部分负责将 HashSet 转换为 TreeSet。

还有一种实现叫做 LinkedHashSet，它是带有链表连接的哈希表。这种实现以不同方式维持顺序：每当插入新元素时，都会保持插入顺序。

我们本节课一开始讨论了集合在数据结构中的重要性。接着，我们处理了一个包含重复元素的集合，并将其转换为另一个集合，去除了所有重复元素。