【文章內(nèi)容簡(jiǎn)介】 ? p代表 “我很累 ”, ? q代表 “我下班早 ”, ? r代表 “我去商店看看 ” 命題邏輯 （ 3）李四是計(jì)算機(jī)系的學(xué)生 , 他住在 312室或 313室 . ? p∧ ((q∨ r)∧ (172。(q∧ r)))，其中： ? p代表 “李四是計(jì)算機(jī)系學(xué)生 ”, ? q代表 “李四住 312室 ”, ? r代表 “李四住 313室 ”. ? 還可表示為： ? p∧ ((q∧ (172。 r)) ∨ ((172。q)∧ r)) 命題邏輯 命題公式及其解釋 原子公式：?jiǎn)蝹€(gè)命題變?cè)?、單個(gè)命題常元稱為原子公式。 命題公式：由如下規(guī)則生成的公式稱為命題公式： 1. 單個(gè)原子公式是命題公式。 2. 若 A ,B是命題公式，則 ~A , A∧ B , A∨ B , A ?B , A ? B是公式。 3. 所有命題公式都是有限次應(yīng)用 2得到的符號(hào)串。 命題邏輯 命題公式的 解釋 ：給命題公式中的每一個(gè)命題變?cè)付ㄒ粋€(gè)真假值，這一組真假值，就是命題公式的一個(gè)解釋。用 I表示。 例如：公式 G= (A?B) ?C 的一個(gè)解釋是： I1(G) = A/T, B/F, C/T 在解釋 I1(G)下 G為真。 永真公式與永假公式：如果公式在它所有的解釋 I下，其值都為 T，則稱公式 G為恒真的；如果其值都為 F，則稱公式 G為恒假的（不可滿足的）。 命題邏輯 注意： 關(guān)于五個(gè)聯(lián)結(jié)詞的約定 ： * 結(jié)合力的強(qiáng)弱順序： 172。， ?， ?， ?， ? * 聯(lián)結(jié)詞相同時(shí)，從左至右運(yùn)算。 解釋的個(gè)數(shù) ：如果一個(gè)公式 G中有 n個(gè)不同的原子公式（或簡(jiǎn)稱原子），則 G有 2n個(gè)不同的解釋，于是 G在 2n個(gè)解釋下有 2n個(gè)真值。如果將這些真值和它們的解釋列成表，就是 G的真值表。 命題邏輯 等價(jià)命題公式 如果兩個(gè)命題公式所含原子公式相同，且在任一解釋下，兩個(gè)命題公式的值相同 ，則稱這兩個(gè)命題公式為等價(jià)命題公式或等價(jià)公式。常用的等價(jià)公式有： 1. (P ? Q)= (P ? Q) ? (Q ? P) 2.(P ? Q)=(172。P ? Q) 3. 172。(172。P)= P ： P ? Q=Q ? P P ? Q=Q ? P ： P ? F=P , P ? T=P P ? F=F , P ? T=T ： P ? ~P=T, P ? ~P=F ? 摩根定律： ~(P ? Q)=~P ? ~Q ~(P ? Q)=~P ? ~Q ： P ?(Q ? R)=(P ? Q) ? R P ? (Q ? R)=(P ? Q) ?R ： P ?(Q ?R)=(P ? Q) ? (P ? R) P ? (Q ? R)=(P ?Q) ? (P ?R) 命題邏輯 證明兩個(gè)公式等價(jià)，可用真值表，也可用基本公式。 例如 要證明公式 P ? Q=~Q ? ~P [證 ] P ? Q =~ P ? Q =~ P ?~ (~ Q ) =~(~Q) ?~P =~Q ?~P 命題邏輯 永真蘊(yùn)涵式 若命題公式 G ? H是恒真的 ，稱其為永真蘊(yùn)涵式。記為 G?H，讀做“ G蘊(yùn)涵 H” ，也稱“ G是 H的邏輯結(jié)果”。 永真蘊(yùn)涵式 常用的永真蘊(yùn)涵式： 1. P ? P ? Q [證 ] P ? P ? Q = ~P ? (P ?Q) = ~P ? P ?Q = T ? Q = T 2. P ? Q ? P [證 ] P ? Q ? P =~(P ? Q) ? P = ~P ? ~Q ?P =T ?~Q= T 3. P ? (P ? Q) ? Q 4.( P ? Q) ? ~Q ? ~P 5. ~P ?(P ? Q) ? Q 6.(P ? Q) ?(Q ? R) ? (P ? R) 7.( P ? Q) ?( (Q ? R) ?( P ? R)) 8.((P ? Q) ?( R ? S)) ? (P ? R ? Q ? S) 9.(( P ? Q) ?( Q ? R)) ?( P ? R) 在命題邏輯中有一個(gè)三段論法： P:“ 所有的人都會(huì)犯錯(cuò)誤” Q:“ 張三是人” R:“ 張三會(huì)犯錯(cuò)誤” R應(yīng)該是 P和 Q的邏輯結(jié)論。但在命題邏輯中無法準(zhǔn)確表達(dá)這三個(gè)命題的邏輯關(guān)系 。 為準(zhǔn)確表達(dá)此類公式，必須引進(jìn)謂詞和量詞的概念 。 因?yàn)? ( P ? Q ) ? R 不是恒真 的。如：解釋 : I=P/T,Q/T,R/F 則公式為假值 F. 就是說解釋 I 弄假了此公式。 命題邏輯 命題邏輯與謂詞邏輯 ? 命題邏輯雖能夠把客觀世界的各種實(shí)事表示為邏輯命題，但具有很大局限性，即不適合表達(dá)比較復(fù)雜的問題；而謂詞邏輯則允許我們表達(dá)那些無法用命題邏輯表達(dá)的事情 . 謂詞邏輯法 ? 謂詞邏輯法采用 謂詞合式公式 和 一階謂詞演算 把要解決的問題變?yōu)橐粋€(gè)有待證明的問題 ,然后采用 消除定理 和 消除反演來證明一個(gè)新語(yǔ)句是從已知的正確語(yǔ)句導(dǎo)出的 ,從而證明新語(yǔ)句也是正確的 . 謂詞 ? 1. 3是質(zhì)數(shù) ? 2. 王二生于武漢市 ? 3. 7=2?3 x是質(zhì)數(shù) x生于武漢市 x=y ? z F(x) G(x,y) H(x,y,z) 稱“ 3” 、“王二”、“武漢市”、“ 7” 、“ 2” 、“ 3”為個(gè)體 。 “ 是質(zhì)數(shù)”、“生于”、“ … =... ?...” 都是謂詞。 謂詞 ? 謂詞： 用來刻畫個(gè)體詞的性質(zhì)或個(gè)體詞之間關(guān)系的詞 ? 例如 :張三是研究生，李四是研究生 . ? 這兩個(gè)命題可以用不同的符號(hào) P、 Q表示，但是 P和 Q的 謂語(yǔ)有共同的屬性 ：是研究生。因此引入一個(gè)符號(hào)表示 “是研究生 ”，再引入一個(gè)方法表示個(gè)體的名稱，這樣就能把 “某某是研究生 ”這個(gè) 命題的本質(zhì)屬性 刻畫出來。 ? 對(duì)于上面的命題，可以用謂詞公式分別表示為 Graduate（張三）、 Graduate（李四）。 其中 Graduate是謂詞名，張三和李四都是個(gè)體， “Graduate”刻畫了 “張三 ” 和 “李四 ” 是研究生這一特征。 謂詞 ? 一般來說 ， “x是 A”類型的命題可以用 A（ x） 表達(dá) 。 對(duì)于 “x大于 y”這種兩個(gè)個(gè)體之間關(guān)系的命題 ， 可表達(dá)為 B（ x， y） ， 這里 B表示 “… 大于 … ”謂詞 。 我們把 A（ x） 稱為一元謂詞 B（ x， y） 稱為二元謂詞 ， M（ a， b， c） 稱為三元謂詞 ， 依次類推 ， 通常把二元以上謂詞稱作多元謂詞 。 語(yǔ)法與語(yǔ)義 謂詞邏輯的基本符號(hào)：謂 詞符號(hào)、變量符號(hào)、常量符號(hào)、函數(shù)符號(hào)、括號(hào)和逗號(hào) 。 謂詞符號(hào)：規(guī)定定義域內(nèi)的一個(gè)相應(yīng)關(guān)系。 變量符號(hào)：不明確指定是哪一個(gè)實(shí)體。 常量符號(hào)：表示論域內(nèi)相應(yīng)的一個(gè)實(shí)體。 函數(shù)符號(hào) ：規(guī)定論域內(nèi)相應(yīng)的一個(gè)函數(shù)。 原子公式 (atomic formulas)是由謂詞符號(hào)和若干項(xiàng)組成的謂詞演算。 語(yǔ)法與語(yǔ)義 ? 常量符號(hào)是最簡(jiǎn)單的項(xiàng)，用來表示論域內(nèi)的物體或?qū)嶓w。例如，要表示 “機(jī)器人(ROBOT)在１號(hào)房間 (r1)內(nèi) ”，可以應(yīng)用原子公式 : INROOM(ROBOT, r1) 謂詞符號(hào) 常量符號(hào) 語(yǔ)法與語(yǔ)義 ? 函數(shù)符號(hào)表示論域內(nèi)的函數(shù)，如 “李的母親和他的父親結(jié)婚 ”這句話的原子公式表示如下： ? MARRIED( father(LI), mother(LI)) 函數(shù)符號(hào) 謂詞符號(hào) 語(yǔ)法與語(yǔ)義 ? 變量符號(hào) : 擴(kuò)大命題演算的能力，需要使公式中的命題帶有變量。 ? 句子 “所有的機(jī)器人都是灰色的 ”可表示為 ( ) [ RO B O T ( ) CO L O R( , G RA Y ) ]x x x??我們注意到：這里的 x是被量化的變量 若某個(gè)變量是經(jīng)過量化的，就把這個(gè)變量叫做約束變量 ，否則叫做 自由變量 。 連詞和量詞 連詞和量詞 ? 連詞 ? 合取 （ conjunction)—用符號(hào) ∧ 將幾個(gè)公式連接起來而構(gòu)成的公式，其中的合取項(xiàng)是合取式的每個(gè)組成部分。 ? 例：我喜愛音樂和繪畫。 ? LIKE(I， MUSIC) ∧ LIKE(I ,PAINTING) ? 李住在一座黃色的房子里 ” ? LIVE（ LI， HOUSE1） ∧COLOR （ HOUSE1， YELLOW） ? 析取 (disjunction) —用連詞 ∨ 把幾個(gè)公式連接起 來而構(gòu)成的公式。析取項(xiàng)是析取式的每個(gè)組成部分 . ? 例：李力打籃球或踢足球 . PLAYS(LILI， BASKETBALL)∨ PLAYS(LILI,FOOTBALL) ? 蘊(yùn)涵（ Implication—用連詞 ?表示 “如果 —那么 ”的 語(yǔ)句 . ? 例：如果劉華跑得最快，那么他取得冠軍 RUNS(LIUHUA FASTEST) ?(LIUHUA，CHAMPION) ? 例如， “如果該書是何平的，那么它是藍(lán)色的 ” ? OWN（ HEPING， BOOK1)? COLOR（ BOOK1，BLUE） ? 非（ Not) — 用符號(hào) ～ 表示否定的公式（有時(shí)也用 ┑ 表示） ? 例：機(jī)器人不在 例：機(jī)器人不在 2號(hào)房間內(nèi)。 ? ～ INROOM(ROBOT， r2) 經(jīng)連詞連接后公式的真值 ? 合取：各合取項(xiàng)均為真，合取才為真，否則為假。 ? 析?。何鋈№?xiàng)至少一個(gè)為真，析取為真。 ? 蘊(yùn)含：若后項(xiàng)為真，無論前項(xiàng)為真為假；或者前項(xiàng)為假，無論后項(xiàng)為真為假，蘊(yùn)含都為真。 ? 非：原式真值相反。 量詞 ? 全稱量詞 （ Universal Quantifiers )?? ? 若一個(gè)原子公式 P(x)，對(duì)于所有可能變量對(duì)于 x都具有 T值 ,則用 (?x)P(x)表示。 ? 例：所有學(xué)生都穿彩色制服 (?x)[Student(X)? Uniform (x, Color)] ? 所有的機(jī)器人都是灰色的 (?x)[Robot(X) ? COLOR(x, GRAY)] 量詞 ? 存在量詞（ Existential Quantifiers ) ? 若一個(gè)原子公式 P(x), 至少有一個(gè)變?cè)?X可使 P(X)為 T值 , 則用 (?x)P(x)表示。 ? 例： 1號(hào)房間內(nèi)有個(gè)物體 (?x)INROOM(x,r1) 量詞的轄域 ? 定義 :量詞的轄域 是鄰接量詞之后的最小子公式，故除非轄域是個(gè)原子公式，否則應(yīng)在該子公式的兩端有括號(hào)。 ? 例： (?x)P(x)→Q( x) ? ?x的轄域是 P(x) ? (?x ) [P(x, y)→Q( x， y)] ? P(y, z) ? ?x的轄域是 P(x， y)→Q( x， y) 量詞的轄域 ? 定義：在量詞 ?x， ?x轄域內(nèi)變?cè)?x的一切出現(xiàn)叫約束出現(xiàn)，稱這樣的 x為 約束變?cè)? ? 變?cè)姆羌s束出現(xiàn)稱為 自由出現(xiàn) ,稱這樣的變?cè)獮樽杂勺冊(cè)?。 ? 例： 指出下列謂詞公式中的自由變?cè)图s束變?cè)?，并指明量詞的轄域 ? (? x )[P(x) ? R(x)]→( ? x ) P(x) ? Q(x) ? 解：表達(dá)式中的 ? x[P(x)?R(x)]中 x的轄域是 P(x) ? R(x),其中的 x是約束出現(xiàn) ? (? x ) P(x)中 x的轄域是 P(x),其中的 x是約束出現(xiàn) ? Q(x)中的 x是自由變?cè)? 量詞的轄域 ? 例：指出下列謂詞公式中的自由變?cè)图s束變?cè)?, 并指明量詞的轄域。 ? (?x )[P(x， y)→( ?y)R(x， y) ] ? 解：其中的 P(x， y)中的 y是自由變?cè)?x是約束變?cè)? R(x， y)中的 x， y是約束變?cè)? ? 注：在一個(gè)公式中，一個(gè)變?cè)瓤梢约s束出現(xiàn)，又可以自由出現(xiàn)。為避免混淆可用改名規(guī)則對(duì)變?cè)拿? 注意事項(xiàng) ? (1) 分析命題中表示 性質(zhì) 和 關(guān)系 的謂詞，分別符號(hào)化為一元和 n（ n ? 2）元謂詞。 ? (2) 根據(jù)命題的實(shí)際意義選用 全稱量詞 或 存在量詞。 ? (3) 在不同的個(gè)體域中，命題符號(hào)化的形式可能不一樣。如果事先沒有給出個(gè)體域，都應(yīng)以 全總個(gè)體域 為個(gè)體域。 ? (4)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能隨意顛倒它們的順序，顛倒后會(huì)改變?cè)}的含義。 謂詞公式 ? 原子謂詞公式 ? 用 P（ x1， x2， …x n）表示一個(gè) n元謂詞公式 其中P為 n元謂詞 ， x1,x2,…x n為客體變量或變?cè)?。通常?P（ x1,x2,…,x n）叫做謂詞演算的原子公式 ? 分子謂詞公式