Crimson-boi[8] 布尔代数

题目背景

从复旦出版的 数理逻辑-证明及其限度 上抄的. 觉得还算有意思的一道布尔代数, 可以出给信息与未来的小朋友.

题面

(1) 将真值F与T看作0与1, 并认为0<1, 若对\forall i, f(x_1,\cdots,x_{i-1},0,x_{i+1},\cdots,x_n)\leq f(x_1,\cdots,x_{i-1},1,x_{i+1},\cdots,x_n), 则称布尔函数f为单调的. 试证明f为单调的当且仅当f可被只出现联词: 与\land, 或\lor, 永真\top, 永假\bot的公式所表达.

(2) 称一个联词集合C为极大不完全的, 若C不是功能完全的(即不能表示一切布尔函数), 但对任意C表示不了的布尔函数g, 联词集C\cup\lbrace g\rbrace是功能完全的. 证明联词集\lbrace\land,\lor,\top,\bot\rbrace为极大不完全的.

先想再看提示哦

提示

(1) 这样的题目肯定要给出构造方案, 但我们不好像证明\lbrace\land,\lnot\rbrace为功能完全时直接进行"插值"式的构造(这个属于经典结论了, 下面证明中要用到). 于是考虑能否进行归纳的构造. 正好, 根据定义, f(x_1,\cdots,x_n,0)与f(x_1,\cdots,x_{n},1)分别都是单调的, 那么也许归纳构造是可行的.

(2) 一般接触到的功能完全集都会包含\lnot, 于是一个很自然的想法就是要通过g表示出\lnot. 要是没有(1)的结论, 这确实是一道较难的题目. 然而, 在(1)的帮助下, 我们知道g一定不是单调的, 于是题目就迎刃而解了.

愿你无需看标答

标答

(1) 反面是显然的, 这里我们只证明正面. 我们对函数的元数n进行归纳.

首先n=1时, f(x_1)有如下三种情况:

f(0)=0, f(1)=0, 此时f(x_1)可表示为f(x_1)=\bot;

f(0)=0, f(1)=1, 此时f(x_1)可表示为f(x_1)=x_1;

f(0)=1, f(1)=1, 此时f(x_1)可表示为f(x_1)=\top;

原结论成立.

现假设n=k时原结论成立, 考察f(x_1,\cdots,x_k,x_{k+1}).

由所给定义知f(x_1,\cdots,x_k,0)与f(x_1,\cdots,x_k,1)分别都为k元单调函数, 于是它们都满足原结论.

构造函数(x_k\lor f(x_1,\cdots,x_k,0))\land f(x_1,\cdots,x_k,1). 显然它也满足原结论. 现来验证此函数正是f(x_1,\cdots,x_{k+1}).

当x_{k+1}=1时(此处=是真值指派意义上的, 并非字符串意义上的等于), 我们构造的函数值就是(1\lor f(x_1,\cdots,x_k,0))\land f(x_1,\cdots,x_k,1)=1\land f(x_1,\cdots,x_k,1)=f(x_1,\cdots,x_k,1).

而当x_{k+1}=0时, 若f(x_1,\cdots,x_k,0)=0, 我们构造的函数值就是(0\lor0)\land f(x_1,\cdots,x_k,1)=0\land f(x_1,\cdots,x_k,1)=0;

若f(x_1,\cdots,x_k,0)=1, 由单调性f(x_1,\cdots,x_k,1)=1, 此时构造的函数值为(0\lor1)\land1=1\land1=1.

经过上面的讨论, 我们发现这个构造出来的函数正是f(x_1,\cdots,x_{k+1}), 所以原结论对n=k+1也成立!

(2) 由(1)的结论, 原联词集不能表示非单调的函数, 所以它是功能不完全的, 存在这样的g(x_1,\cdots,x_n)且它一定不是一个单调函数. 所以, 一定\exists i与一组真值指派a_1,\cdots,a_{i-1},a_{i+1},\cdots,a_n(a_j\in\lbrace\top,\bot\rbrace)使得g(a_1,\cdots,a_{i-1},0,a_{i+1},\cdots,a_n)=1且g(a_1,\cdots,a_{i-1},1,a_{i+1},\cdots,a_n)=0.

可以看出, g(a_1,\cdots,a_{i-1},x,a_{i+1},\cdots,a_n)=\lnot x, 并且g(a_1,\cdots,a_{i-1},x,a_{i+1},\cdots,a_n)仅由g, \top, \bot构成, 符合条件.

此时我们已能表示\lnot这个联词, 结合原联词集中的\land或\lor, 即可表示一切布尔函数, 命题得证!