Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:first-order_logic_semantics [2008/03/19 21:46] damien |
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) &=& (\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) &=& (\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 ===== | ||
Line 130: | Line 133: | ||
With an empty domain, this formula would be false. | With an empty domain, this formula would be false. | ||
There are other problems, for instance "how to evaluate a variable?". | There are other problems, for instance "how to evaluate a variable?". | ||
+ | |||
===== Satisfiability, Validity, and Semantic Consequence ===== | ===== Satisfiability, Validity, and Semantic Consequence ===== | ||
Line 149: | Line 153: | ||
\[ | \[ | ||
\begin{array}{rcl} | \begin{array}{rcl} | ||
- | T \models G & \leftrightarrow & \forall I. ((\forall F \in T. e_F(F)(I)) \rightarrow e_F(G)) \\ | + | T \models G & \leftrightarrow & \forall I. ((\forall F \in T. e_F(F)(I)) \rightarrow e_F(G)(I)) \\ |
- | & \leftrightarrow & \forall I. (\lnot (\forall F \in T. e_F(F)(I)) \lor \lnot e_F(\lnot G)) \\ | + | & \leftrightarrow & \forall I. (\lnot (\forall F \in T. e_F(F)(I)) \lor \lnot e_F(\lnot G)(I)) \\ |
- | & \leftrightarrow & \forall I. (\exists F \in T. \lnot e_F(F)(I)) \lor \lnot e_F(\lnot G)) \\ | + | & \leftrightarrow & \forall I. (\exists F \in T. \lnot e_F(F)(I)) \lor \lnot e_F(\lnot G)(I)) \\ |
& \leftrightarrow & \forall I. \exists F \in T \cup \{\lnot G\}. \lnot e_F(F)(I) \\ | & \leftrightarrow & \forall I. \exists F \in T \cup \{\lnot G\}. \lnot e_F(F)(I) \\ | ||
& \leftrightarrow & \lnot \exists I. \forall F \in T \cup \{\lnot G\}. e_F(F)(I) \\ | & \leftrightarrow & \lnot \exists I. \forall F \in T \cup \{\lnot G\}. e_F(F)(I) \\ |