北交大《离散数学》——第二部分

第二部分"/>

北交大《离散数学》——第二部分

第三讲：谓词逻辑

3.1 谓词与量词

1. 【个体词】：表示独立存在的具体或抽象的客体，是一个命题里表示思维对象的词。具体的、确定的个体词称为个体常项；抽象的、不确定的个体词则称为个体变项。个体变项的取值范围称为个体域或论域。宇宙间所有事物组成的个体域称为全总个体域。
2. 【谓词】：表示个体词性质或相互之间关系的词称为谓词。
3. 【一元谓词】：命题中只含一个个体词，这时表示该个体词的性质或属性的词即一元谓词，以 P ( x ) , Q ( x ) P(x),Q(x) P(x),Q(x)表示。
4. 【二元谓词】：若命题中含多个个体词，这时表示个体词间关系的词称为多元谓词，以 P ( x 1 , ⋯   , x n ) P(x_1,\cdots,x_n) P(x1​,⋯,xn​)表示。
5. 谓词表示严格说只是命题形式而非命题，除非确定了谓词的含义与个体词的含义。
6. 【量词】：表示个体数量的词。给谓词加上量词称为谓词的量化。
7. 【全称量词】 ∀ \forall ∀
8. 【存在量词】 ∃ \exist ∃

3.2 谓词公式及分类

1. 【谓词公式】：命题常项、命题变项、原子谓词公式（不含联结词）是谓词公式；谓词公式的否定、逻辑联结得到的符号串是谓词公式；若 A A A是谓词公式，且 A A A中无 ∀ x \forall x ∀x和 ∃ x \exist x ∃x存在，则 ( ∀ x ) A ( x ) , ( ∃ x ) A ( x ) (\forall x)A(x),(\exist x)A(x) (∀x)A(x),(∃x)A(x)（即谓词一次量化后）也是谓词公式。
2. 【谓词公式的解释】：解释由四部分组成：非空论域D；D中的一些特定元素；D上的一些特定函数；D上的一些特定谓词。如 D 上 有 ： F ( x )    ⟹    G ( x + y , 2 ) D上有：F(x)\implies G(x+y,2) D上有：F(x)⟹G(x+y,2)。解释规定了相应的个体常项、个体变项、函数符号及谓词符号的具体含义，以及个体变项的取值范围。
3. 【谓词命题的分类】：A为一个谓词公式，若A在任何解释下均为真，则称A为普遍有效的公式或逻辑有效式；若在任何解释下均为假，则称A为不可满足式或矛盾式；若至少存在一个解释使得A为真，则称A为可满足的公式。
4. 【约束】：量词对变项会有约束作用，如 ∀ x G ( x ) \forall xG(x) ∀xG(x)中， ∀ \forall ∀对 x x x产生约束作用。
   
5. 【定理】：（丘吉-图灵定理）对任一谓词公式而言，没有一个可行的方法判明它是否普遍有效。但谓词逻辑的某些子类是可判定的。
6. 【代换实例】：若命题公式 A 0 A_0 A0​含命题变项 p 1 , ⋯   , p n p_1,\cdots,p_n p1​,⋯,pn​，用 n n n个谓词公式 A 1 , ⋯   , A n A_1,\cdots,A_n A1​,⋯,An​分别代换 p 1 , ⋯   , p n p_1,\cdots,p_n p1​,⋯,pn​，所得的公式 A A A称为 A 0 A_0 A0​的代换实例。
7. 【定理】：命题公式中的重言式的代换实例均为逻辑有效式，矛盾式的代换实例均为矛盾式。
8. 【子公式】：谓词公式中的连续字符串称为该谓词公式的子公式。
9. 【概念】：量词的指导变项（作用变项）与作用域（辖域）；约束出现、约束变项；自由变项。

3.3 自然语句的形式化

1. 【自然语句的形式化】：首先将问题分解为原子命题和逻辑联结词；接着分解出各个原子命题的个体词、量词和谓词；最后按合式公式的规则翻译出自然语句。

3.4 谓词逻辑的等值演算

1. 【谓词逻辑的等值】：若A,B是两个谓词公式，且 A    ⟺    B A\iff B A⟺B是逻辑有效式，则称A与B等值，记作 A ≡ B A\equiv B A≡B。
2. 【谓词逻辑中的等值式】：一类是命题逻辑中等值式的代换实例；一类是与量词有关的特有等值式。
3. 【消去量词等值式】：设论域 D = { a 1 , ⋯   , a m } D=\{a_1,\cdots,a_m\} D={a1​,⋯,am​}是有限集合，则有 ( ∀ x ) A ( x ) ≡ A ( a 1 ) ∧ A ( a 2 ) ∧ ⋯ ∧ A ( a m ) ; ( ∃ x ) A ( x ) ≡ A ( a 1 ) ∨ A ( a 2 ) ∨ ⋯ ∨ A ( a m ) (\forall x)A(x)\equiv A(a_1)\land A(a_2)\land \cdots\land A(a_m);(\exist x)A(x)\equiv A(a_1)\lor A(a_2)\lor \cdots\lor A(a_m) (∀x)A(x)≡A(a1​)∧A(a2​)∧⋯∧A(am​);(∃x)A(x)≡A(a1​)∨A(a2​)∨⋯∨A(am​)。
4. 【量词否定等值式】：设 A ( x ) A(x) A(x)是 x x x自由出现的公式，则