Video在线视频

前面我们已经了解了

所谓命题联结词的充足集

我们看到就是正如我们十进制的

是表达自然数的充足集

二进制的也是充足集

那么同样我们在这里

否定 合取 析取是充足集

合取和析取可以去掉一个

否定 合取也是充足集

否定 析取也是充足集

另外我们还有一种花样

就是说否定 蕴涵

它也是充足集

那么下面我们继续地来

也可能是要钻牛角尖

我们说十进制到八进制

八进制又到二进制

两个就够了

我们现在问

能不能再少一些 二进制

一进制可以吗

大家说一进制一定是不行的

不一定

一进制可不可以

一进制应该说可以的

你看汉字一怎么写

一

二呢

再加一横

三呢

再加一横

四呢

古代的汉字有写四横的

现在没有了

那么从这里可以看到

这似乎是可行的

我们知道有一个

大家都知道一个笑话

小孩学校里边上学

一 画一杠

二 画一杠

三 画一杠

知道了知道了

回家爸爸让他写封信

写给姓万的人

哎呀写不完

他为什么要姓万

我这写不完

但是我们说这个万

并不是写不完

你在一分钟之内可能是写不完

你时间要长一些

万是可以写完的

是可以写出来的

所以一进制对于这个自然数来说

是可以的

它当然 一进制不能代表0

你什么也不写不行

但是你从1开始

理论上是可以的

一万你就写一万笔

一万条杠

三万五千你就写三万五千条杠

是可以的

理论上是可以的

但是非常不方便

方便不方便是另外一回事情

能不能够成立又是一回事情

所以一进制可不可以成立呢

一进制是可以成立的

就是作为字码来说

表达除了0以外的自然数

传统数学里边自然数

从1算起

现代数学里边自然数从0算起

那么我们说从1开始的自然数

你不怕麻烦的话

用一进制理论上是可以的

二进制可以

一进制也是可以的

不过很不实用

我们不会用它

但是理论上是存在的

那么我们来看命题联结词

刚才说三个已经减到两个了

一个行不行

大家说一个恐怕不行

我告诉大家一个是行的

一个 谁呢 大家马上想到一定是否定

否定不行

为什么

否定它是个一元联结词

一元联结词它要处理两个东西

它没法处理

反过来二元联结词

它倒可以处理一元的

可以处理三元的

因为二元联结词要处理一元的东西

它两个东西

它两个输入端

你采用同一个信号就可以了

那么你二元的要处理三元的呢

你两个两个来处理就是了

三元四元你一个一个加上去处理

就可以了

所以它至少得是个二元的

那么什么样的命题联结词

是可以做一元的充足集的

那么就是我们现在看到的

这个符号

向下的一个箭头

那么它

我们看它的真值表

它的真值表是这样的

两个都真的时候是假的

一真是假是假的

一假一真是假的

两个都假是真的

这个很奇怪

自然语言里边有哪一个词

跟它一样的呢

没有

自然语言里边没有跟它对应的东西

但是我们会发现

它是假假假真

跟什么东西正好相反呢

跟那个析取正好相反

析取是真真真假

所以它是析取的否定

析取的否定呢

所以给它一个名字

就是析取是或者

或者是or

or前面加上一个表示否定的

一个前缀n

就是nor

这个nor就是or的否定

那么中文就翻译成或非

就是或者的否定叫或非

那么好

这个或非它的真值表是这样的

我们说或非 我们想要证明

它是一个能够表达所有

命题联结词的充足集

怎么来证明呢

很好证明

因为我们前面已经有根据了

我们前面已经知道了

否定 合取 析取是充足集

否定 合取是充足集

否定 析取是充足集

否定 蕴涵是充足集

所以你只要说

你能够独立地经过有限次的

重复和组合

你能够只用这一个命题联结词

你能够把否定表达出来

然后合取 析取 蕴涵这三个里边

你只要能表达一个

那我们就可以承认

你是充足集了

是不是

是这样的吧

因为你 否定合取 否定析取

否定蕴涵

都是充足集

所以你先得有一个否定

你一定要能够把否定表达出来

然后你合取 析取 蕴涵

这三个表达任何一个都可以

所以我们看看

它能不能独立地来表达否定

表达合取

表达析取

我们看

A或非A

那么你看因为A真假两种情况

这个跟这是一样的

它两个都真是假的

两个都假是真的

所以你看真的

因为它本来是一个二元的东西

它是个二元的命题联结词

你现在处理一个对象

你处理一个对象可以啊

一个对象你两边都有同一个对象就是了

所以虽然这里有两个

但是你这个真值表你写两行就够了

因为这里只有一个命题变元

只有一个A

你看这个当它是真的时候它是假的

它是假的时候它是真的

那么这个恰恰跟否定是一样的

所以我们看到

这个或非可以独立地表达否定

