离散件3-谓词逻辑.ppt

《离散件3-谓词逻辑.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章谓词逻辑首先看看著名的“苏格拉底三段论式”：Everymanismortal.Socratesisaman.Socratesismortal.按命题形式化方法，可翻译为P，QR这个形式化结果无法利用命题逻辑推理证明。又如x+y>6不是命题，但是对任何具体的实数x和y，它都有确定的真值。命题逻辑的局限性----难以表达命题之间的内在联系；----难以表达局部和全局的概念；----没有考虑命题与“范围”之间的联系。第一节量词化逻辑一、谓词：描述客观对象的性质或客观对象之间关系的断语。例：梨花是白的，桃花是红的。小张长得比小刘更结实。1。谓词的形式化1）个体域：又叫论域，由客体构

2、成的集合，可表示为={a1，a2，，an}。2）客体：一般用x，y，z等表示客体变元，用a，b，c或具体的客体符号等表示客体常元。3）谓词标识符：表达谓语的符号串，常用大写字母串表示，如A，B等表示。4）谓词：由谓词标识符和客体等构成的符号串。如A(a，x，f(x))例：令W(x）：x是白的；p：梨花，则“梨花是白的”的谓词表示为：W(p）。令H(x，y）：x比y结实，a：小张，b：小刘，则“小张长得比小刘更结实”的谓词表示为：H(a，b）。2。注意事项：1）谓词中客体的位置不能随意交换。一般，A(x，y）不等价于A(y，x）。2）谓词的真值与论域相关。例如用谓词A(x，0)表示

3、x>0，在由正数构成的论域中，其值为真;而在由0或负数构成的论域中，其值为假。3）一般情况下，使用全总个体域构造谓词，而用特性谓词来限制或说明客体。4）谓词中客体变元的个数称为谓词的元数。如H(x，y)是一个二元谓词。A(x,y,z)是一个三元谓词。把命题作为谓词的特殊形式，即0元谓词。例如P，H(a,b)等等。二、量词1。全称量词：表达“任意的”、“一切的”等限定概念。用符号“”表示。常用法:(x)A(x)2。存在量词：表达“存在”、“有”、“某个”等限定概念。用“”表示。常用法:(x)A(x)注意：在表达式(x)A(x)中，如果谓词A(x)是一个一元谓词，那么在确定的论

4、域中(x)A(x)就是一个命题。同理(x)A(x)也一样。例：设论域1={1，2，3，4}，2={2，3，7}，令PRIME（x）：x是素数。那么，(x)PRIME(x)在论域1上取值0，而在2上取值1。(x)PRIME(x)在论域1上取值1，而在2上也取值1。一般情况下，使用全总个体域构造谓词，而用特性谓词来限制或说明客体。例：把“并非每个正整数都是素数”翻译成谓词表达式。解：令N(x）：x是正整数，P(x）：x是素数，则可译为：(x)[N(x）P(x)]也可译为：(x)[N(x）P(x)]对全称量词，特性谓词作条件式的前件加入对于存在量词、特性谓词

5、作合取项加入例：把“苏格拉第三段论式”翻译成谓词表达式：解：令M(x）：x是人，D(x）：x是要死的，s：苏格拉底。则可把“苏格拉底三段论式”翻译为：((x)[M(x)D(x)]M(s))D(s)例：把“每个实数的平方不小于0”译成谓词表达式。解：令R(x）：x是实数，L(x，y）：x

6、x)称为量词的辖域。4。约束变元和自由变元量词辖域中与指导变元同名的变元称为约束变元，其它变元称为自由变元。例：在表达式(x)[A(x)(y)[B(y)C(x,y)]]中，对于全称量词而言，辖域中变量x是受约束的，对于存在量词而言，其辖域中变量y是受约束的，而x是自由的。注意：当对公式中的指导变元和约束变元换用另一个符号表示时，不改变公式的实际意义。也就是说，(x)A(x)与(t)A(t)无本质区别，(y)B(y)与(x)B(x)也是相同的.5。在有限论域上量词公式的等价表示设论域={a1，a2，，an}，则(x)R(x)R(a1)R(a2)R(a

7、n)(x)R(x)R(a1)R(a2)R(an)作业：习题2.11，2(3)，3(2),4(2)（吴子华）or习题二1，2(3)，3(2),4(2)（冯伟森）第二节、谓词合适公式（WFF）一、定义1.项：个体域上的常元、变元、函数称为项。例：a，b，x，y，f（x，y），g（h（x），x）等都是论域上的项。2。原子公式：当P是n元谓词标识符，t1，t2，，tn都是论域中的项时，称P(t1，t2，，tn)为n元原子谓词公式。例：A(x)，L(