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:homework06 [2008/04/02 16:50] vkuncak |
sav08:homework06 [2008/04/08 15:38] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Homework 06 - DRAFT ====== | + | ====== Homework 06 - Due April 9 ====== |
===== Problem 1 ===== | ===== Problem 1 ===== | ||
+ | |||
+ | (Recall [[Definition of Resolution for FOL]].) | ||
Let $F_0$ denote formula | Let $F_0$ denote formula | ||
Line 58: | Line 60: | ||
\] | \] | ||
Show that $[r]$ is a partial order on $[D]$. | Show that $[r]$ is a partial order on $[D]$. | ||
+ | |||
+ | Optional: Explain this constructions using terminology of graphs and strongly connected components. | ||
===== Problem 3 ===== | ===== Problem 3 ===== | ||
Line 65: | Line 69: | ||
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}$. | ||
- | 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$? | **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$. |
**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]$). | **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]$). | ||
- |