math-chap2-2.离散数学-谓词逻辑

1第二章谓词逻辑2主要内容谓词逻辑的根本概念谓词公式谓词逻辑等值式谓词逻辑推理3命题逻辑的缺乏之处命题逻辑研究的对象为命题(为一个完整的陈述句)，对于原子命题不可分。例鱼儿离不开水。鲫鱼是鱼。所以鲫鱼离不开水。简单命题之间的内在联系需要通过进一步分析原子命题中主、谓等之间的关系。个体谓词量词4个体定义：可以独立存在的客观实体称为个体。具体事物抽象概念例小王和小明是同学。a能被2整除。x是有理数。个体常项：表示具体或特定的个体，常用字母a,b,c...表示；个体变项：表示抽象或泛指的个体，常用字母x,y,z...表示；个体域：个体变项的取值范围，也称论域。全总个体域：宇宙间一切事物组成的个体域。5谓词定义：刻画个体具有的性质或个体之间关系的词。谓词常项：表示具体性质或关系的谓词。谓词变项：表示抽象的或泛指的谓词。谓词符号通常用大写字母表示。例：F：...和...是同学。G：...能被...整除。H：...是有理数。6谓词元数：谓词中包含的个体变项数。含n个个体变项的谓词称为n元谓词。0元谓词：不带个体变项的谓词。命题均可以表示成0元谓词。例：4=3+1如果2是素数，那么3是素数。7量词定义：表示个体常项或变项之间数量关系的词。全称量词：一切的、所有的、每一个、任意的、都...。符号化为“

”。表示个体域里的所有个体关系。存在量词：存在、有一个、有的、至少有一个...。符号化为“

”。表示个体域里有的个体关系。例所有人都需要呼吸空气。有的人没来上课。8量词量词需要注意个体域的问题。在不同的个体域内，命题的真值可能不同。例：存在x，使得x+3=2。个体域为自然数个体域为整数特性谓词：将某类个体从个体域中区分出来的谓词。M(x)：x是人；F(x)：x是鱼；Z(x)：x是整数。9命题符号化明确命题个体域，分别找出个体常项、个体变项、量词和谓词；按照命题的意思用逻辑联结词将其组合；注意：引入特性谓词时，全称量词的特性谓词作为命题的前提引入，而存在量词的特性谓词作为命题的合取项引入；多个量词同时出现，需要注意量词的顺序不能随意颠倒。例：并非所有的人都爱看电视。10一阶谓词的例火车比汽车跑得快。有理数可以表示成分数。有的女孩不喜欢穿裙子。11谓词公式谓词公式的符号集个体常项：a,b,c,...个体变项：x,y,z,...函数符号：f,g,h,...谓词符号：F,G,H,...量词：,;联结词符号：¬,∧,∨,→,↔;括号：),(12谓词公式谓词公式的项的递归定义个体常项和个体变项是项；假设f(x1,x2,...,xn)是任意的n元函数，t1,t2,...,tn是任意n个项，那么f(t1,t2,...,tn)是项；所有的项都由有限次使用上述两条规定得到。原子公式：设R(x1,x2,...,xn)是符号集上任意n元谓词，t1,t2,...,tn是符号集的任意n个项，那么称R(t1,t2,...,tn)为原子公式。13合式公式定义(1)原子公式是合式公式；(2)假设A是合式公式，那么(¬A)也是合式公式(3)假设A，B是合式公式，那么(A∧B)，(A∨B)，(A→B)，(A↔B)也是合式公式；(4)假设A是合式公式，那么xA，xA也是合式公式；(5)只有有限次的应用(1)-(4)得到的符号串才是合式公式。14约束变项及自由变项定义：xF，xF中，x称为指导变项，F称为相应量词的辖域。辖域中x的所有出现称为约束出现，x称为约束变项，F中不是约束出现的其他变项称为自由变项。例xF(x)→yG(x,y)x(F(x,y)∧y(G(x,y))xy(F(x,y)∧G(y,z))∨H(x,y)闭式：假设合式公式中无自由出现的个体变项，那么称A为封闭的公式，简称闭式。15变项替换规那么变项替换的目的：为了防止个体变项的混淆。规那么约束变项换名规那么：将量词辖域中出现的某个约束变项及其对应的指导变项改成公式中未出现的个体变项符号，其余局部不变。自由变项代替规那么：将公式中某自由变项用原公式中未出现过的某个个体变项符号代替，且处处代替。16谓词公式的解释定义：为使公式成为真值确定的命题而指定的有关规定，称为谓词公式的一个解释。解释I的组成特定的个体域DD中一局部特定元素D上每个函数变项所取得的具体函数D上每个谓词变项所取的具体谓词例：x(F(f(x))→G(x))17谓词公式的分类谓词公式的分类：如果A在任何解释下都为真，那么称A为永真式〔逻辑有效式〕。如果A在任何解释下都为假，那么称A为永假式〔矛盾式〕。假设至少存在一组A的解释使A为真，那么称A为可满足式。代换实例：设A0是含命题变项p1,p2,...,pn的命题公式，A1,A2,...,An是n个谓词公式。用Ai代换A0中的每一个pi，所得的公式A称为A0的代换实例。18谓词公式的定理定理：命题公式中的重言式的代换实例在谓词公式中为逻辑有效式；命题公式中的矛盾式的代换实例是谓词公式中仍为矛盾式。19谓词逻辑等值式等值式的定义：设谓词逻辑中任意两个公式A和B，假设A↔B是是逻辑有效式，那么称A与B为等值式。记作AB。原命题等值式的代换实例都是等值式。消去量词等值式：设个体域D＝{a1,a2,...,an}xA(x)A(a1)∧A(a2)∧...∧A(an)xA(x)A(a1)∨A(a2)∨...∨A(an)量词否认等值式¬xA(x)x¬A(x)¬xA(x)x¬A(x)20谓词逻辑等值式量词辖域扩张和伸缩等值式

x(A(x)∨B)

xA(x)∨B

x(A(x)∨B)

xA(x)∨B

x(A(x)∧B)

xA(x)∧B

x(A(x)∧B)

xA(x)∧B

x(A(x)→B)

xA(x)→B

x(A(x)→B)

xA(x)→B

x(B→A(x))

B→

xA(x)

x(B→A(x))

B→

xA(x)21谓词逻辑等值式量词分配等值式

x(A(x)∧B(x))

xA(x)∧

xB(x)

x(A(x)∨B(x))

xA(x)∨

xB(x)量词交换等值式

x

yA(x,y)

y

xA(x,y)

x

yA(x,y)

y

xA(x,y)22前束范式定义：设A为谓词逻辑公式，假设A具有形式Q1x1Q2x2...QnxnB，其中Qi为或，B为不含量词的公式。存在定理：任何谓词逻辑公式都存在与之等值的前束范式。前束范式例：

xF(x)→xG(x)(

xF(x,y)→yG(y))→

xH(x,y)23