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

1、1-3命題公式與翻譯命題公式與翻譯1-3.1 命題公式命題公式 p，p q，(p q) (pq)都是復(fù)合命都是復(fù)合命題。若題。若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è)?/p>

2、身是一個(gè)合式公式。單個(gè)命題變?cè)旧硎且粋€(gè)合式公式。(2)如果如果a是合式公式，那么是合式公式，那么 a是合式公式。是合式公式。(3)如果如果a和和b是合式公式，那么是合式公式，那么(a b), (a b), (ab), (a b)是合式公式。是合式公式。(4)當(dāng)且僅當(dāng)能夠有限次地應(yīng)用當(dāng)且僅當(dāng)能夠有限次地應(yīng)用(1)、(2)、(3)所得到的包含命題變?cè)?、?lián)結(jié)詞和括號(hào)的符所得到的包含命題變?cè)⒙?lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。號(hào)串是合式公式。1-3.1 命題公式命題公式注：這是一個(gè)遞歸方式的定義（遞歸定義）注：這是一個(gè)遞歸方式的定義（遞歸定義） （1）是遞歸定義的基礎(chǔ)）是遞歸定義的基礎(chǔ) （2）、（）、

3、（3）是歸納）是歸納 （4）是遞歸的界限）是遞歸的界限例：例： (p q)就不是合式公式就不是合式公式聯(lián)結(jié)詞的運(yùn)算次序：聯(lián)結(jié)詞的運(yùn)算次序：(1)使用括號(hào)使用括號(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)化為：原命題可

4、以符號(hào)化為： p q 或化為：或化為：qp例例3. 如果你和他都不固執(zhí)己見的話，那么不愉快如果你和他都不固執(zhí)己見的話，那么不愉快的事也不會(huì)發(fā)生了。的事也不會(huì)發(fā)生了。解：設(shè)解：設(shè)p：你固執(zhí)己見。：你固執(zhí)己見。 q：他固執(zhí)己見。：他固執(zhí)己見。 r：不愉快的事也不會(huì)發(fā)生了：不愉快的事也不會(huì)發(fā)生了原命題可以符號(hào)化為：（原命題可以符號(hào)化為：（ pq）r例例4. 如果你和他不都是固執(zhí)己見的話，那么不愉如果你和他不都是固執(zhí)己見的話，那么不愉快的事也不會(huì)發(fā)生了?？斓氖乱膊粫?huì)發(fā)生了。解：設(shè)解：設(shè)p：你固執(zhí)己見。：你固執(zhí)己見。 q：他固執(zhí)己見。：他固執(zhí)己見。 r：不愉快的事也不會(huì)發(fā)生了：不愉快的事也不會(huì)發(fā)生了原命

5、題可以符號(hào)化為：原命題可以符號(hào)化為： （p q）r作業(yè)(1-3)p12. (5)1-4真值表與等價(jià)公式真值表與等價(jià)公式定義定義1-4.1真值表：真值表： 對(duì)于給定的命題公式，對(duì)其分量進(jìn)對(duì)于給定的命題公式，對(duì)其分量進(jìn)行所有可能的真值指派得到該公式的相行所有可能的真值指派得到該公式的相應(yīng)的真值取值情況，將其匯列成表，稱應(yīng)的真值取值情況，將其匯列成表，稱做該命題公式的真值表。做該命題公式的真值表。例：給出例：給出 (pq)的的真值表。真值表。pqpq(pq)tttftfftfttffftf1-4 真值表與等價(jià)公式真值表與等價(jià)公式在真值表中，命題公式真值的取值數(shù)目，在真值表中，命題公式真值的取值數(shù)目，

6、決定于分量的個(gè)數(shù)。決定于分量的個(gè)數(shù)。n個(gè)命題變?cè)M成的個(gè)命題變?cè)M成的命題公式有命題公式有2n種真值情況。種真值情況。定義定義1-4.2 永真公式永真公式 永假公式：永假公式： 無(wú)論對(duì)其分量作怎樣的真值指派，其無(wú)論對(duì)其分量作怎樣的真值指派，其真值永為真值永為t，稱為永真公式，記為，稱為永真公式，記為t 。 無(wú)論對(duì)其分量作怎樣的真值指派，其無(wú)論對(duì)其分量作怎樣的真值指派，其真值永為真值永為f，稱為永假公式，記為，稱為永假公式，記為f 。 1-4 真值表與等價(jià)公式真值表與等價(jià)公式定義定義1-4.3 等價(jià)等價(jià)(equivalent)公式：公式： 設(shè)設(shè)a和和b是兩個(gè)命題公式，是兩個(gè)命題公式，p1，p2，

7、pn是出現(xiàn)在是出現(xiàn)在a和和b中的所有原子變?cè)魧?duì)中的所有原子變?cè)?，若?duì)p1，p2，pn的任何真值指派，的任何真值指派， a和和b真值相真值相同，稱同，稱a和和b等價(jià)或邏輯相等。記作等價(jià)或邏輯相等。記作ab。 要證明兩個(gè)命題公式等價(jià)，可用：要證明兩個(gè)命題公式等價(jià)，可用：（1）真值表法）真值表法（2）等價(jià)命題定律。）等價(jià)命題定律。1-4 真值表與等價(jià)公式真值表與等價(jià)公式例例: pq p q p q (pq) (qp) p q (p q) ( pq)p15 表表1-4.8 命題定律命題定律1-4 真值表與等價(jià)公式真值表與等價(jià)公式定義定義1-4.4 子公式子公式設(shè)設(shè)a是一個(gè)命題公式，是一個(gè)命題公式，

8、x是是a的一部分且的一部分且x本身也是公本身也是公式，則稱式，則稱x為公式為公式a的子公式。的子公式。定理定理1-4.1（等價(jià)置換）（等價(jià)置換）設(shè)設(shè)a是一個(gè)命題公式，是一個(gè)命題公式，x是是a的一個(gè)子公式，若公式的一個(gè)子公式，若公式y(tǒng)與與x等價(jià)，用等價(jià)，用y置換置換a中的中的x得到一個(gè)公式得到一個(gè)公式b，則，則 a b?？捎谜嬷当矸ǖ米C可用真值表法得證1-4 真值表與等價(jià)公式例：例：證明證明 q q( (p p ( (p p q) q) q qp p證明：應(yīng)用吸收律證明：應(yīng)用吸收律 p p ( (p p q) q) p p 左邊左邊 q qp p 得證！得證！1-4 真值表與等價(jià)公式p19 (7) a) p19 (7) a) 證明證明 a a( (b ba) a) a a(a(a b)b)證明證