演绎推理和因果关系

http://bbs.oursci.org/newreply.php?postid=30829

------------------------------------
30829-疑问 又是问题: 演绎推理和因果性 是什么样的关系?
作者:uncutstone
时间:2004-12-29 11:50

------------------------------------
30886- 不知道你所说的因果性是什么概念……
作者:荒唐
时间:2004-12-30 08:10

演绎推理是根据一些假定得出假定成立时必然成立的判断。至于是谁是因谁是果,跟前提和条件之间并没有对应关系。

例如,你发现米饭烧糊了(前提),结合一些环境因素以及以往的经验(前提),可以推断出烧干锅了(结论);你做饭时发现烧干锅了(前提),结合一些环境因素和以往的经验(前提),也可以推断出米饭会被烧糊(结论)。虽然我们认为烧干锅是米饭糊的原因之一,而不是结果,但结果仍然可以做为前提,原因仍然可以做为结论。

所以前提、结论并不等价于因、果。虽然在包含了如何判断谁是因、谁是果的判断规则的逻辑系统中,也可能可以利用演绎推理来得出哪个是因哪个是果,但因和果却不一定是前提和结论的关系。

因果关系的通常理解除了逻辑上的蕴含关系之外,还跟时间顺序有关。如果我们要在严格定义因果关系的同时,不破坏这个概念在日常不精确语言中的中心含义,就必须把时序也考虑进去。我没有仔细研究过日常语言中因果关系的核心含义是什么,不能随便给出一个因果关系的定义,但我想时序可能是不可忽略的要素。前提和结论虽然在语言中似乎也有先后之分,但是在数学中这两个概念跟时序没有任何联系,只是由于它们借用了不精确的日常概念,从而容易引起误解。

爱因斯坦说过:
只要数学的命题是涉及实在的,他们就不是可靠的;只要他们是可靠的,他们就不涉及实在。

我认为因果关系应该是一种描述实在(物理世界)的概念,他们跟前提和结论这种数学世界的概念的是不可等同看待的。

关于逻辑中的蕴含关系

http://bbs.oursci.org/newreply.php?postid=30793

------------------------------------
30793- 另一个迷思, 请教
作者:uncutstone
时间:2004-12-28 19:04

有两个真值函数 p , q.
如果 p->q 取真值, 不表示p 是 q 的原因。
p->q 永取真值, 也不表示p 是 q 的原因。
p=>q, 也不表示 p 是q 的 原因。
-> 表示逻辑连接词 if ..then ..
=>表示逻辑推论

举一个例: 1+1 =2 => 饭可以吃。 谁也不是谁的原因。

还是感觉违反直觉。按照通常的理解, p=>q, 那么p 是q的一个原因。

愚钝啊。 🙁

------------------------------------
30876-高兴 我尝试解释一下:
作者:荒唐
时间:2004-12-29 21:32

我怕我们使用的符号不一致,
所以先说一下命题逻辑的符号约定:
 非:~
 与:&   a&b严格等价于~(a->~b)、~(~a|~b)
 或:|   a|b严格等价于~a->b、~(~a&~b)
蕴含:->   a->b严格等价于~a|b、~(a&~b)、(a<->b)|b
等价:<->   a<->b严格等价于(a&b) | (~a|~b)

约定从上到下运算优先级从高到低。
只要有~运算外加&、|、->三者之一,就可以推出其余逻辑运算符

上面这些命题逻辑的符号,包括->,都是一种运算符号,他们的左项和右项无需有任何关系。

a->b的含义是,只要不是a真b假,a->b的值就是真,并非a能推导出b或者a是b的前提。把->当作if…then…实际上很容易引起误解。
所以“1+1=2 -> 饭可以吃”这个公式并非表示前者是后者的前提,仅仅表示如果前者是“1+1=2”后者是“饭可以吃”就可以让这个公式取“真”值。仅此而已。

你所提到的符号=>,含义应该是下面两个符号之一(我的书里面大部分使用下面这两种符号):
逻辑后承:|=
逻辑推论:|-(也就是推出)
这两个符号定义不同,但命题逻辑的完备性定理证明了这两个符号是等价的。
一个命题是一组命题的逻辑后承(|=)表示如果该组命题为真,那么该命题就必为真。
而一个命题是一组命题的逻辑推论(|-)表示这组命题按照直接推导规则能够在有限步骤内得到该命题。
命题逻辑所定义直接推导规则只有一个:a, (a->b) |- b
(一阶逻辑增加一条基本推导规则:A |- (for all x)A。)

