当前课程知识点:Petri网:模型、理论与应用 > 第四章 网论 > 4-5 信息流网 > Video
卫兵和门
也就是说真话也说假话的普通人
他们之间的关系呢
确定了这个关系以后
这个问题马上就出来了
就跟刚才我们那个问题一样
其实很简单你回去想一下
把两颗星的
难上又难的问题解出来
你就能够体会到
用信息流动和信息交互作用
来分析这一类的问题
它的益处是很大的
能够给你启发
上次我给大家留了一个思考题
就是现在大家看到的这个问题
我再把它重复一下
就是一个犯人
住在一个牢房里面
这个牢房子有两个门
每个门都有一个卫兵把守
这两个卫兵一个人是
老说假话一个人老说真话
法官跟犯人宣布
你可以问一个是非问题问一个卫兵
然后选择一个门出去
这两个门有一个门出去你就自由了
有一个门出去就被处死
所以现在给你这个机会
你设计一个是非题
然后问其中的一个卫兵
然后选择一个门出去
这就是上次我留的
让大家思考的
我为什么今天再说一遍这个问题呢
因为上次我讲的时候
因为我
可能是太熟悉了
所以准备片子的时候
出了点毛病
我们今天来纠正这个毛病
我们说过
这个题看起来像是一个脑筋急转弯的题
或者叫做拍脑袋的题
今天我们讲课
我们就要从
理论的角度方法的这个角度
来找到一个系统的方法
来解决这个问题
那么我们现在讲的是
信息流网信息流系统
我们要从信息的角度
来思考这个问题
这个涉及的物理对象
一共有多少信息这里面
我们说的信息是one bit information
就是一位信息
这里面有两位信息
一个是卫兵
你选择一个卫兵问
这个卫兵或者说真话
或者是假话
这是一位信息或真或假
另外这个门是一位信息
这个门的信息是什么
或者死或者活
所以这是两个信息
另外这两个信息
他们是互相关联的
因为卫兵守卫着门
所以门跟卫兵之间有一个守卫的关系
所以这样一来我们希望的是什么呢
我们要问你这个是非题
就是要迫使在卫兵回答的时候
引起这两个信息的交互
我们从卫兵的回答能够判断出
哪个门是活门哪个门是死门
这个是非题我上次说过了
是非题就是一个陈述句
然后让这个被问的人判断陈述的事实
陈述的东西是对还是错
刚才我讲的我们希望这个是非题
能够引起信息的交互
信息的交互
讲这个课也讲了很多年十多年二十年了
但是我就当时有过一个疑问
但是没有去仔细的思考
这个信息交互为什么
那些箭头函数
那个Q函数
就是上次我讲过的
为什么要那样定义
我当时有过一个疑问
但是没有细究
这次呢我准备这个课
我是仔细的思考了一下
这个信息的交互
有这么几个特点
第一我们说的信息交互
是一位信息跟另外一位信息交互
其他的信息就是多位
像我们上次讲的
n箭头函数
就是有n位信息
n可以是123456随便一个正整数
然后作用在另外一位信息上
看上去是多位信息
但是实际上呢
是一位信息一位信息作用以后
构造在一起的组合在一起的
所以基本的信息交互就是两位信息
一位信息作用在另外一位信息上
两位信息作用
然后输出的还是两位
上次我们讲过的基本的
信息交互函数是
p1
我们以前的定义是定义成这样
输出的a的位信息
自己不改变
它作用在第二位信息
b这位信息上面
输出的是u
u怎么计算的呢
就是a加上b加是按位加
也就是说它等价于什么
就是a不等于b
咱们想一想一位信息来
作用在我这位信息上
只可能有这两种情况
就是我判断一下
这个作用在我这个身上的这位信息
跟我相同的还是跟我不同的
只可能有这两种情况
所以p1第一箭头函数
就是判断
作用在第二位信息上的第一位信息是不是跟他相等
是不是跟他一致
他的结论是
如果不一致的话我就输出1不一致
如果要是一致的话那我输出0
说不一致不成立
那么很自然的就第二种作用方式
就是判断它是不是相等
我给他起个名字叫做r1
这是第二个一位箭头函数可能的定义
我判断一下作用在b这个信息上面的a信息
跟b是不是相等
相等我就输出1
说他跟我一样
不相等我就输出0
说他跟我不一样
所以信息的交互
最基本的信息交互只有这两种可能性
这是我以前曾经
有过一闪念就是为什么这么定义
这次呢我仔细的思考了一下
就这两种可能性
第一箭头函数p1
原来我书上也是这么定义的
就是这样
第二个和第三个变迁
第二个变迁是a等于1b等于1
所以两个都是相等的
第三个a等于1b等于0
这两个那是不相等的
不相等所以他输出是u等于1
说他俩个不相等
然后第三个是a等于0b等于1
也还是不相等
输出的还是u等于1
第一个和第四个呢正好
两个都是一或者两个都是零
所以他输出的就是零
说他们不相等不对
它们相等
这就是第一箭头函数的p1
这个r1就是换了一个
u在第二个第三个就是u等于0
第一个第四个呢就是u等于
他给出的判断就是这个这两是相等的
我就告诉你是1这两个不相等我就告诉你是0
这就是第一箭头函数
就是一位信息作用在另外一位信息上面
只有这两种可能性
你们大概见过这张片子
就是我说我们用p1这个箭头函数来分析
刚才我们说的这个犯人和门的问题
我上次的片子写的是
u也就是信息交互以后的输出的信息
u是得到的回答
如果u等于1的话
就相当于回答的是yes
他背后就是活门
这个片子是写错了
为什么写错了
我思考了一下
第一个结论就是熟能生错
过去一句话叫熟能生巧
其实熟也能生错
因为太熟了
所以就没有把它当回事
所以想当然的就写在那了
另外一个
我要跟大家说的就是
我这么多年来教学的体会
就是教学相长我只有这一次
有这个机会来讲这门课
我才有机会重新思考这个问题
才能把一位信息交互
跟另外一位信息交互作用
这两种可能把它想清楚
这个u刚才我们看到了
u不是卫兵的回答
他是作用以后得到的结论
这个结论这个u它是有物理含义的
我们看看它的物理含义是什么
刚才我们说了
u等于1就是两个不相等
从p1一这个角度来讲
我们分析p1
u等于1就是他两个不相等
不相等是什么呢
说真话的人守的是死门
就是D门
说假话的人就是F
他守的是活门就是L
我们期待的结果是什么呢
如果卫兵回答的是yes
我们就判定他的背后是活门
因为说假话的卫兵后面守的是活门
我们什么样的问题
能让这个卫兵回答我们yes呢
这个问题很显然
就是你问他
说真话的卫兵守着是活门吗
现在明明是说假话的守着活门
所以说假话的人了一定会告诉你yes
只要他说yes你就从他的背后走出去
他那个门一定是活门
如果你问的不是说假话的人
问的是说真话的人
说真话的人守着死门
你问他说真话人守着的是活门吗
他说真话当然说no
所以当你听见到他说no
你就从另外一个卫兵的背后走出
那一定是活门
这是u等于1的情况
如果u等于0了正好
u等于0的时候是
说真话的守着的是活门
说假话的守着的是死门
这时候我们什么样的问题
能够让说真话的人说yes呢
当然就是说真话的守着的是活门吗
这个问题正好
和刚才u等于1那个情况问的是同一问题
因此我们就得到了一个唯一的问题
刚才我们看到分析p1
分析u等于1u等于0物理意义
我们就得出了一个统一的
是非题
就是守活门的卫兵是说真话吗
或者是说说真话的卫兵守的是活门吗
这个问题你可以
变换着来问都没有问题
不是唯一的
从这个问题我们就知道
只要那个卫兵回答yes
你选他背后的门一定是活门
如果他回答这是no
你从另外一个卫兵的
背后走出去一定是活门
这就是信息交互
带给我们的分析的一个系统的分析方法
能够推导出所需要问的是非题
这就是统一的问题
基本的交互只有两种
一个p1一个是r1
那么你自己去分析一下
r1我刚才分析的是p1
你如果用r1作为基本的信息交互
你来分析一下会不会得出
同样的结论呢
这作为练习你去分析
当然应该有同样的结论
如果没有同样的结论
那就错了
我们看如果p1或r1
如果这两个箭头函数
这两个一位信息
作用在另外一个信息的交互
如果你从分析他们当中
得不出是非题了没有答案
那么我可以告诉你
就是刚才我们讲的这个是非问题
是不存在的
当然我们现在
它是存在的
这就告诉我们
这一套方法
不仅可以得出正面的结论
没有答案的时候
也可以得出否定的结论
这是理论的作用
以及由理论产生的方法它的作用
理论信息交互是基础
是产生方法的依据
如果我们把方法用方法代替灵感
代替拍脑袋
把灵感上升成方法
这样才有实用价值
我们可以解决了一个问题
然后就把这个推广
能够解决另外一个问题
上次我记得
还给大家留着另外一个题
就是三个人
说三个人啊围桌而坐
在饭馆里面吃饭
当地的一个人跟他的朋友说
你看这里有三个人
就是我们这个镇子上的名人
这三个人的有一个老说真话
有一个老说假话
还有一个是个普通人
有时候说真话有的时候说假话
现在你能不能够
问他们随便谁
一共问三个是非题
然后你能不能判断出来这三个人
谁讲真话谁讲假话谁是一个普通人
这个题目我上次曾经说过
我的一位同事曾经跟我说
他认为这是无解的
这是不可能有这样的三个是非题
这个问题从哪里来呢
是从Knuth的那个书
就是The are ofo programming
他本来打算出7册书
后来出了3册
因为计算机发展太快
他不写了
那个练习题打了双星号就是难难
这是个很难的问题
但是不是无解的问题
如果你靠灵感的话
我这个同事是这个比我聪明多
他也没答出答案来
但是如果你
掌握了刚才我们说的信息交互的概念
掌握了由这个概念产生的方法
那么你就可以很容易的
把这个问题解决
这里我提示大家一下
我不给你解我提示大家一下
这里面也有信息
讲真话讲假话
也有关系
这个你自己去找
现在的物理现象就是他们三个人
围着一个圆桌而坐
而不是谁守卫谁
但是呢要从他们之间的物理位置
找出他们之间的
类似于守卫的关系
然后这个问题就迎刃而解了
留给大家思考
我在课上也不讲了
书上有
我相信你如果掌握好了信息交互
你就会很容易的找到这个解
我们不再浪费时间
前面我们看到了p1
就是第一箭头函数它的petri网表示
我们还讲过一个Q函数
Q函数的网表示呢
是像大家看见的这个
其中有一个b撇和e撇
因为刚才我说过
任何一个这个箭头函数也好
信息交互的函数
它的基本的构建就是p1或者r1
就是第一箭头函数
既然这个是三位信息
他肯定是有两位
p1组成的p1构造出来的
所以不止一个p1
所以第一个p1作用以后
产生一个中间信息
这个中间信息又作为输入
作为第二个函数第一箭头的的输入
因此他会有一个中间这个信息
就是b撇或e撇
其中一个是
作为中间输出
另外一个是作为中间的输入
你要有兴趣的自己去分析分析petri网
看看是不是它的作用像我们说的一样
是在b等于1的时候
交互a或c的值
而b于0的时候a或c的值不被改变
有了前面我们讲的从p1到r1
这个q1就Q这个函数
也就很容易我们就能找到一个
跟它类似的叫做h
03年petri最后一次到中国来讲学
就在香山饭店
讲了将近一个月吧
他那次讲课的时候就提出了这个h
当时我没太在意
因为有Q就够了
就像刚才咱们讲的
有p1就够了用不着r1
那么现在我们想想
Q跟R其实是一对
这个也没有什么神秘的地方
q那就是在b等于1的时候交换a跟c
h是在b等于0的时候交换a跟c
好这样一来我就把
基本的信息交互的这几个函数的讲完了
现在我们来看看这些函数有什么作用
我们有几个命题第一个命题就是
p1和q这两个函数
都是可逆的什么叫做可逆的
就是你作用一次再作用一次
就等于没有作用
ld是什么就是恒同逆守
就是来的时候是什么
出去的时候还是什么
q平方也是q平方也等于这个ld
作用两次等于没有作用
所以Q是Q自己的逆函数
p1是p1自己的逆函数
第二他们两个都是守恒的
当然了
所谓守恒就是有几进就有几出
p1是一进一出
p2是二进二出
pn是n进n出
Q是3进3出
这是第一个命题
第二个命题就是
一切逻辑函数
从n位f的n次方到f的m次方
都可以用箭头函数来构造
一切的逻辑系统
都可以用p1或Q来构造
上面的一切都可以用pn
就是有若干多个
第二个命题告诉你
只需要两个就够
p1或Q就够了
p2以上p2 p3一直到Pn
都可以用p或q来表示
刚才我们看到这些
都可以用petri网来表示
所以这些函数P1 Q Pn
都可以用petri网来表示
他们都是en系统就是基本网系统
所以我们讲的呢叫做
信息流网或者叫信息流系统
刚才我们所看到的这些petri网表示
都可以分解为
所谓的一位噪音通道
这是最基本的元件
一位噪音通道就是我这里画的这个
a等于0或a等于1b等于0或b等于1
a输入b是输出
不管a输入的是1 还是输入的是0
它的输出
有可能是1也有可能是0
不确定所以叫噪音
我不知道你输入了以后它到底会输出什么
所以叫做噪音
一位噪音通道是基础的基础
所有的箭头函数q h p1 r1
都可以分解成一位噪音通道
因此如果我们在设计
信息作用的函数的时候
你如果用电子元件
用硬件来实现的话
只要用这一个原件就够了
我们研究了半天信息流网信息流系统
目的是什么呀
目的是
用这些东西作为核心部件
来构造信息处理器
计算机就是个信息处理
你输入若干个信息
然后计算机经过加工以后有输出
所以计算机就是一个大的信息处理器
所以我们要用这些箭头函数这些基本网系统
构造信息处理元件
再用这些信息处理元件构造大的信息系统
这是我们研究这个的目的
我们看这个就是一个信息处理器
这个信息处理器的核心
原件是什么
就是p1
我就用大的花括号括出来
中间那一部分
就是我们前面见到的p1
这里面的有两位token控制信息
s1和s2里面的token
这个是起控制作用的
我们看s1这里t1或t2
是处于冲突状态因为只有token
t1或t2里面只有一个能够发生
到底谁能够发生
需要环境
也就是从外界输入一位信息
来告诉他是
t1还是t2发生
然后t3和t4共享一个s2这个token
他们也是互相冲突的
他也需要从外界输入一位信息
像这个s1t1t2
叫做一个信息源lnformation source
这就是从外界来一位信息
另外呢
这个s2t3t4是另外一个信息源
当我们从外界得到这两个两个一位信息以后
就经过p1的加工
我们刚才讲的p1是一个
信息交互的一个元件
经过他的加工以后
最后在s7s8s9s10
这里面s7s8得到一个token
s9s10里面得到一个token
t9t10它们是有冲突的
因为他们共享一个输出元素
而这是一个en系统
这里面只能搁一个token
因此这个t9和t10不能都发生
只能有一个发生
这个叫做反向冲突反相冲突
这个时候如果它发生了以后
就会向环境向外界释放一位信息
到底是t9还是t10发生了
我在s11里面得到了一个token
一旦s11里面得到一个token
我就不知道是从哪儿来的
这是t9还是t10
所以这位信息就消失在环境当中了
这叫信息洞
lnformation think
一个洞
同样的t11t12还有s12
这构成另外一个信息洞
这就是一个信息元件
这个信息元件是反复的
这个两个控制token又会回来
在接受两位新的信息
再经过加工
在输出到环境当中去
信息原件怎么由信息函数
信息交互的函数构造信息元件
那么这样
这样可以用p1可以用r1可以用Q
可以用h可以用他们的任何组合
来作为核心处理器
这样的我们就
完成新的信息元件的设计
这一页的内容我已经讲过了
信息元 信息洞
信息的输入 信息的输出
经过p1这个核心函数的作用
输出和输入的就不是同一个信息了
是经过加工的了
得到信息元件以后
我们有什么用呢
刚才我讲了
第一个作用就是
构造信息系统
信息处理系统像计算机系统
如果我们能够用硬件实现
p1r1等等这些信息核心的处理器
那么我们就可以
设计新型的计算机
这个计算机有什么好处
这个计算机刚才我们说了
所有的信息函数他都是可逆的
咱们现在的计算机
一旦您算错了
你的程序有错
你就不知道怎么回到原来的初始状态
而如果用我们这样的
信息元件构造的计算机呢
你就可以重新运行一遍
他就回复了原态了
所以不怕信息丢失
这样的计算机是可逆的
我曾经有过错觉
以为这样会需要信息系统里面
计算机里面保留大量的信息
以便恢复的时候用
其实我们可以看到
不需要
我们只需要保留一个
当前状态
当前的输出
然后你从当前的输出在一步一步
反过来作用
他就恢复了
不需要额外的
只需要保留
信息系统里面当前的信息
不需要把过去的历史记录
都记录在案
那个都丢掉了
因为我们可以恢复
这是第一个
当然现在这只能是一种梦
咱们不是现在都在做梦
为什么我说它是梦呢
因为现在的计算机
已经占有了几乎每一个角落
占有了所有的领域
那些造计算机的人
设计软件的人
正在用这个挣大钱
不可能再重新投资
重新的设计一套
取代现在的计算机
生产的人不愿意投资
用的人可能也舍不得改掉
他已经养成的习惯
已经得到的知识
所以这只是一个梦
我们还可以做第二个梦
就是用这个信息处理元件
来构造保密系统
如果我们手里头有用这个信息
元件构造的
信息处理元件构造出来的一个信息系统
你需要传输的信息
经过这个信息处理系统加工以后
你把这个得到的那个信息传输出去
只要接收的那个人知道
你是用什么信息元件信息处理器
加工以后发给我的
那么我只要再用同样的信息元件处理文件
那我就得到原始的因为他是可逆的
所以这是另外一个梦
我们这个不需要密钥
而且这个信息元件你可以随时
灵活的去临时拼装
我有基本的123456比方说10个
我今天组装的是13576
那么你告诉对方一个数字13576
对方就组装起来这就是你的解码器
下次你换一个数字
而且你可以不断的变换这个元件的代码
所以这个保密呢
可以实现
很容易起到保密和解密的作用
不需要有什么密钥不需要了
这也是一个梦
能不能实现
我不知道
因为我是不做这个
只做理论研究
我这个能力有限
这个想法我已经很久了
但是到现在为止
仍然是个梦
能不能行不知道
凤凰台有一次说了
梦有可能会成真的
我刚才讲的这些他的好处就在于
可逆
我们的信息处理器
都是可逆的
因此我们制造的计算机是可逆的
我们得到的保密系统
是借助可逆可以恢复原件的
信息流网和信息流系统
我就讲到这儿了这部分内容就讲完了
-概述
--Video
-有向网
--Video
-3-1 Petri网定义
--Video
-3-2 Petri网层次系统
--Video
-3-3 基本网(EN)系统
--第一部分
--第二部分
--第三部分
--第四部分
-第三章 Petri网--3-3 基本网系统课后思考题
-3-4 条件-事件(C-E)系统
--Video
-第三章 Petri网--3-4 条件-事件系统课后习题
-3-5 库所-变迁(P-T)系统
--Video
--Video
--Video
--Video
--Video
-3-5 库所-变迁(P-T)系统课后习题--作业
-3-6 网系统层次
--Video
-3-7 高级网系统
--Video
-3-8 化简网系统
--Video
-3-9 非线性网系统
--Video
-3-10 小结
--Video
-4-1 前言
--Video
-4-2 网拓扑
--Video
-4-3 并发论
--Video
-4-4 网逻辑
--Video
-4-5 信息流网
--Video
--Video
-4-6 同步论
--Video
--Video
-4-7 同步论-合同实例
--Video
-4-8 同步论-婚礼教堂实例
--Video
-4-9 同步论 同步器
--Video
-第四章 网论--思考题1
-4-10 实例与方法——电梯控制
--第一部分
--第二部分
--第三部分
--第四部分
-4-11 建模方法论
--Video
-4-12 汉诺塔问题
--第一部分
--第二部分
-第四章 网论--思考题2
-5-1 工作流管理联盟
--Video
-5-2 工作流网(WF_net)
--Video
-5-3 Artifacts
--Video
-5-4 BPMN2.0
--Video
-5-5 学界
--Video
-5-6 业务流程管理(BPM)
--Video
-5-7 BPM建模
--A of ARM
-5-8 流程举例
--第一部分
--第二部分
-5-9 流程之外
--Video
-Petri网小结
--Video
--Video
-6.1 过程挖掘基础
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
-6.2 过程挖掘工具
--Video
--Video
-6.3 过程挖掘算法介绍
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
-6.4 未来研究方向
--Video
-7.1 科研三要素
--Video
-7.2 Program today
--Video
-7.3 Program yesterday
--Video
-7.4 Theory of Programming
--Video
-7.5 A of ARM
--Video
-7.6 R of ARM
--Video
-7.7 M of ARM
--Video
-7.8 OESPA
--Video
-第七章 科研思考--习题
-8.1 树个靶子
--Video
-8.2 八卦与自然
--Video
-8.3 结束语和感谢
--Video
-第八章 总结--习题