Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:first-order_logic_semantics [2008/03/19 21:24] damien |
sav08:first-order_logic_semantics [2008/04/02 20:46] 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)(I) &=& (\exists d \in D_I.\ e_F(F)(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)(I) &=& (\forall d \in D_I.\ e_F(F)(I[x \mapsto d])) |
\end{array} | \end{array} | ||
\] | \] | ||
Line 92: | Line 92: | ||
\] | \] | ||
++++ | ++++ | ||
+ | |||
Line 104: | Line 105: | ||
\forall x.\, \exists y.\, dvd(x,y) | \forall x.\, \exists y.\, dvd(x,y) | ||
\] | \] | ||
- | ++++answer| | + | ++answer| |
$true$. For any $x$ choose $y$ as $2 \cdot x$. | $true$. For any $x$ choose $y$ as $2 \cdot x$. | ||
- | ++++ | + | ++ |
What is the truth value of this formula | What is the truth value of this formula | ||
\[ | \[ | ||
\exists x.\, \forall y. dvd(x,y) | \exists x.\, \forall y. dvd(x,y) | ||
\] | \] | ||
- | ++++answer| | + | ++answer| |
$false$ | $false$ | ||
- | ++++ | + | ++ |
==== Domain Non-Emptiness ==== | ==== Domain Non-Emptiness ==== | ||
Line 122: | Line 125: | ||
\] | \] | ||
What is its truth value in $I$? Which condition on definition of $I$ did we use? | What is its truth value in $I$? Which condition on definition of $I$ did we use? | ||
+ | |||
+ | This formula is true with the assumption that $D$ is not empty. | ||
+ | |||
+ | With an empty domain, this formula would be false. | ||
+ | There are other problems, for instance "how to evaluate a variable?". | ||
Line 142: | Line 150: | ||
\[ | \[ | ||
\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) \\ |