Video在线视频

好 下面我们要说一个新的题目

叫作命题联结词的充足集

首先我们说

前面我们也已经看到了

就是每一个真值函数

它都可以用一个符号

也就是用一个命题联结词来表示

比方说我们看

这个（p q）真真 真假 假真 假假

在这种情况之下

如果你是真假假假

那就是合取

你是真真真假那就是析取

你是假真真假

那就是不相容析取

如果你是真假真真

那就是蕴涵

你是真真假真

那就是反蕴涵

真假假真就是等值

我们说还有没有其他的变化

那显然是有的

比如说我可以有一个真值函数是

真真真真

所有情况下我都真

可不可以

当然可以

那么这个我们也要用一个符号

来表示它

所以我们到这里

我们一直说

这是常用的命题联结词

什么叫常用的

那有没有不常用的

有

比如说有一个命题联结词

但是自然语言里边没有

但是意思上我们可以理解的

就是说不管怎么样

不管p和q情况怎么样

它这个函数呢

它永远是真

这是可以的

真真真真

当然也可以是假假假假

那么也可以是比如说

这个里边没有出现的

比如说假假真真

我们这里边没有吧

你可以有一个是假假真真

这里边没有

真真假假也没有

好 那又是一个

假假真真又是一个

真真假假又是一个

所以不同的命题联结词

那我们可以用不同的符号

我们再创造其他的符号

但是为什么不用呢

因为那些是不常用的命题联结词

甚至于在自然语言里边

都找不出跟它对应的东西

所以我们就不说了

但是理论上是存在的

那么我现在要问

理论上存在着多少个不同的

真值函数

否定 析取 合取

这是常用的真值函数

我们现在要打破沙锅问到底

你真值函数到底有多少个

你是有限的还是无限的

如果有限的有多少个

如果是无限的

那么有没有一个规律

那我们说这个呢

问题要给它分开来说

因为这个真值函数啊

我们知道

这个否定这个真值函数

跟析取 合取是很不一样的

为什么

因为它 否定 它处理一个对象

就好像我们前面说到函数

你加减乘除都是处理两个对象的

你说加你得把两个数拿来让我加

乘 你得拿两个数拿来让我乘

但是我说平方

你给我一个数就行了

你给我一个8我告诉你64

加倍也是

你给我一个数

我就可以给你加倍了 翻一番

所以处理一个对象的

那个函数叫作一元函数

那么处理两个的那叫作二元函数

那当然也有三元四元

比如说你拿三个数来

我算它的总和

或者你拿三个数来

我取它的最大

或者你拿三个数来

我取它的最小

或者你拿三个数来

我取它的平均值

这个都是一种处理

都是一种函数

处理三个的叫三元函数

处理四个的叫四元函数

那我们分着来看

处理一个对象的

这个函数有多少个

那么这个在代数里边

在算术里边是无穷无尽的

比如说你平方是一个

那立方也是一个

你加倍是一个

你加两倍也可以

你加1也可以

加1也是个函数啊

你给我一个5

我给你6

你给我80我给你81

你给我10000

我给你10001

在它后面的一个

这个花样是层出不穷的

但是我们现在讨论的是真值函数

真值函数就比较容易

因为真值函数

它的定义域和值域

都是只有两个东西

真和假

我们说过一个真值函数呢

一个函数它就是相当于一个装置

处理东西的一个装置

那么一个真值函数呢

也是这样

比如说我现在很简单

我就处理一个对象的

一元真值函数

我们看一元真值函数

当然我们碰到的只有一个 否定

但是理论上有多少个

我们不难得到

比如说我现在是

这是一个装置

这个装置是一个处理

一元函数的

处理一元真值函数的一个装置

怎么样呢

就是我有一个输入端

有一个输出端

输出端比如说一个灯亮或者不亮

我输入端呢

因为我现在是逻辑

我是真值

真值只取两个

所以这个输出就是一个

就是一个输出端

而且这个输出端就两种情况

就是这个灯亮

或者这个灯不亮

当然也可以是一个铃

铃响或者不响

反正两种情况

这个灯亮或者不亮

然后输入也是只有一个

因为我现在一元我只处理一个

一个比如说是有电

或者是没有电

就两种情况

有电没有电

前边这个灯亮或者不亮

那么好 我们看这样的装置

能有多少种花样

第一种装置

我给它一个电

我有电它这个灯不亮

我把这个电断了

它这个灯就亮了

那么这是什么

我们知道家里边没有这样的灯

但是公共场所都有这样的灯

叫应急灯

应急灯在正常供电的情况下

它是不亮的

一旦断电

这个灯立刻大放光明

