離散數(shù)學(xué)discretemathematics

1、離散數(shù)學(xué)Discrete Mathematics,引言 為什么要學(xué)習(xí)離散數(shù)學(xué)？,離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支，它充分描述了計算機(jī)科學(xué)離散性的特點(diǎn)，是計算機(jī)學(xué)科的數(shù)學(xué)基礎(chǔ)，是計算機(jī)專業(yè)必修的專業(yè)基礎(chǔ)課。    20世紀(jì)，計算機(jī)學(xué)科及其它學(xué)科為應(yīng)用數(shù)學(xué)提出了越來越多的問題，而幾乎所有這些問題都具有離散的性質(zhì)，亦具有有限結(jié)構(gòu)，在解決和轉(zhuǎn)換這些問題的過程中應(yīng)用數(shù)學(xué)的新學(xué)科——離散數(shù)學(xué)誕生和發(fā)展了。

2、    什么是離散的性質(zhì)呢？簡單地說，是問題本身具有離散的結(jié)構(gòu)，它們涉及的函數(shù)是定義在離散的點(diǎn)而不是連續(xù)的點(diǎn)的集合上，即它們涉及離散的量，因而需要離散地求解這些問題。    數(shù)字計算機(jī)本身就是點(diǎn)量的機(jī)器，它僅涉及整數(shù)，而離散數(shù)學(xué)恰好提供點(diǎn)量的模型，于是它成為計算機(jī)學(xué)科的一個極其有用且容易理解的工具。,一、內(nèi)容簡介,離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支，是計算機(jī)

3、科學(xué)中基礎(chǔ)理論的核心課程，是計算機(jī)及應(yīng)用專業(yè)的重要基礎(chǔ)課程。離散數(shù)學(xué)與計算機(jī)科學(xué)中的數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法設(shè)計與分析、邏輯設(shè)計、系統(tǒng)結(jié)構(gòu)、容錯診斷、人工智能等課程緊密聯(lián)系。 離散數(shù)學(xué)主要講授數(shù)理邏輯、集合論、近世代數(shù)與圖論四個部分。,二、本課程的目的和任務(wù),由于離散數(shù)學(xué)的重要地位，因此通過本課程的教學(xué)，使計算機(jī)及應(yīng)用專業(yè)的學(xué)生能夠掌握數(shù)理邏輯、集合論、近世代數(shù)與圖論的基本概念、基本定理、基本方法，并

4、且培養(yǎng)學(xué)生具有一定的抽象思維能力和邏輯推理能力。同時為計算機(jī)及應(yīng)用專業(yè)的其它重要后續(xù)課程（如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理等課程）奠定比較堅實(shí)的基礎(chǔ)。,三、本課程與其它課程的關(guān)系,學(xué)生在進(jìn)入本課程之前，應(yīng)學(xué)習(xí)下列課程：         ·高等數(shù)學(xué)（一元微積分部分）       

5、  ·工程數(shù)學(xué)（線性代數(shù)部分）     本課程學(xué)習(xí)結(jié)束后，學(xué)生才能進(jìn)入下列課程學(xué)習(xí)階段：         ·數(shù)據(jù)結(jié)構(gòu)         ·操作系統(tǒng)    

6、     ·編譯原理     因此，本課程是一門重要的理論基礎(chǔ)課，理論性強(qiáng)并且與許多專業(yè)基礎(chǔ)課有著十分密切的聯(lián)系，學(xué)生應(yīng)對本門課程產(chǎn)生足夠的重視。,四、本門課的基本要求,1、數(shù)理邏輯     熟練掌握命題的連結(jié)詞及其真值表、恒等式及永真蘊(yùn)含式，掌握對偶與范式，了解其它連結(jié)詞，熟練地進(jìn)行命題邏輯的推理

7、。     掌握謂詞的概念及量詞，對自然語言與邏輯語言能進(jìn)行翻譯，了解變元的約束，熟練掌握謂詞演算的等價式與蘊(yùn)含式，了解前束范式，熟練掌握謂詞的推理理論與推理方法。     2、集合論     了解集合的運(yùn)算、序偶、笛卡兒乘積，掌握關(guān)系及表示，關(guān)系的復(fù)合與逆關(guān)系，熟練掌握關(guān)系的性質(zhì)、關(guān)系的閉包運(yùn)算，

