吉林大學遠程教育課件主講人:楊鳳杰學時：64(第七講)離散數(shù)學1.3.3不可數(shù)集合

前面我們討論的無窮集合都是可數(shù)集合，并且知道了在數(shù)軸上稠密的有理數(shù)集合也可以與自然數(shù)集合建立1-1對應關系，那么是不是所有的無窮集合都是可數(shù)集合呢？定理1.3.6全體實數(shù)做成的集合是不可數(shù)集合。證明：由定理1.3.2知,只要證明（０，１）區(qū)間內(nèi)的實數(shù)不可數(shù)就可以了。若不然，我們可以把（０，１）區(qū)間內(nèi)的數(shù)排成一個序列：

０.a11a12a13…０.a21a22a23…(2)０.a31a32a33…┆

我們考慮下面的數(shù)：０.r1r2…rk…(３)其中

１，當akk≠１rk=２，當akk＝１，k＝１，２，…

顯然，（３）是（０，１）區(qū)間內(nèi)的數(shù),但它卻不是序列(２)中的任一個數(shù)。事實上,對(２)中任一個數(shù)０.ak1ak2…akk…，因為rk≠akk,故０.ak1ak2…akk…≠０.r1r2…rk…與假設矛盾。故（０，１）區(qū)間內(nèi)的實數(shù)不可數(shù)，所以實數(shù)集不可數(shù)。上述定理的證明方法，就是著名的“康托爾對角線法”，該方法在可計算理論中有廣泛的應用。推論

實數(shù)集合R,區(qū)間(a,+)、[a,b]、[a,b)、（a,b]，a≠b都是不可數(shù)的，且與區(qū)間(0,1)等濃。我們僅看構造區(qū)間[0，1]與（0，1）之間1-1映射的例子。我們知道全體有理數(shù)的集合是可數(shù)的，于是（0，1）區(qū)間中的有理數(shù)是可數(shù)的，不妨將它們排成形式為（1）的序列。而閉區(qū)間[0，1]比區(qū)間（0，1）多兩個數(shù)0，1，它們是有理數(shù)，于是可建立閉區(qū)間[0，1]中的有理數(shù)到區(qū)間（0，1）中的有理數(shù)的1-1映射σ1如下圖。