好 我们再看

A或非A

或非 B或非B

那么这里有A和B两个了

所以（A B）是有 真真 真假

假真 假假

这一列和这一列是一样的

这一列和这一列是一样的

然后我们来做或非

真真是假

真真假

假假真

假假真

然后真真假

假假真

真真假

假假真

然后这一列和这一列来作或非

我们看

假假真

假真假

因为它只有两个假才是真的

其余都是假的

真假假

真真假

你看真假假假

好 这就跟（A B）真真 真假

假真 假假

这个合取是完全一样的

真假假假

真假假假

好 我们已经证明了

它可以独立地表达刚才的否定

还可以独立地表达合取

实际上我们证明到这里

就可以结束了

但是我们把它怎么表达析取

也给大家展示一下

它表达析取是这样的

A或非B

或非 A或非B

我们作它的真值表

大家可以自己慢慢地看

那么它最后得到真真真假

和这个析取真真真假

是完全一样的

所以它可以表达合取

可以表达析取

可以表达否定

表达蕴涵也可以的

要长一些 我们在这里就不写了

那么在这里我们已经可以证明了

因为我们已经证明

否定 合取 析取是充足集

那么你既然它自己独立地

经过有限次的重复和组合

可以表达否定

可以表达合取

可以表达析取

所以我们可以证明或非

是命题联结词的充足集

这是很奇妙的结果

我们说2的2的n次方

那么多个不同的

命题联结词

居然用一个就可以表达了

而且这个或非

是析取的否定

大家可能会想到

合取的否定是不是也有这种功能

是的

合取的否定也有这种功能

我们看它的这个符号

这个叫做与非

我们看它的真值表

它是假真真真

我们知道合取是真假假假

它和合取相反

合取是与是并且

所以它是and

前面加上一个表示否定的前缀n

就变成nand这么一个词

那么nand我们翻译成与非

与的合取的这个否定

与非

那么它的真值表是这样的

那么它和或非一样

也可以用来独当一面的

表达否定 合取 析取

我们来看是这样的

实际上呢

跟或非是非常近似的

这个跟或非一样

它这个和这个值

然后呢

刚才是这个式子和这个等值

这个式子和这个等值

它现在是A与非B

与非 A与非B

跟这个A合取B等值

那么这个和这个等值

那么这个等值怎么见得

作真值表

我们这里就不作了

有兴趣的你可以

按照前面的真值表

你把这个这个作一个真值表

你会发现是一样的

这个和这个作真值表以后发现

这两个是一样的

这个和这个是一样的

因此我们证明

因为已经知道否定合取析取

就跟刚才一样的

这是充足集

那么因为有这些个等值

其实这两个只要有一个就够了

那么我们知道

我们可以证明与非

也是命题联结词的充足集

那么这两个符号

一个或非

一个与非

那么称为Sheffer stroke

或者是Sheffer bar

翻译成就是谢弗尔竖

谢弗尔是发现这两个符号的人

这两个符号呢

它是命题联结词的单元素充足集

也就是说否定 合取 析取

是充足集

否定 合取充足集

否定 析取充足集

否定 蕴涵也是充足集

但是它们有两个或者三个元素

但是这个充足集呢

它这个集合里边只有一个元素

这个集合里边只有一个元素

所以是叫做命题联结词的

单元素充足集

或者叫做独元充足集

就是独立一个元素的充足集

这是非常奇妙的结果

就是一个命题联结词

它可以独当一面

表达所有的命题联结词

而且还有两种方案

那么这个呢

在开关电路中呢

也有具体的运用

因为我们说一个叫做或非

一个叫做与非

在数字电路中呢

它们就有或非门

也有与非门

那么或非门和与非门

它的功用就是说

我只要有一种开关就行了

我只要有一种与非门就行了

我不需要什么或门与门非门

我只要有一种或非门

那么所有的你这个灯

不管有多少个

你只有亮不亮两种情况

开关不管有多少个

只有开不开两种情况

不管有多少个 有多么复杂

你有多少个灯 多少开关

不管有多么复杂

你用或非门一种

或者你用与非门一种就足够了

当然它的代价是或非门

肯定要用很多

与非门肯定要用很多

但是从品种来说

它只需要一种就可以了

这个仓库里边

它只要有一种零件

很多很多就可以了

它不需要这一种多少

那种多少

所以也有它的用处

所以我们数理逻辑里边

我们的充足集

你可以用一个的可以用两个

可以用三个

你也可以多用一些

用六七个也可以

你三个已经够了

我多用一些也可以

你二进制本来够了

我用十进制当然也可以

那么数字电路 开关电路里边也是

你用或门 与门 非门三种也可以

你就用或非门也行

你就用与非门也行

好 我们这一讲呢

说了两个问题

一个是范式

一个是命题联结词的充足集

这一讲就到这里