LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
sav08:first-order_logic_semantics [2008/04/02 20:46]
vkuncak
sav08:first-order_logic_semantics [2008/04/02 21:27]
vkuncak
Line 32: Line 32:
 ++++How do we evaluate quantifiers?​| ++++How do we evaluate quantifiers?​|
 \[\begin{array}{rcl} \[\begin{array}{rcl}
-e_F(\exists x.F)(I) &=& (\exists d \in D_I.\ e_F(F)(I[x \mapsto d])) \\ +e_F(\exists x.F)((D_I,​\alpha_I)) &=& (\exists d \in D_I.\ e_F(F)((D_I,​\alpha_I[x \mapsto d])) \\ 
-e_F(\forall x.F)(I) &=& (\forall d \in D_I.\ e_F(F)(I[x \mapsto d]))+e_F(\forall x.F)((D_I,​\alpha_I)) &=& (\forall d \in D_I.\ e_F(F)((D_I,​\alpha_I[x \mapsto d]))
 \end{array} \end{array}
 \] \]
-where $I[x \mapsto d] = (D_I,​\alpha^\prime_I)and +See [[Sets and relations#​function update|function update notation]] for definition of $\alpha_I[x \mapsto d]$.
-$\alpha^\prime_I(v) = \left \{ { {\alpha_I(v)~~\text{if}~ v \neq x} ~~ \atop {d ~~~~\text{if} ~ v=x}} \right$+
 ++++ ++++
  
 We generalize this notion as follows: if $I$ is an interpretation and $T$ is a set of first-order formulas, we write $e_S(T)(I)={\it true}$ iff for every $F \in T$ we have $e_F(F)(I)={\it true}$ (set is treated as infinite conjunction). ​  This is a generalization because $e_S(\{F\})(I) = e_F(F)(I)$. We generalize this notion as follows: if $I$ is an interpretation and $T$ is a set of first-order formulas, we write $e_S(T)(I)={\it true}$ iff for every $F \in T$ we have $e_F(F)(I)={\it true}$ (set is treated as infinite conjunction). ​  This is a generalization because $e_S(\{F\})(I) = e_F(F)(I)$.
 +
 +
 +**A terminological note:** in algebra, an interpretation is often called a //​structure//​. Instead of using $\alpha$ mapping language ${\cal L} = \{ f_1,​\ldots,​f_n,​ R_1,​\ldots,​R_m\}$ to interpretation of its symbols, the structure is denoted by a tuple $(D,​\alpha(f_1),​\ldots,​\alpha(f_n),​\alpha(R_1),​\ldots,​\alpha(R_n))$. ​ For example, an interpretation with domain ${\can N}$, with one binary operation whose interpretation is $+$ and one binary relation whose interpretation is $\leq$ can be written as $({\cal N},​+,​\leq)$. ​ This way we avoid writing $\alpha$ all the time, but it becomes more cumbersome to describe correspondence between structures.
 +
  
 ===== Examples ===== ===== Examples =====