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

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

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