Solutions to 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?

• 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
  Universals: Ax Ay O(x,y) v O(y,x)
  Existentials: !Ex Ey O(x,y) ^ 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. Prove that gcd(a,b) = gcd(b, a mod b).

If we show that a and b have the same common divisors as b and r do, we will show this to be true. Suppose that d divides both a and b. Then d also divides a-bq=r. Hence, any common divisor of a and b is also a common divisor of b and r. Likewise, suppose that d divides both b and r. Then d also divides bq+r=a. Thus any common divisor of b and r is also a common divisor of a and b. Since a and b have the same set of common divisors as b and r, gcd(a,b)=gcd(b,r).

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. If a and b are rationals, is a^b rational? Prove or disprove this conjecture.

Consider a = 2, b = 1/2. Then a and b are rational, and a^b=2^(1/2), which is irrational. Hence a^b is not necessarily rational.

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. ...

• 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