TU Wien:Logic and Computability VU (Ciabattoni)/Exam 2022-09-13

Exam 2022-09-13

Task 1

Formalize the following sentence:

"If every politician is a showman and no showman is sincere, then there exists a politician that is insincere."

If the sentence is true then prove it, otherwise state a counterexample.

Task 2

Consider the following formula: $\exists x_{1}\exists x_{2}.{\big (}B(x_{1},x_{2})\to \forall y_{1}\forall y_{2}.(B(f(y_{1}),y_{2})){\big )}$

If the formula is valid present a proof using sequent calculus, otherwise state a counterexample.

Task 3+4

Consider the following two sets

$I_{1}=\{j\mid \Phi _{j}(j)\downarrow {\text{ within }}k{\text{ steps }}\}$

and

$I_{2}=\{j\mid \Phi _{j}(j)\downarrow {\text{ with }}j\in k\}$

are the two sets recursive or r.e.? Can we use Rice Theorem? Motivate your answer and consider the two cases where

(a) $k=1,\dots ,4$

(b) $k={\mathcal {N}}$

Task 5

Let G be the modal formula $\Diamond \Diamond \neg A\to \neg \Box A$. Prove or refute:

(1) G is valid in every transitive frame. (2) If $F\models G$ for a frame F, then F is transitive.

Task 6

Compute all Robinson resolvents of two clauses.

Task 7

Use the proof of the ADRF theorem to show that the function $f(g(x)\cdot g(y),x+y)+2$ is arithmetically definable, if f and g are arithmetically definable. Hint: Specify the witnessing formula, following slide 23 of the last set of slides (on incompleteness).