国防科学技术大学：《数理逻辑》（英文版）Lecture 8 Semantics

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 , 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=,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 =, 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=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 = 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

Semantics of wffs Given an interpretation l= and an assignment o, I(o (A), the value of A with respect to o in l. for each wff is defined as follows I(p(o)=lo(p)if p is a propositional constant I(p)o=o(p) if p is a propositional variable T(Pt1…tn)(σ)=o(P")(t1)()…T(tn)(a) if Pn is an n-ary predicate constant, and t1,…, tn are terms T(P"t1…tn)(σ)=σ(P")(t1)(σ)…(tn)(σ if Pn is an n-ary predicate variable, and ,……, t are terms. Logic in Computer Science -p 6/18

Semantics of Wffs Given an interpretation I = and an assignment σ, I(σ)(A), the value of A with respect to σ in I, for each wff, is defined as follows • I(p)(σ) = I0(p) if p is a propositional constant. • I(p)(σ) = σ(p) if p is a propositional variable. • I(Pnt1 · · ·tn)(σ) = I0(Pn)I(t1)(σ)· · · I(tn)(σ) if Pn is an n-ary predicate constant, and t1, · · · ,tn are terms. • I(Pnt1 · · ·tn)(σ) = σ(Pn)I(t1)(σ)· · · I(tn)(σ) if Pn is an n-ary predicate variable, and t1, · · · ,tn are terms. Logic in Computer Science – p.6/18

T()(A) I( A(o)=I(A)(o)if A is a wff I(AVBo)=I(A(oVI(B)(o)if A and B are wtrs If a is a wff and x is an individual variable if there exists d∈D such that I(A)(olc/d t otherwise Logic in Computer Science -p 7/18

I(σ)(A) • I(∼ A)(σ) = ¬I(A)(σ) if A is a wff. • I(A ∨ B)(σ) = I(A)(σ)∨I(B)(σ) if A and B are wffs. • If A is a wff and x is an individual variable, I(∀xA)(σ) =  F if there exists d ∈ D such that I(A)(σ[x/d]) = F T otherwise Logic in Computer Science – p.7/18

a set of Important Definitions 1. 0 satisfies A in I(F(I) A)iff I(A)(o)=T 2. A is satisfiable in I iff there is o E Xr such that (Z,0)A 3. A is satisfiable iff there is an interpretation in Which a is satisfiable 4. A is valid in I(FI A) iff for every assignment ∈∑x,F(x)A 5. A is valid iff a is valid in every interpretation 6. A is contradictory or unsatisfiable iff for every interpretation i and every assignment o T(A)()=F Logic in Computer Science -p8/18

A set of Important Definitions 1. σ satisfies A in I (|=(I,σ) A) iff I(A)(σ) = T 2. A is satisfiable in I iff there is σ ∈ ΣI such that |=(I,σ) A. 3. A is satisfiable iff there is an interpretation in which A is satisfiable. 4. A is valid in I (|=I A) iff for every assignment σ ∈ ΣI, |=(I,σ) A. 5. A is valid iff A is valid in every interpretation. 6. A is contradictory or unsatisfiable iff for every interpretation I and every assignment σ, I(A)(σ) = F. Logic in Computer Science – p.8/18

Definitions(continued 1. a set t of wff is satisfiable in i iff there is an assignment o∈∑ r such that for all B∈T (工,o) B 2.a set t of wff is satisfiable iff there is an interpretation I such that r of wff is satisfiable n⑦ 3. a sett of wff is unsatisfiable iff it is not satisfiable 4. a model for a set of wffs is an interpretation in Which each of the wffs is valid 5. I logically implies A (T F A)iff fc or ever interpretation I and every g∈∑r,F(xo)A provided that F(I, o B for every B. gic in Computer Science-p. 9/18

Definitions (continued) 1. A set Γ of wff is satisfiable in I iff there is an assignment σ ∈ ΣI such that for all B ∈ Γ, |=(I,σ) B. 2. A set Γ of wff is satisfiable iff there is an interpretation I such that Γ of wff is satisfiable in I. 3. A set Γ of wff is unsatisfiable iff it is not satisfiable. 4. A model for a set of wffs is an interpretation in which each of the wffs is valid. 5. Γ logically implies A (Γ |= A) iff for every interpretation I and every σ ∈ ΣI, |=(I,σ) A provided that |=(I,σ) B for every BLogic . in Computer Science – p.9/18

Proposition on semantics of Terms and wifs Let a be a wff t a term and l= an Interpretation,anda1,a2∈∑r If o1 and o2 agree on all variables which occur in t. then T(t)(01)=T(t) 2. If 01 and 2 agree on all variables which occur free in a, then T(A)(01)=(4)(02) Logic in Computer Science- p10/18

Proposition on Semantics of Terms and Wffs Let A be a wff, t a term and I = an interpretation, and σ1, σ2 ∈ ΣI. 1. If σ1 and σ2 agree on all variables which occur in t, then I(t)(σ1) = I(t)(σ2) 2. If σ1 and σ2 agree on all variables which occur free in A, then I(A)(σ1) = I(A)(σ2) Logic in Computer Science – p.10/18