離散數(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為兩個 命題 復(fù)合命題 為兩個 命題 復(fù)合命題 p與與q之 中恰有一個成立 之 中恰有一個成立 稱為稱為p 與與q的的排斥或排斥或 異或 記為 異或 記為p q 稱為排斥 或 稱為排斥 或 P q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng) p與與q中恰有一個為真 中恰有一個為真 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 請大家自證 請大家自證 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為兩個 命題 復(fù)合命題 為兩個 命題 復(fù)合命題 p不蘊 涵 不蘊 涵q 稱為稱為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為兩個命 題 復(fù)合命題 為兩個命 題 復(fù)合命題 p與與q的否 定 的否 定 稱為稱為p與與q的的與非式與非式 記為 記為p q p q為真當(dāng) 且僅當(dāng) 為真當(dāng) 且僅當(dāng)p與與q不同時為真 不同時為真 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為兩個命 題 復(fù)合命題 為兩個命 題 復(fù)合命題 p或或q的否 定 的否 定 稱為稱為p與與q的的或非式或非式 記為 記為p q p q為真當(dāng) 且僅當(dāng) 為真當(dāng) 且僅當(dāng)p與與q不同時為真 不同時為真 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 一個一個n維卡氏積維卡氏積 0 1 n到到 0 1 的函數(shù)稱為的函數(shù)稱為n元 真值函數(shù) 定義 元 真值函數(shù) 定義1 16 在一個聯(lián)結(jié)詞的集合中 如果一個聯(lián)結(jié)詞可 以用集合中的其余聯(lián)結(jié)詞表示 則稱該聯(lián)結(jié)詞為 在一個聯(lián)結(jié)詞的集合中 如果一個聯(lián)結(jié)詞可 以用集合中的其余聯(lián)結(jié)詞表示 則稱該聯(lián)結(jié)詞為冗余 的 冗余 的聯(lián)結(jié)詞 否則稱為聯(lián)結(jié)詞 否則稱為獨立的獨立的聯(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個聯(lián)結(jié)詞可組成集合 個聯(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é)詞 也是冗余的 請大家討論 請大家討論 無冗余 且無冗余 且 也是無冗 余的 也是無冗 余的 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é)詞的命題公式表示 則稱 該聯(lián)結(jié)詞集為 若任一真值函數(shù) 命題公式 都可以用僅 含某一聯(lián)結(jié)詞集合的聯(lián)結(jié)詞的命題公式表示 則稱 該聯(lián)結(jié)詞集為全功能集全功能集 功能完備集 若一個聯(lián) 結(jié)詞的全功能集不含冗余的聯(lián)結(jié)詞 則稱它為 功能完備集 若一個聯(lián) 結(jié)詞的全功能集不含冗余的聯(lián)結(jié)詞 則稱它為極小 的全功能集 極小 的全功能集 極小的功能完備集 因此 極小的功能完備集 因此 是極小的全功能集 可以證明 是極小的全功能集 可以證明 也是極小的全功能集 也是極小的全功能集 例例1 12和例和例1 13請大家自學(xué) 請大家自學(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 對偶與范式對偶與范式對偶與范式對偶與范式 1 5 1 對偶式 定義 對偶式 定義1 18 在僅含在僅含 的命題公式的命題公式A中 將 與 對 換 若 中 將 與 對 換 若A中含中含0或或1 則將 則將0和和1對換 所得到的命題公 式稱為 對換 所得到的命題公 式稱為A的對偶式 記為的對偶式 記為A 顯然 顯然 A與與A 互為對偶式 且互為對偶式 且 A A 例例 求求p q p q的對偶式 解 因 的對偶式 解 因p q p q 則 則 p q的對偶式為 的對偶式為 p q 即 即p q 同理 同理 p q的對偶式為的對偶式為p q 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)14 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 定理定理1 2 設(shè)設(shè)A和和A 互為對偶式 互為對偶式 p1 p2 pn是出現(xiàn) 在 是出現(xiàn) 在A和和A 中的全部命題變項 則 中的全部命題變項 則 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 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)16 定理定理1 3 設(shè)設(shè)p1 p2 pn是出現(xiàn)在是出現(xiàn)在A和和B中的命題 變項 若 中的命題 變項 若A B 則 則A B 對偶原理對偶原理 證明 由 證明 由 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 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)17 1 5 2 范式范式 給定一個命題公式 判斷它是永真式 永假式 還是可滿足式 這類問題稱為 給定一個命題公式 判斷它是永真式 永假式 還是可滿足式 這類問題稱為判定問題判定問題 前面學(xué)過的判定方法 前面學(xué)過的判定方法 真值表法真值表法 等值演算法等值演算法 但 以上方法不適合命題變項的數(shù)目較多的情形 必須將 命題公式化為規(guī)范的形式 但 以上方法不適合命題變項的數(shù)目較多的情形 必須將 命題公式化為規(guī)范的形式 主析取范式主析取范式和和主合取范 式 主合取范 式 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)18 定義定義1 19 1 一個命題公式稱為 一個命題公式稱為析取范式析取范式 當(dāng)且僅當(dāng) 它具有形式 當(dāng)且僅當(dāng) 它具有形式 A1 A2 An 其中 其中Ai i 1 2 n 由命題變元或其否定所組成的合取式 如 由命題變元或其否定所組成的合取式 如 p p q p q r 為為析取范式析取范式 2 1 一個命題公式稱為 一個命題公式稱為合取范式合取范式 當(dāng)且僅當(dāng)它 具有形式 當(dāng)且僅當(dāng)它 具有形式 A1 A2 An 其中 其中Ai i 1 2 n 由命題變元或其否定所組成的析取式 如 由命題變元或其否定所組成的析取式 如 p p q p q r 為為合取范式合取范式 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 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 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)20 否定號的消去或內(nèi)移 用 否定號的消去或內(nèi)移 用 p p p q p q p q p q 利用分配率 利用分配率 求求析取范式析取范式 使用 使用 對對 的分配律 的分配律 求求合取范式合取范式 使用 使用 對對 的分配律 的分配律 注意 析取范式和合取范式存在 但不是唯一的 注意 析取范式和合取范式存在 但不是唯一的 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)21 例例1 14 求命題公式 求命題公式 p q r p的合取范式和析 取范式 解 的合取范式和析 取范式 解 1 求 求合取范式合取范式 p q r p p q r p 消去第一個 消去第一個 p q r p 消去第二個 消去第二個 p q r p 消去 消去 p q p r p 對 的分配律 對 的分配律 p q r p 顯然 合取范式不唯一 以上兩式都是顯然 合取范式不唯一 以上兩式都是合取范式合取范式 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)22 2 求 求析取范式析取范式 p q r p p q r p 前面的結(jié)論 前面的結(jié)論 p r q r p 對 的分配律 對 的分配律 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 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)23 定義定義1 5 4 在含在含n個命題變項的簡單合取式中 若每 個命題變項與其否定不同時存在 但 個命題變項的簡單合取式中 若每 個命題變項與其否定不同時存在 但Pi與 與 Pi必須出 現(xiàn)且僅出現(xiàn)一次 且 必須出 現(xiàn)且僅出現(xiàn)一次 且Pi與 與 Pi出現(xiàn)在從左起的第出現(xiàn)在從左起的第i 位 上 若命題變項無角標(biāo) 則按字典順序 這樣的 簡單合取式稱為極小項 位 上 若命題變項無角標(biāo) 則按字典順序 這樣的 簡單合取式稱為極小項 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 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 極小項極小項 m77111 m66011 m55101 m44001 m33110 m22010 m11100 m00000 記號十進(jìn)制數(shù)記號十進(jìn)制數(shù)rqp 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 3個命題變項例個命題變項例 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)25 一般地 一般地 n個命題變項共產(chǎn)生個命題變項共產(chǎn)生2n個極小項 個極小項 m0 m1 m2n 1 1 5 3 主析取范式 定義 主析取范式 定義1 21 在含在含n個命題變項的命題公式個命題變項的命題公式A中 若中 若A的析 取范式中的簡單合取式全部是極小項 則稱該析取范 式為主析取范式 的析 取范式中的簡單合取式全部是極小項 則稱該析取范 式為主析取范式 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 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 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)27 定理定理1 5 任何命題公式的為主析取范式都是存在的 并 且唯一 求給定命題公式 任何命題公式的為主析取范式都是存在的 并 且唯一 求給定命題公式A的主析取范式的步驟如下 的主析取范式的步驟如下 求求A的析取范式的析取范式A 若若A 的某簡單合取式的某簡單合取式B中不含命題變項中不含命題變項pi或 或 pi 則將 則將 B展成 展成 B B 1 B pi pi B pi B pi 將重復(fù)出現(xiàn)的命題變項 永假式及重復(fù)出現(xiàn)的極小項將重復(fù)出現(xiàn)的命題變項 永假式及重復(fù)出現(xiàn)的極小項 消去消去 將極小項按由小到大的順序排列 并用將極小項按由小到大的順序排列 并用 表示 表示 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 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 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)29 也可利用真值表 法求命題公式的主 析取范式 也可利用真值表 法求命題公式的主 析取范式 例例1 16 求上例求上例p q r的主析取范式 解法 的主析取范式 解法2 真值表見右 圖 顯然 真值表見右 圖 顯然 主析取范式 為 主析取范式 為 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 對偶與范式對偶與范式對偶與范式對偶與范式 2006 3 1電子工程學(xué)院 離散數(shù)學(xué)30 總結(jié) 主析取范式有以下用途 總結(jié) 主析取范式有以下用途 判斷兩個命題公式是否等值 判斷兩個命題公式是否等值 判斷命題公式的類型 判斷命題公式的類型 1 5 1 5 1 5 1 5 對偶與范式對偶與范式對偶與范式對偶與范式 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