2.2   谓词逻辑公式与解释

2.2.1   谓词逻辑的合式公式  

  定义2.1   设P（x1，x2，…，xn）是n元谓词公式，其中，x1x2，…，xn是个体变项，则称P（x1，x2，…，xn）为谓词演算的原子公式。

   定义2.2   谓词演算的合式公式定义如下：

（1）原子公式是合式公式；

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

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

（4）若A是合式公式，则x A、x A是合式公式；

（5）只有有限次地应用（1）－（4）构成的符号串才是合式公式。 

   例2.5  在谓词逻辑中将下列命题符号化。

（1）不存在最大的数。

（2）计算机系的学生都要学离散数学。

解  取个体域为全总个体域。

（1）令F（x）：x是数，L（x，y）：x大于y；则命题（1）符号化为

﹁x（F（x）∧ y（F（y）→ L（x，y）））

（2）令C（x）：x是计算机系的学生，G（x）：x要学离散数学;则命题（2）可符号化为：             x（C（x）→ G（x）） 

  例2.6  将下列命题符号化。

（1）尽管有人聪明，但并非所有人都聪明。

（2）这只大红书柜摆满了那些古书。

解  （1）令C（x）：x聪明；M（x）：x是人。则命题（1）可符号化为

x（M（x）∧C（x））∧﹁x（M（x）→C（x））

（2）令F（x，y）：x摆满了y；R（x）：x是大红书柜；Q（x）:x是古书；a：这只；b：那些。则命题（2）可符号化为

R（a）∧Q（b）∧F（a，b） 

  2.2.2   约束变元与自由变元 

  1．约束变元与自由变元的概念

定义 2.3  在公式x F（x）和x F（x）中，称x为指导变元，F（x ）为相应量词的辖域或作用域。在x和x的辖域中，x的所有出现都称为约束出现，F（x）中不是约束出现的其他变元均称为自由出现。

    例2.7  指出下列各式量词的辖域及变元的约束情况：

（1）x（F（x，y）→ G（x，z））

（2）x（P（x）→y R（x，y））

（3）x（F（x）→ G（y））→ y（H（x）∧M（x，y，z））

 解 （1）对于x的辖域是A=（F（x，y）→ G（x，z）），在A中，x是约束出现的，而且约束出现两次，y，z均为自由出现，而且各自由出现一次。

（2）对于x的辖域是（P（x）→y R（x，y）），y的辖域是R（x，y），x，y均是约束出现的。

（3）对于x的辖域是（F（x）→ G（y）），其中x是约束出现的，而y是自由出现的。对y的辖域是（H（x）∧M（x，y，z）），其中y是约束出现的，而x，z是自由出现的。在整个公式中，x约束出现一次，自由出现两次，y约束出现一次，自由出现一次，z仅自由出现一次。

    2．约束变元的换名与自由变元的代入 

例2.8  对公式x（P（x）→ R（x，y））∧Q（x，y）进行换名。

解  对约束变元x换名为t后为

t（P（t）→ R（t，y））∧Q（x，y）

同理，对公式中的自由变元也可以更改，这种更改称作代入。

自由变元的代入规则是：

（1）对于谓词公式中的自由变元，可以代入，此时需要对公式中出现该自由变元的每一处进行代入。

（2）用以代入的变元与原公式中所有变元的名称都不能相同。

  例2.9  对公式x（F（x）→ G（x，y））∧y H（y）代入。

解  对y实施代入，经过代入后原公式为

x（F（x）→ G（x，t））∧ y H（y）

另外，量词作用域中的约束变元，当论域的元素是有限时，个体变元的所有可能的取代是可以枚举的。

设论域元素为a1，a2，…，an，

则         x A（x） A（a1）∧A（a2）∧…∧A（an）

           x A（x） A（a1）∨A（a2）∨…∨A（an）。 

2.2.3   谓词逻辑公式的解释

   定义2.4   谓词逻辑公式的一个解释I，是由非空区域D和对G中常项符号、函数符号、谓词符号以下列规则进行的一组指定组成：

（1）对每一个常项符号指定D中一个元素。

（2）对每一个n元函数符号，指定一个函数。

（3）对每一个n元谓词符号，指定一个谓词。

显然，对任意公式G，如果给定G的一个解释I，则G在I的解释下有一个真值，记作TI（G）。

  例2.10  指出下面公式在解释I下的真值。

（1）G=x（P（f（x））∧Q（x，f（a）））；

（2）H=x（P（x）∧Q（x，a））。

给出如下的解释I：

D={2，3}；

a：2；

f（2）：3、f（3）：2；

P（2）：0、P（3）：1； 

Q（2，2）：1、Q（2，3）：1、Q（3，2）：0、Q（3，3）：1；

解  （1）TI（G）= TI（（P（f（2））∧Q（2，f（2）））∨（P（f（3））∧Q（3，f（2））））

               = TI（（P（3）∧Q（2，3））∨（P（2）∧Q（3，3））

               = （1∧1）∨（0∧1）

               = 1

（2）TI（H）= TI（P（2）∧Q（2，2）∧P（3）∧Q（3，2））

               =0∧1∧1∧0=0

     定义2.5   若存在解释I，使得G在解释I下取值为真，则称公式G为可满足的，简称I满足G。

定义2.6   若不存在解释I，使得I满足G，则称公式G为永假式（或矛盾式）。若G的所有解释I都满足G，则称公式G为永真式（或重言式）。