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

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

1、第一部分 數(shù)理邏輯,2,概述:基本概念,邏輯學(xué)的分類: 辯證邏輯 形式邏輯 辯證邏輯 以辯證法認識論的世界觀為基礎(chǔ)的邏輯學(xué) 形式邏輯 對思維的形式結(jié)構(gòu)和規(guī)律進行研究的類似于語法的一門工具的學(xué)科,3,概述:基本概念,思維的形式結(jié)構(gòu) 包括概念、判斷和推理之間的結(jié)構(gòu)和聯(lián)系 形式邏輯的側(cè)重點 與其說是注重論證本身，不如說注重的是論證形式,形式邏輯的一般格式就是三段論。 例：蘇格拉底三段論： 所有的人都是要死的， 蘇格拉底是人， 所以，蘇格拉底是要死的。,4,概述:基本概念,傳統(tǒng)邏輯和數(shù)理邏輯 19世紀中葉以前的形式邏輯是傳統(tǒng)邏輯 19世紀中葉以后發(fā)展起來的現(xiàn)代形式邏輯，通常稱為數(shù)理邏輯,

2、5,什么是數(shù)理邏輯,數(shù)理邏輯：以數(shù)學(xué)的方法研究思維規(guī)律和推理過程的科學(xué)。 它首先引進一套符號體系，規(guī)定一些規(guī)則，導(dǎo)出一些定律，然后借助于這些符號、規(guī)則、定律，將邏輯推理的過程在形式上變得像代數(shù)演算一樣，因此數(shù)理邏輯又稱符號邏輯。 數(shù)理邏輯是傳統(tǒng)邏輯的發(fā)展，是現(xiàn)代形式邏輯,6,微積分,力學(xué)、機械工程,人類體力勞動自動化,數(shù)理邏輯,人工智能、知識工程,腦力勞動自動化,7,數(shù)理邏輯,命題邏輯（數(shù)理邏輯的基礎(chǔ)，以命題為研究對象，研究基于命題的符號邏輯體系及推理規(guī)律，也稱命題演算）。 主要內(nèi)容： 、命題與聯(lián)結(jié)詞 、命題公式、翻譯和真值表 、重言式 、命題聯(lián)結(jié)詞的擴充 、范式 、命題演算的推理規(guī)則和證明方

3、法 謂詞邏輯（對命題邏輯的深入研究）。,,8,第一章 命題邏輯,1 命題與聯(lián)結(jié)詞 一、命題 1、什么是命題？ 命題是陳述客觀外界發(fā)生事情的陳述句。 命題或為真或為假的陳述句。 特征： 陳述句 真假必居其一，且只居其一。,1 命題與聯(lián)結(jié)詞,9, 中國是一個發(fā)展中國家。 人是由猴進化而來的。 早上好！ 王侯將相，寧有種乎？ 己所不欲，勿施于人！ 宇宙是大爆炸形成的。 我正在說謊。 這道題太難。 2、命題的真值。 一個命題的真或假稱為命題的真值，簡稱值。 由于命題只有真假兩個值，所以命題邏輯也稱二值邏輯。 以T（或1）表示命題的真值為真，F(xiàn)（或0）表示命題的真值為假,,,,1 命題與聯(lián)結(jié)詞,EX1：

4、,10,3、命題的分類與表示,分類根據(jù)其真值分類： 真命題。 假命題。 根據(jù)其復(fù)雜程度分類： 簡單命題或原子命題。 復(fù)合命題。,1 命題與聯(lián)結(jié)詞,11,命題的抽象表示 在數(shù)理邏輯中，通常用大(小)寫字母表示命題，P、Q、R，或用帶下標的大寫字母Pi、Qi、Ri 或者數(shù)字（1）、（2）、 。 表示命題的符號稱為命題標識符，如P、 Q、 R、 Pi、Qi、Ri 。 EX2： P：4是偶數(shù)； Q：煤是白的。 P1：離散數(shù)學(xué)考試，張三和李四都及格了。,1 命題與聯(lián)結(jié)詞,12,命題的抽象表示,一個命題標識符如果表示確定的命題，就稱為命題常量。 如果命題標識符只表示任意命題的位置標志，就稱為命題變元。 則

