CS计算机代考程序代写 /Users/billy/gits/moc-2021/tutes/week05.dvi

/Users/billy/gits/moc-2021/tutes/week05.dvi

School of Computing and Information Systems

COMP30026 Models of Computation Tutorial Week 5

23–27 August 2021

Semantics of Predicate Logic

We will introduce some additional notation in this tutorial to enable us to discuss interpretations

more explicitly. The data of an interpretation, I, involves the following choices, which associate

symbols (syntax) with objects and functions (semantics).

• A non-empty set D called the domain. Also written ID to distinguish it as “the domain of

I”. This set can be finite or infinite.

• For each constant a, an object of the domain I(a) ∈ D. This is the object that I decides a

to denote (it’s a name for that object).

• For each n-place function symbol f , a function I(f) : Dn → D. This is the function on objects

that I decides f to denote.

• For each n-place predicate symbol P , a function I(P ) : Dn → {f , t}. This is the truth-function

on objects that I decides P to denote.

A valuation σ : vars → D picks out an object for each variable, and we extend it to assign objects

to every term by adding it to the interpretation. So, given an interpretation I and valuation σ, the

object assigned to a term t is denoted I(σ, t), and is defined recursively on the term t as follows.

• I(σ, a) = I(a), for any constant a

• I(σ, x) = σ(x), for any variable x

• I(σ, f(t1, t2, . . . , tn)) = I(f)(I(σ, t1), I(σ, t2), . . . , I(σ, tn)) where f(t1, t2, . . . , tn) is a term

constructed from an n-place function symbol f and n-many terms ti.

We can now associate truth values to formulas. We will write I(σ,G) to denote the truth-value of

a formula G in an interpretation I with valuation σ. This is defined recursively on G.

• I(σ, P (t1, t2, . . . , tn)) = t iff I(P )(I(σ, t1), I(σ, t2), . . . , I(σ, tn)) = t

• I(σ,¬G) = t iff I(σ,G) = f

• I(σ,G ∧H) = t iff I(σ,G) = t and I(σ,H) = t

• . . . similarly for ∨,⇒,⇔,⊕

• I(σ, ∀xG) = t iff I(σx 7→d, G) = t for every d ∈ ID

• I(σ, ∃xG) = t iff I(σx 7→d, G) = t for at least one d ∈ ID

We say a formula G is true in an interpretation I, and write I � G, exactly when I(σ,G) = t for

any valuation σ. A formula is satisfiable if there is an interpretation I such that I � G, and valid

if this is true for every interpretation.

The exercises

T5.1 Consider the following interpretation I with domain ID = {Jemima,Thelma, Louise}. We

interpret names such that I(a) = Jemima, I(b) = Thelma, I(c) = Louise, and we interpret

predicate symbols as the following truth functions:

I(F ) Jemima Thelma Louise

Jemima f f t

Thelma t t f

Louise f t f

I(M)

Jemima t

Thelma f

Louise t

These tables define the truth-functions I(F ) : ID ×ID → {f , t}, which decides who “follows”

whom, and I(M) : ID → {f , t}, which decides who “is muddy”. For I(F ), the row determines

the first argument, and the column determines the second.

Let v be a valuation such that v(x) = Louise, v(y) = Thelma, v(z) = Jemima.

For each formula G, use the semantics from the first page to evaluate the truth of G in the

interpretation I with valuation v, that is, what is I(v,G)? You should spell out the details

of evaluating a couple of them, and then intuitively explain the rest.

(i) F (x, a)

(ii) ∃y F (x, y)

(iii) ∀x(∃y F (x, y))

(iv) ∀y F (b, y)

(v) ∃x(∀y F (x, y))

T5.2 We define a new interpretation I as follows. Let ID = N = {0, 1, 2, 3, . . . }. We interpret the

name a as the zero object, so I(a) = 0 ∈ N, the function symbol s as the successor function

I(s) : N → N, such that I(s)(x) = x + 1, the predicate symbol P as the truth-function

I(P ) : N × N × N → {f , t} which is true of numbers x, y, z iff x + y = z, and the predicate

symbol L as the truth-function I(L) : N × N → {f , t}, which is true of numbers x and y iff

x ≤ y.

For each formula G, decide whether I � G. Remember this requires the truth of I(v,G) for

any valuation v.

(i) P (s(a), a, s(s(a)))

(ii) ∃xP (s(s(a)), s(a), s(x))

(iii) P (s(s(a)), s(a), s(x))

(iv) ∀x∀y∀z(P (x, y, z)⇒ P (y, x, z))

(v) ∀x(∃yL(s(y), x))

(vi) L(x, s(x))

T5.3 For each formula G, modify the interpretation I from T5.1 so that I � G. Remember

this requires the truth of I(v,G) for any valuation v. You will need to provide a function

I(g) : ID → ID for the function symbol g in (iii).

(i) ¬∀x∃y F (x, y)

(ii) M(a) ∧M(b) ∧M(c) ∧ ¬∀x M(x)

(iii) ∀x F (x, g(x))

(iv) M(x)