一个博客

随便写写

0%

程序化输出真值表

发表于 更新于

之前离散数学课上，老师教了一种列真值表的方式来判断两个集合是否相等，这种方法很机械，非常适合写程序来打表。

集合的部分运算的表示

首先我们需要用计算机能理解的方式表示集合的运算。按照老师上课说的，0和1表示的就是元素是否属于集合，0不属于，1属于，然后接下来看看每个运算的表示方法。

注意，下面计算中任何看起来是集合的东西，表示的都是元素是否在集合中，并不是集合。运算的结果看起来也是集合，但是表示的也是这个元素是否在结果集合中。

补集

首先从最简单的补集开始，根据定义，显然如果x属于A，那么x不属于A的补集，相反x不属于A，那么x一定属于A的补集，画成表应该是下面这样

$A$ $\overline{A}$
1 0
0 1

可以很明显的看出来，这个就是逻辑运算或者布尔运算里面的“非”运算，用代码来写大概就是这样

1
2
3
4
//补集运算
bool complement(bool A){
    return !A;
}

并集

并集就是把两个集合拼起来，新集合包含两个集合的所有的元素，或者说原本两个集合中的元素都能够在新的集合中找到。

所以显然，如果一个元素属于任意一个集合，那就必定属于这两个集合的交集，这就跟逻辑运算的“或”是一样的

$A$ $B$ $A \cup B$
1 1 1
1 0 1
0 1 1
0 0 0

代码如下

1
2
3
4
//并集运算
bool union(bool A,bool B){
    return A||B;
}

交集

看了上面两个例子之后应该可以很容易的推出，交集相当于逻辑运算中的“且”，元素要同时属于两个集合，才会属于两个集合的交集。

$A$ $B$ $A \cup B$
1 1 1
1 0 1
0 1 1
0 0 0

代码如下

1
2
3
4
//交集运算
bool intersection(bool A,bool B){
    return A||B;
}

打表实现

打表主要就两件事，

  1. 根据变量的数量枚举所有可能情况
  2. 对于每一种情况代入表达式求值

枚举所有可能可以用递归实现，在递归的最后一层的时候代入求值，代码大致应该是这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<bool>S;
void f(int n){
    if(n==0){
        g(S);
        return;
    }
    S.push_back(1);
    f(n-1);
    S.pop_back();
    
    S.push_back(0);
    f(n-1);
    S.pop_back();
}

S是一个全局列表，保存表达式用到的每一个变量，g是表达式求值函数。

其实最好还是写一个将字符串解析为表达式的函数，用户的输入就是字符串，例如“补(交(A,B))”然后构造一个函数对象。

最终实现

综合考虑，我最后决定用js写，一来有现成的Function可以将字符串解析为函数，二来可以用html来打表，比C++控制台显示的好看点，三来web端的程序使用都比较方便

事实证明，js并不好写，或者说前端都不好写，逻辑上很简单，但是前端写起来很麻烦。

又更新了一下，现在不需要输入字符串了，全部操作都可以从下拉列表中选择，新测试版本地址