5、命題的抽象為：取值為T（或1）或F（或0）的P、Q、R等符號。 若P取值T（或1），則表示P為真命題； 若P取值F（或0），則表示P為假命題；,1 命題與聯(lián)結(jié)詞,13,“復(fù)雜命題”,EX3：由簡單命題能構(gòu)造更加復(fù)雜的命題 期中考試，張三沒有考及格。 期中考試，張三和李四都及格了。 期中考試，張三和李四中有人考90分。 如果張三能考90分，那么李四也能考90分。 張三能考90分當且僅當李四也能考90分。,1 命題與聯(lián)結(jié)詞,14,聯(lián)結(jié)詞和復(fù)合命題,上述諸如“沒有”、“如果那么”等詞稱為聯(lián)結(jié)詞。 由聯(lián)結(jié)詞和命題連接而成的更加復(fù)雜命題稱為復(fù)合命題；相對地，不能分解為更簡單命題的命題成為簡單命題。（命題

6、的分類） 復(fù)合命題的真假完全由構(gòu)成它的簡單命題的真假所決定。 注：簡單命題和復(fù)合命題的劃分是相對的。,1 命題與聯(lián)結(jié)詞,15,1、否定聯(lián)結(jié)詞,在 EX3 中，“期中考試，張三沒有考及格”。 P ：“期中考試，張三考試及格了”， 設(shè) P 為一個命題，復(fù)合命題“非P”稱為P的否定式，記為P，“ ”稱為否定聯(lián)結(jié)詞。“P”為真當且僅當P為假。,二、命題聯(lián)結(jié)詞,1 命題與聯(lián)結(jié)詞,16,1、否定聯(lián)結(jié)詞,EX4：求“我們班上所有的同學(xué)都大于18歲”的否定。 P：我們班上所有的同學(xué)都大于18歲。 P：我們班上所有的同學(xué)不都大于18歲。 P：我們班上所有的同學(xué)都不大于18歲。,1 命題與聯(lián)結(jié)詞,17,2、合取聯(lián)

7、結(jié)詞,EX4：“期中考試，張三和李四都及格了。” P 代表：“期中考試張三考試及格了” Q 代表：“期中考試李四考試及格了”。 設(shè)P、Q為兩個命題，復(fù)合命題“P而且Q”稱為P、Q的合取式，記為PQ，“”稱為合取聯(lián)結(jié)詞。 PQ為真當且僅當P 與 Q 為同時為真。,1 命題與聯(lián)結(jié)詞,18,3、析取聯(lián)結(jié)詞,設(shè)P、Q為兩個命題，復(fù)合命題“P或者Q”稱為P、Q的析取式，記為PQ，“”稱為析取聯(lián)結(jié)詞。 PQ為真當且僅當P與Q為中至少有一個為真。,EX4： “期中考試張三或李四中有人考90分?！?P 代表：“期中考試張三考了90分”， Q 代表：“期中考試李四考了90分”。,1 命題與聯(lián)結(jié)詞,19,“可兼或

8、”與“排斥或”,日常語言中“或”有三種標準用法， EX5： 張三或者李四考了90分。 第一節(jié)課上數(shù)學(xué)課或者上政治課。 去教學(xué)樓需要6分鐘或8分鐘。,差異在于： 當構(gòu)成他們的簡單命題都真時，（1）為真，（2）為假。 （1）稱為“可兼或”，（2）稱為“排斥或”，（3）非聯(lián)結(jié)詞，表示近似的數(shù)。 （1）可表示為PQ，（2）卻不能。 注意：不能見了“或”就表示為PQ。,1 命題與聯(lián)結(jié)詞,20,EX6：求“今天下雪且今天下雨”的否定。 P：今天下雪。 Q：今天下雨。 練習(xí)：求“今天不下雪且今天不下雨”的否定,1 命題與聯(lián)結(jié)詞,21,4、蘊含聯(lián)結(jié)詞,EX4：“如果張三能考90分，那么李四也考90分?！?

9、P ：“張三考90分”。 Q ：“李四考90分”。 設(shè)P、Q為兩個命題，復(fù)合命題“如果P，則Q”稱為P對Q的蘊含式，記為PQ，其中又稱P為此蘊含式的前件，稱Q為此蘊含式的后件，“ ”稱為蘊含聯(lián)結(jié)詞。 “PQ”為假當且僅當P真而Q假。,1 命題與聯(lián)結(jié)詞,22,EX7：如果你今年離散數(shù)學(xué)考100分，那么就獎勵你100元。 P：你今年離散數(shù)學(xué)考100分。 Q：獎勵你100元。,1 命題與聯(lián)結(jié)詞,1,23,pq 的邏輯關(guān)系：q 為 p 的必要條件 “如果 p，則 q ” 的不同表述法很多： 若 p，就 q 只要 p，就 q p 僅當 q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否則非

10、p， 當 p 為假時，pq 為真 常出現(xiàn)的錯誤：不分充分與必要條件,24,,例 設(shè) p:天冷，q:小王穿羽絨服， 將下列命題符號化 (1) 只要天冷，小王就穿羽絨服. (2) 因為天冷，所以小王穿羽絨服. (3) 若小王不穿羽絨服，則天不冷. (4) 只有天冷，小王才穿羽絨服. (5) 除非天冷，小王才穿羽絨服. (6) 除非小王穿羽絨服，否則天不冷. (7) 如果天不冷，則小王不穿羽絨服. (8) 小王穿羽絨服僅當天冷的時候.,注意： p q與 q p 等值（真值相同）,pq,pq,pq,pq,qp,qp,qp,qp,25,5、等價聯(lián)結(jié)詞,EX4： “張三能考90分當且僅當

11、李四也能考90分?！?P ：“張三考90分?！?Q ：“李四考90分?！?設(shè)P、Q為兩個命題，復(fù)合命題“P當且僅當Q”稱為P、Q的等價式，記為PQ，“”稱為等價聯(lián)結(jié)詞。 PQ為真當且僅當P與Q同時為真或同時為假。,,1 命題與聯(lián)結(jié)詞,26,“注意”,上述五個聯(lián)結(jié)詞來源于日常使用的相應(yīng)詞匯，但并不完全一致，在使用時要注意： 以上聯(lián)結(jié)詞組成的復(fù)合命題的真假值一定要根據(jù)它們的定義去理解，而不能據(jù)日常語言的含義去理解。 不能“對號入座”，如見到“或”就表示為“”。 有些詞也可表示為這五個聯(lián)結(jié)詞，如“但是”也可表示為“”。 在今后我們主要關(guān)心的是命題間真的假值的關(guān)系，而不討論命題的內(nèi)容。,1 命題與聯(lián)結(jié)

12、詞,27,EX1： 鐵和氧化合，但鐵和氮不化合。 如果我下班早，就去商店看看，除非我很累。 李四是經(jīng)管院的學(xué)生，他住在312室或313室。,1 命題與聯(lián)結(jié)詞,三、復(fù)合命題,28,鐵和氧化合，但鐵和氮不化合。 P：“鐵和氧化合” Q：“鐵和氮化合” 則用符號表示: P(Q) 如果我下班早，就去商店看看，除非我很累。 P：“我很累” Q：“我下班早” R：“我去商店看看” 則用符號表示: (P)(QR) 或者可以表示為： ((P)Q)R), 命題公式、翻譯和真值表,29,李四是經(jīng)管院的學(xué)生，他住在312室或313室。 P：“李四是經(jīng)管院的學(xué)生?！?Q：“李四住312室?！?R：“李四住313室?！?/p>

13、 則用符號表示: P((Q( R))((Q)R)) 或者可以表示為： P((QR)((QR))), 命題公式、翻譯和真值表,30,復(fù)合命題,由原子命題經(jīng)命題聯(lián)結(jié)詞可構(gòu)成各種形式的復(fù)合命題，在復(fù)合命題中涉及到括號的使用問題，目前均使用圓括號，為減少括號的使用，在此作下列規(guī)定： 規(guī)定5個聯(lián)結(jié)詞的結(jié)合能力強弱順序為：“否定”、“合取”、“析取”、“蘊含”、“等價”，即，這五個邏輯運算的優(yōu)先順序為、、、、 。凡符合此順序者，括號均可除去。, 命題公式、翻譯和真值表,31,小結(jié),命題及其符號P、Q、R。 構(gòu)成復(fù)合命題的聯(lián)結(jié)詞、、、、 ，以及由聯(lián)結(jié)詞構(gòu)成的復(fù)合命題及其真假值。 注意：有了命題和命題聯(lián)結(jié)詞，