那么这是一种装置

这个装置是什么呢

就相当于我们那个否定

真的变假的

假的变真的

有电 不亮

没有电就亮了

好 这是一种装置

第二种装置

给电它就亮了

不给电就不亮

这是我们家里边的正常的电灯

这又是一种情况

第三种情况

给电这个灯是亮的

电断了这个灯还是亮的

这个很奇怪当然也不奇怪

它里边有蓄电池

那么好 这又是一种情况

就是不管你给电不给电

这个灯都是亮的

那么当然第四种情况就是

给电不给电

灯都是不亮的

这个灯是坏的

有没有第五种情况

没有了

不可能有第五种情况

因为它的真值的组合

只有这几种

因为你这个进去的

只有有电没电两种情况

它这个输出的是灯亮灯不亮

也是两种情况

你组合起来只有四种情况

所以说一元真值函数

理论上只有四个

一个是否定

一个就是你什么也不写

就是p本身

一个是永远真

一个是永远假

永远真是p或者非p

永远假是p并且非p

这个当然是我们用比较复杂的

简单的你就可以用一个命题联结词

那么一共有四个命题联结词

一个叫作就是普通的

一个叫作否定

（1）一个叫肯定

（2）一个叫否定

（3）一个叫全真

（4）一个叫全假

你可以用这四个

有没有第五种情况

不可能了

因为我们现在只考虑

一个输入一个输出

输入只考虑两种情况

输出只考虑两种情况

所以不可能还有第五种情况

如果你找到第五种情况

找到第五个装置

一定它和我前面四个装置里边的

某一个装置

它的功能是一样的

你结构可以不一样

但是它的功能是一样的

从功能来说只有这四种

一元的

那么二元的要复杂一些了

就是它有两个输入

有一个输出

那么就是说一个是

两个都有电

它是亮的

一个有电一个没有电

它是怎么样的

这个有电那个没电

它是怎么样

两个都没电是怎么样的

这是一种情况

然后第二种情况第三种情况

那么一共能有多少种情况呢

我们来看

因为我们现在这个是比较乱的

这个是真假假假

这个是真真真假

我们说还可以真真真真

还可以真真假假

假如你按照某一种规律来安排

比如说第一种

你也不用什么析取合取什么了

你用1 2 3 4 5 6 7 8 9

你看一共有多少种

真真真真

真真真假

真真假真

真假真真

假真真真

你反正用某一种

你比如说用1和0

你用进位也好退位也好

你看一共有多少种组合

如果是两个的

你从真真真真

真真真假

真真假真

退退退

最后退到假假假假

一共有多少种

大家不难想到

多少种呢

如果是两个的话

应该是16种

就是这样的花样啊

有16种

我们现在这个里面是1 2 3 4 5 6

6种

你还可以想出10种来

真真真真

假假假假

真真假假

假假真真

你还想得出10种

但是你想不出第11种了

第11种一定是和

因为我们已经有6种了

你再加上那个10种 16种

你再想到第17种

一定和这个前面16种

中间的一种是完全相重合的

所以我们说

存在多少个不同的真值函数呢

要看它的元数

一元的4个

二元的16个

三元的呢 我处理三个东西

我处理三个东西

那当然写起来更复杂

那么要多少个呢

我们可以想到应该是256个

那么也就是说存在多少个不同的

n元的真值函数

或者说有多少个不同的

n元命题联结词呢

它是由 2的 2的n次方

也就是n=1

那么它等于4

n=2的话

2的4次方

那就是16

如果是n=3

那就是256

那么依此类推

所以我们就可以看到了

就是说真值函数呢

它是无穷无尽的

因为你那个n元

这个n

它可以根据自然数来增加

自然数是无穷无尽的

所以真值函数的花样是无穷无尽的

但是当你的这个n确定以后

那么这个真值函数的数量

是确定的

好 那我们就知道了

命题联结词有多少个

一元的有4个

二元的有16个

三元的有256个

n元的有 2的 2的n次方 那么多

不同的真值函数

但是我们又知道

虽然理论上存在着那么多的

命题联结词

但是有一些是可以不用的

比如我们刚才说

二元的命题联结词

我们这里列了6个

你还可以列出10个来

我们已经知道这里边有些是不用的

是可以不用的

你这里（反蕴涵）可以不用

你把它倒过来

你把这两个倒过来就变成这个（蕴涵）

那么这个（反蕴涵）就可以不用

我们同样的道理我们前面说过

这个不相容析取可以不用

等值也可以不用

因为你用它们其他的东西

经过有限次的组合就可以了

这样我们打一个比方 什么呢

