第10章修改稿

10.0 0 D E 2 3 D 3 1 (a) x! x (b) x! x (c) x! x (d) x! x (e) x = x (f) x! x 2 1.0.1 11.4 (a) a b a b (b) (a b) ( b c) ( a c) = (a b) ( b c) ( a c) (c) a (a b) (d) a = (b a) = a b (e) a = (a b) = a b (f) (a c) (b c) (a b) (g) a b a b (h) (a b) (c d) ( a c) ( b d) (i) a a b (j) (a b) (b a) (k) ( a " ( a! b) (l) ( a $ b) # ( a " b)! ( a c b c) (m) (a a ) a (n) (a b) ( a b) = b (o) (a b) a = a (p) a=b a=c b=c (q) a! b " a! b = a (r) a ( b a) (s) (t) a a b = a b = a b b if a then a else a 1

(u) (v) (w) (x) (y) (z) if b c then P else Q = if b then if c then P else Q else Q if b c then P else Q = if b then P else if c then P else Q if b then P else if b then Q else R = if b then P else R if if b then c else d then P else Q = if b then if c then P else Q else if d then P else Q if b then if c then P else R else if c then Q else R = if c then if b then P else Q else R if b then if c then P else R else if d then Q else R = if if b then c else d then if b then P else Q else R 3. ( ) T! op 0( a) = ( op1a ) op0 op1 ( a ) op0( b) = ( aop1b ) op0 op1 (a) 4 (b) 16 6 4 (c) if then else if then else (d) (e) P (d) ( P ) = P a b a! b a! b a! b = ( a! b) a! b = ( a! b) a! b (f)!! T T T T T T T!! T! T!! T!!! T T!!!!!! 4 16 2

(i)!! (ii) aop0 b = bop1a op0 op1!! 4. T T T T x 5. (a) T = (b) = (c) a = (d) a b = (e) a b = (f) a b = (g) a b = (h) a b = ( ) (i) a b ( ) (ii) a b ( ) (iii) a b ( ) (iv) a b ( ) (v) if then else a b ( ) 6. BDD BDD T! if then BDD else BDD if x then if a then T else! else if y then if b then T else! else! BDD OBDD BDD BDD if then else if then else OBDD if a then if c then T else! else if b then if c then T else! else! OBDD LBDD BDD = T =! = if then else then else 3

LBDD true = T false =! alice = if b then true else false bob = if a then alice else false LOBDD OBDD LBDD LOBDD RBDD BDD if then else then else BDD ROBDD RLBDD RLOBDD RLOBDD (a) BDD a a! b a! b a! b a = b a! b if a then b else c (b) (c) (d) OBDD OBDD RLOBDD T RLOBDD 7. 8. 9. if a then b else c a a 10. T! =! (a) (b) T!! T =!! = 11. p q p ( ) (a) q (b)q=q 12. (a) (b) (c) (d) 4

(e) (f) (g) (h) (i) (j) (k) (l) (m) 13. (a) (b) (c) (d) (e) 14. Jane Jane 15. 7-9am 4-6pm t d 16. ( ) (a) (b)? 17. ( ) mit = ( ) btt = ( ) blr = ( ) 5

bnk = ( ) bhs = ( ) 18. ( ) P Q R (a) P P P (b) P Q P Q (c) P P (d) P Q R P P Q P Q P R Q Q R (e) P P Q P R Q Q R (f) P Q P Q R 19. X Y X 20. ( ) ( ) 21. ( ), 6

22. 1 (2 + 3) 4 154 23. ( ) e 12e3 12 10 3 (6+6)e(5 2) 12e3 24. ( 1) 1/2 11.4.2 ( 1) 1/2 0 = 0? 25. (a) x (b) x -1 0 +1 x 26. <y< y 0 (x/y = z = x=z y) 27. <y< x/y y = x 28. ( ) + = < 29. 0/0=5 30. ()(())((())()) T T! T! ( T! T x y z ((x)) x x()y () xyz x yz 7

x x y z z y y (( a ) b(( a) b)) x y ( a) b z (( a ) b) (( a ) b( )) x ( a) b y ( ( )) (a) ( ( a! b)! ( a! b)! ( a! b)! ( a! b)) (b) ( a " b)! ( a $ b) # ( a! c " b! c) (c) (d) xy yx (e) (f) T 31. ( 3) T ( 7) T a b = a b = a (a) (b) (c) (d) T (e) T (f) T (g) 32. ( ) Jack, Jill, p p p p p p p p p q p=q (p ) (p ) ------------------------------------------------------------------------------------------------------------------------------------------------------- 10.1 33. (a) (1, 7 3) + 4 (2, 6, 8) (b) nat nat 8

(c) (d) nat nat (nat+1) (nat+1) 34. 7 : null 35. null : A null A : all all 36. A A = A A 37. 2.0 38. ( ) 0 ( ) 1 ( ) ( ) (a) (multibunch) 2 7 5 ( ) (b) (wholebunch) (c) (fuzzybunch) 0 1 39. 40. # ( 3) n#m n m, m: n nat n#m = 0 n 0 n#(m n) = n#m+1 (a) (0,..3)# (0,..3) 3 3 (b) (c) # 41. n m n m m : n nat (a) 0 (b) 0 (c) 1 (d) 1 42. B = 1,3, 5 (a) ( B + B) 9

(b) ( B! 2) (c) ( B! B) (d) 2 ( B ) 43. x : A, B = x : A x : B 16, (,) 16? 44. ( ) (a) 0 = {null} n+1 = {n, ~n} n (b) (c) 0 = {null} i+1 = {i, ~i} i 45. ( ) $ 2 S > $S 46. 2.2, (a), (b), 47. S T, S<T, S=T, S>T 48. 2.3, c!e c e 49. (a) null, nil (b) null ; nil (c) *nil (d) [null] (e) [*null] 50. [0,1,2] [0;1;2]? 51. ( ) S T, S T 10

52., i:0,..#l (a) i Li L (b) L[0;..i] + [x] + L[i+1;..#L] 53. (a) 0 1 1 2 2 3 3 4 4 5 [0;..5] (b) (4 2 [ 3;..3]) 3 (c) ((3;2) [10;..15] 3 [5;..10] [0;..5])3 (d) ([0;..5][3;4])1 (e) (2;2) `j ["abc";"de";"fghi"] (f) #[nat] (g) #[*3] (h) (i) (j) (k) [3;4]:[3*4*int] [3;4]:[3;int] [3,4;5]:[2*int] [(3;4);5]:[2*int] (l) [3;(4,5);6;(7,8,9)] [3;4;(5,6);(7,8)] 54. L, i j L i Lj j Li L -------------------------------------------------------------------------------------------------------------------------------------------------- 10.2 55., P λx: int λy: int λz: int x 0 x 2 y z: int z 2 y z x x, y, z, u, w: int (a) p(x+y)(2!u+w) z (b) p(x+y)(2!u+w) (c) p(x+z)(y+y)(2+z) 56. "! x : D! Px D x Px! 57. (a) ( x : D! Px) = 0 (b) ( x : D! Px) = 1 (c) ( x : D! Px) = 2 58. cat 11

cat [[ 0;1;2];[ nil];[[3]];[4;5]] = [0;1;2;[3];4;5] 59. L M [ 0;2;1 ] [ 0;1;2;2;1;0 ] [ 0;2;1 ] [ 0;1;2;3 ] 60. L M (a) ( ) (b) (c) M 61. n L 62. x t y (a) (b) (c) (i) (ii) (iii) 63. ( ) (i) (ii) (iii), (iv) (v),, (vi) (vii) (viii) (ix) (x) (a), (b) 9, 10 64. ( ) ( ), αf (f ) 65. p holds k p k p unlocks d 12

k d p opens d p d (a) (b) (c) 66. i j P Q, ( $ i " Pi)! (# i " Qi) = (# i, j " Pi! Qj) 67.,? 68. 69. 70. 13 6 drink drive 6 71. (a) (b) 10 (c) 10 (d) 1000 (e) (f) 72. (a) n m ( 1 m) (b) g a b (c) m a b (d) p (e) n m (f) n p (g) (h) (i) L M x ( ) (j) L i ( ) j ( ) (k) a b ( ) A B 13

(l) (m) (n) (o) (p) (q) P L ( ) L 10 L L ( ) L m L M 73. [1;3;4;5;5;6;4;4;3] L 74. 75. ( ) 76. ( ) 77. 78. (a) (0,..n) m (b) (0,..n) m (c) "( 0,.. n )! b (d) "( 0,.. n )! b 79. nil x = x (S ; T) x = S T x (a) 2 3 (b) 2 3 80. ( ) 81. ( ) 14

82. ( ) rus = λf : null bool f f (a) rus rus = rus rus (b) (c) f : Δ f 83. 84. ( / ) " s : [*char] # s 0" = s : [*char] # s 0 85. f g nat nat f g f = g? f f g = g? 86. #[n*t] [n*t] 87. (a) i Li m = (MIN L) m (b) i Li m = (MAX L) m 88. ( ) ( L) > n #L i : Δ L L i > n 89. f : A B p : B bool (a) (b) b : f A pb = a : A pfa b : f A pb = a : A pfa 90. 3 λ v b, v b ( ) λ v b = λ w ( b v w) (λ v b)x = ( b v x) a b a > b b > 12 T > b = b 15

(a) (b) (c) a > b > c = a b > c a > b if b a v : D λ n n: nat > n+1 λ n : nat n+1 3 (λ n n: nat > n+1)3 = 3 : nat > 3+1 = T > 4 = 4 3, (λ n n: nat > n+1)( 3) = 3 : nat > 3+1 = > 2 91. R x y Rxy x Rxx x, y, z Rxy Ryz Rxz u x x = u Rxu 92. n R 0,.. n R : (0,.. n)! (0,.. n)! bool x x Rxy x y Rxy Ryz x z x y 93. x, y, z R x y R y z R x z R R Q (R Q ) -------------------------------------------------------------------------------------------------------------------------------------------------------- 10.3 94. S σ S.T ( T ) 16

95. x (a) x 0 x' '2 = x (b) x' 0 x = 0 (c) (x 0 x' = 0) (d) (x 0 x' = 0) 96. a,b c a b b c a c S S S.S 97. (x y ) (a) x:=y+1. y' >x' (b) x:=x+1. y' >x x' >x (c) x:=y+1. y' =2x (d) x:=1. x 1 x y' =2x (e) x:=y. x 1 y y' =x y (f) (g) (h) (i) (j) (k) x:=1. ok x:=1. y:=2 x:=1. P where P = y:=2 x:=1. y:=2. x:=x+y x:=1. if y>x then x:=x+1 else x:=y x:=1. x' >x. x' =x+1 98. (a) x:=x = ok (b) x:=e. x:=f x = x:=f e (c) if b then x:=e else x:=f = x:= if b then e else f 99. (a) R. if b then P else Q = if b then (R. P) else (R.Q) (b) if b then P Q else R S = (if b then P else R) (if b then Q else S) (c) if b then (P. Q) else (R. S) = if b then P else R. if b then Q else S 100. (a) P Q R R (b) P Q R Q P R 101. S A. A. S. Z. Z S A. S. Z 17

102. ( R! R. S) = ( R!". S)!. = ( R!")! = T 103. P Q (a) (P. Q) P. Q (b) (c) P. Q (P. Q) P. Q = (P. Q) 104. L L [ 6 ; 3 ; 5 ; 5 ; 7 ] [ 6 ; 6 ; 3 ; 3 ; 5 ; 5 ; 5 ; 5 ; 7 ; 7 ] 105. P Q C C ' P. Q P C '. C Q 106. P Q C C' C (P. Q) C P. Q C (P.Q) C P. Q (P.Q) C' P. Q C' ( P. Q)! C' P. Q! C' P. C Q P C'. Q P. Q P C'. C Q 107. S C C ' S C ' (S. C) S 108 A if b then C else D E if b then F else G A E if b then C F else D G A B.C D E.F, A D B E. C F A B C D A C B D 2 109. x y y = x x : = x + 1. y : = y + 2 " x! 1 110 x 18

(a) (b) x := x+1 x' > 5 A x := x+1 A A (a) 111 L (a) x'+y' >8 x:=1 (b) x' =1 x:=1 (c) x' =2 x:=1 (d) x' =y y:=1 (e) x' y' x:=y+z (f) y'+z' 0 x:=y+z (g) x' 1 x' 5 x:=x+1 (h) x' < y' x Lx < y' x:=1 (i) y Ly<x' x:=y+1 (j) L' 3 = 4 L:=i 4 L (k) x' =a if a>b then x:=a else ok (l) x' =y y' =x z:=x. x:=y. y:=z (m) ax' 2 +bx'+c=0 x:=ax+b. x:= x/a (n) f ' = n'! n:=n+1. f:=f n,! (o) 7 c' <28 odd c' a:=b 1. b:=a+3. c:=a+b (p) s' = L[0;..i' ] s:=s+li. i:=i+1 112 x 0 (a) x:=x+1 (b) x:=abs(x+1) (c) x:=x 2 113 x 0 0 (a) x:=x+1 (b) x:=abs(x+1) (c) x:=x 2 114. (a) P S C C! P S (b) P S C C '! P S 115. ( ) P Q S ( P Q) P (a) S. Q (b) Q. S 19

116. a b (a) b:=a b. b:=a b (b) a:=a+b. b:=a b. a:=a b (c) c : = a! b! c. b : = a! b! c. a : = a! b! c. c : = a + b + c 117. x y (a) x:=x=y. x:=x=y (b) x:=x y. y:= x y. x:=x y 118. x (a) x' =0 if x=0 then ok else (x:=x 1. x' =0) (b) P if x=0 then ok else (x:=x 1. t:=t+1. P) P = x' =0 if x 0 then t' =t+x else t' = 119. x (a) x' =1 if x=1 then ok else (x:=div x 2. x' =1) (b) R if x=1 then ok else (x:=div x 2. t:=t+1. R) R x' =1 if x 1 then t' t+log x else t' = 120. s n n P! if n = 0 then ok else ( n : = n! 1. s : = s + 2! n. t : = t + 1. P) n P = s' = s + 2 " n# ( n " 1) / 2 " 1! n' = 0! t' = t + n 121. P = x < 0 x' =1 t' = P if x = 0 then ok else (x := x 1. t := t +1. P) 122. ( ) n f f := n! if n=0 then f :=1 else (n:=n 1. f:=n!. n:=n+1. f:=f n) n! = 1 2 3... n 123. n m P n:=n+1. if n=10 then ok else (m:=m 1. P) P = m := m+n 9. n:=10 124. x n P x = x' 2 n ' n:=0. P P if even x then (x:=div x 2. n:=n+1. P) else ok 20

125. ( ) s n P s' = n 2 s:= n. P P if n=0 then ok else (n:=n 1. s:=s+n+n. P) 126. a b x u v (a) (b) P = u 0 v 0 x = u!a v! b x' =0 P if x > 0 then (x:=x a. u:=u 1. P) else if x < 0 then (x:=x+b. v:=v 1. P) else ok (a) 127. i P (a) P if even i then i:=i/2 else i:=i+1. (b) if i=1 then ok else P P if even i then i:=i/2 else i:=i 3. if i=0 then ok else P 128. f i j t' t + f i j if i=0 j=0 then ok else if i=0 then (i:=j j. j:=j 1. t:=t+1. t' t + f i j ) else (i:=i 1. t:=t+1. t' t + f i j ) 129. P a b 2 3 (a) (b) (c) x P Q P a:=0. b:=0. Q Q if x: 2 nat then (x:=x/2. a:=a+1. Q) else if x: 3 nat then (x:=x/3. b:=b+1. Q) else ok (b) 130. R S 0 131. ( ) R x := x +1. R ( ) 2 x 21

132. P = t' =5 P t := t +1. P 5 133. n r P if n=1 then r := 0 else (n := div n 2. P. r :=r+1) (a) (b) div + 1 ( ) P P P 134. ( ) L L (a) n: 0,..#L L' n = L [0;..n] (b) n: 0,..#L L' n = L [0;..n+1] 135. ( ) 136. ( ) 137. ( 2) n n 2 n' = mod n 2 if n < 2 then ok else (n := n 2. n' =mod n 2) 138. ( 2) n p n 2 n' = mod n 2 if n<2 then ok else (even n' = even n. n' =mod n 2) (a) (b) even n' = even n p:=2. even p even p' even n' = even n even p even p' even n' = even n n:=n p. p:=p+p. if n<p then ok else even p even p' even n' = even n 139. t (a) x 0 t' t+x (b) n: nat t' t+n (c) f : int nat t' t+f x 140. ( ) 22

141. ( ) 142. ( ) 143. ( ) L L0 L1 + L2 L3 + L4... 144. ( ) a+b a b 145. ( ) t t t ( t ) 146. ( ) n: nat, c: [n*rat] y: rat c x ( n 1 ) y' = i : 0,..n. ci x i 147. ( ) n: nat M : [*[*nat] ] M n n=4 M' = [ [0]; [0; 1]; [0; 2; 4]; [0; 3; 6; 9] ] 148. ( ) n: nat, P : [*[*nat] ] P n n=4 P' = [ [1]; [1; 1]; [1; 2; 1]; [1; 3; 3; 1] ] 1 149. (2 ) x y y' =2 x 150. 2 151. ( ) x z y z' =x y, 23

152. ( ) 153. ( ) 154. ( ) 155. 154 (a) (b) (c) 1 (d) 156. ( ) 157. ( ) 158. ( ) 159. ( ) 160. ( ) subject pattern pattern subject h (a) 2 (b) 161. ( ) L n log n L i Li=i 162. ( ) 163. ( ) n 0,..n+1 24

164. ( ) ( ) 165. ( ) 166. ( ) ( ) 167. [ a ; b] [ c;d] = a < c b<d n:nat L:[n*[int;int] ], L j:0,..#l, i. Li Lj n log n 168. n L L ( 0,..# L) = 0,..# L L L 169. (n 2 ) n 2 n 170. (n! log n ) n! log n n 171. ( ) 172. ( ) ( ) 173. ( ) m 0,..n m 0,..n 174. ( ) 0,..n,, 0,..n 175. ( ) P, 0,..#P,, PP' =[0;..#P] 25

176. ( ) 0,..#L ( ),, L'L' = L' 177. ( ) L, L0 L1 L(#L 2) L(#L 1) i : 1,..#L 1 L(i 1) Li L(i+1), L 178. ( ) n p q q n/p < q+1, log n n p, (div, mod, floor, ceil,...) 179. ( ) 178, (, ) 180. ( 2 ) p 2 b 2 b p < 2 b+1, log p p 2 181. ( ) n s s 2 n < (s+1) 2 (a) (b), log n n, log n n, ( ) 182. ( ), ( ) 183. ( ) c,, a 2 +b 2 = c 2 a b, c ( 1 2 a b, b a ) 184. ( ) L = [ [ 3; 5]; 2; [5;[7]; [nil] ] ] L' = [3; 5; 2; 5; 7] Li : int 185. ( ) 26

186. ( ), (a) ( ) (b) 187. ( ), (c) ( ) (d) 188. ( ) (a), (b), 189. ( ) ( ) (a) (b) 190. ( ) 1 191. ( ), T ( ) 192. ( ) 193. ( ) ( ) 194. 0, 1, 2 (a) ( ) (b) 0, 1, 2 ( ) 195. L M Li Mj i:0,..#l j:0,..#m 196. ( ) L i j L[0;..i] = L[j ;..#L] 27

197. ( ) i i+1/2 198. ( ) ( ) 199. ( ) 200. [13;14;15;14;15;13] 14 13 15 14 201. ( ) L R L 202. ( ) 1 203. ( ) 204. ( ) 1 205. 206. s q s 2 a b c d s p 207. n s p n ( ) s p 208. ( ) R : (0,..n) (0,..n) bool n (a) ( ) (b) ( ) 209. ( ) S, S h ( ) h ( ) 28

210. ( ) i j i j i j, i j i j i j ( ) 211. ( 91 ) i (a) (b) M = if i>100 then i:=i 10 else i:=91 M if i>100 then i:=i 10 else (i:=i+11. M. M) (a) M 212. 3 n 0 n! 1 A n A B C (a) MoveDisk from to from to A B (b) MoveDisk 1 (c) (d) (e) (f) 1 1 1 213. ( ) ack ack 0 0 = 2 ack 1 0 = 0 ack (m+2) 0 = 1 ack 0 (n+1) = ack 0 n + 1 ack (m+1) (n+1) = ack m (ack (m+1) n) (a) n:=ack m n (b) ack (c) 214. f n:=f m n f (a) f 0 n = n +2 29

f 1 0 = 0 f (m+2) 0 = 1 f (m+1) (n+1) = f m (f(m+1) n) (b) f 0 n = n! 2 f (m+1) 0 = 1 f (m+1) (n+1) = f m (f(m+1) n) (c) f 0 n = n +1 f 1 0 = 2 f 2 0 = 0 f (m+3) 0 = 1 f (m+1) (n+1) = f m (f(m+1) n) 215. n P if n 2 then (n:=n 2. P. n:=n+1. P. n:=n+1) else ok 216. ( ) n n' =1 if n=1 then ok else if even n then (n:=n/2. n' =1) else (n:=3n+1. n' =1) 217. ( ) f n f 0 = 0 f 1 = 1 f (n+2) = f n + f (n+1) log n f n 301 218. ( ) a b, a b f 0 = 0 f 1 = 1 f (n+2) = a fn + b f (n+1) ( 1 1 ) k, n: 0,..k f n f (k n) 219. ( ) 220. ( ), (a) (b) 30

221. ( z ) z 222. ( ) 223. ( ) b>1 0,..b b=10 [9 ; 2 ; 7] 729 (a) (b) (c) (d) (e) 224. ( ) 225. ( ), 226. ( ) 227. 228. ( ) (a) ( ) (b) 229. ( ) 230. ( ) 231. ( ) f : int int x 0 = 0 x n +1 = f (x n ) 31

p: nat+1 n: nat x n = x n +p n:nat x n = x n+p p f 232. ( ) n n (a) n n=3, [[3]; [1;2]; [2;1]; [1;1;1]] (b) n n=3, [[3] ; [1;2] ; [1;1;1]] (c) n n=3, [[1;1;1]; [1;2]; [2;1]; [3]] (d) n n=3, [[1;1;1] ; [1;2] ; [3]] 233. ( ) T 234. (P ) S P P P S i: 1,..#P P(i 1) < P i S (P (i 1)) S P 235. (J ) n n J 2n m:0,..n m m (a) n ( ) n J (b) n J 236. ( J ) n n J 2n 1 0 m:1,..n m m (a) n ( ) n J (b) n J 237. ( ) 238. ( ) 239. ( ) 32

240. ( ) A B 241. ( ) A B A B 242. ( ) 243. 244. 245. ( ) 25621 2547 25 246. ( ) n s f ( ) A, D:[n*rat]( ) i: s Ai Di f s n i Ai Dj f n (a) A (b) D 247. ( ) 248. ( ) t t ( ) 249. L L swap (a) swap = λi, j: 0,..#L L:=i Lj j Li L ( ) 33

(b) (c) L ( ) r r ( r<0 r ) #L ( ) p L p 250. ( ) L L 251. n p nat n! 2 " p': 2 2 # n $ p' < n 2 252. ( ) H H ( ) 253. ( ) n n ( ) 254. (,, ) (a) (b) P F P n Fn P[0;..n+1] F A:: (i:=0. F:=[#P*0]. j:= 1. B:: if j #P then ok else ( C :: if Pi=Pj then i:=i+1 else if i=0 then ok else (i:=f (i 1). C ). F := j i F. j := j+1. B ) ) A, B C A S ( ) P ( ) F ( (a) ) P S D:: (m:=0. n:=0. E:: if m=#p then h:=n #P else F :: if n=#s then h:= else if Pm=Sn then (m:=m+1. n:=n+1. E) else G :: if m=0 then (n:=n+1. F) else (m:=f (m 1). G) ) 34

D, E, F G D -------------------------------------------------------------------------------------------------------------------------------------------------------- 10.4 255. ( ) x:=e e x x:=nat x 256. var x: T P = x: undefined x' : T P var x:int ok 257. var x: T P = x: T x' : T P 258. var x: T := e = var x: T x:=e 5.5.0 259. var x : T : = e " P = # x, x' : T " x = e! P var x : T : = e! P = " x; : T! P x e 260. var x: nat x:= 1 ( ) 261. ( ) x P = x' =0 P var y: nat y:=0. P. x:=y y P P y 262. x, y, z frame frame x T x 263. x:=i. i:=a i. A i :=x i A i nat i A 35

(a) (b) (c) x i A i Ai A x (a) (a) 264. (A(Ai):=0. Ai:=1. i:=2) A' i' =1 265. x y while x = y = 0 do if y > 0 then y : = y! 1 else ( x : = x! 1. var n : nat! y : = n) 266. W! while b do P W! if b then ( P. W ) else ok R! R! P. if b then ok else R ( R! repeat P until b ) " ( W! while b do P )! ( R! PW. ) " ( W! ifb then ok else R ) repeat P until b 267. ( ) Dijkstra if b P [] c Q fi b c P Q b c b c P Q ( ) b c (a) (b) 268. for 1 269. for j, n, k m i for i:=nil do P = ok for i:=j do P = ( P i j ) for i:=n;..k ; k;..m do P = for i:=n;..k do P. for i:=k;..m do P (a) for i:=0;..n do n:=n+1 n (b) for 270. ( ) ( ) ( ) L m (a) var e: nat := 0 36

(b) for i:=0;..#l do if m = Li then e:=e+1 else if i = 2 e then (m:=li. e:=e+1) else ok var s: nat := 0 for i:=0;..#l do if m = Li then ok else if i = 2 s then m:=li else s:=s+1 271. P result e x' = (P result e) = P. x' = e x' = (P result e) = P x' = e' 272. a b P P = λx, y : rat if x=0 then a:=x else (a:=x y. a:=a y) (a) P a(1/b) a' =b' (b) (eager) (lazy) 273. (Call-by-value-result) 274. (λx: int a:=x. b:=x) (a+1) x ( (call-by-name)) 275. wait until w = t:= max t w t w (a) wait until w if t w then ok else (t:=t+1. wait until w) (b) t w wait until w 276. wait w w w (a) (b) 37

277. P Q 278. T=1! =0 (i) 0 1 a b ( ) + -! (ii) (a) (b) (c) (d) (e) (f) (g) 0 1 a b ( ) max min a a! b a! b a! b a! b a = b a! b 279. (a) n 2! n nat + 1 n 2 6 (b) n n ( 5 / 6)! 1/ 6 nat 5 280. n 2! n R R! t : = t +1. if rand 2 then ok else R 281. 1 13 14 14 7 282. 283. n (a) 2/3 1/3 (b) 1/4 1/2 1/4 (c) 1/2 1/4 1/4 284. 38

1/2 1/2 ------------------------------------------------------------------------------------------------------------------------------------------ 10.5 285. 1: nat 286. ( ) " f : nat # nat # nat! $ g : nat # nat! " n : nat! fn = g 287. : n:nat Pn = n:nat m:0,..n Pm 288. n 8m+1 m 289. ( ) 290. 1 n n+1, p 0, p 1,..., p n n p 0, p 1,..., p n 1 p 1 n p 1, p 2,..., p n p 1 n+1 291. nat 0,1, nat + nat : nat (a) (b) (a) nat 292. nat 293. nat = 0,..! 294. bad ( n: nat n: bad) : bad (a) (b) ( n: nat n: B) : B bad : B bad = n: nat n: bad 39

295. nat (a) i, j j 0 2 1/2 = i/j 2 (b) n ( i: 0,..n 1) = n (c) n ( i: 0,..n i) = n (n 1) / 2 (d) n ( i: 0,..n i 3 ) = ( i: 0,..n i) 2 (e) n ( i: 0,..n 2 i ) = 2 n -1 i n (f) % n $ (! i : 0,.. n $ i " 2 ) = ( n # 2) " 2 + 2 (g) n ( i: 0,..n ( 2) i ) = (1 ( 2) n ) / 3 (h) n n 10 2 n > n 3 (i) 3 $ n # n " 4! 3 > n (j) 3 2 % n $ n # 3 " 2! n > 3! n + 3! n (k) a, d q, r d 0 r<d a = q! d + r i b a (l) & a, b # a % b $ (! i : a,.. b # 3 ) = (3 " 3 ) / 2 296. nat (a) # n : nat " 0! n < n + 1 (b) $ m : nat " # n : nat " m! n < n + 1 297. nat 0, nat + 1: nat 0, B + 1: B! nat : B nat = 0, nat + 1 B = 0, B + 1! nat : B 298. nat nat = 0, nat + 1 B = 0, B + 1! nat : B 0, nat + 1: nat 0, B + 1: B! nat : B 299. ( ) 300. f i j f i f j (a) f f i < f j i < j 40

(b) (c) f : int int f f i f ( i+1) f : int int n ffn < f (n+1) f n n f n f n f n n 301. f 0 = 0 f 1 = 1 f (n+2) = f n + f (n+1) (a) f (gcd n m) = gcd (f n)(f m) gcd (b) f n f (n+2) = f (n+1) 2 ( 1) n (c) (d) f (n+m+1) = f n f m + f (n+1) f (m+1) f (n+m+2) = f n f (m+1) + f (n+1) f m + f (n+1) f (m+1) (e) f (2!n+1) = f n 2 + f (n+1) 2 (f) f (2!n+2) = 2 f n f (n+1) + f (n+1) 2 302. R R : nat! nat! bool # i, j " Rij! Ri( j + 1) " i!# j! Rij = # j! " i! Rij 303. (a) B = 0, 2!B + 1 (b) B = 2, B B 304. P = 1, x, P, P+P, P P P 2 x 2 1 : P 305. this 2, 2 this: this 2, 2 B : B this : B that 2, that that : that 2, B B : B that : B this=that 306. 2 2 int 307. n ply=n, ply+ply ply i 41

(a) ply i ( ) (b) ply i (c) ply? (d) ply 308. (a) M = [*int], [*M] (b) T = [nil], [T; int; T] (c) A = bool, rat, char, [*A] 309. A B A B x : A B = x :A x : B (a) Q = nat (Q+3) (b) D = 0, (D+1) (D 1) (c) E = nat ( E +1) F = 0, ( nat F ) + 1 310. (a) P = n: nat n=0 P=null n: P+1 (b) Q = x: xnat x=0 Q=null x: Q+1 311. even = 0 odd+1 odd = even + 1 (a) (b) even odd 312. (a) E E, E +1 = nat (b) B, B + 1 = nat! E : B E 313. 0, 1 few : few (a) (b) few (c) (d) 314. strange = n: nat m: strange m+1: n nat 42

315. truer T, ; truer; truer: truer T, ; B; B: B truer: B truer 316. S * S S * * S 317. T [nil], [T], list + list : list [nil], [T], L+L : L list : L list = [*T] 318. ( ) 319. ( ) <exp> ::= <exp> + <exp> <exp> <exp> 0 1 exp = exp; "+"; exp, exp; " "; exp, "0", "1" (a) (b) (c) a b (d) a b 320. 6.1 zap zap = if x=0 then y:=0 else (x:=x 1. t:= t+1. zap) (a) zap x 0 x' = y' = 0 t' = t+x (b) x 0 x' = y' = 0 t' = t+x zap (c) (d) (e) zap zap 6.1 321 (a) skip = if i 0 then (i:=i 1. skip. i:=i+1) else ok (b) inc = ok (i:= i+1. inc) 43

(c) sqr = if i=0 then ok else (s:=s + 2!i 1. i:=i 1. sqr) (d) fac = if i=0 then f:=1 else (i:=i 1. fac. i:=i+1. f :=f i) (e) chs = if a=b then c:=1 else (a:=a 1. chs. a:=a+1. c:=c a / (a(b)) 322. (a) walk = if i 0 then (i:=i 2. walk. i:=i+1. walk. i:=i+1) else ok (b) crawl = if i 0 then (i:=i 1. crawl. i:=i+2. crawl. i:=i 1) else ok (c) run = if even i then i:=i/2 else i:=i+1. if i=1 then ok else run 323. (a) t' = (b) t := 324. x P Q P x' 0. Q Q if x=0 then ok else (x:=x 1. Q) x 0 325. x (a) (b) S S if x=0 then ok else if x>0 then (x:=x 1. S) else (x' 0. S) x' 0 t' t 326. R R = ok! ( R. S) R = ok! ( S. R) R = ok! S! ( R. R) 327. while 328. $ %,% '#( t' " t! ( if b then ( P. t : = t + inc. W ) else ok )! W ) # " $, $ '!( while b do P! W ) while 44

$ %,% '#( t' " t! ( if b then ( P. t : = t + inc. W ) else ok )! W ) = "#,# '!( while b do P! W ) 329. repeat P until b P b T! repeat P until b 330. 329 (a) repeat P until b = P. t : = t + inc. while b do P (b) while b do P = if b then repeat P until b else ok (c) ( σ, σ' (R=repeat P until b)) ( σ, σ' (W = while b do P)) = ( σ, σ' (R=P. t : = t + inc.w)) ( σ, σ' (W = if b then ok else R)) 331. P : nat bool (a) FIRST FIRST m : nat Pm Pm m (b) n:=first m: nat Pm n:=0. while Pn do n:=n+1 332. b c W = if b then (P. W) else ok X = if b c then (P. X) else ok (a) W. X = X (b) W X W. X = X 333. x P = P. x:=x 2 (a) P 7 (b) T (c) t' t (d) x 334. while b do P if b then (P. while b do P) else ok while b do P σ, σ' (if b then (P. W) else ok W) σ, σ' (while b do P W) while b do P = if b then (P. while b do P) else ok σ, σ' (W = if b then (P. W) else ok ) σ, σ' (while b do P W) 335. while b do P while b do P = if b then (P. while b do P) else ok 45

σ, σ' (W = if b then (P. W) else ok ) σ, σ' (while b do P W) if b then (P. while b do P) else ok while b do P σ, σ' (if b then (P. W) else ok W) σ, σ' (while b do P W) ----------------------------------------------------------------------------------------------------------------------------------------------------- 10.6 336. (a) (b) (c) 337. pop empty = empty top empty = 0 338. stack = [nil], [stack; X] push = λs: stack λx: X [s; x] pop = λs: stack s 0 top = λs: stack s 1 339. ( ) 7.1.3 340 ( ) 7.0 341. ( ) end slip end: slip slip = [T; slip] T 342. 7.1.1 7.1.0 343. 46

344. (a) (b) (c) (d) (e) push`a push `B push `C push` D push` E print top pop BDECA BCDEA CADEB ABECD ABCDE 345. ( ) t `x, `(, `), `[, `] t 346. ( ) limit:nat full( empty) isfull( isempty) (a) (b) (c) limit 0 347. ( ) limitq:nat fullq( emptyq) isfullq( isemptyq) (a) (b) (c) limit 0 348. (a) (b) (c) (d) (e) push`a push `B push `C push` D push` E print front leave BDECA BCDEA CADEB ABECD ABCDE 349. 350. ( ) 47

( ) 351. ( ) 3 value( X) set( X ) reset( ) value' =x set x value' =value set x. reset reset. reset = reset 352. mkempty extend x x swap i j i j length item i i (a) (b) 353. ( ) 354. ( ) 355. (a) 0 n 2n+1 2n+2 (b) (b) k k 356. ( ) ( ) 357. ( ) (a) (b) heapgraft graft 48

358. ( ) 359. ( ) (a) (b) (c) (d) (e) (f) (g) 360. 361. ( ) (a) (b) (c) (d) [...; 4 ; 7 ; 1 ; 0 ; 3 ; 8 ; 9 ; 2 ; 5 ;...] insert ( ) erase item forward back 362. ( ) E E = "x", "if" ; E ; "then" ; E ; "else" ; E E 363. zero, increase, inquire u: bool v: nat zero = v:=0 increase = v:=v+1 inquire = u:=even v v w: bool (a) w = even v (b) T 49

(c) ( w v ) 364. set, flip, ask u: bool v: nat set = v:= T flip = v:= v ask = u:= v (a) v = even w, w: nat v (b) (w=0 v) ( w=1 v), w: nat v, (c) (v w=0) ( v w=1), w: nat v, 365. a b c a b c seta = a := T reseta = a :=! flipa = a : = a setb = b := T resetb = b :=! flipb = b : = b and = c : = a! b or = c : = a! b 0! T (a) (b) seta (c) flipa (d) and 366. 270(a) 270(b) 367. a b c a b c (a) (b) (a) 368. b x y done = b : = x = y = 0 step = if y > 0 then y : = y! 1else ( x : = x! 1. var n : nat! y : = n) 50

z x y 265 369. n p m m := n p := prime m prime prime m m 370. ( ) ( ) n ( ) n ( ) (a) (b) (c) 371. n Q :[ n * X ] p : nat makemptyq = p := 0 isemptyq = p = 0 isfullq = p = n joinx = Qp : = x. p : = p + 1 leave = for i := 1;.. p do Q ( i! 1) : = Qi. p : = p! 1 front = Q0 p! 1 372. 1 n 2! n 2! n + 1 x : X s :[* X ] p : nat + 1 gohome = p := 1 goleft = p : = 2! p goright = p : = 2! p + 1 51

goup = p : = div p 2 put = s : = p! x s get = x : = s p 0 0 1 2 373. ( ) A:[*[*rat]] 0 0 A i j = x 0 [i ; j ; x] (a) A:= [100*[100*0]] (b) i:= A i j (c) A:= (i; j) x A 374. i j nat initialize = i ' = 0! j' < 3 step = if j > 0 then ( i : = i + 1. j : = j! 1) else ok i j initialize i 0 j 3 step i 0 1 2 j (a) b j initialize i '= 0 step if b! i < 2 then i' = i + 1else ok initialize b T i! i step b i i < 2 i 3 i b i 0 0 1 2 (b) b = ( j > 0) initialize i + j = k! step k : 0,1, 2 --------------------------------------------------------------------------------------------------------------------------------------------- 10.7 375. x y (a) x:=x+1 if x=0 then y:=1 else ok (b) if x > 0 then y : = x! 1else ok if x = 0 then x : = y + 1 else ok 376. x:=3. y:=4 = x:=3 y:=4 P.Q P Q 52

t:=t+1. t:=t+2 = t:=t+3 P Q P Q t:=t+1 t:=t+2 = t:=t+2 377. P Q P Q P Q v w P v w Q = ( P. v' = v)! ( Q. w' = w) (a) P v w Q (b) P Q P v w Q 378. P Q P Q Q P Q (a) (b) (c) (d) x y z x : = z y : = z (e) x y z x : = y y : = x (f) x y z x : = y x : = z (g) x y z x : = y x : = z if x = y tehn x : = z else if x = z then x : = y else( x : = y x : = z (h) x y z x : = x! z y : = y! z x : = x! z y : = y! z (i) w : 0,.. 4 z : 0, 1 w : = 2! max( div w ) z + max(mod w )( 1! z) P 53

w : = 2! max( div w )( 1! z) + max(mod w 2 ) z 379. P Q 378 380. P Q 378 P Q (a) (b) 381. p 0,.. n p 1 n p p 382. 134 log n n 383. ( ) p : [n*bool]:=[ ; ; (n 2)*T] (a) (b) for i:=2;..ceil(n 1/2 ) do if p i then for j:=i;..ceil(n/i) do p:=(j i) p else ok n 384. ------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.8 385. a b x y t 1 ( x : = 2. x : = x + y. x : = x + y) ( y : = 3. y : = x + y) 386. a b 54

loop = if b then loop else ok b : =! loop 387. (a) (b) 388. thermomete r control thermostat burner temperature desired, flame, gas, T! spark T!!! 3 20 1 389. alloc GrowSlow! if t = 2! x then ( alloc x : = t) else t : = t +1. GrowSlow 2! x x x 390. (a) (b) 391. 7.2 55

392. ( ) ( ) ( ) 5 5 2 393. ( ) 394. read x 9.1 395. 396. 397. L *(L(0,..#L) 398. (T ) L : [*(`a,`b,`c)] T i, j, k 0 i < j < k #L L[i;..j] = L[j;..k] T ( T ) 399. ( ) 400. 5.5.0 result 401. ( ) (a) 0 1 0 1 ( ) (b) (a) 56