8、了解集合的劃分與覆蓋，熟練掌握等價關(guān)系與等價類，掌握相容關(guān)系與序關(guān)系。了解映射的概念、逆映射與映射的復(fù)合，了解基數(shù)的概念、可數(shù)集與不可數(shù)集、基數(shù)的比較。     3、代數(shù)系統(tǒng)     了解代數(shù)的概念、運(yùn)算及性質(zhì)，掌握半群、獨(dú)異點(diǎn)，掌握群與子群，熟練掌握阿貝爾群與循環(huán)群，熟練掌握陪集與拉格朗日定理，熟練掌握同態(tài)與同構(gòu)，了解環(huán)與域。 &#

9、160;   了解格的概念，掌握分配格、有補(bǔ)格，熟練掌握布爾代數(shù)，了解布爾表達(dá)式。     4、圖論     了解圖的概念、路與回路，熟練掌握圖的矩陣表示，掌握歐拉圖與哈密頓圖，掌握平面圖、對偶圖與著色，熟練掌握樹與生成樹，掌握樹根與應(yīng)用。,第一篇　數(shù)理邏輯,邏緝學(xué)是一門研究思維形式及思維規(guī)律的科學(xué)。邏輯規(guī)律就是客觀事物

10、在人的主觀意識中的反映。    邏輯學(xué)分為辯證邏緝與形式邏輯兩種，前者是以辯證法認(rèn)識論的世界觀為基礎(chǔ)的邏輯學(xué)，而后者主要是對思維的形式結(jié)構(gòu)和規(guī)律進(jìn)行研究的類似于語法的一門工具性學(xué)科。思維的形式結(jié)構(gòu)包括了概念，判斷和推理之間的結(jié)構(gòu)和聯(lián)系，其中概念是思維的基本單位，通過概念對事物是否具有某種屬性進(jìn)行肯定或否定的回答，這就是判斷；由一個或幾個判斷推出另一判斷的思維形式，就是推理。研究推理有很多方法，用數(shù)學(xué)方法來

11、研究推理的規(guī)律稱為數(shù)理邏輯，即通過引入表意符號研究推理，因此，數(shù)理邏輯又名符號邏輯。    現(xiàn)代數(shù)理邏輯可分為證明論、模型論、遞歸函數(shù)論、公理化集合論等，這里介紹的是數(shù)理邏輯最基本的內(nèi)容：命題邏輯和謂詞邏輯。 命題邏輯，也稱命題演算，記為Ls。它與謂詞邏輯構(gòu)成數(shù)理邏輯的基礎(chǔ)，而命題邏輯又是謂詞邏輯的基礎(chǔ)。,學(xué)習(xí)《數(shù)理邏輯》這一篇的要求,一、學(xué)習(xí)目的與要求 本章目的

12、是介紹命題邏輯的基本概念。掌握利用命題邏輯表示自然語言，描述概念、判斷和推理。建立初步的語言形式化方法。,二、知識點(diǎn)1．命題的概念、表示方法；聯(lián)結(jié)詞的邏輯意義。2．命題公式的遞歸定義，自然語言翻譯成命題公式3．真值表的構(gòu)造、命題公式等價的概念。4．重言式與蘊(yùn)涵式的定義、邏輯意義，邏輯等價與邏輯蘊(yùn)涵的意義和證明方法。常用的邏輯等價公式和邏輯蘊(yùn)涵公式。,5．命題公式的對偶式、合取范式、析取范式、主合取范式、主析取范式。邏輯小項(xiàng)、邏輯

13、大項(xiàng)。任給公式化為析取范式、任給公式化為主析取范式、任給公式化為合取范式、任給公式化為主合取范式。 6．命題邏輯的推理理論，主要的推理方法：真值表法、直接證明法、間接證明法。常用推理規(guī)則：P規(guī)則、T規(guī)則、CP規(guī)則。 7．命題邏輯的應(yīng)用示例。,三、要求1．識記 命題表示方法、真值判斷、命題公式的遞歸定義。2．領(lǐng)會 聯(lián)結(jié)詞真值確定、翻譯、命題公式的等價性和蘊(yùn)涵性證明、任給公式化為析取范式、任給公式化為主析取范式

