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:47] vkuncak |
sav08:homework06 [2008/04/03 13:51] 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 48: | Line 50: | ||
| **a)** Give an example $r_0$ for which $r$ is not necessarily a partial order. | **a)** Give an example $r_0$ for which $r$ is not necessarily a partial order. | ||
| - | **b)** Define $s = r \cup r^{-1}$. Show that $s$ is a congruence with respect to $r$, that is: $s$ is reflexive, symmetric, and transitive and for all $x,x',y,y' \in D$, | + | **b)** Define $s = r \cap r^{-1}$. Show that $s$ is a congruence with respect to $r$, that is: $s$ is reflexive, symmetric, and transitive and for all $x,x',y,y' \in D$, |
| \[ | \[ | ||
| (x,x') \in s \land (y,y') \in s \rightarrow ((x,y) \in r \leftrightarrow (x',y') \in r) | (x,x') \in s \land (y,y') \in s \rightarrow ((x,y) \in r \leftrightarrow (x',y') \in r) | ||
| 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 69: | Line 73: | ||
| **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 \cup 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 $\sigma_2 = \sigma_1 \circ 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, then there exists a least element of $[U]$, that is, there exists $a \in [U]$ such that for all $b \in [U]$, we have $(a,b) \in [r]$. | + | |
| + | **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]$). | ||