# Exercises 02

#### 1

Translate:

if (x % 2 = 0) x = x / 2 else x = 3 * x + 1

#### 2

Prove identities using relations from Sets and relations.

More examples:

http://en.wikipedia.org/wiki/Relation_algebra#Expressing_properties_of_binary_relations_in_RA

#### 3

Prove monotonicity (by induction): if we have any relation given by expression built from , if we replace a relation in this expression with its superset, we obtain an expression denoting a larger relation.

#### 4

Prove that this program

if (P) { if (Q) { s1 } else { s2 } } else { if (Q) { s3 } else { s4 } }

has the same meaning as this program:

if (Q) { if (P) { s1 } else { s3 } } else { if (P) { s2 } else { s4 } }