離散數(shù)學(xué)真值表與等價(jià)公式ppt課件

1、1-3命題公式與翻譯1-3.1 命題公式命題公式P，PQ，(PQ)(PQ)都是復(fù)都是復(fù)合命題。假設(shè)合命題。假設(shè)P和和Q是命題變?cè)鞘敲}變?cè)?，那么上述各式均稱作命題公式。么上述各式均稱作命題公式。 P和和Q稱為命題公式的分量。稱為命題公式的分量。命題公式是沒有確定的真值的，僅當(dāng)命題公式是沒有確定的真值的，僅當(dāng)在一個(gè)公式中命題變?cè)么_定的命在一個(gè)公式中命題變?cè)么_定的命題代入時(shí)，才干得到一個(gè)命題。題代入時(shí)，才干得到一個(gè)命題。1-3.1 命題公式定義定義1-3.1 命題演算的合式公式命題演算的合式公式wff(well formed formula)(1)單個(gè)命題變?cè)旧硎且粋€(gè)合式公式。單個(gè)命題變

2、元本身是一個(gè)合式公式。(2)假設(shè)假設(shè)A是合式公式，那么是合式公式，那么 A是合式公式。是合式公式。(3)假設(shè)假設(shè)A和和B是合式公式，那么是合式公式，那么(AB), (AB), (AB), (A B)是合式公式。是合式公式。(4)當(dāng)且僅當(dāng)可以有限次地運(yùn)用當(dāng)且僅當(dāng)可以有限次地運(yùn)用(1)、(2)、(3)所得到的包含命題變?cè)?、結(jié)合詞和括號(hào)的符所得到的包含命題變?cè)?、結(jié)合詞和括號(hào)的符號(hào)串是合式公式。號(hào)串是合式公式。1-3.1 命題公式注：這是一個(gè)遞歸方式的定義遞歸定義注：這是一個(gè)遞歸方式的定義遞歸定義 1是遞歸定義的根底是遞歸定義的根底 2、3是歸納是歸納 4是遞歸的界限是遞歸的界限例：例： (PQ)就不

3、是合式公式就不是合式公式結(jié)合詞的運(yùn)算次序：結(jié)合詞的運(yùn)算次序：運(yùn)用括號(hào)運(yùn)用括號(hào)(2) 規(guī)定運(yùn)算符運(yùn)算優(yōu)先次序：規(guī)定運(yùn)算符運(yùn)算優(yōu)先次序： , , , ,1-3.2 翻譯例例1. 除非他努力，否那么他將失敗。除非他努力，否那么他將失敗。解：設(shè)解：設(shè)P：他努力。：他努力。 Q：他將失敗。：他將失敗。原命題可以符號(hào)化為：原命題可以符號(hào)化為： P Q例例2. 除非除非(僅當(dāng)僅當(dāng))我有時(shí)間，我才去看電影。我有時(shí)間，我才去看電影。解：設(shè)解：設(shè)P：我有時(shí)間。：我有時(shí)間。 Q：我去看電影。：我去看電影。原命題可以符號(hào)化為：原命題可以符號(hào)化為： P Q 或化為：或化為：QP例例3. 假設(shè)他和他都不固執(zhí)己見的話，那么

4、不愉快假設(shè)他和他都不固執(zhí)己見的話，那么不愉快的事也不會(huì)發(fā)生了。的事也不會(huì)發(fā)生了。解：設(shè)解：設(shè)P：他固執(zhí)己見。：他固執(zhí)己見。 Q：他固執(zhí)己見。：他固執(zhí)己見。 R：不愉快的事也不會(huì)發(fā)生了：不愉快的事也不會(huì)發(fā)生了原命題可以符號(hào)化為：原命題可以符號(hào)化為： PQR例例4. 假設(shè)他和他不都是固執(zhí)己見的話，那么不愉假設(shè)他和他不都是固執(zhí)己見的話，那么不愉快的事也不會(huì)發(fā)生了?？斓氖乱膊粫?huì)發(fā)生了。解：設(shè)解：設(shè)P：他固執(zhí)己見。：他固執(zhí)己見。 Q：他固執(zhí)己見。：他固執(zhí)己見。 R：不愉快的事也不會(huì)發(fā)生了：不愉快的事也不會(huì)發(fā)生了原命題可以符號(hào)化為：原命題可以符號(hào)化為： PQR作業(yè)(1-3)P12. (5)1-4真值表與等

