- 相關推薦
邏輯推理中猜數(shù)問題的研究
作 者:張寧
【目的和思路】
研究典型的“思維嵌套”問題——猜數(shù)問題，從問題的本質(zhì)入手分析，避免了表面上的“思維嵌套”，使得解決問題的效率大幅度上升。
【制作過程】
首先對問題的原形產(chǎn)生了濃厚的興趣，經(jīng)過一系列深入的思考，將描述性的解決過程表達為嚴格的數(shù)學證明，同時也發(fā)現(xiàn)了問題可以繼續(xù)推廣，結(jié)合計算機來輔助研究，將問題兩次推廣，并最終較為圓滿地解決了問題。
【科學性】
采用了嚴格的數(shù)學方法，經(jīng)過詳細的討論得出了一系列結(jié)論。
【先進性】
采用初等數(shù)學的手段來研究一個規(guī)�；倪壿嬐评韱栴}，采用的證明方法也具有相當?shù)膭?chuàng)造性。
【實用性】
這類問題在數(shù)理邏輯和計算機科學中有較大的意義，這種解決邏輯推理問題的新思路，將會對這一類問題的解決產(chǎn)生影響。
【創(chuàng)新點】
摒棄了考慮邏輯推理問題的常規(guī)思路，從“思維嵌套”問題的本質(zhì)入手分析，并證明了數(shù)個重要結(jié)論，并且在證明過程中，采用了多元數(shù)組及分組等概念來描述推理過程中的情形，并采用記號將抽象的推理過程用數(shù)學加以證明，在理論上有一個飛躍。
在邏輯推理中有一類比較特殊的問題——“思維嵌套”問題，即在C的腦海中要考慮B是如何思考A的想法。這種問題通常非常抽象，考慮情況又十分繁多，思想過程極其復雜，用一般方法分析效果極差。
一、問題原形
一位邏輯學教授有三名善于推理且精于心算的學生A，B和C。有一天教授給他們?nèi)顺隽艘坏李}：教授在每個人的腦門上貼了一張紙條并告訴他們，每個人的紙條都寫了一個大于0的整數(shù)，且某兩個數(shù)的和等于第三個。于是，每個學生都能看見貼在另外兩個同學頭上的整數(shù)，但卻看不見自己的數(shù)。
教授輪流向A，B和C發(fā)問：是否能夠猜出自己頭上的數(shù)。經(jīng)過若干次的提問之后，當教授再次詢問某人時，他突然露出了得意的笑容，把貼在自己頭上的那個數(shù)準確無誤地報了出來。
我們的問題就是：證明是否有人能夠猜出自己頭上的數(shù)，若有人能夠猜出，則計算最早在第幾次提問時有人先猜出頭上的數(shù)。
我們先分析一個簡單的例子，觀察每個人是如何進行推理的。
假設A，B和C三人，頭上的數(shù)分別是l，2和3。
l. 先問A
這時，A能看見B，C兩人頭上的數(shù)分別是2，3。A會發(fā)現(xiàn)自己頭上只可能為3+2=5，或者3-2=1�？傻降资莑還是5，A無法判斷，所以只能回答“不能”。
2.再問B
B會發(fā)現(xiàn)自己頭上只可能為3+1=4，或者3-1=2。可到底是2還是4，B只能從A的回答中入手分析：(以下為B腦中的分析)
如果自己頭上是2。則A能看見B，C兩人頭上的數(shù)分別是2，3，A會發(fā)現(xiàn)自己頭上只可能為3+2=5，或者3- 2=1。到底是l還是5，A無法判斷，只能回答“不能”。這與A實際的回答相同，并不矛盾，所以B無法排除這種情況。
如果自己頭上是4。則A能看見B，C兩人頭上的數(shù)分別是4，3，A會發(fā)現(xiàn)自己頭上只可能為4+3=7，或者4-3=１。到底是l還是7，A無法判斷，只能回答“不能”。這也與A實際的回答相同，并不矛盾，所以B也無法排除這種情況。
B無法判斷，只能回答“不能”。
3．再問C
C會發(fā)現(xiàn)自己頭上只可能為2+1=3，或者2-1=l�？傻降资莑還是3．C只能從A或B的回答中入手分析：(以下為C腦中的分析)
如果自己頭上是1。
A會發(fā)現(xiàn)自己頭上只可能為2+l=3，或者2-1=1�？傻降资莑還是3，是無法判斷的，只能回答“不能”。這與A實際的回答相同，并不矛盾。
B會發(fā)現(xiàn)自己頭上只可能為1+1=2(因為B頭上是大于0的整數(shù)，所以B頭上不能是1-l=0)。B應回答“能”。但這與B實際的回答矛盾。C能以此排除頭上是1這種情況。
繼續(xù)分析C頭上是3這種情況，會發(fā)現(xiàn)毫無矛盾(與實際情況相符)。
C將準確判斷頭上的數(shù)是3，所以回答“能”。所以在第三次提問時有人猜出頭上的數(shù)。
我們從每個人的角度出發(fā)，分析了頭上數(shù)是l，2和3的情況。這種方法也是我們解決簡單的邏輯推理問題所采用的普遍做法。但如果將問題的規(guī)模變大，會發(fā)現(xiàn)問題的復雜程度會急劇上升，幾乎是多一次推理，問題的復雜度就要變大一倍。
靠如此煩瑣的推理是不能很好解決問題的。原因在于有大量的“思維嵌套”。即：在C的腦海中要考慮B是如何思考A的想法。此外，這種方法不能夠推導出有普遍意義的結(jié)論。讓我們換一種思路來解決問題。
下面我們用第一位、第二位、第三位學生分別表示A，B，C三人。
經(jīng)推論，無論三個數(shù)如何變化，無論從誰開始提問，必然是頭上數(shù)最大的人最先猜出自己頭上的數(shù)。
由上述結(jié)論，對于，(a1,a2,a3,k)可以定義f(a1,a2,a3,k)的遞推式：
當k=1時
當a2=a3時，f(a1,a2,a3,1)=1
當a2＞a3時，f(a1,a2,a3,1)=f(a2-a3,a2,a3,2)+2
當a2＜a3時，f(a1,a2,a3,1)=f(a3-a2,a2,a3,3)+1
當k=2時
當a1=a3時，f(a1,a2,a3,2)=2
當a2＞a3時，f(a1,a2,a3,2)=f(a1,a1-a3,a3,1)+1
當a2＜a3時，f(a1,a2,a3,2)=f(a1,a3-a1,a3,3)+2
當k=3時
當a1=a2時，f(a1，a2，a3，3)=3
當a1＞a2時，f(al，a2，a3，3)=f(a1，a2，a1-a2,1)+2
當al＜a2時，f(a1，a2，a3，3)=f(a1，a2，a2-a1,2)+1
由于我們只考慮(a1，a2，a3，k)∈= S3，因此k可由a1,a2,a3三個數(shù)直接確定，因此f(a1,a2,a3,k)可以簡化為f(a1,a2,a3)。
利用上面的公式，通過計算機編程來輔助解決問題。
由于建立了線性的遞推關系，因此避免了問題規(guī)模隨著提問次數(shù)呈指數(shù)型增長，有效地解決了問題，其解決方法是建立在對問題的深入分析之上的�，F(xiàn)在讓我們總結(jié)解決問題中思路的主線：
提煉重要的前提條件→考慮何種情形為“終結(jié)情形” →對非“終結(jié)情形"建立推理的等價關系→考慮何種情形能歸結(jié)到“終結(jié)情形”→分情況討論并加以證明→得出結(jié)論并改寫等價關系→得出公式。
整個過程是從分析問題的本質(zhì)入手，而非一味單純地從每個人思想出發(fā)，并推導出普遍意義的結(jié)論。從全局的角度分析問題，避免了最煩瑣的“思維嵌套"，并且使得問題規(guī)模從指數(shù)型轉(zhuǎn)變?yōu)榫�性。
二、第一種推廣
一位邏輯學教授有n(n≥3)名非常善于推理且精于心算的學生。有一天，教授給他們出了一道題：教授在每個人腦門上貼了一張紙條并告訴他們，每個人的紙條上都寫了一個大于0的整數(shù)，且某個數(shù)等于其余n-1個數(shù)的和。于是，每個學生都能看見貼在另外n-1個同學頭上的整數(shù)，但卻看不見自己的數(shù)。
教授輪流向?qū)W生發(fā)問：是否能夠猜出自己頭上的數(shù)。經(jīng)過若干次的提問之后，當教授再次詢問某人時，此人突然露出了得意的笑容，把貼在自己頭上的那個數(shù)準確無誤地報了出來。
我們的問題就是：證明是否有人能夠猜出自己頭上的數(shù)，若有人能夠猜出，則計算最早在第幾次提問時有人先猜出頭上的數(shù)，分析整個推理的過程，并總結(jié)出結(jié)論。
經(jīng)推論，無論n個數(shù)如何變化，無論從誰開始提問，必然是頭上數(shù)最大的人最先猜出自己頭上的數(shù)。
由上述結(jié)論，對于(a1,a2…,an,k)，可以定義f((a1,a2…,an,k)的遞推式：
當2W-M≤0時，f((a1,a2…,an,k)=k，
當2W-M>O時
設ai’=ai，其中，i≠k，ak’=2W-M
當v＜k時，f(a1,a2…,an,k)=f(a1’,a2’…,an’,v)+k-v
當v＞k時，f(a1,a2…,an,k)=f(a1’,a2’…,an’,v)+n-k+v
由于我們只考慮(a1,a2…,an,k)∈=S3，因此k可由n個數(shù)直接確定，因此f(a1,a2…,an,k)可以簡化為f(a1,a2…,an)。
利用上面的公式，通過計算機編程來輔助解決問題。
至此，第一種推廣情形就解決了�？梢园l(fā)現(xiàn)n=3時情形的證明，對解決一般情形提供了很好的對比，使得我們能夠較為輕松地解決問題，這其實也是建立在對n=3時的情形的分析之上的。
三、第二種推廣
一位邏輯學教授有n(n≥3)名非常善于推理且精于心算的學生。有一天，教授給他們出了一道題：教授在每個人腦門上貼了一張紙條并告訴他們，每個人的紙條上都寫了一個大于0的整數(shù)，并將他們分成了兩組(一組學生有m人，(m≥n／2)，且學生并不知道如何分組)，且兩組學生頭上數(shù)的和相等。于是，每個學生都能看見貼在另外n一1個同學頭上的整數(shù)，但卻看不見自己的數(shù)。
教授輪流向?qū)W生發(fā)問：是否能夠猜出自己頭上的數(shù)。經(jīng)過若干次的提問之后，當教授再次詢問某人時，此人突然露出了得意的笑容，把貼在自己頭上的那個數(shù)準確無誤地報了出來。
我們的問題就是：證明是否有人能夠猜出自己頭上的數(shù)，若有人能夠猜出，則計算最早在第幾次提問時有人先猜出頭上的數(shù)。
由于當n=3時，m只可能為2，即為問題原形，而對于m=n-1，即第一種推廣情形。因此只討論n＞3，m＜n-1時的情形。
對于每個人判斷自己頭上的數(shù)，依據(jù)分組情況不同，頭上的數(shù)就可能不同。
對(A1，A2，…,An，k)，第k位學生可以看見除自己外所有學生頭上的數(shù)，并假設在某種分組情況下，可以計算出與自己不同組的學生頭上數(shù)的和，由題目條件“兩組學生頭上數(shù)的和相等”，可以計算出自己頭上的數(shù)。由于有Cmn種分組情況，因此相對應頭上的數(shù)有Cmn種(其中可能也包括了一部分重復的數(shù)及非正整數(shù))。
經(jīng)推論，不存在情況使邏輯推理中猜數(shù)問題的研究得沒有人能夠猜出頭上的可能，且推理時四個數(shù)始終在減小，因此經(jīng)過有限次推理之后，必然達到“終結(jié)情形”。
而對于第一種推廣情形，即n=4，m=3，必然有人能猜出自己頭上的數(shù)。因此n=4時的一切情況，必然有人能猜出自己頭上的數(shù)。
由于現(xiàn)在的推理在加強判定的情況下，依然可能出現(xiàn)多種考慮情況。所以推理已不是線性的推理，整個推理過程將成為樹狀結(jié)構。
由于分組情況繁多，而且判定方式也比較復雜，因此這時計算f(A1，A2，…，An，k)的值已經(jīng)非人力能夠解決，但是可以利用上述證明的結(jié)論，依靠計算機強大的計算功能輔助解決問題。
【邏輯推理中猜數(shù)問題的研究】相關文章：
猜數(shù)游戲教學反思04-11
隱喻研究中的若干問題與研究課題05-02
組織錯誤研究中存在問題的思考04-25
關于AHP中逆判問題的研究04-28
現(xiàn)代物流中車輛路徑問題的研究05-03
生態(tài)哲學研究中的若干問題評析04-29
意象圖示研究中的問題及最新成就綜述04-26