Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
sav07_homework_1_solution [2007/03/17 18:51] vkuncak |
sav07_homework_1_solution [2007/03/19 12:00] wikiadmin |
||
---|---|---|---|
Line 4: | Line 4: | ||
<latex> | <latex> | ||
- | r \circ (s \cap t) \subseteq (r \circ s) \cap (r \circ t) | + | r \circ (s \cap t) \subseteq (r \circ s) \cap (r \circ t) |
</latex> | </latex> | ||
- | holds. Namely, suppose <latex>(x,z) \in r \circ (s \cap t)</latex>. | + | holds. Namely, suppose <latex>(x,z) \in r \circ (s \cap t) </latex>. |
Then there is a y such | 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, | ||
Line 41: | Line 41: | ||
\{(z,x) \mid \exists y. (x,y) \in r \land (y,z) \in s \} | \{(z,x) \mid \exists y. (x,y) \in r \land (y,z) \in s \} | ||
</latex> | </latex> | ||
+ | |||
==== Task 4 ==== | ==== Task 4 ==== | ||
Line 70: | Line 71: | ||
wp. | 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. |