402. ( ) n 2 2! n 2 n n n 403. ( ) ( ) 404. 405. twos = c!2. t:=t+1. twos (a) (b) (c) 406. A = if c d then c? d? else if c then c? else if d then d? else if T c r c < T d r d then (t:= T c r c + 1. c?) else if T d r d < T c r c then (t:= T d r d + 1. d?) else (t:= T c r c + 1. c? d?) B = if c d then c? d? else if c then c? else if d then d? else (t:=t+1. B) A=B 407. ( ) W c (a) W = t:= max t (T r+1). c? W if?c then r:= r+1 else (t:= t+1. W) (b) W 408. 407 W c W! if t! deadline then if c then c? else ( t : = t + 1. W ) else alarm W 409. partmerge : nat nat bool 57

partmerge 0 0 partmerge (m+1) 0 = partmerge m 0 M c (w c +m) = M a (r a +m) partmerge 0 (n+1) = partmerge 0 n M c (w c +n) = M b (r b +n) partmerge (m+1) (n+1) = partmerge m (n+1) M c (w c +m+n+1) = M a (r a +m) partmerge (m+1) n M c (w c +m+n+1) = M b (r b +n) partmerge m n c m+n a m b n merge merge = (a?. c! a) (b?. c!b). merge merge = ( m n partmerge m n) ( n m partmerge m n) 410. c d 411. ( ) c d e ( ) (a) (b) T e w e = max t (min (T c r c ) (T d r d )+1) m, n T e (w e +m+n+1) max (max (T c (r c +m)) (T d (r d +n))) (T e (w e +m+n))+1 412. ( ) 413. 9.1.6 ( ) 414. ( ) a! 0 a choose d b c c?. b! c 58

chan a, b, c a! 0 choose (c?. b! c) (a) choose = (a?. c! 0. d! 0) (b?. c! 1. d! 1) choose a c d 0 b c d 1 (b) choose = (a?. c! 0. d! 0) (b?. c! 1. d! 1) (a) choose a c d 0 b c d 1 choose ( ) 415 ( ) a a 0 +a 1!x+a 2! x 2 +a 3! x 3... a 0, a 1, a 2, a 3..., b b 0 +b 1!x+b 2! x 2 +b 3! x 3... b 0, b 1, b 2, b 3..., c 0 +c 1!x+c 2!x 2 +c 3! x 3... c 0, c 1, c 2, c 3... c 416. ( ) 417. ( ) zzzz 418. ( ) P N p Cp Q P = N P.. C P. P Q = N Q. C Q. Q (P Q) P Q 419. ( ) (a) ( ) 59

(b) (c) -------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------- 60