Computer Science - 布林邏輯
on 2013-08-27
布林邏輯
思維規律的研究(an investigation of the laws of thought)-布耳(George Boole)
布林代數(Boolean algebra)
布林代數很像高中所學的的代數,不同的是方程式中的變數所代表的是邏輯敘述而不是數字.
布林的變數象徵對或錯,
透過 MIT工學院學生夏濃(Claude Shannon)的碩士論文,布林的研究結果得以跨入計算機科學領域,夏濃因發明了資訊理論而負盛名,這個理論定義了資訊的計算單位,位元.
夏濃希望建造一部可以下棋的機器,可以模仿人類思考的機器.1940年他發表了碩士論文,替續開關電路的符號分析(a symbolic analysis of relay switching circuits).
他在論文中說明,建立與布林代數運算式相同意義的電路是可行的.夏濃的電路中,開關的On和Off對應布林代數中邏輯變數的對和錯.
Computer Science - 有限狀態機
on 2013-08-27
有限狀態機
它可以執行隨時間而改變的函數,也就是不但與目前的輸入值有關,也受之前輸入值影響的函數.
有限狀態機的基本構想是將一個對照表與記憶元件加以結合,而這個對照表則是以布林邏輯建構的,記憶元件儲存過去的概要,本身就是有限狀態機的[狀態].
密碼鎖就是簡單的例子,它的狀態就是記住一連串數字輸入鎖中的結果.鎖並不記得撥過的所有數字,但它可以記住最後輸入的幾組數 字,而這幾組數字就足以在數字序列正確的時候把鎖打開.
自動筆是一個更簡單的例子,它有兩種可能的狀態,伸出筆芯和縮回筆芯,而且還記得它的按鈕被按了奇數次還是偶數次. 所有有限狀態機都有一組固定的可能狀態、一組可以改變狀態的輸入(按原子筆的按鈕or撥動鎖上的數字盤)以及一組可能的輸出(筆 芯的縮回或伸出or開鎖).輸出只由狀態決定,而狀態則取決於輸入的順序.
為了儲存有限狀態機的狀態,需再介紹最後一個建構區域,也就是可以儲存位元的暫存器.n位元的暫存器有n個輸入及輸出端外,另加一個輸入端以告知暫存器何時該改變狀態.將新資訊存入暫存器的動作叫寫入(writing),當定時輸入端告知暫存器要寫入新狀態時,暫存器的狀態便會改變使與輸入訊號相符.至於暫存器的輸出,則總是顯示目前的狀態.
暫存器的裝置有很多種,其中之一是以布林邏輯區組將狀態訊息推入一個圓圈循環中,這種暫存器是電腦中最常用的一種,所以當電源突然中斷時,電腦便不會繼續當時所做的工作.
有限狀態機包含了一個布林邏輯區組及一個暫存器,有限狀態機將布林邏輯區組的輸出寫入暫存器中,然後邏輯區組會依新的輸入及當時的狀態計算出下一個狀態,並再下一個循環寫入暫存器中,如此週而復始的重複,有限狀態機因此不斷更新其狀態.
包括電腦在內的許多數位計算裝置也都已固定的時間間隔變換其狀態,而變換的頻率則稱為這部機器的時脈(clock rate),在電腦的世界裡,時間並不是連續的,而是一組固定的變換序列.電腦的時脈決定這些狀態變換的速度,因此也決定了實際時間與計算機時間的對應關係.
雖然有限狀態機的功能非常強大,但它卻無法辨識所有序列形式.例如,我們不可能建構一個用迴文開鎖的有限狀態機,所謂迴文就是由前往後唸和由後往前唸都一樣.因為迴文的長度不一定,且必須要記住迴文前半部中的每個字,才能辨識後半部,又由於前半部有無限多種可能,因此需要一部具有無限個狀態的機器才能處理.