離散數(shù)學(xué)命題邏輯.ppt

1、第一章 命 題 邏 輯,命題與聯(lián)結(jié)詞,邏輯,研究人類思維的科學(xué)。公元前四世紀(jì)亞里斯多德工具論奠定了邏輯學(xué)的理論基礎(chǔ)。中國(guó)最早的一部邏輯專著墨經(jīng)也創(chuàng)造了一個(gè)比較完整的邏輯體系。,形式邏輯,辨證邏輯,數(shù)理邏輯,數(shù)理邏輯,數(shù)理邏輯是一門用數(shù)學(xué)方法來研究推理規(guī)律的科學(xué)。 所謂數(shù)學(xué)方法主要是指引進(jìn)一套符號(hào)體系的方法，所以數(shù)理邏輯也稱做符號(hào)邏輯。,（創(chuàng)始人：十七世紀(jì)，德國(guó)數(shù)學(xué)家萊布尼茲）,形式符號(hào)體系,由于自然語言存在模棱兩可、含糊的特性，所以有必要引入形式化語言。形式化語言在數(shù)理邏輯中稱為目標(biāo)語言。 例如：今天晚上八點(diǎn)中央一臺(tái)播放連續(xù)劇或紀(jì)錄片。 我吃蘋果或雪梨。 定義目標(biāo)語言：具有單一、明確的含義的語

2、言。（基本元素是命題） 定義形式符號(hào)體系：由目標(biāo)語言和一些規(guī)定的公式與符號(hào)構(gòu)成的體系,為何學(xué)習(xí)數(shù)理邏輯,程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu) 算法 = 邏輯 + 控制,數(shù)理邏輯的主要內(nèi)容,數(shù)理邏輯內(nèi)容豐富，但其主要包括“兩個(gè)演算” 加“四論”，即： 邏輯演算。包括命題演算和謂詞演算 證明論。主要研究數(shù)學(xué)理論系統(tǒng)的相容性（即不矛盾、協(xié)調(diào)性）的證明。 遞歸論（能行性理論）。自從電子計(jì)算機(jī)發(fā)明后，迫切需要在理論上弄清計(jì)算機(jī)能計(jì)算哪些函數(shù)。遞歸論研究能行可計(jì)算的理論，它為能行可計(jì)算的函數(shù)找出各種理論上精確化的嚴(yán)密類比物。 模型論。主要是對(duì)各種數(shù)學(xué)理論系統(tǒng)建立模型，并研究各模型之間的關(guān)系以及模型與系統(tǒng)之間的關(guān)系

3、。 公理集合論。主要研究在消除已知集合論悖論的情況下，用公理方法把有關(guān)集合的理論充分發(fā)展下去。,命題邏輯研究的內(nèi)容,命題邏輯也稱為命題演算 研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系. (1) 什么是命題？ (2) 如何表示命題？ (3) 如何由一些前提推導(dǎo)出一些結(jié)論?,命題與聯(lián)結(jié)詞,命題 聯(lián)結(jié)詞,命題的概念,具有判斷內(nèi)容（非真即假）的陳述句稱為命題。 能夠確定或分辨其真假的陳述句。 命題有一個(gè)值，稱為真值，真值只有“真”和“假”兩種，分別用“T”（或“1”）和“F”（或“0”）表示。 命題中的判斷正確，其真值為真，稱為真命題，命題中的判斷錯(cuò)誤，真值為假，稱為假命題。,命題示例1,中

4、華人民共和國(guó)的首都是北京。 我們?cè)趯W(xué)習(xí)離散數(shù)學(xué)的數(shù)理邏輯部分。 所有素?cái)?shù)都是奇數(shù)。 雪是黑色的。,命題示例2,某些感嘆句、祈使句、疑問句等沒有真假之分，所以不是命題。 明天開會(huì)嗎？ 多美妙啊！ 請(qǐng)進(jìn)來。 全體立正。,判斷語句是否為命題要注意的問題：,目前無法確定真值，但從本質(zhì)而言，真值存在的語句是命題。 例： (1) 別的星球上有生物。 (2) 2046年世界杯在中國(guó)舉行。 真值因時(shí)因地而異的判斷性陳述句是命題。 例：(1) 現(xiàn)在是上午。 (2) 今天下雨。 含有未確定內(nèi)容的代詞，不能判斷真假的語句不是命題。 例： (1) 1+101=110。 當(dāng)1和101是二進(jìn)制數(shù)，語句為真，為十進(jìn)制數(shù)，語

