TU Wien:Logic and Computability VU (Ciabattoni)/Written Exam 2017-05

Task 1: Prove in sequent calculus

$(A\rightarrow \exists xB(x))\rightarrow \exists x(A\rightarrow B(x))$

where x is not free in A.

Task 2: Formalize the sentence: "every number greater than 1 is divisible by a prime number" using the symbols = (equality predicate), < (predicate strictly less than), 1 (constant 1) and the binary predicate | (divisible). [Note that you dont have a predicate prime number at your disposal]

Task 3: Is the following set

$\{x\mid \lnot \exists y\Phi _{x}(y)\downarrow \}$

Recursive, r.e. or none of them? (Motivate your answer)

Task 4: Let I be any set of indexes of computable functions. Consider the following statement:

I is infinite if and only if I is extensional.

Is the statement true? (Motivate your answer and argue separately for each of the two cases: ”if” and ”only if”.)

Task 5: Prove or refute:

$(\lnot B\lor \Diamond A)\supset (B\supset A)$ characterizes reflexivity of Kripke frames. Treat the two directions of the claim separately and argue directly about the corresponding frames.

Task 6: Compute all factors of the clause $p(x,f(x))\lor p(f(y),y)\lor p(f(a),z)$ Specify the MGU and the unified literals for each factor. (x, y, z are variables, a is a constant.)

Task 7: Show: The diagonal set U* of the set U of Gödel numbers of all expressions that are not true sentences (not in set T) is not expressible in any arithmetic system.