14、為了進一步的研究，今后，將只注重命題的真假值，而并不注意其內(nèi)容含義，對命題聯(lián)結(jié)詞，只承認它由真值表定義，而不理會它的實際含義，這樣，就可以在命題與命題聯(lián)結(jié)詞的基礎(chǔ)上建立起一個形式系統(tǒng)。,32,命題聯(lián)結(jié)詞的擴充,不可兼析取（排斥或）“”或“”或 “”：設(shè)P和Q是兩個命題，稱P Q為P和Q的不可兼析取。 規(guī)定： P Q的值為真，當且僅當P、Q的真值不相同時，否則P Q的值為F。 其真值表如下：,4命題聯(lián)結(jié)詞的擴充,33,不可兼析取,“” 有以下性質(zhì)： P QQ P (P Q) RP (Q R) P(Q R)(PQ) (PR) (P Q)(PQ)(PQ) (P Q) (PQ),4命題聯(lián)結(jié)詞的擴充,3

15、4,蘊含否定（條件非 ）,蘊含否定或條件非： 設(shè)P和Q是兩個命題，稱P Q為P和Q的蘊含否定或條件非。 規(guī)定：P Q的值為T，當且僅當P的真值為T，Q的真值為F。其真值表如下： 由上表可知：P Q(PQ),4命題聯(lián)結(jié)詞的擴充,35,謝佛（與非）,謝佛或與非 “” ：設(shè)P和Q是兩個命題，稱PQ為P和Q的與非。 規(guī)定：當且僅當P和Q真值都是T時，PQ為F。 其真值表如下： 由真值表可得出：PQ(PQ),4命題聯(lián)結(jié)詞的擴充,36,與非,“” 有以下性質(zhì)： PP (PP) P (PQ)(PQ) (PQ)PQ (PP)(QQ)PQ(PQ)PQ,4命題聯(lián)結(jié)詞的擴充,37,魏泊（或非）,魏泊或稱

16、作或非“”：設(shè)P和Q是兩個命題，稱PQ為P和Q的或非 規(guī)定：當且僅當P和Q的真值都為F時，PQ的真值為T 其真值表如下： 由真值表可得出：PQ(PQ),4命題聯(lián)結(jié)詞的擴充,38,或非（續(xù)）,“” 有以下性質(zhì)： PP(PP)P (PQ)(PQ) (PQ)PQ (PP)(QQ)PQPQ,4命題聯(lián)結(jié)詞的擴充,39,是否每個符號串都是命題呢？ PQ 、 PQ 什么樣的符號串才能表示命題呢？ 如下命題公式定義的符號串表示的才是命題。, 命題公式、翻譯和真值表 一、命題公式（合式公式或公式）, 命題公式、翻譯和真值表,40,命題公式的定義,由命題變元經(jīng)命題聯(lián)結(jié)詞可構(gòu)成命題邏輯公式，亦可叫命題公式或

17、公式。 定義1:命題公式是由命題變元和聯(lián)結(jié)詞按以下規(guī)則組成的符號串 原子命題變元本身是一個命題公式； 如果P是命題公式，則 P 也是命題公式； 如果P、Q是命題公式，則PQ、PQ、 PQ和PQ都是命題公式； 只有有限次地應(yīng)用構(gòu)成的符號串才是命題公式。 命題公式是一個按上述法則由命題變元、命題聯(lián)結(jié)詞及圓括號組成的符號串或字符串。, 命題公式、翻譯和真值表,41,下列符號串都是命題公式：,P P(Q) P(P) P(P) P(P) (P(P))((P)(PR)), 命題公式、翻譯和真值表,42,下列符號串是否為命題公式？,PQ PQ PQ R, 命題公式、翻譯和真值表,43,一些注意,定義2是歸納

18、定義，而不是循環(huán)定義。 （1）是奠基，（2）、（3）是歸納步驟，（4）是界限。 如果我們規(guī)定聯(lián)結(jié)詞運算的優(yōu)先次序為： 、、、、 ，則，PQR也是命題公式。 有了聯(lián)結(jié)詞和命題公式概念，我們就可以把自然語言中的有些語句，翻譯成數(shù)理邏輯中的符號形式。, 命題公式、翻譯和真值表,44,二、命題的翻譯,EX1：將下列語句翻譯為命題公式 他既聰明，又用功。 他雖聰明但不用功。 張明正在睡覺或游泳。 除非他通知我，否則我不參加會議。 張明與李強都可以做這件事。, 命題公式、翻譯和真值表,45,二、命題的翻譯,EX2：設(shè) P：“李明是男生”； Q：“李明是足球隊隊員”； R：“李明是班干部” 用日常語言敘述下

