【正文】 算 (一階謂詞演算）是命題演算的擴(kuò)充和發(fā)展 ,其本質(zhì)同命題演算 ,是把數(shù)學(xué)中的邏輯論證加以符號(hào)化 ,從而推動(dòng)了這個(gè)數(shù)學(xué)分支的發(fā)展 . 99 第二章 謂詞邏輯 21 謂詞的概念與表示 22 命題函數(shù)與量詞 23 謂詞公式與翻譯 24 變?cè)募s束 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 26 前束范式 27 謂詞演算的推理理論 100 在命題演算中，基本研究單位是原子命題，也就是對(duì)原子命題不再分解，對(duì)研究命題間的關(guān)系而言是較適合的。 證明： （ 1） D P規(guī)則（附加前提） （ 2） ?D?A P規(guī)則 （ 3） A T（ 1）、（ 2） ,I （ 4） A?（ B?C） P規(guī)則 （ 5） B?C T（ 3）、（ 4） ,I （ 6） B P （ 7） C T（ 5）、（ 6）， I （ 8） D?C CP規(guī)則 97 18 推理理論 （續(xù)） 例題 6. 設(shè)有下列情況，結(jié)論是否成立？ (a)或者是晴天。 不相容的概念用于命題公式的證明： 要證明 H1 ? H2 ? … ? Hm =C，只需證明H1,H2,… ,Hm與 ?C是不相容的。 86 18 推理理論 （續(xù)） （ 2）直接證法 P規(guī)則：前提在推導(dǎo)過程中的任何時(shí)候都可以引入使用。這份統(tǒng)計(jì)表格的錯(cuò)誤不是由于材料不可靠，所以這統(tǒng)計(jì)表格的錯(cuò)誤是由于計(jì)算有錯(cuò)誤。或稱 C可以由 H1,H2,… ,Hn邏輯地推出。 ? 性質(zhì) 4. 若 A=B且 C=B，則 (A ? C)=B。 ? P ? Q ? ? Q ? ? P ? Q ? P ? ? P ? ? Q 逆反命題 80 17 重言式與蘊(yùn)涵式 14個(gè)常用蘊(yùn)涵命題： 序號(hào) 表達(dá)式 1 P ? P ＝ P 2 P ? P = P 3 P = P ? Q *4 ?P = P ? Q *5 Q = P ? Q *6 ?(P ? Q) = P *7 ?(P ? Q) = ?Q 8 P ? (P ? Q) = Q 9 ?Q ? (P ? Q) = ?P 81 17 重言式與蘊(yùn)涵式 14個(gè)常用蘊(yùn)涵命題（續(xù)）： 序號(hào) 表達(dá)式 10 ?P ? (P ? Q) ＝ Q 11 (P ? Q) ? (Q ? R) = P ? R 12 (P ? Q) ? (P ? R) ? (Q ? R) = R 13 (P ? Q) ? (R ? S) = (P ? R) ?(Q ? S) 14 (P ? Q) ? (Q ? R) = (P ? R) 82 17 重言式與蘊(yùn)涵式 ? 定理： 設(shè) P， Q為任意兩個(gè)命題公式， P ? Q 的充分必要條件是 P =Q 且 Q = P 。 ? 注： P =Q 與 Q = P 是不等價(jià)的。 ? 定理： 任何兩個(gè)重言式的合取或析取仍然是一個(gè)重言式。 75 16 對(duì)偶與范式（續(xù)） 例題 10：利用真值表技術(shù)求 (P?Q) ?(?P?R)的主析取范式和主合取范式。 71 16 對(duì)偶與范式（續(xù)） 大項(xiàng)的二進(jìn)制編碼： n=2: M00＝ P ? Q M01＝ P ? ?Q M10＝ ?P ? Q M11＝ ?P ? ?Q 72 16 對(duì)偶與范式（續(xù)） 大項(xiàng)的二進(jìn)制編碼： n=3: M000＝ P ? Q ? R M001＝ P ? Q ? ? R M010＝ P ? ?Q ? R M011＝ P ? ?Q ? ?R M100＝ ?P ? Q ? R M101＝ ?P ? Q ? ?R M110＝ ?P ? ?Q ? R M111＝ ?P ? ?Q ? ?R 73 16 對(duì)偶與范式（續(xù)） 大項(xiàng)的性質(zhì) : （ 1）每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為 F，在其余 2n1中指派情況下均為 T。 例題 6： 給定 P ? Q， P ? Q和 ? (P ? Q)，求這些公式的主析取范式。 63 16 對(duì)偶與范式（續(xù)） 兩個(gè)變?cè)?P和 Q的小項(xiàng)的真值表： P Q P?Q P??Q ?P?Q ?P??Q 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 64 16 對(duì)偶與范式（續(xù)） 三個(gè)變?cè)?P， Q， R的小項(xiàng)的真值表： P Q R ?P ? ?Q ? ?R ?P ? ?Q ? R ?P ? Q ? ?R ?P ? Q ? R 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 65 16 對(duì)偶與范式（續(xù)） 三個(gè)變?cè)?P， Q， R的小項(xiàng)的真值表 : P Q R P ? ?Q ? ? R P ? Q ? R P ? Q ? ?R P ? Q ? R 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 1 66 16 對(duì)偶與范式（續(xù)） 三個(gè)變?cè)?P， Q， R的小項(xiàng)的真值表 : 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 67 16 對(duì)偶與范式（續(xù)） 三個(gè)變?cè)?P， Q， R的小項(xiàng)的編碼表 : m000＝ ?P ? ?Q ? ?R m001＝ ?P ? ?Q ? R m010＝ ?P ? Q ? ?R m011＝ ?P ? Q ? R m100＝ P ? ?Q ? ?R m101＝ P ? ? Q ? R m110＝ P ? Q ? ?R m111＝ P ? Q ? R 68 16 對(duì)偶與范式（續(xù)） 小項(xiàng)的性質(zhì) : （ 1）每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為 T，在其余 2n1中指派情況下均為 F。 62 16 對(duì)偶與范式（續(xù)） 定義： n個(gè)命題變?cè)暮先∈椒Q為 布爾合取 （或 小項(xiàng) ），其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 注意：一個(gè)命題的合取范式或析取范式不是唯一的。 ? 例題 1. ? 例題 2. 定理： 設(shè) A*為 A的對(duì)偶式 ， P1,P2,… ,Pn是出現(xiàn)在 A和 A*中的 原子變?cè)?，則 ?A(P1,P2,… , Pn) ? A*(?P1,?P2,… , ?Pn) A(?P1,?P2,… , ?Pn) ? ?A*(P1,P2,… , Pn) 59 16 對(duì)偶與范式（續(xù)） ? 例題 4： p ↑ q 的對(duì)偶式是 p ↓ q 。 P Q P Q T T F T F T F T F F F F 52 15 其它連結(jié)詞 ? 定義： 設(shè) P和 Q是兩個(gè)命題公式，復(fù)合命題 P↑ Q稱為 P和 Q的 “ 與非 ” ，當(dāng)且僅當(dāng) P和 Q的真值都為 T時(shí)， P↑ Q 的真值為 F；否則， P↑ Q的真值為為 T。 P Q的真值為 T，當(dāng)且僅當(dāng) P與 Q的真值不相同時(shí)為 T，否則為 F。 證畢。 例題 5：證明 P? Q ? (P?Q)?(Q?P) 。 P Q P?Q ?P (P?Q) ??P 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 例題 3： (P?Q) v(?P??Q)的真值表。 38 14 真值表與等價(jià)公式 ? 定義： 在命題公式中，對(duì)于分量指派真值的各種可能組合，就確定了這個(gè)命題公式的各種真值情況，把它們匯列成表，就是命題公式的真值表。 解 找出原子命題： P：上海到北京的 14次列車是下午五點(diǎn)半開。 C：我們要做到工作好。 遞歸定義 基礎(chǔ) 歸納 界限 32 13 命題公式及其賦值 （續(xù)） ? 例如： ? 合式公式： ?(P?Q), ?(P?Q) (P?(P??Q)) ?(((P?Q)?(Q?R))? (S? T)) 非合式公式： (P?Q)?(?Q) (P?Q (P?Q)?Q) 括號(hào)不匹配 括號(hào)不匹配 ?應(yīng) 是雙目運(yùn)算符 33 13 命題公式及翻譯 ? 聯(lián)結(jié)詞的運(yùn)算優(yōu)先級(jí)： 高 低 ? ? ? ? ? ? 命題公式的層（描述公式的復(fù)雜程度） ? 命題公式的賦值（解釋、翻譯） ? 真值表 34 13 命題公式及翻譯 （續(xù)） ? 請(qǐng)看教材 Page 1011。 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è)合式公式。 Q：他可能是 100米或 400米賽跑的冠軍。 規(guī)定： P∨ Q的真值為 1當(dāng)且僅當(dāng) P， Q中至少有一個(gè)真值為 1。 0 0 0 0 0 1 0 1 P ? Q 1 0 1 1 P Q P ? Q的真值關(guān)系： 26 12 聯(lián)結(jié)詞 （續(xù)） 析取 設(shè) P， Q為兩個(gè)命題，則新命題“ P或者 Q”稱為命題 P，Q的析取。 P與 ? P的真值關(guān)系： 1 0 ?P 0 1 P 25 12 聯(lián)結(jié)詞 （續(xù)） 合取 設(shè) P， Q是兩命題，新命題“ P并且 Q”稱為命題 P，Q的合取。 記作： ? P 如： P： 2是常數(shù)?？墒?，如果他們絞死他，他就說對(duì)了，就不應(yīng)該絞死他。一切都好辦。看來，沒有任何人能給這位理發(fā)師刮臉了！ 22 唐 但是，他的招牌說明他不給這類人刮臉，因此他不能自己來刮。 21 M：著名的理發(fā)師悖論是伯特納德 寫成一個(gè)推理．即： 伊勒克持拉不知道站在她面前的這個(gè)人是她的哥哥。具體為：如果他的確正在撒謊，那么這句話是真的，所以伊壁孟德不在撤謊，如果他不在撒謊，那么這句話是假的，因而伊壁孟德正在撒謊。這里就產(chǎn)生了問題：理發(fā)師給不給自己刮胡子？如果他給自己刮胡子，他就是自己刮胡子的人，按照他的原則，他不能給自己刮胡子；如果他不給自己刮胡子，他就是不自己刮胡子的人，按照他的原則，他就應(yīng)該給自己刮胡子。愛因斯坦也收藏了整整一書架關(guān)于數(shù)學(xué)游戲和數(shù)學(xué)謎的書。 18 希爾伯特證明了切割幾何圖形中的許多重要定理。這就是說它帶有強(qiáng)烈的游戲色彩。 悖論是 自相矛盾 的 命題 。 不是命題， 祈使句不是命題。 ? 2+3=5 ? 2+3=6 ? 你會(huì)講英語嗎？ ? 3x=5 是命題，真值為 T 是命題，真值為 T 是命題，真值為 F 不是命題 （ 疑問句不是命題） 。 命題 p1