5、價(jià)公式定義定義1-4.1真值表：真值表： 對(duì)于給定的命題公式，對(duì)其分量進(jìn)對(duì)于給定的命題公式，對(duì)其分量進(jìn)展一切能夠的真值指派得到該公式的相展一切能夠的真值指派得到該公式的相應(yīng)的真值取值情況，將其匯列成表，稱應(yīng)的真值取值情況，將其匯列成表，稱做該命題公式的真值表。做該命題公式的真值表。例：給出例：給出 (PQ)的真值表。的真值表。PQPQ(PQ)TTTFTFFTFTTFFFTF1-4 真值表與等價(jià)公式在真值表中，命題公式真值的取值數(shù)目，在真值表中，命題公式真值的取值數(shù)目，決議于分量的個(gè)數(shù)。決議于分量的個(gè)數(shù)。n個(gè)命題變?cè)M成的個(gè)命題變?cè)M成的命題公式有命題公式有2n種真值情況。種真值情況。定義定義1

6、-4.2 永真公式永真公式 永假公式：永假公式： 無論對(duì)其分量作怎樣的真值指派，其無論對(duì)其分量作怎樣的真值指派，其真值永為真值永為T，稱為永真公式，記為，稱為永真公式，記為T 。 無論對(duì)其分量作怎樣的真值指派，其無論對(duì)其分量作怎樣的真值指派，其真值永為真值永為F，稱為永假公式，記為，稱為永假公式，記為F 。 1-4 真值表與等價(jià)公式定義定義1-4.3 等價(jià)等價(jià)(equivalent)公式：公式： 設(shè)設(shè)A和和B是兩個(gè)命題公式，是兩個(gè)命題公式，P1，P2，Pn是出如今是出如今A和和B中的一切原子變?cè)?，假設(shè)中的一切原子變?cè)僭O(shè)對(duì)對(duì)P1，P2，Pn的任何真值指派，的任何真值指派， A和和B真值一樣，

7、稱真值一樣，稱A和和B等價(jià)或邏輯相等。記作等價(jià)或邏輯相等。記作AB。 要證明兩個(gè)命題公式等價(jià)，可用：要證明兩個(gè)命題公式等價(jià)，可用：1真值表法真值表法2等價(jià)命題定律。等價(jià)命題定律。1-4 真值表與等價(jià)公式例例: PQ PQ P Q (PQ)(QP) P Q (PQ) ( PQ)P15 表表1-4.8 命題定律命題定律1-4 真值表與等價(jià)公式定義定義1-4.4 子公式子公式設(shè)設(shè)A是一個(gè)命題公式，是一個(gè)命題公式，X是是A的一部分且的一部分且X本身也是公本身也是公式，那么稱式，那么稱X為公式為公式A的子公式。的子公式。定理定理1-4.1等價(jià)置換等價(jià)置換設(shè)設(shè)A是一個(gè)命題公式，是一個(gè)命題公式，X是是A的一個(gè)子公式，假設(shè)公式的一個(gè)子公式，假設(shè)公式Y(jié)與與X等價(jià)，用等價(jià)，用Y置換置換A中的中的X得到一個(gè)公式得到一個(gè)公式B，那么，那么 A B?？捎谜嬷当矸ǖ米C可用真值表法得證1-4 真值表與等價(jià)公式例：證明例：證明 Q(P(PQ) QP證明：運(yùn)用吸收律證明：運(yùn)用吸收律 P(PQ) P 左邊左邊 QP 得證！得證！1-4 真值表與等價(jià)公式P19 (7) a) P19 (7) a) 證明證明 A A(B(BA) A) A A(A(A B) B)證明證明: