Logik Und Beweismethoden

Transcript

Logik 1 Stefan Richter basierend auf früheren Vorträgen von Bärbel Janssen, Winnifried Wollner, Casper Goch, Axel Wagner, Saskia Klaus Vorkurs zum WS 2015/2016 Inhaltsverzeichnis 1 Klassische Aussagenlogik - Einführung 1.1 Aussagen und Wahrheitswerte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Operatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 3 2 Sätze und Beweise 2.1 Struktur eines Satzes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8 3 Prädikatenlogik erster Stufe 9 3.1 Quantoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Negation von Quantoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1 1 KLASSISCHE AUSSAGENLOGIK - EINFÜHRUNG 2 Tag 1 Dieser Vortrag hat das Ziel, die elementaren Begriffe der Klassischen Logik einzuführen und die wesentlichen Regeln im Arbeiten mit mathematischen Aussagen darzulegen. Aufgrund der beschränkten Zeit und des Ziels einer maximalen Verständlichkeit können wir keine formal exakte Herleitung geben. Dies ist auch deswegen nicht möglich, weil andere, dafür benötigte Begriffe erst in späteren Vorträgen dieses Vorkurses erklärt werden. 1 Klassische Aussagenlogik - Einführung 1.1 Aussagen und Wahrheitswerte In der Mathematik wollen wir Sätze / Theoreme formulieren, die immer wahr sein sollen. Aus solchen Sätzen wollen wir auch neue Sätze herleiten. Damit bei diesen Herleitungen kein Fehler passiert und plötzlich ein "falscher" Satz herauskommt, wurde das Gebiet der Klassischen Logik entwickelt. Die Klassische Logik gibt uns eine Konzept, mit der wir die Formulierung und die Beweise von mathematischen Sätzen auf ein sicheres Fundament stellen können. Wichtigstes Element der Klassischen Logik ist die Aussage. Definition 1.1 (Aussage). Eine (logische) Aussage ist ein sprachliches Gebilde, von dem es sinnvoll ist zu fragen, ob es wahr oder falsch ist. Notation: Wir bezeichnen Aussagen mit Großbuchstaben (A,B,C,...) Die Klassische Logik ist durch genau zwei Eigenschaften gekennzeichnet. Die erste besagt: Axiom 1.2 (Prinzip der Zweiwertigkeit). Jede Aussage hat einen von genau zwei Wahrheitswerten, wahr und falsch. Notation: Wir bezeichnen die beiden Wahrheitswerte kurz mit w für wahr und f für falsch. Beispiel 1.3. Aussagen sind: • A = "Es regnet." • B = "Die Straße ist nass." • C = "5 ist eine Primzahl." • D = "16 ist durch 5 teilbar." Der Wahrheitswert von A, B ist durch Überprüfung bestimmbar, C ist wahr, D ist falsch. Keine Aussage ist: • Hoffentlich gewinne ich im Lotto. Es ist hier nicht sinnvoll nach wahr oder falsch zu fragen. 1 KLASSISCHE AUSSAGENLOGIK - EINFÜHRUNG 1.2 3 Operatoren Aus bestehenden Aussagen können mit Hilfe von so genannten Operatoren neue Aussagen gewonnen werden. Ein Operator nimmt eine bestimmte Anzahl von Aussagen (sog. "Operanden") entgegen und ordnet diesen - abhängig von ihrem Wahrheitswert - einen neuen Wahrheitswert (w oder f ) zu. Ein Operator macht also aus einer oder mehreren Aussagen eine neue Aussagen. Definition 1.4 (Operator). Ein Operator f ordnet einer bestimmten Anzahl von Aussagen A1 , ..., An eine neue Aussage f (A1 , ..., An ) zu. Das folgende zweite Axiom der Klassischen Logik sorgt dafür, dass die Definition eines Operator sinnvoll ("wohldefiniert") ist: Axiom 1.5 (Prinzip der Extensionalität). Der Wahrheitswert jeder zusammengesetzten Aussage ist eindeutig durch die Wahrheitswerte ihrer Teilaussagen bestimmt. Durch Definition 1.4 ist klar, wie wir einen neuen Operator von Aussagen A1 , ..., An zu definieren haben: Für jede mögliche Kombination von Wahrheitswerten müssen wir angeben, welchen Wahrheitswert die neue Aussage f (A1 , ..., An ) hat. Wir führen nun nacheinander die bekanntesten Operatoren ein. Hinter jedem Operator steht eine anschauliche Interpretation, bzw. jeder Operator ist durch eine anschauliche Interpretation motiviert. (Einschub: Die Kenntnis der Interpretation ist in der Mathematik allgemein sehr wichtig, um mit mathematischen Objekten zu arbeiten und den gewünschten anschaulichen Sachverhalt in die Mathematik zu übertragen. Man kann dann die mathematischen Errungenschaften nutzen, um eine neue mathematische Aussage zu erhalten und diese in einem letzten Schritt mittels der Interpretation wieder in die reale Welt zu übertragen. Es ist aber ebenso wichtig, zwischen Interpretation und mathematischem Objekt zu trennen: Oft ist es nötig, bei der Definition mathematischer Objekte Fragen zu stellen, die man sich in der realen Welt gar nicht stellt. Diese Fragen sind aber notwendig, um in der Mathematik keine unsinnige Theorie zu erzeugen. Deswegen steht die mathematische Definition auch manchmal der anschaulichen Interpretation entgegen oder beantwortet zumindest eine Frage auf eine Weise, die in der realen Welt als nicht offensichtlich empfunden wird. Der Sinn dieser Definition liegt dann darin, eine mathematisch sinnvolle, funktionierende Theorie zu erhalten.) Wir definieren die Operatoren mit dem nützlichen Werkzeug der Wahrheitstafeln. Das sind Tabellen, in denen jede Spalte eine Aussage repräsentiert und jede Zeile eine mögliche Kombination von Wahrheitswerten. Bei Wahrheitstafeln schreibt man in die linken Spalten alle möglichen Wahrheitswerte der auftretenden Ausgangsaussagen (z.B. A und B); in den Spalten rechts davon schreibt man die Wahrheitswerte der aus den Ausgangsaussagen kombinierten Aussagen. Definition 1.6 (Operator: Negation). Für eine Aussage A definieren wir die Negation ¬A durch: 1 KLASSISCHE AUSSAGENLOGIK - EINFÜHRUNG A w f 4 ¬A f w Interpretation: ¬A nimmt immer genau den umgekehrten Wahrheitswert von A an. Beispiel 1.7 (Vgl. Beispiel 1.3). ¬A = "Es regnet nicht." An einer Wahrheitstafel kann man auch erkennen, was weitere mögliche Operatoren wären, die nur auf eine einzige Aussage wirken: Bemerkung 1.8 (Alle möglichen Operatoren für nur eine Aussage). Alle möglichen Operatoren für eine Aussage A lauten: A w f w w f f f w w f Man sieht hieran, dass nicht die Notwendigkeit besteht, einen weiteren Operator zu definieren, der auf nur eine Aussage wirkt: Die erste Spalte entspricht w, die zweite Spalte entsprich f , die dritte Spalte entsprich ¬A und die vierte Spalte entspricht A selbst. Definition 1.9 (Operator: Und-Verknüpfung). Für zwei Aussagen A, B definieren wir die undVerknüpfung A ∧ B durch: A w w f f B w f w f A∧B w f f f Interpretation: A ∧ B ist genau dann wahr, wenn A und B wahr sind. Beispiel 1.10 (Vgl. Beispiel 1.3). A ∧ B = "Es regnet und die Straße ist nass." Definition 1.11 (Operator: Oder-Verknüpfung). Für zwei Aussagen A, B definieren wir die oder-Verknüpfung A ∨ B durch: 1 KLASSISCHE AUSSAGENLOGIK - EINFÜHRUNG A w w f f B w f w f 5 A∨B w w w f Interpretation: A ∨ B ist genau dann wahr, wenn A wahr ist oder B wahr ist (oder sowohl A als auch B wahr ist). Beispiel 1.12 (Vgl. Beispiel 1.3). A ∨ B = "Es regnet oder die Straße ist nass." Definition 1.13 (Operator: Implikation). Für zwei Aussagen A, B definieren wir die Implikation A ⇒ B durch: A w w f f B w f w f A⇒B w f w w Interpretation: Wenn A wahr ist, dann auch B. Man sagt auch: A ist hinreichend für B. Beispiel 1.14 (Vgl. Beispiel 1.3). A ⇒ B = "Wenn es regnet, dann ist die Straße nass." Anmerkung zur Definition der Implikation: Die Lesart "wenn ... dann..." ist problematisch, da damit in der normalen Sprache vor allem inhaltliche Zusammenhänge wie Kausalität oder zeitliche Nähe ausgedrückt werden. All das macht die Implikation in der Logik nicht, sie nennt nur den formalen Zusammenhang "Wenn A, dann B". Zur Frage, warum A hinreichend für B ist - ob aufgrund eines kausalen Zusammenhangs oder auch nur rein zufällig - nimmt die Implikation nicht Stellung. Die Wahrheitswerte der Implikation in den beiden unteren Zeilen der Wahrheitstabelle sind in der Mathematik nicht unumstritten (vgl. "parakonsistente Logiken"). Argumente für diese Setzung sind: • Die Implikation wird vor allem genutzt, wenn man bereits weiß, dass A wahr ist. In dem Sinne hat man eine gewisse Definitionsfreiheit für den Wahrheitswert von A ⇒ B, wenn A falsch ist. • Durch die obige Definition entsteht eine "einfache Logik", d.h. wir können bestimmte Sachverhalte, die wir als immer erfüllt ansehen, auch einfach ausdrücken. Beispielsweise 1 KLASSISCHE AUSSAGENLOGIK - EINFÜHRUNG 6 ist mit obiger Setzung für alle x ∈ N die Aussage (x > 3) ⇒ (x > 1) immer wahr. • (Erst verständlich mit den Sätzen aus Kapitel 2): Mit der obigen Setzung wird eine wichtige Eigenschaft des Kalküls der klassischen zweiwertigen Logik erreicht: Aus einem Widerspruch folgen beliebige Aussagen (Aus Falschem folgt Beliebiges, "ex falso sequitur quodlibet"): Nehmen wir dazu an, wir haben eine Aussage A, von der bekannt ist, dass sowohl A als auch ¬A wahr ist. Für eine beliebige Aussage B ist dann auch ¬A ∨ B wahr. Man kann zeigen (Übungen), dass (¬A ∨ B) ⇐⇒ (A ⇒ B), d.h. A ⇒ B ist wahr. Nach Satz 2.4 gilt (A ∧ (A ⇒ B)) ⇒ B. Da sowohl A als auch A ⇒ B wahr sind, ist also B wahr. In diesem Sinne haben wir gezeigt, dass jede beliebige Aussage B wahr ist, wenn ein Widerspruch in unserem Kalkül angenommen wird. Die obige Definition der Implikation sorgt also dafür, dass die klassische Logik mathematische Theorien "bestraft", die Widersprüche enthalten. In solch einer mathematischen Theorie wären dann nämlich einfach alle Aussagen wahr, unabhängig davon, was behauptet wird (auch die Aussage "London liegt in Berlin" wäre in solch einer Theorie wahr). Solche widersprüchlichen Theorien werden dadurch wertlos für die Anwendung in der Realität. Definition 1.15 (Operator: Äquivalenz). Für zwei Aussagen A, B definieren wir die Äquivalenz A ⇐⇒ B durch: A w w f f B w f w f A ⇐⇒ B w f f w Interpretation: A ⇐⇒ B ist wahr, wenn A und B die gleichen Wahrheitswerte haben. Beispiel 1.16 (Vgl. Beispiel 1.3). A ⇐⇒ B = "Es regnet genau dann, wenn die Straße nass ist." Wir werden im nächsten Kapitel sehen, dass dem Äquivalenzzeichen insbesondere beim Vergleichen verschiedener Aussagen / dem Vereinfachen von Aussagen eine wesentliche Rolle zuteil wird. 2 SÄTZE UND BEWEISE 2 7 Sätze und Beweise Definition 2.1 (Satz/Beweis). Ein Satz ist eine Aussage, die überprüfbar immer wahr ist. Ein Beweis eines Satzes ist eine logische Herleitung dieser Wahrheits-Aussage aus Axiomen und Sätzen. Andere Bezeichnungen für einen Satz sind auch (je nacht Kontext): Lemma, Korollar, Proposition, etc. Anstatt "Die Aussage ist immer wahr" verwenden wir auch "Die Aussage gilt". Als Beispiel wollen wir nun den "Satz vom Widerspruch" beweisen. Dies machen wir mit Hilfe von Wahrheitstafeln, d.h. wir gehen alle logischen Möglichkeiten durch und zeigen in jedem Fall, dass die Aussage des Satzes wahr ist. Satz 2.2 (Der Satz vom Widerspruch). Für eine beliebige Aussage A gilt: (A ∧ ¬A) ⇐⇒ f (1) Alternative Formulierung: Es gilt ¬(A ∧ ¬A). Beweis. Mittels Wahrheitstafeln. Unter Nutzung der Wahrheitstafeln. Wir leiten spaltenweise die Wahrheitswerte der in der Kopfzeile der Tafel stehenden Aussagen her: A w f ¬A A ∧ ¬A f f w f (A ∧ ¬A) ⇐⇒ f w w Aussagen mit Äquivalenzzeichen ("⇐⇒ "), die immer wahr sind, können dazu genutzt werden, andere Aussagen umzuformen: Haben wir zum Beispiel eine Aussage wie in (1), können wir nun in jeder anderen Aussage, in der A ∧ ¬A vorkommt, stattdessen einfach f schreiben. Zum Beispiele gilt für Aussagen A, B: B ∨ (A ∧ ¬A) ⇐⇒ B ∨ f. Auf ähnliche Weise wie den Satz vom Widerspruch (Satz 2.2) kann der "Satz vom Ausgeschlossenen Dritten" gezeigt werden: Satz 2.3 (Satz vom ausgeschlossenen Dritten). Für eine beliebige Aussage A gilt: A ∨ ¬A. Alternative Formulierung: Es gilt (A ∨ ¬A) ⇐⇒ w. 2 SÄTZE UND BEWEISE 8 Im Gegensatz zum Satz vom Widerspruch ist der Satz vom ausgeschlossenen Dritten eine Besonderheit der zweiwertigen Klassischen Logik, d.h. eine Konsequenz von Axiom 1.2. Nicht alle Mathematiker nehmen den Satz vom ausgeschlossenen Dritten an, weswegen neben der zweiwertigen Logik auch andere Konzepte entwickelt wurden. 2.1 Struktur eines Satzes Auch wenn an sich jede stets wahre Aussage einen Satz darstellt, so tritt eine bestimmte Struktur bei mathematischen Sätzen besonders häufig auf: A⇒B (2) A ist hierbei meistens eine zusammengesetzte Aussage wird hierbei die "Prämisse" oder "Voraussetzung" genannt, B eine manchmal zusammengesetzte Aussage, genannt die "Konklusion" oder "Folgerung". Die Voraussetzungen und Folgerungen bei einem Satz zu identifizieren ist ein wichtiger Schritt in einem sauberen Beweis. Geraden in den ersten Semestern führt ein genaues Aufführen der Voraussetzungen eines Satzes, gemeinsam mit ein paar einfachen Definitionen und schon bekannten Sätzen ziemlich direkt zur Folgerung. Die Struktur (2) an sich ist im Allgemeinen noch kein Satz (d.h. immer wahr), weil die Aussagen A,B hier nicht bekannt sind und daher die Wahrheit der Implikation A ⇒ B nicht überprüft werden kann. Es gibt jedoch eine Möglichkeit, die Aussage logisch anders zu formulieren, sodass sie immer wahr wird und auch das Wesen des Satzes besser in Erscheinung treten lässt. Diese lautet: Satz 2.4 ("modus ponens"). Für alle Aussagen A, B gilt: (A ∧ (A ⇒ B)) ⇒ B. (3) Interpretation: Wenn A gilt und B aus A folgt, dann gilt auch B. Beweis. Mittels Wahrheitstafeln: A B A⇒B w w w w f f f w w f f w A ∧ (A ⇒ B) w f f f (A ∧ (A ⇒ B)) ⇒ B w w w w Zwei beliebte falsche Schlüsse von Sätzen der Form A ⇒ B sind: • Aus der Gültigkeit der Folgerung B wird geschlossen, dass die Voraussetzungen A erfüllt sein müssen. Beispiel: ()2 −2 = 2 ⇒ 4 = 4 3 PRÄDIKATENLOGIK ERSTER STUFE 9 wird gefolgert, dass −2 = 2 gelten sollte, weil ja 4 = 4 wahr ist. Rein formal entspräche diese Folgerung der Vermutung, dass (B ∧ (A ⇒ B)) ⇒ A gilt (hier ist A die Aussage −2 = 2 und B die Aussage 4 = 4). Blick auf die Wahrheitstafel zeigt aber, dass dem nicht so ist: A w w f f B w f w f A⇒B w f w w B ∧ (A ⇒ B) (B ∧ (A ⇒ B)) ⇒ A w w f w w f f w Wie wir sehen, ist die Implikation genau dann falsch, wenn A falsch ist, B aber wahr, was in unserem Beispiel der Fall ist. • Daraus, dass die Voraussetzungen A nicht gelten, wird gefolgert, dass die Folgerung B auch nicht wahr ist. Beispiel: Wenn es regnet, dann ist die Straße nass. Fehlschluss: Wenn es nicht regnet, dann ist die Straße auch nicht nass. Formel entspräche diese Folgerung der Vermutung, dass (¬A ∧ (A ⇒ B)) ⇒ (¬B) gilt. Eine Wahrheitstafel zeigt, dass dies nicht der Fall ist: A w w f f 3 3.1 B w f w f A⇒B w f w w ¬A ∧ (A ⇒ B) f f w w (¬A ∧ (A ⇒ B)) ⇒ (¬B) w w f w Prädikatenlogik erster Stufe Quantoren Im Gegensatz zur Aussagenlogik, welche die Zerlegung von Aussagen in nicht weiter teilbare Aussagen (sog. Elementaraussagen) untersucht, beschäftigt sich die Prädikatenlogik mit der Struktur dieser Elementaraussagen. Das Problem in der oben formulierten Aussagenlogik liegt darin, dass wir nur Sätze über Aussagen formulieren können, die uns vollständig bekannt sind. Beispiel 3.1. Wir betrachten die Aussagen A = "Steffen darf Alkohol kaufen" 3 PRÄDIKATENLOGIK ERSTER STUFE 10 und B = "Steffen ist älter als 10 Jahre". Nehmen wir nun an, dass wir zeigen konnten, dass wenn A wahr ist, auch B wahr ist. Im Allgemeinen wollen wir aber nicht nur eine Aussage über die Person Steffen machen, sondern wir wollen möglicherweise ausdrücken, dass das relevante Merkmal von Steffen ist, Alkohol kaufen zu dürfen und dass bestimmte Aussagen alleine aus dieser Tatsache folgen. So darf zum Beispiel Claudia auch Alkohol kaufen und ist damit vermutlich ebenfalls älter als 10 Jahre. Bisher wurde der Sachverhalt aber nur für Steffen bewiesen. Wir wollen also eine Aussage beweisen können wie Alle Leute, die Alkohol kaufen dürfen, sind älter als 10 Jahre. (4) Die Situation von Beispiel 3.1 tritt auch direkt in der Mathematik auf: Oft kommt es vor, dass mathematische Sätze mit Unbekannten formuliert werden, deren Wert erst später (zum Beispiel bei Anwendung des Satzes) bekannt ist. Wir werden nun Aussagen einführen, die auch Variablen erlauben, so genannte Prädikate. Definition 3.2 (Prädikat). Ein Prädikat A(x1 , ..., xn ) ist ein sprachliches Gebilde mit Variablen x1 , ..., xn , dass zu einer Aussage wird, wenn für jede Variable x1 , ..., xn ein konkreter Wert eingesetzt wird. Bemerkung 3.3. Auf Prädikaten können dieselben Operatoren angewandt werden wie auf Aussagen. Beachte aber, dass das Ergebnis dann immer noch ein Prädikat ist und keine Aussage! Beispiel 3.4 (Vergleiche Beispiel 3.1). Definiere A(x) := "x darf Alkohol kaufen", und B(y) := "y ist älter als 10 Jahre" Die Interpretation des Prädikats A(x) ⇒ B(x) lautet: "Wenn x Alkohol kaufen darf, dann ist x älter als 10 Jahre". Definition 3.5 (Prädikat Elementrelation). Für x ein Objekt und M eine Menge können wir das Prädikat E(x, M ) := x ∈ M definieren (Interpretation: "x ist Element von M "). 3 PRÄDIKATENLOGIK ERSTER STUFE 11 Beispiel 3.6. Die Aussage E(2, {1, 2, 3}) = "2 ist Element von {2, 3, 4}" ist wahr, die Aussage E(4, {1, 2, 3}) ist falsch. Wie können wir aus Prädikaten wieder Aussagen gewinnen? Eine Möglichkeit ist, konkrete Werte für die Variablen einzusetzen. Die resultierenden Aussagen für sich genommen sind aber sehr schwach, damit erreichen wir keine Aussage der Form (4). In der Prädikatenlogik wurden daher "Quantoren" eingeführt. Diese geben an, für wie viele Objekte x ein bestimmtes Prädikat gilt. Definition 3.7 (Quantoren: All-Quantor und Existenz-Quantor). Die Aussage ∀x : A(x) ist wahr, wenn für alle x die Aussage A(x) wahr ist (∀ heißt All-Quantor ). Die Aussage ∃x : A(x) ist wahr, wenn es ein x gibt, sodass die Aussage A(x) wahr ist (∃ heißt Existenz-Quantor ). Die Quantoren alleine reden von allen möglichen Objekten / Variablen x, d.h. mit x können alle möglichen Zahlen, Mengen, etc. gemeint sein. Wollen wir unsere Aussagen auf bestimmte Teilmengen einschränken, brauchen wir dazu zusätzliche Prädikate: Beispiel 3.8. Für zwei Prädikate A(x), B(x) ist ∀x : (A(x) ⇒ B(x)) eine Aussage. Interpretation: "Für alle x gilt: Wenn A(x) wahr ist, dann ist auch B(x) wahr". Für eine feste Menge M und ein Prädikat A(x) sind ∀x : (E(x, M ) ⇒ A(x)) ∃x : (E(x, M ) ∧ A(x)) (5) (6) Aussagen. Interpretation: Gleichung (5): "Für alle x aus der Menge M ist A(x) wahr." bzw. Gleichung (6): "Es gibt ein x aus der Menge M , für welches A(x) wahr ist". Für Aussagen der Form (5) und (6) führen wir folgende Abkürzungen ein, die in der Mathematik allgemein gebräuchlich ist: ∀x ∈ M : A(x) ∃x ∈ M : A(x). 3 PRÄDIKATENLOGIK ERSTER STUFE 3.2 12 Negation von Quantoren Bemerkung 3.9 (Negation von Quantoren). Für ein Prädikat A(x) gilt: ¬(∃x : A(x)) ⇐⇒ ∀x : ¬A(x), die Negation von "Es existiert ein x, sodass A(x) wahr ist" ist also "Für alle x ist A(x) falsch". Es gilt weiter: ¬(∀x : A(x)) ⇐⇒ ∃x : ¬A(x), die Negation von "Für alle x ist A(x) wahr" ist also "Es existiert ein x, für dass A(x) falsch ist". (Achtung: Die Negation der Aussage (∀x : A(x)) lautet also nicht etwa "Für alle x ist A(x) falsch"! Denn offensichtlich würde dann die Aussage und ihre Negation nicht alle Möglichkeiten abdecken: Der Fall, dass A(x) für genau zwei x falsch ist, wäre weder in der Aussage noch ihrer Negation enthalten). Lemma 3.10. Für zwei Aussagen A, B gilt: ¬(A ⇒ B) Beweis. Mittels Wahrheitstafeln: A B A ⇒ B ¬(A ⇒ B) w w w f w f f w f w w f f f w f ¬B f w f w ⇐⇒ A ∧ ¬B A ∧ ¬B f w f f ¬(A ⇒ B) ⇐⇒ (A ∧ ¬B) w w w w Korollar 3.11. Für eine Menge M und ein Prädikat A(x) gilt: ¬(∀x ∈ M : A(x)) ¬(∃x ∈ M : A(x)) ⇐⇒ ⇐⇒ ∃x ∈ M : ¬A(x), ∀x ∈ M : ¬A(x). Beweis. Es gilt ¬(∀x ∈ M : A(x)) ⇐⇒ ⇐⇒ Lemma 3.10 ⇐⇒ ⇐⇒ ¬(∀x : (E(x, M ) ⇒ A(x))) ∃x : ¬(E(x, M ) ⇒ A(x)) ∃x : E(x, M ) ∧ ¬A(x) ∃x ∈ M : ¬A(x), Der zweite Teil kann mit einer ähnlichen Rechnung bewiesen werden.