离散数学discrete2B..doc

5. 联结词的完全集 【定义1.22】{0, 1}上的n元函数f : {0, 1}n({0, 1}就称为一个n元真值函数。 联结词(实际上一个一元真值函数： f((0) = 1, f((1) = 0 而联结词(、(、(和(则都是二元真值函数： f((0, 0) = 0, f((0, 1) = 0, f((1, 0) = 0, f((1, 1) = 1 f((0, 0) = 0, f((0, 1) = 1, f((1, 0) = 1, f((1, 1) = 1 f((0, 0) = 1, f((0, 1) = 1, f((1, 0) = 0, f((1, 1) = 1 f((0, 0) = 1, f((0, 1) = 0, f((1, 0) = 0, f((1, 1) = 1 反过来，一个真值函数就可看成一个真值联结词。设f : {0, 1}n({0, 1}是一个n元真值函数，则可如下定义一个n元真值联结词Nf : 对于n个命题变元p1, p2, …, pn，命题公式Nf(p1, p2, …, pn)在真值赋值函数t1, t2, …, tn下的真值为f(t1, t2, …, tn)。 显然互不相同的n元真值函数的个数为22n，因此可定义22n个n元真值联结词，例如1元真值函数有四个： f1: 0(0, 1(0 f2: 0(0, 1(1 f3: 0(1, 1(0 f4: 0(1, 1(1 而2元真值函数有16个，可定义16个真值联结词，而我们常用的只不过是其中的4个。现在的问题是，是否所有的真值函数都可使用常用的这5个真值联结词来表示呢？ 【定义1.23】设(是联结词的一个集合，称(为联结词的一个完全集，如果任意真值函数f都可用仅含(中联结词的命题公式A来表示，即对A中命题变元的任意一个真值赋值t1, t2, …, tn，A在t1, t2, …, tn下的真值为f(t1, t2, …, tn)。 【定理1.24】{(, (, (, (}是联结词的一个完全集。 【证明】根据定义1.23只要证明对任意n元真值函数都可由只含(、(、(和(的n元命题公式来表示即可。对真值函数的元数n进行归纳证明。 归纳基：当n = 1时，一元真值函数只有4个，可分别用p(((p)、p、(p和p(((p)来表示，因此定理成立。 归纳步：假设当n = k时定理成立，要证n = k + 1定理也成立。设f(x1, x2, …, xk, xk+1)是一个k+1元真值函数，定义如下两个k元真值函数： f1(x1, x2, …, xk) = f(x1, x2, …, xk, 0) f2(x1, x2, …, xk) = f(x1, x2, …, xk, 1) 由归纳假设知f1和f2都可由只含(、(、(和(的k元命题公式来表示，设它们分别可由A1和A2表示，且假定A1和A2中的k个命题变元为p1, p2, …, pk。现在我们证f可由A = (((pk+1)(A1)((pk+1(A2)表示，其中pk+1是不同于p1, p2, …, pk的一个命题变元。即要证对命题变元p1, p2, …, pk, pk+1的一个真值赋值t1, t2, …, tk, tk+1时，A的真值是f(t1, t2, …, tk, tk+1)。当tk+1 = 0时，即pk+1被赋值为0，这时(((pk+1)(A1)与A1等值，而(pk+1(A2)的真值为1，所以A与A1等值，而按归纳假设有A1的真值为f1(t1, t2, …, tk)，即为f(x1, x2, …, xk, 0)。同理可证当tk+1 = 1时A的真值是f(x1, x2, …, xk, 1)，从而A的真值是f(t1, t2, …, tk, tk+1)。 □ 【推论1.25】{(, (}, {(, (}和{(, (}都是联结词的完全集。 【证明】1. 要证{(, (}是联结词的一个完全集，只要证任一命题公式可与一个只含(和(的命题公式等值，事实上有： (A(B)((((A)(B) (A(B)((((((A)(((B))) 2. {(, (}是联结词的一个完全集，因为： (A(B)((((((A)(((B))) (A(B)((((A)(B) 3. {(, (}是联结词的一个完全集，因为： (A(B)((((((A)(((B))) (A(B)((((A)(B) 事实上，上述每个集合都是极小的完全集，即不能再从集合中去掉任意一个联结词还能保持是完全集。 □ 【定理1.26】{(, (, (, (}不是联结词的完全集。 【证明】总取0值的真值函数不能由只含此联结词集中的联结词的命题公式来表达，因为这样的命题公式当所有命题变元都真值赋值为1时真值为1，不