【文章內容簡介】 ? 中一個 m元函數符號 , t1, t2, …, tm是 ? 中項 , 則 fm(t1, t2, …, tm)是 ? 中項 。 3. 每個項都是有限次應用 (1)和 (2)得到的 . ―項 ‖相當于 ‖復合個體 ‖. 2022/8/27 離 散 數 學 38 公式 ? 生成的一階語言的 ‖公式 ‖歸納定義如下 : (1) 如果 Fn是 ? 中的一個 n元謂詞符號 , t1, t2, …, tn 是 ? 中項 , 則 Fn(t1, t2, …, tn)是 ? 中公式 , —— 稱為 原子公式 (2) 若 A是公式 , 則 (172。 A)是公式 。 (3) 若 A, B是公式 , 則 (A∨ B), (A∧ B), (A→ B), (A? B)是 ? 中公式 。 (4) 若 A是公式 , x是個體變元符號 , 則 (?x)A, (?x)A也是公式 。 (5) 每個公式都是有限次使用 (1)(4)得到的 . 2022/8/27 離 散 數 學 39 一些注記 注 1: 與命題演算的形式語言相比 , 一階語言中沒有 符號 , 代之的是原子公式 . 注 2: 所有一階語言中都含有相同的邏輯符號 , 但所 含的非邏輯符號不一定相同 . 注 3: 在定義中沒有要求個體變元 x一定要在 A中出現(xiàn) : (?x1)F2(x1, x2)和 (?x3)F2(x1, x2)都是公式 . 注 4: 總假設 : ? 中至少有一個謂詞符號 . 否則 ? 生成的一階語言中沒有公式 . 2022/8/27 離 散 數 學 40 括號省略規(guī)則 (1) 省略公式最外層的括號 。 (2) 聯(lián)結詞符號 ‖172?！膬?yōu)先級高于其它的四個聯(lián)結 詞 , 可以去掉 (172。 A)中的外層括號 。 (3) A1→ A2→ …→ An1→ An表示 (A1→ (A2→ …→ (An1→ An)…))。 對 ∨ , ∧ , ? 也類似規(guī)定 . (4) ?x, ?x的優(yōu)先級高于所有聯(lián)結詞 . 將 (?x)A, (?x)A分別記為 ?xA, ?xA. (5) (?x1)…(?xn)A簡記為 ?x1…xnA。 (?x1)…(?xn)A簡記為 ?x1…xnA. 2022/8/27 離 散 數 學 41 項和公式 ? 項的作用是描述 ‖復合 ‖個體 公式的作用是描述命題 . ? ―項 ‖相當于 ‖詞組 ‖, 它們不表達完整的判斷 。 ―公式 ‖代表完整的句子 , 表達判斷 . f(x1, x2, …, xn)表示 f作用到個體 x1, …, xn得到的個體 Fn(x1, x2, …, xn)表示 x1, x2, …, xn是否具有關系 Fn(或性質 Fn). 2022/8/27 離 散 數 學 42 例 3 用一階語言描述群的定義 解 : 令 ? = {f2, E2, c}, 其中 : f2代表群的乘法運算 , 是一個二元函數符號 。 E2描述元素的相等關系 , 是一個二元謂詞符號 。 c代表群的單位元 , 是一個常元符號 . 則群公理可表示為由 ? 中的如下三個公式 : (1)?x1x2x3 E( f( f(x1, x2), x3), f(x1, f(x2, x3) ) ) (2)?x0(E( f(x0, c), x0) ∧ E( f(c, x0), x0) ) (3)?x1?x2(E( f(x1, x2), c) ∧ E( f(x2, x1), c) ) 2022/8/27 離 散 數 學 43 用一階語言描述等價關系的定義 解 : 令 ? = {E2}, 其中 : E2描述元素的等價關系 , 是一個二元謂詞符號 。 則等價關系的定義可表示為由 ? 中的如下三個公式 : (1) (?x) E(x, x)。 (2) (?xy) (E(x, y) → E(y, x))。 (3) (?xyz) (E(x, y) ∧ E(y, x)) → E(x, z)). 2022/8/27 離 散 數 學 44 轄域 定義 3: 稱公式 (?x)A中的 A為量詞 (?x)的轄域 。 稱公式 (?x)A中的 A為量詞 (?x)的轄域 . 例 : 在 ?x1?x2(?x3F(x1, x2)→ F(x2, x3))中 , (?x1)的轄域為 ?x2(?x3F(x1, x2)→ F(x2, x3)), (?x2)的轄域為 (?x3F(x1, x2)→ F(x2, x3)), (?x3)的轄域為 F(x1, x2). 2022/8/27 離 散 數 學 45 約束出現(xiàn)與自由出現(xiàn) 定義 4: 變元符號 x在公式 A中的某處 出現(xiàn) 稱為是 約束出現(xiàn) , 如果 ? 此處出現(xiàn)是在 (?x)或 (?x)的轄域內 , 或者 ? 是 (?x)中的 x, 或者 ? 是 (?x)中的 x. 若 x在 A中的某處出現(xiàn)不是約束出現(xiàn) , 則稱 x的 此處 出現(xiàn) 為 自由出現(xiàn) . 2022/8/27 離 散 數 學 46 例 4 下列公式中 , 指出變元的各處出現(xiàn)是自由出現(xiàn)還是 約束出現(xiàn) . (1)?x1?x2(F(x1, x2)→ F(x1, x3)) (2)?x1F(x1)→ F(x1) (3)?x1F(x1, x2)→ ?x1F(x2) 2022/8/27 離 散 數 學 47 例 4的解 解 : (1) ?x1 ?x2 (F(x1, x2) → F(x1, x3)) 約束 約束 約束 約束 約束 自由 (2) ?x1 F(x1) → F(x1) 約束 自由 (3) ?x1 (F(x1, x2)) → ?x1 F(x2) 約束 約束 自由 約束 自由 注 : 同一個變元在同一個公式中可能既有自由出現(xiàn) ,又有約束出現(xiàn) . 2022/8/27 離 散 數 學 48 約束變元與自由變元 定義 5: 設個體變元符號 x在公式 A中出現(xiàn) . ? 如果 x在 A中的所有出現(xiàn)都是約束出現(xiàn) , 稱 x為 A的約束變元 。 ? 如果 x不是 A的約束變元 , 則稱 x為 A的自由變元 . 易知 : x是 A的自由變元 ? x在 A中有某處出現(xiàn)是自由出現(xiàn) . 2022/8/27 離 散 數 學 49 約束變元與自由變元的例 例 4中 : (1)中的 x1, x2為約束變元 , x3是自由變元 。 (2)中的 x1是自由變元 。 (3)中的 x1是約束變元 , x2是自由變元 . 約定 : 以 A(x1, …, xn)表示公式 A的自由變元都在 x1, …, xn中 . 2022/8/27 離 散 數 學 50 約束變元與自由變元的差別 約束變元與自由變元的差別很大 . 令 ? = {E2, c}, 其中 : E代表二元謂詞 ‖…=…‖, c代表一個常量 . 考慮 的公式 : ?x1E(x1, c)與 ?x2E(x1, c). ?x1E(x1, c)為真 ? 個體域中只能有一個元素 c. 故 ?x1E(x1, c)的真假與 x1取值無關 . 但 ?x2E(x1, c)的真假與 x1取值有關 . 約束變元的出現(xiàn) ——反映論域的某種性質 并非決定其取值 2022/8/27 離 散 數 學 51 t對 x在 A中可代入 考察將公式 ?y(yx)中的