2.2.1 一阶谓词的基本概念

1.命题与真值

命题：具有真假意义的陈述句称为命题。

命题的真值：T：表示命题为真；F：表示命题为假。

一个命题不能同时既为真又为假，一个命题可在一定条件下为真，而在另一条件下为假。

2.论域和谓词

论域：由所讨论对象的全体构成的集合，亦称为个体域。个体为论域中的元素。

谓词：在谓词逻辑中命题是用形如P（x₁，x₂，…，x_n）的谓词来表示的。谓词名是命题的谓语，表示个体的性质、状态或个体之间的关系。个体是命题的主语，表示独立存在的事物或概念。

例如：GREATER（x，6），表示x大于6；TEACHER（father（Wang Hong）），表示王宏的父亲是一位教师。

谓词与函数的区别：谓词是D到{T，F}的映射，函数是D到D的映射；谓词的真值是T和F，函数的值（无真值）是D中的元素；谓词可独立存在，函数只能作为谓词的个体。

3.连接词

﹁：“非”或者“否定”。表示对其后面的命题的否定。

∨：“析取”。表示所连接的两个命题之间具有“或”的关系。

∧：“合取”。表示所连接的两个命题之间具有“与”的关系。

→：“条件”或“蕴含”。表示“若……则……”的语义。读作“如果P，则Q”。其中，P称为条件的前件，Q称为条件的后件。

↔：称为“等价”或“双条件”。它表示“当且仅当”的语义。即读作“P当且仅当Q”。例如，对命题P和Q，“P↔Q”表示“P当且仅当Q”。

4.量词

∀：全称量词，意思是“所有的”、“任一个”。命题为真，当且仅当对个体域中的所有个体x，都有为真；为假，当且仅当至少存在一个x_i∈D，使得P（x_i）为假。

∃：存在量词，意思是“至少有一个”、“存在有”。命题为真，当且仅当至少存在一个x_i∈D，使得为真；命题为假，当且仅当对个体域中的所有个体x，都有为假。

5.项与合式公式

项是指把个体常量、个体变量和函数统一起来。项满足如下规则：

（1）单独一个个体词是项；

（2）若t₁，t₂，…，t_n是项，f是n元函数，则f（t₁，t₂，…，t_n）是项；

（3）由（1）、（2）生成的表达式是项。

原子谓词公式：

若t₁，t₂，…，t_n是项，P是谓词，则称P（t₁，t₂，…，t_n）为原子谓词公式。

满足如下规则的谓词演算可得到合式公式：

（1）单个原子谓词公式是合式公式；

（2）若A是合式公式，则﹁A也是合式公式；

（3）若A，B是合式公式，则A∨B，A∧B，A→B，A↔B也都是合式公式；

（4）若A是合式公式，x是项，则（x）A（x）和（x）A（x）都是合式公式。

例如：﹁P（x，y）∨Q（y），（x）（A（x）→B（x）），都是合式公式。

连词的优先级：﹁，∧，∨，→，↔。

6.自由变元与约束变元

辖域内与量词中同名的变元称为约束变元。不受约束的变元称为自由变元。辖域指位于量词后面的单个谓词或者用括号括起来的合式公式。

例如：（∀x）（P（x，y）→Q（x，y））∨R（x，y），其中，（P（x，y）→Q（x，y））是（∀x）的辖域。辖域内的变元x是受（∀x）约束的变元，R（x，y）中的 x和所有的 y都是自由变元。

谓词公式中的变元可以换名。但需注意：

（1）对约束变元，必须把同名的约束变元都统一换成另外一个相同的名字，且不能与辖域内的自由变元同名。

例如：对（∀x）P（x，y），可把约束变元x换成z，得到公式（∀z）P（z，y）。

（2）对辖域内的自由变元，不能改成与约束变元相同的名字。

例如：对（∀x）P（x，y），可把y换成z，得到（∀x）P（x，z），但不能换成x。