Freewind @ Thoughtworks scala java javascript dart 工具 编程实践 月结 math python english [comments admin] [feed]

(2012-12-01) 离散数学学习疑问 – 真值函数

广告: 云梯:翻墙vpn (省10元) 土行孙:科研用户翻墙http proxy (有优惠)

在《离散数学(耿素云、屈婉玲编著)》这本书里第37页(第二章命题逻辑等值演算 2.3 联结词的完备集)里,提到了n元真值函数。

对于这个概念,我想了几个小时终于基本想通(可能还不正确),先记在这里,怕又忘了。n元真值函数的定义不贴,只贴我的理解。

最难理解的地方在于:n个命题变项,可以构成22n个真值函数。为什么有22n个?

还有它给出来的表,

image

也不太理解。里面的F0/F1等等,到底指什么?

当我想通这个问题时,脑海中冒出一句话:数学就是不断的抽象,在抽象的基础上进一步抽象。

现在先不管F函数,先看前面讲的比较好理解的极小项(极大项)的概念。

极小项就是一个抽象,对于一个含有2个变项的命题来说,m0代表的是:

┐p ∧ ┐q

m1代表的是:

┐p ∧ q

对于3变项的命题来说,m0代表的就是:

┐p ∧ ┐q ∧ ┐r

这对于简单变项来说,极小项与极大项是一层抽象。以前看到的都是p, q之类,现在研究的都是它们的组合(只是用简单的符号代替了),就像是“字”与“词”的关系。眼睛清静了,但脑袋里的抽象层次要高一层。

等到真值函数时,抽象又高了一层。

变项之间可以通过联结符组成无穷无尽个命题。研究无限的东西总是比较困难的,能否把它们变为有限的什么?

这无限个命题中,有很多其实是互相等值的。如果把每个命题都化简为它所对应的唯一的主合取范式或主析取范式,那么等于把这无限个命题分成了很多组。每个组中各命题都可以化简为同一个主范式,而组的个数是有限的。对于n个变项来说,它的主范式个数为22n个,即分成了22n个组。

这样就把无限变为了有限。

然后为了方便研究这“有限个主范式”,提出n元真值函数的定义F。F是个黑盒子,它只管内容,只看输入和输出。

以2元真值函数为例:

image

它有222,即16个真值函数,分别定义为:imageimage,这些函数到底是什么样子的呢?

每一个真值函数,都对应着无数的命题,只要它们的输入和输出满足这个条件:

image

则都可以以image代之。观察它,可以发现,不论输入是什么,值总为0,是一个矛盾式。故所有的由2个变项组成的矛盾式都与它等值。

再看image,它可以有很多形式,比如:

p -> q <=> (┐p ∨ q) <=> ┐(p ∧ ┐q) <=> (┐p ∧ ┐q) ∨ (┐p ∧ q) ∨ ( p ∧ q ) <=> …

这些不同的命题,它们虽然形式万千,但输入与输出都满足这个条件:

image

如果用最小项来表示,是这样的:

m1 ∨ m3 ∨ m4

看到这里,前面的极小项已经成为了它的一个基本单位,可见抽象层次又提高了一层,到达了“句”。

先写到这里,在写的过程中,几次写不下去,发现自己理解上的错误。现在也还不是十分的清楚,等以后再有理解后补充。

comments powered by Disqus