此时a & (a->b)确实可以作为b成立的前提条件,b确实可以看做是他们的逻辑结论。而如果写“1+1=2 |- 饭可以吃”是错误的,没有这样的推导规则。这样写才是正确的:“(1+1=2 -> 饭可以吃), (1+1=2) |- (饭可以吃)”

意思是说,只要你规定了“如果1+1=2为真,那么饭可以吃就必为真”这件事情是必然的,那么此时只要“1+1=2”也确实为真,就一定可以逻辑第推断出“饭可以吃”这个逻辑结论。

这个逻辑推论的真实性是并非直接是因为“1+1=2”,而是基于上面的两个前提的真实性。上面的真实性是你规定出来的,并非逻辑系统能够判断出来的。

------------------------------------
30892- 这里有点误解, 我解释一下
作者:uncutstone
时间:2004-12-30 09:58

我写的 ‘1+1=2’ 和 “饭可以吃”, 意思是这两个命题分别都是永真命题。
所以命题 ‘1+1=2’ ->“饭可以吃”, 也是永真的。
那么根据 ‘|-’ 的定义, 如果p-> q 永真,有 p |- q.
所以我有 ‘1+1=2’ |- “饭可以吃”。 也就是说, 如果任意两个命题 A , B 永真, 就会有 A |- B, B |-A. 一个永真命题可以推导出任何一个永真命题。

我的理解, 一个永真的蕴涵就是一个逻辑推论。这个地方有一点自相似性, 容易让人糊涂。

------------------------------------
30923-哈哈 嘿嘿,你对永真的理解错了啦……
作者:荒唐
时间:2004-12-30 13:51

形式逻辑中的永真式(重言式)是指逻辑系统内部的公式,永真式中任何一个项无论取什么样的值,式子本身都保持真。

例如A<->A、A|~A、~(A&~A)这些都是永真式。

而“米饭能吃”核“1+1=2”这两个命题在逻辑系统内部根本是不可能判断真假的,所以它们根本不是(逻辑系统的)永真式。

------------------------------------
33050- “蕴含”可以理解成“如果…那么…”
作者:荒唐
时间:2005-01-25 16:30

日常生活中的“如果…那么…”在“如果”不成立的时候没什么用处,但在逻辑运算中,“如果”不成立也有真值,其真值为“假”。

“推出”(|-)也可以看作是“如果…那么…”,但“推出”这个东西不是用来参与逻辑运算的。

推导规则就是把“|-”和“->”二者联系起来的东西。

推导规则是说,如果“如果A那么B”为真,同时“A”也为真,那么我们可以“推出”一个逻辑结论:“B”为真。

你只需把逻辑公式当做有真假的判断句,由逻辑运算符连接起来的句子也是有真假的逻辑公式,“->”理解为“如果……那么……”并且即使句子错误的也可以利用这个句子的“假”值。

推出“|-”除了它不用来表示逻辑运算,而是用于逻辑推导过程之外,跟“->”没有什么区别就行了。因为如果再使用“->”表示推出,那么推导过程就被这个东西连接成了一个整个的逻辑表达式了,为了避免这种情况出现,就制造了一个专门用于表示推出的符号“|-”。

------------------------------------
32610- 逻辑推导规则并不需要真值表才能定义。
作者:荒唐
时间:2005-01-19 15:20javascript:void(0)

“->”仅仅是“蕴含”这个“逻辑运算”的符号,并不表示“推出”

命题逻辑只有一条基本推导规则(其它规则可以导出):
A, A->B |- B
意思是说,只要有A和A->B二者成立,那么可以推导出B。

一阶逻辑增加一条基本推导规则:
A |- (for all x)A

Goodstein定理

http://bbs.oursci.org/newreply.php?postid=31376

------------------------------------
Goodstein定理——歌德尔不完全定理在皮亚诺公理系统中的一个例子
作者:冷饭
时间:2005-01-05 18:45

从非常非常粗糙的角度讲,歌德尔证明他的不完全定理的方法,就是构造了一个类似“本命题不可被证明”这样一个命题。当然这个陈述是很不严格的,因为现在逻辑中禁止在命题中提到“本命题”这样的玩意,另外,“证明”不是一个在皮亚诺算术系统中定义了的概念。歌德尔证明中的主要思想之一,就是如何解决后一个难点。这个就不具体说了。