比如说自然数是无穷无尽的

自然数有多少

那数不完的

但是用来表达用来表现

用来标记自然数的数码

可以是有限的

自然数是无穷无尽的

那我们需不需要无穷无尽个符号

来表达这无穷无尽个自然数呢

我们说是不需要的

我们日常只用十个就够了

1 2 3 4 5 6 7 8 9 0就够了

因为你再多没关系

你超过了9个我10

你再超过我11

我可以用它们重复 十进制

所以我们十进制的话

我们用十个数字

就足够表达所有的自然数了

自然数是无穷无尽的

用来表达自然数的这个数码

它是有限的

那么同样我们说

这个真值函数

它是无穷无尽的

但是我们用来表达它们

可以不一定要那么多

可以用有限的若干个就可以了

那么这就是我们下边要讨论的

就是命题联结词的充足集

什么叫命题联结词的充足集

这个充足集有的教科书上

翻译成完全集也可以的

命题联结词充足集是这样的

这个集合它是若干个

命题联结词的集合

就是这个集合里边的元素是什么

这个集合里边的元素

是命题联结词

那么这些命题联结词怎么样呢

用这些个命题联结词

当然要加上命题变元p{\fs10}1{\r} p{\fs10}2{\r}……

p q r s t…… 要加上这些东西

用这些命题联结词和命题变元一起呢

经过有限次的重复和组合

就可以表示任意的真值函数

我们还是拿刚才那个比方来说

我们可以说

表达自然数的数码的充足集

什么叫数码的充足集

就是你有若干个数码

用这些数码呢

它经过有限次的重复和组合

它可以用来表达所有的自然数

那么1 2 3 4 5 6 7 8 9 0

或者说0 1 2 3 4 5 6 7 8 9

这就是表达自然数的字码的充足集

因为我用0到9这（十）个字码

我足以经过

你要允许我重复

允许我组合

我用不同的方法重复和组合以后

我可以用来表达任何

任意大的自然数

你自然数不管有多么大

我用这（十）个字码足够用了

那么所以就是个充足集

那么这里也是

命题联结词

你这个真值函数虽然无穷无尽的

2的 2的n次方

但是我用来表达它们的命题联结词呢

我只用有限个就可以了

那么什么样的命题联结词的集合

是充足集呢

首先我们说 否定 合取 析取

是充足集

为什么

刚才我们说了一个

非常重要的结论

范式存在定理

范式存在定理怎么说的

你不管什么样的真值函数

你不管什么样的复合命题形式

我都可以用一个范式来代替它

而范式里边我们知道

根据范式的作法

它的命题联结词只有三种

否定 合取 析取

其他的没有的

蕴涵 反蕴涵 等值都没有

都不需要

否定 合取 析取三个

足以用来

当然加上p{\fs10}1{\r} p{\fs10}2{\r}……

加上括号

而且它们本身允许它们重复

允许它们各种方法的组合

这可以用来表达所有的真值函数

所有的复合命题形式

所以 否定 合取 析取

是命题联结词的充足集

这是非常重要的一个结果

它告诉我们命题联结词的花样

虽然有那么多

但是三个足够了

否定 合取 析取

这三个就足够了

这个同时也回答了

就是我们说开关电路上的一个问题

我们知道 与门 非门 或门

它们经过有限次的重复和组合

可以用来解决一切

就是二值范围之内的

就是你灯亮或者不亮

灯开或者关

你不要有第三种情况

有第三种情况那个情况复杂一些

那另外再讨论

我们讨论就是说

灯亮和不亮

不管你有多少灯

不管你有多少个开关

你开关 每一个开关

就是“开 关”两种情况

每一个灯就是“亮 不亮”

两种情况

亮和暗两种情况

那么用 或门 与门

非门 这三种足够了

是不是需要第四种

不需要

这三种足够解决一切这样的问题了

谁可以保证这三个一定可以

我们说范式存在定理来保证

因为 否定 合取 析取

它对应

它对应非门 与门 或门

你不管什么样的复合命题形式

不管什么样的真值函数

我用这三个够了

因此你同样的你不管什么样的

那一类的问题

你用 或门 与门 非门

这三个一定够了

所以它也回答了应用上的一个问题

那我们说 否定 合取 析取

这三个是充足集

有没有其他的充足集

比如我们说

0 1 2 3 4 5 6 7 8 9是充足集

这个充足集能小一些吗

可以的

0 1 2 3 4 5 6 7也可以的

八进制

八进制同样可以

不一定要十进制

用八进制

八进制的话不要8和9

从0到7

它也可以用来表示所有的自然数

我们说八进制还太麻烦

二进制

