《離散數(shù)學(xué)及其應(yīng)用》的一道邏輯題

Quasimodo_lory

不知道這樣的帖子該不該發(fā)到這里來(lái)，但是我自己自學(xué)實(shí)在找不人來(lái)幫我解答。
還望各位不吝賜教，謝謝了！
題目：
在一個(gè)100條語(yǔ)句的列表中，第n條語(yǔ)句是“在這個(gè)列表中，恰有n個(gè)語(yǔ)句為假”
a）從這些語(yǔ)句中你可以得出什么結(jié)論？
b）若第n條語(yǔ)句是“在這個(gè)列表中，至少有n個(gè)語(yǔ)句為假”，回答問(wèn)題a
c）假設(shè)這個(gè)列表包含99條語(yǔ)句，回答問(wèn)題b

問(wèn)題a我很快知道答案了，問(wèn)題b看了答案也想不明白。

kangtian

我怎么覺(jué)得這有點(diǎn)“子非魚(yú)，安知魚(yú)之樂(lè)也”思辨味道。

[ 本帖最后由 kangtian 于 2009-10-14 09:46 編輯 ]

Quasimodo_lory

沒(méi)人會(huì)嗎？
自己頂一下吧～

naihe2010

首先得從這個(gè)第N條語(yǔ)句為真或假進(jìn)行分析吧？

kangtian

另外我覺(jué)得這個(gè)題目的表述不嚴(yán)謹(jǐn)，語(yǔ)句應(yīng)該改為命題。真命題，假命題。
還有，題面是完整的嗎？還是大致意思？

epegasus

編程序驗(yàn)證啊.

b,推理也很簡(jiǎn)單啊,如果至少有n個(gè)語(yǔ)句為假,則對(duì)于m<n來(lái)說(shuō),"至少有m個(gè)語(yǔ)句為假"是真的.
也就是當(dāng)?shù)趎句對(duì)的,那么他前面的都是對(duì)的.而他后面的都是錯(cuò)的.這樣一共n句是對(duì)的.
一共n句是對(duì)的 和 至少n句為假, 怎么樣才不矛盾呢?
只有n<=50

c,根據(jù)上面的n < 50

kouu

a)
"恰有n個(gè)語(yǔ)句為假"(n=1~100)這100句話是互斥的，所以，其中至多有一句是真（即有0句或1句是真）。
第一種情況，有1句是真，則有99句是假。正好，第99句說(shuō)"恰有99個(gè)語(yǔ)句為假"。所以，第99句是真，其余是假；
第二種情況，有0句是真，則有100句是假。但是，第100句說(shuō)"恰有100個(gè)語(yǔ)句為假"，這句話是真，矛盾了。所以不存在這種情況。
所以，第99句是真，其余是假。


b)
如果"至少有n個(gè)語(yǔ)句為假"這句話是真的，則"至少有n-1個(gè)語(yǔ)句為假"、"至少有n-2個(gè)語(yǔ)句為假"、...、"至少有1個(gè)語(yǔ)句為假"這些都是真的。
即從第1句到第n句都是真的。
且第n句到第100句都是假的（否則，如果第n+x句是真的，那么第n+1、n+2、...n+x都是真的了）。

現(xiàn)在假設(shè)第n句是真，那么第1~n句是真的，第N+1~100句是假的，真的語(yǔ)句數(shù)目為n，假的語(yǔ)句數(shù)目為100-n。
第n句說(shuō)"至少有n個(gè)語(yǔ)句為假"，這是真的，則100-n>=n；
第n+1句說(shuō)"至少有n個(gè)語(yǔ)句為假"，這是假的，則100-(n+1)<n；
于是99-n < n <= 100-n，99<2n<=100，n=50。
所以，前50句是真的，后50句是假的。


c)
同b，假設(shè)第n句是真，那么第1~n句是真的，第N+1~99句是假的，真的語(yǔ)句數(shù)目為n，假的語(yǔ)句數(shù)目為99-n。
有99-n>=n，99-(n+1)<n，
于是98-n < n <= 99-n，98<2n<=99，n無(wú)解(49 < n <= 49.5)。
所以，前49句是真的，后49句是假的。
第50句無(wú)解： 如果為真，則"至少有50個(gè)語(yǔ)句為假"，實(shí)際上只有后面的49句為假，矛盾；如果為假，則"至少?zèng)]有50個(gè)語(yǔ)句為假"，實(shí)際上只有前面的49句不為假，矛盾。

Quasimodo_lory

太謝謝各位了！我明白了！
尤其要感謝epegasus 和kouu
謝謝！

epegasus

這事還沒(méi)完呢...

我昨天看了kouu 的回復(fù),想了很久..

首先要指出kouu 的幾個(gè)錯(cuò)誤.
在b的證明中,
>>第n+1句說(shuō)"至少有n個(gè)語(yǔ)句為假"，這是假的，則100-(n+1)<n；
這句話是明顯錯(cuò)誤.應(yīng)該是
第n+1句說(shuō)"至少有n+1個(gè)語(yǔ)句為假"，這是假的，則100-(n+1)<n+1；[1]