19、列命題： PQ QR PQR PQR, 命題公式、翻譯和真值表,46,三、指派和真值表,命題公式的真假由其中命題變元的值完全確定。 命題公式中所有命題變元的一組確定的取值稱為公式的一組真值指派。 公式值的確定是按公式中聯(lián)結(jié)詞出現(xiàn)的先后次序及括號順序逐步應(yīng)用命題聯(lián)結(jié)詞的真值表規(guī)定而得到的，所有的指派構(gòu)成的公式的值即組成了此公式的真值表。, 命題公式、翻譯和真值表,47,EX3：構(gòu)造(PQ) R的真值表, 命題公式、翻譯和真值表,48,EX4：構(gòu)造(PQ)(PQ)的真值表, 命題公式、翻譯和真值表,49,EX5：構(gòu)造(PQ) P的真值表, 命題公式、翻譯和真值表,50,3 等價重言式和蘊含重言式,

20、練習(xí)：構(gòu)造((PQ)(QR))(PR))的真值表,((PQ)(QR))(PR)),51,命題公式的類型,定義2：一個公式如果對其所有指派均取值為真，則稱此類型公式為永真公式或叫重言式。 反之，一個公式如果對其所有指派均取假值，則稱此類型公式為永假公式或叫矛盾。 定義3：一個公式如果至少存在一個指派使其取值為真，則稱此公式為可滿足公式。 重言式特性 重言式的否定是矛盾，矛盾的否定是重言式。 兩個重言式的合取、析取、蘊含、等價均為重言式。 若兩個公式的等價是重言式，則此兩公式對任何指派必同真假(EX4)。, 命題公式、翻譯和真值表,52,命題公式的類型,命題公式,可滿足公式,永真式（或重言式）,可

21、真可假式,不可滿足公式 （永假式或矛盾式）,,, 命題公式、翻譯和真值表,53,判斷下列公式的類型,例 A= (qp) qp,54,例 B = (pq) q,55,例 C= (pq) r,56,3 等價重言式和蘊含重言式,EX1：構(gòu)造PQ與PQ的真值表,(PQ) (PQ),3 等價重言式和蘊含重言式,57,等價重言式,設(shè)A、B為兩個命題公式，P1，P2Pn是所有出現(xiàn)于A和B的命題變元，如果對于命題變元P1，P2Pn的任何一組真值指派，公式A和B都相同，即AB是永真式，則稱A與B是等價重言式或是等價的（邏輯等價的），記作AB。 由上例知： (PQ)(PQ),3 等價重言式和蘊含重言式,58,EX

22、2：證明 PQ (PQ)(QP),兩者的真值表相等，故PQ(PQ)(QP) 不難驗證：P P PP P (PP)Q Q P P QQ,3 等價重言式和蘊含重言式,59,注意：“” ，“”的區(qū)別和聯(lián)系：,區(qū)別： （1）“”是命題聯(lián)結(jié)詞，AB是一個命題公式，該公式取值可以是真，可以是假。 （2）“”不是命題聯(lián)結(jié)詞，而是公式的等價關(guān)系符，AB不代表命題，而表示的是命題A、B有完全相同的真值。 聯(lián)系： AB當且僅當AB是永真式。,3 等價重言式和蘊含重言式,60,等價公式的性質(zhì),自反性：即對任意公式A，有AA； 對稱性：即對任意公式A和B，若AB，則BA； 傳遞性：即對任意公式A和B