14、、任給公式化為合取范式、任給公式化為主合取范式。 3．簡單應(yīng)用 命題邏輯推理規(guī)則。,第一章 命題邏輯學(xué)時安排（14學(xué)時，共7講）,第一章 命題邏輯 第1講 §1—1 命題及其表示法 §1—2 聯(lián)結(jié)詞 要求：深刻理解命題、真值、 原子命題 、復(fù)合命題 、命題標(biāo)識符、命題常量、 命題變元、原子變元等概念， 熟練掌握命題的聯(lián)結(jié)

15、詞及其真值表。,§1—1 命題及其表示法一、命題1、定義 能表達(dá)判斷的陳述句稱作命題（Proposition）。例：判斷下列語句是否為命題:(1)地球外存在智慧生物。(2)1＋1=10。(3)邏輯是枯燥無味的。(4)你今年暑假去旅行嗎？（疑問句）(5)克里特島人說：“克里特島人都是說謊話者”。（悖論）,,陳述句：述說一件事情的句子，句末用句號。祈使句：要求或者希望別人做什么事或者不做什么事時用的句子，句末用

16、句號或感嘆號。疑問句：提出問題的句子，句末用問號。感嘆句：帶有濃厚感情的句子，句末用感嘆號。悖：相反。悖論：自相矛盾的陳述。,2、真值：命題所表達(dá)的判斷結(jié)果稱為命題的真值。真值只有“真”和“假”兩種，記作True（真）和False（假），分別用符號T和F表示。 由于命題只有兩種真值，所以稱這種邏輯為二值邏輯。命題的真值是具有客觀性質(zhì)的，而不是由人的主觀決定的。,再看下面的語句中，哪些語句是命題，如果是命題，指出它的真

17、值：    （1）能整除2的正整數(shù)是偶數(shù)。  （2）對于每一個正整數(shù)n存在一個大于n的素數(shù)。  （3）煤是白的。（F）  （4）雪是黑的。（F）    （5）我學(xué)英語，或者我學(xué)日語。（T）  （6）在宇宙中地球是唯一有生命的地球。    （7）1+101

18、=110   （8）買兩張星期六的電影票。（祈使句）  （9）全體立正?。ㄆ硎咕洌?#160; （10）明天是否開會？（疑問句）  （11）天氣多好?。。ǜ袊@句）  （12）我正在說謊。（悖論）,（3）和（4）是命題，真值為F。,（1）、（2）和（5）是命題，真值為T。,祈使句、疑問句、感嘆句等都不能作為命題，悖論無真值，也不

19、能作為命題。語句（8）—（12）都不是命題。,（6）是命題，有確定真值，只是目前還不知道。,（7）不是命題，在二進(jìn)制中為T，在十進(jìn)制中為F，,3、分類 命題有兩種類型：原子命題和復(fù)合命題 (1)原子命題：不能分解為更簡單的陳述句。 (2)復(fù)合（分子）命題：由聯(lián)結(jié)詞、標(biāo)點(diǎn)符號和原子命題復(fù)合構(gòu)成的命題。 前面例子中的（1），（2），（3），（4），（6），（7）是原子命題，（5）是復(fù)合命題

20、。,練習(xí)：指出下列語句哪些是命題，哪些不是命題，如果是命題，指出它的真值。（見教材第8頁習(xí)題（1））,a）離散數(shù)學(xué)是計算機(jī)科學(xué)系的一門必修課。     b）計算機(jī)有空嗎？     c）明天我去看電影。     d）請勿隨地吐痰！     e）不存在最大質(zhì)數(shù)。 

21、    f）如果我掌握了英語、法語，那么學(xué)習(xí)其他歐洲語言就容易的多。     g）9+5≤12     h）x=3     i）我們要努力學(xué)習(xí)。,解：,a）離散數(shù)學(xué)是計算機(jī)科學(xué)系的一門必修課。 是命題，真值為T。     b）計算機(jī)有空嗎？

22、疑問句，不是命題。     c）明天我去看電影。 是命題，真值要根據(jù)具體情況確定。     d）請勿隨地吐痰！ 祈使句，不是命題。     e）不存在最大質(zhì)數(shù)。 是命題，真值為T。     f）如果我掌握了英語、法語，那么學(xué)習(xí)其他歐洲語言就容易的多。 是命題，真值為T。

23、     g）9+5≤12 是命題，真值為F。     h）x=3 不是命題，x=3的真假由x確定，當(dāng)x取3時句子為真，當(dāng)x取其他值時句子為假。     i）我們要努力學(xué)習(xí)。 祈使句，不是命題。,a），e），g），h）是原子命題，f）是復(fù)合命題。,三、命題的表示法    1、命題標(biāo)識

