# Trying to understand interpretation and denotation in FOL

I am going through the book "Knowledge Representation and Reasoning" by Brachman and Levesque.

So an interpretation $F$ is defined as a pair $\langle D,I \rangle$ mapping from a set of objects $D$ called domain of the interpretation and $I$ is a mapping called interpretation mapping from the non-logical symbols to functions and relations over $D$.

Then it has been written that $I$ will assign meaning to the predicate symbols as follows:

To every predicate symbol P of arity $n$, $I[P]$ is an n-ary relation, that is, $I[P]$ is contained in $D \times D \times D \times \dots \times D$.

Now for denotation it is written that for an interpretation $F = \langle D,I \rangle$ we can specify which elements of $D$ are denoted by variable free term FOL.

And hence the notion of variable assignment $\mu$ has been introduced and the following two rules have been introduced:

Given an interpretation $F$ and a variable assignment $\mu$, the denotation of the term $t$ is written as $\|t\|_{F \mu}$ and defined as follows:

1. If $x$ is a variable then $\|x\|_{F \mu} = \mu [x]$.

2. If $t_1 ,\dots,t_n$ are terms and $f$ is a function symbol of arity $n$ then $\| f(t_1,\dots,t_n)\|_{F \mu} = G( d_1,\dots,d_n)$, where $G = I[f]$, and $d_i = \| t_i\| _{f \mu}$.

I am a bit confused about how to interpret the last two rules.

So the act of choosing elements from $D$ to represent the arguments of the function symbol is represented by $\mu$? Will it be right to say so?

How exactly are $f$ and $G$ related?

The output is evaluated by computing $G$ for values which get substituted in the argument which is represented in $d_i = \| t_i\| _{f \mu}$ of the second rule.

But I could not understand how are the above two rules recursive? What exactly should I conclude about the way $I$, $G$ , $f$ and $\mu$ are related to each other and what exactly do they mean? Is my understanding correct?

Attaching the screenshots from the book:

• Predicate symbols and function symbols are not the same thing. An $n$-ary predicate symbol $P$ is interpreted as a subset of $D^n$. A $n$-ary function symbol, $f$ is interpreted as a function $D^n\to D$. Function symbols are parts of terms. Predicate symbols are parts of formulas. There are a lot of typos, other possibly unintentional errors, and conflations of terms/notation in your question. For example, both $F$ and $I$ are called "interpretations" and $F$ is used both for an interpretation and a function. It would be helpful if you use different words/symbols for different things. – Derek Elkins left SE Apr 5 '18 at 4:24
• @DerekElkins : Actually I have quoted whatever is there in the book .Hiw to understand the two rules given there ? – Sheldon Kripke Apr 6 '18 at 3:59
• @DerekElkins :Hello Derek , could you help me find out the typos . I found one place where usage of same symbol might be resulting in confusion . I guess it is in the second rule and I am making that correction . Could you help me find out the other typos where I should make differentiation in the symbols ? – Sheldon Kripke Apr 12 '18 at 17:13

Consider the expression $+(x,\times(y,y))$, which is the FOL way to write $x+(y\cdot y)$. If I substitute $x=3$ and $y=5$ and do the arithmetic over the integers, what do I get? I need to evaluate the expression recursively.

In order to evaluate $+(x,\times(y,y))$, I need to evaluate $x$, to evaluate $\times(y,y)$, and then to combine them using the function $+$.

Evaluating $x$ is easy, since $x$ is just a variable. My assignment says that $x=3$, so the value of the expression $x$ is $3$.

Evaluating $\times(y,y)$ is more difficult. First I need to evaluate $y$ (twice) - as before, this is easy, and gives the result $5$. Now I need to combine the two values $5,5$ using the function $\times$. I have a large table which, for every pair of integers $a,b$, tells me what $\times(a,b)$ is. Looking at the table, I find out that $\times(5,5) = 25$.

Now that I have evaluated $x$ To $3$ and $\times(y,y)$ to $25$, I can finally look at the table for $+$ and deduce that $+(3,25) = 28$. So $28$ is the value of the entire expression.

The formal definitions you quote in your question attempt to capture the preceeding process in an abstract form. It's best if you work out the correspondence on your own.

• What exactly do you mean by evalauating the expression recursively ? – Sheldon Kripke Apr 13 '18 at 20:25
• So $\mu$ corresponds to the assignment of values that you are doing here , the process of selecting a table is $I$ , $G$ is the table that you are using . Isn't it so ? – Sheldon Kripke Apr 13 '18 at 20:27
• If that is so , in the notation $d_i$ = $|| t_i ||_{F \mu }$, where we are just assigning values to the $d$ 's , what is the need of emphasizing the "interpretation " $F$ . Isn't the assignment of values independent of interpretation ? – Sheldon Kripke Apr 13 '18 at 20:35
• $F$ consists of all tables defining functions and predicates. They are not set in stone. – Yuval Filmus Apr 13 '18 at 20:40
• Recursive evaluation is the way you would evaluate arithmetic expressions. The key is using recursion - I suggest doing some relevant reading. – Yuval Filmus Apr 13 '18 at 20:41