在歌德尔不完全定理被证明时,大多数数学家并不太担心自己会实际上碰到这样的既真但又不可被证明的命题,因为这样的命题似乎都是一些很怪的绕来绕去的人造玩意,在数学中被实际研究的问题,应该不会是这样的。现在大多数数学家应该还是这个心态,比如说研究歌德巴赫猜想的很少会去怀疑这个命题会不会是在集合论公理体系下解决不了的。

但是有一些看起来很自然的命题,已经被证明是不能在某些公理体系下证明的。在这里我介绍其中最早被发现的这样的定理之一:Goodstein定理。

任取一个自然数n,比方说266,我们把它写成以2为底的幂次的和,其实就是转成2进制:
266 = 2^8+2^3+2
现在右边还有比2大的数字比如说8啊3啊,就进一步转换变成
266 = 2^2^3 + 2^(2+1)+2
还有一个3,继续写成
266 = 2^2^(2+1) + 2^(2+1)+2

可以知道,无论什么自然数都可以唯一地写成这样的形式。同样地,如果不是以2为底而是以其他大于2的自然数为底,也可以做同样的事情。

现在我要把刚才那个式子的右边中的所有2都改写成3,那就成了
3^3^(3+1) + 3^(3+1)+3
再减去一个小小的1,就成了
3^3^(3+1) + 3^(3+1)+2
这就是现在这个数以3为底的这种展开。

现在把这个式子的右边中的所有3都改写成4,那就成了
4^4^(4+1) + 4^(4+1)+2
再减去一个小小的1,就成了
4^4^(4+1) + 4^(4+1)+1
这就是现在这个数以4为底的这种展开。

现在把这个式子的右边中的所有4都改写成5,那就成了
5^5^(5+1) + 5^(5+1)+1
再减去一个小小的1,就成了
5^5^(5+1) + 5^(5+1)
这就是现在这个数以5为底的这种展开。

现在把这个式子的右边中的所有5都改写成6,那就成了
6^6^(6+1) + 6^(6+1)
再减去一个小小的1,就成了
6^6^(6+1) + 6^(6+1) – 1
这可不是现在这个数以6为底的这种展开,因为有一个-1。所以展开来,它就是:
6^6^(6+1) + 5*6^6 + 5*6^5 + 5*6^4 + 5*6^3 + 5*6^2 + 5*6 + 5
这就是现在这个数以6为底的这种展开。

现在把这个式子的右边中的所有6都改写成7,那就成了
7^7^(7+1) + 5*7^7 + 5*7^5 + 5*7^4 + 5*7^3 + 5*7^2 + 5*7 + 5
减去一个小小的1,就成了
7^7^(7+1) + 5*7^7 + 5*7^5 + 5*7^4 + 5*7^3 + 5*7^2 + 5*7 + 4
这就是现在这个数以7为底的这种展开。

……

这么我们可以一直继续下去,数字似乎变得越来越大,增大的速度也越来越快,比方上面以7为底的那个数字要比7^7^8大,而7^7^8如果要用十进制写出来,需要用四百八十多万位数字,要印成了书都成煌煌巨著了。因为底数增加1,原来的数字就会增加很多,减去一个小小的1根本是九牛拔一毛无所谓。

但是,但是,Goodstein定理说,对任意的自然数n,当然266也包括在内,如果我们一直重复这个过程,我们最后总会到达0!

让我们来验证一下:对于n=0,1,2,3,都没什么好说的,很快掉到0。
n=4,第一排数字是步数,也就是现在是以几为底的表示了,第三排是那个式子,第二排是式子用十进制表示出来的值。

2  4    2^2
3  26  2*3^2 + 2*3 + 2
4  41   2*4^2 + 2*4 + 1
5  60   2*5^2 + 2*5
6  83   2*6^2 + 6 + 5
7  109   2*7^2 + 7 + 4
8  139   2*8^2 + 8 + 3
9  173   2*9^2 + 9 + 2
10  211  2*10^2 + 10 + 1
11  253  2*11^2 + 11
12  299  2*12^2 + 11
13  348  2*13^2 + 10
:   :    :
23  1058  2^23^2
24  1151  24^2 + 23*24 + 23
25  1222  25^2 + 23*25 + 22
:   :    :
47  3290  47^2 + 23*47
48  3407  48^2 + 22*48 + 47
:   :    :
95  11115  95^2 + 22*95
96  11327  96^2 + 21*96 + 95
:   :    :