1和0

只要两个

1和0我只有两个

它是不是表达自然数的充足集

是的

不管你有多么大的自然数

用1和0来表达足够了

当然代价是这个式子要写得长

如果我们都用十进制的话

计算机里边用十进制

你要给它设置十种状态

比较麻烦

所以计算机里边用二进制

那我们日常生活也用二进制

行不行呢

用二进制理论上说也可以

但是我们会非常麻烦

我们每个人有一个身份证

你出去旅行的时候

你经常要填你这个身份证的号码

我们现在身份证是十进制的

如果我们的身份证用二进制

那你想想我们的身份证得多少位

能不能背下来

我想大部分人就背不下

他的身份证的号码了

我们现在十进制的身份证

已经有很多人背不下来了

如果是二进制的身份证

恐怕绝大多数人都背不下来

所以我们日常生活还是要十进制

所以十进制 二进制

各有各的用处

那么同样的我们说

否定 合取 析取

三个它足以解决一切问题了

能不能让这个再小一点呢

我们说是可以的

我们看

如果A析取B

我可以不用析取

我可以用否定和合取

经过有限次的组合来代替它

也就是说比如说

我说你去或者他去

这句话意思是你们两个

至少有一个人去

你去或者他去

我也可以不这么说

我也可以说

你不去并且他也不去是不行的

不能你不去他也不去

这两句话是一样的

但是这句话我就可以不用那个或者

但是代价是长了

倒过来也是一样

合取也是这样的

你也可以不用合取的

你可以用

并非 非A或者非B

来代替 A合取B

同样还是刚才那个例子

你去并且他去

就是你们两个都得去

你们两个都得去等于什么呢

就是说你不去或者他不去

是不行的

不要你不去或者他不去

意思就是说

你们两个有一个人不去都不行

意思是你们两个都得去

跟这是一样的

当然我们说

这个和这个是等值的

我们从直观上可以知道是等值的

但是严格的怎么样

你作真值表

你这个下面作一个真值表

这个下面作一个真值表

你会发现这一列和这一列是一样的

真值表我们已经作得很多

我们在这里不再作了

作为复习大家可以自己去作

你可以证明这个和这个是等值的

这个和这个是等值的

那么好

既然否定 合取 析取够用了

那么凡是出现析取的地方

你用否定和合取来代替它

那么好 我否定和合取呢

我本身就是充足集

正如我们十进制里边的

2 3 4 5 6 7 8 9

我用0和1都可以表示

所以我0和1这两个

它也是充足集

所以我们说否定和合取也是充足集

否定和析取也是充足集

那么这个呢

又少了一个了

析取不要 合取不要 都可以

但是代价是会写得很长

比原来写得更长一些

那我们说还有没有其他的花样呢

就是 否定合取 否定析取

有没有其他的花样做它的充足集呢

我们说有

我们来看

A析取B

我可以写成非A蕴涵B

A合取B

我可以写成并非A蕴涵非B

这两个是等值的

我们可以用真值表来证明

这两个也是等值的

我们可以用真值表来验证

我们直观上也可以验证

你去或者他去什么意思啊

如果你不去

那么他去

是不是一样的

当然你直观上会觉得

那我还得倒过来说

如果他不去那么你去

不需要

这个我们日常语言里边

有其他的色彩

所以你会觉得还需要倒过来说

其实不需要

仅仅从真值的角度来说

你只说一个方向够了

怎么见得

你用真值表来验证

你会发现这两个是一样的

那么同样你去并且它也得去

你们两个都得去

那么就是说什么呢

你去的话他不去

那么是不行的

就是不要如果你去

那么他就不去

那这个等于说

A和B都得去

当然你直观上你会觉得

好像不太一样

这是因为直观上

我刚才说的你去他不去

这个里边的而且 不

这里边有其他色彩

如果你完全纯粹地在真值的角度

这两个是一样的

何以见得

真值表

所以我们看

既然你析取可以用它们来表示

合取可以用它们来表示

因为你否定合取

你否定和析取是充足集

否定和合取是充足集

那么我现在否定仍然用

我否定和蕴涵

否定和蕴涵可以代替你这个合取

否定和蕴涵可以代替你这个析取

所以否定和蕴涵

也是命题联结词的充足集

你看没有合取析取也是可以的

否定和蕴涵两个

也可以作为命题联结词的充足集

所以结论是我们看到

根据范式存在定理

否定 合取 析取

是命题联结词的充足集

根据我们刚才那几个等式

否定 合取 也是充足集

否定 析取 也是充足集

否定 蕴涵 也是充足集

关于命题联结词的充足集

我们先说到这里