24、符：表示命題的符號稱為命題標(biāo)識符。在數(shù)理邏輯中，使用大寫字母，或帶下標(biāo)的大寫字母，或用方括號括起的數(shù)字表示表示命題。     例：P：今天下雨。    “今天下雨”是一個命題，P是命題標(biāo)識符。 A1：今天下雨。     [12]：今天下雨。   A1  ， [12]也是命題標(biāo)識符。&#

25、160;   2、命題常量：一個命題標(biāo)識符如表示確定的命題，就稱為命題常量。 3、命題變元：如果命題標(biāo)識符只表示任意命題的位置標(biāo)志，就稱為命題變元。 命題變元可以表示任意命題，所以它不能確定真值，故命題變元不是命題。當(dāng)命題變元用一個特定命題取代時，才能確定真值，這稱為對命題變元進(jìn)行指派。 4、原子變元：當(dāng)命題變元表示原子命題時，該變元稱為原子變元。,四、

26、小結(jié)    學(xué)習(xí)本節(jié)要掌握下列概念：    命題 能表達(dá)判斷的語句，并具有確定真值的陳述句。    真值 一個命題總具有一個“值”，稱為真值。真值只有真和假兩種，分別記為T和F。    原子命題 不能分解為更簡單的陳述句，稱為原子命題。    復(fù)合命題

27、 由聯(lián)結(jié)詞、標(biāo)點(diǎn)符號和原子命題復(fù)合構(gòu)成的命題，稱為復(fù)合命題。復(fù)合命題亦稱分子命題。    命題標(biāo)識符 表示命題的符號。    命題常量 一個命題標(biāo)識符表示確定的命題，該標(biāo)識符稱作命題常量。    命題變元 題標(biāo)識符如僅是表示任意命題的位置標(biāo)志，就成為命題變元。    原子變元

28、 當(dāng)命題變元表示原子命題時，該變元稱原子變元。,§1—2 聯(lián)結(jié)詞,在數(shù)理邏輯中，復(fù)合命題是由原子命題與邏輯聯(lián)結(jié)詞組合而成，命題的連接方式叫做命題聯(lián)結(jié)詞或命題運(yùn)算符。聯(lián)結(jié)詞是復(fù)合命題中的重要組成部分，為了便于書寫和進(jìn)行推演，必須對聯(lián)結(jié)詞作出明確規(guī)定并符號化。我們主要討論下述五種聯(lián)結(jié)詞（亦稱真值聯(lián)結(jié)詞，邏輯聯(lián)結(jié)詞或邏輯運(yùn)算符），借助它們組成復(fù)合命題。,（1）否定（Negation）（一元聯(lián)結(jié)詞）,1.定義 定義1-2.

29、1 設(shè)P為一命題，P的否定是一個新的命題，記作 ┐P。若P為T，┐P為F；若P為F，┐P為T。聯(lián)結(jié)詞“┐”表示命題的否定，稱為否定聯(lián)結(jié)詞或否定詞，讀作“非”或“not”。否定聯(lián)結(jié)詞有時亦可記作“ˉ”。,2.真值表 表1-2.1,命題P與其否定┐P的關(guān)系如表1-2.1所示。,“否定”的意義僅是修改了命題的內(nèi)容，它是一個一元運(yùn)算，我們?nèi)园阉醋鳛槁?lián)結(jié)詞。 自然語言中的“不”、“無”、“沒有

30、”等詞在命題演算中常與“非”相當(dāng)。 例：P：今天下雨。 ┐P：今天不下雨。 ┐P：今天無雨。 ┐P：今天沒有下雨。 P：上海是一個大城市。 ┐P：上海不是一個大城市。 ┐P：上海是一個不大的城市。 練習(xí)：P：一個世紀(jì)是一百年。寫出┐P。,（2）合取（Conjunction）（二元聯(lián)結(jié)詞）,1.定義 定義1-2.

31、2 兩個命題P和Q的合取是一個復(fù)合命題，記作P∧Q。當(dāng)且僅當(dāng)P、Q同時為T時，P∧Q為T，在其他情況下，P∧Q的真值都是F。聯(lián)結(jié)詞“∧”稱為合取詞，讀作“和”或“and”。,2.真值表 聯(lián)結(jié)詞“∧”的定義如表1-2.2所示。,表1-2.2,表1-2.2中給出復(fù)合命題P∧Q為T當(dāng)且僅當(dāng)P、Q同時為T。,與“和”有相同意義的漢字還有“與”、“以及”、“并且”、“而且”等。 例：P：今天下雨。 Q：明天下雨。

