Abschnitt 1.1: Mathematische Logik
Leitfaden für die 1. Präsenzübung
| \( \circ \) | Beispiele von Aussagen |
| \( \circ \) | Beispiele aussagenlogischer Tautologien II |
| \( \circ \) | Negieren von Quantoren |
Leitfaden für das 1. Tutorium
| \( \circ \) | Beispiele aussagenlogischer Tautologien III |
| \( \circ \) | Umschreiben von Formeln in Worten |
Aussagen und Aussageformen
Aufgabe (Mathematische Logik - Beispiele von Aussagen)
Welche der folgenden Sätze sind Aussagen, welche sind keine Aussagen?
| (i) | Berlin ist die Hauptstadt der Bundesrepublik Deutschland. |
| (ii) | Alle Studenten sind fleißig. |
| (iii) | Gestern hat es den ganzen Tag geregnet. |
| (iv) | Reisen bildet. |
| (v) | Der Unterricht hat bereits begonnen. |
| (vi) | Ist Mathematik schwer? |
| (vii) | Herzlichen Glückwunsch! |
Aufgabe (Mathematische Logik - Eigene Beispiele von Aussagen)
Formulieren Sie wenigstens
| (i) | drei eigene Beispiele für Aussagen, |
| (ii) | drei eigene Beispiele von Sätzen, die keine Aussagen sind. |
Aufgabe (Mathematische Logik - Beispiele von Aussageformen)
Geben Sie jeweils ein Beispiel einer Aussageform \( {\mathcal R}(x) \) mit einer, \( {\mathcal S}(x,y) \) mit zwei und \( {\mathcal T}(x,y,z) \) mit drei Variablen, so dass
| (i) | \( {\mathcal R}(6) \) ist wahr, |
| (ii) | \( {\mathcal S}(1,7) \) ist wahr, |
| (iii) | \( {\mathcal T}(1,3,12) \) ist wahr. |
Verknüpfung von Aussagen
Aufgabe (Mathematische Logik - NOR-Verknüpfung)
Die NOR-Verknüpfung (Nicht-Oder) ist erklärt als \[ \neg(a\vee b). \] Stellen Sie für diese Verknüpfung eine Wahrheitstabelle auf. Wann ist sie wahr, wann ist sie falsch?
Aufgabe (Mathematische Logik - NAND-Verknüpfung)
Die NAND-Verknüpfung (Nicht-Und) ist erklärt als \[ \neg(a\wedge b). \] Stellen Sie für diese Verknüpfung eine Wahrheitstabelle auf. Wann ist sie wahr, wann ist sie falsch?
Aufgabe (Mathematische Logik - XOR-Verknüpfung)
Die XOR-Verknüpfung (exklusives Oder) ist erklärt als \[ (a\wedge\neg b)\vee(\neg a\wedge b). \] Stellen Sie für diese Verknüpfung eine Wahrheitstabelle auf. Wann ist sie wahr, wann ist sie falsch?
Aufgabe (Mathematische Logik - XNOR-Verknüpfung)
Die XNOR-Verknüpfung (exklusives Nicht-Oder) ist erklärt als \[ (a\vee b)\vee(\neg a\wedge\neg b). \] Stellen Sie für diese Verknüpfung eine Wahrheitstabelle auf. Wann ist sie wahr, wann ist sie falsch?
Aufgabe (Mathematische Logik - AOI-Verknüpfung)
Die AOI-Verknüpfung (AND-OR-Invert) ist erklärt als \[ \neg[(a\wedge b)\vee c]. \] Stellen Sie für diese Verknüpfung eine Wahrheitstabelle auf. Wann ist sie wahr, wann ist sie falsch?
Aufgabe (Mathematische Logik - OAI-Verknüpfung)
Die OAI-Verknüpfung (OR-AND-Invert) ist erklärt als \[ \neg[(a\vee b)\wedge c]. \] Stellen Sie für diese Verknüpfung eine Wahrheitstabelle auf. Wann ist sie wahr, wann ist sie falsch?
Aufgabe (Mathematische Logik - Doppelte Verneinung)
Beweisen Sie vermittels einer Wahrheitstabelle \[ \neg\neg a\equiv a. \]
Aufgabe (Mathematische Logik - Idempotenzgesetze der Aussagenlogik)
Beweisen Sie vermittels einer Wahrheitstabelle:
| (i) | \( a\equiv a\vee a \) |
| (ii) | \( a\equiv a\wedge a \) |
Aufgabe (Mathematische Logik - Umkehrung der Implikation)
Beweisen Sie vermittels einer Wahrheitstabelle \[ a\to b\equiv\neg b\to\neg a. \]
Aufgabe (Mathematische Logik - Kommutativität der Disjunktion und Konjunktion)
Beweisen Sie vermittels einer Wahrheitstabelle:
| (i) | \( a\vee b\equiv b\vee a \) |
| (ii) | \( a\wedge b\equiv b\wedge a \) |
Aufgabe (Mathematische Logik - Assoziativgesetze der Aussagenlogik)
Beweisen Sie vermittels einer Wahrheitstabelle:
| (i) | \( a\vee(b\vee c)\equiv(a\vee b)\vee c \) |
| (ii) | \( a\wedge(b\wedge c)\equiv(a\wedge b)\wedge c \) |
Aufgabe (Mathematische Logik - Distributivgesetze der Aussagenlogik)
Beweisen Sie vermittels einer Wahrheitstabelle:
| (i) | \( a\vee(b\wedge c)\equiv(a\wedge b)\vee(a\wedge c) \) |
| (ii) | \( a\wedge(b\vee c)\equiv(a\vee b)\wedge(a\vee c) \) |
Aufgabe (Mathematische Logik - Verschmelzung von Disjunktion und Konjunktion)
Beweisen Sie vermittels einer Wahrheitstabelle:
| (i) | \( a\equiv a\wedge(a\vee b) \) |
| (ii) | \( a\equiv a\vee(a\wedge b) \) |
Aufgabe (Mathematische Logik - de Morgansche Regeln der Aussagenlogik)
Beweisen Sie vermittels einer Wahrheitstabelle:
| (i) | \( \neg(a\vee b)\equiv\neg a\wedge\neg b \) |
| (ii) | \( \neg(a\wedge b)\equiv\neg a\vee\neg b \) |
Aussagenlogische Beweisprinzipien
Aufgabe (Mathematische Logik - Beispiele aussagenlogischer Tautologien I)
Beweisen Sie vermittels einer Wahrheitstabelle, dass es sich im Folgenden um Tautologien handelt:
| (i) | \( a\vee(b\wedge\neg b)\to a \) |
| (ii) | \( a\wedge(b\vee\neg b)\to a \) |
Aufgabe (Mathematische Logik - Beispiele aussagenlogischer Tautologien II)
Beweisen Sie vermittels einer Wahrheitstabelle, dass es sich im Folgenden um Tautologien handelt:
| (i) | \( a\vee\neg a \) |
| (ii) | \( \neg(a\wedge\neg a) \) |
| (iii) | \( \neg(\neg a)\to a \) |
| (iv) | \( (a\to b)\to(\neg b\to\neg a) \) |
Aufgabe (Mathematische Logik - Beispiele aussagenlogischer Tautologien III)
Beweisen Sie vermittels einer Wahrheitstabelle, dass es sich im Folgenden um Tautologien handelt:
| (i) | \( (a\to b)\wedge a\to b \) |
| (ii) | \( (a\to b)\wedge\neg b\to\neg a \) |
| (iii) | \( (a\to b)\wedge(b\to c)\to(a\to c) \) |
Aufgabe (Mathematische Logik - Weitere Tautologien)
Die folgenden Regeln werden in → R.E. Hodel Kapitel 3, Abschnitt 3.1 für einen axiomatischen Zugang zur Aussagenlogik verwendet. Beweisen Sie, dass es sich bei diesen Regeln um Tautologien handelt.
| (i) | Kontraktionsregel | \( a\vee a\to a \) |
| (ii) | Expansionsregel | \( a\to a\vee b \) |
| (iii) | Schnittregel | \( (a\vee b)\wedge(\neg a\vee c)\to(b\vee c) \) |
Aufgabe (Mathematische Logik - Tautologien der Implikation)
Beweisen Sie vermittels einer Wahrheitstabelle, dass es sich im Folgenden um Tautologien handelt:
| (i) | \( a\to((a\to b)\to b) \) |
| (ii) | \( a\to(b\to(a\to b)) \) |
| (iii) | \( \neg(a\to a)\to b \) |
| (iv) | \( \neg(a\to b)\to\neg b \) |
| (v) | \( \neg(a\to b)\to a \) |
Aufgabe (Mathematische Logik - Disjunktion und Konjunktion mit einer Kontradiktion)
Es sei \( p \) eine Aussage, und es sei \( q \) eine Kontradiktion, d.h. es ist \( q \) stets falsch, unabhängig von der Belegung ihrer Variablen. Beweisen Sie vermittels einer Wahrheitstabelle \[ p\vee q\equiv p,\quad p\wedge q\equiv q. \]
Quantoren und deren Negation
Aufgabe (Mathematische Logik - Mathematische Aussagen mit Quantoren)
Es bedeute \( \mathbb Z=\{\ldots,-2,-1,0,1,2,3,\ldots\} \) die Menge der ganzen Zahlen. Formulieren Sie folgende Aussagen als Formeln mit Quantoren. Welche Aussagen sind wahr, welche sind falsch?
| (i) | Es existieren ein \( x\in\mathbb Z \) und ein \( y\in\mathbb Z \) mit \( x+y=0. \) |
| (ii) | Zu jedem \( x\in\mathbb Z \) existiert ein \( y\in\mathbb Z \) mit \( x+y=0. \) |
| (iii) | Es existiert ein \( x\in\mathbb Z, \) so dass \( x+y=0 \) richtig ist für alle \( y\in\mathbb Z. \) |
| (iv) | Für alle \( x\in\mathbb Z \) und für alle \( y\in\mathbb Z \) gilt \( x+y=0. \) |
Aufgabe (Mathematische Logik - Aus Peanos Axiomensystem der natürlichen Zahlen)
Es bedeute \( \mathbb N=\{1,2,3,\ldots\} \) die Menge der natürlichen Zahlen. Formulieren Sie folgende Axiome für \( \mathbb N \) als Formeln mit Quantoren.
| (i) | Jede natürliche Zahl \( n\in\mathbb N \) besitzt einen Nachfolger \( n'\in\mathbb N. \) |
| (ii) | Es existiert keine natürliche Zahl \( n\in\mathbb N \) mit \( n'=1. \) |
| (iii) | Sind \( m,n\in\mathbb N \) und \( m=n, \) so gilt \( m'=n'. \) |
Aufgabe (Mathematische Logik - Umschreiben von Formeln in Worten)
Schreiben Sie die folgenden Formeln in eigenen Worten um.
| (i) | \( \exists m\in\mathbb N\,\forall n\in\mathbb N\,(m\gt n) \) |
| (ii) | \( \exists m\in\mathbb Z\,\forall n\in\mathbb N\,(m\lt n) \) |
| (iii) | \( \forall m\in\mathbb N\,\exists n\in\mathbb N\,(n\lt m) \) |
| (iv) | \( \forall m\in\mathbb N\,\exists n\in\mathbb Z\,(n\gt m) \) |
Welche dieser Aussagen ist wahr, welche ist falsch?
Aufgabe (Mathematische Logik - Negieren von Tautologien I)
Negieren Sie die folgenden Formeln:
| (i) | \( a\vee\neg a \) |
| (ii) | \( \neg(\neg a)\to a \) |
Aufgabe (Mathematische Logik - Negieren von Tautologien II)
Negieren Sie die folgenden Formeln:
| (i) | \( (a\to b)\wedge a\to b \) |
| (ii) | \( (a\to b)\wedge(b\to c)\to(a\to c) \) |
Aufgabe (Mathematische Logik - Negieren der Quantoren)
Negieren Sie die folgenden Formeln:
| (i) | \( \forall m\,\exists n\,(m\gt n) \) |
| (ii) | \( \exists m\,\forall n\,(n\le m) \) |
Aufgabe (Mathematische Logik - Negieren der Stetigkeit)
Negieren Sie die folgende Definition der Stetigkeit einer Funktion \( f\colon\Omega\to\mathbb R \) in einem Punkt \( x_0\in\Omega: \) \[ \forall\varepsilon\gt 0\,\exists\delta\gt 0\,\forall x\in\Omega\,(|x-x_0|\lt\delta\to|f(x)-f(x_0)|\lt\varepsilon). \]