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

Aus VoWi
Zur Navigation springen Zur Suche springen

Exam 2022-09-13[Bearbeiten | Quelltext bearbeiten]

Task 1[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Consider the following formula:

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

Task 3+4[Bearbeiten | Quelltext bearbeiten]

Consider the following two sets


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



Task 5[Bearbeiten | Quelltext bearbeiten]

Let G be the modal formula . Prove or refute:

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

Task 6[Bearbeiten | Quelltext bearbeiten]

Compute all Robinson resolvents of two clauses.

Task 7[Bearbeiten | Quelltext bearbeiten]

Use the proof of the ADRF theorem to show that the function 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).