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

Aus VoWi
Zur Navigation springen Zur Suche springen

Task 1: Prove in sequent calculus

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

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:

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