Math 2090.03 N (Winter 98-99) TEST 2A Part 2
Friday April 9th, 1999
SOLUTIONS

SURNAME (BLOCK CAPITALS):

INITIALS:

STUDENT NUMBER:

SIGNATURE:

\

All questions concern our predicate logic and material covered in Chapters 8 and 9 of the course text. The marks for each question are shown in brackets. You may NOT use inference rule/Metatheorem MON-AMON or inference rule/Metatheorem MODUS-PONENS anywhere on the test.

All axioms, allowed Metatheorems from Chapters 3, 4, 8, 9, and lower numbered theorems may be used in the proof of a higher numbered theorem.

The 4th page has been left blank for working, please indicate if there is part of your test there that needs marking. You are advised to do the questions worth the most marks first.

\

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. However, in this question you may ONLY use the existential quantifier, , in your translation. (3)
1. Not all cars have four wheels. SOLUTION: Let C be type cars, and Fx mean x has 4 wheels.

2. No mouse is heavier than any elephant. SOLUTION: Let M be type mouse, E be type elephant, Hxy mean x is heavier than y.

2. Compute the following contextual substitution: (2)

SOLUTION: .

3. Let our UD be . Let Ax mean x is prime, and Bxy mean x is a multiple of y (that is ). 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. (6)
1. SOLUTION: Since y is free it maybe true or it maybe false depending on the state. It is clearly true if y=1, however it is false otherwise as for any y we can find an x which it doesn't divide, so the body is false in this case.
2. SOULTION: Since no occurence of x is free, this is either true or false. This is true since the body is true when x is 2.
4. Give a bullet proof that (i.e. ).(9)

SOLUTION