【文章內(nèi)容簡介】 1. 個體常項(xiàng)和變項(xiàng)是項(xiàng) 2. 若 φ(x1,x2,… ,xn)是任意的 n元函數(shù)，x1,x2,… ,xn是項(xiàng)，則 φ(x1,x2,… ,xn)是項(xiàng) 3. 只有有限次地使用 1， 2生成的符號才是項(xiàng) ?a,b,x,y, f(x,y), f(x,g(a,b,z)) 2020/11/17 50 合式公式（謂詞公式） ? 原子公式 ?定義 13：設(shè) R(x1,x2,..,xn)是任意的 n元謂詞，t1,t2,… ,tn為項(xiàng)，則 R(t1,t2,… ,tn)稱為原子公式 ? 合式公式，定義 14： 1. 原子公式是合式公式 2. 如果 A是合式公式，則（ 172。A）為合式公式 3. 如果 A,B是合式公式，則（ A∧ B） ,（ A∨ B） , （ A→ B） , （ A B）也是合式公式 4. 如果 A是合式公式，則 xA， xA也是合式公式 5. 只有有限次地應(yīng)用 1－ 4組成的符號串才是合式公式（謂詞公式） 2020/11/17 51 指導(dǎo)變項(xiàng)、轄域 ? 定義 15：在合式公式 xA和 xA中，稱 x為指導(dǎo)變項(xiàng) ，稱 A為相應(yīng)量詞的 轄域 。在轄域中，x的所有出現(xiàn)稱為 約束出現(xiàn) （即 x受相應(yīng)量詞指導(dǎo)變項(xiàng)的約束）， A中不是約束出現(xiàn)的其它變項(xiàng)稱為 自由出現(xiàn) 。 ? 通常用 A(x)表示 x是自由出現(xiàn)的任意公式 ? 例子 ? x(F(x)→ yH(x,y)) ? xF(x)∧ G(x,y) ? x y(R(x,y)∨ L(y,z))∧ xH(x,y) 2020/11/17 52 閉式 ? 定義 16：設(shè) A為任一公式，若 A中無自由出現(xiàn)的個體變項(xiàng)，則稱 A是 封閉的合式公式 ，簡稱 閉式 。 ? 例子： 2020/11/17 53 換名規(guī)則和代替規(guī)則 ? 為了避免出現(xiàn)某個變項(xiàng)既是自由出現(xiàn)的又是約束出現(xiàn)的，使用以下 2種辦法 ?換名規(guī)則 ：將量詞轄域種出現(xiàn)的某個約束出現(xiàn)的個體變項(xiàng)及對應(yīng)的指導(dǎo)變項(xiàng)，改成另外一個轄域中未曾出現(xiàn)過的個體變項(xiàng)符號，公式其它部分不變 xF(x)∧ G(x,y) zF(z)∧ G(x,y) ?代替規(guī)則 ：對某個自由出現(xiàn)的個體變項(xiàng)用與原公式中的所有個體變項(xiàng)符號不同的變項(xiàng)符號來代替，且處處代替 xF(x)∧ G(x,y) xF(x)∧ G(z,y) 2020/11/17 54 公式的解釋 ? 公式的解釋 ：一階謂詞公式中含有：個體常項(xiàng)，個體變項(xiàng)（自由出現(xiàn)或約束出現(xiàn)的），函數(shù)變項(xiàng)，謂詞變項(xiàng)等。對各種變項(xiàng)指定特殊的常項(xiàng)來代替，就構(gòu)成公式的一個解釋。 ? 解釋，定義 17 ?一個解釋 I由下面的 4個部分構(gòu)成 1. 非空個體域 D 2. D上的一部分特定的元素 3. D上的一些特定的函數(shù) 4. D上的一些特定的謂詞 2020/11/17 55 解釋的例子 ? 解釋 ? DI={2,3} ? DI上的特定元素 ? 函數(shù)： f(2)=3,f(3)=2 ? 謂詞： F(2)=0。f(3)=1 G(x,y)為 G(i,j)=1, i,j=2,3。 L(x,y)為 L(2,2)=L(3,3)=1 L(3,2)=L(2,3)=0。 ? 2020/11/17 56 公式的解釋 2020/11/17 57 公式的性質(zhì) ? 定義 18 ?設(shè) A為一個公式 (謂詞公式 ) ?若 A在它的任何解釋下取值均為真，則稱 A為邏輯有效式 或 永真式 ?若 A在它的任何解釋下取值均為假，則稱 A為矛盾式 或 永假式 ?若 A至少存在一組解釋是成真賦值，則稱 A為可滿足式 2020/11/17 58 代換實(shí)例 ? 定義 19：設(shè) A0是含命題變項(xiàng) p1,p2,… ,pn的命題公式， A1,A2,… ,An是 n個謂詞公式，用Ai(i=1… n)處處代替 pi，所得到的公式稱為 A0的 代換實(shí)例 ? 例子 ?命題公式： p∨ q A1 xF(x) A2 G(x,y) ?代換實(shí)例： ( xF(x))∨ G(x,y) 2020/11/17 59 代換實(shí)例的一個結(jié)論 ? 命題公式的重言式的代換實(shí)例在謂詞邏輯中，仍然是重言式； ? 命題公式的矛盾式的代換實(shí)例在謂詞邏輯中，仍然是矛盾式； ? 例子： 2020/11/17 60 一階邏輯等值式 ? 定義 20：設(shè) A,B是一階邏輯中的任意 2公式，若A B是邏輯有效式，則稱 A與 B是 等值 的，記做 A B，稱 A B為 等值式 ? 命題邏輯中的 24條等值式的代換實(shí)例也是邏輯等值式 2020/11/17 61 謂詞邏輯中的邏輯等值式 1 ? 定理 1：量詞否定等值式 2020/11/17 62 謂詞邏輯中的邏輯等值式 2 ? 定理 2：量詞的 轄域收縮 和 擴(kuò)張 等值式 2020/11/17 63 謂詞邏輯中的邏輯等值式 3 ? 定理 3： 量詞分配 等值式 2020/11/17 64 謂詞邏輯中的邏輯等值式 4 ? 定理 4 ?量詞的性質(zhì)相同，可以交換位置 ?量詞的性質(zhì)不同，不可交換位置 2020/11/17 65 前束范式 ? 定義 21：設(shè) A為一謂詞公式，如果 A具有如下形式： Q1x1Q2x2… QkxkB 則稱 A是 前束范式 。其中每一個 Qi為 或 B為不含量詞的謂詞公式（ 母式 ） 例如： x y(F(x,y)→ G(x,y)) 前束范式 x(F(x)→ y(G(y)→ H(x))) 非前束范式 2020/11/17 66 前束范式例題 ? 求下列公式的前束范式 2020/11/17 67 謂詞公式的合取范式和子句集 ? 對任一公式 ?量詞轄域擴(kuò)張和收縮定理，得到 前束范式 ?對于母式，等值演算得到 合取范式 ?合取項(xiàng)的集合，構(gòu)成了該公式的 子句集 S ? 前束范式 ? 母式 ?原子：謂詞 ?文字：謂詞或謂詞的否定 ?子句：文字的析取 ?合取范式：子句的合取 ?子句集：合取范式的集合形式，元素之間的關(guān)系為合取關(guān)系 2020/11/17 68 ? 一階謂詞邏輯 ? 語法和語義： 謂詞邏輯的基本組成、謂詞符號、常量符號、變量符號、函數(shù)符號、項(xiàng)的遞歸定義、原子、謂詞演算語言的語義 ? 連詞和量詞： 合適公式、連詞、合取、析取、蘊(yùn)含、否定、等價、命題演算、全稱量詞、存在量詞、約束變量、自由變量、句子、一階謂詞演算 表示方法 — 邏輯表示法 2020/11/17 69 ? 謂詞邏輯的基本組成 ：謂詞符號、變量符號、函數(shù)符號和常量符號，并用圓括弧、方括弧、花括弧和逗號隔開，以表示論域內(nèi)的關(guān)系。 ? 謂詞符號 ：表示個體所具有的性質(zhì)，或者若干個體之間的關(guān)系的符號。習(xí)慣用大寫字母 P， Q， R或 GREATER， LOVE表示。 ? 常量符號 ：用來表示論域內(nèi)的物體或?qū)嶓w，它可以是實(shí)際的物體和人，也可以是概念或具有名字的任何事情。一般用英文字母表中前幾個帶下標(biāo)或不帶下標(biāo)的小寫字母表示。如 a， b， ... ， a1，b2， c3， ... 。 2020/11/17 70 ? 變量符號 ：不必明確涉及是哪一個實(shí)體。習(xí)慣上用帶下標(biāo)或不帶下標(biāo)的小寫字母表示。如 x，y， ... ， x1， y2， 。 ? 函數(shù)符號 ：表示論域內(nèi)的函數(shù)。習(xí)慣用小寫字母 f，g， h表示。 2020/11/17 71 ?例如，要表示“機(jī)器人（ ROBOT）在 1號房間（ ROOM1）內(nèi)”，簡單的原子公式如下： INROOM（ ROBOT， r1） 式中， INROOM為謂詞符號， ROBOT和 r1為常量符號。 ?又如，要表示“李（ LI）的母親與他的父親結(jié)婚”， 原子公式如下： MARRIED[father（ LI）， mother（ LI） ] 式中，函數(shù)符號 mother、 father分別用來表示某人與他（她的）母親、父親之間的 映射 。 2020/11/17 72 ? 謂詞演算語言的語義 ：