Math 2090.03 N Assignments 4& 5
due April 5th, 1999

INSTRUCTIONS: This assignment is due April 5th 1999, in class. Groups may hand in a single assignment paper. The maximum group size is 4.

The assignments must have the name and York number of all group members listed at the top of the paper.

Any axiom may be used. Lower numbered theorems may be used in the proof of a higher numbered theorem.


  1. Translate the following english sentences into quantified expressions in predicate logic. First construct suitable types, then a suitable 2-place predicate, and then write the quantified expressions.

    SOLUTION: Let P be the set of all people, T be the set of all times measured in, say, seconds from some initial time. Let F pt mean you can fool person p at time t .

    1. You can fool some of the people some of the time. SOLUTION tex2html_wrap_inline55.
    2. You can fool all of the people some of the time. SOLUTION tex2html_wrap_inline57.
    3. You can't fool all the people all the time. SOLUTION tex2html_wrap_inline59.
    4. You can't fool a person all the time. SOLUTION tex2html_wrap_inline61. TYPO!! The last quantifier should be a "forall".

  2. For every occurrence of an object variable in the following expression state whether it is free or bound

    SOLUTION From left to right the occurrences are free, bound, bound, bound, free.

  3. Let our domain be the set of non-negative integers (i.e. tex2html_wrap_inline63). Let + and tex2html_wrap_inline67 have their usual meaning of addition and multiplication. Let us also have the following predicates Prove that the following are true, false, or may be true in a certain state, and may be false in another. In the latter case if possible give a state for which it is true and a state for which it is false, otherwise justify why all states either give true or give false.
    1. tex2html_wrap_inline73. SOLUTION Since y is free it maybe true or it maybe false depending on the state. However it is alsways false since our set is infinite, so no matter what y we chose, we can still find an x bigger than it.
    2. tex2html_wrap_inline87. SOLUTION Since y is free it maybe true or it maybe false depending on the state. If y is 0 or 1 then it is true, otherwise it is false
    3. tex2html_wrap_inline99. SOLUTION This is true, as tex2html_wrap_inline103 is true when x is 3 and y is 6.
    4. tex2html_wrap_inline111. SOLUTION This is false as tex2html_wrap_inline115 is false for x and y both being 0.
  4. Give a bullet proof that tex2html_wrap_inline123 (tex2html_wrap_inline125).



  5. Give a bullet proof that tex2html_wrap_inline127 (tex2html_wrap_inline129)



Stephanie van Willigenburg