【正文】 =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, 條件命題。（ 平行傳遞 ）。 證： 1 、自反性： 即任一條直線與自身平行（ 自身平行 ）； 2 、對稱性： 直線 a 平行于直線 b ，則直線 b 也平行于直線 a 。 不同類的任兩條直線不相互平行，即不等價。 幾何中的等價： 一個平面上的直線的平行關(guān)系，就是一種等價關(guān)系。 同一類的代數(shù)式相互 的 “等價性”是按“同類項”性質(zhì)劃分的。 如 5a ， 2 a b ， 6x ， 4a ， 7x ， 3ab 。 相等關(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} ? 每一類中的元素都是等量，即相互等價； 不同類的任兩個元素是不相等的，即相互不等價。 S= S1∪S 2∪ … ∪ Sn∪ … 2)、任何兩個不同的類沒有公共元素。數(shù)學(xué)中的 “ 同類項 ” 、 “ 相等 ” 、 “ 相似 ” 、“ 平行 ” 等關(guān)系都屬于等價關(guān)系。即集合 A 中的任一變元 “ 僅且僅能 ” 屬于一個等價類。 事實上，集合 A 中與 x 有等價關(guān)系 R 的 所有元素構(gòu)成的集合就是 x 的等價類R[ x ]。 ? 只有嚴格遵守形式邏輯的基本法則，充分保證邏輯的可靠性，才能保證結(jié)論的正確性。 ? 數(shù)學(xué)高度的抽象性和邏輯的嚴密性是緊密相關(guān)的。 ?數(shù)學(xué)的抽象性還表現(xiàn)為簡潔的形式化，即使用由字符組成的公式。 ?抽象，是任何一門科學(xué)乃至全部人類思維都具有的特性。 ?否則，計算機將不能處理該問題。該問題可以是一段文字描述 說明實現(xiàn)他的過程；也可以是一個數(shù)學(xué)的表達式或流圖。 了解這些內(nèi)容會提高對具體問題的抽象能力和對算法的深入理解。 ? 數(shù)學(xué)方法在任何一門學(xué)科中都有不同程度的應(yīng)用，而計算學(xué)科對數(shù)學(xué)方法的使用就更廣泛、更深入 。 在這方面，最有意義的就是公理化方法。 從計算學(xué)科研究形式化語言的目的在于實現(xiàn)機器計算，而實現(xiàn)機器計算的前提是由一種機器可以識別的“語言”。就是運用數(shù)學(xué)的形 式化語言，在觀測和實驗的基礎(chǔ)上建立起來的，它有助于人們認識和把握超出感性經(jīng)驗之外的客觀世界。 本章小結(jié) ?本章介紹的主要內(nèi)容 ?數(shù)學(xué)概念和術(shù)語、 證明方法作用 ?數(shù)學(xué)的基本特征： 抽象性、嚴密性、適用性 ?計算學(xué)科中常用的數(shù)學(xué)概念和術(shù)語 ?集合、函數(shù)、關(guān)系、等價關(guān)系與等價類、 ?必要條件、充分條件 ?證明方法 ：直接、間接、 反證法 （ 無理數(shù)）、歸納法 （數(shù)學(xué)） ?遞歸和迭代 : 遞歸的定義、算法 ?公理化方法： 理論體系、理論集合的“三元組” ? 公理化概念、公理系統(tǒng)的條件：相容、獨立、完備； ? 例：平面幾何的公理化概括、 本章作業(yè) ? 作業(yè)： 149頁 習題五： ? 2 2 28 □ 數(shù)學(xué)的形式化語言能抽象 而準確 地表達許多自然 界 客觀事物的科學(xué)規(guī) 律 （能寫出有確切含義的一個表達式） ， 如牛頓的萬有引力定律（122mmfGr?，f ma?，等差、等比級數(shù)公式 ）等 等。 原始概念：點、線、面 ； 原始命題（公設(shè)和公理）如下： 公設(shè) 1：兩點之間可作一條直線； 公設(shè) 2：一條有限直線可不斷延長； 公設(shè) 3：以任意中心和直徑可以畫圓； 公設(shè) 4：凡直角都彼此相等； 公設(shè) 5：在平面上，過給定直線之外的一點，存在且僅存在一條平行線，即所謂的 “ 平行公設(shè)（公理） ” 。 原始概念： 1； 原始命題（公理）：任何正整數(shù) n或者等于 1，或者可以從 1開始，重復(fù)地 “ 加 1”來得到它。 ?⑶、完備性： 即從公理系統(tǒng)出發(fā)，能推出該領(lǐng)域所有的命題。 572 公理化方法的基本概念 ?什么是公理化方法 是一種構(gòu)造理論體系的演繹方法，它是從盡可能少的基本概念、公理出發(fā)，運用演繹推理規(guī)則，推出一系列的命題（定理、推論等）從而建立整個理論體系的思想方法。 167。 公理化方法 本節(jié)介紹的公理化方面的有關(guān)內(nèi)容，包括理論體系的公理化構(gòu)建。即：使 |Sn Sn1| ε 滿足精度的要求，計算就結(jié)束 。 效率：遞歸比迭代耗費更多的時間和空間，具體實現(xiàn)時希望盡可能將遞歸程序轉(zhuǎn)化為等價的迭代程序。 ?遞歸與迭代雖然本質(zhì)相同，但實際還是有一些差別。 562 迭代 ?“迭”是屢次和反復(fù)的意思，“代”是替換的意思，合起來，“迭代”就是 反復(fù)替換 的意思。 ?⑸ 遞歸程序：指直接或間接調(diào)用自身的程序 ?⑹ 遞歸方法： n + 2 n + 1 nf f f???遞歸與數(shù)學(xué)歸納法的 關(guān)系 ?遞歸的定義功能 ： ⑴ 定義序列； ⑵ 定義函數(shù)； ⑶ 定義集合 ?阿克曼函數(shù)： 一個有趣而經(jīng)典的 遞歸函數(shù) 167。 斐波那契數(shù)列：0,1,1,2,3,5,8,13,21,34,… ， ,… ?⑶ 遞歸過程：指調(diào)用 “ 自身 ” 的過程。 561 遞歸 （數(shù)學(xué)概念） ?遞歸及其有關(guān)概念 ?⑴ 遞歸關(guān)系：指一個數(shù)列的若干連續(xù)項之間的關(guān)系。 作業(yè)題： 167。 167。 552 反證法 畢達哥拉斯學(xué)派 的無理； 是無理數(shù) 的證明 2 首先假定一個 與原命題相反的命題成立 ，然后通過正確的推理 得出與已知（或假設(shè)）條件、公理、已證過的定理等相互矛盾或自相矛盾的結(jié)果， 用來證明原命題的正確。因為對這個蘊含式后件的否定蘊含著前件為假，因此該蘊含式為真。則對某個整數(shù) k來說有 p=2k+1。 例 用間接證明法證明“若 p2是偶數(shù)，則 p是偶數(shù)”。因此， p2是偶數(shù)（它是一個整數(shù)的 2倍）。 證明：假定 p是偶數(shù)為真，設(shè) p=2k（ k為整數(shù)）。 55 證明方法 ?167。 例 x=2是 x2=4的充分條件。 這一命題中， 正方形是長方形的充分條件，長方形是正方形的必要條件。 這一命題中 ， “ 人 ” 是哺乳類的充分條件， “ 哺乳類 ” 是人的必要條件。 若兩個命題相互蘊涵，即 p?q，我們說， p和 q 互為充分必要條件（簡稱 充要條件 ）。 非等價關(guān)系： ? 關(guān)系 ? 朋友關(guān)系 ? 同學(xué)關(guān)系 ?等價關(guān)系與等價類 ?等價關(guān)系的重要性質(zhì)：集合 A上的一個等價關(guān)系 R 可將 A 劃分為若干個互不相交的子集，稱為 等價類 。 因此，以上并發(fā)關(guān)系不是等價關(guān)系。 問：以上反映的并發(fā)現(xiàn)象，如用關(guān)系來表示時，是否是等價關(guān)系？ 答：以上反映的是一種并發(fā)（ co）現(xiàn)象。 ②、對稱性證明 對集合中的任意元素 a,b， n∈ N， 若 a mod 3=b mod 3（或 ab=3n∈ 3N） , 則有 : b mod 3=a mod 3 （或 ba=3n∈3N ） ③、傳遞性證明 對集合中的任意元素 a,b,c,n,m∈N ， 若 a mod 3=b mod 3， b mod 3=c mod 3， 則有 a mod 3=c mod 3 或若 ab=3n， bc=3m， 則有： (ab)+(bc)=3n+3m =3(n+m)∈ 3N 。 例 N上的模 3的同余關(guān)系 R為等價關(guān)系。 ?傳遞性：（ 說明變元之間的關(guān)系是可以遞推的 ） 167。（ ） (1)R={ 1,1,1,2,1,3,2,1,2,2,2,3, 3,1,3,2,3,3 } (2)R ={ 1,3,2,2,2,3,3,3 } (3)R ={ 1,1,2,2,3,3 } (4)R ={ 1,22,3,3,1 } ? 等價關(guān)系 ?自反性 ：（ 即，對集合中的每一個元素 a都有 aRa ， ） ?（或： ） 。 R={ } R , , , , , , 錯誤 正確對稱性的定義 ?R為定義在 X上的二元關(guān)系，若對于每個 x?X，y?X，每當 xRy，都有 yRx，則稱關(guān)系 R是 對稱的。 ?練習 ： A={1,2,3},下列的 關(guān) 系 R中 哪 些在 A上是自反