I.9

f = {(green,sunday), (blue,monday), (red,friday)}
g = {(sunday,red), (monday,blue), (tuesday,green), (wednesday,blue),
     (thursday,green), (friday,green), (saturday,red)}



f o g
-----

x		g(x)	f(g(x))
-------------------------------
sunday		red	friday
monday		blue	monday
tuesday		green	sunday
wednesday	blue	monday
thursday	green	sunday
friday		green	sunday
saturday	red	friday



g o f
-----

x	f(x)	g(f(x))
-----------------------
green	sunday	red
blue	monday	blue
red	friday	green


I.10

f = {((x,y,z),r)|x,y,z,r&{0,1,2}, r=((x*y)+z)%3}

a)

x y z  r
========
0 0 0  0
0 0 1  1
0 0 2  2
0 1 0  0
0 1 1  1
0 1 2  2
0 2 0  0
0 2 1  1
0 2 2  2
1 0 0  0
1 0 1  1
1 0 2  2
1 1 0  1
1 1 1  2
1 1 2  0
1 2 0  2
1 2 1  0
1 2 2  1
2 0 0  0
2 0 1  1
2 0 2  2
2 1 0  2
2 1 1  0
2 1 2  1
2 2 0  1
2 2 1  2
2 2 2  0


b)

f1 = {(0,{((y,z),r)|y,z,r&{0,1,2}, r=(z%3)}),
      (1,{((y,z),r)|y,z,r&{0,1,2}, r=(y+z)%3}),
      (2,{((y,z),r)|y,z,r&{0,1,2}, r=(2*y+z)%3})}


c)

f2 = {((x,y),{(z,r)|z,r&{0,1,2}, r=((x*y)+z)%3})|x,y,&{0,1,2}}


d)

f1(1) = {((y,z),r)|y,z,r&{0,1,2}, r=(y+z)%3}

(f1(1))(1,1) = 2


e)

f2(1,1) = {(z,r)|z,r&{0,1,2}, r=(1+z)%3}



II.1

infix:

(b+sqrt(b*b-4*a*c))/(2*a)



prefix:

/(+(b,sqrt(-(*(b,b),*(*(4,a),c)))),*(2,a))



reverse polish:

b b b * 4 a * c * - sqrt + 2 a * /



II.2

(b+sqrt(b*b-4*a*c))/(2*a)

a)

rewrite rule:

f(a,b,c) = (b+sqrt(b*b-4*a*c))/(2*a)


lambda function:

(lambda a b c|(b+sqrt(b*b-4*a*c))/(2*a))


composition:

/(+(b,sqrt(-(*(b,b),*(*(4,a),c)))),*(2,a))


b)

rewrite rule:

f(2,6,-8) = (6+sqrt(6*6-4*2*(-8)))/(2*2) = (6+sqrt(100))/4 = 4


lambda function:

((((lambda a b c|(b+sqrt(b*b-4*a*c))/(2*a))2)6)-8) =
(((lambda b c|(b+sqrt(b*b-4*2*c))/(2*2))6)-8) =
((lambda c|(6+sqrt(6*6-4*2*c))/(2*2))-8) =
((6+sqrt(6*6-4*2*(-8)))/(2*2)) = (6+sqrt(100))/4 = 4


composition:

/(+(b,sqrt(-(*(b,b),*(4,*(a,c))))),*(2,a))(2,6,-8) =
/(+(6,sqrt(-(*(6,6),*(4,*(2,-8))))),*(2,2)) =
/(+(6,sqrt(100)),*(2,2)) = 4





II.3

[2/y]([3/x](x+y)) ==> [2/y](3+y) ==> 3+2 ==> 5

[2/y,z/x](x+y) ==> z+2

[2/y]([y/x](x+y)) ==> [2/y](y+y) ==> 2+2 ==> 4

[2/y,y/x](x+y) ==> y+2





II.5

<string> := {<alphabet>}+
<nonterminal> := "<"<string>">"
<metasymbol> := ":=" | "<" | ">" | "|" | "{" | "}" | "*" | "+" | """

<BNF-program> := {<production>}*
<production> := <nonterminal> ":=" <BNF-expression> {"|" <BNF-expression>}*
<BNF-expression> :=
	<string> |
	{<nonterminal>}+  |
	""" <metasymbol> """ |
	"{" <BNF-expression> "}"  |
	"{" <BNF-expression> "}+" |
	"{" <BNF-expression> "}*" |
	<BNF-expression><BNF-expression>