Benutzer:Dirk Hünniger/mnf

Mathe für Nicht-Freaks

Wikibooks

Was ist Mathematik?

Was ist Mathematik?

Die Mathematik ist eine für unser Leben unentbehrliche Wissenschaft. Sie hilft uns, zu vielen Fragen und Problemen Lösungen zu finden und ist für zahlreiche weitere Wissenschaften unersetzlich. Für einige Menschen besitzt sie sogar einen Wert an sich. Dabei ist die Frage, was Mathematik ist, gar nicht leicht zu beantworten. Was macht also die Mathematik aus und womit beschäftigt sie sich?

Historisch ist die Mathematik aus der Untersuchung von geometrischen Figuren und dem Rechnen mit Zahlen entstanden. Heute beschäftigt sie sich in unterschiedlichen Teilgebieten mit abstrakten Strukturen, die in der Regel durch einige wenige Grundaussagen beschrieben werden. Diese Grundaussagen heißen Axiome und alle weiteren Eigenschaften und Gesetzmäßigkeiten der Struktur werden aus den Axiomen mit Hilfe der Logik hergeleitet. Ein Beispiel für eine solche Struktur sind die natürlichen Zahlen, die durch die Peano-Axiome beschrieben werden. Ein anderes Beispiel ist die euklidische Geometrie, die durch Hilberts Axiomensystem charakterisiert wird.

Wie funktioniert Mathematik?

Skizze zum mathematischen Gebäude

Jede mathematische Theorie besitzt dabei ihre eigenen Axiome. Theorien bauen auch oftmals aufeinander auf, indem sie die Axiome einer Theorie um neue erweitern. Ob die Theorie dabei in sich stimmig ist, also keine Widersprüche erzeugt, zeigt sich erst im Laufe ihrer Entwicklung. Innerhalb einer Theorie werden aus den Axiomen weitere Aussagen hergeleitet, die man Theoreme oder Sätze nennt. Aus den neu gewonnenen Theoremen und den ursprünglichen Axiomen werden weitere Theoreme bewiesen, über die weitere Theoreme bewiesen werden und so fort. Am Ende hat man so eine Vielzahl von Sätzen hergeleitet, die eine mathematische Theorie ausmachen.

Oft wird der Aufbau einer mathematischen Theorie mit dem eines Gebäudes verglichen. Das Fundament bilden die Axiome. Darauf setzen die Theoreme auf und die Beweise sind der Mörtel, welcher alles zusammenhält. Am Ende entsteht so ein komplettes mathematisches Gebäude, die mathematische Theorie. Die Aufgabe des Mathematikers ist hier ähnlich der eines Maurers. Er findet und setzt Axiome für neue Theorien (Fundament legen) und beweist neue Theoreme (neue Steine mit Mörtel auf die Wand mauern).

Ziel einer mathematischen Theorie ist es, gewisse abstrakte Strukturen zu beschreiben und Vorhersagen über diese Strukturen zu machen. Die natürlichen Zahlen mit ihren Rechengesetzen oder Wahrscheinlichkeitsbetrachtungen sind Beispiele für solche Strukturen. Die Axiome einer Theorie legen die betrachtete Struktur fest und die Theoreme sind zusätzliche Eigenschaften der Struktur. Indem Theoreme aus den Axiomen logisch hergeleitet sind, ist garantiert, dass die Struktur die Eigenschaften besitzt, welche durch die Theoreme beschrieben werden. Dies begründet auch das Vorgehen des Beweisens. Immer, wenn man etwas findet, das alle Axiome einer Theorie erfüllt, sind dafür alle Theoreme der Theorie anwendbar, ohne dass man dies extra nachprüfen muss.

Bei der Erforschung einer mathematischen Theorie sieht man oft Muster, die häufig oder in „natürlicher Weise“ auftreten. Man gibt ihnen dann Namen, um sie einfach und kurz bezeichnen zu können. So werden neue Objekte definiert. Diese Definitionen sind entscheidend dafür, dass man kurz und trotzdem exakt über mathematische Theorien sprechen kann. Wenn wir zum Beispiel wissen, was die natürlichen Zahlen sind und wie man sie in Faktoren zerlegen kann, so stoßen wir auf die Struktur der Primzahlen (Zahlen, die sich nur durch eins und sich selbst teilen lassen). Ob und wann eine bestimmte Definition sinnvoll ist, ist durchaus nicht immer leicht zu beantworten. In Bezug auf die Primzahlen erwies es sich später als vorteilhaft, sie wie folgt zu definieren: „Eine Primzahl ist eine natürliche Zahl, die genau 2 Teiler hat.“ Weil die Eins jetzt keine Primzahl mehr ist, kann z. B. $90$ eindeutig (bis auf die Reihenfolge) durch das Produkt von vier Primzahlen ($2\cdot 3\cdot 3\cdot 5$) dargestellt werden. Bei der Beschäftigung mit mathematischen Objekten erkennt man oft weitere Muster. Beispielsweise sieht man bei Primzahlen, dass es sehr viele von ihnen gibt. Man gelangt so zur Vermutung: Möglicherweise gibt es unendlich viele Primzahlen. Ganz gleich, wie offensichtlich eine Vermutung sein kann: Man muss sie nach den strengen Prinzipien der Logik beweisen.

Oft sind mathematische Theorien durch Naturbeobachtungen oder „die Welt um uns herum“ motiviert. So erhält man intuitive Ideen von Strukturen, die man mathematisch beschreiben will. Welche Axiome man als Grundlage einer Theorie wählen sollte, ist keine einfache Frage. Ein Beispiel sind die natürlichen Zahlen: Früh begegnet uns die Idee des Zählens und wir vergleichen Mengen, indem wir die Anzahl ihrer Elemente bestimmen. Ebenso ist uns klar, wie man Zahlen addieren kann. Die Aufgabe eines Mathematikers besteht nun darin, die Struktur der natürlichen Zahlen durch Axiome zu beschreiben. Dazu werden einige einleuchtende Eigenschaften der natürlichen Zahlen festgehalten. Als Mathematiker muss man nun die „richtigen“ Axiome finden, um die Struktur vollständig zu beschreiben. Sie müssen unabhängig voneinander sein und es sollten möglichst wenige davon gesetzt werden.

Sind die Axiome aber erst einmal gesetzt, so existieren sie unabhängig von der „Welt um uns herum“ – und alle daraus logisch ableitbaren Schlussfolgerungen ebenso. Anders als formulierte Naturgesetze der Physik oder Chemie können sie nicht durch spätere Experimente widerlegt werden, sondern gelten als „unbedingt wahr“. In diesem Moment löst sich die Mathematik von den Naturbeobachtungen und ist deshalb streng genommen auch keine Naturwissenschaft mehr. Von einigen wird die Mathematik deshalb den Geisteswissenschaften zugeordnet. Heutzutage wird sie oftmals als Strukturwissenschaft bezeichnet. Wenn die Gesetze der Logik universelle Gültigkeit haben (also zu jeder Zeit und an jedem Ort stimmen), so müsste jede andere Gesellschaft, wenn sie von denselben Axiomen ausgeht, dieselbe Mathematik entwickeln wie wir – ganz egal, ob es sich dabei um Menschen oder eine außerirdische Intelligenz handeln würde. Einmal bewiesene Aussagen haben innerhalb einer mathematischen Theorie eine ewige Gültigkeit und sind nicht mehr widerlegbar.

Die Frage, ob die Logik wirklich so universell ist und welche Axiome zu wählen sind, ist jedoch eine heikle und durchaus philosophische Frage. Als Grundlage des mathematischen Schlussfolgerns wird heutzutage die formale Logik verwendet. Die Logik – traditionell ein Teil der Philosophie – ist heute ein fester Bestandteil der Mathematik. Als axiomatische Grundlage verwendet man in der modernen Mathematik die Axiome der Mengenlehre nach Ernst Zermelo und Abraham Adolf Fraenkel (kurz: ZF) und zumeist das Auswahlaxiom (ZFC, vom englischen choice). Letzteres Axiom ist nicht völlig unumstritten, da sich damit teilweise kontraintuitive Ergebnisse beweisen lassen. Andererseits ist das Auswahlaxiom jedoch für viele Bereiche der Mathematik unerlässlich.

Wird Mathematik entdeckt oder erschaffen?

Diese Frage ist eher philosophischer Natur. Es gibt hierzu zwei unterschiedliche Positionen. In der ersten, der so genannten platonischen Sichtweise sind mathematische Objekte universell vorhanden und werden vom Mathematiker entdeckt. Der Konstruktivismus demgegenüber nimmt die Position ein, dass Mathematik von Menschen erschaffen wird: Ein mathematisches Objekt kann nur dann existieren, wenn man weiß, wie es konstruiert wird. Der Mathematiker Leopold Kronecker tätigte hierzu auch den Ausspruch: „Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.“ Hier betont Kronecker den konstruktiven Charakter der Mathematik, nennt aber mit den ganzen Zahlen auch ein für ihn platonisches Element.

Welche Sichtweise du der Mathematik gegenüber einnimmst, ist dir frei überlassen.

Mathematik und die Natur

Es ist tatsächlich bemerkenswert, dass sich die Natur durch unsere Mathematik sehr gut beschreiben lässt. Galileo Galilei schrieb dazu: „Das Buch der Natur ist mit mathematischen Symbolen geschrieben.“ Fast alle Wissenschaften nutzen die Mathematik, um mit ihr Modelle über ihr jeweiliges Forschungsfeld zu erstellen: Die Physik, die Chemie, die Biologie, die Wirtschaftswissenschaften und die Geographie zählen dabei noch zu den „direktesten Anwendern“. Jedoch praktisch alle empirischen Wissenschaften führen Beobachtungen durch und brauchen die Hilfsmittel der Statistik, um ihre Aussagen überprüfen zu können.

Dass sich die mehr oder weniger alltäglichen Phänomene mit Hilfe von Mathematik gut erklären lassen, mag vielleicht nicht verwundern: Schließlich wurde die Mathematik entwickelt, um solche Phänomene zu beschreiben. Es ist jedoch erstaunlich, wie universell die Methoden der Mathematik sind. Sie sind auch auf neuere Beobachtungen anwendbar und auf Phänomene, die nichts mit unserem Alltag zu tun haben: die Berechnungen von Planetenbahnen etwa oder elektromagnetische Felder und Ströme. Diese Dinge wurden entdeckt, als die Mathematik schon entwickelt war und nicht „mal eben angepasst“ werden konnte. Noch viel verblüffender ist die Tatsache, dass Mathematiker manchmal völlig abstrakte Konzepte entwickeln, ohne über eine mögliche Anwendung nachzudenken und diese Strukturen sich erst lange Zeit später in Naturbeobachtung wiederfinden, sozusagen „in der Natur realisiert“ sind. Hierfür gibt es streng genommen keinerlei logischen Grund. Schon Albert Einstein stellte sich die Frage, wie es kommt, dass die Mathematik „auf die Gegenstände der Wirklichkeit so vortrefflich passt.“

