Theoretische Informatik: Logik WS 96/97

Übung 1

1. Überprüfen Sie folgende Strukturen daraufhin, ob sie reflexive bzw. irreflexive Halbordnungen bilden!

(a) [N^{+}, |] (die Menge der von Null verschiedenen natürlichen Zahlen mit der Teilbarkeitsrelation | — es gilt a | b genau dann, wenn eine natürliche Zahl k existiert mit a · k = b)

(b) [N × N, ♯] (die Menge der geordneten Paare natürlicher Zahlen mit der Relation ”♯“, die definiert ist durch: [a, b]♯[c, d] genau dann, wenn a > c und b ≤ d ist)

(c) [N × N, ⋈] (die Menge der geordneten Paare natürlicher Zahlen mit der Relation ”⋈“, die definiert ist durch: [a, b] ⋈ [c, d] genau dann, wenn a ≥ c und b ≤ d ist)

(d) [{♣, ♠, ♡, ♢},^{}], wobei die folgenden Elemente in der Relation ^{} stehen sollen (und keine weiteren): ♣^{}♠̸, ♠^{}♡̸, ♣^{}♡̸.

2. Weisen Sie nach, daß [N^{+}, ggT, kgV] ein Verband ist! Gibt es ein Nullelement? Gibt es ein Einselement? (ggT – größter gemeinsamer Teiler zweier Zahlen; kgV – kleinstes gemeinsames Vielfaches zweier Zahlen)

3. (∗)Ist [N^{+}, ggT, kgV] ein distributiver Verband?

4. Beweisen Sie die folgenden Beziehungen zwischen Mengen M,N und L erster Stufe. Stützen Sie sich dabei auf die Definitionen der beteiligten Mengenoperationen und -relationen!

(a) Wenn M ⊆ N gilt, so ist M ∩ L ⊆ N ∩ L

(b) Wenn L ⊆ M gilt, so ist M ∩ (N ∪ L) = (M ∩ N) ∪ L

(c) M ⊆ N gilt genau dann, wenn M ∩ \overline{N} = ∅ ist