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?
- 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).
Let r = a mod b. We know that r = a - bq for some q. We have to show
that a and b have the same common divisors as b and r. 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. 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.
6. Proof by induction:
1*2^{0}+2*2^{1} + 3*2^{2} + ... + n*2^{n-1}
= (n-1)*2^{n}+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} = (n-1)*2^{n}+ 1 +(n+1)*2^{n} =
n*2^{n+1}+1
7. ...
- 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