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

Task 1: Consider the following set of formulas:

$i)\ \forall x\forall y(R(x,y)\rightarrow R(y,x))$

$ii)\ \forall x\forall y\forall z((R(x,y)\wedge R(y,z))\rightarrow R(x,z))$

$iii)\ \forall x\exists y(R(x,y))$

$iv)\ \forall x(R(x,x))$

Does $(i),(ii),(iii)\vDash (iv)$ hold? Show either a proof or a counterexample.

Task 2: Show either a sequent calculus proof or a counterexample of the following formula:

$\vdash \exists x((\exists yA(y))\rightarrow A(x))$

Task 3: Let $A$, $B$ be r.e.. Is $A\cap B$ recursive, r.e. or none? Motivate your answer.

Task 4: Consider the set $I=\{i\mid \phi _{i}(1)<i\}$. Is it recursive, r.e. or none? Can Rice Theorem be applied? Motivate your answer.

Task 5: Show all Robinson-Resolvents of the following clauses:

$C=p(f(y),f(a))\vee \neg p(f(x),x)\vee \neg p(z,y)$

$D=\neg p(x,x)\vee p(x,a)$

Task 6: Does the following formula in modal logic characterise the class of serial frames?

$(\Box A\wedge \neg \Diamond B)\supset \neg \Box (A\supset B)$

Task 7: Use the proof of the ADRF theorem to show that the following function is arithmetically definable (assuming $f$ is arithmetically definable):

$g(x,y)=f(f(2x)+y)+3$