【正文】 群論 6/73 引言 ?教學內(nèi)容 第三部分 代數(shù)結(jié)構(gòu) 第九章 環(huán)與域 第十章 格與布爾代數(shù) 7/73 第一部分 數(shù)理邏輯 ?邏輯學 –是一門研究思維形式和規(guī)律的科學。離散數(shù)學的應用遍及現(xiàn)代科學技術(shù)的諸多領域。1/73 離散數(shù)學 II 肖明軍 Web: Email: 2/73 引言 ?課程簡介 – 離散數(shù)學是現(xiàn)代數(shù)學的一個重要分支 ， 是計算機科學中基礎理論的核心課程 ， 它 研究的對象是有限個或可數(shù)的離散量 。 – 離散數(shù)學是隨著計算機科學的發(fā)展而逐步建立起來的一門新興的工具性學科 ， 形成于上上個世紀七十年代 。分為辯證邏輯和形式邏輯兩種。所謂數(shù)學方法就是引用一套符號體系的方法，所以數(shù)理邏輯又稱作符號邏輯。 –德國數(shù)學家萊布尼茨 Leibniz（現(xiàn)代邏輯的首席創(chuàng)始人）；布爾 Boole （奠基人，邏輯的數(shù)學分析）；弗雷格（數(shù)論的基礎） 9/73 第一章 命題邏輯 命題邏輯也稱命題演算或語句邏輯。真值只有“真”和“假”兩種，分別用“ T”或“ 1”和“ F”或“ 0”表示。 ?注意： 由定義知，一切沒有判斷內(nèi)容的句子如命令，感嘆句，疑問句，祈使句，二義性的陳述句等都不能作為命題。但其真值一定是唯一確定的。 15/73 命題聯(lián)結(jié)詞 命題通常可以通過一些聯(lián)結(jié)詞復合而構(gòu)成新的命題 ，這些聯(lián)結(jié)詞被稱為 邏輯聯(lián)結(jié)詞 ?！睘榉穸?lián)結(jié)詞 。P ： 2不是素數(shù) 。 則 P ∧ Q： 2是素數(shù)并且是偶數(shù) 。 則 P ∨ Q： 2是素數(shù)或是奇數(shù) 。 蘊含式 P→Q可以用多種方式陳述： “ 若 P， 則 Q”。 “P僅當 Q”等 。 例如 ， P：合肥是安徽省會 ， Q：鳥會飛 ， 則 P?Q：合肥是安徽省會當且僅當鳥會飛 。P 非 P 172。 c)：最外層括號可省 。(P ∧ 172。 e)：如果我上街了 ， 我就去書店看看 ， 除非我很累 。與計算機中的與門 ， 或門 ， 非門電路是相對應的 看 P67 例 ， P9 例 命題與命題聯(lián)結(jié)詞 26/73 ：命題公式 就像在代數(shù)學里引入變量一樣 ， 為了更廣泛的應用命題演算 ， 在數(shù)理邏輯中也引入了命題變量 。 命題變量無具體的真值 ， 它的值域是集合 {T， F}(或 {1， 0})。P 也是公式； (3).如果 P， Q是公式 ， 則 P∧ Q﹑ P∨ Q﹑ P→Q﹑ P?Q也是公式； (4).命題公式 (Prepositional Formula)是僅由有限步使用規(guī)則 (1)~(3)后產(chǎn)生的結(jié)果 。P ∧ Q)) ， (((P∧ Q) ∧ (R ∨ Q)) ?(P →R))是命題公式 (P →Q )∧ 172。 –合成公式?jīng)]有真值 ， 只有對其變元進行指派后才有真值 。 31/73 公式的解釋與真值表 ：公式的解釋與真值表 公式本身沒有真值 ， 只有在對其所有命題變元指定真值后才變成一個具有真值的命題 。 32/73 公式的解釋與真值表 例 ： 5個聯(lián)結(jié)詞的真值表 (T： 1， F： 0) P Q 172。 Q) ? 172。 ?注意： (1). 重言式的否定是矛盾式 ， 矛盾式的否定是重言式 ， 所以研究其一就可以了； 36/73 公式的解釋與真值表 (2). 重言式的合取 ， 析取 ， 蘊含 ， 等值等都是重言式； (3). 重言式中有許多非常有用的恒等式和永真蘊含式 。 37/73 公式的解釋與真值表 ?例 ： 判定公式： (1).(P→Q) ?(172。 38/73 公式的解釋與真值表 ?定理 ： 對于公式 G和 H， G?H的充分必要條件是公式 G ?H是重言式 。172。Q 德 Q 41/73 公式的解釋與真值表 E12 P∨ (P∧ Q) =P 吸收律 E13 P∧ (P∨ Q) =P E14 (P→Q) =172。Q)) =172。Q=172。 44/73 公式的解釋與真值表 (2).若 A=B， A=C， 則 A=B∧ C. 證明： A為真時 ， B， C都為真 ， 則 B∧ C也為真 ，即 A→B∧ C為真； A為假時 ， 則不管 B∧ C是真還是假時 ， A→B∧ C均為真 ， 因此 A=B∧ C。 ?定理 (替換定理 ) ： 設 G1是 G的子公式 ， H1是任意的命題公式 ， 在 G中凡出現(xiàn) G1處都以 H1替換后得到的新的命題公式 H， 若 G1=H1， 則 G=H。 (3).(P∧ (Q∨ R))∨ (P∧ 172。P∧ (172。 對 A*采取同樣的替換 ， 又得到 A， 所以 A也是 A*的對偶 ， 即對偶是相互的 。 ?定理 ： 設 A和 A*是對偶式 ， P1,P2, … ,Pn是出現(xiàn)于 A和 A*中所有命題變元 ， 于是 172。P n) 公式 (1) 50/73 公式的解釋與真值表 ?定理 ： 若 A=B ， 且 A ， B 為 命 題 變 元P1,P2, … ,Pn及聯(lián)結(jié)詞 ∧ ， ∨ ， 172。P ∨ Q， 則由對偶原理 ， 得 (P∨ Q)∧ (172。構(gòu)成的公式 ， 則B*=A* 51/73 聯(lián)結(jié)詞的完備集 我們知道 ， 命題公式通過等價公式的轉(zhuǎn)換 ， 可以以不同的形式表示出來 。 P Q f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 永假 或非 蘊含否定 蘊含否定 合取 非P 非Q 等價 異或 恒等Q 恒等P 與非 蘊含 析取 蘊含 永真 ☆ △ △ △ ◇ ◇ ◇ ◇ △ ☆ ☆ △ ◇ ◇ ◇ ☆ 53/73 聯(lián)結(jié)詞的完備集 ◇ ：已定義； ☆ ：意義不大； △ ：可再定義 f1=P∧ 172。(Q→P)， f5 =P∧ Q， f6 = 172。(P∧ Q)， f13 =P→Q， f14 = P∨ Q， f15 = Q→P， f16 =P∨ 172。(P∧ Q) ， P↓Q ? 172。P ， (P↓Q)↓(P↓Q)?P∨ Q， (P↓P)↓(Q↓Q)?P∧ Q ： P Q ? Q P， P (Q R) ? (P Q) R P P? 0， 0 P ? P， 1 P ? 172。A∨ B， A?B=(A→B)∧ (B→A)，所以 →， ?是冗余的，故 {172。B)，所以 ∨ 也是冗余的 , ∴ {172。,∧ }是一個極小的。, }也是極小完備集，此外由 ↑， ↓的性質(zhì)可知 ， {↑}， {↓}也是極小完備集； ? {∧ ,∨ ,→, ?}及其子集不是完備集； ?實際應用中經(jīng)常采取的聯(lián)結(jié)詞集合為 {172。P∧ Q)用僅含{172。 59/73 ：范式 ?定義 ： (1)：命題變元或命題變元的否定稱為文字； (2)：有限個文字的析取式稱為簡單析取式 (基本和 )，有限個文字的合取式稱為簡單合取式 (基本積 )； (3)：由有限個簡單合取式構(gòu)成的析取式稱為析取范式 (Disjunctive Normal From)，由有限個簡單析取式構(gòu)成的合取式稱為合取范式 (Conjunctive Normal From)。P ∧ Q∧ R；④： (P∧ Q)∨ (172。 ?例 ： 求公式 (P∧ 172。Q)∨ (Q∧ R)，P∨ (P∧ R)∨ (Q∧ R),等，這種不唯一的表達形式給研究問題帶來了不便，因此有必要引進更為標準的范式。Q ，172。Q ， 172。 P Q P∧ Q 172。Q 172。Q P∨ Q 0 0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 n2n264/73 ：范式 ?性質(zhì)： (1)：沒有兩個不同的極小項是等價的，且每個極小項只有一組真值指派使該極小項的真值為真，因此可給極小項編碼，使極小項為“ T”和那組真值指派為對應的極小項編碼；如極小項 172。P ∧ Q∧ 172。P ∨ 172。P∧ 172。Q∧ R M1= P∨ Q∨ 172。Q∨ R 0 1 1 m3= 172。Q∧ 172。P∨ Q∨ 172。Q∨ R 1 1 1 m7= P∧ Q∧ R M7= 172。極大項的否定是極小項，極小項的否定是極大項，即 (4)：所有極小項的析取為永真公式，所有極大項的合取是永假公式，即 iiiinjijimMMmjijiFmmTMM???????????，；， ])12,0[,.(0 1 12 012 0 ???? ???? iiii Mm nn ，67/73 ：范式 ? ?定理 ： 任何命題公式的主析取范式和主合取范式存在且唯一，即任何命題公式都有且僅有一個與之等價的主合取范式和主析取范式。 69/73 ：范式 [公式轉(zhuǎn)換法 ] 唯一性： 設任一命題公式 A有兩個主析取范式 B和 C，則因為 A=B， A=C，所以 B=C，若 B， C是 A的(在不計極小項的順序的情況下 )不同的主析取范式，則必有在存在極小項 mi， mi只存在于 B， C之一中，不妨設 mi在 B中 ,而不在 C中，因此 i之二進制表示 B的一個真值解釋，而對于 C則為真值為假的解釋，這與 B=C矛盾，所以 B和 C相同，同理主合取范式也是唯一的。下面介紹一種兩者之間的轉(zhuǎn)換方法。G)即是 G的主合取范式 即：若 為 G的主析取范式，則 為 172。G 的主合取范式，即 G的主合取范式中沒有出現(xiàn)過的極大項的合取 b： G=172。其中 后剩下的極大項。R),求其對應的主析取范式和主合取范式 ?性質(zhì)： (1)：如果命題公式是永真公式 =它的主析取范式包含所有極小項，此時主合取范式不含有任何極大項，為空，記