5、句為假。 (2) x+y10。 悖論不是命題。 例：我正在說慌。,命題的分類,根據(jù)命題的構(gòu)成形式，可以將命題分為： 定義原子命題：不包含任何聯(lián)結(jié)詞的命題。 定義復(fù)合命題：由原子命題和聯(lián)結(jié)詞組成的命題。連接詞一般譯為：“或者”、“并且”、“不”、“如果則”、“僅當(dāng)”、“當(dāng)且僅當(dāng)”等。 例如：“明天下雪”、“9是素?cái)?shù)”都是原子命題， “2不是素?cái)?shù)”是復(fù)合命題 “明天下雪或明天下雨”是復(fù)合命題。 “中國(guó)獲得2008奧運(yùn)的主辦權(quán)并且加入了WTO”是復(fù)合命題。 “如果A和B是對(duì)頂角，則角A等于角B”是復(fù)合命題。,命題的表示,定義命題標(biāo)識(shí)符：表示命題的符號(hào)，通常是大寫英文字母。 定義命題符號(hào)化：將表示命題

6、的符號(hào)放在該命題的前面。 例：P：北京是中國(guó)的首都。 Q：北京承辦2008年奧運(yùn)。,命題的表示（續(xù)）,定義命題常量：表示確定命題的命題標(biāo)識(shí)符。 定義命題變?cè)嚎杀硎救我庖粋€(gè)（原子或復(fù)合）命題的命題標(biāo)識(shí)符，就稱為命題變?cè)．?dāng)命題變?cè)硎驹用}時(shí)，該變?cè)Q為原子變?cè)?當(dāng)命題變?cè)狿用一個(gè)特定命題去取代時(shí)， 才能確定P的真值，這時(shí)也稱對(duì)P進(jìn)行指派。 例： 若P是命題變?cè)?P：北京是中國(guó)的首都。（指派P為命題北京是中國(guó)的首都）,命題小結(jié),判斷一句話是否是命題的步驟： 1）看它是否是陳述句，如果是疑問句、感嘆句和祈使句則不是命題； 2）看它是否是悖論，悖論不是命題，如“我正在說謊”； 3）看它真值是

7、否唯一，如果不唯一，則不是命題。,命題與聯(lián)結(jié)詞,命題 聯(lián)結(jié)詞,命題聯(lián)結(jié)詞,1. 否定： 2. 合取： 3. 析?。?4. 排斥析取： 5. 條件（蘊(yùn)含）： 6. 雙條件：,否定,設(shè)P為命題，P的否定也是一個(gè)命題，記作 P 當(dāng)P為T時(shí)， P為F 當(dāng)P為F時(shí)， P為T P與P的關(guān)系如右表 例：設(shè)P：上海是個(gè)大城市。 則P：上海不是一個(gè)大城市。 或：上海是個(gè)不大的城市。,合取,設(shè)P、Q是命題，P和Q的合取也是個(gè)命題，記作PQ 當(dāng)且僅當(dāng)P、Q同時(shí)為T時(shí)，PQ為T 其他情況下，PQ的真值都是F 讀作“P并且（與）Q”,合取示例,(1) P: 我富有。 Q: 我快樂。 PQ：我富有并且快樂。 (2) P:

8、 我們?nèi)ナ程贸燥垺?Q: 教室里有三塊黑板。 PQ: 我們?nèi)ナ程贸燥埐⑶医淌依镉腥龎K黑板。 注：復(fù)合命題中的原子命題之間無需有一般邏輯意義上的關(guān)聯(lián)，如(2)。,析取,設(shè)P、Q是命題，則P和Q的析取也是個(gè)命題，記作PQ。 當(dāng)且僅當(dāng)P、Q同時(shí)為F時(shí)，PQ為F 其他情況下， PQ的真值都是T 讀作“P或Q” （與自然語言中的“或”不完全相同，是兼并或）,析取例子,例：(1) P：猴子吃香蕉。 Q：猴子吃橘子。 猴子吃香蕉或者吃橘子 ？ PQ (2) P：他明天早上吃蛋糕。 Q：他明天早上喝牛奶。 PQ？ 他明天早上吃蛋糕或者喝牛奶 。 (3) P: 我明天早上9點(diǎn)在家看書。 Q: 我明天早上9點(diǎn)出去

