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

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

1、離散數(shù)學(xué)命題邏輯(Proposition)主講教師：吳旭第一章????命題邏輯數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科。所謂數(shù)學(xué)方法是指:用一套數(shù)學(xué)的符號系統(tǒng)來描述和處理思維的形式與規(guī)律。因此,數(shù)理邏輯又稱為符號邏輯。本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯。首先引入命題、命題公式等概念。然后,在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊含關(guān)系,并給出推理規(guī)則,進行命題演繹。主要內(nèi)容如下：命題和命題聯(lián)結(jié)詞命題公式與翻譯命題公式的等值關(guān)系和蘊含關(guān)系對偶與范式命題演算的推理理論命題和命題聯(lián)結(jié)詞一、命題的概念命題：是能分辨真假的陳述句。例1判斷下列語句是否是

2、命題。（1）空氣是人生存所必需的。（2）請把門關(guān)上。（3）南京是中國的首都。（4）你吃飯了嗎？（5）x=3。（6）啊，真美呀！(7)明年春節(jié)是個大晴天。解語句（1）,（3）,（5），(7)是陳述句（1）、（3）、(7)是命題用真值來描述命題是“真”還是“假”。分別用“1”和“0”表示命題用大寫的拉丁字母A、B、C、……P、Q、……或　　者帶下標(biāo)的大寫的字母來表示。例2判斷下列陳述句是否是命題。P：地球外的星球上也有人；Q：小王是我的好朋友；解P、Q是命題二、命題聯(lián)結(jié)詞原子命題：由簡單句形成的命題。復(fù)合命題：由一個或幾個原子命題通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)

3、成的命題。例3A：李明既是三好學(xué)生又是足球隊員。B：張平或者正在釣魚或者正在睡覺。C：如果明天天氣晴朗，那么我們舉行運動會。定義五種聯(lián)結(jié)詞（或稱命題的五種運算）。1.否定“?”定義1-1設(shè)P是一個命題，利用“?”和P組成的復(fù)合命題稱為P的否命題，記作“?P”(讀作“非P”)。命題P取值為真時，命題?P取值為假；命題P取值為假時，命題?P取值為真。例4設(shè)P：上海是一個城市；Q：每個自然數(shù)都是偶數(shù)。則有?P：上海不是一個城市;?Q：并非每個自然數(shù)都是偶數(shù)。P?P10012．合取“∧”定義1-2設(shè)P和Q是兩個命題，由P、Q利用“∧”組成的復(fù)合命題，稱為

4、合取式復(fù)合命題，記作“P∧Q”（讀作“P且Q”）。當(dāng)且僅當(dāng)命題P和Q均取值為真時，P∧Q才取值為真。例5設(shè)P：我們?nèi)タ措娪?。Q：房間里有十張桌子。則P∧Q表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子?！盤QP∧Q0000101001113.析取“∨”定義1-3由命題P和Q利用“∨”組成的復(fù)合命題，稱為析取式復(fù)合命題，記作“P∨Q”（讀作“P或Q”）。當(dāng)且僅當(dāng)P和Q至少有一個取值為真時，P∨Q取值為真。PQP∨Q000011101111例6將命題“他可能是100米或400米賽跑的冠軍?！狈柣?。解令P：他可能是100米賽跑冠軍；Q：他可能是400米賽跑冠

5、軍。則命題可表示為P∨Q。設(shè)P、Q是兩個命題，P異或Q是一個復(fù)合命題，記作P∨Q。例7今天晚上我在家看電視或去劇場看戲。令P：今天晚上我在家看電視。Q：今天晚上我去劇場看戲例7中的命題可表示為P∨Q，或者表示為（P∧?Q∨(?P∧Q)。由于“∨”可用“∨”，“∧”和“?”表示，故我們不把它當(dāng)作基本聯(lián)結(jié)詞。PQP∨Q0000111011104.蘊含“→”定義1-4由命題P和Q利用“→”組成的復(fù)合命題，稱為蘊含式復(fù)合命題，記作“P→Q”（讀作“如果P，則Q”）。當(dāng)P為真，Q為假時，P→Q為假，否則P→Q為真。PQP→Q001011100111例8將命

6、題“如果我得到這本小說，那么我今夜就讀完它。”符號化。解令P：我得到這本小說；Q：我今夜就讀完它。于是上述命題可表示為P→Q。例9若P：雪是黑色的；Q：太陽從西邊升起；R：太陽從東邊升起。則P→Q和P→R所表示的命題都是真的.5．等值“?”定義1-5由命題P和Q，利用“?”組成的復(fù)合命題，稱為等值式復(fù)合命題，記作“P?Q”（讀作“P當(dāng)且僅當(dāng)Q”）。當(dāng)P和Q的真值相同時,P?Q取真,否則取假。PQPQ001010100111例10非本倉庫工作人員，一律不得入內(nèi)。解令P：某人是倉庫工作人員；Q：某人可以進入倉庫。則上述命題可表示為P?Q。例11黃山比

7、喜馬拉雅山高，當(dāng)且僅當(dāng)3是素數(shù)令P：黃山比喜馬拉雅山高；Q：3是素數(shù)本例可符號化為P?Q從漢語的語義看，P與Q之間并無聯(lián)系，但就聯(lián)結(jié)詞?的定義來看，因為P的真值為假，Q的真值為真，所以P?Q的真值為假。對于上述五種聯(lián)結(jié)詞，應(yīng)注意到：復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真值，而與這些原子命題的內(nèi)容含義無關(guān)。三、命題符號化利用聯(lián)結(jié)詞可以把許多日常語句符號化?；静襟E如下：（1）從語句中分析出各原子命題，將它們符號化；（2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示。例12用符號形式表示下列命題。（1）　如果明天早上下

8、雨或下雪，那么我不去學(xué)校（2）　如果明天早上不下雨且不下雪，那么我去學(xué)校。（3）　如果明天早上不是雨夾雪，那么我去學(xué)校。（4）　只有當(dāng)明