Einführung in die Mathematische Logik

1. Übungsblatt Abgabe: 25.04.2002, vor der Vorlesung

1.) Eine aussagenlogische Funktion ist eine Funktion

(X_{0}, ⋯, X_{n−1}) ↦ f(X_{0}, ⋯, X_{n−1})

mit X_{0}, ⋯, X_{n−1} ∈ {0, 1} und f(X_{0}, ⋯, X_{n−1}) ∈ {0, 1}.

a) Wieviele n-stellige aussagenlogische Funktionen f(X_{0}, ⋯, X_{n−1}) gibt es?

b) Ein Rechner untersucht in einer Sekunde 10^{6} 10-stellige aussagenlogische Funktionen. Schätzen Sie ab, wie lange die Untersuchung aller 10-stelligen Funktionen dauern würde.

c) Schreiben Sie alle 2-stelligen aussagenlogischen Funktionen mit Hilfe von F, W, ¬, ∨.

2.a) Geben Sie für jedes n−Tupel s = (a_{0}, ⋯, a_{n−1}) ∈ {0, 1}^{n} einen n-stelligen aussagenlogischen Ausdruck A in den Variablen X_{0}, ⋯, X_{n−1} an, der den Wert 1 genau dann annimmt, wenn X_{0} = a_{0}, ⋯, X_{n−1} = a_{n−1}. Schreiben Sie diese Bedingung exakter mit dem Begriff der Belegung auf.

b) Geben Sie für jede aussagenlogische Funktion einen Ausdruck an, dessen Interpretation diese Funktion ist.

3.) Eine aussagenlogische Funktion G heißt universell, wenn sich jede aussagenlogische Funktion als (wiederholte) Komposition von G unter Benutzung der Konstante 0 darstellen lässt.

a) Zeigen Sie, dass die Funktion

\begin{matrix}nor & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}

universell ist. b) Sind die Funktionen “oder” und “und” universell? (Beweis!)

4.) Beweisen Sie aus den in der Vorlesung angegebenen Booleschen Axiomen:

a) Das Komplement ¬A von A ist durch die Bedingung ¬A ∧ A = F , ¬A ∨ A = W eindeutig bestimmt, d.h.:

B ∧ A = F und B ∨ A = W impliziert B = ¬A.

b) Die De Morganschen Gesetze:

A ∨ B = ¬(¬A ∧ ¬B),
A ∧ B = ¬(¬A ∨ ¬B).

Homepage der Vorlesung: http://www.math.uni-bonn.de/people/logic/Lectures/SoSe2002/Vorlesung.html Newsgroup: uni-bonn.math.logik