第一篇：離散數(shù)學(xué)自學(xué)
學(xué)習(xí)體會(huì)
專(zhuān)業(yè)：計(jì)算機(jī) 姓名：范文芳 學(xué)號(hào)： 成績(jī)： 院校：
離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的基礎(chǔ)核心課程。通過(guò)本課程的學(xué)習(xí)，使學(xué)生具有現(xiàn)代數(shù)學(xué)的觀點(diǎn)和方法，并初步掌握處理離散結(jié)構(gòu)所必須的描述工具和方法。同時(shí)，也要培養(yǎng)學(xué)生抽象思維和慎密概括的能力，使學(xué)生具有良好的開(kāi)拓專(zhuān)業(yè)理論的素質(zhì)和使用所學(xué)知識(shí)，分析和解決實(shí)際問(wèn)題的能力，為學(xué)生以后學(xué)習(xí)計(jì)算機(jī)基礎(chǔ)理論與專(zhuān)業(yè)課程打下良好的基礎(chǔ)。
學(xué)習(xí)離散數(shù)學(xué)有兩項(xiàng)最基本的任務(wù)：其一是通過(guò)學(xué)習(xí)離散數(shù)學(xué)，使學(xué)生了解和掌握在后續(xù)課程中要直接用到的一些數(shù)學(xué)概念和基本原理，掌握計(jì)算機(jī)中常用的科學(xué)論證方法，為后續(xù)課程的學(xué)習(xí)奠定一個(gè)良好的數(shù)學(xué)基礎(chǔ)；其二是在離散數(shù)學(xué)的學(xué)習(xí)過(guò)程中，培訓(xùn)自學(xué)能力、抽象思維能力和邏輯推理能力，以提高專(zhuān)業(yè)理論水平。因此學(xué)習(xí)離散數(shù)學(xué)對(duì)于計(jì)算機(jī)、通信等專(zhuān)業(yè)后續(xù)課程的學(xué)習(xí)和今后從事計(jì)算機(jī)科學(xué)等工作是至關(guān)重要的。但是由于離散數(shù)學(xué)的離散性、知識(shí)的分散性和處理問(wèn)題的特殊性，使部分學(xué)生在剛剛接觸離散數(shù)學(xué)時(shí)，對(duì)其中的一些概念和處理問(wèn)題的方法往往感到困惑，特別是在做證明題時(shí)感到無(wú)從下手，找不到正確的解題思路。因此，對(duì)離散數(shù)學(xué)的學(xué)習(xí)方法給予適當(dāng)?shù)闹笇?dǎo)和對(duì)學(xué)習(xí)過(guò)程中遇到的一些問(wèn)題分析是十分必要的。
一、認(rèn)知離散數(shù)學(xué)
離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)基礎(chǔ)理論的核心課程之一，是計(jì)算機(jī)及應(yīng)用、通信等專(zhuān)業(yè)的一門(mén)重要的基礎(chǔ)課。它以研究量的結(jié)構(gòu)和相互關(guān)系為主要目標(biāo)，其研究對(duì)象一般是有限個(gè)或可數(shù)個(gè)元素，充分體現(xiàn)了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。學(xué)習(xí)離散數(shù)學(xué)的目的是為學(xué)習(xí)計(jì)算機(jī)、通信等專(zhuān)業(yè)各后續(xù)課程做好必要的知識(shí)準(zhǔn)備，進(jìn)一步提高抽象思維和邏輯推理的能力，為計(jì)算機(jī)的應(yīng)用提供必要的描述工具和理論
基礎(chǔ)。
1．定義和定理多
離散數(shù)學(xué)是建立在大量定義、定理之上的邏輯推理學(xué)科，因此對(duì)概念的理解是學(xué)習(xí)這門(mén)課程的核心。在學(xué)習(xí)這些概念的基礎(chǔ)上，要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的實(shí)體則是大量的定理和性質(zhì)。在考試中有一部分內(nèi)容是考查學(xué)生對(duì)定義和定理的識(shí)記、理解和運(yùn)用，因此要真正理解離散數(shù)學(xué)中所給出的每個(gè)基本概念的真正的含義。比如，命題的定義、五個(gè)基本聯(lián)結(jié)詞、公式的主析取范式和主合取范式、三個(gè)推理規(guī)則以及反證法；集合的五種運(yùn)算的定義；關(guān)系的定義和關(guān)系的四個(gè)性質(zhì)；函數(shù)（映射）和幾種特殊函數(shù)（映射）的定義；圖、完全圖、簡(jiǎn)單圖、子圖、補(bǔ)圖的定義；圖中簡(jiǎn)單路、基本路的定義以及兩個(gè)圖同構(gòu)的定義；樹(shù)與最小生成樹(shù)的定義。掌握和理解這些概念對(duì)于學(xué)好離散數(shù)學(xué)是至關(guān)重要的。2.方法性強(qiáng)
在離散數(shù)學(xué)的學(xué)習(xí)過(guò)程中，一定要注重和掌握離散數(shù)學(xué)處理問(wèn)題的方法，在做題時(shí)，找到一個(gè)合適的解題思路和方法是極為重要的。如果知道了一道題用怎樣的方法去做或證明，就能很容易地做或證出來(lái)。反之，則事倍功半。在離散數(shù)學(xué)中，雖然各種各樣的題種類(lèi)繁多，但每類(lèi)題的解法均有規(guī)律可循。所以在聽(tīng)課和平時(shí)的復(fù)習(xí)中，要善于總結(jié)和歸納具有規(guī)律性的內(nèi)容。在平時(shí)的講課和復(fù)習(xí)中，老師會(huì)總結(jié)各類(lèi)解題思路和方法。作為學(xué)生，首先應(yīng)該熟悉并且會(huì)用這些方法，同時(shí)，還要勤于思考，對(duì)于一道題，進(jìn)可能地多探討幾種解法。3.抽象性強(qiáng)
離散數(shù)學(xué)的特點(diǎn)是知識(shí)點(diǎn)集中，對(duì)抽象思維能力的要求較高。由于這些定義的抽象性，使初學(xué)者往往不能在腦海中直接建立起它們與現(xiàn)實(shí)世界中客觀事物的聯(lián)系。不管是哪本離散數(shù)學(xué)教材，都會(huì)在每一章中首先列出若干個(gè)定義和定理，接著就是這些定義和定理的直接應(yīng)用，如果沒(méi)有較好的抽象思維能力，學(xué)習(xí)離散數(shù)學(xué)確實(shí)具有一定的困難。因此，在離散數(shù)學(xué)的學(xué)習(xí)中，要注重抽象思維能力、邏輯推理能力的培養(yǎng)和訓(xùn)練，這種能力的培養(yǎng)對(duì)今后從事各種工作都是極其重要的。
在學(xué)習(xí)離散數(shù)學(xué)中所遇到的這些困難，可以通過(guò)多學(xué)、多看、認(rèn)真分析講課
中所給出的典型例題的解題過(guò)程，再加上多練，從而逐步得到解決。在此特別強(qiáng)調(diào)一點(diǎn)：深入地理解和掌握離散數(shù)學(xué)的基本概念、基本定理和結(jié)論，是學(xué)好離散數(shù)學(xué)的重要前提之一。所以，同學(xué)們要準(zhǔn)確、全面、完整地記憶和理解所有這些基本定義和定理。4.內(nèi)在聯(lián)系性
離散數(shù)學(xué)的三大體系雖然來(lái)自于不同的學(xué)科，但是這三大體系前后貫通，形成一個(gè)有機(jī)的整體。通過(guò)認(rèn)真的分析可尋找出三大部分之間知識(shí)的內(nèi)在聯(lián)系性和規(guī)律性。如：集合論、函數(shù)、關(guān)系和圖論，其解題思路和證明方法均有相同或相似之處。
二、認(rèn)知解題規(guī)范
一般來(lái)說(shuō)，離散數(shù)學(xué)的考試要求分為：了解、理解和掌握。了解是能正確判別有關(guān)概念和方法；理解是能正確表達(dá)有關(guān)概念和方法的含義；掌握是在理解的基礎(chǔ)上加以靈活應(yīng)用。為了考核學(xué)生對(duì)這三部分的理解和掌握的程度，試題類(lèi)型一般可分為：判斷題、填空題、選擇題、計(jì)算題和證明題。判斷題、填空題、選擇題主要涉及基本概念、基本理論、重要性質(zhì)和結(jié)論、公式及其簡(jiǎn)單計(jì)算；計(jì)算題主要考核學(xué)生的基本運(yùn)用技能和速度，要求寫(xiě)出完整的計(jì)算過(guò)程和步驟；證明題主要考查應(yīng)用概念、性質(zhì)、定理及重要結(jié)論進(jìn)行邏輯推理的能力，要求寫(xiě)出嚴(yán)格的推理和論證過(guò)程。
學(xué)習(xí)離散數(shù)學(xué)的最大困難是它的抽象性和邏輯推理的嚴(yán)密性。在離散數(shù)學(xué)中，假設(shè)讓你解一道題或證明一個(gè)命題，你應(yīng)首先讀懂題意，然后尋找解題或證明的思路和方法，當(dāng)你相信已找到了解題或證明的思路和方法，你必須把它嚴(yán)格地寫(xiě)出來(lái)。一個(gè)寫(xiě)得很好的解題過(guò)程或證明是一系列的陳述，其中每一條陳述都是前面的陳述經(jīng)過(guò)簡(jiǎn)單的推理而得到的。仔細(xì)地寫(xiě)解題過(guò)程或證明是很重要的，既能讓讀者理解它，又能保證解題過(guò)程或證明準(zhǔn)確無(wú)誤。一個(gè)好的解題過(guò)程或證明應(yīng)該是條理清楚、論據(jù)充分、表述簡(jiǎn)潔的。針對(duì)這一要求，在講課中老師會(huì)提供大量的典型例題供同學(xué)們參考和學(xué)習(xí)。
通過(guò)離散數(shù)學(xué)的學(xué)習(xí)和訓(xùn)練，能使同學(xué)們學(xué)會(huì)在離散數(shù)學(xué)中處理問(wèn)題的一般性的規(guī)律和方法，一旦掌握了離散數(shù)學(xué)中這種處理問(wèn)題的思想方法，學(xué)習(xí)和掌握離散數(shù)學(xué)的知識(shí)就不再是一件難事了。復(fù)習(xí)離散數(shù)學(xué)的整個(gè)過(guò)程可大致分為三個(gè)
階段。
第一階段，大量進(jìn)行知識(shí)儲(chǔ)備的階段。
離散數(shù)學(xué)是建立在大量定義上面的邏輯推理學(xué)科。因而對(duì)概念的理解是我們學(xué)習(xí)這門(mén)學(xué)科的核心。由于這些定義非常抽象，初學(xué)者往往不能在腦海中建立起它們與現(xiàn)實(shí)世界中客觀事物的聯(lián)系。對(duì)于跨專(zhuān)業(yè)自學(xué)的朋友來(lái)說(shuō)更是如此。這是離散數(shù)學(xué)學(xué)習(xí)中的第一個(gè)困難。因此，對(duì)于第一遍復(fù)習(xí)，我們提出一個(gè)最為重要的要求，即準(zhǔn)確、全面、完整地記憶所有的定義和定理。具體做法可以是：在進(jìn)行完一章的學(xué)習(xí)后，用專(zhuān)門(mén)的時(shí)間對(duì)該章包括的定義與定理實(shí)施強(qiáng)記，直到能夠全部正確地默寫(xiě)出來(lái)為止。無(wú)須強(qiáng)求一定要理解，記住并能準(zhǔn)確復(fù)述 各定義定理是此階段的最高要求。也不需做太多的題（甚至不做課后習(xí)題也是可以的，把例題看懂就行），重心要放在對(duì)定義和定理的記憶上。請(qǐng)牢記，這是為未來(lái)的向廣度和深度擴(kuò)張作必要的準(zhǔn)備。
這一過(guò)程視各人情況不同耗時(shí)約在一到兩個(gè)月內(nèi)。第二階段，深入學(xué)習(xí)，并大量做課后習(xí)題的階段。
這是最漫長(zhǎng)的一個(gè)階段，耗時(shí)也很難估計(jì)，一般來(lái)說(shuō)，若能熟練解出某一章75%以上的課后習(xí)題，可以考慮結(jié)束該章。
解離散數(shù)學(xué)的題，方法非常重要，如果拿到一道題，立即能夠看出它所屬的類(lèi)型及關(guān)聯(lián)的知識(shí)點(diǎn)，就不難選用正確的方法將其解決，反之則事倍功半。例如在命題邏輯部分，無(wú)非是這么幾種題目：將自然語(yǔ)言表述的命題符號(hào)化，等價(jià)命題的相互轉(zhuǎn)化（包括化為主合取范式與主析取范式），以給出的若干命題為前提進(jìn)行推理和證明。相應(yīng)的對(duì)策也馬上就可以提出來(lái)。以推理題為例，主要是利用P、T規(guī)則，加上蘊(yùn)涵和等價(jià)公式表，由給定的前提出發(fā)進(jìn)行推演，或根據(jù)題目特點(diǎn)采用真值表法、CP規(guī)則和反證法。由此可見(jiàn)，在平常復(fù)習(xí)中，要善于總結(jié)和歸納，仔細(xì)體會(huì)題目類(lèi)型和此類(lèi)題目的解題套路。如此多作練習(xí)，則即使遇到比較陌生的題也可以較快地領(lǐng)悟其本質(zhì)，從而輕松解出。
“熟讀唐詩(shī)三百首，不會(huì)做詩(shī)也會(huì)吟。”要是拿到一本習(xí)題集，從頭到尾做過(guò)，甚至背會(huì)的話。那么，在考場(chǎng)上就會(huì)發(fā)現(xiàn)絕大多數(shù)題見(jiàn)過(guò)或似曾相識(shí)。這時(shí)，要取得較好的成績(jī)也就不是太難的事情了。這一情況具有普遍性，對(duì)許多院校的考試都適用。
第三階段，進(jìn)行真題模擬訓(xùn)練，提高整體水平和綜合能力的階段。
這一階段從第二階段結(jié)束一直持續(xù)到考試。
除了我們使用的課本外，應(yīng)盡可能地弄到報(bào)考院校的專(zhuān)業(yè)課歷年試題。因?yàn)槊總€(gè)單位對(duì)該科目的側(cè)重點(diǎn)畢竟有不同，從歷年試題中可以獲取許多有用的信息。這些歷年試題此時(shí)就有了巨大的作用。
第二篇：離散數(shù)學(xué)
離散數(shù)學(xué)課件作業(yè)
第一部分 集合論
第一章集合的基本概念和運(yùn)算
1-1 設(shè)集合 A ={1，{2}，a，4，3}，下面命題為真是[ B ]
A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2} ? A。
1-2 A,B,C 為任意集合，則他們的共同子集是[ D ]
A．C；B．A；C．B；D．?。
1-3 設(shè) S = {N，Z，Q，R}，判斷下列命題是否成立 ？
（1）N ? Q，Q ∈S，則 N ? S［不成立］
（2）-1 ∈Z，Z ∈S，則-1 ∈S［不成立］
1-4 設(shè)集合 A ={3，4}，B = {4，3} ∩ ?，C = {4，3} ∩{ ? }，D ={ 3，4，? }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F(xiàn) = { 4，?，3，3}，試問(wèn)哪兩個(gè)集合之間可用等號(hào)表示 ？
答：A = E；B = C；D = F
1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x2 ≤ 9 }
（2）A = { x│x ∈N 且 3－x 〈 3 }
答：（1）A = { 0，1，2，3 }；
（2）A = { 1，2，3，4，……} = Z+；
第二章二元關(guān)系
2-1 給定 X =（3, 2，1），R 是 X 上的二元關(guān)系，其表達(dá)式如下：
R = {〈x，y〉x，y ∈X 且 x≤ y }
求：(1)domR =?;(2)ranR =?;(3)R 的性質(zhì)。
答：R = {<2，3>，<1,2>，<1,3>}；
DomR={R中所有有序?qū)Φ膞}={2,1,1}={2,1};
RanR={R中所有有序?qū)Φ膟}={3,2,3}={3,2}；
R 的性質(zhì):反自反,反對(duì)稱(chēng),傳遞性質(zhì).2-2 設(shè) R 是正整數(shù)集合上的關(guān)系，由方程 x + 3y = 12 決定，即
R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，試求：
（1）R 的列元表達(dá)式；（2）給出 dom（R。R）。
答：根據(jù)方程式有：y=4-x/3，x 只能取 3，6,9。
（1）R = {〈3，3〉,〈6，2〉,〈9，1〉}；
至于(2),望大家認(rèn)真完成合成運(yùn)算 R。R={<3,3>}.然后,給出 R。R 的定義域,即
（2）dom（R。R）= {3}。
2-3 判斷下列映射 f 是否是 A 到 B 的函數(shù)；并對(duì)其中的 f：A→B 指出他的性質(zhì)，即
是否單射、滿射和雙射，并說(shuō)明為什么。
（1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。
（2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。
（3）A = B = R，f=x。
（4）A = B = N，f=x2。
（5）A = B = N，f = x + 1。
答：（1）是 A 到 B 的函數(shù)，是滿射而不是單射；
（2）是雙射；
（3）是雙射；
（4）是單射，而不是滿射；
（5）是單射而不是滿射。
2-4 設(shè) A ={1，2，3，4}，A 上的二元關(guān)系
R ={〈x，y〉︱（x-y）能被3整除}，則自然映射 g：A→A/R使 g(1)=[C]
A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。
2-5 設(shè) A ={1，2，3}，則商集A/IA =[D]
A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。
2-6．設(shè)ｆ(x)＝x+1，ｇ(x)＝x-1 都是從實(shí)數(shù)集合Ｒ到Ｒ的函數(shù)，則ｆ。ｇ＝[C]
A．x+1；B．x-1；C．x；D．x2。
第三章 結(jié)構(gòu)代數(shù)(群論初步)
3-1 給出集合及二元運(yùn)算，闡述是否代數(shù)系統(tǒng)，何種代數(shù)系統(tǒng) ？
（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元運(yùn)算 *是普通乘法。
（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；
二元運(yùn)算。定義如下：對(duì)于所有 ai，aj ∈S2，都有 ai。aj = ai。
（3）S3 = {0，1}，二元運(yùn)算 * 是普通乘法。
答：（1）二元運(yùn)算*在S1上不封閉．所以，＂S1，*＂不能構(gòu)成代數(shù)系統(tǒng)。
（2）由二元運(yùn)算的定義不難知道。在 S2 內(nèi)是封閉的，所以，〈S2。〉構(gòu)成代數(shù)
系統(tǒng)；然后看該代數(shù)系統(tǒng)的類(lèi)型：該代數(shù)系統(tǒng)只是半群。
（3）很明顯，〈{0，1}，*〉構(gòu)成代數(shù)系統(tǒng)；滿足結(jié)合律，為半群；1是幺元，為獨(dú)異
點(diǎn)；而 0 為零元；結(jié)論：僅為獨(dú)異點(diǎn)，而不是群。
3-2 在自然數(shù)集合上，下列那種運(yùn)算是可結(jié)合的［A］
A．x*y = max(x,y)；B．x*y = 2x+y ；
C．x*y = x2+y2 ；D．x*y =︱x-y︱..3-3 設(shè) Z 為整數(shù)集合，在 Z 上定義二元運(yùn)算。，對(duì)于所有 x，y ∈Z都有
x。y=x + y，試問(wèn)〈Z。〉能否構(gòu)成群，為什麼 ？
答：由題已知，集合Z滿足封閉性；二元運(yùn)算滿足結(jié)合律，依此集合Z為半群；有幺元為 －5，為獨(dú)異點(diǎn).假設(shè)代數(shù)系統(tǒng)的幺元是集合中的元素 e,則一個(gè)方程來(lái)自于二元運(yùn)算定義, 即e。x= e + x，一個(gè)方程來(lái)自該特殊元素的定義的性質(zhì),即e。x = x.由此而來(lái)的兩個(gè)方程聯(lián)立結(jié)果就有: e+x=x 成立.削去 x,e=0 的結(jié)果不是就有了嗎!；每個(gè)元素都有逆.求每個(gè)元素的逆元素,也要解聯(lián)方程,如同求幺元一樣的道理；結(jié)論是：代數(shù)系統(tǒng)〈 Z。〉構(gòu)成群。
第二部分圖論方法
第四章 圖
4-1 10 個(gè)頂點(diǎn)的簡(jiǎn)單圖 G 中有 4 個(gè)奇度頂點(diǎn)，問(wèn) G 的補(bǔ)圖中有幾個(gè)偶數(shù)度頂點(diǎn) ？ 答：因?yàn)?0階完全圖的每個(gè)頂點(diǎn)的度數(shù)都是n-1=9――為奇數(shù)。這樣一來(lái)，一個(gè)無(wú)向簡(jiǎn)單圖 G 的某頂點(diǎn)的度數(shù)是奇數(shù)，其補(bǔ)圖的相應(yīng)頂點(diǎn)必偶數(shù)，因?yàn)橐粋€(gè)偶數(shù)與一個(gè)奇數(shù)之和才是奇數(shù)．所以，Ｇ的補(bǔ)圖中應(yīng)有 10-4＝6 個(gè)奇數(shù)度頂點(diǎn)。
4-2 是非判斷：無(wú)向圖G中有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)度數(shù)全是2,共有 8 個(gè)頂點(diǎn).[是]
4-3 填空補(bǔ)缺：1條邊的圖 G 中，所有頂點(diǎn)的度數(shù)之和為[2]
第五章樹(shù)
5-1握手定理的應(yīng)用（指無(wú)向樹(shù)）
（1）在一棵樹(shù)中有 7 片樹(shù)葉，3 個(gè) 3 度頂點(diǎn)，其余都是 4 度頂點(diǎn)，問(wèn)有(有1個(gè)4度頂點(diǎn))個(gè)？
（2）一棵樹(shù)有兩個(gè) 4 度頂點(diǎn)，3 個(gè) 3 度頂點(diǎn)，其余都是樹(shù)葉，問(wèn)有(9個(gè)1度頂點(diǎn))片？
5-2 一棵樹(shù)中有 i 個(gè)頂點(diǎn)的度數(shù)為 i（i=2，…k），其余頂點(diǎn)都是樹(shù)葉(即一度頂點(diǎn))，問(wèn)樹(shù)葉多少片？設(shè)有x片,則 x=
答：假設(shè)有 x 片樹(shù)葉，根據(jù)握手定理和樹(shù)的頂點(diǎn)與邊數(shù)的關(guān)系，有關(guān)于樹(shù)葉的方程，解方程得到樹(shù)葉數(shù) x = Σi（i—2）i + 2，（i = 2，3，……k）。
5-3 求最優(yōu) 2 元樹(shù)：用 Huffman 算法求帶權(quán)為 1，2，3，5，7，8 的最優(yōu) 2 元樹(shù) T。試問(wèn)：（1）T 的權(quán) W（T）？（2）樹(shù)高幾層 ？
答：用 Huffman 算法，以 1，2，3，5，7，8 為權(quán)，最優(yōu) 2 元樹(shù) T ；然后，計(jì)算并回答所求問(wèn)題：（1）T 的權(quán) W（T）= 61；（2）樹(shù)高幾層：4 層樹(shù)高。
5-4以下給出的符號(hào)串集合中，那些是前綴碼？將結(jié)果填入[]內(nèi).B1 = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非]
5-5(是非判斷題)11階無(wú)向連通圖G中17條邊，其任一棵生成樹(shù) T 中必有6條樹(shù)枝 [非]
5-6(是非判斷題)二元正則樹(shù)有奇數(shù)個(gè)頂點(diǎn)。[是]
5-7 在某次通信中 a，b，c，d，e 出現(xiàn)的頻率分別為 5%;10%;20%;30%;35%.求傳輸他們的最佳前綴碼。
1、最優(yōu)二元樹(shù) T；2.每個(gè)字母的碼字；
答：每個(gè)字母出現(xiàn)頻率分別為：G、D、B、E、Y：14%，O：28%；(也可以不歸一,某符號(hào)
出現(xiàn)次數(shù)即為權(quán)，如右下圖).。100（近似）7.。563..4。282..2..2。..1..14141414111
1所以，得到編碼如下：G（000），D（001），B（100），E（101），Y（01），O（11）。
第三部分邏輯推理理論
第六章 命題邏輯
6-1 判斷下列語(yǔ)句是否命題，簡(jiǎn)單命題或復(fù)合命題。
（1）2月 17 號(hào)新學(xué)期開(kāi)始。[真命題]
（2）離散數(shù)學(xué)很重要。[真命題]
（3）離散數(shù)學(xué)難學(xué)嗎 ？[真命題]
（4）C 語(yǔ)言具有高級(jí)語(yǔ)言的簡(jiǎn)潔性和匯編語(yǔ)言的靈活性。[復(fù)合命題]
（5）x + 5 大于 2。[真命題]
（6）今天沒(méi)有下雨，也沒(méi)有太陽(yáng)，是陰天。[復(fù)合命題]
6-2 將下列命題符號(hào)化.（1）2 是偶素?cái)?shù)。
（2）小李不是不聰明，而是不好學(xué)。
（3）明天考試英語(yǔ)或考數(shù)學(xué)。（兼容或）
（4）你明天不去上海，就去北京。（排斥或）
答：（1）符號(hào)化為： p ∧ q。
（2）符號(hào)化為：p ∧ ﹃q。
（3）符號(hào)化為：p ∨ q。
（4）符號(hào)化為：（﹃p ∧ q）∨（p ∧ ﹃q）。
6-3分別用等值演算法,真值表法,主析取范式法,判斷下列命題公式的類(lèi)型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0；
（2）Σ（0，1，2，3）；
（3）Σ（1，3）。
以下兩題(6-4;6-5)為選擇題,將正確者填入[]內(nèi).6-4 令 p：經(jīng)一塹；q：長(zhǎng)一智。命題’’只有經(jīng)一塹，才能長(zhǎng)一智’’符號(hào)化為[B]
A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p
6-5 p：天氣好；q：我去游玩．命題 ”如果天氣好，則我去游玩” 符號(hào)化為［B］
A． p→q；B．q→p；C．p∧q；D．﹁q→p
6-6證明題:用不同方法(必須有構(gòu)造證明法)判斷推理結(jié)果是否正確。
如果今天下雨，則明天不上體育課。今天下雨了。所以，明天沒(méi)有上體育課。答：將公式分成前提及結(jié)論。
前提：（p→﹃q），p；
結(jié)論：﹃q；
證明：（1）（p→﹃q）前提引入
（2）p前提引入
（3）（p→﹃q）∧p（1）（2）假言推理
（4）﹃q
要證明的結(jié)論與證明結(jié)果一致，所以推理正確。
第七章謂詞邏輯
7-1 在謂詞邏輯中用 0 元謂詞將下列命題符號(hào)化
（1）這臺(tái)機(jī)器不能用。
（2）如果 2 ＞ 3，則 2 ＞ 5。
答：（1）﹃F（a）。
（2）L（a，b）→ H（a，z）。
7-2 填空補(bǔ)缺題：設(shè)域?yàn)檎麛?shù)集合Ｚ，命題?x?y彐z（x-y=z）的真值為（0）
7-3在謂詞邏輯中將下列命題符號(hào)化
（1）有的馬比所有的牛跑得慢。
（2）人固有一死。
答：（1）符號(hào)化為：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。
（2）與（1）相仿，要注意量詞、聯(lián)結(jié)詞間的搭配：
x（F（x）→y（G（y）→ H（x，y）））。
《附錄》習(xí)題符號(hào)集
? 空集, ∪ 并, ∩ 交,⊕ 對(duì)稱(chēng)差,～ 絕對(duì)補(bǔ),∑ 累加或主析取范式表達(dá)式縮寫(xiě) , － 普通減法, ÷ 普通除法, ㏑ 自然對(duì)數(shù), ㏒ 對(duì)數(shù)，﹃ 非，?量詞 ”所有”，”每個(gè)”，∨ 析取聯(lián)結(jié)詞，∧ 合取聯(lián)結(jié)詞，彐 量詞”存在”，”有的”。
2010年8月12號(hào)。
第三篇：淺談離散數(shù)學(xué)專(zhuān)題
淺談離散數(shù)學(xué)
【摘要】離散數(shù)學(xué)是一門(mén)理論性強(qiáng),知識(shí)點(diǎn)多,概念抽象的基礎(chǔ)課程,學(xué)生學(xué)習(xí)起來(lái)普遍感到難度很高。本文從離散數(shù)學(xué)內(nèi)容、學(xué)生學(xué)習(xí)興趣的激發(fā)、教學(xué)內(nèi)容的安排、教學(xué)方式方法的使用等方面,探討了如何上好、學(xué)好離散數(shù)學(xué)課。
【關(guān)鍵詞】離散數(shù)學(xué)教學(xué)方法教師 學(xué)生
離散數(shù)學(xué)研究的是離散量，是計(jì)算機(jī)科學(xué)與技術(shù)系各專(zhuān)業(yè)的核心課程。課程內(nèi)容具有知識(shí)點(diǎn)多、散、抽象等特點(diǎn),加之學(xué)生不能認(rèn)識(shí)到該課程的重要性,缺乏學(xué)習(xí)興趣和學(xué)習(xí)主動(dòng)性,不僅忽視該課程的學(xué)習(xí),甚至害怕這門(mén)課程。因此,創(chuàng)新教學(xué)方法,提高學(xué)生自主學(xué)習(xí)的積極性,對(duì)提高學(xué)生的能力、提升教學(xué)質(zhì)量和水平具有重要的意義。通過(guò)一學(xué)期的學(xué)習(xí)和專(zhuān)研,我積累了少許經(jīng)驗(yàn),總結(jié)了一些關(guān)于離散數(shù)學(xué)的教學(xué)方法，僅供大家參考。
一、離散數(shù)學(xué)的特點(diǎn)
本課程介紹計(jì)算機(jī)科學(xué)與技術(shù)系各專(zhuān)業(yè)所需要的離散數(shù)學(xué)基礎(chǔ)知識(shí),主要有以下兩點(diǎn)特點(diǎn)：
1、知識(shí)點(diǎn)集中，概念和定理多：《離散數(shù)學(xué)》是建立在大量概念之上的邏輯推理學(xué)科，概念的理解是我們學(xué)習(xí)這門(mén)學(xué)科的核心。掌握、理解和運(yùn)用這些概念和定理是學(xué)好這門(mén)課的關(guān)鍵。要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的則是定理和性質(zhì)。
2、方法性強(qiáng)：離散數(shù)學(xué)的特點(diǎn)是抽象思維能力的要求較高。培養(yǎng)學(xué)生抽象思維能力、邏輯推理能力、縝密概括能力以及分析和解決實(shí)際問(wèn)題能力的主干課程,對(duì)學(xué)習(xí)其他諸多課程,具有重要的指導(dǎo)作用。《離散數(shù)學(xué)》的證明題多，不同的題型會(huì)需要不同的證明方法，同一個(gè)題也可能有幾種方法，具有很強(qiáng)的方法性。
二、教學(xué)困難所在1、離散數(shù)學(xué)是一門(mén)理論性強(qiáng),知識(shí)點(diǎn)多,概念抽象的基礎(chǔ)課程, 內(nèi)容具有知
識(shí)點(diǎn)多、散、抽象等特點(diǎn)，學(xué)生學(xué)者困難；
2、學(xué)生不能認(rèn)識(shí)到該課程的重要性,缺乏學(xué)習(xí)興趣和學(xué)習(xí)主動(dòng)性,不僅忽視該課程的學(xué)習(xí),甚至害怕這門(mén)課程。
3、離散數(shù)學(xué)課程在課堂教學(xué)難度、教學(xué)時(shí)間等方面的原因,很多學(xué)校都出現(xiàn)師生、學(xué)生之間的交流較少，從而使學(xué)生學(xué)習(xí)困難。
三、離散數(shù)學(xué)的教學(xué)方法引導(dǎo)學(xué)生提高對(duì)離散數(shù)學(xué)課程應(yīng)用性的認(rèn)識(shí),激發(fā)學(xué)生學(xué)習(xí)的興趣和愛(ài)好,增強(qiáng)汲取知識(shí)的自主性
離散數(shù)學(xué)課程是一門(mén)基礎(chǔ)性課程,學(xué)習(xí)離散數(shù)學(xué)課程對(duì)學(xué)生今后的學(xué)習(xí)和工作,具有重要的作用,例如培養(yǎng)學(xué)生的抽象思維能力和縝密的邏輯推理能力,為學(xué)生今后處理離散信息,提高專(zhuān)業(yè)理論水平,從事計(jì)算機(jī)的實(shí)際工作提供必備的數(shù)學(xué)工具;通過(guò)學(xué)習(xí),可以掌握數(shù)理邏輯,集合論,代數(shù)結(jié)構(gòu)和圖論的基本概念和原理,并會(huì)運(yùn)用離散數(shù)學(xué)的方法,分析和解決計(jì)算機(jī)理論和應(yīng)用中的一些問(wèn)題等。學(xué)習(xí)主動(dòng)性是學(xué)生的力量之源,因此,引導(dǎo)學(xué)生充分認(rèn)識(shí)學(xué)習(xí)離散數(shù)學(xué)課程的作用,能夠激發(fā)學(xué)生學(xué)習(xí)的愛(ài)好和熱情,提升學(xué)生學(xué)習(xí)的積極性和主動(dòng)性,從而使學(xué)生學(xué)有成效。認(rèn)真?zhèn)湔n,合理準(zhǔn)備教學(xué)內(nèi)容和安排教學(xué)環(huán)節(jié),優(yōu)化教學(xué)方式方法
備好課是教學(xué)取得預(yù)期效果的前提和基礎(chǔ),針對(duì)學(xué)生學(xué)習(xí)具體情況,合理準(zhǔn)備教學(xué)內(nèi)容和安排教學(xué)環(huán)節(jié),使用恰當(dāng)?shù)慕虒W(xué)方法,在教學(xué)中可以起到事半功倍的效果。
(1)合理地準(zhǔn)備教學(xué)內(nèi)容。根據(jù)課程教學(xué)大綱和離散數(shù)學(xué)課程定理定義比較多、知識(shí)比較抽象的特點(diǎn)以及學(xué)生的實(shí)際情況,準(zhǔn)備深度和廣度適合學(xué)生特點(diǎn)的教學(xué)內(nèi)容。
(2)合理地講解課程內(nèi)容,重難點(diǎn)突出講解,注意輕重緩急。對(duì)于離散數(shù)學(xué)中比較重要、比較抽象的概念和定理,如邏輯的推理理論、關(guān)系的性質(zhì)、群、圖等,認(rèn)真分析,用多種方式和方法深入
講解,可以使用解析法、圖示法、矩陣法舉實(shí)例等多種方法講解。對(duì)于比較容易理解和掌握的內(nèi)容,可以一筆帶過(guò)。這樣,學(xué)生對(duì)所學(xué)內(nèi)容就會(huì)有重點(diǎn)地學(xué)習(xí),主次分明,學(xué)生不僅可以對(duì)所學(xué)內(nèi)容掌握透徹,更能熟練把握離散數(shù)學(xué)中分析問(wèn)題和解決問(wèn)題的思路、方式和方法。
(3)啟發(fā)式教學(xué)和教師講授相結(jié)合。很多人認(rèn)為,大學(xué)教學(xué)課時(shí)緊,內(nèi)容多,關(guān)鍵靠學(xué)生自主學(xué)習(xí),我卻認(rèn)為并不完全是這樣的。如果教師不顧學(xué)生的理解情況,只顧在講臺(tái)上講授知識(shí),課堂氛圍會(huì)很沉悶,很多同學(xué)不能專(zhuān)注于該門(mén)課程的學(xué)習(xí),經(jīng)常走神,教學(xué)很難達(dá)到預(yù)期的效果。因此,有針對(duì)性地提問(wèn)和展開(kāi)討論,不僅能夠培養(yǎng)學(xué)生的思考能力,更能調(diào)動(dòng)學(xué)生學(xué)習(xí)的興趣和積極性,從而使教學(xué)達(dá)到最佳效果。也可以引進(jìn)有趣生動(dòng)的例子說(shuō)明概念，既活躍課堂，又鞏固了學(xué)生的記憶。3 合理布置作業(yè),認(rèn)真批改作業(yè),有針對(duì)性地安排習(xí)題課和課后答疑
學(xué)數(shù)學(xué)就要做數(shù)學(xué)，《離散數(shù)學(xué)》的學(xué)習(xí)也不例外。學(xué)習(xí)數(shù)學(xué)不僅限于學(xué)習(xí)數(shù)學(xué)知識(shí)，更重要的還在于學(xué)習(xí)數(shù)學(xué)思維方法。為了強(qiáng)化學(xué)生能力的訓(xùn)練,培養(yǎng)學(xué)生的抽象思維能力、邏輯推理能力、實(shí)際問(wèn)題的解決能力等,在保證作業(yè)數(shù)量的同時(shí),更要提高布置作業(yè)的質(zhì)量,增加典型簡(jiǎn)答題、討論題、推理題、實(shí)際應(yīng)用題等習(xí)題在作業(yè)中的分量,使學(xué)生在掌握各種基本知識(shí)和基本技能的同時(shí),提高自身的綜合能力。
認(rèn)真檢查和批改作業(yè),是督促學(xué)生學(xué)習(xí)的主要途徑,也是教師了解學(xué)生理解和掌握所學(xué)課程情況的主渠道。必要時(shí),教師可以批改一部分作業(yè),其他作業(yè)讓同學(xué)們之間互相檢查和批改,不僅可以督促學(xué)生學(xué)習(xí),更能讓學(xué)生在批改其他同學(xué)作業(yè)時(shí)逐步認(rèn)識(shí)到自身的缺陷和不足,以備今后更有針對(duì)性地學(xué)習(xí)。
教師在作業(yè)檢查和批改過(guò)程中發(fā)現(xiàn)的主要問(wèn)題和疑難以及學(xué)生提出的有代表性的問(wèn)題,有必要安排習(xí)題課進(jìn)行講解,幫助學(xué)生對(duì)解決疑難,加深對(duì)所知識(shí)的理解。對(duì)于學(xué)生比較爭(zhēng)論的問(wèn)題,可以展開(kāi)討論,鼓勵(lì)學(xué)生大膽發(fā)言,培養(yǎng)學(xué)生探索未知的精神和創(chuàng)造性解決實(shí)際問(wèn)題的能力。
四、總結(jié)
從此上看，上好離散數(shù)學(xué)課,關(guān)鍵是根據(jù)學(xué)生具體實(shí)際,有針
對(duì)性地安排教學(xué)內(nèi)容,合理使用教學(xué)方式方法,最大限度地激發(fā)學(xué)生的學(xué)習(xí)興趣,充分發(fā)揮教師的主導(dǎo)作用和學(xué)生的主體作用,達(dá)到教與學(xué)和諧。
參考文獻(xiàn)
[1] 屈婉玲,耿素云,張立昂.離散數(shù)學(xué)[M].北京:高等教育出版社.2008.[2] 黃巍,金國(guó)祥.”離散數(shù)學(xué)”課程教學(xué)改革的探討[J].中國(guó)電力教育,2009(8):82-83.[3] 周小燕,胡豐華.對(duì)提高離散數(shù)學(xué)教學(xué)質(zhì)量的探討[J].浙江科技學(xué)院學(xué)報(bào),2007,19(2):156-158.[4] 龍浩,張佳佳.怎樣教好《離散數(shù)學(xué)》課[J].貴陽(yáng)學(xué)院學(xué)報(bào),2007,2(1):53-57.[5] 廖仲春.離散數(shù)學(xué)的教學(xué)探討[J].湖南工業(yè)職業(yè)技術(shù)學(xué)院學(xué)報(bào),2008,8(5)http://
第四篇：離散數(shù)學(xué)
離散數(shù)學(xué)試題（A卷答案）
一、（10分）
（1）證明(P?Q)∧(Q?R)?(P?R)（2）求(P∨Q)?R的主析取范式與主合取范式，并寫(xiě)出其相應(yīng)的成真賦值和成假賦值。解：（1）因?yàn)?(P?Q)∧(Q?R))?(P?R)??((?P∨Q)∧(?Q∨R))∨(?P∨R)?(P∧?Q)∨(Q∧?R)∨?P∨R ?(P∧?Q)∨((Q∨?P∨R)∧(?R∨?P∨R))?(P∧?Q)∨(Q∨?P∨R)?(P∨Q∨?P∨R)∧(?Q∨Q∨?P∨R)?T 所以，(P?Q)∧(Q?R)?(P?R)。
（2）(P∨Q)?R??(P∨Q)∨R?(?P∧?Q)∨R ?(?P∨(Q∧?Q)∨R)∧((P∧?P)∨?Q∨R)?(?P∨Q∨R)∧(?P∨?Q∨R)∧(P∨?Q∨R)∧(?P∨?Q∨R)?M2∧M4∧M6 ?m0∨m1∨m3∨m5
所以，其相應(yīng)的成真賦值為000、001、011、101、111：成假賦值為：010、100、110。
二、（10分）分別找出使公式?x(P(x)??y(Q(y)∧R(x，y)))為真的解釋和為假的解釋。
解：設(shè)論域?yàn)閧1，2}。
若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，則 ?x(P(x)??y(Q(y)∧R(x，y)))??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))?(T?((F∧F)∨(F∧F)))∧(T?((F∧F)∨(F∧F)))?(T?F)∧(T?F)?F 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，則 ?x(P(x)??y(Q(y)∧R(x，y)))??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))?(T?((T∧T)∨(T∧T)))∧(T?((T∧T)∨(T∧T)))?(T?T)∧(T?T)?T
三、（10分）
在謂詞邏輯中構(gòu)造下面推理的證明：每個(gè)喜歡步行的人都不喜歡做汽車(chē)，每個(gè)人或者喜歡坐汽車(chē)或者喜歡騎自行車(chē)。有的人不喜歡騎自行車(chē)，因而有的人不喜歡步行。
解
論域：所有人的集合。A(x)：x喜歡步行；B(x)：x喜歡坐汽車(chē)；C(x)：x喜歡騎自行車(chē)；則推理化形式為：
?x(A(x)??B(x))，?x(B(x)∨C(x))，??xC(x)?x?A(x)下面給出證明：(1)??xC(x)
P(2)?x?C(x)
T(1)，E(3)?C(c)
T(2)，ES(4)?x(B(x)∨C(x))
P(5)B(c)∨C(c)
T(4)，US(6)B(c)
T(3)(5)，I(7)?x(A(x)??B(x))
P(8)A(c)??B(c)
T(7)，US(9)?A(c)
T(6)(8)，I(10)?x?A(x)
T(9)，EG
四、（10分）
下列論斷是否正確？為什么？(1)若A∪B＝A∪C，則B＝C。(2)若A∩B＝A∩C，則B＝C。(3)若A?B＝A?C，則B＝C。
解(1)不一定。例如，令A(yù)＝{1}，B＝{1，2}，C＝{2}，則A∪B＝A∪C，但B＝C不成立。(2)不一定。例如，令A(yù)＝{1}，B＝{1，2}，C＝{1，3}，則A∩B＝A∩C，但B＝C不成立。(3)成立。因?yàn)槿鬉?B＝A?C，對(duì)任意的x∈B，當(dāng)x∈A時(shí)，有x∈A∩B?x?A?B?x?A?C＝(A∪C)－(A∩C)?x∈A∩C?x∈C，所以B?C；當(dāng)x?A時(shí)，有x?A∩B，而x∈B?x∈A∪B，所以x∈A∪B－A∩B＝A?B?x∈A?C，但x? A，于是x∈C，所以B?C。
同理可證，C ?B。
因此，當(dāng)A?B＝A?C時(shí)，必有B＝C。
五、（10分）若R是集合A上的自反和傳遞關(guān)系，則對(duì)任意的正整數(shù)n，R＝R。
證明 當(dāng)n＝1時(shí)，結(jié)論顯然成立。設(shè)n＝k時(shí)，Rk＝R。當(dāng)n＝k＋1時(shí)，Rk+1＝Rk*R＝R*R。下面由R是自反和傳遞的推導(dǎo)出R*R＝R即可。
由傳遞性得R*R?R。另一方面，對(duì)任意的
由數(shù)學(xué)歸納法知，對(duì)任意的正整數(shù)n，Rn＝R。
n
六、（15分）設(shè)函數(shù)f：R×R?R×R，f定義為：f(
(1)證明f是單射。(2)證明f是滿射。(3)求逆函數(shù)f。
(4)求復(fù)合函數(shù)f－1?f和f?f。
證明(1)對(duì)任意的x，y，x1，y1∈R，若f(
(2)對(duì)任意的
1，y＝
u?w2，則f(
u?w2＋
u?w2，u?w2－>＝
u?w2－1(3)f(
x?y?x?y2x?y?(x?y)2(4)f?f(
七、（15分）設(shè)X＝{1，2，3，4}，R是X上的二元關(guān)系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫(huà)出R的關(guān)系圖。(2)寫(xiě)出R的關(guān)系矩陣。
(3)說(shuō)明R是否是自反、反自反、對(duì)稱(chēng)、傳遞的。解(1)R的關(guān)系圖如圖所示：(2)R的關(guān)系矩陣為：
?1??0M(R)??1??1?101110110??0? 0??0??(3)對(duì)于R的關(guān)系矩陣，由于對(duì)角線上不全為1，R不是自反的；由于對(duì)角線上存在非0元，R不是反自反的；由于矩陣不對(duì)稱(chēng)，R不是對(duì)稱(chēng)的；
經(jīng)過(guò)計(jì)算可得 ?1??02M(R)??1??1?101110110??0??M(R)，所以R是傳遞的。?0?0??
八、（10分）若
對(duì)于任意的a、b∈H，有a*b＝a*(b)∈H，即a*b∈H。又因?yàn)镠是G非空子集，所以*在H上滿足結(jié)合律。綜上可知，
九、（10分）給定二部圖G＝
證明 設(shè)|V1|＝m1，則|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m22
2－
1－1
－1
m12。因?yàn)?m2?m1)2?0，即4?mm1?m1，所以n≤m2/4。離散數(shù)學(xué)試題（B卷答案）
一、（20分）用公式法判斷下列公式的類(lèi)型：(1)(?P∨?Q)?(P??Q)(2)(P?Q)?(P∧?(Q∨?R))解：（1）因?yàn)??P∨?Q)?(P??Q)??(?P∨?Q)∨(P∧?Q)∨(?P∧Q)
?(P∧Q)∨(P∧?Q)∨(?P∧Q)?m1∨m2∨m3 ?M0
所以，公式(?P∨?Q)?(P??Q)為可滿足式。
（2）因?yàn)?P?Q)?(P∧?(Q∨?R))??(?(P∨Q))∨(P∧?Q∧R))
?(P∨Q)∨(P∧?Q∧R))
?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R)?(P∨Q)∧(P∨Q∨R)
?(P∨Q∨(R∧?R))∧(P∨Q∨R)?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)?M0∧M1
?m2∨m3∨m4∨m5∨m6∨m7
所以，公式(P?Q)?(P∧?(Q∨?R))為可滿足式。
二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：每個(gè)科學(xué)家都是勤奮的，每個(gè)勤奮又身體健康的人在事業(yè)中都會(huì)獲得成功。存在著身體健康的科學(xué)家。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。
Q(x)：x是勤奮的；x是科學(xué)家；C(x)：解：論域：所有人的集合。H(x)：x是身體健康的；S(x)：x是事業(yè)獲得成功的人；F(x)：x是事業(yè)半途而廢的人；則推理化形式為：
?x(S(x)?Q(x))，?x(Q(x)∧H(x)?C(x))，?x(S(x)∧H(x))
?x(C(x)∨F(x))下面給出證明：
(1)?x(S(x)∧H(x))
P(2)S(a)∧H(a)
T(1)，ES(3)?x(S(x)?Q(x))
P(4)S(a)?Q(a)
T(1)，US(5)S(a)
T(2)，I(6)Q(a)
T(4)(5)，I(7)H(a)
T(2)，I(8)Q(a)∧H(a)
T(6)(7)，I(9)?x(Q(x)∧H(x)?C(x))
P(10)Q(a)∧H(a)?C(a)
T(9)，Us(11)C(a)
T(8)(10)，I(12)?xC(x)
T(11)，EG(13)?x(C(x)∨F(x))
T(12)，I
三、（10分）設(shè)A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。解
P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}}
四、（15分）設(shè)R和S是集合A上的任意關(guān)系，判斷下列命題是否成立？(1)若R和S是自反的，則R*S也是自反的。(2)若R和S是反自反的，則R*S也是反自反的。(3)若R和S是對(duì)稱(chēng)的，則R*S也是對(duì)稱(chēng)的。(4)若R和S是傳遞的，則R*S也是傳遞的。(5)若R和S是自反的，則R∩S是自反的。(6)若R和S是傳遞的，則R∪S是傳遞的。
解
(1)成立。對(duì)任意的a∈A，因?yàn)镽和S是自反的，則
(2)不成立。例如，令A(yù)＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，則R和S是反自反的，但R*S＝{<1，1>}不是反自反的。
(3)不成立。例如，令A(yù)＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，則R和S是對(duì)稱(chēng)的，但R*S＝{<1，3>，<3，2>}不是對(duì)稱(chēng)的。
(4)不成立。例如，令A(yù)＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，則R和S是傳遞的，但R*S＝{<1，3>，<1，1>，<2，1>}不是傳遞的。
(5)成立。對(duì)任意的a∈A，因?yàn)镽和S是自反的，則
五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。問(wèn)(1)有多少個(gè)不同的由X到Y(jié)的函數(shù)？
(2)當(dāng)n、m滿足什么條件時(shí)，存在單射，且有多少個(gè)不同的單射？(3)當(dāng)n、m滿足什么條件時(shí)，存在雙射，且有多少個(gè)不同的雙射？
解
(1)由于對(duì)X中每個(gè)元素可以取Y中任一元素與其對(duì)應(yīng)，每個(gè)元素有n種取法，所以不同的函數(shù)共n個(gè)。
(2)顯然當(dāng)|m|≤|n|時(shí)，存在單射。由于在Y中任選m個(gè)元素的任一全排列都形成X到Y(jié)的不同的單射，故不同的單射有Cnm!＝n(n－1)(n―m―1)個(gè)。
(3)顯然當(dāng)|m|＝|n|時(shí)，才存在雙射。此時(shí)Y中元素的任一不同的全排列都形成X到Y(jié)的不同的雙射，mm故不同的雙射有m!個(gè)。
六、（5分）集合X上有m個(gè)元素，集合Y上有n個(gè)元素，問(wèn)X到Y(jié)的二元關(guān)系總共有多少個(gè)？ 解
X到Y(jié)的不同的二元關(guān)系對(duì)應(yīng)X×Y的不同的子集，而X×Y的不同的子集共有個(gè)2mn，所以X到Y(jié)的二元關(guān)系總共有2mn個(gè)。
七、（10分）若
證明 設(shè)e是群
若x?∈G也是a*x＝b的解，則x?＝e*x?＝(a*a)*x?＝a*(a*x?)＝a*b＝x。所以，x＝a*b是a*x
－
1－1
－1
－1＝b的惟一解。
八、（10分）給定連通簡(jiǎn)單平面圖G＝
由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是?d(f)＝2|E|＝24。若存在f∈
f?FF，使得d(f)＞3，則3|F|＜2|E|＝24，于是|F|＜8，與|F|＝8矛盾。故對(duì)任意f∈F，d(f)＝3。
第五篇：離散數(shù)學(xué)
第一章
數(shù)學(xué)語(yǔ)言與證明方法
例1 設(shè)E={ x | x是北京某大學(xué)學(xué)生}, A,B,C,D是E的子集, A= { x | x是北京人}，B= { x | x是走讀生}, C= { x | x是數(shù)學(xué)系學(xué)生}，D= { x | x是喜歡聽(tīng)音樂(lè)的學(xué)生}.試描述下列各集合中學(xué)生的特征:
(A?D)? ~ C={ x | x是北京人或喜歡聽(tīng)音樂(lè),但不是數(shù)學(xué)系學(xué)生} ~ A?B={ x | x是外地走讀生}(A-B)? D={ x | x是北京住校生, 并且喜歡聽(tīng)音樂(lè)} ~ D ? ~ B={ x | x是不喜歡聽(tīng)音樂(lè)的住校生} 例3 證明:(1)A?B=B?A(交換律)證 ?x
x?A?B
? x?A?x?B
(并的定義)
?x?B?x?A
(邏輯演算的交換律)
?x?B?A
(并的定義)(2)A?(B?C)=(A?B)?(A?C)(分配律)證 ?x
x?A?(B?C)
? x?A?(x?B? x?C)
(并,交的定義)
?(x?A?x?B)?(x?A?x?C)
(邏輯演算的分配律)
?x?(A?B)?(A?C)
(并,交的定義)(3)A?E=E(零律)證 ?x
x?A?E
? x?A?x?E
(并的定義)
? x?A?1
(全集E的定義)
?1
(邏輯演算的零律)
?x?E
(全集E的定義)(4)A?E=A(同一律)證 ?x
x?A?E
? x?A?x?E
(交的定義)
? x?A?1
(全集E的定義)
? x?A
(邏輯演算的同一律)例4 證明 A?(A?B)=A（吸收律）證 利用例3證明的4條等式證明
A?(A?B)
=(A?E)?(A?B)
(同一律)
= A?(E?B)
(分配律)
= A?(B?E)
(交換律)
= A?E
(零律)
= A
(同一律)例5 證明(A-B)-C=(A-C)-(B-C)證
(A-C)-(B-C)
=(A ? ~C)? ~(B ? ~C)
(補(bǔ)交轉(zhuǎn)換律)
=(A ? ~C)?(~B ? ~~C)
(德摩根律)
=(A ? ~C)?(~B ? C)
(雙重否定律)
=(A ? ~C ? ~B)?(A ? ~C ? C)
(分配律)
=(A ? ~C ? ~B)?(A ? ?)
(矛盾律)
= A ? ~C ? ~B
(零律,同一律)
=(A ? ~B)? ~C
(交換律,結(jié)合律)
=(A – B)– C
(補(bǔ)交轉(zhuǎn)換律)例6 證明(A?B)?(A?C)=(B?C)(A?C))?((A?C)A 例7 設(shè)A,B為任意集合, 證明:(1)A?A?B 證 ?x x?A ? x?A?x?B
(附加律)
? x?A?B
(2)A?B?A
證 ?x x?A?B ? x?A?x?B
? x?A
(化簡(jiǎn)律)(3)A-B?A
證 ?x x?A-B ? x?A?x?B
? x?A
(化簡(jiǎn)律)(4)若A?B, 則P(A)?P(B)證 ?x x?P(A)? x?A
? x?B
(已知A?B)
? x?P(B)例8 證明 A?B=A?B-A?B.證
A?B=(A?~B)?(~A?B)
=(A?~A)?(A?B)?(~B?~A)?(~B?B)
=(A?B)?(~B?~A)
=(A?B)?~(A?B)
=A?B-A?B 例3 若A-B=A, 則A?B=?
證 用歸謬法, 假設(shè)A?B??, 則存在x,使得
x?A?B ? x?A?x?B ? x?A-B?x?B
(A-B=A)
? x?A?x?B?x?B ? x?B?x?B，矛盾 例4 證明
是無(wú)理數(shù)
證
假設(shè)
是有理數(shù), 存在正整數(shù)n,m, 使得
=m/n,不妨設(shè)m/n為既約分?jǐn)?shù).于是m=n, m2=2n2, m2是偶數(shù), 從而m是偶數(shù).設(shè)m=2k, 得(2k)2=2n2, n2=2k2, 這又得到n也 是偶數(shù), 與m/n為既約分?jǐn)?shù)矛盾.例6 對(duì)于每個(gè)正整數(shù)n, 存在n個(gè)連續(xù)的正合數(shù).證
令x=(n+1)!
則 x+2, x+3,…, x+n+1是n個(gè)連續(xù)的正合數(shù):
i | x+i，i=2,3,…,n+1 例7 判斷下述命題是真是假:
若A?B=A?C, 則B=C.解
反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有
A?B=A?C = {a,b} 但B?C, 故命題為假.例8 證明:對(duì)所有n?1, 1+2+ … +n=n(n+1)/2 證
歸納基礎(chǔ).當(dāng)n=1時(shí), 1=1?(1+1)/2, 結(jié)論成立.歸納步驟.假設(shè)對(duì)n?1結(jié)論成立, 則有
1+2+ … +n +(n+1)=n(n+1)/2 +(n+1)
(歸納假設(shè))
=(n+1)(n+2)/2 得證當(dāng)n+1時(shí)結(jié)論也成立.例9 任何大于等于2的整數(shù)均可表成素?cái)?shù)的乘積 證 歸納基礎(chǔ).對(duì)于2, 結(jié)論顯然成立.歸納步驟.假設(shè)對(duì)所有的k(2?k?n)結(jié)論成立, 要證結(jié)論 對(duì)n+1也成立.若n+1是素?cái)?shù), 則結(jié)論成立;否則n+1=ab, 2?a,b 命題邏輯 例1 下列句子中那些是命題？ (1)北京是中華人民共和國(guó)的首都.(2)2 + 5 ＝8.(3)x + 5 ＞ 3.(4)你會(huì)開(kāi)車(chē)嗎？ (5)2050年元旦北京是晴天.(6)這只兔子跑得真快呀！(7)請(qǐng)關(guān)上門(mén)！(8)我正在說(shuō)謊話.(1),(2),(5)是命題,(3),(4),(6)~(8)都不是命題 例2 將下列命題符號(hào)化.(1)王曉既用功又聰明.(2)王曉不僅聰明，而且用功.(3)王曉雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學(xué).解 (1)p∧q (2)p∧q (3)p∧?q(4)記 r:張輝是三好生, s:王麗是三好生，r∧s(5)簡(jiǎn)單命題，記 t:張輝與王麗是同學(xué) 例3 將下列命題符號(hào)化(1)2或4是素?cái)?shù).(2)2或3是素?cái)?shù).(3)4或6是素?cái)?shù).(4)元元只能拿一個(gè)蘋(píng)果或一個(gè)梨.(5)王曉紅生于1975年或1976年.解 (1)p∨r, 真值:1(2) p∨q, 真值: 1(3)r∨s,真值: 0(4)記t:元元拿一個(gè)蘋(píng)果,u:元元拿一個(gè)梨 (t∧?u)∨(?t∧u)(5)記v:王曉紅生于1975年,w:王曉紅生于1976年 (v∧?w)∨(?v∧w)又可形式化為 v∨w 例4 設(shè)p:天冷, q:小王穿羽絨服，將下列命題符號(hào)化 (1)只要天冷，小王就穿羽絨服.p?q(2)因?yàn)樘炖洌孕⊥醮┯鸾q服.p?q (3)若小王不穿羽絨服，則天不冷.?q??p 或 p?q(4)只有天冷，小王才穿羽絨服.q?p(5)除非天冷，小王才穿羽絨服.q?p(6)除非小王穿羽絨服，否則天不冷.p?q (7)如果天不冷，則小王不穿羽絨服.?p??q 或 q?p(8)小王穿羽絨服僅當(dāng)天冷的時(shí)候.q?p 例5 求下列復(fù)合命題的真值 (1)2+2＝4 當(dāng)且僅當(dāng) 3+3＝6.(2)2+2＝4 當(dāng)且僅當(dāng) 3是偶數(shù).0(3)2+2＝4 當(dāng)且僅當(dāng) 太陽(yáng)從東方升起.(4)2+2＝5 當(dāng)且僅當(dāng) 美國(guó)位于非洲.(5)f(x)在x0處可導(dǎo)的充要條件是它在 x0處連續(xù).0 例6 公式A=(? p1? ? p2? ? p3)?(p1? p2) 000是成真賦值，001是成假賦值 公式B=(p?q)?r 000是成假賦值，001是成真賦值 例3 證明 p?(q?r)?(p?q)?r 證 p?(q?r) ? ?p?(?q?r) （蘊(yùn)涵等值式） ?(?p??q)?r （結(jié)合律） ? ?(p?q)?r （德摩根律） ?(p?q)?r （蘊(yùn)涵等值式 例4 證明: p?(q?r) (p?q)?r 方法一 真值表法（見(jiàn)例2） 方法二 觀察法.容易看出000使左邊成真, 使右邊成假.方法三 先用等值演算化簡(jiǎn)公式, 再觀察.例5 用等值演算法判斷下列公式的類(lèi)型(1)q??(p?q)解 q??(p?q) ? q??(?p?q) （蘊(yùn)涵等值式） ? q?(p??q) （德摩根律） ? p?(q??q) （交換律，結(jié)合律） ? p?0 （矛盾律） ? 0 （零律）該式為矛盾式.(2)(p?q)?(?q??p)解 (p?q)?(?q??p) ?(?p?q)?(q??p) （蘊(yùn)涵等值式） ?(?p?q)?(?p?q) （交換律） ? 1 該式為重言式.(3)((p?q)?(p??q))?r) 解 ((p?q)?(p??q))?r) ?(p?(q??q))?r （分配律） ? p?1?r （排中律） ? p?r （同一律） 非重言式的可滿足式.如101是它的成真賦值,000是它的 成假賦值.例1 求?(p?q)??r 的析取范式與合取范式 解 ?(p?q)??r ? ?(?p?q)??r ?(p??q)??r 析取范式 ?(p??r)?(?q??r) 合取范式 注意: 公式的析取范式與合取范式不惟一.例1(續(xù))求?(p?q)??r 的主析取范式與主合取范式 解(1)?(p?q)??r ?(p??q)??r p??q ?(p??q)?1 同一律 ?(p??q)?(?r?r) 排中律 ?(p??q??r)?(p??q?r) 分配律 ? m4?m5 ?r ?(?p?p)?(?q?q)??r 同一律, 排中律 ?(?p??q??r)?(?p?q??r)?(p??q??r)?(p?q??r) ? m0? m2? m4? m6 得 ?(p?q)??r ? m0? m2? m4 ?m5 ? m6 可記作 ? ?(0,2,4,5,6)(2)?(p?q)??r ?(p??r)?(?q??r) p??r ? p?0??r 同一律 ? p?(q??q)??r 矛盾律 分配律 ?(p?q??r)?(p??q??r) 分配律 ? M1?M3 ?q??r ?(p??p)??q??r 同一律, 矛盾律 ?(p??q??r)?(?p??q??r) 分配律 ? M3?M7 得 ?(p?q)??r ? M1?M3?M7 可記作 ? ?(1,3,7)例2(1)求 A ?(?p?q)?(?p??q?r)?r的主析取范式 解 用快速求法 (1)?p?q ?(?p?q??r)?(?p?q?r)? m2? m3 ?p??q?r ? m1 r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1? m3? m5? m7 得 A? m1? m2? m3? m5? m7 ? ?(1,2,3,5,7)(2)求 B? ?p?(p?q??r)的主合取范式 解 ?p ?(?p?q?r)?(?p?q??r)?(?p??q?r)?(?p??q??r) ? M4?M5?M6?M7 p?q??r ? M1 得 B? M1?M4?M5?M6?M7 ? ?(1,4,5,6,7)例3 用主析取范式判斷公式的類(lèi)型:(1)A? ?(p?q)?q (2)B? p?(p?q) (3)C?(p?q)?r 解(1)A ? ?(? p?q)?q ?(p??q)?q ? 0 矛盾式(2)B ? ? p?(p?q)? 1 ? m0?m1?m2?m3 重言式(3)C ? ?(p?q)?r ?(?p??q)?r ?(?p??q?r)?(?p??q??r)?(?p??q?r) ?(?p?q?r)?(p??q?r)?(p?q?r) ? m0?m1?m3? m5?m7 非重言式的可滿足式 例4 用主析取范式判斷下面2組公式是否等值:(1)p與(?p?q)?(p?q)解 p ? p?(?q?q)?(p??q)?(p?q)? m2?m3 (?p?q)?(p?q)? ?(?p?q)?(p?q) ?(p??q)?(p?q)? m2?m3 故 p ?(?p?q)?(p?q)(2)(p?q)?r 與 p?(q?r)解(p?q)?r ?(p?q??r)?(p?q?r) ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1?m3?m5? m6?m7 p?(q?r)?(p?q)?(p? r) ?(p?q??r)?(p?q?r)?(p??q?r)?(p?q?r) ? m5? m6?m7 故 (p?q)?r p?(q?r)例5 某單位要從A,B,C三人中選派若干人出國(guó)考察, 需滿 足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問(wèn)有幾種可能的選派方案? 解 記p:派A去, q:派B去, r:派C去 (1)p?r，(2)q??r，(3)(p??q)?(?p?q)求下式的成真賦值 A=(p?r)?(q??r)?((p??q)?(?p?q))例6 求A=(?p??q?r)?(?p?q?r)?(p?q?r)的主合取范式 解 A ? m1?m3?m7 ? M0?M2?M4?M5?M6 例1 判斷下面推理是否正確:(1)若今天是1號(hào), 則明天是5號(hào).今天是1號(hào).所以, 明天是5號(hào).解 設(shè) p: 今天是1號(hào), q: 明天是5號(hào) 推理的形式結(jié)構(gòu)為 (p?q)ùp?q 證明 用等值演算法 (p?q)ùp?q ? ?((?púq)ùp)úq ?((pù?q)ú?p)úq ? ?pú?qúq ? 1 得證推理正確 (2)若今天是1號(hào), 則明天是5號(hào).明天是5號(hào).所以, 今天是1號(hào).解 設(shè)p: 今天是1號(hào), q: 明天是5號(hào).推理的形式結(jié)構(gòu)為 (p?q)ùq?p 證明 用主析取范式法 (p?q)ùq?p ?(?púq)ùq?p ? ?((?púq)ùq)úp ? ?qúp ?(?pù?q)ú(pù?q)ú(pù?q)ú(pùq) ? m0úm2úm3 01是成假賦值, 所以推理不正確.例2 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明: 前提: púq, q?r, p?s, ?s 結(jié)論: rù(púq)證明 ① p?s 前提引入 ② ? s 前提引入 ③ ? p ①②拒取式 ④ púq 前提引入 ⑤ q ③④析取三段論 ⑥ q?r 前提引入 ⑦ r ⑤⑥假言推理 ⑧ rù(púq) ⑦④合取 推理正確, rù(púq)是有效結(jié)論 例3 構(gòu)造推理的證明: 若明天是星期一或星期三, 我就有 課.若有課, 今天必需備課.我今天下午沒(méi)備課.所以, 明天 不是星期一和星期三.解 設(shè) p:明天是星期一, q:明天是星期三，r:我有課，s:我備課 前提:(púq)?r, r?s, ?s 結(jié)論: ?pù?q 例4 構(gòu)造下面推理的證明: 前提: ?púq, ?qúr, r?s 結(jié)論: p?s 證明 ① p 附加前提引入 ② ?púq 前提引入 ③ q ①②析取三段論 ④ ?qúr 前提引入 ⑤ r ③④析取三段論 ⑥ r?s 前提引入 ⑦ s ⑤⑥假言推理 推理正確, p?s是有效結(jié)論 例5 構(gòu)造下面推理的證明 前提: ?(pùq)úr, r?s, ?s, p 結(jié)論: ?q 證明 用歸繆法 ① q 結(jié)論否定引入 ② r?s 前提引入 ③ ?s 前提引入 ④ ?r ②③拒取式 ⑤ ?(pùq)úr 前提引入 ⑥ ?(pùq) ④⑤析取三段論 ⑦ ?pú?q ⑥置換 ⑧ ?p ①⑦析取三段論 ⑨ p 前提引入 ⑩ ?pùp ⑧⑨合取 推理正確, ?q是有效結(jié)論 例6 用歸結(jié)證明法構(gòu)造下面推理的證明: 前提:(p?q)?r, r?s, ?s 結(jié)論:(p?q)?(pùs)解 (p?q)?r ? ?(?púq)úr ?(pù?q)úr ?(púr)ù(?qúr) r?s ? ?rús ? (p?q)?(pùs)? ?(?púq)ú(pùs)?(pù?q)ú(pùs)? ? pù(?qús)推理可表成 前提: púr, ?qúr, ?rús, ?s 結(jié)論: pù(?qús) 第3章 一階邏輯 例1(1)4是偶數(shù) 4是個(gè)體常項(xiàng), “是偶數(shù)”是謂詞常項(xiàng), 符號(hào)化為: F(4)(2)小王和小李同歲 小王, 小李是個(gè)體常項(xiàng), 同歲是謂詞常項(xiàng).記a:小王，b: 小李, G(x,y): x與y同歲, 符號(hào)化為: G(a,b)(3)x< y x,y是命題變項(xiàng), < 是謂詞常項(xiàng), 符號(hào)化為: L(x,y)(4)x具有某種性質(zhì)P x是命題變項(xiàng), P是謂詞變項(xiàng), 符號(hào)化為: P(x)例2 將下述命題用0元謂詞符號(hào)化, 并討論它們的真值:(1) 是無(wú)理數(shù), 而 是有理數(shù)(2)如果2>3，則3<4 解 (1)設(shè)F(x): x是無(wú)理數(shù), G(x): x是有理數(shù) 符號(hào)化為 真值為0(2)設(shè) F(x,y): x>y, G(x,y): x 個(gè)體域分別取(a)人類(lèi)集合,(b)全總個(gè)體域.解:(a)(1)設(shè)F(x): x愛(ài)美，符號(hào)化為 ?x F(x) (2)設(shè)G(x): x用左手寫(xiě)字，符號(hào)化為 ?x G(x) (b)設(shè)M(x): x為人，F(xiàn)(x), G(x)同(a)中 (1)?x(M(x)?F(x)) (2)? x(M(x)?G(x))M(x)稱(chēng)作特性謂詞 例4 將下列命題符號(hào)化, 并討論其真值:(1)對(duì)任意的x, 均有x2-3x+2=(x-1)(x-2)(2)存在x, 使得x+5=3 分別取(a)個(gè)體域D1=N,(b)個(gè)體域D2=R 解 記F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3(a)(1)?x F(x) 真值為1 (2)?x G(x) 真值為0(b)(1)?x F(x) 真值為1 (2)?x G(x) 真值為1 例5 將下面命題符號(hào)化:(1)兔子比烏龜跑得快 (2)有的兔子比所有的烏龜跑得快(3)并不是所有的兔子都比烏龜跑得快(4)不存在跑得一樣快的兔子和烏龜 解 用全總個(gè)體域，令F(x): x是兔子, G(y): y是烏龜，H(x,y): x比y跑得快，L(x,y): x和y跑得一樣快(1)?x?y(F(x)?G(y)?H(x,y))(2)?x(F(x)?(?y(G(y)?H(x,y)))(3)? ?x?y(F(x)?G(y)?H(x,y))(4)? ?x?y(F(x)?G(y)?L(x,y))例6 公式 ?x(F(x,y)??yG(x,y,z))?x的轄域:(F(x,y)??yG(x,y,z))，指導(dǎo)變?cè)獮閤 ?y的轄域:G(x,y,z)，指導(dǎo)變?cè)獮閥 x的兩次出現(xiàn)均為約束出現(xiàn) y的第一次出現(xiàn)為自由出現(xiàn), 第二次出現(xiàn)為約束出現(xiàn) z為自由出現(xiàn).例7 公式 ?x(F(x)??xG(x))?x的轄域:(F(x)??xG(x))，指導(dǎo)變?cè)獮閤 ?x的轄域:G(x)，指導(dǎo)變?cè)獮閤 x的兩次出現(xiàn)均為約束出現(xiàn).但是, 第一次出現(xiàn)的x是?x中 的x, 第二次出現(xiàn)的x是?x中的x.例8 給定解釋I 如下: (a)個(gè)體域 D=N (b) (c) (d)謂詞 說(shuō)明下列公式在 I 下的含義, 并討論其真值 (1)?xF(g(x,a),x)?x(2x=x) 假命題 (2)?x?y(F(f(x,a),y)?F(f(y,a),x))?x?y(x+2=y?y+2=x) 假命題(3)?x?y?zF(f(x,y),z) ?x?y?z(x+y=z) 真命題 (4)?xF(f(x,x),g(x,x)) ?x(2x=x2) 真命題(5)F(f(x,a), g(x,a))x+2=2x 不是命題 (6)?x(F(x,y)?F(f(x,a), f(y,a)))?x(x=y?x+2=y+2) 真命題 例8(1)~(4)都是閉式, 在I下全是命題.(5)和(6)不是閉式, 在I下(5)不是命題,(6)是命題 例9 判斷下列公式的類(lèi)型:(1)?x(F(x)?G(x))取解釋I1, D1=R，:x是整數(shù)，:x是有理數(shù), 取解釋I2, D2=R，:x是整數(shù)，:x是自然數(shù), 非永真式的可滿足式(2)?(?xF(x))?(?xF(x)) 這是 ?p?p 的代換實(shí)例, ?p?p是重言式，永真式(3)?(?xF(x)??yG(y))? ?yG(y)這是?(p?q)?q的代換實(shí)例, ?(p?q)?q是矛盾式 矛盾式 例1 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個(gè)體變項(xiàng) 真命題 假命題 (1)?xF(x,y,z)? ?yG(x,y,z)? ?uF(u,y,z)? ?yG(x,y,z) 換名規(guī)則 ? ?uF(u,y,z)? ?vG(x,v,z) 換名規(guī)則 或者 ? ?xF(x,u,z)? ?yG(x,y,z) 代替規(guī)則 ? ?xF(x,u,z)? ?yG(v,y,z) 代替規(guī)則(2)?x(F(x,y)? ?yG(x,y,z))? ?x(F(x,y)? ?tG(x,t,z)) 換名規(guī)則 或者 ? ?x(F(x,t)? ?yG(x,y,z)) 代替規(guī)則 例2 設(shè)個(gè)體域D={a,b,c}, 消去下面公式中的量詞:(1)?x(F(x)?G(x))?(F(a)?G(a))?(F(b)?G(b))?(F(c)?G(c))(2)?x(F(x)??yG(y))? ?xF(x)??yG(y) 量詞轄域收縮 ?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))(3)?x?yF(x,y)? ?x(F(x,a)?F(x,b)?F(x,c))?(F(a,a)?F(a,b)?F(a,c))?(F(b,a)?F(b,b)?F(b,c)) ?(F(c,a)?F(c,b)?F(c,c))例3 給定解釋I:(a)D={2,3},(b) (c) :x是奇數(shù)，: x=2 ? y=2，: x=y.在I下求下列各式的真值:(1)?x(F(f(x))?G(x, f(x))) 解 (F(f(2))?G(2, f(2)))?(F(f(3))?G(3, f(3)))?(1?1)?(0?1)? 1(2)?x?yL(x,y)解 ?yL(2,y)??yL(3,y)?(L(2,2)?L(2,3))?(L(3,2)?L(3,3))?(1?0)?(0?1)? 0 例4 證明下列等值式: ? ?x(M(x)?F(x))? ?x(M(x)? ?F(x))證 左邊 ? ?x ?(M(x)?F(x)) 量詞否定等值式 ? ?x(?M(x)??F(x))? ?x(M(x)? ?F(x))例5 求公式的前束范式(1)?xF(x)???xG(x)解 ? ?xF(x)??x?G(x) 量詞否定等值式 ? ?x(F(x)??G(x)) 量詞分配等值式 解2 ? ?xF(x)???yG(y) 換名規(guī)則 ? ?xF(x)??y?G(y) 量詞否定等值式 ? ?x(F(x)??y?G(y)) 量詞轄域擴(kuò)張 ? ?x?y(F(x)??G(y)) 量詞轄域擴(kuò)張 第4章 關(guān)系 例1 <2,x+5>=<3y?4,y>，求 x, y.解 3y?4=2, x+5=y ? y=2, x= ?3 例2 A={0, 1}, B={a, b, c} A?B={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} B?A ={ A = {?}, B = ? P(A)?A = {, <{?},?>} P(A)?B = ? 例3 (1)R={ ={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>} (2)C={ R={ |A|=n, |B|=m, |A×B|=nm, A×B 的子集有 個(gè).所以從A到B有 元關(guān)系.|A|=n, A上有 不同的二元關(guān)系.例如 |A|=3, 則 A上有512個(gè)不同的二元關(guān)系.例 5A={a, b, c, d}, R={ ??1110??1000???0000???0100??例1 R={ domR = ranR = fldR = 例2 R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R?1 = R°S = S°R = 個(gè)不同的二 例3 設(shè)A = {a, b, c, d}, R = { ?0100??0100??01 ???1010??1010102???M?? M???0001??0001??00 ?????00000000???00?? 例1 A = {a, b, c}, R1, R2, R3 是 A上的關(guān)系, 其中 R1 = { 00??1?010????01??0??00??0010?101??000??000?R2自反, R3 反自反, R1既不自反也不反自反.例2 設(shè)A＝{a,b,c}, R1, R2, R3和R4都是A上的關(guān)系, 其中 R1＝{ R1＝{ R2＝{ R3＝{ 證明若 IA ?R，則 R 在 A 上自反.證 任取x，x?A ? 因此 R 在 A 上是自反的.例5 證明若 R=R?1 , 則 R 在A上對(duì)稱(chēng).證 任取 因此 R 在 A 上是對(duì)稱(chēng)的.例6 證明若 R∩R?1?IA , 則 R 在 A 上反對(duì)稱(chēng).證 任取 ? 因此 R 在 A 上是反對(duì)稱(chēng)的.例7 證明若 R°R?R , 則 R 在 A 上傳遞.證 任取 因此 R 在 A 上是傳遞的.例8 判斷下圖中關(guān)系的性質(zhì), 并說(shuō)明理由 (1)不自反也不反自反；對(duì)稱(chēng), 不反對(duì)稱(chēng)；不傳遞.(2)反自反, 不是自反；反對(duì)稱(chēng), 不是對(duì)稱(chēng)；傳遞.(3)自反，不是反自反；反對(duì)稱(chēng)，不是對(duì)稱(chēng)；不傳遞.例1 設(shè)A={a,b,c,d}, R={ 例1 設(shè) A={1, 2, …, 8}, 如下定義 A上的關(guān)系R： R={ ?x?A, 有x≡x(mod 3) ?x,y?A, 若x≡y(mod 3), 則有y≡x(mod 3) ?x,y,z?A, 若x≡y(mod 3), y≡z(mod 3), 則有 x≡z(mod 3)例2 令A(yù)={1, 2, …, 8}，A關(guān)于模 3 等價(jià)關(guān)系R 的商集為 A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} } A關(guān)于恒等關(guān)系和全域關(guān)系的商集為： A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} } 例3 設(shè)A＝{a, b, c, d}, 給定? 1, ? 2, ? 3, ? 4, ? 5, ? 6如下： ? 1={{a, b, c},jdb3l39rxn9}，? 2={{a, b},{c},jdb3l39rxn9} ? 3={{a},{a, b, c, d}}，? 4={{a, b},{c}} ? 5={?,{a, b},{c, d}}，? 6={{a,{a}},{b, c, d}} 則? 1和? 2是A的劃分, 其他都不是A的劃分.例4 給出A＝{1,2,3}上所有的等價(jià)關(guān)系 求解思路：先做出A的所有劃分, 然后根據(jù)劃分寫(xiě)出 對(duì)應(yīng)的等價(jià)關(guān)系.A上的等價(jià)關(guān)系與劃 分之間的對(duì)應(yīng)： ? 4對(duì)應(yīng)于全域關(guān)系EA ? 5對(duì)應(yīng)于恒等關(guān)系IA ? 1, ? 2和? 3分別對(duì)應(yīng)于等價(jià)關(guān)系 R1, R2和R3.其中 R1={<2,3>,<3,2>}∪IA R2={<1,3>,<3,1>}∪IA R3={<1,2>,<2,1>}∪IA 例5 設(shè)A={1,2,3,4}，在A?A上定義二元關(guān)系 R： < A?A={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>，<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>，<4,4>} 根據(jù)有序?qū)?x,y>的 x+y=2,3,4,5,6,7,8 將A?A劃分.(A?A)/R={{<1,1>}, {<1,2>,<2,1>}, {<1,3>, <2,2>, <3,1>}，{<1,4>, <2,3>, <3,2>, <4,1>}, {<2,4>, <3,3>, <4,2>}，{<3,4>, <4,3>}, {<4,4>}} 例6 <{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除> 例7 已知偏序集 R={ 例8 設(shè)偏序集 例1 設(shè)A = {1, 2, 3}, B = {a, b}, 求BA.解BA = { f0, f1, … , f7 }, 其中 f0={<1,a>,<2,a>,<3,a>} f1={<1,a>,<2,a>,<3,b>} f2={<1,a>,<2,b>,<3,a>} f3={<1,a>,<2,b>,<3,b>} f4={<1,b>,<2,a>,<3,a>} f5={<1,b>,<2,a>,<3,b>} f6={<1,b>,<2,b>,<3,a>} f7={<1,b>,<2,b>,<3,b>} 例2 判斷下面函數(shù)是否為單射, 滿射, 雙射的, 為什么?（1）f : R→R, f(x)= ?x2+2x?1（2）f : Z+→R, f(x)=lnx, Z+為正整數(shù)集（3）f : R→Z, f(x)=?x?（4）f : R→R, f(x)=2x+1（5）f : R+→R+, f(x)=(x2+1)/x, 其中R+為正實(shí)數(shù)集.解(1)f : R→R, f(x)= ?x2+2x?1 在x=1取得極大值0.既不是單射也不是滿射的.(2)f : Z+→R, f(x)=lnx 單調(diào)上升, 是單射的.但不滿射, ranf={ln1, ln2, …}.(3)f : R→Z, f(x)= ?x? 是滿射的, 但不是單射的, 例如 f(1.5)=f(1.2)=1.(4)f : R→R, f(x)=2x+1 是滿射、單射、雙射的, 因?yàn)樗菃握{(diào)函數(shù)并且ranf=R.(5)f : R+→R+, f(x)=(x2+1)/x 有極小值f(1)=2.該函數(shù)既不是單射的也不是滿射的.例3 A=P({1,2,3}), B={0,1}{1,2,3} 解 A={?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={ f0, f1, … , f7 }, 其中 f0={<1,0>,<2,0>,<3,0>}，f1={<1,0>,<2,0>,<3,1>}, f2={<1,0>,<2,1>,<3,0>}，f3={<1,0>,<2,1>,<3,1>}，f4={<1,1>,<2,0>,<3,0>}，f5={<1,1>,<2,0>,<3,1>}，f6={<1,1>,<2,1>,<3,0>}，f7={<1,1>,<2,1>,<3,1>}.令 f : A→B，f(?)=f0, f({1})=f1, f({2})=f2, f({3})=f3，f({1,2})=f4, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f7 例4 A=[0,1] B=[1/4,1/2] 構(gòu)造雙射 f : A→B解 令 f : [0,1]→[1/4,1/2] f(x)=(x+1)/4 例5 A=Z, B=N，構(gòu)造雙射 f : A→B 將Z中元素以下列順序排列并與N中元素對(duì)應(yīng)： Z：0?11 ?22?33 … ↓ ↓ ↓ ↓ ↓ ↓ ↓ N：0 1 2 4 5 6 … 則這種對(duì)應(yīng)所表示的函數(shù)是： x?0?2xf:Z?N,f(x)????2x?1x?0例1 設(shè) f : R→R, g : R→R ?x2x?3f(x)?? x?3??2 g(x)?x?2 求 f °g, g°f.如果 f 和 g 存在反函數(shù), 求出它們的反函數(shù).解 f?g:R?R?x2?2x?3f?g(x)??x?3?0g?f:R?R?(x?2)2g?f(x)????2x?1x?1 f : R→R不存在反函數(shù)；g : R→R的反函數(shù)是 g?1: R→R, g?1(x)=x?2 第6章 圖 例1 下述2組數(shù)能成為無(wú)向圖的度數(shù)列嗎?(1)3,3,3,4;(2)1,2,2,3 解(1)不可能.有奇數(shù)個(gè)奇數(shù).(2)能 例2 已知圖G有10條邊, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小 于等于2, 問(wèn)G至少有多少個(gè)頂點(diǎn)? 解 設(shè)G有n個(gè)頂點(diǎn).由握手定理，4?3+2?(n-4)?2?10 解得 n?8 例3 已知5階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解 2,1,1,1,2 例4 證明不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的 多面體.證 用反證法.假設(shè)存在這樣的多面體, 作無(wú)向圖G= 討論所有可能的情況.設(shè)有a個(gè)5度頂點(diǎn)和b個(gè)6度頂點(diǎn)(1)a=0, b=9; (2)a=2, b=7;(3)a=4, b=5;(4)a=6, b=3;(5)a=8, b=1(1)~(3)至少5個(gè)6度頂點(diǎn),(4)和(5)至少6個(gè)5度頂點(diǎn) 方法二 假設(shè)b<5, 則a>9-5=4.由握手定理的推論, a ? 6 例6 畫(huà)出4階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖 解 總度數(shù)為6, 分配給4個(gè)頂點(diǎn), 最大度為3, 且奇度頂點(diǎn)數(shù) 為偶數(shù), 有下述3個(gè)度數(shù)列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,3 1,1,2,2 例7 畫(huà)出3個(gè)以1,1,1,2,2,3為度數(shù)列的非同構(gòu)的無(wú)向簡(jiǎn)單圖 0,2,2,2 例1 右圖有 個(gè)面 R1的邊界:a R2的邊界:bce R3的邊界:fg R0的邊界:abcdde, fg deg(R1)=1 deg(R2)=3 deg(R3)=2 deg(R0)=8 例2 右邊2個(gè)圖是同一平面圖的平面嵌入.R1在(1)中是外部面, 在(2)中是內(nèi)部面;R2在(1)中是內(nèi)部面, 在(2)中是外部面.R3 R1 R3 R2(1) R2 R1(2) 說(shuō)明:(1)一個(gè)平面圖可以有多個(gè)不同形式的平面嵌入, 它們都同構(gòu).(2)可以通過(guò)變換(測(cè)地投影法)把平面圖的任何一面作為外部面 例3 證明 K5 和 K3,3不是平面圖 證 K5 : n=5, m=10, l=3 K3,3 : n=6, m=9, l=4 不滿足定理6.15的條件 例 5證明下面2個(gè)圖均為非平面圖.與K3,3同胚也可收縮到K3,3 與K5同胚也可收縮到K5 例6 畫(huà)出所有非同構(gòu)的6階11條邊的簡(jiǎn)單連通非平面圖 解 在K5(5階10條邊)上加一個(gè)頂點(diǎn)和一條邊 在K3,3(6階9條邊)上加2條邊 例1 某中學(xué)有3個(gè)課外活動(dòng)小組:數(shù)學(xué)組, 計(jì)算機(jī)組和生物組.有趙,錢(qián),孫,李,周5名學(xué)生, 問(wèn)分別在下述3種情況下, 能否選出3人各任一個(gè)組的組長(zhǎng)?(1)趙, 錢(qián)為數(shù)學(xué)組成員, 趙,孫,李為計(jì)算機(jī)組成員, 孫,李,周為生物組成員.(2)趙為數(shù)學(xué)組成員, 錢(qián),孫,李為計(jì)算機(jī)組成員, 錢(qián),孫,李,周為生物組成員.(3)趙為數(shù)學(xué)組和計(jì)算機(jī)組成員, 錢(qián),孫,李,周為生物組成員.解 數(shù) 計(jì) 生 數(shù) 計(jì) 生 趙 錢(qián) 孫 李 周 趙 錢(qián) 孫 李 周 (1(數(shù) 計(jì) 生 趙 錢(qián) 孫 李 周 (3(1),(2)有多種方案,(3)不可能 例2 證明下述各圖不是哈密頓圖: (a(b(c) (c)中存在哈密頓通路 例3 證明右圖不是哈密頓圖 證 假設(shè)存在一條哈密頓回路, a,f,g是2度頂點(diǎn), 邊(a,c),(f,c)和(g,c)必在這條哈密頓回路上,從而點(diǎn)c出現(xiàn)3次, 矛盾.a b c f d e g 此外, 該圖滿足定理6.10的條件, 這表明此條件是必要、而不充分的.又, 該圖有哈密頓通路.例4 有7個(gè)人, A會(huì)講英語(yǔ), B會(huì)講英語(yǔ)和漢語(yǔ), C會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ), D會(huì)講日語(yǔ)和漢語(yǔ), E會(huì)講德語(yǔ)和意大利語(yǔ), F會(huì)講法語(yǔ)、日語(yǔ)和俄語(yǔ), G會(huì)講法語(yǔ)和德語(yǔ).問(wèn)能否將他們沿圓桌安排就坐成一圈, 使得每個(gè)人都能與兩旁的人交談? 解 作無(wú)向圖, 每人是一個(gè)頂點(diǎn), 2人之間有邊?他們有共同的語(yǔ)言.G F E D A B C ACEGFDBA是一條哈密頓回路,按此順序就坐即可.
點(diǎn)擊咨詢 