离散数学(第7讲)谓词逻辑

《离散数学(第7讲)谓词逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栾新成四川大学软件学院luanxch@sina.com8599782213808024081第2章一阶谓词逻辑(2)主要内容谓词公式与解释1.谓词的合适公式2.谓词公式的解释3.几个特殊的公式谓词公式的等价与范式表示1.谓词公式的等价2.基本等价式3.前束范式4.斯柯林范式2021年9月14日2谓词公式同命题演算一样，在谓词逻辑中也同样包含命题变元和命题联结词，为了能够进行演绎和推理，为了对谓词逻辑中关于谓词的表达式加以形式化，利用联结词、谓词与量词构成命题函数，我们必须引入公式的概念。2021年9月14日3谓词公式四类符号:常量符号：一般用a,b,c,

2、…,a1,b1,c1,…来表示，它可以是D中的某个元素;变量符号：一般用x,y,z,…,x1,y1,z1,…来表示.它可以取值于D中的任意元素；函数符号：一般用f,g,h,…,f1,g1,h1,…来表示。n元函数符号f(x1,x2,...xn)可以是Dn→D的任意一个函数；谓词符号：一般用P,Q,R,...,P1,Q1,R1,...来表示。n元谓词符号P(x1,x2,...xn)可以是Dn→{0,1}的任意一个谓词。注：不含变元的函数是常量；不含客体变元的谓词是命题。2021年9月14日4谓词公式n元函数符号f(x1,x2,...xn)与n元谓词符号P(

3、x1,x2,...xn)1）两个n元相同吗？2）函数符号f(x1,x2,...xn)中的f可以用P代换吗？如果能，则代换结果为P(x1,x2,...xn)，与谓词符号P(x1,x2,...xn)的区别是什么？2021年9月14日值域不同5谓词公式定义2-2.1谓词逻辑中的项被递归地定义为：1）任意的常量符号是项；2）任意的变量符号是项；3）若f(x1,x2,x3,…,xn)是n元函数符号，t1,t2,t3,…,tn是项，则f(t1,t2,t3,…,tn)是项；4）只有有限次使用1)-3)产生的符号串才是项。例2.1复合函数f(g(f(a),g(a,x))

4、)是一个项2021年9月14日6谓词公式定义2-2.2设P(x1,x2,x3,...xn)是n元谓词，t1,t2,t3,...tn是项,则P(t1,t2,t3,...tn)是原子谓词公式，简称原子公式。定义2-2.3满足下列条件的表达式，称为合适公式,简称公式。1）原子公式是合适公式；2）若G，H是合适公式，则(┐G)、(┐H)、(G∨H)、(G∧H)、(G→H)、(GH)也是合适公式；3）若G是合适公式，x是个体变量，则(x)G、(x)G也是合适公式；4）仅仅由1)-3)产生的表达式才是合适公式。2021年9月14日G的区别:G与(x)G（x)

5、7谓词公式例2.2(P(x)→(Q(x,y)∨┐R(x,a,f(z))))(P(x)∨R(y))(x)(P(x))等都是公式。而(x)(P(x)→R(x)(x)∨P(x)(y)等则不是公式，前者括号不匹配，后者量词无辖域。2021年9月14日8谓词公式的翻译例1并非每个实数都是有理数解：设R(x):x是实数,Q(x):x是有理数原命题为：～x(R(x)→Q(x))例2没有不犯错误的人解：设M(x)：x是人,F(x):x犯错原命题为：～x（(M(x)∧～F(x))例3尽管有人聪明，但未必一切人都聪明。解：设M(x):x是人,P(x):x聪明原题

6、为：x(M(x)∧P(x))∧～x(M(x)→P(x))2021年9月14日9谓词公式的翻译多元谓词可以多重量化例4翻译‘每个人都有缺点’。解：设F（x,y）:x有y,M(x):x是人G(y):y有缺点原命题为:x(M(x)→y(G(y)∧F(x,y))例5:翻译‘某些人对某些食物过敏’。解：设F（x,y）:x对y过敏,M(x):x是人G(y):y是食物。原命题为:xy(M(x)G(y)∧F(x,y))2021年9月14日10谓词公式的翻译谓词对于个体刻划的深度的机动灵活性例6翻译‘那只小花猫逮住这只大老鼠’。解：设a:F(x,y):x逮住

7、y,P(x):x是小花猫,Q(y):y是大老鼠,S(a):a是那只,R(b):b是这只原命题为：ab(P(a)∧Q(b)∧F(a,b)∧S(a)∧R(b))bA(x):x是猫,B(x):x是小的,C(x):x是花的,D(y):y是的,E(y):y是老鼠,F(x,y),S(a),R(b)同上。原命题为：ab(A(a)B(a)C(a)D(b)E(b)∧F(a,b)∧S(a)∧R(b))。2021年9月14日11谓词公式的解释定义2-2.4一个定义在论域D上的公式G的每一个解释（指派）由如下四部分组成：1、非空的个体域集合D；2、G中的每个常量

8、符号,指定D中的一个元素；3、G中的每个n元函数符号,指定Dn到D的一个函数；4