Differences

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

--- sav08:homework06 [2008/04/08 15:38]
vkuncak
+++ sav08:homework06 [2008/04/08 15:45]
vkuncak
@@ 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$.
-**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).