【文章內(nèi)容簡(jiǎn)介】 形態(tài)的核心內(nèi)容。其中，定義是蘊(yùn)含在公理系統(tǒng)之中的概念和命題；定理是被證明為真的數(shù)學(xué)命題；證明是為使人們確信一個(gè)命題為真，而作的一種邏輯論證。 數(shù)學(xué)家們認(rèn)為，定義是數(shù)學(xué)的靈魂，定理和證明是數(shù)學(xué)的精髓。對(duì)一個(gè)問(wèn)題來(lái)說(shuō)，給出一個(gè)精確的定義是不容易的，以至有人認(rèn)為，若能像圖靈給出“計(jì)算”的形式化定義那樣給出“智能”的定義，那么，“智能”的本質(zhì)將被揭示，“智能”領(lǐng)域也將產(chǎn)生一個(gè)質(zhì)的飛躍。 例 定義是對(duì)一種事物的本質(zhì)特征或一個(gè)概念的內(nèi)涵與外延確切而簡(jiǎn)要的說(shuō)明。陳波在其著作 《 邏輯是什么？ 》 一書(shū)中，從定義的作用、規(guī)則等多方面對(duì)定義作了系統(tǒng)的論述。下面，簡(jiǎn)介之： （ 1）綜合作用：人們可以通過(guò)定義，對(duì)事物已有的認(rèn)識(shí)進(jìn)行總結(jié)，用文字的形式固定下來(lái)，并成為人們進(jìn)行新的認(rèn)識(shí)和實(shí)踐活動(dòng)的基礎(chǔ)； （ 2）分析作用：人們可以通過(guò)定義，分析某個(gè)語(yǔ)詞、概念、命題的使用是否適合，是否存在邏輯方面的錯(cuò)誤； （ 3）交流作用：人們可以通過(guò)定義，在理性的交談、對(duì)話、寫(xiě)作、閱讀中，對(duì)于所使用的語(yǔ)詞、概念、命題有一個(gè)共同的理解，從而避免因誤解、誤讀而產(chǎn)生的無(wú)謂爭(zhēng)論，提高成功交際的可能性。 （ 1）定義必須揭示被定義對(duì)象的區(qū)別性特征； （ 2）定義項(xiàng)和被定義項(xiàng)的外延必須相等； （ 3）定義不能惡性循環(huán)； （ 4）定義不可用含混、隱晦或比喻性詞語(yǔ)來(lái)表示。 下面，再給出幾個(gè)例子，以便加深對(duì)“定義這個(gè)概念的理解。 例 抽象 在常用詞典中，抽象一般有兩個(gè)解釋。一個(gè)是，從許多事物中，舍棄個(gè)別的、非本質(zhì)的屬性，抽出共同的、本質(zhì)的屬性，叫抽象；另一個(gè)是，不能具體的，籠統(tǒng)的，空洞的，叫抽象。 例 科學(xué) 科學(xué)是反映自然、社會(huì)、思維等的客觀規(guī)律的分科的知識(shí)體系。 該定義從三方面規(guī)定了“科學(xué)是什么”，首先，科學(xué)是一種知識(shí)，而知識(shí)的本義則是對(duì)實(shí)踐經(jīng)驗(yàn)的真實(shí)陳述；其次，科學(xué)不是單個(gè)真實(shí)陳述的雜亂堆積，而是有序的組織起來(lái)的一個(gè)體系；第三，該陳述體系中的每一個(gè)陳述均可直接或間接加以證明。 例 人 人是能制造工具并使用工具進(jìn)行勞動(dòng)的高等動(dòng)物。 該定義采用的是屬加種差的定義，該定義是一種常見(jiàn)的內(nèi)涵定義形式。該定義，確定了“人”屬于一種“動(dòng)物”；其次，確定了人與動(dòng)物種類的區(qū)別。 例 哺乳動(dòng)物 與“人”相似的定義還有，哺乳動(dòng)物是最高等的脊椎動(dòng)物，基本特點(diǎn)是靠母體的乳腺分泌乳汁哺育初生幼體的。除最低等的單孔類是卵生的以外，其他哺乳動(dòng)物全是胎生的。 必要條件和充分條件 必要條件（ necessary condition）和充分條件（ sufficient condition）不僅是數(shù)學(xué)的兩個(gè)基本概念，而且也是社會(huì)學(xué)中的兩個(gè)重要概念。然而，要真正的理解并掌握這兩個(gè)概念卻不是一件容易的事。下面，簡(jiǎn)介之。 一般地，若命題 p蘊(yùn)涵命題 q，即 p?q，則我們說(shuō)， p是 q的充分條件， q是 p的必要條件。若兩個(gè)命題相互蘊(yùn)涵，即 p?q，我們說(shuō)， p和 q互為充分必要條件（簡(jiǎn)稱充要條件）。 從集合論的角度出發(fā)，借助于文氏圖，有助于對(duì)什么是必要條件，什么是充分條件的判定。 若 p?q，則 p是 q的充分條件， q是 p的必要條件。 假設(shè) A={x|p}， B={x|q}，若 A?B，設(shè) x 為 A中的任一元素，即 x∈ A，則 x∈ B。因此，可以判定， A是 B的充分條件，即 p?q，如圖 (a)所示。 若 p?q, 則 p和 q互為充分必要條件，即 A=B, 如圖 (b)所示。 ABBA（ a） A、 B(b) 幾個(gè)例子： 例 人是哺乳類。這一命題中，“人”是哺乳類的充分條件，“哺乳類”是人的必要條件。 例 正方形就是長(zhǎng)方形。這一命題中，正方形是長(zhǎng)方形的充分條件， 圖 集合 A和 B相互關(guān)系的文氏圖 長(zhǎng)方形是正方形的必要條件。 例 x＞ 0是 x＞ 100的必要條件。 例 x=2是 x2=4的充分條件。 在現(xiàn)實(shí)生活中，必要條件和充分條件常被誤用。如找人才，本來(lái)是找必要條件，但人們往往會(huì)用充分條件來(lái)找。相反，要用充分條件時(shí)，卻錯(cuò)誤的采用必要條件。如草率地上馬一個(gè)涉及面廣的項(xiàng)目。 “必要條件”和“充分條件”是兩個(gè)很容易混淆概念，所對(duì)應(yīng)的集合大小也常容易搞錯(cuò)。下面介紹一個(gè)在生活中與“必要條件”和“充分條件”有關(guān)的例子，以便加深對(duì)兩個(gè)概念的理解，并區(qū)別之。 對(duì)于充分條件，約束的條件自然就會(huì)多一些，若應(yīng)用于人們的日常生活中，找充分條件的人，往往就是俗話說(shuō)的“小心眼”。對(duì)于必要條件，由于約束的條件少，人往往會(huì)變得大度，大度的人與“小心眼”的人相比，會(huì)將注意力集中在很少的，卻又是起關(guān)鍵作用的必要條件上（必要條件，用計(jì)算機(jī)的行話來(lái)說(shuō)，就是找不到一個(gè)反例的條件）。 證明方法 直接證明法和間接證明法 1．直接證明 假定 p為真，通過(guò)使用公理或已證明的定理以及正確的推理規(guī)則證明 q也為真，以此證明蘊(yùn)含式 p→ q為真。這種證明方法為直接證明法。 例 用直接證明法證明“若 p是偶數(shù)，則 p2是偶數(shù)”。 證明：假定 p是偶數(shù)為真，設(shè) p=2k（ k為整數(shù)）。由此可得， p2=2（ 2k2）。因此， p2是偶數(shù)（它是一個(gè)整數(shù)的 2倍）。 2．間接證明 因?yàn)樘N(yùn)含式 p→ q與其逆否命題 172。q→ 172。p等價(jià)，因此可以通過(guò)證明172。q→ 172。p來(lái)證明蘊(yùn)含式 p→ q為真。這種證明方法為間接證明法。 例 用間接證明法證明“若 p2是偶數(shù)，則 p是偶數(shù)”。 證明：假定此蘊(yùn)含式后件為假，即假定 p是奇數(shù)。則對(duì)某個(gè)整數(shù) k來(lái)說(shuō)有 p=2k+1。由此可得 p2=4k2+4k+1=2（ 2k2+2k） +1，因此，p2是奇數(shù)（它是一個(gè)整數(shù)的 2倍加 1）。因?yàn)閷?duì)這個(gè)蘊(yùn)含式后件的否定蘊(yùn)含著前件為假，因此該蘊(yùn)含式為真。 反證法 首先假定一個(gè)與原命題相反的命題成立，然后通過(guò)正確的推理得出與已知（或假設(shè)）條件、公理、已證過(guò)的定理等相互矛盾或自相矛盾的結(jié)果，用來(lái)證明原命題的正確。這種證明方法就是反證法，也稱歸謬法，是一種常用的數(shù)學(xué)證明方法。 例 證是 無(wú)理數(shù)。 作為無(wú)理數(shù)的發(fā)現(xiàn)， 是數(shù)學(xué)史上的一個(gè)重要事件，公元前 500年，畢達(dá)哥拉斯（ Pythagoras）學(xué)派提出了“萬(wàn)物皆數(shù)”的命題，把數(shù)歸結(jié)為整數(shù)或整數(shù)之比。而 的發(fā)現(xiàn)，使當(dāng)時(shí)人們的認(rèn)識(shí)產(chǎn)生了混亂，并導(dǎo)致了第一次數(shù)學(xué)危機(jī)。 傳說(shuō)畢氏學(xué)派的希帕索斯（ Hippasus）因最先發(fā)現(xiàn)了 為不可公度比數(shù)，而被該學(xué)派投入大海。鑒于該學(xué)派迫害數(shù)學(xué)人才的“無(wú)理行為”， 15世紀(jì)的達(dá) 芬奇（ ）將不可公度比數(shù)（即無(wú)限不循環(huán)小數(shù)）稱為無(wú)理數(shù)。 本例是數(shù)學(xué)反證法的一個(gè)典型實(shí)例，下面證明之。 證明： 歸納法 1．歸納法的定義 所謂歸納法，是指從特殊推理出一般的一種證明方法。歸納法可分為不完全歸納法、完全歸納法和數(shù)學(xué)歸納法。 2．不完全歸納法 不完全歸納法是根據(jù)部分特殊情況作出推理的一種方法，該方法多用于無(wú)窮對(duì)象的論證，然而，論證的結(jié)果不一定正確。因此，不完全歸納法不能作為嚴(yán)格的證明方法。 3．完全歸納法 完全歸納法也稱窮舉法，它是對(duì)命題中存在的所有特殊情況進(jìn)行考慮的一種方法，用該方法論證的結(jié)果是正確的，然而，它只能用于“有限”對(duì)象的論證。 4．?dāng)?shù)學(xué)歸納法 （ 1）數(shù)學(xué)歸納法的概念 數(shù)學(xué)歸納法是一種用于證明與自然數(shù)有關(guān)的命題正確性的證明方法，該方法能用“有限”的步驟解決無(wú)窮對(duì)象的論證問(wèn)題。數(shù)學(xué)歸納法廣泛地應(yīng)用于計(jì)算理論研究之中，如算法的正確性證明、圖與樹(shù)的定理證明等方面。 （ 2）數(shù)學(xué)歸納法的基本原理 數(shù)學(xué)歸納法由歸納基礎(chǔ)和歸納步驟兩個(gè)部分組成，其基本原理如下： 假定對(duì)一切正整數(shù) n，有一個(gè)命題 P(n)，若以下證明成立，則 P(n)為真： ① 歸納基礎(chǔ)：證明 P(1)為真； ② 歸納步驟：證明對(duì)任意的 i≥1，若 P(i)為真，則 P(i+1)為真。 （ 3）數(shù)學(xué)歸納法的形式化定義 根據(jù)數(shù)學(xué)歸納法的原理，可以對(duì)數(shù)學(xué)歸納法形式化地定義為： P(1)∧ ( )(P(n)→ P(n+1))→ P(n) （ 4）實(shí)例 例 求證命題 P(n)：“從 1開(kāi)始連續(xù) n個(gè)奇數(shù)之和是 n的平方”，即公式 1+3+5+…+(2n–1)=n2成立。 證明： ① 歸納基礎(chǔ)：當(dāng) n=1時(shí)，等式成立，即 1=12 ② 歸納步驟： 設(shè)對(duì)任意 k≥1， P(k)成立，即： 1+3+5+…+(2k–1)= k2 而 1+3+5+…+(2k–1)+(2(k+1)–1) = k2+2k+1=(k+1)2 即當(dāng) P(k)成立時(shí)， P(k+1)也成立，根據(jù)數(shù)學(xué)歸納法，該命題得證。 ? 構(gòu)造性證明 1．存在性證明 存在一個(gè) x使命題 P(x)成立可表示為： ?xP(x)。對(duì)形如 ?xP(x)的命題的證明稱為存在性證明。 2．構(gòu)造性證明 一般而言，在證明“存在某一個(gè)事物”時(shí)，人們常常會(huì)對(duì)條件和結(jié)論進(jìn)行分析，構(gòu)造一個(gè)符合結(jié)論要求的事實(shí)來(lái)進(jìn)行證明，這就是構(gòu)造性證明?；蛘哒f(shuō)，構(gòu)造性證明方法就是通過(guò)找出一個(gè)使得命題 P(a)為真的元素 a，從而完成該函數(shù)值的存在性證明的方法。 構(gòu)造性的證明方法，對(duì)于要解決的問(wèn)題，不光要證明該問(wèn)題解的存在，還要給出解決該問(wèn)題的具體步驟，這種步驟往往就是對(duì)解題算法的描述。 構(gòu)造性證明方法是計(jì)算機(jī)科學(xué)中廣泛使用的一種證明方法，附錄 B中Armstrong公理系統(tǒng)的完備性證明就采用了構(gòu)造性的證明方法。 遞歸和迭代 構(gòu)造性是計(jì)算機(jī)軟硬件系統(tǒng)的最根本特征，而遞歸和迭代是最具代表性的構(gòu)造性數(shù)學(xué)方法，它廣泛地應(yīng)用于計(jì)算學(xué)科各個(gè)領(lǐng)域，理解遞歸和迭代的基本思想，有助于今后的學(xué)習(xí)。 遞歸和迭代密切相關(guān)，實(shí)現(xiàn)遞歸和迭代的基礎(chǔ)基于以下一個(gè)事實(shí)。 不少序列項(xiàng)，常?？梢杂眠@樣的方式得到：由 an–1得到 an，按這樣的法則，可以從一個(gè)已知的首項(xiàng)開(kāi)始，有限次地重復(fù)做下去，最后產(chǎn)生一個(gè)序列。該序列是遞歸和迭代運(yùn)算的基礎(chǔ)。 遞歸 1．遞歸及其有關(guān)概念 遞歸不僅是數(shù)學(xué)中的一個(gè)重要概念，也是計(jì)算技術(shù)中重要的概念之一。20世紀(jì) 30年代，正是可計(jì)算的遞歸函數(shù)理論與圖靈機(jī)、 λ演算和 POST規(guī)范系統(tǒng)等理論一起為計(jì)算理論的建立奠定了基礎(chǔ)。 在計(jì)算技術(shù)中，與遞歸有關(guān)的概念有：遞歸關(guān)系、遞歸數(shù)列、遞歸過(guò)程、遞歸算法、遞歸程序、遞歸方法。 （ 1）遞歸關(guān)系指的是：一個(gè)數(shù)列的若干連續(xù)項(xiàng)之間的關(guān)系。 （ 2）遞歸數(shù)列指的是：由遞歸關(guān)系所確定的數(shù)列。 （ 3）遞歸過(guò)程指的是：調(diào)用“自身”的過(guò)程。 （ 4）遞歸算法指的是：包含遞歸過(guò)程的算法。 （ 5）遞歸程序指的是：直接或間接調(diào)用“自身”的程序。 （ 6）遞歸方法（也稱遞推法），是一種在“有限”步驟內(nèi)，根據(jù)特定的法 則或公式對(duì)一個(gè)或多個(gè)前面的元素進(jìn)行運(yùn)算，以確定一系列元素（如數(shù)或函數(shù)）的方法。 在以上有關(guān)遞歸概念的定義中，調(diào)用自身中的“自身”兩個(gè)字加了引號(hào)。若不加引號(hào)，就會(huì)出現(xiàn)循環(huán)定義的問(wèn)題。事實(shí)上，遞歸定義從來(lái)不是以某一事物自身來(lái)定義的，而是以比自身簡(jiǎn)單一些的說(shuō)法來(lái)定義的。在計(jì)算中，這種比自身簡(jiǎn)單的說(shuō)法，就是要在計(jì)算結(jié)構(gòu)相同的情況下，使計(jì)算的規(guī)模小于自身。 2．遞歸與數(shù)學(xué)歸納法 遞歸是一個(gè)重要的概念，然而，對(duì)于剛?cè)氪髮W(xué)的同學(xué)來(lái)說(shuō)，理解起來(lái)卻有一定的困難，為了更好地理解遞歸思想，我們先給出一個(gè)簡(jiǎn)單的例子。 例 計(jì)算 5?6。 計(jì)算方法之一： 6， 6+6=12， 12+6=18， 18+6=24， 24+6=30； 計(jì)算方法之二： 5?6， 4?6， 3?6， 2?6， 1?6； 1?6+6=12， 12+6=18，18+6=24， 24+6=30； 方法之二從 5?6開(kāi)始計(jì)算，假設(shè)一個(gè)剛學(xué)乘法的小學(xué)生計(jì)算不出這個(gè)數(shù)，那么，這個(gè)小學(xué)生一般會(huì)先計(jì)算 4?6，然后再加 6就可以了，若仍計(jì)算不出，則會(huì)再追溯到 3?6，直到 1?6，然后，再依次加 6，最后得到 30。這種計(jì)算方法其實(shí)就反映了一種遞歸的思想，這個(gè)例子還可以用更一般的遞歸關(guān)系表示： an=Can1+g(n)， 2， 3， 4， … 其中， C是已知常數(shù)， {g(n)}是一個(gè)已知數(shù)列。如果已知 an1就可以確定 an。從數(shù)學(xué)歸納法的角度來(lái)看，這相當(dāng)于數(shù)學(xué)歸納法歸納步驟的內(nèi)容。但僅有這個(gè)關(guān)系，還不能確定這個(gè)數(shù)列，若使它完全確定，還應(yīng)給出這個(gè)數(shù)列的初始值 a1，這相當(dāng)于數(shù)學(xué)歸納法歸納基礎(chǔ)的內(nèi)容。 與數(shù)學(xué)歸納法相對(duì)應(yīng)，遞歸由遞歸基礎(chǔ)和遞歸步驟兩部分組成。數(shù)學(xué)歸納法是一種論證方法，遞歸是算法和程序設(shè)計(jì)的一種實(shí)現(xiàn)技術(shù)，涉及遞歸定義的證明通常采用數(shù)學(xué)歸納法。 3．遞歸的定義功能 遞歸不僅應(yīng)用于算法和程序設(shè)計(jì)之中，它還廣泛地應(yīng)用于定義序列、函數(shù)和集合等各個(gè)方面。下面，舉例說(shuō)明之。 （ 1）定義序列