Viele mathematische Bereiche hängen auch sehr eng mit Naturbeobachtungen zusammen. Deswegen unterscheidet man häufig die reine von der angewandten Mathematik. Die Abgrenzung ist dabei oftmals unscharf, doch gibt es einige Forschungszweige, die man klar der einen oder der anderen Richtung zuweisen kann. „Algebra“ und „Zahlentheorie” zählen beispielsweise zur reinen Mathematik. Die Frage, wie man mit Hilfe von Computern am effizientesten Klimasimulationen durchführen kann, ist jedoch sicherlich angewandt und fällt in den Bereich der „Numerik“.

Teilgebiete der Mathematik

Die ältesten Teilgebiete der Mathematik sind die Geometrie und die Zahlentheorie. Die Geometrie beschäftigt sich mit Figuren in der Ebene wie Dreiecken oder Kreisen und mit Körpern im Raum wie Pyramiden, Quadern oder Kugeln. Die Zahlentheorie, auch Arithmetik genannt, untersucht die Eigenschaften der Zahlen, vor allem der natürlichen Zahlen $0,1,2,\dots$, und die damit verbundenen Rechengesetze. Diese beiden Teilgebiete werden schon seit tausenden von Jahren betrieben. Sie waren nicht nur den Babyloniern, den Ägyptern und den Griechen bekannt, sondern auch den Chinesen, Indern und den Mayas.

Die grundlegenden Gebiete der modernen Mathematik sind Analysis und Lineare Algebra. Sie werden an den Hochschulen in der Regel als mehrsemestrige Kurse angeboten. Schwerpunkt in der Analysis sind Grenzwertprozesse wie Ableitungen oder Integrale. Die Lineare Algebra behandelt demgegenüber Vektorräume und lineare Abbildungen zwischen diesen Vektorräumen.

Eine Sonderrolle als Teilgebiete der Mathematik spielen seit dem 20. Jahrhundert die Logik und die Mengenlehre. Sie haben eine Doppelrolle: sie sind einerseits Teilgebiete der Mathematik und nutzen mathematische Methoden, stellen aber andererseits die Grundlagen für die gesamte Mathematik zur Verfügung. Die rasante Entwicklung der Naturwissenschaften, der Technik und der Informatik machte ein Nachdenken über die Grundlagen der Mathematik, und damit eine Beschäftigung mit Logik und Mengenlehre, notwendig.

Aus den Anfängen der Mathematik hat sich eine Vielzahl von weiteren Teilgebieten entwickelt. Der Brockhaus nennt 11 Teilgebiete:

• Geometrie
• Zahlentheorie
• Algebra
• Mengenlehre
• Logik
• Analysis
• Funktionentheorie, -analysis
• Topologie, Graphentheorie
• Wahrscheinlichkeitstheorie und Statistik
• Komplexitätstheorie
• Numerische Mathematik

Im Wikipedia-Artikel „Teilgebiete der Mathematik“ werden 21 Teilgebiete genannt.

In der Funktionentheorie werden komplexe Funktionen analysiert. Die Topologie beschäftigt sich mit der Verformung von Körpern, die Graphentheorie mit Knoten und Kanten. Die Wahrscheinlichkeitstheorie untersucht zufällige Ereignisse, die Statistik entwickelt Methoden zur Auswertung von Messdaten. In der Numerischen Mathematik werden Berechnungsverfahren ermittelt und die Komplexitätstheorie untersucht den Aufwand von Rechenverfahren.

Charakteristisch für die Mathematik sind fließende Übergänge von einem Teilgebiet zum anderen. Immer wieder werden die in einem Teilgebiet entwickelten Methoden auch in anderen Teilgebieten verwendet. Daher ist es kaum möglich, die Teilgebiete exakt voneinander abzugrenzen.

Aussagenlogik

Mathematische Symbole und Zeichen.

In den beiden vorangegangenen Kapiteln hast du Aussagen und Junktoren kennengelernt. Mit Hilfe der Junktoren kann man aus Aussagen weitere Aussagen erzeugen. Wir hatten auch gesehen, dass in der Mathematik eine formalisierte Sprache benutzt wird. Das hat mehrere Gründe:

• Zum einen ist unsere natürliche Sprache nicht eindeutig. Die Eindeutigkeit der Begriffe und Zusammenhänge ist aber für die Mathematik ganz wesentlich.
• Zum anderen werden in der Mathematik viele abstrakte Sachverhalte beschrieben und analysiert, für die neue Begriffe mit einer genau festgelegten Bedeutung benötigt werden.

Deshalb benutzt die Mathematik eine künstliche Sprache, die als formale Sprache bezeichnet wird. Wir werden diese Sprache schrittweise vorstellen und beginnen damit in diesem Kapitel. Die weiteren Schritte folgen in der Prädikatenlogik und in der Klassenlogik.

Die folgenden Definitionen erscheinen sehr formal, insbesondere dann, wenn ihr zum ersten Mal damit konfrontiert werdet. Diese formale Strenge hilft jedoch dabei, Fehlschlüsse zu vermeiden und die Mathematik auf eine sichere Grundlage zu stellen.

Die Sprache der Aussagenlogik

Für die Logik ist die formale Sprache besonders wichtig, denn mit Hilfe der Logik werden ja die mathematischen Beweise geführt. Beweise verlaufen nach ganz bestimmten Regeln. Das Einhalten dieser Regeln muss automatisiert nachprüfbar sein! Und das geht in einer formalisierten Sprache am besten. Die Sprache, in der Aussagen mit Junktoren verknüpft werden, ist die Sprache der Aussagenlogik. Wie unsere natürliche Sprache hat sie ein Alphabet:

Definition (Alphabet der Aussagenlogik)

Die Sprache der Aussagenlogik hat drei Arten von Zeichen:

1. die Aussagenkonstanten $K_{0},K_{1},K_{2},\dots$, ${\mathsf {W}}$ und ${\mathsf {F}}$,
2. die Junktoren $\neg$, $\land$, $\lor$, ${\dot {\lor }}$, $\Rightarrow$ und $\Leftrightarrow$,
3. die Klammern $($ und $)$.

Die Zeichen heißen ${\mathsf {W}}$ (Wahr) und ${\mathsf {F}}$ (Falsch), die Junktoren $\neg$ (Negation), $\land$ (Konjunktion), $\lor$ (Disjunktion), ${\dot {\lor }}$ (Kontravalenz), $\Rightarrow$ (Implikation) und $\Leftrightarrow$ (Äquivalenz).

Anmerkung: Genau genommen bestehen die Konstanten selbst aus mehreren Zeichen, dem Buchstaben $K$ und einer Zahl. Wir wollen die Konstanten hier aber als eine Einheit betrachten. Es ist nicht weiter wichtig, wie sie genau realisiert werden. Wichtig ist nur, dass wir ausreichend viele Konstanten haben und bei Bedarf immer noch ein paar neue hinzunehmen können.

Aus diesen Zeichen können nach bestimmten Regeln Wörter gebildet werden, die in diesem Zusammenhang Formeln oder wohlgeformte Zeichenreihen genannt werden. Zeichenreihen entstehen einfach dadurch, dass Zeichen aus dem Alphabet hintereinander geschrieben werden, zum Beispiel so: $(K_{3}\land {\mathsf {W}}\lor \neg K_{0}(\Rightarrow$. Aber das ist keine Formel!

Definition (Formeln der Aussagenlogik)

Die Formeln der Aussagenlogik werden nach folgenden Regeln gebildet:

1. Jede Aussagenkonstante ist eine Formel, ${\mathsf {W}}$ und ${\mathsf {F}}$ sind Formeln.
2. Ist $A$ eine Formel, so ist auch $\neg A$ eine Formel.
3. Sind $A$ und $B$ Formeln, so sind auch $(A\land B)$, $(A\lor B)$, $(A\;\;\!\!{\dot {\lor }}\;\;\!\!B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$ Formeln.

Es gibt keine weiteren Formeln.

Eine solche Definition wird rekursiv (lat. zurückgehend) genannt, weil bei der Erzeugung weiterer Formeln auf bereits erzeugte Formeln zurückgegriffen wird.

Beispiel für eine Formel

Um zu zeigen, wie diese Regeln angewendet werden, zeigen wir, dass $(\neg (K_{1}\Leftrightarrow K_{2})\Leftrightarrow (K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2}))$ eine Formel der Aussagenlogik ist:

Zeile	Formel	Begründung
1	$K_{1}$	nach Regel 1, $K_{1}$ ist eine Aussagenkonstante
2	$K_{2}$	nach Regel 1, $K_{2}$ ist eine Aussagenkonstante
3	$(K_{1}\Leftrightarrow K_{2})$	nach Regel 3 angewendet auf Zeile 1 und 2
4	$\neg (K_{1}\Leftrightarrow K_{2})$	nach Regel 2 angewendet auf Zeile 3
5	$(K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2})$	nach Regel 3 angewendet auf Zeile 1 und 2
6	$(\neg (K_{1}\Leftrightarrow K_{2})\Leftrightarrow (K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2}))$	nach Regel 3 angewendet auf Zeile 4 und 5

Beweis über den Aufbau der Formeln

Die rekursive Definition der Formeln erlaubt ein besonderes Beweisverfahren. Um eine Behauptung für alle Formeln zu beweisen, genügen zwei Schritte:

