Solutions to midterm excersizes

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?

• Ax D(x,x) - True
• Ax Ay (D(x,y) -> D(y,x)) - False
• Ax Ay ((D(x,y) ^ D(y, x)) -> (x=y)) - True
• Ax Ay (D(x,y) v D(y,x)) - False
• Ax Ay Az ((D(x,y) ^ D(y,z)) -> D(x,z)) - True

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:

• Every parent is older than his/her children.
  Ax Ay P(x,y) -> O(x,y)

• Alice and Bob have the same parents
  Ax P(x, Bob) <-> P(x, Alice)

• John is Mary's oldest child
  Ax P(Mary, x) -> (O(John, x) v x=John)

• Every person has at least two parents
  Ax Ey,z y!=z ^ P(y,x) ^ P(z,x)

• No two people are exactle the same age
  Ax,y O(x,y) v O(y,x)

3. True or False

• p -> q is equivalent to q -> p - False
• ((p -> q) ^ ~p) -> ~q is a tautology. - False
• ((Ax [P(x)->Q(x)]) ^ P(y)) -> Q(y) is a tautology. - True
• There is a one-to-one function from A to B if and only if there exists an onto function from B to A. - True
• To prove by contradiction that p->q, one must show that p is false. - False.
• If A is a subset of B, then the power set of A is a subset of the power set of B. - True.
• For any two sets A and B, complement(A U B) = comp(A) intersection comp(B) - True.
• The rationals are countable. - True.
• Every subset of a countable set is countable. - True.

f°g questions

• If f is one-to-one, f ° g is one to one. - False.
• If f and g are both onto, f ° g is onto - True.

4. Find gcd(2n+1, 3n+2).
=gcd(2n+1, n+1) = gcd(n, n+1) = 1

5. Define a function on the non-negative integers by g(0)=2. g(1)=3 and g(n+1)=3g(n)-2g(n-1). Use strong induction to prove g(n)=2ⁿ+1

Proof: Base case (n=1) works.
Inductive step:
g(n+1) = 3g(n)-2g(n-1) = 3*2ⁿ+3 - 2*2^n-1-2 = 2ⁿ⁺¹+1

6. Proof by contradiction: if x is a rational number and y is an irrational number, then x+y is irrational.
Suppose it's not the case, i.e. x+y = p/q Since x = r/s, y = p/q-r/s = (ps-rq)/qs - rational number!

7. Proof by induction:
1*2⁰+2*2¹ + 3*2² + ... + n*2^n-1 = (n-1)*2ⁿ+1

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

8. ...

• The proof uses strong induction
• a) is the answer. b) is not correct because the inductive hypothesis only considers values less than n so the inductive step must consider n