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

第三讲：谓词逻辑

3.1 谓词与量词

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

3.2 谓词公式及分类

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

3.3 自然语句的形式化

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

3.4 谓词逻辑的等值演算

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