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