離散數(shù)學(xué) 第三講.pdf

2006 3 1電子工程學(xué)院 離散數(shù)學(xué)1 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 1 4 1 其它聯(lián)結(jié)詞其它聯(lián)結(jié)詞 定義定義1 11 設(shè)設(shè)p q為兩個(gè) 命題 復(fù)合命題 為兩個(gè) 命題 復(fù)合命題 p與與q之 中恰有一個(gè)成立 之 中恰有一個(gè)成立 稱(chēng)為稱(chēng)為p 與與q的的排斥或排斥或 異或 記為 異或 記為p q 稱(chēng)為排斥 或 稱(chēng)為排斥 或 P q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng) p與與q中恰有一個(gè)為真 中恰有一個(gè)為真 011 101 110 000 p qqp 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)2 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 聯(lián)結(jié)詞聯(lián)結(jié)詞 有以下性質(zhì) 設(shè) 有以下性質(zhì) 設(shè)p q r為命題 則 為命題 則 p q q p p q r p q r p q r p q p r 請(qǐng)大家自證 請(qǐng)大家自證 p q p q p q p q p q p p 0 0 p p 1 p p 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)3 定理定理 設(shè)設(shè)p q r為命題 若為命題 若p q r 則 則 p r q q r p p q r 為永假式 矛盾式 證明 為永假式 矛盾式 證明 p r p p q 0 q q q r q p q 0 q q p q r r r 0 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)4 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 定義定義1 12 設(shè)設(shè)p q為兩個(gè) 命題 復(fù)合命題 為兩個(gè) 命題 復(fù)合命題 p不蘊(yùn) 涵 不蘊(yùn) 涵q 稱(chēng)為稱(chēng)為p與與q的的條件否 定 條件否 定 記為 記為p q p q為 真當(dāng)且僅當(dāng) 為 真當(dāng)且僅當(dāng)p為真為真q為 假 為 假 p q p q 011 101 010 000 p qqp 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)5 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 定義定義1 13設(shè)設(shè)p q為兩個(gè)命 題 復(fù)合命題 為兩個(gè)命 題 復(fù)合命題 p與與q的否 定 的否 定 稱(chēng)為稱(chēng)為p與與q的的與非式與非式 記為 記為p q p q為真當(dāng) 且僅當(dāng) 為真當(dāng) 且僅當(dāng)p與與q不同時(shí)為真 不同時(shí)為真 p q p q 011 101 110 100 p qqp 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)6 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 聯(lián)結(jié)詞聯(lián)結(jié)詞 有以下性質(zhì) 設(shè) 有以下性質(zhì) 設(shè)p q為命題 則 為命題 則 p p p p p p q p q p q p q p p q q p q p q p q 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)7 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 定義定義1 14 設(shè)設(shè)p q為兩個(gè)命 題 復(fù)合命題 為兩個(gè)命 題 復(fù)合命題 p或或q的否 定 的否 定 稱(chēng)為稱(chēng)為p與與q的的或非式或非式 記為 記為p q p q為真當(dāng) 且僅當(dāng) 為真當(dāng) 且僅當(dāng)p與與q不同時(shí)為真 不同時(shí)為真 p q p q 011 001 010 100 p qqp 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)8 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 聯(lián)結(jié)詞聯(lián)結(jié)詞 有以下性質(zhì) 設(shè) 有以下性質(zhì) 設(shè)p q為命題 則 為命題 則 p p p p p p q p q p q p q p p q q p q p q p q 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)9 1010101011 1100110001 1111000010 1111111100 1p qp q p q p q p qp qqp 1010101011 1100110001 1111000010 0000000000 p qp qqq ppp qp q0qp 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)10 1 4 2 全功能集全功能集 定義定義1 15 一個(gè)一個(gè)n維卡氏積維卡氏積 0 1 n到到 0 1 的函數(shù)稱(chēng)為的函數(shù)稱(chēng)為n元 真值函數(shù) 定義 元 真值函數(shù) 定義1 16 在一個(gè)聯(lián)結(jié)詞的集合中 如果一個(gè)聯(lián)結(jié)詞可 以用集合中的其余聯(lián)結(jié)詞表示 則稱(chēng)該聯(lián)結(jié)詞為 在一個(gè)聯(lián)結(jié)詞的集合中 如果一個(gè)聯(lián)結(jié)詞可 以用集合中的其余聯(lián)結(jié)詞表示 則稱(chēng)該聯(lián)結(jié)詞為冗余 的 冗余 的聯(lián)結(jié)詞 否則稱(chēng)為聯(lián)結(jié)詞 否則稱(chēng)為獨(dú)立的獨(dú)立的聯(lián)結(jié)詞 聯(lián)結(jié)詞 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)11 前面定義的前面定義的5個(gè)聯(lián)結(jié)詞可組成集合 個(gè)聯(lián)結(jié)詞可組成集合 而 而 p q p q p q p q q p p q q p 顯然 聯(lián)結(jié)詞 顯然 聯(lián)結(jié)詞 是冗余的 再考慮集合 是冗余的 再考慮集合 而 而 p q p q p q 所以 聯(lián)結(jié)詞 也是冗余的 所以 聯(lián)結(jié)詞 也是冗余的 請(qǐng)大家討論 請(qǐng)大家討論 無(wú)冗余 且無(wú)冗余 且 也是無(wú)冗 余的 也是無(wú)冗 余的 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)12 定義定義1 17 若任一真值函數(shù) 命題公式 都可以用僅 含某一聯(lián)結(jié)詞集合的聯(lián)結(jié)詞的命題公式表示 則稱(chēng) 該聯(lián)結(jié)詞集為 若任一真值函數(shù) 命題公式 都可以用僅 含某一聯(lián)結(jié)詞集合的聯(lián)結(jié)詞的命題公式表示 則稱(chēng) 該聯(lián)結(jié)詞集為全功能集全功能集 功能完備集 若一個(gè)聯(lián) 結(jié)詞的全功能集不含冗余的聯(lián)結(jié)詞 則稱(chēng)它為 功能完備集 若一個(gè)聯(lián) 結(jié)詞的全功能集不含冗余的聯(lián)結(jié)詞 則稱(chēng)它為極小 的全功能集 極小 的全功能集 極小的功能完備集 因此 極小的功能完備集 因此 是極小的全功能集 可以證明 是極小的全功能集 可以證明 也是極小的全功能集 也是極小的全功能集 例例1 12和例和例1 13請(qǐng)大家自學(xué) 請(qǐng)大家自學(xué) 1 4 1 4 1 4 1 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)13 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 1 5 1 對(duì)偶式 定義 對(duì)偶式 定義1 18 在僅含在僅含 的命題公式的命題公式A中 將 與 對(duì) 換 若 中 將 與 對(duì) 換 若A中含中含0或或1 則將 則將0和和1對(duì)換 所得到的命題公 式稱(chēng)為 對(duì)換 所得到的命題公 式稱(chēng)為A的對(duì)偶式 記為的對(duì)偶式 記為A 顯然 顯然 A與與A 互為對(duì)偶式 且互為對(duì)偶式 且 A A 例例 求求p q p q的對(duì)偶式 解 因 的對(duì)偶式 解 因p q p q 則 則 p q的對(duì)偶式為 的對(duì)偶式為 p q 即 即p q 同理 同理 p q的對(duì)偶式為的對(duì)偶式為p q 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)14 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 定理定理1 2 設(shè)設(shè)A和和A 互為對(duì)偶式 互為對(duì)偶式 p1 p2 pn是出現(xiàn) 在 是出現(xiàn) 在A和和A 中的全部命題變項(xiàng) 則 中的全部命題變項(xiàng) 則 1 A p1 p2 pn A p1 p2 pn 2 A p1 p2 pn A p1 p2 pn 證明 由證明 由p q p q p q p q 則 則 A p1 p2 pn A p1 p2 pn 同理 同理 A p1 p2 pn A p1 p2 pn 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)15 例例 設(shè)設(shè)A p q r 是 是 p q r 證明 證明 A p q r A p q r 證明 因證明 因 A p q r 是 是 p q r 則 則 A p q r 是是p q r 但 但 A p q r 是 是 p q r 故 故 A p q r 是是 p q r 所以 所以 A p q r A p q r 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)16 定理定理1 3 設(shè)設(shè)p1 p2 pn是出現(xiàn)在是出現(xiàn)在A和和B中的命題 變項(xiàng) 若 中的命題 變項(xiàng) 若A B 則 則A B 對(duì)偶原理對(duì)偶原理 證明 由 證明 由 A B 則 則 A p1 pn B p1 pn 是永真式 故 是永真式 故 A p1 pn B p1 pn 也是永真式 即 也是永真式 即 A p1 pn B p1 pn 由定理由定理1 2 A p1 p2 pn B p1 p2 pn 即 即 A B 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)17 1 5 2 范式范式 給定一個(gè)命題公式 判斷它是永真式 永假式 還是可滿足式 這類(lèi)問(wèn)題稱(chēng)為 給定一個(gè)命題公式 判斷它是永真式 永假式 還是可滿足式 這類(lèi)問(wèn)題稱(chēng)為判定問(wèn)題判定問(wèn)題 前面學(xué)過(guò)的判定方法 前面學(xué)過(guò)的判定方法 真值表法真值表法 等值演算法等值演算法 但 以上方法不適合命題變項(xiàng)的數(shù)目較多的情形 必須將 命題公式化為規(guī)范的形式 但 以上方法不適合命題變項(xiàng)的數(shù)目較多的情形 必須將 命題公式化為規(guī)范的形式 主析取范式主析取范式和和主合取范 式 主合取范 式 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)18 定義定義1 19 1 一個(gè)命題公式稱(chēng)為 一個(gè)命題公式稱(chēng)為析取范式析取范式 當(dāng)且僅當(dāng) 它具有形式 當(dāng)且僅當(dāng) 它具有形式 A1 A2 An 其中 其中Ai i 1 2 n 由命題變?cè)蚱浞穸ㄋM成的合取式 如 由命題變?cè)蚱浞穸ㄋM成的合取式 如 p p q p q r 為為析取范式析取范式 2 1 一個(gè)命題公式稱(chēng)為 一個(gè)命題公式稱(chēng)為合取范式合取范式 當(dāng)且僅當(dāng)它 具有形式 當(dāng)且僅當(dāng)它 具有形式 A1 A2 An 其中 其中Ai i 1 2 n 由命題變?cè)蚱浞穸ㄋM成的析取式 如 由命題變?cè)蚱浞穸ㄋM成的析取式 如 p p q p q r 為為合取范式合取范式 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)19 定理定理1 4 范式存在定理 任一命題公式都存在與它等 值的析取范式或合取范式 范式存在定理 任一命題公式都存在與它等 值的析取范式或合取范式 消去除消去除 外冗余的聯(lián)結(jié)詞 因 外冗余的聯(lián)結(jié)詞 因 是全功能集 若命題公式中含其它聯(lián)結(jié) 詞 可用如下基本等值式及置換規(guī)則將它們消去 是全功能集 若命題公式中含其它聯(lián)結(jié) 詞 可用如下基本等值式及置換規(guī)則將它們消去 p q p qp q p q p q p q q p p q p q p q p q p q p q p q p q 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)20 否定號(hào)的消去或內(nèi)移 用 否定號(hào)的消去或內(nèi)移 用 p p p q p q p q p q 利用分配率 利用分配率 求求析取范式析取范式 使用 使用 對(duì)對(duì) 的分配律 的分配律 求求合取范式合取范式 使用 使用 對(duì)對(duì) 的分配律 的分配律 注意 析取范式和合取范式存在 但不是唯一的 注意 析取范式和合取范式存在 但不是唯一的 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)21 例例1 14 求命題公式 求命題公式 p q r p的合取范式和析 取范式 解 的合取范式和析 取范式 解 1 求 求合取范式合取范式 p q r p p q r p 消去第一個(gè) 消去第一個(gè) p q r p 消去第二個(gè) 消去第二個(gè) p q r p 消去 消去 p q p r p 對(duì) 的分配律 對(duì) 的分配律 p q r p 顯然 合取范式不唯一 以上兩式都是顯然 合取范式不唯一 以上兩式都是合取范式合取范式 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)22 2 求 求析取范式析取范式 p q r p p q r p 前面的結(jié)論 前面的結(jié)論 p r q r p 對(duì) 的分配律 對(duì) 的分配律 p q r 利用交換律和吸收律 顯然 以上兩式均為 利用交換律和吸收律 顯然 以上兩式均為析取范式析取范式 由于命題公式的合取范式和析取范式不唯一 因此 不能作為命題公式的標(biāo)準(zhǔn)形式 因此必須引入 由于命題公式的合取范式和析取范式不唯一 因此 不能作為命題公式的標(biāo)準(zhǔn)形式 因此必須引入主合取范 式 主合取范 式和和主析取范式主析取范式的概念 討論標(biāo)準(zhǔn)型 的概念 討論標(biāo)準(zhǔn)型 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)23 定義定義1 5 4 在含在含n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式中 若每 個(gè)命題變項(xiàng)與其否定不同時(shí)存在 但 個(gè)命題變項(xiàng)的簡(jiǎn)單合取式中 若每 個(gè)命題變項(xiàng)與其否定不同時(shí)存在 但Pi與 與 Pi必須出 現(xiàn)且僅出現(xiàn)一次 且 必須出 現(xiàn)且僅出現(xiàn)一次 且Pi與 與 Pi出現(xiàn)在從左起的第出現(xiàn)在從左起的第i 位 上 若命題變項(xiàng)無(wú)角標(biāo) 則按字典順序 這樣的 簡(jiǎn)單合取式稱(chēng)為極小項(xiàng) 位 上 若命題變項(xiàng)無(wú)角標(biāo) 則按字典順序 這樣的 簡(jiǎn)單合取式稱(chēng)為極小項(xiàng) 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)24 P q r p q r p q r p q r p q r p q r p q r p q r 極小項(xiàng)極小項(xiàng) m77111 m66011 m55101 m44001 m33110 m22010 m11100 m00000 記號(hào)十進(jìn)制數(shù)記號(hào)十進(jìn)制數(shù)rqp 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 3個(gè)命題變項(xiàng)例個(gè)命題變項(xiàng)例 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)25 一般地 一般地 n個(gè)命題變項(xiàng)共產(chǎn)生個(gè)命題變項(xiàng)共產(chǎn)生2n個(gè)極小項(xiàng) 個(gè)極小項(xiàng) m0 m1 m2n 1 1 5 3 主析取范式 定義 主析取范式 定義1 21 在含在含n個(gè)命題變項(xiàng)的命題公式個(gè)命題變項(xiàng)的命題公式A中 若中 若A的析 取范式中的簡(jiǎn)單合取式全部是極小項(xiàng) 則稱(chēng)該析取范 式為主析取范式 的析 取范式中的簡(jiǎn)單合取式全部是極小項(xiàng) 則稱(chēng)該析取范 式為主析取范式 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)26 例例1 15 前面例前面例1 14的析取范式的析取范式 p q r p 1 1 1 q r p q q r r p p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r m2 m4 m5 m6 m7 2 4 5 6 7 顯然 上式是標(biāo)準(zhǔn)的顯然 上式是標(biāo)準(zhǔn)的主析取范式主析取范式 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)27 定理定理1 5 任何命題公式的為主析取范式都是存在的 并 且唯一 求給定命題公式 任何命題公式的為主析取范式都是存在的 并 且唯一 求給定命題公式A的主析取范式的步驟如下 的主析取范式的步驟如下 求求A的析取范式的析取范式A 若若A 的某簡(jiǎn)單合取式的某簡(jiǎn)單合取式B中不含命題變項(xiàng)中不含命題變項(xiàng)pi或 或 pi 則將 則將 B展成 展成 B B 1 B pi pi B pi B pi 將重復(fù)出現(xiàn)的命題變項(xiàng) 永假式及重復(fù)出現(xiàn)的極小項(xiàng)將重復(fù)出現(xiàn)的命題變項(xiàng) 永假式及重復(fù)出現(xiàn)的極小項(xiàng) 消去消去 將極小項(xiàng)按由小到大的順序排列 并用將極小項(xiàng)按由小到大的順序排列 并用 表示 表示 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)28 例例1 16 求求p q r的主析取范式 解法 的主析取范式 解法1 p q r p q r p q 1 1 1 r p q r r p p q q r p q r p q r p q r p q r p q r p q r m1 m3 m5 m6 m7 1 3 5 6 7 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)29 也可利用真值表 法求命題公式的主 析取范式 也可利用真值表 法求命題公式的主 析取范式 例例1 16 求上例求上例p q r的主析取范式 解法 的主析取范式 解法2 真值表見(jiàn)右 圖 顯然 真值表見(jiàn)右 圖 顯然 主析取范式 為 主析取范式 為 1 3 5 6 7 與解法與解法1的結(jié)果完全 一致 的結(jié)果完全 一致 1 1 0 0 0 0 0 0 p q 1111 1011 1101 0001 1110 0010 1100 0000 p q rrqp 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)30 總結(jié) 主析取范式有以下用途 總結(jié) 主析取范式有以下用途 判斷兩個(gè)命題公式是否等值 判斷兩個(gè)命題公式是否等值 判斷命題公式的類(lèi)型 判斷命題公式的類(lèi)型 1 5 1 5 1 5 1 5 對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式對(duì)偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)31 解 原式 解 原式 p q r p p q r p p q r p p r q r p p 1 r 1 q r p 1 1 p q q r p p q r p q q r r p q r p q r p q r p q r p q r p q r p q r