32、 上述命題的合取為 P∧Q：今天下雨而且明天下雨。 P∧Q：今天與明天都下雨。 P∧Q：這兩天都下雨。 顯然只有當(dāng)“今天下雨”與“明天下雨”都是真時，“這兩天都下雨”才是真的。,合取的概念與自然語言中的“與”意義相似，但并不完全相同。例如 P：我們?nèi)タ措娪啊?Q：房間里有十張桌子。 上述命題的合取為 P∧Q：我們?nèi)タ措娪芭c

33、房間里有十張桌子。 在自然語言中，上述命題是沒有意義的，因?yàn)镻與Q沒有內(nèi)在聯(lián)系，但作為數(shù)理邏輯中P和Q的合取P∧Q來說，它仍可成為一個新的命題，只要按照定義，在P、Q分別取真值后，P∧Q的真值也必確定。,例如 ①P：1+1=2 Q：地球是行星。 P∧Q：1+1=2與地球是行星。 P∧Q的真值為T。 ②P：1+1=2 Q：地球是恒星。

34、 P∧Q：1+1=2與地球是恒星。 P∧Q的真值為F。,③P：1+1=3 Q：地球是行星。 P∧Q：1+1=3與地球是行星。 P∧Q的真值為F。 ④P：1+1=3 Q：地球是恒星。 P∧Q：1+1=3與地球是恒星。 P∧Q的真值為F。,命題聯(lián)結(jié)詞“合取”甚至可以將兩個互為否定的命題聯(lián)結(jié)在一起。這時，

35、其真值永為F。 P：今天下雨。 Q：今天不下雨。（此時Q既是┐P） P∧Q：今天下雨與今天不下雨。 P∧Q的真值為F。 命題聯(lián)結(jié)詞“合取”也可以將若干個命題聯(lián)結(jié)在一起。 “合取”是一個二元運(yùn)算。,注意，并非所有的“和”、“與”、“并且”均可用“∧”表示。例如“李華和張南是表兄弟?！薄巴觖惻c王萍是堂姐妹”“他打開箱子并且取出一件衣服來。”這三句中的“和”

36、、“與”、“并且”就不能用“∧”表示。 練習(xí)：P：一個世紀(jì)是一百年。 Q：4是偶數(shù)。 寫出P∧Q并確定其真值。,（3）析取（Disjunction）（二元聯(lián)結(jié)詞）,1.定義 定義1-2.3 兩個命題P和Q的析取是一個復(fù)合命題，記作P∨Q。當(dāng)且僅當(dāng)P、Q同時為F時，P∨Q為F，否則P∨Q的真值為T。聯(lián)結(jié)詞“∨”稱為合取詞，讀作“或”或“or”。,2.真值表聯(lián)結(jié)詞∨的定義如表1-2.3

37、所示。,表1-2.3,表1-2.3中給出復(fù)合命題P∨Q為F當(dāng)且僅當(dāng)P、Q同時為F。,例：P：燈泡壞了。 Q：開關(guān)壞了。 上述命題的析取為 P∨Q：燈泡壞了或開關(guān)壞了。,并非所有的“或”可用“∨”表示。例如，“我向東行或向西行?！痹撜Z句中的“或”稱為“排斥或”，因?yàn)槭聦?shí)上一個人不會既向東行，又向西行。 析取“∨”指的是“可兼或”。例如，他可能是100米或400米賽跑的冠軍。這里

38、 P：他可能是100米賽跑的冠軍。 Q：他可能是400米賽跑的冠軍。 P∨Q：他可能是100米或400米賽跑的冠軍。,還有一些漢語中的“或”字實(shí)際上不是命題聯(lián)結(jié)詞。例如，他昨天做了二十或三十道習(xí)題。這里的“或”字只表示了習(xí)題的近似數(shù)目，不能用聯(lián)結(jié)詞“∨”表達(dá)。 練習(xí)：P：雪是黑的。 Q：4是偶數(shù)。 寫出P∨Q并確定其真值。,（4）條件（Con

39、dition）（二元聯(lián)結(jié)詞）,1.定義定義1-2.4 給定兩個命題P和Q，其條件命題是一個復(fù)合命題，記作P→Q，讀作“如果P，那么Q”或“若P則Q”。當(dāng)且僅當(dāng)P的真值為T，Q的真值為為F時，P→Q的真值為F，否則P→Q的真值為T。我們稱P為前件，Q為后件。,2.真值表聯(lián)結(jié)詞→的定義如表1-2.4所示。,表1-2.4,例1 如果某動物為哺乳動物，則它必胎生。 例2 如果我得到這本小說，那么我今夜就讀完它。 例3

40、 如果雪是黑的，那么太陽從西方出。 上述三個例子都可用條件命題P→Q表達(dá)。 在例1中，P：某動物為哺乳動物，Q：它必胎生。P的真值為T，Q的真值為T，P→Q的真值為T。 在例2中，P：我得到這本小說，Q：我今夜就讀完它。P的真值為T，Q的真值為T，P→Q的真值為T。如果P的真值為T，Q的真值為F，P→Q的真值為F。如果P的真值為F，Q的真值為T，P→Q的真值為T。 在

41、例3中，P：雪是黑的，Q：太陽從西方出。P的真值為F，Q的真值為F，P→Q的真值為T。,在自然語言中，“如果…”與“那么…”之間常常是有因果聯(lián)系的，否則就沒有意義，但對條件命題P→Q來說，只要P、Q能夠分別確定真值，P→Q即成為命題。此外，自然語言中對“如果…、則…”這樣的語句，當(dāng)前提為假時，結(jié)論不管真假，這個語句的意義，往往無法判斷。而在條件命題中，規(guī)定為“善意的推定”，即前提為F時，條件命題的真值都取為T。,在數(shù)學(xué)上和有些邏輯學(xué)的書

42、籍中，“若P則Q”亦可叫作蘊(yùn)含Q，而本書在條件命題中將避免使用“蘊(yùn)含”一詞，因?yàn)樵谝院髮⒘硗舛x“蘊(yùn)含”這個概念。 命題聯(lián)結(jié)詞“→”亦可記作“ ”。,,,,(5)雙條件（Double Condition）（二元聯(lián)結(jié)詞）,1.定義 定義1-2.5 給定兩個命題P和Q，其復(fù)合命題P Q稱作雙條件命題，讀作“P當(dāng)且僅當(dāng)Q”，當(dāng)P和Q的真值相同時，P Q的真值為T，否則P Q的真值為F。,表1-

43、2.5,2.真值表聯(lián)結(jié)詞“ ”的定義可如表1-2.5所示。,例1 兩個三角形全等，當(dāng)且僅當(dāng)它們的三組對應(yīng)邊相等。 例2 燕子飛回南方，春天來了。 例3 2+2＝4當(dāng)且僅當(dāng)雪是白的。 上面三個例子都可用雙條件命題P Q來表示。與前面的聯(lián)結(jié)詞一樣，雙條件命題也可以不顧其因果聯(lián)系，而只根據(jù)聯(lián)結(jié)詞定義確定真值。雙條件聯(lián)結(jié)詞亦可記作“ ”或“iff”。它亦是二元運(yùn)算。有時也用符號€表

44、示雙條件。,應(yīng)強(qiáng)調(diào)指出的是：復(fù)合命題的真值只取決于各原子命題的真值，而與它們的內(nèi)容、含義無關(guān)，與原子命題之間是否有關(guān)系無關(guān)。理解和掌握這一點(diǎn)是至關(guān)重要的。,小結(jié) 本節(jié)給出了如下五種聯(lián)結(jié)詞的定義： 否定 設(shè)P為一命題，P的否定是一個新的命題，記作 ┐P。若P為T，┐P為F；若P為F，┐P為T。 合取 兩個命題P和Q的合取是一個復(fù)合命題，記作P∧Q。當(dāng)且僅當(dāng)P、Q同時為T時，P∧Q為T

45、，在其他情況下，P∧Q的真值都是F。 析取 兩個命題P和Q的析取是一個復(fù)合命題，記作P∨Q。當(dāng)且僅當(dāng)P、Q同時為F時，P∨Q為F，否則P∨Q的真值為T。 條件 給定兩個命題P和Q，其條件命題是一個復(fù)合命題，記作P→Q，讀作“如果P，那么Q”或“若P則Q”。當(dāng)且僅當(dāng)P的真值為T，Q的真值為為F時，P→Q的真值為F，否則P→Q的真值為T。 雙條件 給定兩個命題P和Q，其

