Übungen zur Vorlesung Logik (Grundkurs)

Abgabe am Mittwoch, dem 1. 7. 98, fünf Minuten vor der Vorlesung.

14.1 Eine ∀-Formel hat die Form ∀x_{1}∀x_{2} … ∀x_{n}A für quantorenfreies A, entsprechend definieren wir eine ∃-Formel.

Finden Sie eine ∀-Formel, die zu einer ∃-Formel äquivalent ist, sowie eine ∀-Formel, die zu keiner ∃-Formel äquivalent ist.

10.3 Zeigen Sie: für jede endliche Menge M von natürlichen Zahlen gibt es eine Formel F, so daß die Größe (= Anzahl der Elemente des Universums) jedes normalen Modells von F eine Zahl aus M ist.

15.1 Eine Aussage A heißt unabhängig von einer Formelmenge X, wenn eine der folgenden Bedingungen gilt:

• X |̸= A und X |̸= ¬A.

• es existieren Modelle M und N von X mit M ⊧ A und N ⊧ ¬A.

Zeigen Sie, daß beide Bedingungen äquivalent sind.

15.2 Gruppen sind normale Modelle für die Formelmenge G:

x · (y · z) = (x · y) · z  (1)
1 · x = x  (2)
x · 1 = x  (3)
∀x∃y x · y = 1  (4)

Folgt eine dieser Formeln aus den restlichen drei?

Ist die Aussage ∀x∀y : x · y = y · x unabängig von G?

Ist die Aussage ∀x∃y : y · x = 1 unabhängig von G?