1. Im ersten Schritt wird die Behauptung für die Aussagenkonstanten $K_{i}$ und für ${\mathsf {W}}$ und ${\mathsf {F}}$ gezeigt.
2. Im zweiten Schritt wird gezeigt, dass sich die Behauptung unter den Regeln vererbt. Das heißt Folgendes:
   • Wenn die Behauptung für eine Formel $A$ gilt, dann gilt sie auch für die Formel $\neg A$.
   • Wenn die Behauptung für die Formeln $A$ und $B$ gilt, dann gilt sie auch für die Formel $(A\land B)$, $(A\lor B)$, $(A\;\;\!\!{\dot {\lor }}\;\;\!\!B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$.

Es ist klar, dass die Behauptung dann für alle Formeln gelten muss, denn Formeln können ja nur aufgrund dieser Regeln entstehen! Wir zeigen als Beispiel den folgenden einfachen Satz:

Satz

Jede Formel enthält genauso viele linke wie rechte Klammern.

Beweis

1. Für beliebige Aussagenkonstanten $K_{i}$ und für ${\mathsf {W}}$ und ${\mathsf {F}}$ ist das richtig, denn sie enthalten gar keine Klammern.
2. Wenn $A$ genauso viele linke wie rechte Klammern enthält, dann gilt das auch für $\neg A$, denn bei der Bildung der Negation kommen keine Klammern dazu. Haben schließlich $A$ und $B$ jeweils gleich viele linke wie rechte Klammern, so kommen bei $(A\land B)$ genau eine linke und eine rechte Klammer dazu. Also bleiben es gleich viele. So ist es auch bei den weiteren Regeln für $(A\lor B)$, $(A\;\;\!\!{\dot {\lor }}\;\;\!\!B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$. ✔

Klammerersparnis, Schreibweisen

Bei der Schreibweise von Formeln lassen wir die Außenklammern in der Regel weg und erlauben uns auch andere Freiheiten. Es muss nur immer klar sein, welche Formel im Sinne der obigen Definition gemeint ist. Natürlich übernehmen wir auch die Bindungsregeln aus dem Kapitel über Junktoren, um Klammern wegzulassen:

1. Negation $\neg$
2. Konjunktion $\land$
3. Disjunktion $\lor$
4. Implikation $\Rightarrow$
5. Äquivalenz $\Leftrightarrow$

Falls es dem Verständnis dient, setzen wir auch zusätzliche Klammern.

Aussagen formalisieren

Wir greifen nun einige Aussagen auf, die wir schon im Kapitel Junktoren angesprochen haben. Wenn wir Aussagen formalisieren, dann heißt das nichts anderes, als sie in eine Formel zu übersetzen, die der Aussage möglichst gut entspricht.

Beispiel 1: Zwei Aussagen werden mit dem Junktor und verbunden.

„$2$ ist kleiner als $36$ und $5$ ist gerade.“

Zurzeit haben wir nur die Möglichkeit, die beiden Aussagen durch eine Konstante wiederzugeben, sagen wir durch $K_{1}$ („$2$ ist kleiner als $36$“) und $K_{2}$ („$5$ ist gerade“). Dann lautet die formalisierte Aussage einfach:

$K_{1}\land K_{2}$

Da es hierbei auf die Konstanten $K_{1}$ und $K_{2}$ gar nicht ankommt, verwendet man einfach auch die Variablen $A$ und $B$ und schreibt $A\land B$ für die formalisierte Aussage. Wir wissen aber aus dem Zusammenhang, dass damit eine exakte Formel der Aussagenlogik gemeint ist.

Anmerkung: Wir werden in den Kapiteln Prädikatenlogik und Klassenlogik weitere Möglichkeiten kennenlernen, Aussagen besser zu formalisieren.

Verständnisfrage: Formalisiere die folgenden Aussagen:

1. Wenn Berlin in Deutschland liegt und der Rhein durch Deutschland fließt, dann liegt Berlin am Rhein.
2. Teilt $6$ eine natürliche Zahl $n$, dann wird $n$ entweder von $2$ oder von $3$ geteilt.
3. Es gibt unendlich viele Primzahlen.

Antwort:

1. Sei $K_{1}:=$ Berlin liegt in Deutschland, $K_{2}:=$ Der Rhein fließt durch Deutschland, $K_{3}:=$ Berlin liegt am Rhein. Dann lautet die Formalisierung $(K_{1}\land K_{2})\Rightarrow K_{3}$. Die Außenklammern haben wir nach der Klammerersparnisregel weggelassen.
2. $A\Rightarrow (B\;\;\!\!{\dot {\lor }}\;\;\!\!C)$, wobei $A:=6{\text{ teilt }}n$, $B:=2{\text{ teilt }}n$ und $C:=3{\text{ teilt }}n$ bedeuten. Hier haben wir für die Konstanten einfach $A,B,C$ anstelle von $K_{1},K_{2},\dots$ verwendet, weil ja klar ist, dass damit in diesem Zusammenhang Aussagenkonstanten gemeint sind.
3. Diese Aussage enthält keine Junktoren. In der Aussagenlogik kann man sie nur durch eine Konstante formalisieren.

Teilformeln

Beim rekursiven Aufbau einer Formel $A$ erhält man zwischendurch weitere Formeln. Diese Formeln werden Teilformeln genannt. Die genaue Definition ist natürlich ebenfalls rekursiv. Teilformeln, die keine echten Teilformeln haben, heißen atomare Formeln.

Definition (Teilformeln, atomare Formeln)

1. Die Aussagenkonstanten $K_{i}$ und die Formeln ${\mathsf {W}}$ und ${\mathsf {F}}$ sind atomare Formeln und Teilformeln von sich selbst.
2. Die Teilformeln von $\neg A$ sind die Teilformeln von $A$ und $A$ selbst. Die Teilformeln von $(A\land B)$, $(A\lor B)$, $(A\;\;\!\!{\dot {\lor }}\;\;\!\!B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$ sind die Teilformeln von $A$ und $B$, sowie $A$ und $B$ selbst.

Verständnisfrage: Welche Teilformeln hat die im Beispiel oben erstellte Formel $(\neg (K_{1}\Leftrightarrow K_{2})\Leftrightarrow (K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2}))$?

Antwort:

Atomere Formeln: $K_{1}$ und $K_{2}$. Weitere Teilformeln: $(K_{1}\Leftrightarrow K_{2})$, $(K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2})$, $\neg (K_{1}\Leftrightarrow K_{2})$ und die Formel $(\neg (K_{1}\Leftrightarrow K_{2})\Leftrightarrow (K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2}))$ selbst.

Junktor

Junktoren sind bestimmte Symbole in der Aussagenlogik, die Aussagen miteinander verbinden oder in eine Beziehung stellen. Das Wort Junktor stammt vom lateinischen Wort „iungere“ ab, was so viel wie „verknüpfen, verbinden“ bedeutet. Junktoren kann man deshalb gut mit Bindewörtern vergleichen, wie sie in natürlichen Sprachen vorkommen (Beispiele für Bindewörter sind „und“, „oder“, „aber“). Während Junktoren in der Logik Aussagen miteinander verknüpfen, verbinden Bindewörter einzelne Satzteile in einer natürlichen Sprache. Dementsprechend gibt es (wie du noch sehen wirst) in der deutschen Sprache für Junktoren ein äquivalentes oder ähnliches Bindewort.

Es gibt aber einen entscheidenden Unterschied: Die Bedeutung eines Junktors ist eindeutig definiert, wohingegen Bindewörter oftmals eine unterschiedliche Bedeutung (je nach Kontext, in dem sie verwendet werden) besitzen. So bedeutet „oder“ im Satz „Gehst du nun ins Kino oder bleibst du zu Hause?“, dass die angesprochene Person die Entscheidung hat, entweder ins Kino zu gehen oder zu Hause zu bleiben (es geht nur eines von beiden). Im Satz „Er freut sich über seinen Lottogewinn oder seine neue Freundin“ besitzt „oder“ eher die Bedeutung eines „und/oder“ (die Person kann sich sowohl über den Lottogewinn als auch über die neue Freundin freuen). Im Satz „Gehst du nun ins Kino oder ins Restaurant?“ kann „oder“ sowohl ausschließend als auch einschließend gemeint sein.

Es ist wichtig, dass du die Definitionen und Eigenschaften der einzelnen Junktoren genau kennst (insbesondere diejenigen Eigenschaften, die scheinbar der Intuition widersprechen), da dir sonst leicht Fehler in der Anwendung passieren. Es ist auch wichtig, dass du klar zwischen Bindewörtern der natürlichen Sprache und aussagelogischen Junktoren unterscheidest.

Einführende Beispiele

Nimm als Beispiel die folgenden zwei Aussagen:

Aussage $A$: „$36$ ist durch 2 teilbar.“

Aussage $B$: „$5$ ist gerade.“

Diese beiden Aussagen kannst du miteinander verknüpfen, indem du den Junktor „und“ verwendest. Du erhältst dadurch die Aussage: „$36$ ist durch 2 teilbar und $5$ ist gerade.“ Beachte dabei, dass hier „und“ als Junktor verwendet wird. Du kannst aber auch die beiden Aussagen auf eine ganz andere Art und Weise miteinander verknüpfen, nämlich: „Wenn $36$ durch 2 teilbar ist, dann ist $5$ gerade.“ Hier ist der Junktor der „Wenn-dann“-Junktor, der beide Aussagen miteinander verknüpft. Beide Beispiele zur Übersicht:

Aussage „$A$ und $B$“: $\overbrace {36{\text{ ist durch }}2{\text{ teilbar}}} ^{\text{Teilaussage 1}}\ {\color {Orange}\overbrace {\text{ und }} ^{\text{Junktor}}}\ \overbrace {5{\text{ ist gerade}}} ^{\text{Teilaussage 2}}$

Aussage „Wenn $A$, dann $B$“: ${\color {Orange}\overbrace {\text{ Wenn }} ^{\text{Junk-}}}\overbrace {36{\text{ ist durch }}2{\text{ teilbar}}} ^{\text{Teilaussage 1}}\ {\color {Orange}\overbrace {\text{dann}} ^{\text{tor}}}\ \overbrace {5{\text{ ist gerade}}} ^{\text{Teilaussage 2}}$

Für Junktoren werden Symbole verwendet. So ist für den Junktor „und“ das Symbol $\land$ und für den „Wenn-dann“-Junktor das Symbol $\Rightarrow$ gebräuchlich. Damit können obige beide Aussagen folgendermaßen dargestellt werden:

Aussage „$A$ und $B$“: $\overbrace {36{\text{ ist durch }}2{\text{ teilbar}}} ^{\text{Teilaussage 1}}\ {\color {Orange}\overbrace {\land } ^{\text{Junktor}}}\ \overbrace {5{\text{ ist gerade}}} ^{\text{Teilaussage 2}}$

Aussage „Wenn $A$, dann $B$“: $\overbrace {36{\text{ ist durch }}2{\text{ teilbar}}} ^{\text{Teilaussage 1}}\ {\color {Orange}\overbrace {\Rightarrow } ^{\text{Junktor}}}\ \overbrace {5{\text{ ist gerade}}} ^{\text{Teilaussage 2}}$

Offene Frage: Überlege dir einige mathematische Aussagen. Welche Verknüpfungen sind in diesen Aussagen enthalten? Welche verknüpften Teilaussagen kannst du ausmachen?

Verständnisfrage: Nimm den Satz: „Wenn $x$ eine natürliche Zahl ist und $x$ gerade ist, dann ist $x$ durch 2 teilbar.“ Wie kannst du diesen Satz in Teilaussagen und Junktoren zerlegen?

${\begin{aligned}\overbrace {\left(\underbrace {x{\text{ ist eine natürliche Zahl}}} _{\mathrm {Teilaussage} }\ \underbrace {\mathrm {und} } _{\mathrm {Junktor} }\ \underbrace {x\mathrm {\ ist\ gerade} } _{\mathrm {Teilaussage} }\right)} ^{\mathrm {Teilaussage} }\\[0.5em]\qquad \overbrace {\mathrm {Wenn\ } \ldots \mathrm {,\ dann\ } \ldots } ^{\mathrm {Junktor} }\qquad \overbrace {x\mathrm {\ ist\ durch\ } 2\mathrm {\ teilbar} } ^{\mathrm {Teilaussage} }\end{aligned}}$

Und mit Symbolen:

