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

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

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