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 .
2. You can fool all of the people some of the time. SOLUTION .
3. You can't fool all the people all the time. SOLUTION .
4. You can't fool a person all the time. SOLUTION . 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. ). Let + and have their usual meaning of addition and multiplication. Let us also have the following predicates
• Axy means x is less than y.
• Bxy means x is greater than y.
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. . 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. . 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. . SOLUTION This is true, as is true when x is 3 and y is 6.
4. . SOLUTION This is false as is false for x and y both being 0.
4. Give a bullet proof that ().

SOLUTION

5. Give a bullet proof that ()

SOLUTION

Stephanie van Willigenburg