【正文】 律 E21 P∧ 172。(P∨ Q) =172。 (2). ((P→Q)∧ P) →Q； (3). P?(Q ∧ R)。 35/73 公式的解釋與真值表 ： ?定義 ： (1). 公式 G稱為永真公式 （ 重言式 ） ， 如果在它的所有解釋下都為 “ 真 ” ； (2). 公式 G稱為可滿足的 ， 如果它不是永假的； (3). 公式 G稱為永假公式 （ 矛盾式 ） , 如果在它的所有解釋下都為 “ 假 ” 。 一般來說 ， 若有 n個命題變元 ， 則應(yīng)有 2n個不同的解釋 。 P∨ Q ∨ (R， P∨ Q ∨ 不是命題公式 29/73 ?注意： –如果 G是含有 n個命題變元 P1, P2, … ,Pn的公式 ，通常記為 G（ P1, … ,Pn） 或簡記為 G。 但不是說原子命題和聯(lián)結(jié)詞的一個隨便的組合都可以為命題公式 ， 我們用遞歸的方法來定義命題公式 。是自然語言中的 “ 非 ” ﹑ “不 ” 和 “ 沒有 ” 等的邏輯抽象 (2)∧ 是自然語言中的 “ 并且 ” ﹑ “既 … 又 … ” ﹑ “且 ” ﹑ “和 ” 等的邏輯抽象 (3)∨ 是自然語言中的 “ 或 ” 和 “ 或者 ” 等的邏輯抽象；但 “ 或 ” 有 “ 可兼或 ” ﹑ “不可兼或 ” ﹑ “近似或 ” 三種 (4)P→Q是自然語言中的 “ 只要 P， 就 Q” ﹑ “因為P， 所以 Q” ﹑ “P僅當 Q”等的邏輯抽象 25/73 (5) ?是自然語言中的 “ 充分必要條件 ” 和 “ 當且僅當 ” 等的邏輯抽象 (6)聯(lián)結(jié)詞連接的是兩個命題真值之間的聯(lián)結(jié) ， 而不是命題內(nèi)容之間的連接 ， 因此復(fù)合命題 的真值只取決于構(gòu)成他們的各原子命題的真 值 (7) ∧ ， ∨ ， ?具有對稱性 ， 而 172。((P ∧ 172。 20/73 命題與命題聯(lián)結(jié)詞 ?五個聯(lián)結(jié)詞 聯(lián)結(jié)詞 記號 表達式 讀法 真值結(jié)果 否定 172。 “Q是 P的必要條件 ” 。 P ∨ Q為真當且僅當 P， Q至少一個為真 。P 為真當且僅當 P為假 。 例 ， 合肥是安徽的省會當且僅當鳥會飛 。 11/73 命題與命題聯(lián)結(jié)詞 ?例 11：命題示例。 –我們要介紹的是數(shù)理邏輯中最基本的內(nèi)容：命題邏輯和謂詞邏輯。 – 離散數(shù)學(xué)學(xué)習(xí)十分有益于概括抽象能力 、 邏輯思維能力 、 歸納構(gòu)造能力的提高 ， 能夠培養(yǎng)提高學(xué)生的數(shù)學(xué)思維能力和對實際問題的求解能力 。 充分描述了計算機科學(xué)離散性的特征 。思維的形式結(jié)構(gòu)包括了 概念﹑ 判斷 和 推理 之間的結(jié)構(gòu)和聯(lián)系，其中 概念 是思維的基本單位，通過概念對事物是否具有某種屬性進行肯定或否定的回答，就是 判斷 。它研究以 “ 命題 ” 為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系，研究什么是命題？如何表示命題？怎樣由一組前提推導(dǎo)一些結(jié)論。 12/73 命題與命題聯(lián)結(jié)詞 ?例 12：下列句子哪些是命題，判斷命題的真假。 用數(shù)學(xué)方法研究命題之間的邏輯關(guān)系時 （ 也就是在命題演算中 ） ， 這些聯(lián)結(jié)詞可以看作是運算符 ， 因此也叫作 邏輯運算符 。 命題與命題聯(lián)結(jié)詞 16/73 命題與命題聯(lián)結(jié)詞 ?定義 ： 設(shè) P ﹑ Q是任意兩個命題 ， 復(fù)合命題 “ P并且 Q”（ 或 “ P和 Q”） 稱為 P與 Q的合取式（ Conjunction） ， 記作 P ∧ Q， “ ∧ ” 為合取聯(lián)結(jié)詞 。 18/73 命題與命題聯(lián)結(jié)詞 ?定義 ： 設(shè) P ﹑ Q是任意兩個命題 ， 復(fù)合命題 “ 如果 P則 Q” 稱為 P與 Q的蘊含式 （ Implication） ， 記作 P→Q， “ →” 為 蘊含聯(lián)結(jié)詞 ， P稱為蘊含式的前提 ， 假設(shè)或前件 ， 而 Q稱為結(jié)論式后件 。 19/73 命題與命題聯(lián)結(jié)詞 ?給定命題 P→Q， 我們把 Q→P， ﹁ P→﹁ Q， ﹁Q→﹁ P分別叫作命題 P→Q的逆命題 ， 反命題和逆反命題 。P 為真當且僅當 P為假 合取 ∧ P ∧ Q P且 Q P ∧ Q為真當且僅當P， Q同為真 析取 ∨ P ∨ Q P或 Q P ∨ Q為真當且僅當P， Q至少一個為真 蘊含 → P→Q 若 P則 Q P→Q為假當且僅當 P為真 Q為假 等價 ? P?Q P當且僅當Q P?Q為真當且僅當 P，Q同為真假 21/73 命題與命題聯(lián)結(jié)詞 ?一般約定： a)：運算符 (聯(lián)結(jié)詞 )結(jié)合力強弱順序為： 172。Q ∨ R) →R ∨ P∨ Q ?22/73 ?例 ：符號化下列命題。 使得在研究時 ， 只需考慮命題的真值 ， 而不知曉命題的具體含義 。 公式常用符號G﹑ H… 等表示 。 –合成公式無限多 。P P∧ Q P ∨ Q P→Q P?Q 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 33/73 公式的解釋與真值表 例 ： 設(shè)公式 G= ((P∧ Q) →R )∧ (P?Q)， 其中 P，Q， R是 G的命題變元 ， 則其真值表如下： P Q R P∧ Q (P∧ Q) →R P?Q ((P∧ Q) →R )∧ (P?Q) 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 0 0 34/73 公式的解釋與真值表 ：一些特殊的公式 例 ： 考慮： G1= 172。 對任意的公式 ， 判定其是否為永真公式 ， 永假公式 ， 可滿足公式的問題稱為給定公式的判定問題 。 證明： 必要性： 假定 G?H， 則 G和 H在其任意解釋 I下 ，或同為真或同為假 ， 由 “ ?” 的意義知 ， G ?H在任意解釋 I下 ， 其真值為真 ， 即 G ?H為重言式； 充分性： 假設(shè)公式 G ?H是重言式 ， I是它的任意解釋 ， 在 I下 ， G ?H為真 ， 因此 ， G， H或同為真或同為假 ， 由于 I的任意性 ， 故有 G?H。摩根定律 E11 172。P 歸謬律 E24 (P→Q) =172。 45/73 公式的解釋與真值表 ：代入規(guī)則和替換規(guī)則 當一個公式是永真式或永假式時 ， 其公式的真值完全跟隨其命題變元的真值的變化而變化 ， 因此 ，當用其他公式來取代公式中的命題變元時 ， 不會改變公式的永真性和永假性 ?定理 (代入定理 ) ： 設(shè) G(P1, … ,Pn)是一個命題公式 ， 其中 P1, … ,Pn是命題變元 ， G1(P1, … ,Pn), … Gn(P1, … ,Pn)為任意的命題公式 ， 此時若 G是永真公式或永假公式 ， 則用 G1取代 P1,… ,Gn取代 Pn后 ，得到的新的命題公式 G(G1,… ,Gn) = G’(P1, … ,Pn)也是一個永真公式或永假公式 。Q ∧ 172。 例 ， 172。構(gòu)成的公式 ， 則A*=B* (對偶原理 ) 例 ， 若 (P∧ Q)∨ (172。 我們前面介紹了 5個聯(lián)結(jié)詞 ， 是否夠用呢 ？ 聯(lián)結(jié)詞的擴充 ? 1. 一元運算： 我們來看一個命題變元在一個一元運算的作用下可能的真值表 。P， f7 = 172。(P∨ Q) ， 這 9個聯(lián)結(jié)詞構(gòu)成命題演算中的所有聯(lián)結(jié)詞 。,∧ ,∨ }也是一個聯(lián)結(jié)詞完備集 ,而A∨ B=172。 ?同理， {172。 ， ∨ }的公式等價地表示出來。P∧ Q)； ⑤： (P∨ Q)∧ (172。 ?定義 ： (1)包含 A中所有命題變元或其否定一次僅一次的簡單合取式，稱為極小項； (2)包含 A中所有命題變元或其否定一次僅一次的簡單析取式，稱為極大項； (3)由有限個極小項組成的析取范式稱為主析取范式； (4)由有限個極大項組成的合取范式稱為主合取范式。P ∨ 172。P∨ 172。R 也可用 ( )來表示。Q∧ 172。P∧ Q∧ R M3= P∨ 172。R 1 1 0 m6= P∧ Q∧ 172。 [真值表技術(shù) ] ?例 ： 求命題公式 ((P∧ Q)→R)∧ (P?Q)的主析取范式。 71/73 ：范式 ? (1)：已知公式 G的主析取范式求公式 G的主合取范式的步驟如下： a：求 172。(172。 (真值表和主范式是描述命題公式標準形式的兩種不同的等價形式 )。 我們將由 {G1， G2， … ， Gn}推理 H，用蘊含式表示為： (G1∧ G2∧ …Gn) →H 將由 {G1， G2， … ， Gn}正確推理出 H，用蘊含式表示為： G1∧ G2∧ …Gn =H 76/73 ：命題邏輯的推理理論 推理的形式結(jié)構(gòu)為： G1∧ G2∧ …Gn →H ，書寫為： 前提： G1， G2， … ， Gn 結(jié)論： H 推理的有效性判斷，即判斷推理是否正確，也就是判斷 G1∧ G2∧ …Gn→H 是否為重言式。Q ； (3). H： Q。若她去游泳，她就不去看電影了。B =A 析取三段論 6 .(A→B) ∧ (B→C) =A→C 假言三段論 7 .(A?B) ∧ (B?C) =A?C 等價三段論 8 .(A→B)∧ (C→D)∧ (A∨ C) =(B∨ D) 構(gòu)造性二難 (A→B)∧ (172。A ⑻ 假言三段論規(guī)則： (A→B)， (B→C)|=(A→C) ⑼ 析取三段論規(guī)則： (A ? B)， 172。t 結(jié)論： q ?例 ： 分析下列事實：“早飯我吃面包或蛋糕；如果我吃面包，那么我還要喝牛奶；如果我吃蛋糕，那么我還要喝咖啡；但我沒有喝咖啡，所以早飯我吃的是牛奶和面包。如果 D參加球賽，則 C不參加球賽。 由定理知： 歸謬法：將結(jié)論的否定作為附加前提引入，公式序列的最后得到一矛盾式，則原結(jié)論成立。 ∧ ， ∨ ， →， ?； (3)括號與逗號 (， ) 2)公式 (同前面命題公式的定義 ) 3)推理規(guī)則 (用 12條規(guī)則 ) ? （定理 ） (1)可靠性：如果 G1， G2， …Gn |=H ，則G1∧ G2∧ …Gn →H 永真 (2)完備性：反之