《離散數(shù)學(xué)命題邏輯》PPT課件.ppt

《《離散數(shù)學(xué)命題邏輯》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《離散數(shù)學(xué)命題邏輯》PPT課件.ppt（37頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第一章命題邏輯,命題與聯(lián)結(jié)詞,邏輯,研究人類思維的科學(xué)。公元前四世紀(jì)亞里斯多德《工具論》奠定了邏輯學(xué)的理論基礎(chǔ)。中國最早的一部邏輯專著－－《墨經(jīng)》也創(chuàng)造了一個(gè)比較完整的邏輯體系。,形式邏輯,辨證邏輯,數(shù)理邏輯,,數(shù)理邏輯,數(shù)理邏輯是一門用數(shù)學(xué)方法來研究推理規(guī)律的科學(xué)。所謂數(shù)學(xué)方法主要是指引進(jìn)一套符號(hào)體系的方法，所以數(shù)理邏輯也稱做符號(hào)邏輯。,（創(chuàng)始人：十七世紀(jì)，德國數(shù)學(xué)家萊布尼茲）,形式符號(hào)體系,由于自然語言存在模棱兩可、含糊的特性，所以有必要引入形式化語言。形式化語言在數(shù)理邏輯中稱為目標(biāo)語言。例如：今天晚上八點(diǎn)中央一臺(tái)播放連續(xù)劇或紀(jì)錄片。我吃蘋果或雪梨。[定義]目標(biāo)語言：具有單一、明確的含義的語言。（基本元素是命題）[定義]形式符號(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)系。公理集合論。主要研究在消除已知集合論悖論的情況下，用公理方法把有關(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,中華人民共和國的首都是北京。我們?cè)趯W(xué)習(xí)《離散數(shù)學(xué)》的數(shù)理邏輯部分。所有素?cái)?shù)都是奇數(shù)。雪是黑色的。,命題示例2,某些感嘆句、祈使句、疑問句等沒有真假之分，所以不是命題。明天開會(huì)嗎？多美妙??！請(qǐng)進(jìn)來。全體立正。,判斷語句是否為命題要注意的問題：,目前無法確定真值，但從本質(zhì)而言，真值存在的語句是命題。例：(1)別的星球上有生物。(2)2046年世界杯在中國舉行。真值因時(shí)因地而異的判斷性陳述句是命題。例：(1)現(xiàn)在是上午。(2)今天下雨。含有未確定內(nèi)容的代詞，不能判斷真假的語句不是命題。例：(1)1+101=110。當(dāng)1和101是二進(jìn)制數(shù)，語句為真，為十進(jìn)制數(shù)，語句為假。(2)x+y>10。悖論不是命題。例：我正在說慌。,命題的分類,根據(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ù)合命題?！爸袊@得2008奧運(yùn)的主辦權(quán)并且加入了WTO”是復(fù)合命題?！叭绻鸄和B是對(duì)頂角，則角A等于角B”是復(fù)合命題。,命題的表示,[定義]命題標(biāo)識(shí)符：表示命題的符號(hào)，通常是大寫英文字母。[定義]命題符號(hào)化：將表示命題的符號(hào)放在該命題的前面。例：P：北京是中國的首都。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為命題北京是中國的首都）,命題——小結(jié),判斷一句話是否是命題的步驟：1）看它是否是陳述句，如果是疑問句、感嘆句和祈使句則不是命題；2）看它是否是悖論，悖論不是命題，如“我正在說謊”；3）看它真值是否唯一，如果不唯一，則不是命題。,命題與聯(lián)結(jié)詞,命題聯(lián)結(jié)詞,命題聯(lián)結(jié)詞,1.否定：┐2.合?。骸?.析取：∨4.排斥析?。酣?.條件（蘊(yùn)含）：?6.雙條件：?,否定,設(shè)P為命題，P的否定也是一個(gè)命題，記作┐P當(dāng)P為T時(shí)，┐P為F當(dāng)P為F時(shí)，┐P為TP與┐P的關(guān)系如右表例：設(shè)P：上海是個(gè)大城市。則┐P：上海不是一個(gè)大城市?；颍荷虾Ｊ莻€(gè)不大的城市。,合取,設(shè)P、Q是命題，P和Q的合取也是個(gè)命題，記作P∧Q當(dāng)且僅當(dāng)P、Q同時(shí)為T時(shí)，P∧Q為T其他情況下，P∧Q的真值都是F讀作“P并且（與）Q”,合取示例,(1)P:我富有。Q:我快樂。P∧Q：我富有并且快樂。(2)P:我們?nèi)ナ程贸燥?。Q:教室里有三塊黑板。P∧Q:我們?nèi)ナ程贸燥埐⑶医淌依镉腥龎K黑板。注：復(fù)合命題中的原子命題之間無需有一般邏輯意義上的關(guān)聯(lián)，如(2)。,析取,設(shè)P、Q是命題，則P和Q的析取也是個(gè)命題，記作P∨Q。當(dāng)且僅當(dāng)P、Q同時(shí)為F時(shí)，P∨Q為F其他情況下，P∨Q的真值都是T讀作“P或Q”（與自然語言中的“或”不完全相同，是兼并或）,析取例子,例：(1)P：猴子吃香蕉。Q：猴子吃橘子。猴子吃香蕉或者吃橘子＝？P∨Q(2)P：他明天早上吃蛋糕。Q：他明天早上喝牛奶。P∨Q＝？他明天早上吃蛋糕或者喝牛奶。(3)P:我明天早上9點(diǎn)在家看書。Q:我明天早上9點(diǎn)出去打球。我明天早上9點(diǎn)在家看書或出去打球＝P∨Q？,,排斥析取,設(shè)P、Q是命題，P和Q的排斥析取也是個(gè)命題，記作P▽Q當(dāng)且僅當(dāng)P和Q的真值不相同時(shí)，P▽Q為T，其他情況下,P▽Q的真值都是F讀作“P或Q”（排斥或）,排斥析取示例,指出下列命題中的“或”是析取還是排斥析取今晚我去看演出或在家里看電視現(xiàn)場(chǎng)轉(zhuǎn)播。他是一百米冠軍或跳高冠軍。派小王或小趙出差去上海。派小王或小趙中的一個(gè)出差去上海。2、3為析取，1、4為排斥析取,條件/蘊(yùn)含,設(shè)P、Q是命題，P對(duì)于Q的條件命題記為P→Q，或稱為P蘊(yùn)含Q。當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時(shí)，P→Q的真值為F，其他情況，P→Q的真值為T。讀作“如果（若）P，則Q”、“Q是P的必要條件”、“僅當(dāng)Q為真時(shí)，P為真”稱P為前件，Q為后件。,條件示例,P：天不下雨Q：我去看電影如果天不下雨，那么我去看電影：P→Q。P：我不到學(xué)校去。Q：我生病。P→Q：如果我不到學(xué)校去，那么我生病。P：我去踢足球。Q：我有時(shí)間。僅當(dāng)我有時(shí)間，我去踢足球。,P?Q,雙條件,P、Q是命題，P和Q的雙條件命題記作：P?Q當(dāng)P和Q的真值相同時(shí)，P?Q的真值為T，否則P?Q的真值為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：天不下雨Q：我去看足球P?Q：如果天不下雨，我就去看足球，否則，我就不去看足球。P：2＋2＝4Q：雪是白的2＋2＝4當(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┐P→QQ→R(Q∧R)→┐P,天不下雪。如果天不下雪，那么我去看電影。我去看電影，僅當(dāng)我有時(shí)間。如果我去看電影且我有時(shí)間，那么天不下雪。,聯(lián)結(jié)詞———小結(jié),1.復(fù)合命題的真值只取決于構(gòu)成它們的原子命題的真值和命題聯(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成立”：A?B2.“僅當(dāng)A成立時(shí),B成立”和“只有A成立時(shí)，B成立”：B?A3.“A成立,否則B成立”：?A?B。4.遇到“或”，就需要考察兩件事情可否同時(shí)發(fā)生，若不能同時(shí)，則是▽，否則用“?”。,聯(lián)結(jié)詞運(yùn)算順序,優(yōu)先級(jí)從高到底排列：┐、∧/∨/▽、→、?,命題（合式）公式,[定義]命題合式公式：(1)單個(gè)命題變?cè)旧硎且粋€(gè)命題合式公式。(2)如果A是合式公式，則┐A是命題合式公式。(3)如果A和B是合式公式，則A∧B,A∨B、A▽B、A→B、A?B都是命題合式公式。(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)((P→Q)∧(Q→R))?(S?T)(3)(P→Q)→(∧Q)(4)((P→Q)，(P∧Q)→Q),(1)和(2)是命題合式公式,重點(diǎn)掌握,命題的定義和判定。命題常量、命題變?cè)母拍?。命題聯(lián)結(jié)詞命題（合式）公式的定義符號(hào)化復(fù)雜命題和用自然語言敘述命題；,┐、∧、∨、▽、→、?的定義,課堂練習(xí),以符號(hào)形式寫出下列命題：上海到北京的14次列車是下午五點(diǎn)半或六點(diǎn)開。(2)他雖聰明但是不用功。(3)除非你努力，否則你將失敗。(4)如果你來了，他唱不唱歌將由你是否伴奏決定。,