注意到从第三步开始有个大项2*3^2,这个项中只有“3”这个地方以后会大起来,其他的一直保持不变,直到第24步的时候,这个项没有了,大项换成了 24^2,然后这一项里也就“24”这地方会变。然后这样下去大约要4亿多步以后,跟在这个平方项后面的那些杂碎都完蛋了,它成了孤家寡人,然后减一个小小的一,这个平方项就不见了。然后再这么下去,大约要再过10^121步,它才变成了0。

通过验证4,我们可以看见一个图景。就象我们看着倒记时的数字式电子跑表的时候,秒位上的数字滴答得很快,一秒秒减下来,等到0秒,再过1秒的时候,分位上的数字减1,可是秒位上的又变成59了,然后又是60秒后,分位上的数字也成0了,再过1秒,小时位上数字减1,分位和秒位上都又成99了。不过慢是慢,迟早会通通变0的。仔细观察刚才关于4的序列,我们发现Goodstein定理的序列中,也有一个类似的钟,只是它的每“分钟”,都要值许多许多“秒钟”,每“小时”要值许多许多“秒钟”,以至于我们感到这个钟不走了,甚至不是倒记时,而是向前走的!

“它的每‘分钟’,都要值许多许多‘秒钟’,每‘小时’要值许多许多‘分钟’”

不仅如此,它的每‘分钟’要值多少‘秒钟’不是固定的,越晚走掉的每一“分钟”,值的“秒钟”,要比前面的“分钟”要多得多,就好比在那个电子秒表里,第一次秒数走到0再过1秒时,分数减1,秒数变59,而第二次秒数走到0再过1秒时,分数减1,秒数却变成1000,第三次秒数走到0再过1秒时,分数减 1,秒数变成10000……(Goodstein序列中这个秒数增加的速度要比这个快得多)。同样,“小时”对“分钟”也是一样。而且还可以有“小时”以上的级别,象“天”“月”“年”。这样,如果你老是注意着“秒数”,就很容易觉得它越来越大,这倒数记时怎么也数不到0。

验证从5开始的序列……这个就算了吧。

Goodstein定理的叙述完全可以在皮亚诺公理系统中进行,它只牵涉到对数字的加减乘的运算,没有必要用到集合论,但是对于它的证明却用到了集合论。在1982年,两位数学家证明了,如果不用集合论,只在皮亚诺公理系统中,是不可能证明此定理的。

------------------------------------
31770- Goodstein定理的证明大纲
作者:bamboo
时间:2005-01-10 15:28

背景知识:

超穷序数
所有集合A都可加以良序,亦即(1)A的任意两个不同元素都可以比较大小及(2)A的任一子集S都有一个最小元素。如果集合A是有限的,良序化后便与某一自然数(在这里的意思包括0)相对应(包括元素大小的顺序)。个别自然数0,1,2,3,…构成有限序数。自然数整体(包括其顺序)是最小的无限序数,记之为ω={0,1,2,3,…}。在自然数之后还有其它无限序数(超穷序数),例如ω+1={0,1,2,3,…,ω}及ω+2={0,1,2,3,…,ω,ω+1}。如果集合A是无限的,良序化后便与某一超穷序数相对应。当然同一个集合A可以有不同的良序,如果A是无限的,那么不同的良序化后便可能相对应不同的序数。

超穷序数的生成
0,1,2,3,…,ω,ω+1,ω+2,…,ω+ω=ω2,ω2+1,ω2+2,…,ω3,…,ω.ω=ω^2,…,ω^2+ω,…,ω^3,…,ω^ω,…, ω^(ω+1),…,ω^(ω^2),…,ω^(ω^2)+ω^2+ω,…,ω^(ω^2+ω),…,ω^(ω^3),…,ω^(ω^ω)=ω^^3,…, ω^(ω^(ω^ω))=ω^^4,…,ω^^ω=ε0,以及更大的超穷序数。由序数构成的集合按序数大小排列已经是良序化了。