0,1,a1,a2,…,an,……a1,a2,a3,a4,…,an+2，…令區(qū)間[0，1]中的無理數(shù)到區(qū)間（0，1）中的無理數(shù)的1-1映射σ2為自己應成自己。則映射σ=σ1∪σ2為區(qū)間[0，1]到區(qū)間（0，1）的1-1映射。從而區(qū)間[0，1]與（0，1）等濃。我們設實數(shù)集合的基數(shù)為c。定理1.3.7設A1，A2，…，An,…是互不相交的集合序列，它們的基數(shù)都是c，則的基數(shù)也是c。即可數(shù)個基數(shù)為c的集合的并集基數(shù)仍為c。證明：設In=[n-1,n),則當m≠n時，Im∩In=。因為In(n=1,2,…)的基數(shù)是c，故存在1-1映射σ1，σ2，…，使得σn(In)=An。令σ=，則σ是=[0，+）到的1-1映射。從而與[0，+）等濃，由推論知其基數(shù)為c。實際上還有更進一步的結果：可數(shù)個基數(shù)為c的集合的直積基數(shù)仍為c。從而R2，Rn的基數(shù)都是c。定理1.3.8集合Ａ的元素不能與Ａ的所有子集建立１－１映射。證明：假設σ為A到A的所有子集作元素的集合上的1—1映射。令Ｂ＝x|xA并且xσ(x)于是，存在唯一一個元素bA,使得σ(b)＝Ｂ若bＢ，則由Ｂ的定義知，bσ(b),即bB,矛盾。若bＢ,即bσ(b），于是由Ｂ的定義知，bB，矛盾。因此，在Ａ與Ａ的所有子集作元素的集合之間，不能建立１－１映射。有了這個結論，我們就可以構造基數(shù)任意大的集合。如|R||2R|||…。我們知道集合基數(shù)的關系是一個全序關系，把大于等于0的基數(shù)分別記為0，1，2，3，…，滿足0

1

2

3…。假設1=c，著名的“連續(xù)統(tǒng)問題”是：即能否找到一實數(shù)集的子集，它是不可數(shù)集合，但又不能與實數(shù)集合建立一一對應?，F(xiàn)在已經(jīng)證明了：證明連續(xù)統(tǒng)假設成立是不可能的；證明它不成立也是不可能的。因此，所謂“連續(xù)統(tǒng)問題”在現(xiàn)在的數(shù)學理論框架之中是不能判定的。第二章

命題邏輯數(shù)理邏輯是用數(shù)學的方法研究思維規(guī)律的一門學科。由于它使用了一套符號，簡潔地表達出各種推理的邏輯關系，因此，數(shù)理邏輯一般又稱為符號邏輯。數(shù)理邏輯和計算機的發(fā)展有著密切的聯(lián)系，它為機器證明、自動程序設計、計算機輔助設計等計算機應用和理論研究提供必要的理論基礎。下面兩章將介紹數(shù)理邏輯最基本的內(nèi)容：命題邏輯和謂詞邏輯。§2.1命題以及邏輯聯(lián)結詞2.1.1命題

語言的單位是句子，句子可以分為疑問句、祈使句、感嘆句、與陳述句等，其中只有陳述句具有真假意義，其他類型的句子無所謂真假。命題邏輯研究的對象是命題。所謂命題是指一句有真假意義的話。例如，“北京是中國的首都”是命題，而且它是真的；“長春是中國最大的城市”是命題，但它是假的。“關門!”，“你上哪?”這種命令和問話不是命題。需要注意的是,一個句子本身是否能分辨真假與我們是否知道它的真假是兩回事。也就是說,對于一個句子，有時我們可能無法判斷它的真假,但這個句子本身卻是有真假的。例如：(1)1960年長春春城電影院放映了國產(chǎn)故事片“白毛女”。(2)太陽系外有宇宙人。(1)和(2)都是命題。(1)是對過去的事情進行判斷，雖然我們一時很難分辨它的真假,但這句話本身是有其真假的。對于(2),目前人們尚無法確定其真假,但從事物的本質而論,句子本身是可分辨真假的,這類語句也稱為命題。下面,命題用大寫英文字母P,Q,…,P1,P2,…,表示。如果一個命題是真的，就說它的真值是1；如果一個命題是假的，就說它的真值是0。我們也用1代表一個抽象的真命題，用0代表一個抽象的假命題。2.1.2邏輯聯(lián)結詞

當我們用命題組成新的句子的時候，使用了語法中的邏輯聯(lián)結詞，下面我們介紹五種邏輯聯(lián)結詞（或稱命題的五種運算）。我們將會看到，它們和自然語言里的聯(lián)結詞是有所不同的，它們是自然語言里的聯(lián)結詞的邏輯抽象。若干個原子命題通過命題邏輯聯(lián)結詞而構成的新命題稱為復合命題。

定義2.1.1設P是一個命題，命題“P是不對的”稱為P的否定，記以P，讀作非P。P是真的當且僅當P是假的。例如，P：上海是一個城市。P：上海不是一個城市。定義2.1.2設P，Q是兩個命題，命題“P或者Q”稱為P，Q的析取，記以PQ，讀作P或Q。規(guī)定PQ是真的當且僅當P，Q中至少有一個是真的。例如，P：今天下雨，Q：今天刮風，PQ：今天下雨或者刮風。自然語言中的“或者”一詞有不可兼的意思。例如，“我到北京出差或者到廣州去度假”表示的是二者只能居其一，不會同時成立。按照聯(lián)結詞“”的定義，當P，Q都為真時，PQ也為真，因此，“”所表示的“或”是“可兼或”，對于“不可兼或”，我們不可以用來表示。定義2.1.3設P，Q是兩個命題，命題“P并且Q”稱為P，Q的合取，記以PQ，讀作P且Q。規(guī)定PQ是真的當且僅當P和Q都是真的。例如，P：22=5，Q：雪是黑的，PQ：22=5并且雪是黑的。

定義2.1.4設P，Q是兩個命題，命題“如果P，則Q”稱為P蘊涵Q，記以PQ。規(guī)定，PQ是假的當且僅當P是真的而Q是假的。例如，P：f(x)是可微的，Q：f(x)是連續(xù)的，PQ：若f(x)是可微的，則f(x)是連續(xù)的。顯然,由定義知,當P是真的,Q是真的時,命題PQ是真的。這和日常生活中語言“如果…則…”的意思是一致的。但由定義知,如果P是假命題,則不管Q是什么命題,命題“如果P，則Q”在命題邏輯中都被認為是真命題。例如,P:22=5,Q:雪是黑的，于是,命題“如果22=5,則雪是黑的”是真命題。這是和人們?nèi)粘Ｉ钪姓Z言不一致的地方。

定義2.1.5設P,Q是兩個命題,命題“P當且僅當Q”稱為P等價Q,記以PQ。規(guī)定,PQ是真的當且僅當P,Q或者都是真的，或者都是假的。例如，P：a2+b2=a2,Q：b=0，PQ：a2+b2=a2當且僅當b=0。利用上面介紹的這五種邏輯聯(lián)結詞，我們可以把許多日常語句符號化。1、字體安裝與設置如果您對PPT模板中的字體風格不滿意，可進行批量替換，一次性更改各頁面字體。在“開始”選項卡中，點擊“替換”按鈕右側箭頭，選擇“替換字體”。（如下圖）在圖“替換”下拉列表中選擇要更改字體。（如