Solutions to midterm problems

• a is the sibling of b

  Either of the three solutions below is fine:
  
    Ax P(x,a) -> P(x,b)  ^ D(a,b)
  it's not clear if this is correct if b can have more parents than a
  
    Ax P(x,a) <-> P(x,b)  ^ D(a,b)
  this might not be the best solution if a and b are orhpans (they will be siblings)
  
    Ex P(x,a) ^ P(x, b) ^ D(a,b)
  this is probably the best and the easiest to get right. You don't need to
  say that there must be two parents.
  

• c is the uncle of d
  The way to look at this is that d's parent must be a sibling of c. Hence, we can reuse the solution to the previous question, e.g.:

    Ex P(x,d) ^ (Ey P(y,x) ^ P(y,c) ^ D(x,c))
  

  Note that Ax would be wrong because just one parent can be a sibling of c.

• Ax Ey P(x,y)
  Everyone is a parent. Or everyone has a child.

• Ea Ab (D(a,b) -> Ac (~P(c,a) v ~ P(c,b)))
  This can be re-written like this:
  Ea Ab!=a ~(Ex P(c,a) ^ P(c,b)) or
  Ea Ab!=a a and b don't have a common parent (are not siblings)

  So the answer is: there is a person without siblings.

2. True/False

• p->~(r^s) <=> ~p v ~r v ~s
  We can reqrite the implication in LHS as ~p v ~(r^s)
  By DeMorgan's rule, this is equivalent to ~p v ~r v ~s
  Answer: True

• If Ex Ay P(x,y) is true, then Ay Ex P(x,y) is also true.
  By applying the existential instantiation, and all the other methods on page 173, you can formally proof that this is true. Informally, the value of x in the antecedent will still work in the consequent because it doesn't depend on y (it exists for all y).
  Answer: True

• Ax Ay P(x,y) <=> Ay Ax P(x,y)
  Obvious or use rules on page 173.
  Answer: True

• If A, B, and C are sets such that A U C = B U C, then A=B.
  Consider the case when A and B are both subsets of A but are not equal.
  Answer: False

• If A, B, and C are sets such that A * C = B * C, then A=B.
  If A and B have nothing in common with C, the intersection will be empty no matter what A and B are.
  Answer: False

• Let a, b, and c be integers. If a | b, then a | bc
  Theorem 1, p.114
  Answer: True

• The identity function f(x) = x is a bijection.
  It is both one-to-one and onto.
  Answer: True

• If f(x) and g(x) are injective functions from A to B and h(x) is a function from A to B defiend by h(x) = f(x)+g(x) then h is also an injective function.
  Injective means one-to-one. If g(x) = -f(x), h(x) = 0
  Answer: False.

3. Prove by induction that An>=1
sum(5k+3) (k=1,n) = 2.5n² + 5.5n

Proof:

Base case: n=1 works

Inductive step:

The best way to write it (no matter how you tried to prove it at first, is like this:)

sum(5k+3) (k=1,n+1) = sum(5k+3) (k=1,n) + 5(n+1) + 3 = 2.5n2 + 5.5n + 5n + 8 =
= 2.5 (n2 + 2n + 1) - 5n - 2.5 + 5.5n + 5n + 8 = 2.5(n+1)2 + 5.5(n+1)

4. Prove that for every pair of integers a and m such that 0<a<m and gcd(a,m)>1, a doesn't have an inverse modulo m, i.e., ~Eb: ab = 1(mod m)

Proof:

By contradiciton. Suppose Eb: ab = 1(mod m), i.e. ab = km+1 for some k
That can be re-written as ab-km = 1

Lets denote g = gcd(a,m). We know that g|a and g|m hence g|(ab-km) but ab-km=1 so g|1 which is impossible unless g=1

Contradiction!