第2章 一阶逻辑（2）.pptVIP

3.1.4 一阶逻辑公式及解释 上一节中我们在一阶逻辑中符号化得到的命题和命题函数就是一阶逻辑公式(谓词公式)。至此，在一阶逻辑中，我们已涉及到以下这些符号： (1)个体变元符号：用小写的英文字母x，y，z（或加下标）…等表示。 (2)个体常元符号：用小写的英文字母a，b，c（或加下标）…等表示。 (3)运算符号：用小写的英文字母f，g，h（或加下标）…等表示。 (4)谓词符号：用大写的英文字母F，G，H（或加下标）…等表示。 (5)量词符号： ，。 (6)联结词符号： ，∧，∨，→，。 (7)逗号和圆括号。 一个符号化的命题是一串由这些符号所组成的表达式，但并不是任意一个由此类符号组成的表达式就对应于一个命题。所以要给出严格的定义。 二 量词的辖域 定义3.5 在公式?xA和?xA中, 称x为指导变元, A为相应量词的辖域. 在?x和?x的辖域中, x的所有出现称为约束出现，A中不是约束出现的其他变项称为自由出现 例1 公式 ?x(F(x,y)??yG(x,y,z)) ?x的辖域:(F(x,y)??yG(x,y,z))， 指导变元为x ?y的辖域:G(x,y,z)， 指导变元为y x的两次出现均为约束出现 y的第一次出现为自由出现, 第二次出现为约束出现 z为自由出现. 例4 设f，g均为二元运算符，E，L均为二元谓词符，给定解释I如下： 个体域D为自然数集合； f（x，y）=x+y，g（x，y）=x·y，a=0； E（x，y）：x=y，L（x，y）：x＜y。 求下列公式在解释I下的真值。 例5 设解释I为：DI={2，3}，f（2）=3，f（3） =2，F（2，2）=F（2，3）=0， F（3，2）= F（3，3）=1.在I下消去下列公式的量词并求真值。 （1）F（2，f（2））∧F（3，f（3）） (2) xyF（y，x）  x（（F（2，x）∨F（3，x））） （F（2，2）∨F（3，2）） ∧（F（2，3）∨F（3，3）） （0∨1）∧（0∨1） 1∧1  1 定义3.8 一阶逻辑公式的分类： 永真式（逻辑有效式） 在任何解释I下均为真的一阶公式； 永假式（矛盾式） 在任何解释I下均为假的一阶公式； 可满足式 至少有一种解释使其为真的一阶公式。 由定义可知，要判定一个公式A不是永真式，只需找到一个解释I，使A在I下为假； 要判定一个公式A不是永假式，只需找到一个解释I，使A在I下为真； 要判定一个公式A是可满足式，只需找到一个解释I，使A在I下为真，再找到一个解释I，使A在I下为假。 例6 讨论下列公式的类型： （1） xF（x）→xF（x） （2） x G（x）∧xG（x） （3） xyF（x，y）→y xF（x，y） 解 （1）公式 xF（x）→xF（x）在任何解释I下的含义是：如果个体域DI中的每个元素x均有性质F，则DI中的某些元素x必有性质F。前件 xF（x）为真时，后件xF（x）永远为真，所以公式 xF（x）→xF（x）是永真式。 （2）公式 x G（x）∧xG（x）在任何解释I下的含义是：个体域DI中的每个元素x均不具有性质G，且DI中的某些元素x具有性质G。这是两个互相矛盾的命题，不可能同时成立，所以公式 x G（x）∧xG（x）是永假式。 （3）公式 xyF（x，y）→y xF（x，y）既不是永真式，也不是永假式。由于这是闭式，故无需考虑赋值，只要给出一个使其成真的解释和一个使其成假的解释即可。 ?①给定解释I1：DI1为自然数集，F（x，y）：x＜y。此时公式的前件 xyF（x，y）表示“对于每个自然数x，均有自然数y比x大”是真命题，而后件y xF（x，y）表示“存在着自然数y比每个自然