Solutions to first part of midterm exercises

1. If D(x,y) is the predicate 'x divides y' then which of the following statements are true in the domain of positive integers?

2. Let P(x, y) be the predicate 'x is a parent of y', and let O(x,y) be the predicate 'x is older than y', and let the universe of all variables be the set of all people. Express each of the following statements as predicate logic formula using P and O:

3. True or False

f°g questions

4. Prove that gcd(a,b) = gcd(b, a mod b).

5. If a and b are rationals, is a^b rational? Prove or disprove this conjecture.


6. Proof by induction:
1*20+2*21 + 3*22 + ... + n*2n-1 = (n-1)*2n+1

Proof:
Basis case: n=1 works
Inductive step:
sum(k*2k-1) (k=1,n+1) = sum(k*2k-1) (k=1,n) + (n+1)*2n = (n-1)*2n+ 1 +(n+1)*2n = n*2n+1+1

7. ...