Übungen zur Vorlesung Logik (Grundkurs)

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

Ein verallgemeinerter Baum auf einer Menge U ist eine dreistellige Funktion Y mit den Eigenschaften

Y (a, b, c) = Y (b, a, c) = Y (a, c, b)
Y (a, b, a) = a
Y (Y (a, b, c), d, e) = Y (Y (a, d, e), b, Y (c, d, e))

Wieso heißt das Baum? In der Graphentheorie ist ein Baum ein ungerichteter, kreisfreier, zusammenhängender Graph. Durch welche Funktion Y wird die Menge seiner Knoten zu einem verallgemeinertem Baum? (Hinweise: In jedem Baum gibt es zwischen je zwei Knoten genau einen Weg. Der Buchstabe Y sieht aus wie ein Baum.) Wieso heißt es verallgemeinert? Weil es Modelle gibt, die keine graphentheoretischen Bäume sind: Finden Sie eine Funktion Y, die die Potenzmenge einer beliebigen Menge M zu einem Baum macht. Zeigen Sie, daß für jedes a die durch

b ≤_{a} c :⇔ b = Y (a, b, c)

definierte Relation ≤_{a} eine Halbordnung auf U ist.

Beschreiben Sie die Halbordnung für die obigen zwei Beispiele. Finden Sie in der Signatur mit einer Konstanten c und einer einstelligen Funktion f 1.) ein kanonisches, 2.) ein nicht kanonisches Modell für

∀x : f(f(x)) = x

sowie 3.) einen Zeugen für

∃y : f(c) = f(f(y))