$\overbrace {\left(\underbrace {x{\text{ ist eine natürliche Zahl}}} _{\mathrm {Teilaussage} }\ \underbrace {\land } _{\mathrm {Junktor} }\ \underbrace {x\mathrm {\ ist\ gerade} } _{\mathrm {Teilaussage} }\right)} ^{\mathrm {Teilaussage} }\qquad \overbrace {\Rightarrow } ^{\mathrm {Junktor} }\qquad \overbrace {x\mathrm {\ ist\ durch\ } 2\mathrm {\ teilbar} } ^{\mathrm {Teilaussage} }$

Junktoren verbinden nur Aussagen

Du solltest dir auch merken, dass Junktoren nur Aussagen miteinander verbinden. Die durch den Junktor verbundenen Teile müssen also selbst wieder Aussagen und keine Satzfragmente oder Ähnliches sein. Nimm hierzu den Beispielsatz:

„7 und 42 sind natürliche Zahlen.“

Hier ist „und“ kein Junktor! Wenn dem so wäre, dann müssten die Satzteile „7“ sowie „42 sind natürliche Zahlen“ Aussagen sein, was sie aber nicht sind:

${\color {OliveGreen}\underbrace {7} _{\text{Satzfragment }}}{\color {Red}\overbrace {\text{ und }} ^{\text{ kein Junktor }}}{\color {Blue}\underbrace {42{\text{ sind natürliche Zahlen}}} _{\text{grammatikalisch falsch}}}$

Anders sieht die Sache aus, wenn man obigen Satz leicht umformuliert:

„7 ist eine natürliche Zahl und 42 ist eine natürliche Zahl.“

Hier ist „und“ ein Junktor, weil die einzelnen Teile wiederum Aussagen sind:

${\color {OliveGreen}\underbrace {7{\text{ ist eine natürliche Zahl }}} _{\text{Aussage}}}{\color {Orange}\overbrace {\text{ und }} ^{\text{ Junktor }}}{\color {Blue}\underbrace {\ 42{\text{ ist eine natürliche Zahl}}} _{\text{Aussage}}}$

Du siehst an obigem Beispiel gut, dass nicht jedes Bindewort der natürlichen Sprache automatisch ein Junktor ist und dass sauber zwischen Junktoren und deren zugeordneter Übersetzung unterschieden werden muss.

Die Junktoren

Im Folgenden stellen wir die für die Mathematik wichtigsten Junktoren vor. Um eine übersichtliche Notation zu erreichen, werden wir, wie es in der Mathematik üblich ist, als Platzhalter für Aussagen Großbuchstaben wie $A$, $B$ und $C$ verwenden. Beachte, dass diese Platzhalter auch für Aussagen stehen können, die selbst wieder eine Verknüpfung von mehreren Aussagen sind. Neben jedem Junktor findest du eine sogenannte Wahrheitstabelle des jeweiligen Junktors. Sie gibt den Wahrheitswert der zusammengesetzten Aussage in Abhängigkeit der Wahrheitswerte der einzelnen Teilaussagen wieder. $W$ steht dabei für „wahr“ und $F$ steht für „falsch“.

Negation – die Verneinung einer Aussage

Wahrheitstabelle: Negation

$A$	$\neg A$
$\mathrm {F}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {F}$

Der erste Junktor, den wir vorstellen, ist die Verneinung einer Aussage, welche Negation genannt wird. Die Negation kehrt den Wahrheitswert einer Aussage um: Aus „wahr“ wird durch Negation „falsch“ und analog aus „falsch“ wird „wahr“. Mit anderen Worten: Eine negierte Aussage $A$ ist genau dann wahr, wenn die Aussage $A$ falsch ist. Dies kannst du auch rechts der Wahrheitstabelle zur Negation entnehmen. Das Symbol der Negation ist $\neg$. Wenn du also die Verneinung einer Aussage $A$ ausdrücken möchtest, so schreibst du $\neg A$ auf (gesprochen „nicht A“). Es gibt aber auch die Notation ${\overline {A}}$ (gesprochen „A quer“) beziehungsweise ${\sim }A$, um die Negation von $A$ aufzuschreiben.

Es muss nicht unbedingt die Sonne scheinen, wenn es nicht regnet.

Es ist wichtig, dass du lernst, wie man eine Aussage richtig negiert. So ist zum Beispiel die Negation der Aussage „Es regnet“ nicht die Aussage „Es scheint die Sonne“, sondern die Aussage „Es regnet nicht“. Es könnte ja zum Beispiel sein, dass es bewölkt ist, es aber nicht regnet. Um eine logische Aussage zu negieren, gibt es einfache Umformungsregeln, die du beachten musst. Diese werden wir später im Kapitel „Aussagen negieren“ erklären.

Konjunktion – die Und-Verknüpfung

Wahrheitstabelle: Konjunktion

$A$	$B$	$A\land B$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {W}$

Eine wichtige Verknüpfung zwischen zwei Aussagen $A$ und $B$ ist die Konjunktion, die Und-Verknüpfung „$A$ und $B$“. Das Symbol für „und“ ist $\land$ (als Merkhilfe kannst du an ein großes A vom Englischen „and“ für „und“ denken). Wenn du also notieren möchtest, dass sowohl die Aussage $A$ als auch die Aussage $B$ wahr ist, schreibst du $A\land B$. Wie du aus der Wahrheitstabelle entnehmen kannst, ist eine Aussage $A\land B$ dann und nur dann wahr, wenn sowohl $A$ als auch $B$ wahr sind. Wenn bereits eine der beiden Teilaussagen falsch ist, ist die gesamte Aussage falsch. Dies deckt sich mit dem alltäglichen Gebrauch des Bindewortes „und“.

Disjunktion – die Oder-Verknüpfung

Wahrheitstabelle: Disjunktion

$A$	$B$	$A\lor B$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {W}$

Außerdem kann man Aussagen noch über eine Oder-Verknüpfung miteinander verbinden. Dazu gibt es in der Logik die Disjunktion mit dem Symbol $\lor$. Wenn du sagen möchtest, dass mindestens eine der beiden Aussagen $A$, $B$ wahr ist, schreibst du $A\lor B$ („$A$ oder $B$“ ausgesprochen).

Beachte: In der Umgangssprache besitzt „oder“ zwei verschiedene Lesarten: So benutzen wir „oder“ im Sinne von „und/oder“ („Dieses Angebot richtet sich an junge Leute oder Kunstinteressierte.“) und in der Bedeutung als „entweder oder“ („Kommst du mit? Ja oder nein?“). Die Disjunktion ist das nicht-ausschließende Oder im Sinne von „mindestens“ („Der Bus hält, wenn jemand einsteigen oder jemand aussteigen will“).

Kontravalenz – die Entweder-oder-Verknüpfung

Wahrheitstabelle: Kontravalenz

$A$	$B$	$A\,{\dot {\lor }}\,B$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {F}$

Die Kontravalenz ist ein Junktor im Sinne einer Entweder-oder-Verknüpfung. Man benutzt für sie das Symbol ${\dot {\lor }}$ („exklusiv oder“). Eine Aussage $A\,{\dot {\lor }}\,B$ ist genau dann wahr, wenn entweder $A$ oder $B$, aber nicht beide Aussagen gleichzeitig wahr sind. Die Kontravalenz entspricht damit dem ausschließenden Oder im Sinne von „Dieses Jahr gewinnt (entweder) Bayern oder Dortmund die deutsche Fußballmeisterschaft“. Die Kontravalenz wird in der Mathematik seltener verwendet als die Disjunktion.

Implikation – die Wenn-dann-Verknüpfung

Wahrheitstabelle: Implikation

$A$	$B$	$A\Rightarrow B$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {W}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {W}$

Eine wichtige Verknüpfung in der Aussagenlogik ist die Implikation, welche als Wenn-dann-Verknüpfung aufgefasst werden kann. Ihr Symbol ist $\Rightarrow$; weitere weniger gebräuchliche Schreibweisen sind $\rightarrow$ und $\supset$. So bezeichnet $A\Rightarrow B$ die Aussage „Wenn $A$, dann $B$“. Weitere Sprechweisen für $A\Rightarrow B$ sind „Aus $A$ folgt $B$“, „$A$ impliziert $B$“, „$A$ ist eine hinreichende Bedingung für $B$“ und „$B$ ist eine notwendige Bedingung für $A$“. Dabei wird $A$ Prämisse und $B$ Konklusion genannt:

$\overbrace {\underbrace {A} _{\text{Prämisse}}\Rightarrow \underbrace {B} _{\mathrm {Konklusion} }} ^{\mathrm {Implikation} }$

Eine Straße kann nass sein, ohne dass es regnet.

Die Bedeutung von $A\Rightarrow B$ ist demnach, dass wenn bereits die Aussage $A$ gilt, auch die Aussage $B$ gelten muss. Dabei muss aber kein kausaler Zusammenhang zwischen $A$ und $B$ vorliegen (was du vielleicht durch die Formulierung „Wenn $A$, dann $B$“ vermuten könntest). So ist die Aussage $4>1\Rightarrow {\sqrt {9}}=3$ („Aus $4>1$ folgt ${\sqrt {9}}=3$“) eine wahre Aussage, auch wenn aus der Tatsache, dass $4>1$ ist, nicht kausal die Tatsache folgt, dass ${\sqrt {9}}=3$ ist.

Leicht begeht man bei der Implikation $A\Rightarrow B$ den Fehler zu glauben, dass dann auch $B\Rightarrow A$ gelten müsse. So gehen einige davon aus, dass aus dem Satz „Wenn es regnet, ist die Straße nass“ folgen müsse, dass, wenn die Straße nass ist, es auch regne. Dies ist aber nicht der Fall! So kann die Straße aufgrund einer Straßenreinigung nass sein oder es kann vor kurzem geregnet haben, ohne dass es momentan regnet.

Warnung

Viele mathematische Sätze sind als Implikationen definiert (aus gewissen Bedingungen $A$ folgt eine Tatsache $B$). Deshalb ist es wichtig, dass du dir merkst, dass eine Implikation nicht umkehrbar ist (der Pfeil geht schließlich nur von $A$ nach $B$ und nicht umgekehrt). Sonst passiert es dir schnell, dass du Fehler in deinen Beweisen machst.

Frage: Überlege dir selbst mathematische Beispiele, mit denen du andere Leute überzeugen kannst, dass Implikationen im Allgemeinen nicht umkehrbar sind.

Ein Beispiel ist die Implikation „Wenn viel Schnee draußen liegt, ist es kalt“. Die Umkehrung wäre „Wenn es kalt ist, dann liegt Schnee draußen”. Nun hat jeder von uns schon kalte Tage ohne Schnee erlebt, womit die umgekehrte Implikation nicht wahr sein kann.

Ein weiteres Beispiel ist:

$f(x_{0}){\text{ ist in }}x_{0}{\text{ differenzierbar. }}\land \ f(x_{0}){\text{ ist ein lokales Extremum.}}\ \Rightarrow \ f'(x_{0})=0$

Die Umkehrung wäre die Aussage:

