There are no prerequisites for MOD, but we expect the students to have some familiarity with discrete mathematics, first-order logic formulas, context-free grammars, and code fragments in imperative and functional style.
We encourage the students to use the following basic exercises to self-assess their level of knowledge for the above arguments.
Write the formal definitions of injective function and surjective function. Prove that the composition of two injective functions (respectively of two surjective functions) is an injective function (respectively, a surjective function).
Are the formulas “(∀x. P(x)) ⇒ Q” and “∀x. (P(x) ⇒ Q)” equivalent?
Let 7n denote the nth power of 7. Prove by induction that for any natural number n > 1 we have that 3 divides 7n - 1.
Consider the strings (i.e., finite sequences) of symbols {0,1}. Let #0(s) and #1(s) denote the number of occurrences of 0 and 1 in the string s, respectively, and let sn denote the sequence obtained as the concatenation of n instances of the string s. Define context-free grammars that generate each of the following languages
Let us consider the imperative code fragment
while (x!=0 and y!=0) do { x := x-y; y := y-1 }
where x and y are two integer variables. For which initial values of x and y does the execution of the above program terminate?