Theoretische Informatik: Logik WS 96/97

Übung 2

1. Beweisen Sie, daß für beliebige Mengen M und N erster Stufe gilt:

(a) M ⊆ N gdw ℘(M) ⊆ ℘(N).

(b) ℘(\overline{M}) ⊆ \{∅\} ∪ \overline{℘(M)}.

2. Beweisen Sie folgenden Satz: Wenn eine Relation symmetrisch ist, so ist ihre reflexiv-transitive Hülle symmetrisch!

3. Zeigen Sie, daß für drei beliebige Korrespondenzen K, L und M die Beziehung K ∘ (L ∩ M) ⊆ K ∘ L ∩ K ∘ M erfüllt ist!

4. Gegeben sei die Menge M = {1, a, +}.

(a) Wieviele Relationen in M gibt es?

(b) Wieviele Relationen über M gibt es?

(c) Geben Sie alle reflexiven Halbordnungsrelationen in M an!

(d) Geben Sie alle irreflexiven Halbordnungsrelationen in M an!

Theoretische Informatik: Logik WS 96/97

Übung 2

1. Beweisen Sie, daß für beliebige Mengen M und N erster Stufe gilt:

(a) M ⊆ N gdw ℘(M) ⊆ ℘(N).

(b) ℘(\overline{M}) ⊆ \{∅\} ∪ \overline{℘(M)}.

2. Beweisen Sie folgenden Satz: Wenn eine Relation symmetrisch ist, so ist ihre reflexiv-transitive Hülle symmetrisch!

3. Zeigen Sie, daß für drei beliebige Korrespondenzen K, L und M die Beziehung K ∘ (L ∩ M) ⊆ K ∘ L ∩ K ∘ M erfüllt ist!

4. Gegeben sei die Menge M = {1, a, +}.

(a) Wieviele Relationen in M gibt es?

(b) Wieviele Relationen über M gibt es?

(c) Geben Sie alle reflexiven Halbordnungsrelationen in M an!

(d) Geben Sie alle irreflexiven Halbordnungsrelationen in M an!