23、，C，若AB，BC,則AC。,3 等價重言式和蘊含重言式,61,設(shè)P、Q、R是命題變元，下表中列出了24個最基本的等值式:,命題邏輯的基本等式,,3 等價重言式和蘊含重言式,62,命題邏輯的基本等式,基本的等值式,,,,3 等價重言式和蘊含重言式,63,命題聯(lián)結(jié)詞的歸約(完備集),由(PQ)(PQ)(QP)。故可把包含的公式等價變換為包含“”和“”的公式。 由PQ PQ，說明包含“”的公式可以變換為包含“”和“”的公式。 由PQ ( P Q)，PQ ( P Q），說明“”和“”可以相互代替、故由“”、“”、“”、“”、“”這五個聯(lián)結(jié)詞組成命題公式，必可以由 、、或 、組成的命題公式所代替。 故

24、任意命題公式都可由僅包含 、或 、的命題公式等價代換。,命題聯(lián)結(jié)詞的歸約,64,定義 在一個聯(lián)結(jié)詞的集合中，如果一個聯(lián)結(jié)詞可 由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余 的聯(lián)結(jié)詞，否則稱為獨立的聯(lián)結(jié)詞. 例如,在聯(lián)結(jié)詞集, , , , 中，由于 pqpq, 所以，為冗余的聯(lián)結(jié)詞; 類似地，也是冗余的 聯(lián)結(jié)詞. 又在, , 中，由于 pq(pq)， 所以，是冗余的聯(lián)結(jié)詞. 類似地，也是冗余的聯(lián) 結(jié)詞.,65,定義 設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n1) 元 命題公式都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表 示，則稱S是聯(lián)結(jié)詞完備集. 說明： 若S是聯(lián)結(jié)詞全功能集，則任何命題公式都

25、可用S 中的聯(lián)結(jié)詞表示. 若S1, S2是兩個聯(lián)結(jié)詞集合，且S1 S2. 若S1是完備集，則S2也是完備集.,66,聯(lián)結(jié)詞的完備集實例,(1) S1=, , , (2) S2=, , , , (3) S3=, (4) S4=, (5) S5=, 而, 等則不是聯(lián)結(jié)詞完備集.,67,等價公式的代入規(guī)則與替換規(guī)則,代入規(guī)則：在等價式中，將某一命題變元(原子)出現(xiàn)的每處用另一個命題公式代入所得到的公式仍是等價式。 EX3: 求證(PQ)(PQ)為永真式 證： RRT ，即RR為永真式 現(xiàn)用公式PQ代入上述公式中的命題變元R 則得(PQ)(PQ)T 故 (PQ)(PQ)為永真式。 如：在PQ

26、PQ 中， 若用公式(SR)代替P，則得到新的等價公式： (SR)Q (SR)Q,3 等價重言式和蘊含重言式,68,替(置)換規(guī)則：設(shè)A1是命題公式A的子公式，若A1B1，如果將A中的A1用B1來替換得到公式B，則AB。（如果A1是命題公式的一部分，且A1本身也是一個命題公式，則稱A1為公式A的子公式） EX4:求證:(PQ)(RQ) (PR)Q 證： (PQ)(RQ) (P Q)(RQ) (P Q)(RQ) (PR)Q (PR)Q (PR)Q,3 等價重言式和蘊含重言式,69,“代入規(guī)則”和“替換規(guī)則”的區(qū)別： 代入只對永真式適用，而替換可以對任何公式進行； 代入必須處處進行，而替換可以處處

27、替換也可以部分替換； 代入只針對命題變元進行，而替換則可以針對任何子公式、包括命題變元而進行。,3 等價重言式和蘊含重言式,70,應(yīng)用舉例證明兩個公式等值,例 證明 p(qr) (pq)r 證 p(qr) p(qr) （蘊涵等值式，置換規(guī)則） (pq)r （結(jié)合律，置換規(guī)則） (pq)r （德摩根律，置換規(guī)則） (pq) r （蘊涵等值式，置換規(guī)則）,說明:也可以從右邊開始演算（請做一遍） 因為每一步都用置換規(guī)則，故可不寫出 熟練后，基本等值式也可以不寫出,71,應(yīng)用舉例證明兩個公式不等值,例 證明: p(qr) (pq) r 用等值演算不能直接證明兩個公式不等值,證明兩

