【文章內(nèi)容簡介】 術(shù)語、 證明方法作用 ?數(shù)學(xué)的基本特征： 抽象性、嚴(yán)密性、適用性 ?計算學(xué)科中常用的數(shù)學(xué)概念和術(shù)語 ?集合、函數(shù)、關(guān)系、等價關(guān)系與等價類、 ?必要條件、充分條件 ?證明方法 ：直接、間接、 反證法 （ 無理數(shù)）、歸納法 （數(shù)學(xué)） ?遞歸和迭代 : 遞歸的定義、算法 ?公理化方法： 理論體系、理論集合的“三元組” ? 公理化概念、公理系統(tǒng)的條件：相容、獨立、完備； ? 例：平面幾何的公理化概括、 本章作業(yè) ? 作業(yè)： 149頁 習(xí)題五： ? 2 2 28 □ 數(shù)學(xué)的形式化語言能抽象 而準(zhǔn)確 地表達許多自然 界 客觀事物的科學(xué)規(guī) 律 （能寫出有確切含義的一個表達式） ， 如牛頓的萬有引力定律（122mmfGr?，f ma?，等差、等比級數(shù)公式 ）等 等。 □ 這些形式化的數(shù)學(xué)表述， 都是 用簡明的數(shù)學(xué)公式表示 的數(shù)學(xué)模型。就是運用數(shù)學(xué)的形 式化語言，在觀測和實驗的基礎(chǔ)上建立起來的，它有助于人們認識和把握超出感性經(jīng)驗之外的客觀世界。 □ 另外，簡明的 數(shù)學(xué)公式和符號化的表達式便于機器識別 。 從計算學(xué)科研究形式化語言的目的在于實現(xiàn)機器計算，而實現(xiàn)機器計算的前提是由一種機器可以識別的“語言”。 數(shù)學(xué)的邏輯嚴(yán)密性這一特點，使它成為建立一種理論體系的手段。 在這方面，最有意義的就是公理化方法。 數(shù)學(xué)邏輯用數(shù)學(xué)方法研究推理過程，把邏輯推理形式加以公理化、符號化，為建立和發(fā)展科學(xué)的理論體系提供了有效的工具。 ? 數(shù)學(xué)方法在任何一門學(xué)科中都有不同程度的應(yīng)用，而計算學(xué)科對數(shù)學(xué)方法的使用就更廣泛、更深入 。 ? 這一章我們將把計算學(xué)科所要用到的最基本的數(shù)學(xué)方法進行介紹，它們包括計算學(xué)科中常用的： ? 數(shù)學(xué)證明方法、 ? 遞歸和迭代、 ? 公理化方法、 ? 形式化方法等內(nèi)容。 了解這些內(nèi)容會提高對具體問題的抽象能力和對算法的深入理解。 ? 想用計算機處理的任何問題都必須首先變成（抽象成）一個數(shù)學(xué)的問題。該問題可以是一段文字描述 說明實現(xiàn)他的過程；也可以是一個數(shù)學(xué)的表達式或流圖。即必須給一個 “ 具體問題 ” 建立一個 “ 數(shù)學(xué)模型 ” 。 ?否則，計算機將不能處理該問題。因此，對問題的數(shù)學(xué)抽象 (建模 )的本領(lǐng)必須學(xué)會。 ?抽象，是任何一門科學(xué)乃至全部人類思維都具有的特性。 ?數(shù)學(xué)的抽象程度大大超過自然科學(xué)中一般的抽象，它最大的特點在于 拋開現(xiàn)實事物的物理、化學(xué)和生物學(xué)等特性，而僅保留其量的關(guān)系和空間的形式 。 ?數(shù)學(xué)的抽象性還表現(xiàn)為簡潔的形式化，即使用由字符組成的公式。 思考：請舉例說明數(shù)學(xué)的抽象性。 ? 數(shù)學(xué)高度的抽象性和邏輯的嚴(yán)密性是緊密相關(guān)的。 ? 若數(shù)學(xué)沒有邏輯的嚴(yán)密性，在自身理論中矛盾重重，漏洞百出，那么用數(shù)學(xué)方法對現(xiàn)實世界進行抽象就失去了意義。 ? 只有嚴(yán)格遵守形式邏輯的基本法則，充分保證邏輯的可靠性，才能保證結(jié)論的正確性。 等價類 的定義 ： 若 R 是集合 A 上的一個等價關(guān)系， 對任一確定的 xA ? ， 均可構(gòu)造一個 A 的子集R[ x ]， 稱為由 x 生成的（或由以 x 為代表）的 R 等價類。 事實上，集合 A 中與 x 有等價關(guān)系 R 的 所有元素構(gòu)成的集合就是 x 的等價類R[ x ]。 顯然， 等價關(guān)系的一個重要性質(zhì)是：集合 A 上的一個等價關(guān)系 R ， 可將 A 劃分為若干個互不相交的子集，稱為等價類。即集合 A 中的任一變元 “ 僅且僅能 ” 屬于一個等價類。 ?注意： “ 等價類 ” 聯(lián)系到 “ 分類 ” ，即等價類一定是按 “ 等價關(guān)系 ” 分類。數(shù)學(xué)中的 “ 同類項 ” 、 “ 相等 ” 、 “ 相似 ” 、“ 平行 ” 等關(guān)系都屬于等價關(guān)系。 由等價關(guān)系的三條性質(zhì) (自反性 ,對稱性 ,傳遞性 ),可以推出對一非空集的分類具有下面兩條性質(zhì) : 1)、集合中的任一元素屬于且僅屬于某一類 (沒有剩余 )，各類取并集等于該集合。 S= S1∪S 2∪ … ∪ Sn∪ … 2)、任何兩個不同的類沒有公共元素。 當(dāng) i≠j 時 , Si∩S j=Φ ； 而計算學(xué)科有關(guān)各種數(shù)據(jù)類型中的 “ 結(jié)構(gòu)數(shù)據(jù) ” ，如： int、float、 char、 struct等等各屬于一個等價類。 相等關(guān)系： { 1+ 3, 2+ 2, 0+ 4, 4+ 0, 3+ 1, 4} , { 1+ 5, 2+ 4, 3+ 3, 0+ 6, 4 + 2, 6+ 0, 5+ 1, 6} ? 每一類中的元素都是等量，即相互等價； 不同類的任兩個元素是不相等的，即相互不等價。 運算中體現(xiàn)為等價代換是： 6 2 3= ( 2+ 4) 2 3= 4 3= ( 1+ 3) 3= 1 合并同類項： 運算中的同類項合并， 屬于等價類的歸類。 如 5a ， 2 a b ， 6x ， 4a ， 7x ， 3ab 。按同類項分類， 可分為三類： { 5 a , 4 a } ， { 2 a b , 3 a b } ， { 6 x , 7 x } 。 同一類的代數(shù)式相互 的 “等價性”是按“同類項”性質(zhì)劃分的。 兩個元素的“等價”是指這兩個元素是“同類項”， 對它們可以進行合并，否則不能合并。 幾何中的等價： 一個平面上的直線的平行關(guān)系，就是一種等價關(guān)系。 按這種關(guān)系對該平面的所有直線分類， 那么每一類中任兩條直線相互平行，即相互等價。 不同類的任兩條直線不相互平行，即不等價。 直線的平行這種關(guān)系具有 的 等價關(guān)系？試證明。 證： 1 、自反性： 即任一條直線與自身平行（ 自身平行 ）； 2 、對稱性： 直線 a 平行于直線 b ，則直線 b 也平行于直線 a 。 （ 彼此平行 ）； 3 、傳遞性： 直線 a 平行于直線 b ，且直線 b 平行于直線 c ， 則直線 a 平行于直線 c 。（ 平行傳遞 ）。 最基本的布爾運算是： “非 ”（ NOT ，符號為“ ? ”）和 “與 ”（ AND ，符號為“∧”）運算， 其他的布爾運算，如： “或”（ OR ，符號為“∨”） “異或”（ XOR ，符號為“ ⊕ ”） “蘊含”（ Implication ，符號為 “→”）A B A B? ? ? ? “等值”（ Equivalence ，符號為“?”）A B ( A B ) ( A B )? ? ? ? ? ? ? 等運算均可以用最基本的“非”和“與 ”運算來表示。 布爾運算真值表 非運算： ? 0=1 ； ? 1=0 ； 與 ( 交 ) 運算： 0 ∧ 0=0 ； 0 ∧ 1=0 ； 1 ∧ 0=0 ； 1 ∧ 1=1 ； 或 ( 并 ) 運算： 0 ∨ 0=0 ； 0 ∨ 1=1 ； 1 ∨ 0 =1 ； 1 ∨ 1=1 ； 異或運算： 0 ⊕ 0=0 ； 0 ⊕ 1=1 ； 1 ⊕ 0=1 ； 1 ⊕ 1=0 ； 等值運算： 0 ? 0=1 ； 0 ? 1=0 ； 1 ? 0=0 ； 1 ? 1=1 ； 布爾運算真值表 蘊含運算： 0 → 0=1 ； 0 → 1=1 ； 1 → 0=0 ； 1 → 1=1 ； A B A B? ? ? ?p→q, 條件命題。 p為前提， q為結(jié)論 ,例 : 法令 :如果積雪達到或超過 2英寸則不允許汽車整晚停在街上 . P:在 2022年 12月 1日 ,積雪達到或超過 2英寸 q: 2022年 12月 1日 ,汽車不能整晚停在街上 . 違反法令的 (即 p→q 為假 )的情形 ,只有前提 p為真且結(jié)論為假 . 字母表 ∑ 的 定義： 有限個任意符號組成的非空集合 。 字母表中的元素稱 為該字母表的字母（符號、字符） 字母表的內(nèi)的字母不可拆分，如： {0 ,1 } ； {aa,bb, cc } 字母表可以理解為計算機輸入鍵盤上符號的集合 。 字符可以理解為鍵盤上的每一個 英文 字母、數(shù)字 字符 、標(biāo)點符號 、運算符號等。 字母表示構(gòu)成字符串和形成語言的基礎(chǔ)。 字符串（符號串） （組成語句的基礎(chǔ)） 由字母表的字符組成的有限序列 ，常用希臘（英文）字母表示。 字母表∑上的字符串以下列規(guī)則 生成 ： ⑴、 空串：不含任何字符的串；用字符ε表示。 ε為∑上 一個特殊串 ： 對任何 a ?? ， a ε = ε a =a ； ⑵、 若σ是∑上的符號串，且 a ?? ， 則σ a 是∑上的符號串。 ⑶、 若α是∑上的符號串， 當(dāng)且僅當(dāng)它由 ⑴ 和 ⑵ 導(dǎo)出 直觀來說，∑上的符號串 （ 句子 ） 是由其上的符號以任意次序拼接起來構(gòu)成的，任何符號都可以在串中重復(fù)出現(xiàn)。 語言：分 自然語言與形式化語言； “我是一個大學(xué)生” 語言 應(yīng) 包括：字符、 字符串、 語法、語義等。 形式化語言，即 “