当前课程知识点：电子信息科学与技术导引(1) > 第四讲：比特与逻辑 > 第七节 逻辑的用途示例 > 第七节 逻辑的用途示例
刚才我们通过逻辑的
这种表达呢知道
如何用布尔函数来
表示一些逻辑关系了
那么我们看一下
它到底有什么用呢
我们先不解刚才思考的
问题我们给同学们
出一个逻辑上
最难的题就是
mitboolos教授
提到的the hardest logic puzzle ever
顾名思义呢就是
历史上最难的
一道逻辑难题那么
他怎么说呢就是
说有有甲乙丙三个精灵
其中一个只说真话
一个只说假话还有
一个随机地决定
何时说真话何时说假话
那么难在哪儿呢你可以
问这三个精灵三个是
非题那么你的任务是
要从他的答案里找出来
谁说真话谁说假话谁是
随机答话你可以随机选择
任何一个精灵问话问的
问题可以取决于
上一题的答案这个
难题难在哪儿呢
这些精灵是用精灵语
来回答你的问题他会
发出两种音节来一种是
“Da一种是Ja”
你虽然能区分这两个音节
但是并你不知道它们的
含义也就是说你不知道
哪个是对哪个是错那么
你怎么问这三个问题来
找出来哪个精灵说真话
哪个精灵说假话哪个是
随机的那么这个问题呢
当时呢发表在这种
学术期刊上
那么我们这节课呢
可能很难把这个
来龙去脉给大家讲的
很清楚那么我们把
它转化为一个逻辑难题从
最难题转换为一个难题
就是the hardest logic puzzle
首先呢我们把精灵个数
减掉一个就是有
甲里和甲乙两个精灵
其中一直只说真话
另一个呢只说假话
但是呢不是象
刚才说的问3个问题了
我们希望你只问
一个问题那么用
一个问题找出来
你问的那个人
说真话还是假话
当然了这个问题的
困扰还是一样的
精灵呢也是用da和ja来
回答你并不知道
这个音节的含义到底
是对还是错那么
我们该问什么样的
问题呢那么我们
现在就要用逻辑来
表示这个难题了
这个难题首先我们
要把它做一个形式化的
表达那么比如我们用
g代表我们问的
那个精灵说真话还是
假话比如g等于1就
代表我问他说的真话
g等于0代表他说的是
假话然后呢我们用
x来代表问题然后呢
用d来代表回答答案的
含义那么1呢代表是
对0呢代表是错那么
我们有了这些变量之后
我们看怎么设计这些问题
或者说我们希望这个
x等于什么那么我们
希望什么呢假设我们
按照结果来编码
我们希望对于
这个问题x说真话的精灵呢
回答da说假话的精灵呢
回答ja这是我们希望的
这样我们能区分开
两个精灵到底谁说真话
谁说假话那么这句话是
什么意思呢就是说
当g等于1的时候我们
希望这个问题的
答案达标的是da也就是
x等于d当我们问说假话
的那个精灵的时候
我们希望回答的问题的
答案是ja由于他说假话呢
实际上x就等于假的
取反也就正好等于d
那从这样一个推理过程
我们很容易找到
这个方程很好解x变量
两种情况x都等于
d解方程x很容易结出来
就等于d那么x等于d是
一种命题逻辑的
一种抽象那我们看一下
如果把它翻译成人说的
这种语言他代表什么呢
可以问da的含义是
什么或者说da是对吗
用这句话来问这个精灵
那么用这样一句话来
问说真话的精灵他一定
会说da这样的一句话问
说假话的精灵他一定会说
ja那么也就是说这种
规则的逻辑抽象和
这种转换规则很容易
解出这个方程得到
我们应该问的问题
这其中呢并没有奥妙的
推理每一步呢都有
确切的规则来指导
那么从这里我们可以
看到我们刚才说的
逻辑的力量那么有了
这个力量呢实际上呢
我们可以把这个
力量转换到计算机上
让他解这样的难题也
就是说我们刚才说的
这个逻辑小故事如果
我们再看父亲母亲
三个小孩看电视的话
既然这么规则我就
可以让计算机来
解这个问题
那好网上有很多种工具
我们用nusmv来解这样
一个逻辑问题首先呢
我们把这个比特
输进去变量输进去
abcde代表父亲看
电视母亲看电视三个小孩
分别cde看电视然后
我们把这5 句话把
它翻译过去首先
如果A看电视B也
看那么就是a蕴涵bd和e两人
都在看或者其中一个
看就是d或eb和c只有
一个人看了就是b或
cC和D或者两人都看
或者两人都没看就是
c同或d当然这个同或
我们没介绍实际上就
相当于等于e或的
求反那么如果e看了
那么ad也看了那么
e蕴涵a与上d那么
这显然就是我们
这种一一对应关系
那么有了这种翻译之后呢
我们就可以利用
这个工具来解这个
问题我们把这个
模型读进来然后
让他解这个问题
很快一眨眼间要
快很多他解出来
这个问题的答案
就是a＝false b＝false cd＝true e＝false
也就代表什么呢父亲母亲都
没有看三个小孩里cd看了
e没有看这个解决问题是
非常快的那么由此
我们就看到逻辑其实
也并不那么神秘
那么如果我们用
一套布尔代数来表达
上头的编码就可以
来解决我们以前
认为逻辑复杂的问题
那么有了逻辑之后呢
你可能还要问我平时
除了解决逻辑问题
我还算加减乘除做
各种各样的运算
这些运算靠这些
逻辑能实现吗
答案是能实现我们
布尔代数和数值
运算之间的关系
我们也从1比特开始
讲1比特的乘法和1比特的
加法那么这1比特的乘法和
加法是怎么和逻辑对应的
呢我们先看乘法0成
0＝0 0x1＝0 1x0＝0 1x1＝1
这跟我们的与运算是
一模一样的也就是
说所谓的乘法就是
与那么加法呢先看
加法的进位那么
0＋0进位是0 0＋1进位是
0 1＋0进位是01＋1进位是
1我们发现这和我们的
与运算也是一模一样的
进位就是与那我们再看
和数和数呢复杂一点
0＋0＝0 0＋1＝1 1＋0＝1 1＋1＝0
这个东西是什么呢就是
我们前面提到过的
异或异或虽然复杂呢
实际上a的非与上b括上
a与上b的非也是逻辑的
或者说布尔运算能够
体现出来那么从这样
一张表上我们可以看出
发现实际上数值运算和
这个与或非有非常
明确的关系只要
我们找到这种关系
就可以转换为布尔运算
那么好我们就讲
如何用布尔运算构建
1比特的数值运算那么
也就是很简单乘法呢
对应的是与加法的和呢
就是对应的是异或
那么实际上呢我们再
扩展如果1比特的
这种比较可以把它
转换为各种各样的
布尔函数比如说a大于
等于b实际上就等于
aa大于b就等于a与上
b的非不等于b就
等于a异或b
那么有了1比特我们
也可以把它扩展到
多比特比如说我们
举个例子两比特的加法
两比特的加法呢也
很容易求出来那么
他的第一位呢就是
a0异或上b0他的进位呢
就是c0与上b0那么他的
高位的和呢就等于
a1异或上b1异或
上进位c0他的两位的
进位呢就等于a1与
上b1括上a1与上c0或
上b1与c0那么可以
看到两位的数值进算呢
也可以用这种
与或非等等标准的
布尔运算来实现
那么实际上呢
这种过程呢可以
扩展到多位的制的
加法上由此呢我们
就可以知道实际上
多比特的这种数值
计算也没有什么神秘的
就是布尔运算的
一些组合啊各种各样的
排列来实现的当然乘法呢
是可以有加法来实现的
那么通过这样一些变幻
我们知道原来
比特与逻辑力量是
非常非常强大的它实际上
能够帮我们解决各种各样的
逻辑问题也可以帮
我们解决各种各样的
数值问题那么它具有
非常强的表达和处理能力
那么有了这些能力呢我们
也希望你呢能亲自
实践一下我们看刚才这个思考
问题我们把他的第一句话
改了原来是如果a看b就看
那么我们把它改成a和b
有且只有一个人看了
那么看看你来解一解
刚才这个小故事你
也可以呢把我们刚才
用的计算机工具拿来
把这个模型输进去
看看计算机解的和
你解的是不是一样的
-第一节 序言
--第一节 序言
-第二节 电磁学和分析数学发展史：磁学
-第三节 电磁学与分析数学发展史：静电
-第四节 电磁学和分析数学发展史：动电
-第五节 电子器件的发明及电子技术的发展
-第六节 电磁学的广泛应用
-第七节 电磁系统理论
-第八节 电子科学技术各学科间的关系
-第九节 电子科学技术的学科体系
-第一讲：电磁学与分析数学史概览--第一次作业
-第一节 序言
--第一节 序言
-第二节 电磁场（一）
-第三节 电磁场（二）
-第四节 物质
--第四节 物质
-第五节 电磁场与物质的相互作用：非共振作用
-第六节 电磁场与物质的相互作用：共振作用
-第七节 电磁场理论与电路理论
-第一节 空间离散化
-第二节 静场电路分析
-第三节 非静场电路抽象
-第三讲：电路抽象--电路抽象 练习题
-第四节 电路元件抽象
-第五节 非线性元件抽象
-第六节 电路抽象三原则
-第七节 分层抽象思想
-第八节 电路基本问题
-第九节 数字化抽象
-第三讲：电路抽象--Quiz 3
-第一节 序言
--第一节 序言
-第二节 什么是比特
-第三节 比特与编码
-第四节 比特与信息
-第五节 比特的用途示例
-第六节 什么是逻辑
-第七节 逻辑的用途示例
-第八节 与数字电路的关系
-第九节 小结
--第九节 小结
-第四讲：比特与逻辑--Quiz4
-第一节：从算盘到ENIAC
-第二节：通用计算机模型
-第三节：指令集体系结构
-第四节：程序和程序设计语言
-第五节：处理器的工作原理
-第六节：性能问题
--第六节：性能问题
-第七节：小结
--第七节：小结
-第一节：数据与数据处理技术的发展
-第二节：数据处理举例
-第三节：数据模型和算法的概念
-第四节：问题的抽象和建模
-第五节：数值分析问题研究
-第六节：数据和算法的关系I
-第七节：数据和算法的关系II
-第八节：大数据
--第八节：大数据
-第九节：数据挖掘技术和数据算法的展望
-第六讲：数据与算法--Quiz6
-第一节：基本内容简介
-第二节：信息的基本概念和传输的几种方式
-第三节：交换的概念和网络的几种形式
-第四节：模拟与数字通信
-第五节：调制和解调
-第六节：传输涉及的基本理论
-第七节：信息论和几种相关的编码方式
-第八节：多址方式
--第八节：多址方式
-第九节：交换的基本概念
-第十节：网络分层的基本概念
-第十一节：互联网的基本原理和有限状态机模型
-第七讲：通讯与网络--Quiz7
-第一讲：内容简介
--第一讲：内容简介
-第二讲：信息与媒体
-第三讲：人类感知与认知
-第四讲：智能信息处理
-第五讲：媒体与认知相互作用
-第六讲：媒体认知应用
-第七讲：总结
--第七讲：总结
-第八讲：媒体与认知--Quiz8
-期末考试--Final Exam
