Advanced mathematical logic 2017 PDF

Preview

Summary

Download Advanced mathematical logic 2017 PDF

Description

THE UNIVERSITY OF HULL School of Mathematics & Physical Sciences Level 7 Examination Semester 2 2016/17 32413 Advanced Mathematical Logic 2 hours

Answer five questions: All questions are compulsory. Please note that calculators ARE NOT permitted in this examination. You should answer all compulsory questions. If you do not attempt to answer a compulsory question you will receive a mark of zero for that question. If you have a choice of questions and you answer more than you are asked to, all your answers will be marked and the best mark(s) will contribute towards your final mark, but strictly within the rubric as stated above. If any work is crossed through, it will NOT be marked. Do not open or turn over this exam paper, or start to write anything until told to by the Invigilator. Starting to write before permitted to do so may be seen as an attempt to use Unfair Means.

Module 32413

Page 1 of 3

(continued)

1. (a)

Give an informal proof of the following natural language argument. Premises: Everybody likes a winner. Winners are either gifted or lucky. Lucky people are green or blue. Gifted people are blue or red. Joe does not like anybody who is blue. Conclusion: Joe likes somebody who is green or red. [12 marks]

(b)

Give formal proof of the following statement. ¬∃y(P (y) ∧ Q(y)) → ∀z(P (z) → ¬Q(z)) [12 marks]

2.

A sentence is called persistent if, once true in a structure M, the sentence will stay true in every structure obtained from M by just adding further objects to the domain of disclosure. For example, ∃xCube(x) is a persistence sentence, while ¬∃xCube(x) is not a persistent sentence. Classify the following sentences as persistent or not persistent. If you choose persistent, give reasons for your choice. If you choose not persistent, give a counterexample, i.e. a world were the sentence is true and another were it is false, where the latter is obtained from the former by adding objects. i.

Cube(a) → ∃xFrontOf(a, x)

ii.

∃xFrontOf(a, x) → Cube(a) [12 marks]

3.

Call a pair of sentences TW-equivalent if they have the same truth value in each world that can be constructed in Tarski’s world. Give an example of a pair of sentences that are TW-equivalent but not logically equivalent. Justify your answer. [8 marks]

Module 32413

Page 2 of 3

Questions continue. . .

4.

Translate the following statement into First Order Logic (using the predicates from Tarski’s World). If a natural language statement is ambiguous, give all logically non-equivalent possible translations. i.

Every dodecahedron that is left of any tetrahedron is small.

ii.

There is a cube in front of every medium tetrahedron. [12 marks]

5.

Classify each of the given sentences into one of the following categories: A:

a tautology

B:

a first-order validity that is not a tautology

C:

a logical truth with the usual interpretations from Tarski’s world, but not a first order validity

D:

not a logical truth in the interpretations of Tarski’s world

Justify each choice by doing the following actions according to your classification: A:

find the truth-functional form of the sentences and complete a truth table for the form

B:

find the truth-functional form of the sentences and find a row of the truth-table of the form showing that it is not a tautology; then give an formal proof showing that it is a First Order validity (i.e. a proof not involving any premises)

C:

use the replacement method to show that the sentence is not a First Order validity. Then give an informal proof for it from basic facts about the interpretations of the predicates in Tarski’s World.

D:

describe or draw a counter-example world.

i.

∀x (Cube(x) → ¬SameSize(a, x)) → ¬Cube(a)

ii.

¬SameShape(a, b) → (¬SameShape(b, c) → ¬SameShape(a, c))

iii.

¬ (∀xSmall(x) → ∃y Cube(y)) → (¬∃y Cube(y) ∧ ∀xSmall(x)) [24 marks]

Module 32413

Page 3 of 3

Questions continue. . ....