Differences

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

--- sav08:homework06 [2008/04/03 13:51]
vkuncak
+++ sav08:homework06 [2008/04/08 15:50]
vkuncak
@@ Line 65: / Line 65: @@
 ===== 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}$.
-Following Problem 2 above, let $(\sigma_1,\sigma_2) \in r_0$ iff there exists substitution $\tau$ such that $\sigma_2 = \sigma_1 \circ \tau$ where $\circ$ is the standard relation composition.
+Following Problem 2 above, let $(\sigma_1,\sigma_2) \in r_0$ iff there exists substitution $\tau$ such that $subst(\sigma_2) = subst(\sigma_1) \circ subst(\tau)$ where $\circ$ is the standard relation composition.
 **a)** Compute $r = r_0^*$.  What is its relationship to $r_0$?
-**b)** Compute $s = r \cap r^{-1}$.  Show that relation $s$ holds iff $\sigma_2 = \sigma_1 \circ 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$.
+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).
-**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]$).