Wenn die Ableitung einer Funktion $f$ an der Stelle $x_{0}$ gleich null ist, dann ist $f$ in $x_{0}$ differenzierbar und besitzt in $x_{0}$ ein lokales Extremum.

Ein Gegenbeispiel ist die Funktion $f(x)=x^{3}$. Bei dieser Funktion ist die erste Ableitung bei $x=0$ null, da $f'(x)=3x^{2}$ und $3\cdot 0^{2}=0$ ist, aber diese Funktion besitzt keine lokale Extremstelle bei $x=0$.

Beachte auch, dass nach der Wahrheitstabelle die Implikation bereits dann wahr ist, wenn die Prämisse $A$ falsch ist. So ist die Aussage $2+3=11\Rightarrow 7+5=4$ („Wenn $2+3=11$ ist, dann ist $7+5=4$“) eine wahre Aussage, auch wenn $7+5\neq 4$ ist. Dieses Prinzip der Implikation wird ex falso quodlibet genannt oder zu Deutsch: „Aus Falschem folgt Beliebiges.“ Demnach ist eine Implikation nur dann und genau dann falsch, wenn die Prämisse $A$ wahr ist und die Konklusion $B$ falsch ist. Diese Tatsache kann zu recht kontraintuitiven Aussagen führen, die aber dennoch wahr sind. Betrachte dazu folgende Verständnisfrage:

Verständnisfrage: Welche der folgenden Aussagen sind wahr und welche sind falsch?

1. Wenn Berlin in England liegt, ist Schnee schwarz.
2. Wenn Berlin in England liegt, ist Schnee weiß.
3. Wenn Berlin in Deutschland liegt, ist Schnee schwarz.
4. Wenn Berlin in Deutschland liegt, ist Schnee weiß.
5. Wenn der Mond aus grünem Käse besteht, ist heute Sonntag.

Antwort: Die Aussagen (1) und (2) sind wahr, weil bereits die Prämisse „Berlin liegt in England“ falsch ist. Auch Aussage (4) ist wahr, weil sowohl die Prämisse als auch die Konklusion wahr ist. Nur Aussage (3) ist falsch (Prämisse ist wahr und Konklusion falsch). Aussage (5) ist an jedem Tag wahr.

Äquivalenz – die Genau-dann-wenn-Verknüpfung

Wahrheitstabelle: Äquivalenz

$A$	$B$	$A\Leftrightarrow B$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {W}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {W}$

Der letzte Junktor, den wir vorstellen möchten, ist die Äquivalenz. Die Äquivalenz wird mit dem Doppelpfeil $\Leftrightarrow$ dargestellt. Die Sprechweise von $A\Leftrightarrow B$ ist dabei „Genau dann $A$, wenn $B$“, „$A$ ist gleichwertig mit $B$“ oder „$A$ ist äquivalent zu $B$“. Eine Aussage $A\Leftrightarrow B$ ist genau dann und nur dann wahr, wenn die beiden Aussagen $A$ und $B$ denselben Wahrheitswert besitzen. Ist eine der beiden Aussagen wahr und die andere falsch, ist $A\Leftrightarrow B$ falsch. Die Äquivalenz wird auch Bijunktion genannt.

Die Bedeutung der Aussage $A\Leftrightarrow B$ ist dabei, dass aus der Aussage $A$ die Aussage $B$ folgt und dass aus der Aussage $B$ die Aussage $A$ folgt. Dies erkennst du auch am Doppelpfeil – während bei der Äquivalenz der Pfeil von $A$ nach $B$ und umgekehrt geht, geht der Pfeil in der Implikation nur in eine Richtung (und zwar von der Prämisse zur Konklusion). Die Äquivalenz drückt damit eine Gleichwertigkeit zwischen zwei Aussagen aus, da zwei in Äquivalenz stehende Aussagen immer denselben Wahrheitswert besitzen (genau so ist die Äquivalenz definiert).

Verständnisfrage: Überlege dir Beispiele für eine Äquivalenzbeziehung.

Ein einfaches Beispiel aus der Mathematik ist

„Genau dann wenn $x$ durch 2 teilbar ist, ist $x$ gerade.“

Ein weiteres Beispiel aus dem Alltag ist

„Genau dann wenn Schaltjahr ist, hat der Februar 29 Tage.“

Ein Schaltjahr ist nämlich als ein solches Jahr definiert, wo der Februar 29 Tage hat.

Verständnisfrage: Sei $A\Leftrightarrow B$. Ist dann $A$ notwendige oder hinreichende Bedingung von $B$ und wie sieht es umgekehrt aus?

Weil bei $A\Leftrightarrow B$ aus $A$ die Aussage $B$ folgt und umgekehrt, ist $A$ sowohl notwendige als auch hinreichende Bedingung für $B$ und umgekehrt.

Bindungsreihenfolge der Junktoren (Präzedenzregeln)

Aus der Arithmetik kennst du bereits das Phänomen, dass bestimmte Operatoren stärker binden als andere. So bindet die Multiplikation $\cdot$ stärker als die Addition $+$ („Punktrechnung geht vor Strichrechnung“). Beispielsweise muss man $5+4\cdot 2$ als $5+(4\cdot 2)$ lesen. Jedoch ist diese Bindungsreihenfolge in der Logik nicht immer komplett und du musst Klammern einsetzen, um dem Leser die richtige Bindungsreihenfolge zu zeigen. Folgende Bindungsreihenfolge ist aber allgemein akzeptiert:

Negation bindet stärker als Konjunktion und Disjunktion bindet stärker als Implikation und Äquivalenz

Manchmal wird auch eine vollständige Bindungsreihenfolge definiert. Diese lautet dann meistens (der am stärksten bindende Junktor steht am Anfang):

1. Negation $\neg$
2. Konjunktion $\land$
3. Disjunktion $\lor$
4. Implikation $\Rightarrow$
5. Äquivalenz $\Leftrightarrow$

Die Kontravalenz ${\dot {\lor }}$ hat keinen festen Platz in der obigen Liste. Sie bindet stärker als die Implikation und schwächer als die Negation. Wenn aber die Kontravalenz zusammen mit der Disjunktion $\lor$ oder der Konjunktion $\land$ auftritt, solltest du deinen Ausdruck entsprechend Klammern.

Nach obiger Bindungsreihenfolge muss also die Aussage $\neg A\land B\Rightarrow B\lor C\land A$ als $((\neg A)\land B)\Rightarrow (B\lor (C\land A))$ gelesen werden. Ich empfehle dir aber (und werde dies auch im Buch umsetzen), bei der Unterscheidung der Bindung zwischen Konjunktion und Disjunktion sowie zwischen Implikation und Äquivalenz Klammern einzusetzen.

Wenn mehrere Implikationen nacheinander ohne Klammerung verwendet werden, gilt in der Literatur meistens folgende Definition:

$A\Rightarrow B\Rightarrow C\Rightarrow D$ bedeutet $A\Rightarrow (B\Rightarrow (C\Rightarrow D))$

Verständnisfrage: Wie musst du die Klammern in folgenden Ausdrücken richtig setzen (nach der vollständigen Liste zur Bindungsreihenfolge)?

1. $A\land \neg B\Rightarrow C$
2. $A\land B\Rightarrow \neg C\Leftrightarrow A$
3. $C\lor (C\Leftrightarrow B)\land A$

Antwort:

1. $(A\land (\neg B))\Rightarrow C$
2. $((A\land B)\Rightarrow (\neg C))\Leftrightarrow A$
3. $C\lor ((C\Leftrightarrow B)\land A)$

Quantor

Was sind Quantoren?

Neben den Junktoren gibt es noch eine zweite wichtige Gruppe von logischen Symbolen, die Quantoren. Während Junktoren Aussagen miteinander verknüpfen, legen Quantoren fest, für welche Objekte $x$ einer Grundmenge eine Aussageform $A(x)$ gilt. Eine Aussageform $A(x)$ ist dabei ein sprachlich sinnvoller Ausdruck, in dem die Variable $x$ vorkommt und der durch Belegung dieser Variablen mit einem konkreten Wert in eine Aussage übergeht. So sind die Ausdrücke

$x$ ist eine gerade Zahl

und

$x$ ist ein Mensch

Beispiele für solche Aussageformen $A(x)$, die von der Variablen $x$ abhängen.

Wir möchten den Begriff „Quantor“ an einem Beispiel erklären. Stelle dir dazu vor, wir verwenden gerade die Menge der reellen Zahlen. Dies bedeutet, dass alle Variablen, die wir benutzen, nur mit reellen Zahlen belegt werden sollen. Betrachte nun folgende Aussage:

Für alle $x$ gilt, dass $x^{2}\leq 0$ ist.

In diesem Beispiel ist „für alle“ ein Quantor, der Allquantor. Er behauptet, dass die Aussageform $x^{2}\leq 0$ für alle Belegungen der Variablen $x$ wie zum Beispiel $x=-{\tfrac {1}{2}}$, $x=42$ oder $x=0$ gültig sein soll. Wir können also folgende Struktur der obigen Aussage erkennen:

$\underbrace {\text{Für alle}} _{\text{Allquantor}}\ \underbrace {x} _{\text{Variable}}{\text{ gilt, dass }}\underbrace {x^{2}\leq 0} _{{\text{Aussageform }}A(x){\text{, in Abhängigkeit von }}x}{\text{ ist.}}$

Wie auch bei Junktoren werden für Quantoren bestimmte Symbole verwendet. Für den Allquantor ist das Symbol $\forall$ am geläufigsten. So kann die obige Aussage „Für alle $x$ gilt, dass $x^{2}\leq 0$ ist“ auch so geschrieben werden:

$\forall x:x^{2}\leq 0$

Wir können aber auch andere Quantoren zur Bindung der Variablen $x$ in der Aussageform $x^{2}\leq 0$ verwenden. Anstatt auszudrücken, dass die Aussageform $x^{2}\leq 0$ für alle Belegungen von $x$ gültig ist, können wir auch sagen, dass diese Aussageform für mindestens eine reelle Zahl $x$ wahr ist. Dieser Quantor „es gibt mindestens ein“ wird Existenzquantor genannt und hat das Symbol $\exists$. So besitzt die Aussage „Es gibt mindestens ein $x$ mit $x^{2}\leq 0$“ folgende Struktur:

$\underbrace {\text{Es gibt mindestens ein}} _{\text{Existenzquantor}}\ \underbrace {x} _{\text{Variable}}{\text{ mit }}\underbrace {x^{2}\leq 0} _{{\text{Aussageform }}A(x){\text{, in Abhängigkeit von }}x}$

Formal aufgeschrieben wird daraus:

$\exists x:x^{2}\leq 0$

Verständnisfrage: Sind obige Aussagen $\forall x:x^{2}\leq 0$ und $\exists x:x^{2}\leq 0$ für reelle Zahlen wahr oder falsch?

