【正文】 ?對于一個(gè)具體的實(shí)際系統(tǒng)，用形式系統(tǒng)來描述，有兩個(gè)具體的問題必須解決： (1).可靠性問題：形式系統(tǒng)中正確推理出來的公式，定理在所討論的具體實(shí)際系統(tǒng)中是否為永真； (2).完備性問題：具體實(shí)際系統(tǒng)中的永真的語句是否均為形式系統(tǒng)內(nèi)的定理。所以拉齊奧隊(duì)不能獲得亞軍 88/73 ：命題演算的自然推理形式系統(tǒng) ? 永真式是命題邏輯推理中一個(gè)非?；镜闹匾拍睿瑸榱讼到y(tǒng)研究它們，就需要把所有的永真式包括在一個(gè)系統(tǒng)內(nèi)，作為一個(gè)整體來研究，這樣的系統(tǒng)應(yīng)當(dāng)是一個(gè)形式系統(tǒng)，也只有形式系統(tǒng)，才能進(jìn)行充分的研究，從而掌握全部規(guī)律。 86/73 ：命題邏輯的推理理論 ?定理 ： 設(shè)命題公式集合 {G1， G2， … ， Gn}是一致的，于是從前提集合 {G1， G2， … ， Gn}出發(fā)可以邏輯地推出公式 H的充要條件是從前提集合{G1， G2， … ， Gn， 172。 85/73 ：命題邏輯的推理理論 ?例 ： 設(shè)前提條件 T={P→(Q→S)， 172。 ?例 ： 如果 A參加球賽，則 B或 C也將參加球賽。 ?例 ： 用構(gòu)造法證明，找出下列推理的有效結(jié)論。r， s →t， 172。B∨ 172。C)破壞性二難 82/73 ：命題邏輯的推理理論 由著 9個(gè)定律中的 8個(gè)可以得到 8個(gè)推理規(guī)則： ⑷附加規(guī)則： A|=(A∨ B) ⑸ 化簡規(guī)則： (A∧ B)|=A ⑹ 假言推理規(guī)則： (A→B) ， A |=B ⑺ 拒取式規(guī)則： (A→B)， 172。A) =B構(gòu)造性二難 (特殊形式 ) 9 .(A→B)∧ (C→D)∧ (172。B =172。 以上方法，當(dāng)形式結(jié)構(gòu)比較復(fù)雜，特別是所含的命題變元較多時(shí)，一般很不方便，下面介紹構(gòu)造證明法。 79/73 ：命題邏輯的推理理論 將推理的形式結(jié)構(gòu)轉(zhuǎn)化為主析取范式，但仍判斷其是否為重言式。P ， G2： P→Q； 直接用等值演算來判斷推理的形式結(jié)構(gòu)是否是重言式。P。則 H是G1， G2， … ， Gn的邏輯結(jié)果。 =：邏輯蘊(yùn)含關(guān)系， G=H不是命題公式，計(jì)算機(jī)判斷 G=H辦不到； →：蘊(yùn)含聯(lián)結(jié)詞， G →H是命題公式，計(jì)算機(jī)可判斷 G →H為永真公式。 ?定義 ： 設(shè) G1， G2， … ， Gn， H是命題公式，若對于 G1， G2， … ， Gn， H中出現(xiàn)的命題變元的任意一組賦值，或者 G1∧ G2∧ …Gn 為假，或者當(dāng)G1∧ G2∧ …Gn 為真， H也為真，則稱 H是 G1，G2， … ， Gn的有效結(jié)論 (Efficacious Conclusion)或邏輯結(jié)果 (Logic Conclusion)。Q∧ 172。G 的主合取范式。 ilki m1G ???injki mG?????21),1()12,1,0()2,2,1( kimimkim ii jninj ??? ????? 中去掉是inininjkijkijki MmmGG?????? ???????????212121 )(72/73 ：范式 ? (2)：已知公式 G的主合取范式，求 G的主析取范式的步驟如下： a：求 172。(172。但兩者之間必然有相應(yīng)的關(guān)系。 68/73 ：范式 ?利用真值表技術(shù)求主析取范式和主合取范式的方法： ① ：選出公式的真值結(jié)果為真的所有行，在這樣的行中，找到其每一個(gè)解釋所對應(yīng)的極小項(xiàng)，將這些極小項(xiàng)析取即可得到相應(yīng)的主析取范式； ②：選出公式的真值結(jié)果為假的所有行，在這樣的行中，找到其每一個(gè)解釋所對應(yīng)的極大項(xiàng)，將這些極大項(xiàng)合取即可得到相應(yīng)的主合取范式。R 66/73 ：范式 (3)：任意兩極小項(xiàng)的合取必假，任意兩個(gè)極大項(xiàng)的析取必為真。P∨ 172。Q∧ R M5= 172。R 1 0 0 m4= P∧ 172。R M2= P∨ 172。P∧ 172。 000m 0m 010m2m)M(M 711165/73 ：范式 三個(gè)命題變元的真值取值與極小項(xiàng)和極大項(xiàng)的對應(yīng)對位關(guān)系表： P Q R 極小項(xiàng) 極大項(xiàng) 0 0 0 m0= 172。因此可給極大項(xiàng)編碼，使極大項(xiàng)為“ F”的那組真值指派為對應(yīng)的極大項(xiàng)的編碼，如極大項(xiàng) 172。R 只有在 P， Q， R分別取真值 0， 0， 0時(shí)才為真，所以有時(shí)又可用 ( )來表示，又如 172。P∨ Q P∨ 172。P∧ 172。其真值表如下： 一般來說，對于 n個(gè)命題變元，則應(yīng)有 個(gè)不同的極小項(xiàng)和 個(gè)不同的極大項(xiàng)。P ∨ Q, P∨ 172。P ∧ Q， P∧ 172。如公式(P∨ Q)∧ (P∨ R)與之等價(jià)的公式有： P∨ (Q∧ R)，(P∧ P)∨ (Q∧ R) ， P∨ (Q∧ 172。 61/73 ：范式 ?定理 ： 任一命題公式都存在著與之等值的析取范式和合取范式。R ； ③： 172。這樣給命題演算帶來了一定的困難，因此，有必要使命題公式規(guī)范化，為此，引入了范式的概念。R))∧ (172。, →}， {172。 57/73 聯(lián)結(jié)詞的完備集 ?證明聯(lián)結(jié)詞完備集 {172。A∧ 172。,∧ ,∨ ,→,?}是一個(gè)聯(lián)結(jié)詞完備集，而 A→B=172。P ， (P↑Q)↑(P↑Q)?P∧ Q， (P↑P)↑(Q↑Q)?P∨ Q ： P↓Q ? Q↓P， P↓P ? 172。(P→Q) ， P↑Q ? 172。(P?Q) f10=Q， f11=P， f12 = 172。(P→Q)， f4= 172。 ? ： 考慮兩個(gè)變元在一個(gè)二元運(yùn)算作用下可能的真值表 。P ∧ Q ?定理 ： 如果 A=B ， 且 A ， B 為命題變元P1,P2, … ,Pn及聯(lián)結(jié)詞 ∧ ， ∨ ， 172。P∨ Q)= 172。P2, …, 172。P ∧ (Q∨ R)互為對偶； P∨ F和 P∧ T互為對偶 。在 A中將 ∧ ， ∨ ， T， F分別換以 ∨ ， ∧ ， F， T得到公式 A*， 則 A*稱為 A的對偶公式 。 (4).(172。Q)∧ Q)是永真公式； (2).P→(Q→R)=(P∧ Q)→R。(P→Q) →P；用 H(P, Q) =(P ∧ Q)； S(P, Q) =(P ?Q)代入 G驗(yàn)證代入定理。 ∴ A ?C為重言式 ， 即 A=C； A=B， B=C， 即 A→B， B→C為真； ∴ (A→B)∧ (B→C)為真 ， 由公式 I6： A→C為重言式 ， 即 A=C。P 逆反律 42/73 公式的解釋與真值表 ： ?定義 ：若 A→B是一永真式 ， 那么稱為永真蘊(yùn)含式 ， 記為 A?B， 讀作 A永真蘊(yùn)含 B ?常用的永真蘊(yùn)含式 I1 P=P∨ Q I2 P∧ Q=P I3 P∧ (P→Q) =Q I4 (P→Q) ∧ 172。P=F 矛盾律 E22 (P∧ Q→R) =(P→(Q→R)) 輸出律 E23 ((P→Q) ∧ (P→172。P∨ 172。P∧ 172。 40/73 公式的解釋與真值表 ?常用邏輯恒等式（ P， Q， R為任意命題， T為真命題， F為假命題）： E1 172。 ： ?定義 ： 公式 G， H， 如果在其任意解釋下 ， 其真值相同 ， 則稱 G是 H的等價(jià)式 (Equivalent)或稱 G恒等于 H， 記作 G?H。 其判定方法有 真值表法 和 公式推演法 。有時(shí)也稱永假公式為不可滿足公式 。(P∧ 172。 ?定義 ： 公式 G在其所有可能的解釋下所取真值的表 ， 稱作 G的真值表 (Truth)。B， B是 n層公式； b). A=B∧ C， 其中 B， C分別為 i層和 j層公式 ,且n=max(i, j)； c). A=B∨ C， 其中 B， C的層次同 b； d). A=B→C， 其中 B， C的層次同 b； e). A=B?C， 其中 B， C的層次同 b； 從圖論的觀點(diǎn)來看每個(gè)多層公式可以用一個(gè) “ 樹 ”來表示 。 –原子命題變元是最簡單的 （ 合式 ） 公式 ， 也叫原子 （ 合式 ） 公式 。 P∧ Q)， (P→(172。 公式的解釋與真值表 28/73 公式的解釋與真值表 ?定義 ：命題公式 ， 也叫 （ 合式 ） 公式 (1).命題變元本身是一個(gè)公式； (2).如果 P是公式 ， 則 172。 而一個(gè)任意的沒有賦予具體內(nèi)容的原子命題是一個(gè)變量命題 ， 常稱它為命題變量 (或命題變元 、 命題變項(xiàng) )(Proposition Variable)。 →沒有 (8) ∧ ， ∨ ， 172。 d)：若不是他生病了或出差了 ， 我是不會同意他不參加學(xué)習(xí)的 。Q) ∨ R) →((R ∨ P)∨ Q)) 172。 b)：相同的運(yùn)算符 ， 從左到右次序計(jì)算時(shí) ， 括號可省去 。 172。 P?Q為真當(dāng)且僅當(dāng) P， Q同為真假 。 “Q每當(dāng) P”。 例 ， P： G是正方形 ， Q： G的四邊相等 ， 則 P→Q：如果 G是正方形 ， 則 G的四邊相等 。 例 ， P： 2是素?cái)?shù) ， Q： 2是奇數(shù) 。 例 ， P： 2是素?cái)?shù) ， Q： 2是偶數(shù) 。 如： P： 2是素?cái)?shù) ， 則 172。P ， “ 172。 ?注意： –命題通常用大寫英文字母 （ 可帶下標(biāo) ） 來表示 。 –命題的真值有時(shí)可明確給出，有時(shí)還需要依靠環(huán)境條件，實(shí)際情況，時(shí)間才能確定其真值。 (a):今天下雪 (b):3+3=6 (c):2是偶數(shù)而 3是奇數(shù) (d):陳勝起義那天，合肥下雨 (e):較大的偶數(shù)都可表為兩個(gè)質(zhì)數(shù)之和 (f):x+y4 (g):真好啊 ! (h):x=3 (i):你去哪里？ (j):我正在說謊。 ?命題的取值稱為真值。即一般所謂的古典邏輯。 ?數(shù)理邏輯 –用數(shù)學(xué)方法研究推理的規(guī)律稱為數(shù)理邏輯。 ?教學(xué)內(nèi)容 – 數(shù)理邏輯 、 集合論 、 代數(shù)結(jié)構(gòu) 、 圖論 4/73 引言 ?教學(xué)內(nèi)容 第一部分 數(shù)理邏輯 第一章 命題邏輯 第二章 謂詞邏輯 第二部分 集合論 第三章 集合代數(shù) 第四章 二元關(guān)系 5/73 引言 ?教學(xué)內(nèi)容 第二部分 集合論 第五章 函數(shù) 第六章 集合的基數(shù) 第三部分 代數(shù)結(jié)構(gòu) 第七章 代數(shù)系統(tǒng) 第八章