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 $\circ, \union, \cap, *$ , 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
  }
}