【正文】 Q是兩個(gè)命題公式，復(fù)合命題 P↓ Q稱為 P和 Q的 “ 或非 ” ，當(dāng)且僅當(dāng) P和 Q的真值都為 T時(shí)， P↓ Q 的真值為 F；否則， P↓ Q的真值為為 T。 （ 2）任意兩個(gè)不同小項(xiàng)的合取式為永假。 ? 定理： 一個(gè)重言式，對(duì)同一分量都用任何公式置換，其結(jié)果仍然是一個(gè)重言式。 判斷有效結(jié)論的過(guò)程叫做 論證過(guò)程 ?；蛘呤窍掠?。 21 謂詞的概念與表示 （續(xù)） 104 記號(hào)： 一元謂詞： A(c)。在命題函數(shù)中，客體變?cè)恼撌龇秶Q作 個(gè)體域 。 設(shè)： M(x)： x是人。 a) (?x)(P(x)?Q(y)) (?x)的作用域是 P(x)?Q(y)， x為約束變?cè)? 定義 A，其個(gè)體域?yàn)?E。 上述四種語(yǔ)句，表達(dá)的情況各不相同，故全稱量詞與存在量詞的次序，不能隨意更換。 故 (?x)(?y)A(x,y) ? (?y)(?x)A(x,y) 138 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） 但是 (?x)(?y)A(x,y) 表示對(duì)于 甲村所有的人，乙村都有人和他同姓。 123 合式公式的解釋 見(jiàn)書(shū) P43例題 定義 :邏輯有效式（永真式）、矛盾式（永假）、可滿足式 邏輯有效式是可滿足式，但反之不成立。 （ 5）只有經(jīng)過(guò)有限次地應(yīng)用規(guī)則 (1)、 (2)、 (3)、(4)所得到的公式是合式公式。 N(x)： x是負(fù)數(shù)。 a： 2， 則 命題符號(hào)化為 F(a) ? G(a)。 小寫(xiě)字母：表示客體（個(gè)體）如 a、 b、 c?? 。 93 18 推理理論 （續(xù)） 例題 3. 證明 (A?B)， ?(B?C)=A 證明： （ 1） A ? B P規(guī)則 （ 2） A P規(guī)則（附加前提） （ 3） ?(B?C) P規(guī)則 （ 4） ?B ? ?C T規(guī)則作用于（ 3） （ 5） B T（ 1）、（ 2） ,I （ 6） ?B T（ 4） ,I （ 7） B ? ?B（ 矛盾?。? T（ 5）、（ 6）， I 94 18 推理理論 （續(xù)） 例題 4. 證明 (P?Q)?(P?R)?(Q?S)=S ? R （請(qǐng)同學(xué)們自學(xué)） 95 18 推理理論 （續(xù)） 間接證明方法的另外一種情況（ CP規(guī)則 ）： 若要證明要 H1 ? H2 ? … ? Hm =（ R ? C）， 設(shè) H1 ? H2 ? … ? Hm為 S，即要證明 S=（ R ? C）或證明 S=（ ?R ? C），也即證明 S ?（ ?R ? C）為永真式。 83 18 推理理論 定義： 設(shè) A和 C是兩個(gè)命題公式，當(dāng)且僅當(dāng) AC為一個(gè)重言式，即 A=C，稱 C是 A的有效結(jié)論。 解： 公式 (P?Q) ?(?P?R)的真值表如下： P Q R ?P P ? Q ?P ? R (P?Q) ? (?P?R) T T T F T F T T T F F T F T T F T F F F F T F F F F F F F T T T F T T F T F T F F F F F T T F T T F F F T F F F 主和取范式： 主析取范式： 76 16 對(duì)偶與范式（續(xù)） 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 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 77 16 對(duì)偶與范式（續(xù)） 例題 11：將 (P?Q) ?(?P?R)化為主合取范式。 例如：兩個(gè)變?cè)?P和 Q，其小項(xiàng)為： P?Q， P??Q， ?P?Q，?P??Q。 P Q P Q T T F T F T F T T F F F ? 定理： 設(shè) P,Q,R為任意命題公式。 ?含 n個(gè)命題變?cè)拿}公式，共有 2n組賦值。 ? （ 2）如果 A是一個(gè)合式公式，那么 ?A是合式公式。 記作： P∧ Q 如： P：北京是中國(guó)的首都。吉訶德 悖論 M：小說(shuō) 《 唐 20 伊勒克特拉悖論 (Eletra paradox) 邏輯史上最早的內(nèi)涵悖論。然而，切莫以為大數(shù)學(xué)家都看不起 “ 趣味數(shù)學(xué) ” 問(wèn)題。 命題 P2：今天下雨。 9 什么是離散數(shù)學(xué)？ 本課程將學(xué)習(xí) 數(shù)理邏輯 、 集合論 以及 圖論、代數(shù)系統(tǒng) 的部分內(nèi)容 。 12 第一章 命題邏輯 ? 命題演算是數(shù)理邏輯的基本組成部分，是謂詞演算的基礎(chǔ)。 11 命題及其表示法 （續(xù)） 16 判斷下列句子哪些是命題（續(xù)）？ ? 請(qǐng)關(guān)上門(mén)！ ? 除地球外的星球 有生物。紐曼奠基了博弈論。 站在她面前的人是奧列期特。 M：一天，有個(gè)旅游者回答 —— 旅游者：我來(lái)這里是要被絞死。 Q：北京是一個(gè)故都。 解 找出原子命題： A：我們要做到身體好。 P Q P?Q ? (P?Q) ?P ?Q ?Pv?Q (P?Q)?(?Pv?Q) 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 永真公式 41 14 真值表與等價(jià)公式 （續(xù)） 定義： 給定兩個(gè)命題公式 A和 B，設(shè) P1， P2， … ， Pn，為所有出現(xiàn)在 A和 B中的原子變?cè)? P Q P↓ Q T T F T F F F T F F F T 54 15 其它連結(jié)詞 ? 命題公式： 1 2 3 4 5 6 7 8 P Q T F P Q ?P ?Q P?Q P↑ Q T T T F T T F F T F T F T F T F F T F T F T T F F T T F F T F F T F F F T T F T 9 10 11 12 13 14 15 16 P Q P?Q P↓ Q P?Q P Q P?Q P Q Q?P Q P T T T F T F T F T F T F T F F T F T T F F T T F T F F T F T F F F T T F T F T F 55 15 其它連結(jié)詞 等價(jià)公式： 1. P?Q ? (P?Q) ?(Q?P) 2. (P?Q) ? ?P ? Q 3. P ? Q ? ?(?P ? ?Q)， P ? Q ? ?(?P ? ?Q) 4. P Q ? ?(P ? Q) 5. P Q ? ?( P?Q) 6. P↑ Q ? ?(P ? Q) 7. P↓ Q ? ?(P ? Q) 最小聯(lián)結(jié)詞組： {?， ?}或 {?， ?}或 {↑ }或 {↓ } 56 回顧表 10個(gè)命題定律： 序號(hào) 定律 表達(dá)式 1 對(duì)合律 ??P ? P 2 冪等律 P?P ? P P?P ? P 3 集合律 (P ? Q) ? R ? P ? (Q ? R) (P ? Q) ? R ? P ? (Q ? R) 4 交換律 P ? Q ? Q ? P P ? Q ? Q ? P 5 分配律 P ? (Q ? R) ? (P ? Q) ? (P ? R) P ? (Q ? R) ? (P ? Q) ? (P ? R) 16 對(duì)偶與范式 57 序號(hào) 定律 表達(dá)式 6 吸收律 P ? (P ? Q) ? P P ? (P ? Q) ? P 7 德 .摩根律 ?(P ? Q) ? ? P ? ? Q ?(P ? Q) ? ? P ? ? Q 8 同一律 P ? F ? P P ? T ? P 9 零律 P ? T ? T P ? F ? F 10 否定律 P ? ? P ? T P ? ? P ? F 16 對(duì)偶與范式（續(xù)） 回顧表 10個(gè)命題定律： 58 16 對(duì)偶與范式（續(xù)） ? 定義： 在給定的命題中，將聯(lián)結(jié)詞 ?換成 ?，將 ?換成 ?，若有特殊變?cè)?F和 T也相互替代，所得公式 A*稱為 A的對(duì)偶式。 （ 3）全體小項(xiàng)的析取式為永真，記為： 2101 210...nniim m m m T???? ? ? ??69 16 對(duì)偶與范式（續(xù)） 定義： 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由小項(xiàng)的析取所組成，則該等式稱為原式的主析取范式。 ? 定理： 設(shè) A， B為兩個(gè)命題公式， A ? B 當(dāng)且僅當(dāng) A ? B為一個(gè)重言式。 84 18 推理理論 （續(xù)） 三種基本論證過(guò)程方法： 真值表法、直接證法、間接證法。 (b)如果是晴天，我去看電影。 二元謂詞： A(c,d)。個(gè)體域可以是有限的，也可以使無(wú)限的。 P(x)： x是質(zhì)數(shù)。 b) (?x)(P(x)?(?y)(R(x,y)) (?x)的作用域是 (P(x)?(?y)(R(x,y))， (?y)的作用域是 R(x,y)。若對(duì) A的任意變?cè)x值， A都為真，則稱該 A在 E上是有效的（或永真的）。 139 26 前束范式 定理：任何一個(gè)謂詞公式均等價(jià)于某個(gè)前束范式。 (?y)(?x)A(x,y)： 乙村與甲村有人都同姓。 解：對(duì) y施行代入，得到： (?x)(P(z)?R(x,z) 但是 (?x)(P(x)?R(x,x) 和 (?x)(P(z)?R(x,y) 都是錯(cuò)誤的。 （ 4）若 A都是合式公式， x是出現(xiàn)在 A中的任何變?cè)?，則 (?x)A和 (?x)A都是合式公式。 R(x)： x是正數(shù)。 G(x)： x是偶數(shù)。 （客體關(guān)系） 謂詞 客體 客體 103 謂詞記號(hào)： 大寫(xiě)字母：表示謂詞，如： F、 G、 H?? 。 不相容的概念用于命題公式的證明： 要證明 H1 ? H2 ? … ? Hm =C，只需證明H1,H2,… ,Hm與 ?C是不相容的。 ? 性質(zhì) 4. 若 A=B且 C=B，則 (A ? C)=B。 75 16 對(duì)偶與范式（續(xù)） 例題 10：利用真值表技術(shù)求 (P?Q) ?(?P?R)的主析取范式和主合取范式。 62 16 對(duì)偶與范式（續(xù)） 定義： n個(gè)命題變?cè)暮先∈椒Q為 布爾合取 （或 小項(xiàng) ），其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 P Q的真值為 T，當(dāng)且僅當(dāng) P與 Q的真值不相同時(shí)為 T，否則為 F。 38 14 真值表與等價(jià)公式 ? 定義： 在命題公式中，對(duì)于分量指派真值的各種可能組合，就確定了這個(gè)命題公式的各種真值情況，把它們匯列成表，就是命題公式的真值表。 T T F T P ? Q F F F T T F T T P Q F T T T P ? Q F F F T T F T T P Q F F F F F T F T P ? Q T F T T P Q T F ?P F T P T F F T F F F T T F T T P Q P? Q 31 13 命題公式及其賦值 ? 定義：合式公式 ? （ 1）單個(gè)命題變?cè)旧硎且粋€(gè)合式公式。 P與 ? P的真值關(guān)系： 1 0 ?P 0 1 P 25 12 聯(lián)結(jié)詞 （續(xù)） 合取 設(shè) P， Q是兩命題，新命題“ P并且 Q”稱為命題 P，Q的合取?？磥?lái)，沒(méi)有任何人能給這位理發(fā)師刮臉了！ 22 唐 具體為：如果他的確正在撒謊，那么這