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

《離散數(shù)學(xué)命題邏輯.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

2、片。我吃蘋果或雪梨。[定義]目標(biāo)語言：具有單一、明確的含義的語言。（基本元素是命題）[定義]形式符號體系：由目標(biāo)語言和一些規(guī)定的公式與符號構(gòu)成的體系為何學(xué)習(xí)數(shù)理邏輯程序=算法+數(shù)據(jù)結(jié)構(gòu)算法=邏輯+控制數(shù)理邏輯的主要內(nèi)容數(shù)理邏輯內(nèi)容豐富，但其主要包括“兩個演算”加“四論”，即：邏輯演算。包括命題演算和謂詞演算證明論。主要研究數(shù)學(xué)理論系統(tǒng)的相容性（即不矛盾、協(xié)調(diào)性）的證明。遞歸論（能行性理論）。自從電子計(jì)算機(jī)發(fā)明后，迫切需要在理論上弄清計(jì)算機(jī)能計(jì)算哪些函數(shù)。遞歸論研究能行可計(jì)算的理論，它為能行可計(jì)算的函數(shù)找出各種理

3、論上精確化的嚴(yán)密類比物。模型論。主要是對各種數(shù)學(xué)理論系統(tǒng)建立模型，并研究各模型之間的關(guān)系以及模型與系統(tǒng)之間的關(guān)系。公理集合論。主要研究在消除已知集合論悖論的情況下，用公理方法把有關(guān)集合的理論充分發(fā)展下去。現(xiàn)代數(shù)理邏輯命題邏輯研究的內(nèi)容命題邏輯也稱為命題演算研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系.(1)什么是命題？(2)如何表示命題？(3)如何由一些前提推導(dǎo)出一些結(jié)論?命題與聯(lián)結(jié)詞命題聯(lián)結(jié)詞命題的概念具有判斷內(nèi)容（非真即假）的陳述句稱為命題。能夠確定或分辨其真假的陳述句。命題有一個值，稱為真值，真值

4、只有“真”和“假”兩種，分別用“T”（或“1”）和“F”（或“0”）表示。命題中的判斷正確，其真值為真，稱為真命題，命題中的判斷錯誤，真值為假，稱為假命題。命題示例1中華人民共和國的首都是北京。我們在學(xué)習(xí)《離散數(shù)學(xué)》的數(shù)理邏輯部分。所有素?cái)?shù)都是奇數(shù)。雪是黑色的。命題示例2某些感嘆句、祈使句、疑問句等沒有真假之分，所以不是命題。明天開會嗎？多美妙啊！請進(jìn)來。全體立正。判斷語句是否為命題要注意的問題：目前無法確定真值，但從本質(zhì)而言，真值存在的語句是命題。例：(1)別的星球上有生物。(2)2046年世界杯在中國舉行。

5、真值因時因地而異的判斷性陳述句是命題。例：(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ù)”

6、都是原子命題，“2不是素?cái)?shù)”是復(fù)合命題“明天下雪或明天下雨”是復(fù)合命題。“中國獲得2008奧運(yùn)的主辦權(quán)并且加入了WTO”是復(fù)合命題。“如果A和B是對頂角，則角A等于角B”是復(fù)合命題。命題的表示[定義]命題標(biāo)識符：表示命題的符號，通常是大寫英文字母。[定義]命題符號化：將表示命題的符號放在該命題的前面。例：P：北京是中國的首都。Q：北京承辦2008年奧運(yùn)。命題的表示（續(xù)）[定義]命題常量：表示確定命題的命題標(biāo)識符。[定義]命題變元：可表示任意一個（原子或復(fù)合）命題的命題標(biāo)識符，就稱為命題變元。當(dāng)命題變元表示原子命

7、題時，該變元稱為原子變元。當(dāng)命題變元P用一個特定命題去取代時，才能確定P的真值，這時也稱對P進(jìn)行指派。例：若P是命題變元，P：北京是中國的首都。（指派P為命題北京是中國的首都）命題——小結(jié)判斷一句話是否是命題的步驟：1）看它是否是陳述句，如果是疑問句、感嘆句和祈使句則不是命題；2）看它是否是悖論，悖論不是命題，如“我正在說謊”；3）看它真值是否唯一，如果不唯一，則不是命題。命題與聯(lián)結(jié)詞命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞1.否定：┐2.合?。骸?.析?。骸?.排斥析?。酣?.條件（蘊(yùn)含）：?6.雙條件：?否定設(shè)P為命題，P的否

8、定也是一個命題，記作┐P當(dāng)P為T時，┐P為F當(dāng)P為F時，┐P為TP與┐P的關(guān)系如右表例：設(shè)P：上海是個大城市。則┐P：上海不是一個大城市?；颍荷虾Ｊ莻€不大的城市。P┐PFTTF合取設(shè)P、Q是命題，P和Q的合取也是個命題，記作P∧Q當(dāng)且僅當(dāng)P、Q同時為T時，P∧Q為T其他情況下，P∧Q的真值都是F讀作“P并且（與）Q”PQP∧QFFFFTFTFFTTT合取示例(1)P:我富有。Q:我快樂