46、復(fù)合命題P Q稱作雙條件命題，讀作“P當(dāng)且僅當(dāng)Q”，當(dāng)P和Q的真值相同時，P Q的真值為T，否則P Q的真值為F。,練習(xí) 8頁（2）--（6）,(2)舉例說明原子命題和復(fù)合命題。 (3)設(shè)P表示命題“天下雪 Q表示命題“我將去鎮(zhèn)上。 R表示命題“我有時間” 以符號形式寫出下列命題。 a)如果天不下雪和我有時間，那么我將去鎮(zhèn)上。 b)我將去鎮(zhèn)上，僅當(dāng)我有時間時。

47、 c)天不下雪。 d)天下雪，那么我不去鎮(zhèn)上。,(4)用漢語寫出一句子，對應(yīng)下列每一個命題。 a)Q (R∧┐P) b)R∧Q c)(Q→R )∧(R→Q) (5)將下列命題符號化。 8)王強(qiáng)身體很好，成績也很好。 b)小李一邊看書，一邊聽音樂。 c)氣候很好或很熱。 d)如果a和b是偶數(shù)，則a+b是偶數(shù)。 e)四邊形ABCD是平行四邊形，當(dāng)且僅當(dāng)它的對邊平行． f)停機(jī)的原因在于

48、語法錯誤或程序錯誤。,(6)將下列復(fù)合命題分成若干原子命題， a)天氣炎熱且正在下雨。 b)天氣炎熱但濕度較低。 c)天正在下雨或濕度很高。 d)劉英與李進(jìn)上山。 e)老王或小李是革新者。 f)如果你不看電影，那么我也不看電影。 g)我既不看電視也不外出，我在睡覺。 h)控制臺打字機(jī)既可作輸入設(shè)備，又可作輸出設(shè)備。,解答,(2)舉例說明原子命題和復(fù)合命題。 原子命題：北京是中國的首都。 復(fù)

49、合命題：李毅和王強(qiáng)都是優(yōu)秀學(xué)生。,(3)設(shè)P表示命題“天下雪” Q表示命題“我將去鎮(zhèn)上。 R表示命題“我有時間” 以符號形式寫出下列命題。 a)如果天不下雪和我有時間，那么我將去鎮(zhèn)上。（┐P∧R ）→Q b)我將去鎮(zhèn)上，僅當(dāng)我有時間時。 R→Q c)天不下雪。 ┐P d)天下雪，那么

50、我不去鎮(zhèn)上。 P→┐Q,(4)用漢語寫出一句子，對應(yīng)下列每一個命題。 a)Q （R∧┐P) b)R∧Q 王強(qiáng)的數(shù)學(xué)和計算機(jī)都很好。 c)(Q→R) ∧(R→Q) 一個數(shù)是奇數(shù)，則它不能被2整除并且一個數(shù)不能被2整除，則它是奇數(shù)。,,(5)將下列命題符號化。 a)王強(qiáng)身體很好，成績也很好。 設(shè)P：王強(qiáng)身體很好。 Q

51、：王強(qiáng)成績很好。 P∧Q設(shè)P：小李看書。 Q：小b)小李一邊看書，一邊聽音樂。李聽音樂。 R∧Q c)氣候很好或很熱。 設(shè)P：氣候很好。 Q：氣候很熱。 R∨Q d)如果a和b是偶數(shù)，則a+b是偶數(shù)。 設(shè)P：a和b是偶數(shù)。 Q：a+b是偶數(shù)。 P→Q e)四邊形ABCD是平行四邊形，當(dāng)且僅當(dāng)它的對邊平行。 設(shè)P：四邊形ABCD是平行四邊形。 Q：四邊形ABCD的對邊平行。

52、 P Q f)停機(jī)的原因在于語法錯誤或程序錯誤。 設(shè)P：語法錯誤。 Q：程序錯誤。 S：停機(jī)。（R∨Q）→S,(6)將下列復(fù)合命題分成若干原子命題， a)天氣炎熱且正在下雨。 P：天氣炎熱。Q：正在下雨。 P∧Q b)天氣炎熱但濕度較低。 P：天氣炎熱。R：濕度較低。 P∧R c)天正在下雨或濕度很高。 d)劉英與李進(jìn)上山。 S：劉英上山。G：李進(jìn)上山。,e)老王或小