CM20019---Computation III:
Formal Logic and Semantics
2007
Exercise sheet 1---Solutions
Problem 1
=========
1-balanced => 2-balanced
------------------------
*** Base step:
A string of length 0 is 2-balanced.
*** Inductive step:
If x is 1-balanced then either 1) there is a prefix y of x, such that the length of y is less than the length of x and such that the number of ('s is the same as the number of )'s, or 2) this is not the case.
In case 1, x = yz, for some z, and both y and z are 1-balanced and shorter than x, so they are 2-balanced. Then, x is 2-balanced.
In case 2, we deduce that x = (y), for some y, and y is 1-balanced (otherwise case 1 would apply). Then, x is 2-balanced.
2-balanced => 1-balanced
------------------------
*** Base step:
A string of length 0 is 1-balanced.
*** Inductive step:
If x is 2-balanced, either 1) x = (y) and y is 2-balanced or 2) x = yz and y and z are shorter than x and 2-balanced. In both cases it is trivial to apply the induction hypothesis and verify that the definition of 1-balancedness is verified.
Problem 2
=========
For example, a complete graph plus an isolated vertex: interpret R as `being connected by at least one edge'. For example, in
a---c
\ / d , R ={(aa), (ab), (ac), (ba), (bb), (bc), (ca), (cb), (cc)} ;
b
R is not reflexive because (dd) does not belong to it.
Problem 3
=========
Transitive closure:
{(12) (23) (34) (54) (13) (24) (14)} .
Reflexive, transitive closure:
{(11) (22) (33) (44) (55)
(12) (23) (34) (54) (13) (24) (14)} ;
the smart student will observe that we are assuming a minimal S = {1 2 3 4 5}.
Symmetric closure:
{(12) (23) (34) (54)
(21) (32) (43) (45)} .