Homework Sample Solutions Page 192 #1: (a) travel(X) :- young(X), enterprising(X). this question is a bit vague - what does "travel(X)" mean? (b) like(X,Y) :- ( book(Y), well-written(Y), haspictures(Y) ); ( movie(Y), endshappy(Y) ). you can also break this up into two clauses. Page 192 #3: (a) meat(beef). meat(ham). vegetable(carrots). vegetable(lettuce). vegetable(spinach). (b) There are many ways to do this here are two: eat(jim,X) :- vegetable(X). or more interestingly, vegetarian(jim). eat(X,Y) :- vegetarian(X), not(meat(Y)). Page 193 #9: Goal abc(a,b) matches with head of first clause, which is abc(X,Y), giving the solution X=a, Y=b. This entails showing cde(a,U), efg(V,U), hij(V,b). cde(a,U) matches cde(a,b) with U=b then efg(V,b) (since U=b) matches efg(d,b) with V=d then hij(d,b) fails to match anything, so this branch FAILS since hij(d,b) and efg(V,b) do not match with any other clauses, we go back and try to match cde(a,U) with another clause: cde(a,U) matches cde(a,c) with U=c then efg(V,c) matches efg(h,c) with V=h then hij(h,b) mathces with hij(h,b) -- and we're DONE. The machine returns "yes". Page 132 #9: Prove n^2 >= 2n+3 for n>=3: By induction: Base Case: for n=3, 3^2 = 9 >= 2*3+3 = 9 Indeed! Inductive Case: Assume n^2 >= 2n+3 for n>=3 (inductive hypothesis) Need: (n+1)^2 >= 2(n+1)+3 for n>=3. multiplying this out, it becomes n^2 + 2n + 1 >= (2n + 3) + 2 by the inductive hypothesis, n^2 and (2n+3) can be canceled from either side of the inequality, so now we need to show: 2n+1 >= 2, Subtract 1 then divide by 2 on either side and we get n >= 1/2, which holds since n>=3. Page 132 #9: Prove that every well-formed formula of propositional logic without negation has an odd (2n+1 for some n) number of symbols: Base Case: a propositional letter 'p' by itself is a formula, and there's obvious 1 symbol here and 1 is an odd number (duh!). Inductive Case: Assume A and B are well-formed, A has 2n+1 symbols anb B has 2m+1 symbols. Then (A^B), (AvB) and (A->B) are well formed and the number of symbols in each of these formulas is is 2m+1 + 2n+1 + 1 = 2(m+n+1)+1, which is an odd number. If you want to count the parentheses as symbols, then they have 2m+1+2n+1+3 = 2(m+n+2)+1 - still odd number of symbols. Since all formulas without negation are formed this way, we've proved what we needed to. Page 141 #1: I will use "Si(m,n):P_i" to represent a sumation of i from m to n of P_i: We need to show Si(m,n):(a_i+b) = ( Si(m,n):a_i ) + (n-m+1)b By induction on the difference between n and m (i.e, on n starting from m): Base Case: for n = m, by definition of Si(n,n): Si(n,n):(a_i+b) = a_n+b = (Si(n,n):a_i) + (0+1)b Inductive Case: Assume Si(m,n):(a_i+b) = ( Si(m,n):a_i ) + (n-m+1)b for n>=m, We need to show: Si(m,n+1):(a_i+b) = ( Si(m,n+1):a_i ) + ((n+1)-m+1)b By definition of Si(m,n+1), the above simplifies to: (Si(m,n):a_i+b) + a_(n+1)+b = (Si(m,n):a_i) + a_(n+1) + (n-m+1)b + b By the inductive hypothesis, we replace (Si(m,n):a_i+b) with (Si(m,n):a_i) + (n-m+1)b, which gives us: (Si(m,n):a_i)+(n-m+1)b + a_(n+1)+b = (Si(m,n):a_i)+a_(n+1) + (n-m+1)b + b These are the same. (Only the (n-m+1)b and a_(n+1) are added in different order.)