• Die Aussage $\forall x:x^{2}\leq 0$ ist falsch, da sie für die erlaubte Belegung $x=1$ nicht stimmt. Es ist nämlich $1^{2}=1>0$.
• Die Aussage $\exists x:x^{2}\leq 0$ ist wahr. Die Zahl $0$ ist nämlich eine reelle Zahl mit $0^{2}\leq 0$. Damit existiert (mindestens) eine reelle Zahl, welche die Aussageform $x^{2}\leq 0$ erfüllt.

Arten von Quantoren

Allquantor

Allquantor

Symbol:	$\forall$
Bedeutung:	„für alle“ oder „für jede(s)“
Schreibweise:	$\forall x:A(x)$

Im vorherigen Abschnitt hast du den Allquantor bereits kennen gelernt. Sein Symbol ist $\forall$ (ein umgedrehtes A – „für Alle“). Die Schreibweise des Allquantors ist $\forall x:\,A(x)$. Dies bedeutet „Für alle $x$ gilt $A(x)$“ oder „Für jedes $x$ gilt $A(x)$“. Dabei ist $A(x)$ eine beliebige Aussageform, in der die Variable $x$ vorkommt. In der Literatur ist auch die Schreibweise $\bigwedge _{x}A(x)$ zu finden, die wir aber in diesem Projekt nicht verwenden werden.

Die Menge der Objekte, auf die sich der Quantor bezieht, muss eindeutig bestimmt sein (und kann sich zum Beispiel aus dem Kontext ergeben). Wenn du eben natürliche Zahlen behandelst, so behauptet eine Aussage $\forall x:\,A(x)$, dass die Aussageform $A(x)$ für alle Belegungen von $x$ aus den natürlichen Zahlen zu einer wahren Aussage wird. Untersuchst du reelle Zahlen, so behauptet $\forall x:\,A(x)$, dass die Aussageform $A(x)$ für alle reellen Zahlen $x$ zu einer wahren Aussage wird.

Wenn du die Bezugsmenge des Allquantors explizit angeben möchtest oder musst, kannst du die deutlichere Schreibweise $\forall x\in M:\ A(x)$ verwenden. Sie ist eine Kurzschreibweise für $\forall x:x\in M\Rightarrow A(x)$ und bedeutet: „Für alle $x$ aus der Menge $M$ gilt die Aussage $A(x)$.“

Aufgabe: Überlege dir einige (mathematische) Aussagen, in denen du den Allquantor verwenden kannst und schreib diese auf.

Folgende Beispiele können mit dem Allquantor aufgeschrieben werden:

1. Für jedes Auto gilt: Es fährt oder es steht.
2. Für alle reellen Zahlen $x$ und alle natürlichen Zahlen $y$ ist $x+y=x\cdot y$.
3. Alle Schwäne sind weiß.

Aufgabe: Wie lauten die obigen Aussagen in Quantorenschreibweise?

1. $\forall x:\ x{\text{ ist ein Auto}}\Rightarrow (x{\text{ fährt}}\lor x{\text{ steht}})$
2. $\forall x\in \mathbb {R} \ \forall y\in \mathbb {N} :\ x+y=y\cdot x$
3. $\forall x:\ x{\text{ ist ein Schwan}}\Rightarrow x{\text{ ist weiß}}$

Existenzquantor

Existenzquantor

Symbol:	$\exists$
Bedeutung:	es existiert mindestens ein
Schreibweise:	$\exists x:A(x)$

Dieser Quantor wird für Aussagen folgender Form verwendet: „Es gibt mindestens ein $x$, so dass $A(x)$ gilt“. Dieser Quantor heißt Existenzquantor. Sein Symbol ist ein horizontal gespiegeltes E, welches für „es Existiert mindestens ein“ steht. Analog zum Allquantor haben Existenzaussagen die Form $\exists x:\,A(x)$. Diese Schreibweise steht für „Es gibt mindestens ein $x$, so dass $A(x)$ gilt“ oder „Es existiert mindestens ein $x$, für welches $A(x)$ gilt“. Auch hier ist $x$ eine Variable und $A(x)$ eine Aussageform, die von $x$ abhängt. In der Literatur kannst du auch die Schreibweise $\bigvee _{x}A(x)$ finden.

Wie auch beim Allquantor muss die Bezugsmenge $M$ des Quantors klar sein (z. B. aus dem Kontext). Muss die Bezugsmenge explizit angegeben werden, so kannst du die Schreibweise $\exists x\in M:\,A(x)$ verwenden. Sie ist eine Kurzschreibweise für $\exists x:x\in M\land A(x)$ und bedeutet: „Es gibt mindestens ein $x$ aus der Menge $M$, für welches die Aussage $A(x)$ wahr ist“.

Hinweis

In der Mathematik gibt es folgende Konvention: Eine Aussage der Form „Es gibt ein …“ ist immer als Aussage der Form „Es gibt mindestens ein …“ zu verstehen.

Verständnisfrage: Übersetze folgende Aussagen in die formelle Schreibweise mit dem Existenzquantor:

1. Es gibt eine Zahl $x$, so dass $x\cdot 0=5$ ist.
2. Es gibt schöne Männer.
3. Jeder Mensch besitzt einen Seelenverwandten.

Antwort:

1. $\exists x:\,x{\text{ ist eine Zahl }}\land x\cdot 0=5$
2. $\exists x:\,x{\text{ ist ein Mann }}\land \ x{\text{ ist schön}}$
3. $\forall x:\,\left(x{\text{ ist ein Mensch}}\Rightarrow \exists y:\,y{\text{ ist ein Seelenverwandter von }}x\right)$

Eindeutiger Existenzquantor

Eindeutiger Existenzquantor

Symbol:	$\exists !$
Bedeutung:	es existiert genau ein
Schreibweise:	$\exists !x:A(x)$

Der letzte Quantor, den wir dir vorstellen möchten, ist der eindeutige Existenzquantor $\exists !$. Die Schreibweise zu diesem Quantor (der auch Eindeutigkeitsquantor genannt wird) ist $\exists !x:\,A(x)$. Dies bedeutet so viel wie

(*) Es gibt genau ein $x$, so dass die Aussageform $A(x)$ für dieses $x$ eine wahre Aussage ist.

Beachte den Unterschied zwischen dem Existenzquantor und dem eindeutigen Existenzquantor: Während beim Existenzquantor die Aussageform $A(x)$ für mindestens eine Belegung von $x$ gilt, gilt beim eindeutigen Existenzquantor die Aussageform $A(x)$ für genau eine Belegung von $x$ aus der Grundmenge.

Auch bei diesem Quantor muss sich die Bezugsmenge durch den Kontext ergeben. Wenn du sie explizit angeben möchtest, kannst du die Schreibweise $\exists !x\in M:\,A(x)$ verwenden. Sie ist eine Kurzschreibweise für $\exists !x:x\in M\land A(x)$ und bedeutet: „Es gibt genau ein $x$ aus der Menge $M$, für welches die Aussage $A(x)$ wahr ist.“ Alternative und in der Literatur auch verbreitete Schreibweisen für den eindeutigen Existenzquantor sind $\exists _{1}$ und ${\overset {1}{\exists }}$.

Verständnisfrage: Überlege dir, ob folgende Aussagen wahr sind:

1. $\exists x\in \mathbb {R} :x^{2}=4$
2. $\exists !x\in \mathbb {R} :x^{2}=4$
3. $\exists !x\in \mathbb {N} :x^{2}=4$

Antwort:

1. Wahr. Da $2\in \mathbb {R}$ und $2^{2}=4$ ist, gibt es mit $2$ mindestens eine reelle Zahl, deren Quadrat gleich 4 ist.
2. Falsch. Es ist $2,-2\in \mathbb {R}$ und $(-2)^{2}=2^{2}=4$. Somit gibt es kein eindeutiges Element $x\in \mathbb {R}$ mit $x^{2}=4$.
3. Wahr. $2$ ist nämlich die einzige natürliche Zahl, deren Quadrat gleich $4$ ist. Beachte hier, dass $-2$ keine natürliche Zahl ist.

Der eindeutige Existenzquantor $\exists !$ lässt sich mit Hilfe des Existenzquantors $\exists$ und des Allquantors $\forall$ beschreiben, nämlich so:

(**) Es gibt mindestens ein $x$ mit $A(x)$ und wenn zwei Objekte $x$ und $y$ die Aussageformen $A(x)$ und $A(y)$ erfüllen, so sind sie gleich.

Die Formulierungen (*) und (**) beschreiben genau denselben Sachverhalt! Das ist der Grund dafür, dass der Quantor $\exists !$ üblicherweise wie folgt definiert wird:

Definition (Eindeutiger Existenzquantor)

$\exists !x:A(x):\iff \exists x:A(x)\land \forall x\,\forall y:(A(x)\land A(y)\implies x=y)$

Damit ist auch klar, wie Aussagen mit $\exists !$ zu beweisen sind:

• Zunächst wird $\exists x:A(x)$ bewiesen,
• anschließend wird gezeigt, dass aus $A(x)$ und $A(y)$ für beliebige $x$ und $y$ die Gleichheit $x=y$ folgt.

Notation

Für Ausdrücke mit Quantoren werden in der Literatur verschiedene Schreibweisen verwendet. So findet man anstelle vom Ausdruck $\forall x:A(x)$ auch die Notationen:

• $\forall x\ A(x)$
• $\forall x\ .\ A(x)$
• $\forall x(A(x))$
• $\forall _{x}A(x)$

Gleiches gilt für den Existenzquantor $\exists x:A(x)$:

• $\exists x\ A(x)$
• $\exists x\ .\ A(x)$
• $\exists x(A(x))$
• $\exists _{x}A(x)$

Manchmal werden in der Literatur auch Existenzquantoren der Art $\exists _{=n}$ bzw. $\exists _{\leq n}$ verwendet. Ihre Bedeutung ist:

• $\exists _{=n}\,x:A(x)$ bedeutet, es gibt genau $n$ Objekte $x$ mit der Eigenschaft $A(x)$
• $\exists _{\leq n}\,x:A(x)$ bedeutet, es gibt höchstens $n$ Objekte $x$ mit der Eigenschaft $A(x)$
• $\exists _{\geq n}\,x:A(x)$ bedeutet, es gibt mindestens $n$ Objekte $x$ mit der Eigenschaft $A(x)$

Wir werden in diesem Projekt aber die Schreibweise $\forall x:A(x)$ und $\exists x:A(x)$ verwenden. Auch kann man aufeinanderfolgende Quantoren vom selben Typ zusammenfassen, indem man die verschiedenen eingeführten Variablen durch Kommata trennt. So kannst du anstelle von $\forall x\,\forall y:A(x,y)$ auch folgende Schreibweise benutzen: $\forall x,y:A(x,y)$. Analog kann man anstelle von $\exists x\,\exists y:A(x,y)$ auch kürzer $\exists x,y:A(x,y)$ schreiben.

Aussageform und Substitution

Du hast dich vielleicht schon darüber gewundert, dass wir manchmal den Begriff „Aussage“ und manchmal den Begriff „Aussageform“ benutzen. Der Unterschied liegt darin, dass Aussageformen freie Variablen besitzen, während in Aussagen keine freien Variablen vorkommen. Doch was sind freie Variablen?