在C中同時(shí)也也存在類似錯(cuò)誤.
當(dāng)然kouu 分析方法很好.

不過(guò)
我在仔細(xì)查看我自己的錯(cuò)誤后發(fā)現(xiàn)了些東西.
我的證明沒(méi)給出確定的n,為什么呢?
相比kouu 的證明,我漏掉了上面那段紅色標(biāo)記的話.
但是我查看了我的證明,如同kouu 的證明,我通過(guò)假設(shè)第n句是對(duì)的,推論出 大于n的都是錯(cuò)的.kouu 也這樣做了推論.
如此我就在第n 句對(duì)的中已經(jīng)包含了第n+1句是錯(cuò)的這個(gè)事實(shí),
那為什么我還有必要在得出100-(n+1)<n+1這個(gè)結(jié)論呢?
這明顯是可疑的.

我發(fā)現(xiàn)錯(cuò)誤在于:原先的假設(shè)第n句是對(duì)的,推論出 大于n的都是錯(cuò)的.[2]

因?yàn)榛�于以下可以說(shuō)明它是自相矛盾的.
假設(shè)第n句是對(duì)的,那么小于n都是對(duì)的,這是肯定的.
但如果這時(shí)大于n都是錯(cuò)的:
那么n-1是對(duì)的可以得出n是錯(cuò)的
這和假設(shè)相矛盾.

所以[2]不成立.
為什么會(huì)得出[2]這個(gè)錯(cuò)誤結(jié)論呢?
我想是因?yàn)槿嗽谧鲞壿嬐评磉@種機(jī)械思維時(shí)容易犯糊涂.
我們只能得出:當(dāng)n是錯(cuò)誤的時(shí)候,大于n都為錯(cuò).

還沒(méi)完....

我們假設(shè)b中所有語(yǔ)句都是非對(duì)即錯(cuò),那么我們能確定的得出n=50.
我們同樣引到C中來(lái)證明,通過(guò)修正kouu的C的證明,我們能確定得出n=49,而不是kouu的無(wú)解.
由于我們?cè)�先假設(shè)c中的語(yǔ)句非對(duì)即錯(cuò),那么我們就能得出50句是假的,但c給出了50句無(wú)法判斷到出人意料.

哪里錯(cuò)了?
對(duì)于C中50句的判斷,那不就是一個(gè)悖論呢?

我又想起了說(shuō)謊者悖論來(lái).
其本質(zhì)是做了自指的判斷.而再在a,b,c中所有的句子,他們不正是3套隱含自指的命題么?
也就是這里面可能隱含悖論!
我們?cè)�先的假設(shè)并沒(méi)引入悖論.
那什么是悖論?我功力不夠,只能聯(lián)想到數(shù)字邏輯里面的RS觸發(fā)器的不穩(wěn)定態(tài),RS觸發(fā)器就是時(shí)序邏輯電路,輸出的狀態(tài)又返回為輸入.
這個(gè)不正是我們上面的命題的形式嗎?

就拿b來(lái)說(shuō),每個(gè)命題的真假就是一個(gè)一位的邏輯變量,而每條語(yǔ)句就是把這些邏輯變量作為輸入的一個(gè)邏輯函數(shù),也就是等價(jià)為一個(gè)組合邏輯電路,而這個(gè)邏輯函數(shù)的輸出就是一個(gè)命題的值.
那么就等價(jià)于n個(gè)輸入,n個(gè)輸出的組合邏輯,或者組合電路,但這里還要求n輸入 衡等于n輸出.
問(wèn)題本身等價(jià)于:對(duì)于上述給的情況,求n個(gè)輸出的,確定邏輯值.

首先問(wèn)題是存在這樣一組邏輯值嗎?
通過(guò)b和c的例子我們知道可能存在,可能不存在,并且有進(jìn)一步問(wèn)題,如:
是否存在一個(gè)或多個(gè)穩(wěn)定值(不存在悖論),如果存在不穩(wěn)定(悖論),那么是否存在多種情況.
說(shuō)謊者悖論,命題只有1個(gè),所以只有2個(gè)態(tài)的悖論:0->1->0->1........
對(duì)于多命題是否存在多種;比如A->B->C->A......

[ 本帖最后由 epegasus 于 2009-10-15 10:22 編輯 ]

kouu

原帖由 epegasus 于 2009-10-15 10:18 發(fā)表
第n+1句說(shuō)"至少有n+1個(gè)語(yǔ)句為假"，這是假的，則100-(n+1)<n+1；[1]
我發(fā)現(xiàn)錯(cuò)誤在于:原先的假設(shè)第n句是對(duì)的,推論出 大于n的都是錯(cuò)的.[2]

多謝指正~
第一個(gè)問(wèn)題的確是個(gè)錯(cuò)誤；
第二個(gè)問(wèn)題確實(shí)也是錯(cuò)了，其實(shí)我的本意是假設(shè)n是最后一句為真的。呵呵，表述不當(dāng)。

其實(shí)我很想知道LZ看到的標(biāo)準(zhǔn)答案是什么