感觉在学习计算机的过程中,碰到位运算大多涉及异或,又碰巧学离散数学提及与非门是完备集。就疑惑异或这么常用,怎么证明不是完备集呢?
刚学计算机,希望捞捞。
![](https://profile-avatar.csdnimg.cn/6d95590e2cf344018a149050cff3d58d_weixin_50374123.jpg!4)
如何证明异或门不构成逻辑门的完全集?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- P2441M 2023-08-12 20:57关注
别说,这问题确实挺难的🤨证明它是完全集很容易,证明不是又挺难的。
但当然还是有方法的。
通常说单个联结符号构成完全集,就是指可以用 x,y,1,0 的若干次该联结运算的累积,表示任意的基本逻辑符号。
我们尝试用 XOR 表示 AND。
注意到 x XOR y 同余 x + y (mod 2),所以x AND y 同余 ax+by+c×1+d×0 (mod 2) 同余 ax+by+c (mod 2).
我们根据将所有可能的取值代入:
x y AND 值 异或值 1 1 1 a+b+c (mod2) 1 0 0 a+c (mod 2) 0 1 0 b+c (mod 2) 0 0 0 c (mod 2) 令 第二行 + 第三行 - 第四行,我们得到异或值为 a+b+c (mod 2),但是 AND 值却是 0,与第一行不符。
由此得出矛盾。解决 无用评论 打赏 举报
悬赏问题
- ¥15 三分类机器学习模型可视化分析
- ¥15 本地测试网站127.0.0.1 已拒绝连接,如何解决?(标签-ubuntu)
- ¥50 Qt在release捕获异常并跟踪堆栈(有Demo,跑一下环境再回答)
- ¥30 python,LLM 文本提炼
- ¥15 关于将inet引入的相关问题
- ¥15 关于一个倒计时的操作和显示设计
- ¥15 提问STK的问题,哪位航天领域的同学会啊
- ¥15 苹果系统的mac m1芯片的笔记本使用ce修改器使用不了
- ¥15 单相逆变的电压电流双闭环中进行低通滤波PID算法改进
- ¥15 关于#java#的问题,请各位专家解答!