【正文】 x是兔子, G(y): y是烏龜，H(x,y): x比y跑得快，L(x,y): x和y跑得一樣快(1)xy(F(x)217。H(x,y))(2)$x(F(x)217。H(x,y)))(3)216。G(y)174。 $x$y(F(x)217。L(x,y))例6 公式 x(F(x,y)$174。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) 公式 x(F(x)$174。xG(x))，指導(dǎo)變?cè)獮閤 $x的轄域:G(x)，指導(dǎo)變?cè)獮閤 , 第一次出現(xiàn)的x是x中 的x, 第二次出現(xiàn)的x是$ 給定解釋I 如下:(a)個(gè)體域 D=N(b)(c)(d)謂詞說明下列公式在 I 下的含義, 并討論其真值(1)xF(g(x,a),x)x(2x=x)假命題(2)xy(F(f(x,a),y)174。y+2=x)假命題(3)xy$zF(f(x,y),z)xy$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)174。x+2=y+2)真命題例8(1)~(4)都是閉式, 在I下全是命題.(5)和(6)不是閉式, 在I下(5)不是命題,(6)是命題例9 判斷下列公式的類型:(1)x(F(x)174。(xF(x))218。p218。p218。(xF(x)$174。 $yG(y)這是216。q)217。(p174。q是矛盾式矛盾式 例1 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個(gè)體變項(xiàng)真命題 假命題(1)xF(x,y,z)174。 uF(u,y,z)174。 uF(u,y,z)174。 xF(x,u,z)174。 xF(x,u,z)174。 $yG(x,y,z))219。 $tG(x,t,z))換名規(guī)則或者 219。 $yG(x,y,z))代替規(guī)則 例2 設(shè)個(gè)體域D={a,b,c}, 消去下面公式中的量詞:(1)x(F(x)174。(F(a)174。(F(b)174。(F(c)174。yG(y))219。yG(y)量詞轄域收縮 219。F(b)217。(G(a)218。G(c))(3)$xyF(x,y)219。F(x,b)217。(F(a,a)217。F(a,c))218。F(b,b)217。(F(c,a)217。F(c,c))例3 給定解釋I:(a)D={2,3},(b)(c):x是奇數(shù)，: x=2 218。G(x, f(x)))解(F(f(2))217。(F(f(3))217。(1217。(0217。 1(2)$xyL(x,y)解yL(2,y)218。(L(2,2)217。(L(3,2)217。(1217。(0217。 0 例4 證明下列等值式:216。F(x))219。 216。 x 216。F(x))量詞否定等值式219。M(x)218。F(x))219。 216。217。 xF(x)217。G(x)量詞否定等值式 219。217。 xF(x)$216。yG(y)換名規(guī)則 219。y216。 x(F(x)217。G(y))量詞轄域擴(kuò)張 219。217。 y=2, x= 3 例2A={0, 1}, B={a, b, c}A180。A ={,}A = {198。P(A)180。B = 198。N, x+y={, , , , , }(2)C={ | x,y206。R, x+2y+z=3}， A={0,1}, B={1,2,3}，R1={}, R2=AB, R3=198。234。234。234。0000235。0100249。0100249。01 234。234。234。234。M=234。234。234。234。234。00000000235。235。233。010=234。234。234。235。101000000R，則 R 在 A 任取x，x206。 206。 206。R 222。R 1 222。R因此 R 在 A 證明若 R∩R1205。R 217。R 222。R 217。R 1222。R∩R 1 222。IA 222。R , 則 R 在 A 任取，206。206。 206。 206。,{a, b},{c, d}}，p 6={{a,{a}},{b, c, d}} 則p 1和p 2是A的劃分, 給出A＝{1,2,3}上所有的等價(jià)關(guān)系求解思路：先做出A的所有劃分, 然后根據(jù)劃分寫出 分之間的對(duì)應(yīng)：p 4對(duì)應(yīng)于全域關(guān)系EA p 5對(duì)應(yīng)于恒等關(guān)系IA p 1, p 2和p 3分別對(duì)應(yīng)于等價(jià)關(guān)系 R1, R1={,}∪IAR2={,}∪IAR3={,}∪IA 例5設(shè)A={1,2,3,4}，在A180。R 219。A={, , , , , , ，, , , , , , ，}根據(jù)有序?qū)Φ?x+y=2,3,4,5,6,7,8 將A180。A)/R={{}, {,}, {, , }，{, , , }, {, , }，{, }, {}}例6例7已知偏序集的哈斯圖如下圖所示, ={a, b, c, d, e, f, g, h}R={,，}∪IA例8 設(shè)偏序集如下圖所示，求A 的極小元、最小元、極大元、＝{ b, c, d }, 求B 的下界、上界、下 確界、：極小元：a, b, c, g；極大元：a, f, h；, 上界有d 和 f, 最小上界為 函數(shù)例1 設(shè)A = {1, 2, 3}, B = {a, b}, = { f0, f1, … , f7 }, 其中f0={,} f1={,} f2={,} f3={,} f4={,} f5={,} f6={,} f7={,} 例2判斷下面函數(shù)是否為單射, 滿射, 雙射的, 為什么?（1）f : R→R, f(x)= x2+2x1（2）f : Z+→R, f(x)=lnx, Z+為正整數(shù)集（3）f : R→Z, f(x)=235。（4）f : R→R, f(x)=2x+1（5）f : R+→R+, f(x)=(x2+1)/x, 其中R+(1)f : R→R, f(x)= x2+2x1在x=.(2)f : Z+→R, f(x)=lnx單調(diào)上升, , ranf={ln1, ln2, …}.(3)f : R→Z, f(x)= 235。是滿射的, 但不是單射的, 例如 f()=f()=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)=A=P({1,2,3}), B={0,1}{1,2,3} 解A={198。)=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 例4A=[0,1]B=[1/4,1/2] 構(gòu)造雙射 f : A→B解令f : [0,1]→[1/4,1/2]f(x)=(x+1)/4例5A=Z, B=N，構(gòu)造雙射 f : A→B將Z中元素以下列順序排列并與N中元素對(duì)應(yīng)： Z：0112233 …   ↓↓↓↓↓↓↓ N：0 1 2 4 5 6 … 則這種對(duì)應(yīng)所表示的函數(shù)是： x179。2xf:Z174。238。x2x179。 x3238。R236。3fog(x)=237。0gof:R174。(x+2)2gof(x)=237。2x179。(2)1,2,2,3解(1).(2)能例2 已知圖G有10條邊, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小 于等于2, 問G至少有多少個(gè)頂點(diǎn)? 解 ，4180。(n4)179。10 解得n179。V 217。 u185。V, d(v) 設(shè)9階無向圖的每個(gè)頂點(diǎn)的度數(shù)為5或6, 證明它至少有 (1)a=0, b=9。(3)a=4, b=5。(5)a=8, b=1(1)~(3)至少5個(gè)6度頂點(diǎn),(4)和(5)至少6個(gè)5度頂點(diǎn)方法二假設(shè)b95=, a 179。(2)1,1,2,2。R2在(1)中是內(nèi)部面, 在(2) R1 R3 R2(1)R2R1(2)說明:(1)一個(gè)平面圖可以有多個(gè)不同形式的平面嵌入, 它們都同構(gòu).(2)可以通過變換(測(cè)地投影法)把平面圖的任何一面作為外部面 例3 證明 K5 和 K3,3不是平面圖證 K5 : n=5, m=10, l=3K3,3 : n=6, m=9, l=4例,3同胚也可收縮到K3,3與K5同胚也可收縮到K5 例6 畫出所有非同構(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é)組, ,錢,孫,李,周5名學(xué)生, 問分別在下述3種情況下, 能否選出3人各任一個(gè)組的組長(zhǎng)?(1)趙, 錢為數(shù)學(xué)組成員, 趙,孫,李為計(jì)算機(jī)組成員, 孫,李,周為生物組成員.(2)趙為數(shù)學(xué)組成員, 錢,孫,李為計(jì)算機(jī)組成員, 錢,孫,李,周為生物組成員.(3)趙為數(shù)學(xué)組和計(jì)算機(jī)組成員, 錢,孫,李,數(shù) 計(jì) 生 數(shù) 計(jì) 生趙 錢 孫 李 周 趙 錢 孫 李 周(1(數(shù) 計(jì) 生趙 錢 孫 李 周(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次, b c f deg此外, , 這表明此條件是必要、, 有7個(gè)人, A會(huì)講英語, B會(huì)講英語和漢語, C會(huì)講英語、意大利語和俄語, D會(huì)講日語和漢語, E會(huì)講德語和意大利語, F會(huì)講法語、日語和俄語, , 使得每個(gè)人都能與兩旁的人交談? 解作無向圖, 每人是一個(gè)頂點(diǎn), F E DA B CACEGFDBA是一條哈密頓回路,按此順序就坐即可.第四篇：離散數(shù)學(xué)自學(xué)學(xué)習(xí)體會(huì)專業(yè)：計(jì)算機(jī) 姓名：范文芳 學(xué)號(hào)： 成績(jī)： 院校：離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的基礎(chǔ)核心課程。同時(shí)，也要培養(yǎng)學(xué)生抽象思維和慎密概括的能力，使學(xué)生具有良好的開拓專業(yè)理論的素質(zhì)和使用所學(xué)知識(shí)，分析和解決實(shí)際問題的能力，為學(xué)生以后學(xué)習(xí)計(jì)算機(jī)基礎(chǔ)理論與專業(yè)課程打下良好的基礎(chǔ)。因此學(xué)習(xí)離散數(shù)學(xué)對(duì)于計(jì)算機(jī)、通信等專業(yè)后續(xù)課程的學(xué)習(xí)和今后從事計(jì)算機(jī)科學(xué)等工作是至關(guān)重要的。因此，對(duì)離散數(shù)學(xué)的學(xué)習(xí)方法給予適當(dāng)?shù)闹笇?dǎo)和對(duì)學(xué)習(xí)過程中遇到的一些問題分析是十分必要的。它以研究量的結(jié)構(gòu)和相互關(guān)系為主要目標(biāo)，其研究對(duì)象一般是有限個(gè)或可數(shù)個(gè)元素，充分體現(xiàn)了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。1．定義和定理多離散數(shù)學(xué)是建立在大量定義、定理之上的邏輯推理學(xué)科，因此對(duì)概念的理解是學(xué)習(xí)這門課程的核心。在考試中有一部分內(nèi)容是考查學(xué)生對(duì)定義和定理的識(shí)記、理解和運(yùn)用，因此要真正理解離散數(shù)學(xué)中所給出的每個(gè)基本概念的真正的含義。掌握和理解這些概念對(duì)于學(xué)好離散數(shù)學(xué)是至關(guān)重要的。如果知道了一道題用怎樣的方法去做或證明，就能很容易地做或證出來。在離散數(shù)學(xué)中，雖然各種各樣的題種類繁多，但每類題的解法均有規(guī)律可循。在平時(shí)的講課和復(fù)習(xí)中，老師會(huì)總結(jié)各類解題思路和方法。離散數(shù)學(xué)的特點(diǎn)是知識(shí)點(diǎn)集中，對(duì)抽象思維能力的要求較高。不管是哪本離散數(shù)學(xué)教材，都會(huì)在每一章中首先列出若干個(gè)定義和定理，接著就是這些定義和定理的直接應(yīng)用，如果沒有較好的抽象思維能力，學(xué)習(xí)離散數(shù)學(xué)確實(shí)具有一定的困難。在學(xué)習(xí)離散數(shù)學(xué)中所遇到的這些困難，可以通過多學(xué)、多看、認(rèn)真分析講課中所給出的典型例題的解題過程，再加上多練，從而逐步得到解決。所以，同學(xué)們要準(zhǔn)確、全面、完整地記憶和理解所有這些基本定義和定理。通過認(rèn)真的分析可尋找出三大部分之間知識(shí)的內(nèi)在聯(lián)系性和規(guī)律性。二、認(rèn)知解題規(guī)范一般來說，離散數(shù)學(xué)的考試要求分為：了解、理解和掌握。為了考核學(xué)生對(duì)這三部分的理解和掌握的程度，試題類型一般可分為：判斷題、填空題、選擇題、計(jì)算題和證明題。學(xué)習(xí)離散數(shù)學(xué)的最大困難是它的抽象性和邏輯推理的嚴(yán)密性。一個(gè)寫得很好的解題過程或證明是一系列的陳述，其中每一條陳述都是前面的陳述經(jīng)過簡(jiǎn)單的推理而得到的。一個(gè)好的解題過程或證明應(yīng)該是條理清楚、論據(jù)充分、表述簡(jiǎn)潔的。通過離散數(shù)學(xué)的學(xué)習(xí)和訓(xùn)練，能使同學(xué)們學(xué)會(huì)在離散數(shù)學(xué)中處理問題的一般性的規(guī)律和方法，一旦掌握了離散數(shù)學(xué)中這種處理問題的思想方法，學(xué)習(xí)和掌握離散數(shù)學(xué)的知識(shí)就不再是一件難事了。第一階段，大量進(jìn)行知識(shí)儲(chǔ)備的階段。因而對(duì)概念的理解是我們學(xué)習(xí)這門學(xué)科的核心。對(duì)于跨專業(yè)自學(xué)的朋友來說更是如此。因此，對(duì)于第一遍復(fù)習(xí)，我們提出一個(gè)最為重要的要求，即準(zhǔn)確、全面、完整地記憶所有的定義和定理。無須強(qiáng)求一定要理解，記住并能準(zhǔn)確復(fù)述 各定義定理是此階段的最高要求。請(qǐng)牢記，這是為未來的向廣度和深度擴(kuò)張作必要的準(zhǔn)備。第二階段，深入學(xué)習(xí)，并大量做課后習(xí)題的階段。解離散數(shù)學(xué)的題，方法非常重要，如果拿到一道題，立即能夠看出它所屬的類型及關(guān)聯(lián)的知識(shí)點(diǎn)，就不難選用正確的方法將其解決，反之則事倍功半。相應(yīng)的對(duì)策也馬上就可以提出來。由此可見，在平常復(fù)習(xí)中，要善于總結(jié)和歸納，仔細(xì)體會(huì)題目類型和此類題目的解題套路。“熟讀唐詩三百首，不會(huì)做詩也會(huì)吟。那么，在考場(chǎng)上就會(huì)發(fā)現(xiàn)絕大多數(shù)題見過或似曾相識(shí)。這一情況具有普遍性，對(duì)許多院校的考試都適用。這一階段從第二階段結(jié)束一直持續(xù)到考試。因?yàn)槊總€(gè)單位對(duì)該科目的側(cè)重點(diǎn)畢竟有不同，從歷年試題中可以獲取許多有用的信息。第五篇：離散數(shù)學(xué)第三章第三章部分課后習(xí)題參考答案：(2)前提：p174。(q217。p(4)前提：q174。s,s171。r 結(jié)論：p217。(q217。q218。r ①置換 ③q174。r ②蘊(yùn)含等值式 ④r 前提引入 ⑤216。q 前提引入 ⑦￢p ⑤⑥拒取式證明（4）：①t217。s 前提引入 ④s171。t ③④等價(jià)三段論 ⑥（q174。(t174。t）⑥化簡(jiǎn) ⑧q ②⑥ 假言推理 ⑨q174。q ⑧⑩合取15在自然推理系統(tǒng)P中用附加前提法證明下面各推理：(1)前提：p174。r),s174。r 證明①s 附加前提引入 ②s174。(q174。r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理16在自然推理系統(tǒng)P中用歸謬法證明下面各推理：(1)前提：p174。q,216。q,r217。s 結(jié)論：216。﹁q 前提引入 ③﹁q ①②假言推理 ④￢r218。￢s 前提引入 ⑦r ⑥化簡(jiǎn)律 ⑧r217。﹁r 是矛盾式,所以推理正確.