Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav07_lecture_2 [2007/03/22 20:32] vkuncak |
sav07_lecture_2 [2007/04/03 20:31] kremena.diatchka |
||
|---|---|---|---|
| Line 248: | Line 248: | ||
| What is a formal proof? | What is a formal proof? | ||
| + | |||
| Line 308: | Line 309: | ||
| \end{equation*} | \end{equation*} | ||
| - | Sets and properties are interchangable. | + | Sets and predicates are interchangable. |
| $x \in P$ turns set into predicate. | $x \in P$ turns set into predicate. | ||
| Line 371: | Line 372: | ||
| <latex> | <latex> | ||
| \begin{array}{l} | \begin{array}{l} | ||
| - | \exists(x_2,y_2) \{((x_1,y_1)(x_2,y_2),(x_3,y_3)),y_2=y_1 \wedge x_2 = x_1 + 3\\ | + | \exists(x_2,y_2) \{((x_1,y_1)(x_2,y_2),(x_3,y_3)),y_2=y_1 \wedge x_2 = y_1 + 3\\ |
| \wedge y_3 = y_2 \wedge x_3 = x_2 + y_2 \} | \wedge y_3 = y_2 \wedge x_3 = x_2 + y_2 \} | ||
| \end{array} | \end{array} | ||
| Line 505: | Line 506: | ||
| Weakest preconditions of assignments make wp very appealing. | Weakest preconditions of assignments make wp very appealing. | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | ===== Semantics of references and arrays ===== | ||
| - | |||
| - | Program with class declaration | ||
| - | |||
| - | <code java> | ||
| - | class Node { | ||
| - | Node left, right; | ||
| - | } | ||
| - | </code> | ||
| - | |||
| - | How can we represent fields? | ||
| - | |||
| - | Possible mathematical model: fields as functions from objects to objects. | ||
| - | |||
| - | left : Node => Node | ||
| - | right : Node => Node | ||
| - | |||
| - | What is the meaning of assignment? | ||
| - | |||
| - | x.f = y | ||
| - | |||
| - | <latex> | ||
| - | f[x \mapsto y](z) = \left\{ \begin{array}{lr} | ||
| - | y, & z=x \\ | ||
| - | f(z), & z \neq x | ||
| - | \end{array}\right. | ||
| - | </latex> | ||
| - | |||
| - | Eliminating function updates in formulas. | ||
| - | |||
| - | Representing arrays. | ||
| - | |||
| - | What does this mean for our formulas? | ||
| - | |||
| - | <code java> | ||
| - | assume (x.f = 1); | ||
| - | y.f = 0; | ||
| - | assert (x.f > 0) | ||
| - | </code> | ||
| - | |||
| - | left, right - uninterpreted functions (can have any value, depending on the program, unlike arithmetic functions such as +,-,* that have fixed interpretation). | ||
| - | |||
| - | |||
| - | |||