Differences

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

--- sav07_homework_1_solution [2007/03/17 18:51]
vkuncak
+++ sav07_homework_1_solution [2007/03/19 12:02]
wikiadmin
@@ Line 4: / Line 4: @@
 <latex>
 r \circ (s \cap t) \subseteq (r \circ s) \cap (r \circ t)
 </latex>
 holds. Namely, suppose  <latex>(x,z) \in r \circ (s \cap t)</latex>.
 Then there is a y such
-that <latex>(x,y) \in r</latex> and <latex>(y,z) \in s \cap t</latex>.  Therefore,
+that <latex>(x,y) \in r</latex> and <latex>(y,z) \in s \cap t </latex>.  Therefore,
 <latex>(y,z) \in s</latex> and <latex>(y,z) \in t</latex>.  From <latex>(x,y) \in r</latex> and <latex>(y,z) \in s</latex> we
 have <latex>(x,z) \in r \circ s</latex>. Similarly,
@@ Line 41: / Line 41: @@
   \{(z,x) \mid \exists y. (x,y) \in r \land (y,z) \in s \}
 </latex>
 ==== Task 4 ====
@@ Line 70: / Line 71: @@
 wp.
+==== Task 5 ====
+The property
+<latex>
+wp(r,Q_1 \cup Q_2) = wp(r,Q_1) \cup wp(r,Q_2)
+</latex>
+does not hold in general.  As a counterexample, take three
+distinct states s_1, s_2, and s_3, and let
+<latex>
+\begin{array}{l}
+r = \{ (s_1,s_2), (s_1,s_3) \} \\
+Q_1 = \{ s_2 \} \\
+Q_2 = \{ s_3 \}
+\end{array}
+</latex>
+Note: the property does hold for deterministic relations.
+==== Task 6 ====
+The property
+<latex>
+wp(r,Q_1 \cap Q_2) = wp(r,Q_1) \cap wp(r,Q_2)
+</latex>
+is true and follows from the characterization of wp in Task 4 and the distribution of the right-hand side of implication and universal quantification
+with respect to conjunction.