数理逻辑2014.pptVIP

系统的展开 Th16: A??xB(x)├┤?x(A?B(x)) x?A ├ A??xB(x) (已知) ┐?x(A?B(x)) (H) ?x┐(A?B(x)) (2,TH..) ┐(A?B(a)) (3,?-)取a?1,2 A,┐B(a) (5,TH..) ?x┐B(x) (3,2,?+) ┐?xB(x) (6,TH..) ?xB(x) (1,5,?-) ?x(A?B(x)) (2,7,8,┐) 系统的展开 Th16: A??xB(x)├┤?x(A?B(x)) x?A ┤ ?x(A?B(x)) (已知) A?B(a) (H) 取a?1 A (H) B(a) (2,3,?-) ?xB(x) (5,?+) ?xB(x) (6,TH..) A??xB(x) (1,5,?+) A??xB(x) (2,7,?-) 谓词与量词 个体常元：表示固定的个体。 a：表示小王。 P(x):x是教师。 P(a):小王是教师。 函数符号：表示个体域上的n元函数。 P(x):x是教师。 f(x):x的父亲。 P(f(x)):x的父亲是教师。 谓词与量词 用符号来表示下述命题：P(x):x是素数。Q(x):x是偶数。R(x,y):xy。E(x,y):x=y。 1.有的数既是素数又是偶数。 2.任何大于2的素数都不是偶数。 3.无论x是多大的素数，还有比x更大的素数。 4.没有比2大的偶数是素数。 5.没有最大的素数。 6.有且只有一个偶数是素数。 谓词与量词 命题分解后引进的符号： 个体常元 个体变元（包含约束出现的和自由出现的） 函数符号 谓词符号 量词 谓词与量词 谓词逻辑公式的解释（模型）： 指定一个集合作为论域。 将每个常元指定为论域中的一个元素。 将n元函数符号指定为论域上的n元函数。 将n元谓词符号指定为论域上的n元关系。 将自由出现的变元指定为论域中的一个元素。 谓词与量词 谓词逻辑公式的解释： ?xP(x) 论域：{1,2,3,4}, P(x):x0 ?x(P(x)∧Q(x)) 论域：{1,2,3,4}, P(x):x是整数，Q(x)：x是有理数 谓词与量词 谓词逻辑公式的真假值 对于有限论域U={a1..an} ?xB(x)为真  iff B(a1)为真且B(a2)为真..B(an)为真  iff B(a1)∧B(a2)∧..B(an)为真 ?xB(x)为真  iff B(a1)为真或B(a2)为真..B(an)为真  iff B(a1)∨B(a2)∨..B(an)为真 谓词与量词 谓词逻辑公式的真假值： ?xP(x) 论域：{1,2,3,4}, P(x):x0 ?x(P(x)∧Q(x)) 论域：{1,2,3,4}, P(x):x是整数，Q(x)：x是有理数 谓词与量词 永真式：如果一个公式在所有解释下取值都为真，称之为永真式。 ?x(R(x)?R(x)) 永假式：如果一个公式在所有解释下取值都为假，称之为永假式。 ┓?x(R(x)?R(x)) 谓词与量词 同真假式：如果两个公式在所有解释下的真假值都相同，称这两个公式是同真假式。 一些同真假式 ?xA(x)与 ┐?x┐A(x) ?xA(x)与 ┐?x┐A(x) ?xA(x)∧?xB(x)与 ?x(A(x)∧B(x)) ?xA(x)∨?xB(x)与 ?x(A(x)∨B(x)) 谓词逻辑自然推理系统NL NL中的符号： 个体词：a,b,c,ai,bi,ci 谓词：F,G,H,Fi,Gi,Hi 约束变元：x,y,z,xi,yi,zi 量词：?，? 联结词：┓、∧、∨、?、? 辅助符号：(，) 谓词逻辑自然推理系统 中的合式公式： ①如果A是n元谓词符号，a1,a2...an是个体词，则A(a1,a2...an)是合式公式 ②如果A,B是合式公式，则(┓A),(A∧B), (A∨B),(A?B),(A?B)也是合式公式。 ③A(a)是合式公式，a在其中出现，x不在其中出现，则?xA(x)与 ?xA(x)是合式公式 只有通过①②③在有限步内得到的才是合式公式。 判断下列符号串是否为合式公式 ?P(x),?x∧Q(x), ?xF(x,a) 谓词逻辑自然推理系统 系统的推理规则： 1.A1，A2 ...An ├ Ai (i=1,2,...,n) (?) 2.如果Γ├?(???)且?├A，则Γ├A (τ)(传递律) 3.如果Γ├A，则Γ,?├A (τ0)(单调