Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:homework06 [2008/04/08 15:38] vkuncak |
sav08:homework06 [2008/04/08 15:50] vkuncak |
||
|---|---|---|---|
| Line 65: | Line 65: | ||
| ===== Problem 3 ===== | ===== Problem 3 ===== | ||
| - | (Recall [[Unification]].) | + | (Recall [[Substitutions for First-Order Logic]], [[Unification]].) |
| Let $V$ be an infinite set of variables. Let ${\cal L}$ be some first-order language. We will consider terms that contain variables from $V$ and function symbols from ${\cal L}$. | Let $V$ be an infinite set of variables. Let ${\cal L}$ be some first-order language. We will consider terms that contain variables from $V$ and function symbols from ${\cal L}$. | ||
| Line 75: | Line 75: | ||
| **b)** Compute $s = r \cap r^{-1}$. Show that relation $s$ holds iff $subst(\sigma_2) = subst(\sigma_1) \circ subst(b)$ where $b$ is a relation which is bijection on the set $V$. | **b)** Compute $s = r \cap r^{-1}$. Show that relation $s$ holds iff $subst(\sigma_2) = subst(\sigma_1) \circ subst(b)$ where $b$ is a relation which is bijection on the set $V$. | ||
| - | **c)** Let $E$ be a fixed set of syntactic equations. Let $U$ be the set of unifiers for $E$ and $[U] = \{ [\sigma] \mid \sigma \in U \}$. Show that if $U$ is non-empty, $a \in [U]$ such that for all $b \in [U]$, we have $(a,b) \in [r]$ (that is, $a$ is the least element of $[U]$). | + | Optional: **c)** Let $E$ be a fixed set of syntactic equations. Let $U$ be the set of unifiers for $E$ and $[U] = \{ [\sigma] \mid \sigma \in U \}$. Show that if $U$ is non-empty, then there exists $a \in [U]$ such that for all $b \in [U]$, we have $(a,b) \in [r]$ (that is, $a$ is the least element of $[U]$ with respect to $[r]$ defined as in Problem 2). |