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

Zur Navigation springen Zur Suche springen

Task 1: Prove in sequent calculus

${\displaystyle (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

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

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”.)

${\displaystyle (\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 ${\displaystyle 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.)