Freie und gebundene Variablen

Variablen sind Platzhalter (Leerstellen) in einem sprachlichen Ausdruck, die für Elemente der Grundmenge stehen. Sie können durch Quantoren oder andere Operatoren gebunden werden. Die Bedeutung der gebundenen Variablen ist an den Operator gekoppelt, in dessen Wirkungsbereich sie liegen. So besagt $\forall x:A(x)$, dass die Aussage $A(x)$ zutrifft, egal welches Element aus dem Grundbereich für $x$ genommen wird. $\exists x:A(x)$ dagegen heißt nur, dass es wenigstens ein Element aus dem Grundbereich gibt, für das $A(x)$ zutrifft. Eine Variable, die nicht gebunden ist, heißt frei.

So ist die Variable $x$ im Ausdruck $x\geq 23$ frei und im Ausdruck $\forall x:x\geq 23$ durch den Allquantor $\forall$ gebunden. Aber nicht nur Quantoren können Variablen binden. Auch durch Mengenausdrücke der Form $\{x:\ldots \}$ oder durch Summen $\sum _{k=\ldots }^{\ldots }\ldots$ können Variablen gebunden werden. Solltest du Summen oder Mengen noch nicht kennen: Kein Problem. Diese werden wir später behandeln. Generell gilt:

Definition (Freie und gebundene Variablen)

Eine Variable ist gebunden, wenn sie durch einen mathematischen Operator (z. B. einen Quantor) eingeführt wurde und im Wirkungsbereich dieses Operators liegt. Ansonsten ist eine Variable eine freie Variable.

Hier noch einige Beispiele:

Beispiel (freie und gebundene Variablen)

• ${\color {YellowOrange}\forall x}:{\color {Orange}\underbrace {x} _{\text{gebunden}}}+{\color {OliveGreen}\underbrace {y} _{\text{frei}}}=42$
• ${\color {OliveGreen}\underbrace {x} _{\text{frei}}}=4\Rightarrow {\color {YellowOrange}\exists x}:{\color {Orange}\underbrace {x} _{\text{gebunden}}}+4=8$
• ${\color {YellowOrange}\exists x}:\,({\color {OliveGreen}\underbrace {y} _{\text{frei}}}+{\color {Orange}\underbrace {x} _{\text{gebunden}}}=5\land {\color {YellowOrange}\forall y}:{\color {Orange}\underbrace {x} _{\text{gebunden}}}\cdot {\color {Orange}\underbrace {y} _{\text{gebunden}}}=8)$

Verständnisfrage: Welche der Variablen in den folgenden Ausdrücken sind frei und welche sind gebunden?

1. $a+b+c=5$
2. $a=b\lor \exists b:a=b$
3. $\forall a,b:t=a+b$
4. $\forall x:a=9$

Antwort:

1. ${\color {OliveGreen}\underbrace {a} _{\text{frei}}}+{\color {OliveGreen}\underbrace {b} _{\text{frei}}}+{\color {OliveGreen}\underbrace {c} _{\text{frei}}}=5$
2. ${\color {OliveGreen}\underbrace {a} _{\text{frei}}}={\color {OliveGreen}\underbrace {b} _{\text{frei}}}\,\lor \,{\color {YellowOrange}\exists b}:{\color {OliveGreen}\underbrace {a} _{\text{frei}}}={\color {Orange}\underbrace {b} _{\text{gebunden}}}$
3. ${\color {YellowOrange}\forall a,b}:{\color {OliveGreen}\underbrace {t} _{\text{frei}}}={\color {Orange}\underbrace {a} _{\text{gebunden}}}+{\color {Orange}\underbrace {b} _{\text{gebunden}}}$
4. ${\color {YellowOrange}\forall x}:{\color {OliveGreen}\underbrace {a} _{\text{frei}}}=9$

Terme

Variablen sind Platzhalter für Elemente aus einem Grundbereich. Grundbereiche in der Mathematik sind häufig die Zahlbereiche $\mathbb {N}$, $\mathbb {Z}$, $\mathbb {Q}$, $\mathbb {R}$ oder $\mathbb {C}$. Es kann aber auch eine ganz andere Menge der Grundbereich sein, beispielsweise die Menge aller Menschen, Autos oder Musikinstrumente. Ausdrücke, die Elemente aus dem Grundbereich bezeichnen, werden Terme genannt. Mit Hilfe von Operationssymbolen (auch Verknüpfungen genannt) wie $+$, $-$ und $\cdot$ werden aus Termen weitere Terme gebildet. Zu einem Operationssymbol gehört eine natürliche Zahl als Stellenzahl, die angibt, wie viele Terme zu einem neuen Term verknüpft werden. Die Terme, die verknüpft werden, heißen Argumente, das Ergebnis der Verknüpfung Resultat.

Beispiel (Operationssymbole)

• Das Pluszeichen „$+$“ ist 2-stellig und macht aus zwei Zahlen eine dritte, die Summe: $(1+2)$.
• Das Vorzeichen „$-$“ ist 1-stellig: $-13$. Das Subtraktionszeichen „$-$“ dagegen ist 2-stellig: $(7-3)$.
• Beim größten gemeinsamen Teiler „$\operatorname {ggT}$“ und beim kleinsten gemeinsamen Vielfachen „$\operatorname {kgV}$“ werden die Argumente in der Regel dahinter notiert: $\operatorname {ggT} (36,70)$ und $\operatorname {kgV} (12,9)$.
• Die Potenz ist 2-stellig, aber das Operationssymbol wird gar nicht notiert. Stattdessen wird die Verknüpfung durch das Hochstellen widergegeben: $2^{16}$.
• Der Durchschnitt „$\cap$“ und die Vereinigung „$\cup$“ von Mengen sind 2-stellige Verknüpfungen: $(A\cap B)$ und $(A\cup B)$.
• Das Komplement einer Menge „$(\ldots )^{\complement }$“ ist 1-stellig und wird häufig hochgestellt hinter dem Argument notiert: $A^{\complement }$.
• Bei mehrstelligen Verknüpfungen $f$ stehen die Argumente in Klammern hinter dem Symbol: $f(x_{1},x_{2},\dots ,x_{n})$

Bei 2-stelligen Operationssymbolen werden die Klammern weggelassen, wenn sie nicht erforderlich sind.

Definition (Term)

Terme sind sprachliche Ausdrücke, die eine Zahl oder ein anderes Objekt bezeichnen. Insbesondere sind Variable Terme. Mit Hilfe von Verknüpfungen können aus Termen weitere Terme gebildet werden.

Terme treten oftmals als Teile von Aussagen auf.

Beispiel (Terme)

• ${\forall x}:{\color {Orange}\underbrace {x+y} _{\text{Term}}}={\color {OliveGreen}\underbrace {42} _{\text{Term}}}$
• ${\color {OliveGreen}\underbrace {x} _{\text{Term}}}={\color {YellowOrange}\underbrace {4} _{\text{Term}}}\implies \exists x:{\color {SkyBlue}\underbrace {x+4} _{\text{Term}}}={\color {WildStrawberry}\underbrace {8} _{\text{Term}}}$
• $\exists x:\,({\color {SkyBlue}\underbrace {y+x} _{\text{Term}}}={\color {WildStrawberry}\underbrace {5} _{\text{Term}}}\land \forall y:{\color {OliveGreen}\underbrace {x\cdot y} _{\text{Term}}}={\color {YellowOrange}\underbrace {8} _{\text{Term}}})$

Einige Terme aus diesen Beispielen enthalten weitere Terme: So enthält der Term „$x+y$“ die Terme „$x$“ und „$y$“ und der Term „$4\cdot x$“ enthält die Terme „$4$“ und „$x$“.

Prädikate

Von Verknüpfungen sind Prädikate (auch Relationssymbole genannt) zu unterscheiden. Prädikate haben wie Verknüpfungen eine Stellenzahl. Die Argumente von Prädikaten sind ebenfalls Terme, aber das Resultat ist eine Aussage oder eine Aussageform. Beispiele für Prädikate sind größer-gleich ($\geq$) und die Teilmengenbeziehung ($\subseteq$).

Definition (Prädikat)

Prädikate verbinden Terme zu Aussagen bzw. Aussageformen. Sie haben eine Stellenzahl. Ist $P$ ein $n$-stelliges Prädikat, so heißt $P(x_{1},x_{2},\dots ,x_{n})$, dass $P$ auf $x_{1},x_{2},\dots ,x_{n}$ zutrifft. 2-stellige Prädikate werden meist zwischen die Argumente geschrieben.

Hinweis

Die Schreibweise von Prädikaten ist genau dieselbe wie bei Verknüpfungen! Es muss also aus dem Zusammenhang erschlossen werden, was von beiden gemeint ist.

Beispiel (Prädikat)

• $\forall x,y,z:{\color {Orange}\underbrace {x} _{\text{Term}}}{\color {SkyBlue}\underbrace {\quad \quad \leq \quad \quad } _{\text{Prädikat}}}{\color {OliveGreen}\underbrace {y} _{\text{Term}}}\Rightarrow {\color {WildStrawberry}\underbrace {x+z} _{\text{Term}}}{\color {SkyBlue}\underbrace {\quad \quad \leq \quad \quad } _{\text{Prädikat}}}{\color {Sepia}\underbrace {y+z} _{\text{Term}}}$
• $x{\color {SkyBlue}\underbrace {<} _{\text{Prädikat}}}y\lor x{\color {SkyBlue}\underbrace {=} _{\text{Prädikat}}}y\lor x{\color {SkyBlue}\underbrace {>} _{\text{Prädikat}}}y$
• $13\;{\color {SkyBlue}\underbrace {\text{ist Primzahl}} _{\text{Prädikat}}}$

Aussageformen, Formeln

Mit Hilfe der Begriffe freie und gebundene Variable können wir definieren, was Aussageformen sind:

Definition (Aussageform, Formeln)

Aussageformen sind sprachliche Ausdrücke mit freien Variablen, die durch Belegung dieser Variablen mit konkreten Werten in eine Aussage übergehen.

Als Oberbegriff von Aussagen und Aussageformen ist die Bezeichnung Formel üblich:

Definition (Formel)

Eine Formel ist eine Aussage oder eine Aussageform und damit ein Oberbegriff für beide Konzepte. Jede Formel ist damit entweder eine Aussage oder eine Aussageform.

Verständnisfrage: Welche der folgenden formalen Ausdrücke sind Aussagen und welche sind Aussageformen?

1. $x+y=y+x$
2. $\forall x:x+y=y+x$
3. $\forall x\forall y:x+y=y+x$
4. $x>0\implies \exists x:x^{2}=4$
5. $\forall x:\left(x<4\land \exists y:x+y=23\right)$

Antwort:

1. Aussageform ($x$ und $y$ kommen frei im Ausdruck vor)
2. Aussageform ($y$ kommt frei im Ausdruck vor)
3. Aussage (keine freien Variablen)
4. Aussageform ($x$ kommt frei im Ausdruck vor)
5. Aussage (keine freien Variablen)

Der Wahrheitsgehalt der obigen Aussagen und Aussageformen hängt jeweils von der gewählten oder vorgegebenen Grundmenge ab.

Substitution von Termen für Variablen

Ersetzt man in einem Ausdruck eine freie Variable durch einen Term, so nennt man diesen Vorgang Substitution. Das kommt beispielsweise beim Lösen von Gleichungssystemen vor. Beispiel:

1. $x+{\frac {1}{2}}y=7$
2. $x-y=1$

Aus der 2. Gleichung erhalten wir $x=1+y$, was wir als Substitution $x:=1+y$ nutzen können. Daher ersetzen wir in Gleichung 1. die Variable $x$ durch den Term $1+y$ und erhalten so: $1+y+{\frac {1}{2}}y=7$, woraus sich schließlich $y=4$ ergibt.

Beim Substituieren musst du darauf achten, dass du nur und wirklich nur freie Variablen durch den entsprechenden Term ersetzt. Gebundene und quantifizierte Variablen müssen unangetastet bleiben. Beispiel:

${\begin{array}{c}{\color {ForestGreen}x}+y=7\cdot {\color {ForestGreen}x}\land \exists {\color {Periwinkle}x}:{\color {Periwinkle}x}=0\\\downarrow \\{\text{Substitution }}{\color {OliveGreen}x}:={\color {Orange}y+8}\\\downarrow \\{\color {Orange}(y+8)}+y=7\cdot {\color {Orange}(y+8)}\land \exists {\color {Periwinkle}x}:{\color {Periwinkle}x}=0\end{array}}$

Beachte, dass die gebundene Variable ${\color {Periwinkle}x}$ nicht verändert wurde. Wenn im Substitutionsterm freie Variablen vorkommen, die in der Aussageform bereits gebunden sind, dann müssen diese gebundenen Variablen umbenannt werden. Es dürfen nämlich durch die Substitution keine Variablen gebunden werden, die vorher frei waren:

${\begin{array}{c}\exists {\color {RubineRed}y}:{\color {ForestGreen}x}>{\color {RubineRed}y}\\\downarrow \\{\text{ Umbenennung }}{\color {RubineRed}y}:={\color {CornflowerBlue}z}\\\downarrow \\\exists {\color {CornflowerBlue}z}:{\color {ForestGreen}x}>{\color {CornflowerBlue}z}\\\downarrow \\{\text{Substitution }}{\color {ForestGreen}x}:={\color {Orange}y\cdot 42}\\\downarrow \\\exists {\color {CornflowerBlue}z}:{\color {Orange}(y\cdot 42)}>{\color {CornflowerBlue}z}\end{array}}$

Im obigen Beispiel wird durch die Substitution ${\color {OliveGreen}x}:={\color {Orange}y\cdot 42}$ die freie Variable ${\color {Orange}y}$ neu eingeführt. Jedoch ist in der ursprünglichen Aussageform bereits ${\color {RubineRed}y}$ durch den Existenzquantor gebunden. Deswegen muss die gebundene Variable ${\color {RubineRed}y}$ umbenannt werden (hier in die Variable ${\color {CornflowerBlue}z}$). Würde man dies nicht tun, dann würde die freie Variable ${\color {Orange}y}$ ebenfalls gebunden werden, was bei einer Substitution nicht erlaubt ist.

Definition (Substitution)

Gegeben sei ein Ausdruck $A(x)$ mit der freien Variablen $x$ und ein beliebiger Term $t$. Dann entsteht der Ausdruck $A(t)$ durch die Substitution $x:=t$ dadurch, dass alle Vorkommen von $x$ durch $t$ ersetzt werden. Sollten durch die Substitution freie Variable gebunden werden, so sind die gebundenen Variablen vorher umzubenennen.

Eine andere Schreibweise für diese Substitution ist ${\binom {x}{t}}$, für den substituierten Term $A{(_{t}^{x})}$.

Verständnisfrage: Wie lauten folgende Aussageformen beziehungsweise Aussagen nach der Substitution?

1. $x+y=y+x$ für die Substitution $x:=6$
2. $\forall x,y:x+y=y+x$ für die Substitution $x:=6$
3. $x+x=y\cdot x$ für die Substitution $x:=y$
4. $a=b+c$ für die Substitution $x:=a+b$

Antwort:

1. $6+y=y+6$
2. $\forall x,y:x+y=y+x$. In der Aussage $\forall x,y:x+y=y+x$ ist $x$ keine freie Variable und kann daher nicht ersetzt werden.
3. $y+y=y\cdot y$
4. $a=b+c$

Verständnisfrage: Wieso können sich Aussagen durch eine Substitution nicht ändern?

Weil Aussagen per Definition keine freien Variablen besitzen und nur freie Variable substituiert werden, bleiben Aussagen bei einer Substitution unverändert.

Tautologie

Tautologie

Die Aussage „Wenn der Hahn kräht auf dem Mist, dann ändert sich das Wetter oder es bleibt wie es ist.“ ist eine Tautologie.

Es gibt Aussagen, die sind immer wahr. Das klassische Beispiel hierfür ist die Bauernregel: „Wenn der Hahn kräht auf dem Mist, dann ändert sich das Wetter oder es bleibt wie es ist.“ $H$ stehe für die Aussage „Der Hahn kräht auf dem Mist“ und $X$ für „Das Wetter ändert sich“, dann können wir diese Bauernregel folgendermaßen formalisieren:

$\underbrace {H\implies X\lor \neg X} _{{\text{Wenn }}H{\text{ dann }}X{\text{ oder }}\neg X.}$

Da Aussagen entweder „wahr“ oder „falsch“ sind, ist leicht zu sehen, dass die Bauernregel immer wahr ist. Dabei kommt es überhaupt nicht darauf an, ob der Hahn kräht oder nicht. Denn $X$ oder $\neg X$ – eine dieser beiden Aussagen ist wahr. Es spielt auch keine Rolle, was genau mit $X$ gemeint ist: es muss nur eine Aussage sein! $X$ könnte auch für die Behauptung stehen: „Es gibt kleine, grüne Männchen auf dem Mars.“

Woran liegt es, dass diese Aussage immer wahr ist? Es liegt daran, wie die Aussage mit Junktoren aus Teilaussagen zusammengebaut ist. Wir wissen, dass die Negation $\neg$ den Wahrheitswert umdreht: aus ${\mathsf {W}}$ wird ${\mathsf {F}}$ und umgekehrt aus ${\mathsf {F}}$ wird ${\mathsf {W}}$. Die Oder-Verbindung $\lor$ wird wahr, wenn eine der beiden Teilaussagen wahr ist. Also ist $X\lor \neg X$ immer wahr. Die Implikation $A\implies B$ ist nur dann falsch, wenn die Prämisse $A$ wahr ist und die Konklusion $B$ falsch ist. In unserem Beispiel aber ist die Konklusion $X\lor \neg X$ immer wahr. Daher ist auch $H\implies X\lor \neg X$ immer wahr. Mit Junktoren zusammengesetzte Aussagen, die immer wahr sind, werden Tautologien oder auch allgemeingültige Aussagen genannt:

Definition (Tautologie)

Eine mit Junktoren zusammengesetzte Aussage heißt tautologisch oder allgemeingültig, wenn sie bei jeder möglichen Interpretation seiner Teilaussagen mit Wahrheitswerten wahr ist.

Besonders wichtige Tautologien sind Äquivalenzen. Zwei Aussagen $A$ und $B$ sind nämlich genau dann äquivalent, wenn die zusammengesetzte Aussage $A\iff B$ eine Tautologie ist. Das wird oft bei Beweisen genutzt. Statt direkt die Aussage $A$ zu beweisen, wird eine dazu äquivalente Aussage $B$ gezeigt.

Beispiel (Äquivalente Aussagen)

Die folgenden drei Aussagen sind äquivalent:

• $A\implies B$
• $\neg B\implies \neg A$ (Kontraposition)
• $\neg (A\land \neg B)$ (Widerspruchsbeweis)

Es sind also tautologisch:

• $A\implies B\iff \neg B\implies \neg A$
• $A\implies B\iff \neg (A\land \neg B)$

Eine alternative Formulierung des Widerspruchbeweises ist im Übrigen $A\land \neg B\implies {\mathsf {F}}$.

Überprüfung einer Tautologie

Wir werden jetzt drei Möglichkeiten vorstellen, wie du überprüfen kannst, ob eine Aussage eine Tautologie ist oder nicht. Alle diese Möglichkeiten sollen am Beispiel der Kontraposition $(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$ demonstriert werden.

Wahrheitstabelle erstellen

Erklärung der Äquivalenz von dem direktem Beweis, der Kontraposition und dem Widerspruchsbeweis. (YouTube-Video vom Kanal Quatematik)

Eine Methode ist es, eine Wahrheitstabelle für die zu untersuchende Aussage aufzustellen, vgl. Kapitel „Wahrheitstabelle“. Wenn in der letzten Spalte der Wahrheitstabelle nur „wahr“ als resultierender Wahrheitswert auftritt, ist die untersuchte Aussage eine Tautologie. Sobald ein resultierender Wahrheitswert „falsch“ ist, ist die Aussage keine Tautologie.

Aufgabe: Stelle die Wahrheitstabelle für $(A\lor B)\Leftrightarrow (B\lor A)$ auf.

$A$	$B$	$A\lor B$	$B\lor A$	$(A\lor B)\Leftrightarrow (B\lor A)$
${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\boldsymbol {\mathsf {W}}}$

Ergebnis: Die Aussage ist eine Tautologie.

Aufgabe: Stelle die Wahrheitstabelle für $(A\Rightarrow B)\Leftrightarrow (B\Rightarrow A)$ auf.

$A$	$B$	$A\Rightarrow B$	$B\Rightarrow A$	$(A\Rightarrow B)\Leftrightarrow (B\Rightarrow A)$
${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	$\color {red}{\boldsymbol {\mathsf {F}}}$
${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {F}}$	$\color {red}{\boldsymbol {\mathsf {F}}}$
${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$

Ergebnis: Die Aussage ist keine Tautologie.

Aufgabe: Stelle die Wahrheitstabelle für $(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$ auf.

$A$	$B$	$\neg A$	$\neg B$	$A\Rightarrow B$	$\neg B\Rightarrow \neg A$	$(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$
${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$

Ergebnis: Die Aussage ist eine Tautologie.

Aufgabe: Stelle die Wahrheitstabelle für $(X\Rightarrow Y)\Leftrightarrow (\neg X\lor Y)$ auf.

$X$	$Y$	$\neg X$	$X\Rightarrow Y$	$\neg X\lor Y$	$(X\Rightarrow Y)\Leftrightarrow (\neg X\lor Y)$
${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$

Ergebnis: Die Aussage ist eine Tautologie.