28、 個公式不等值的基本思想是找到一個賦值使一個成 真,另一個成假. 方法一 真值表法（自己證） 方法二 觀察賦值法. 容易看出000, 010等是左邊的 成真賦值，是右邊的成假賦值. 方法三 用等值演算先化簡兩個公式，再觀察.,72,應(yīng)用舉例判斷公式類型,例 用等值演算法判斷下列公式的類型 (1) q(pq) 解 q(pq) q(pq) （蘊涵等值式） q(pq) （德摩根律） p(qq) （交換律，結(jié)合律） p0 （矛盾律） 0 （零律） 由最后一步可知，該式為矛盾式.,73,例 (續(xù)),(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蘊

29、涵等值式） (pq)(pq) （交換律） 1 由最后一步可知，該式為重言式. 問：最后一步為什么等值于1？,74,例 (續(xù)),(3) ((pq)(pq))r) 解 ((pq)(pq))r) (p(qq))r （分配律） p1r （排中律） pr （同一律） 這不是矛盾式，也不是重言式，而是非重言式的可 滿足式.如101是它的成真賦值,000是它的成假賦值.,總結(jié)：A為矛盾式當且僅當A0 A為重言式當且僅當A1 說明：演算步驟不惟一,應(yīng)盡量使演算短些,75,蘊含重言式,設(shè)A、B為兩個命題公式，當且僅當AB為永真式時，稱A永真蘊含B，記作AB。 注意： AB

30、與AB的區(qū)別: (類似于與的區(qū)別) 區(qū)別： “”是命題聯(lián)結(jié)詞。 “”是公式的關(guān)系符號，表示兩個公式之間的關(guān)系。 “AB”是一個復(fù)合命題，它可真可假，而AB表示的命題公式之間的關(guān)系，而非命題。 聯(lián)系： AB成立的充要條件是AB為永真式。,3 等價重言式和蘊含重言式,76,蘊含重言式的性質(zhì),自反性:即對任意公式A，有AA 傳遞性:即對任意公式A、B和C，若AB，BC，則AC 對任意公式A、B和C，若AB，AC，則A (BC) 對任意公式A、B和C，若AC，BC，則ABC 若AT，AB，則BT,3 等價重言式和蘊含重言式,77,蘊含重言式的定理,定理：設(shè)A和B是兩個命題公式，AB的充要條件是AB且B

31、A。 證明： 必要性: 若AB，則AB為永真式，因為AB(AB)(BA) 故AB和BA必為永真，即AB且BA。 充分性： 若AB且BA 則AB和BA為永真 又 AB(AB)(BA) AB為永真式，即AB 。,3 等價重言式和蘊含重言式,78,蘊含重言式的證明方法：,真值表法 EX6：試證，P(PQ)Q 證明：構(gòu)造 P(PQ)Q 的真值表 故P(PQ)Q永真，所以P(PQ)Q，證畢,3 等價重言式和蘊含重言式,79,蘊含重言式的證明方法：,推導(dǎo)法 EX7：P(PQ)Q 證明： P(PQ)Q P(PQ)Q (PP)(PQ) Q (F(PQ))Q (PQ)Q (PQ)Q (P Q)Q P1 1

32、P(PQ)Q,3 等價重言式和蘊含重言式, 1,80,蘊含重言式的證明方法：,分析法 包括兩種： 前件真推導(dǎo)后真方法 假設(shè)前件A為T，若能推導(dǎo)出后件也為真。則條件式永真式。 后件假推導(dǎo)前件假方法： 條件式后件為F，若能推導(dǎo)出前件也為F。則條件式是永真式。,3 等價重言式和蘊含重言式,81,EX8：證明 P(PQ)Q 證明： 第一種方法： 設(shè)P(PQ)為T，則P與(PQ)均為T，由P為T且PQ也為真，知Q必為T。 P(PQ)Q 第二種方法： 設(shè)后件Q為F，此時P有兩種可能： 若P為T，因設(shè)Q為F，則PQ為F，所以P（PQ）為F； 若P為F，則P（PQ）為F。 故無論P取怎樣的值，只要后件Q為F，前件P(PQ)必為F， P(PQ)Q,3 等價重言式和蘊含重言式,82,蘊含式的直觀解釋:,設(shè)P表示“天下雨”，Q表示“馬路濕”，則 P(PQ) Q Q(PQ) P 設(shè) P表示“今天下雨”，Q表示“今天刮風(fēng)”。 則 P(PQ)Q,3 等價重言式和蘊含重言式,83,命題邏輯的基本蘊含式,3 等價重言式和蘊含重言式,設(shè)P、Q、R是命題變元，下表中列出了16個最基本的蘊含式。,84,基本的蘊含式,命題邏輯的基本蘊含式,,,3 等價重言式和蘊含重言式,