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

1、1-3命題公式與翻譯1-3.1 命題公式命題公式P，PQ，(PQ)(PQ)都是復(fù)都是復(fù)合命題。假設(shè)合命題。假設(shè)P和和Q是命題變元，那是命題變元，那么上述各式均稱作命題公式。么上述各式均稱作命題公式。 P和和Q稱為命題公式的分量。稱為命題公式的分量。命題公式是沒有確定的真值的，僅當(dāng)命題公式是沒有確定的真值的，僅當(dāng)在一個公式中命題變元用確定的命在一個公式中命題變元用確定的命題代入時，才干得到一個命題。題代入時，才干得到一個命題。1-3.1 命題公式定義定義1-3.1 命題演算的合式公式命題演算的合式公式wff(well formed formula)(1)單個命題變元本身是一個合式公式。單個命題變

2、元本身是一個合式公式。(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)所得到的包含命題變元、結(jié)合詞和括號的符所得到的包含命題變元、結(jié)合詞和括號的符號串是合式公式。號串是合式公式。1-3.1 命題公式注：這是一個遞歸方式的定義遞歸定義注：這是一個遞歸方式的定義遞歸定義 1是遞歸定義的根底是遞歸定義的根底 2、3是歸納是歸納 4是遞歸的界限是遞歸的界限例：例： (PQ)就不

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

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

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

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

7、稱真值一樣，稱A和和B等價(jià)或邏輯相等。記作等價(jià)或邏輯相等。記作AB。 要證明兩個命題公式等價(jià)，可用：要證明兩個命題公式等價(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是一個命題公式，是一個命題公式，X是是A的一部分且的一部分且X本身也是公本身也是公式，那么稱式，那么稱X為公式為公式A的子公式。的子公式。定理定理1-4.1等價(jià)置換等價(jià)置換設(shè)設(shè)A是一個命題公式，是一個命題公式，X是是A的一個子公式，假設(shè)公式的一個子公式，假設(shè)公式Y(jié)與與X等價(jià)，用等價(jià)，用Y置換置換A中的中的X得到一個公式得到一個公式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)證明證明: