Logic in Computer Science An Introductory Course for Master Students Wang j iwang@nudt.edu.cn Lecture 8 Logic in Computer Science- p 1/18
Logic in Computer Science An Introductory Course for Master Students Wang Ji jiwang@nudt.edu.cn Lecture 8 Logic in Computer Science – p.1/18
SEMANTICS Logic in Computer Science- p 2/18
Semantics Logic in Computer Science – p.2/18
Interpretation An interpretation L of f is D, Lo > where d is a non- empty set called the domain of ndividuals Lo is a mapping defined on the constants of F satisfying If c is an individual constant, then lo d 2. If fm is an n-ary function constant, then 0():D→D 3. If p is a propositional constant, then 10p)∈{T,F} 4. If Pn is an n-ary predicate constant, then 0P):Dn→{T,F} Logic in Computer Science -p 3/18
Interpretation An interpretation I of F is < D, I0 >, where • D is a non-empty set called the domain of individuals. • I0 is a mapping defined on the constants of F satisfying 1. If c is an individual constant, then I0(c) ∈ D. 2. If f n is an n-ary function constant, then I0(f n) : Dn → D. 3. If p is a propositional constant, then I0(p) ∈ {T, F}. 4. If Pn is an n-ary predicate constant, then I0(Pn) : Dn → {T, F}. Logic in Computer Science – p.3/18
assignment Given an interpretation I=< D, lo>,an assignment into I is a function o defined on the variables of f and satisfying 1. If a is an individual variable then o(Ed 2. If fm is an n-ary function variable, the en 0():D→D 3. If p is a propositional variable then 0(p)∈{TF}, 4. If Pn is an n-ary predicate variable, then 0(P):Dn→{T,F} If x is variable(of any type) and o1 and o2 are assignments, then o1 and o2 agree off a iff 01(g)=02(g) for all variables y (of any type) cience-p. 4/18
Assignment Given an interpretation I =< D, I0 >, an assignment into I is a function σ defined on the variables of F and satisfying 1. If x is an individual variable, then σ(x) ∈ D. 2. If f n is an n-ary function variable, then σ(f n) : Dn → D. 3. If p is a propositional variable, then σ(p) ∈ {T, F}. 4. If Pn is an n-ary predicate variable, then σ(Pn) : Dn → {T, F}. If x is variable (of any type) and σ1 and σ2 are assignments, then σ1 and σ2 agree off x iff σ1(y) = σ2(y) for all variables y (of any type) distinct from x. Logic in Computer Science – p.4/18
Semantics of terms Given z=<D,0>anda∈∑r,T(o)t), the value of term t with respect to o in I, is defined as follows 1. I(c(o)=Lo(c) if c is an individual constant 2. I(co)=o(c) if x is an individual variable 3.T("+1…tn)(σ)=0(f)T(t1)(σ)…T(t)() if fm is an n-ary function constant, and tr, .., tn are terms 4.T(尸"t1…tn)(σ)=σ(門)工(t1)(σ)…T(tn)(σ)if fn is an n-ary function variable, and t are terms Logic in Computer Science -p5/18
Semantics of Terms Given I =< D, I0 > and σ ∈ ΣI, I(σ)(t), the value of term t with respect to σ in I, is defined as follows 1. I(c)(σ) = I0(c) if c is an individual constant. 2. I(x)(σ) = σ(x) if x is an individual variable. 3. I(f nt1 · · ·tn)(σ) = I0(f n)I(t1)(σ)· · · I(tn)(σ) if f n is an n-ary function constant, and t1, · · · ,tn are terms. 4. I(f nt1 · · ·tn)(σ) = σ(f n)I(t1)(σ)· · · I(tn)(σ) if f n is an n-ary function variable, and t1, · · · ,tn are terms. Logic in Computer Science – p.5/18