关于满足常量闭包条件的布尔函数为Sheffer函数的证明思路问询
关于满足常量闭包条件的布尔函数为Sheffer函数的证明思路问询
我最近在研究布尔函数相关的证明问题,碰到了这么个待证命题:
设f是一个布尔函数,满足0,1 ∈ [{f}]。这里[{Φ}]表示集合Φ的闭包,也就是所有能通过Φ中的函数构造的公式实现的布尔函数的集合。需要证明f是Sheffer函数。
换个更直白的说法:我们要证明,单个布尔函数如果能同时构造出常量0和1,那它一定是Sheffer函数;反过来讲,非Sheffer函数的单个布尔函数,没办法同时实现这两个常量。
目前我能想到的只有暴力枚举的方法——把所有二元布尔函数逐个排查,最后会发现只有Sheffer竖线和皮尔士箭头这两个函数能同时构造出0和1,其他的都做不到。
不过总觉得暴力枚举有点“笨办法”的感觉,想问问各位前辈:我这个思路是正确的吗?还是说存在更严谨、更巧妙的非枚举式证明方法呀?
备注:内容来源于stack exchange,提问作者Lunciare
相关产品推荐
相关产品推荐