超穷归纳法
我们熟悉的数学归纳法可以用集合论的语言表述为:设S是自然数集合Z的一个子集,如果(1)0是S的元素,及(2)从k是S的元素可推出k+1是S的元素,那么(3)S=Z。数学归纳法是Peano算术系统的公理之一。
对于良序化的集合也有类似的性质:设A是良序化的集合,S是A的一个子集,如果(1)A的最小元素是S的元素,及(2)x是A的元素而从所有在A中比x小的元素是S的元素可推出x也是S的元素,那么(3)S=A。这便是良序集合的超穷归纳法。
易证数学归纳法是超穷归纳法的特殊形式,但从数学归纳法不能推出超穷归纳法,因为数学归纳法不能跨越从有限到无限的鸿沟。

Peano算术系统的协调性(Consistency)
Godel证明了不能仅由Peano算术系统的公理出发证明其本身的协调性。但Gentzen证明了藉助超穷归纳法(只需假设直到ε0成立,不需对更大的序数作任何假设),可以证明Peano算术系统的协调性。

由序数构成的严格递减序列
因为由序数构成的集合按序数大小排列已经是良序化了,可以运用超穷归纳法
证明,由序数构成的严格递减序列的长度是有限的。(比对:由有理数构成的严格递减序列的长度可以是无限的,但由自然数构成的严格递减序列的长度必然是有限的。)

Goodstein定理的集合论证明大纲:

在Goodstein序列中把所有进制底数(即第一个Goodstein数中的2,第二个Goodstein数中的3,等等)换成ω,把底数以外的数字保留而加以合适的解释(要注意运算的顺序,3ω跟ω3是不同的,前者其实等于ω,后者等于ω+ω+ω),例如以5为底,2*5^(3*5)+4*5+1便换成(ω^(ω3))2+ω4+1=ω^(ω+ω+ω)+ω^(ω+ω+ω)+ω+ω+ω+ω+1。整个Goodstein序列便换成另一条由序数构成的严格递减序列。因为这种序列的长度是有限的,所以原先的Goodstein序列的长度也是有限的,便推出任一正整数在Goodstein变换下终于会达到0的结论。

Goodstein定理不能由Peano算术系统公理推出的证明思路:

简而言之,就是若从Goodstein定理即「所有Goodstein序列都收敛于0」出发,可以推论出超穷归纳法直到ε0成立。若Goodstein定理能够由Peano算术系统公理推出,根据Gentzen的工作结果,即可证明Peano算术系统本身的协调性,但这与Godel的工作结果相矛盾。因此 Goodstein定理不能由Peano算术系统公理推出。

------------------------------------
但是我有一个疑问,换底之后,递减的过程中出现的“-1”是如何消除的?因为并没有“ω-1”这种东西啊?

------------------------------------
31838- 项数是固定的
作者:bamboo
时间:2005-01-11 09:31

令G为原Goodstein自然数序列,F为进制底数换成ω后的序数序列。要知道F(k+1)不是由F(k)-1而来,而是由G(k+1)换底而来,因此不会产生ω-1的问题。

以266为例:
G(1) = 266 = 2^2^(2+1) + 2^(2+1)+2
F(1) = ω^ω^(ω+1) + ω^(ω+1)+ω
G(2) = 3^3^(3+1) + 3^(3+1)+2
F(2) = ω^ω^(ω+1) + ω^(ω+1)+2
G(3) = 4^4^(4+1) + 4^(4+1)+1
F(3) = ω^ω^(ω+1) + ω^(ω+1)+1
G(4) = 5^5^(5+1) + 5^(5+1)
F(4) = ω^ω^(ω+1) + ω^(ω+1)
G(5) = 6^6^(6+1) + 5*6^6 + 5*6^5 + 5*6^4 + 5*6^3 + 5*6^2 + 5*6 + 5
F(5) = ω^ω^(ω+1) + (ω^ω)5 + (ω^5)5 + (ω^4)5 + (ω^3)5 + (ω^2)5 + ω5 + 5
G(6) = 7^7^(7+1) + 5*7^7 + 5*7^5 + 5*7^4 + 5*7^3 + 5*7^2 + 5*7 + 4
F(6) = ω^ω^(ω+1) + (ω^ω)5 + (ω^5)5 + (ω^4)5 + (ω^3)5 + (ω^2)5 + ω5 + 4

原G序列收敛到0的项数是固定的,F序列跟G序列一样,也是固定的。