9、打球。 我明天早上9點(diǎn)在家看書或出去打球 PQ？,排斥析取,設(shè)P、Q是命題，P和Q的排斥析取也是個(gè)命題，記作 PQ 當(dāng)且僅當(dāng)P和Q的真值不相同時(shí)， PQ為T， 其他情況下,PQ的真值都是F 讀作“P或Q” （排斥或）,排斥析取示例,指出下列命題中的“或”是析取還是排斥析取 今晚我去看演出或在家里看電視現(xiàn)場(chǎng)轉(zhuǎn)播。 他是一百米冠軍或跳高冠軍。 派小王或小趙出差去上海。 派小王或小趙中的一個(gè)出差去上海。 2、3為析取，1、 4為排斥析取,條件/蘊(yùn)含,設(shè)P、Q是命題，P對(duì)于Q的條件命題記為PQ，或稱為P蘊(yùn)含Q 。 當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時(shí)，PQ的真值為F， 其他情況， PQ的真值為T。 讀

10、作“如果（若）P，則Q”、“Q是P的必要條件” 、“僅當(dāng)Q為真時(shí)，P為真” 稱P為前件，Q為后件。,條件示例,P：天不下雨 Q：我去看電影 如果天不下雨，那么我去看電影： PQ 。 P：我不到學(xué)校去。 Q：我生病。 PQ：如果我不到學(xué)校去，那么我生病。 P：我去踢足球。 Q：我有時(shí)間。 僅當(dāng)我有時(shí)間，我去踢足球。,PQ,雙條件,P、Q是命題，P和Q的雙條件命題記作：P Q 當(dāng)P和Q的真值相同時(shí)，P Q的真值為T， 否則PQ的真值為F 翻譯為：“P當(dāng)且僅當(dāng)Q” 或者“若P則Q，否則，則Q”,雙條件示例,P：整數(shù)a能被2整除 Q：a是偶數(shù)。 當(dāng)且僅當(dāng)整數(shù)a能被2整除，a才是偶數(shù)：P Q 。 P：天

11、不下雨 Q：我去看足球 P Q：如果天不下雨，我就去看足球，否則，我就不去看足球。 P：224 Q：雪是白的 224當(dāng)且僅當(dāng)雪是白的： P Q 注：復(fù)合命題中的原子命題之間無需有一般邏輯意義上的關(guān)聯(lián)。如此例中P和Q并無因果關(guān)系，P Q仍是命題，其真值根據(jù)聯(lián)結(jié)詞定義以及P和Q的真值來確定。,綜合示例,設(shè)P表示命題“天下雪”。 Q表示命題“我去看電影”。 R表示命題“我有時(shí)間”。 試以符號(hào)形式表示下列命題：,P PQ Q R (QR) P,天不下雪。 如果天不下雪，那么我去看電影。 我去看電影，僅當(dāng)我有時(shí)間。 如果我去看電影且我有時(shí)間，那么天不下雪。,聯(lián)結(jié)詞小結(jié),1. 復(fù)合命題的真值只取決于構(gòu)成它

12、們的原子命題的真值和命題聯(lián)結(jié)符的定義，而與它們的內(nèi)容、含義無關(guān)，與聯(lián)結(jié)詞所連接的兩個(gè)原子命題之間是否有關(guān)系無關(guān)。 2. ，和具有可交換性，而，沒有。,聯(lián)結(jié)詞小結(jié),1.“只要(若、當(dāng))A成立，則B成立” ：AB 2.“僅當(dāng)A成立時(shí),B成立”和“只有A成立時(shí)，B成立”： BA 3. “A成立,否則B成立”：AB。 4. 遇到“或”，就需要考察兩件事情可否同時(shí)發(fā)生，若不能同時(shí)，則是，否則用“”。,聯(lián)結(jié)詞運(yùn)算順序,優(yōu)先級(jí)從高到底排列： 、/、 、 ,命題（合式）公式,定義命題合式公式： (1) 單個(gè)命題變?cè)旧硎且粋€(gè)命題合式公式。 (2) 如果A是合式公式，則A是命題合式公式。 (3) 如果 A和B是合式公式，則AB,AB、AB、AB、AB都是命題合式公式。 (4) 當(dāng)且僅當(dāng)能夠有限次應(yīng)用(1)、(2)、(3)所得到的包含命題變?cè)?，?lián)結(jié)詞和括號(hào)的符號(hào)串是命題合式公式。,命題（合式）公式舉例,設(shè)P、Q、R、S、T都是命題變?cè)袛嘞铝凶址男┦呛鲜焦剑?(1) (P Q) (2)(PQ) (Q R ) (S T) (3) (PQ) (Q) (4) (PQ)，