电脑科学的理论基础

电脑科学的理论基础内容摘要：

OR xVy NOT x’ NAND (XY)’ NOR (XVY)’ XOR X⊕ Y X Y X Y x X Y X Y X Y X Y W Z (X y)’ v z v (x z’ w) 卡諾圖 ( karnaugh maps) 成本考量得到最適合設計 是布林代數 venn diagram 與真假值混合 尋找 optimal desing 的步驟如下 : +號放入卡諾圖中 : (1)畫出 8個方塊有涵蓋有 +號的地方 ,假如 8個方塊都有 +號 ,則 Boolean function為 1 (2)畫出 4個方塊有涵蓋 +號但之前沒有被涵蓋的地方 (3)畫出 2個方塊來涵蓋有 +號但之前沒有被涵蓋的地方 (4)畫出剩下有 +號但之前沒有被涵蓋的地方 : (1)整體上要包括所有含有 +號的地方 (2)越少方塊越好 literals越好 x Yz Xyz’ v x’ y’ x’ Yz’ Y’z’ Y’z + + + x Yz x x’ Yz’ Y’z’ Y’z + + + x Yz Z’ x’ Yz’ Y’z’ Y’z + + + x Yz x’ y’ v z x’ Yz’ Y’z’ Y’z + + + + + + + x Yz Y v xz’ v x’z x’ Yz’ Y’z’ Y’z + + x X v y v z’ x’ Yz’ Y’z’ Y’z + + + + + + + + + + + 第四章 認識數理邏輯 (predicate calculus) 也稱為數理演算，跟命題演算不太一樣。 邏輯程式設計與人工智慧，主要是以數理演算為基礎的。 數理邏輯 (predicate calculus)導入量詞(quantifiers)的使用。 量詞 (quantifiers) ：所有量詞 存在量詞 運算子 （ OPERATOR）： A E V ﹂ 多重量詞用法 同時使用 與 的情況，必須注意量詞出現順序 例 ： P(X， Y)=「 X是 Y的上司」 X P(X， Y) 意思是所有的人都是 Y的上司 Y P(X， Y) 意思是 X是所有的人的上司 Y P(X， Y) 意思是 X是某人所有的上司 X P(X， Y) 意思是某人是 Y的上司 A E A A E E 認識命題演算(propositional calculus) 命題演算使用的命題符號 (propositional symbols)是英文的大寫字母 命題符號用來表示命題 有關於現實世界的敘述，可能為真 (true)或偽(false)， 這些符號用來組成句子 (sentences)，合法的句子 (legal sentences)也稱為 WFFs (wellformed formulas)。 認識數理演算 (predicate calculus) 數理演算特點來自量詞 (quantifier)的導入 能處理述詞以及述詞中的成員，推理出其他的句子 可以從語法 (syntax)與語意 (semantics)上來認識數理演算 數理演算中的符號包括真值符號 (truth symbols)、常數符號 (constant symbols)、變數符號 (variable symbols)與函數符號(function symbols)， 數理演算很像一種邏輯程式語言 (logic programming language)。 邏輯程式設計 (logicprogramming) 邏輯程式設計 (logic programming) 的基礎就是數理邏輯 邏輯程式語言算是非程序式的程式語言 透過事實 (facts) 與推理規則 (inference rules) 的描述，電腦就可以回答一些問題，或是推理出其他的事實 邏輯程式設計 邏輯程式設計的思考跟一般程序式的程式語言很不一樣 因為邏輯程式設計不必描述推理的過程，只要把事實與規則列出來 語言本身有固定的推理機制，而程序式的程式語言 (procedural programming language) 則需要把詳細的步驟寫出來，越複雜的運算或邏輯，往往需要越複雜的描述 C++ 、 Java 與 Visual Basic 都算是程序式的程式語言 了解 PROLOG尋找與執行流程 兩種不同推演過程： 向前推演 （現有子句推演出目標） 向後推演 (從目標開始，詴著反解出現有的子句 ) Prolog 是後向推演 單一化作業是推演主要過程，包括型式比對與變數連結 單一化之後可以為目標比對到現有事實或規則的頭部，則代表成功 Pro log的直譯程式 必須確定所有可能路徑都有被搜尋過 搜尋事實與規則的順序是 由上而下 規則中好幾個子目標須證明 ，處理順序式由 左而右 子目標證明方式與目標證明方式一樣 第五章演算法的分析 函數值的成長率 函數 函數名。