TU Wien:Logic and Computability VU (Ciabattoni)/Written Exam 2020-01

Question 1: Formalize some statements (1) - (4), does (4) follow from (1)-(3)? e.g.

(1) If there is a bridge or street between X and Y, Y is reachable from X

(2) there is a bridge between Anton and Berta

(3) there is a street between berta and caesar

(4) caesar is reachable from Anton

Question 2: Does this logical consequence hold (something like forall x exists y P(x,y) and .... )? [For the answer it was expected to argue about interpretations satisfying the premises ... I think.]

Question 3: Is this function computable? g(x) = 1 if PHI_x(x) converges or x >= 10; 0 otherwise

Question 4: Is this set recursive, r.e. or none? S = { i | PHI_i is injective }

Question 5: Is [some modal formula G] valid in all symmetric frames? Does F |= G imply that F is symmetric? Give proof or refute!

Question 6: Use Robinson resolution to show that S = { some formulas } is unsatisfiable

Question 7: Use the ARDF proof to show that if f and g are arithmetically definable, than f(x+3, g(2x)) + f(2, x) is arithmetically definable!