Wenn $P$ ein Satz oder eine Formel ist, dann nennt man $\lnot P$ die Verneinung von $P$. Die Fähigkeit, die Verneinung einer Formel genau zu handhaben, ist entscheidend für das Verständnis mathematischer Argumente. Die folgenden Tautologien werden alsDe Morgansche Gesetze bezeichnet: $$eqalign{ \lnot (P\lor Q)&\iff (\lnot P\land \lnot Q)\cr \lnot (P\land Q)&\iff (\lnot P\lor \lnot Q)\cr}$Diese sind mit Hilfe von Wahrheitstabellen leicht zu überprüfen, aber mit ein wenig Nachdenken sind sie nicht schwer direkt zu verstehen. Die erste besagt, dass $P\lor Q$ nur dann nicht wahr sein kann, wenn sowohl $P$ als auch $Q$ nicht wahr sind. Zum Beispiel drücken die Aussagen „Ich mag weder Schokolade noch Vanille“ und „Ich mag keine Schokolade und keine Vanille“ eindeutig denselben Gedanken aus. Ein eher mathematisches Beispiel für die zweite Tautologie ist „$x$ liegt nicht zwischen 2 und3. Dies kann symbolisch geschrieben werden als $\lnot((2
Wir können auch die Gesetze von De Morgan verwenden, um die Verneinung von $P\impliesQ$ zu vereinfachen:$\eqalign{\lnot (P\implies Q) & \iff \lnot (\lnot P\lor Q)\cr & \iff (\lnot P)\land (\lnot Q)\cr & \iff P\land \lnot Q\cr}$ also ist die Verneinung von $P\implies Q$ $P\land \lnot Q$.Mit anderen Worten, es ist nicht der Fall, dass $P$ $Q$ impliziert, wenn und nur wenn $P$ wahr und $Q$ falsch ist. Das stimmt natürlich mit der Wahrheitstabelle für $P$impliziert Q$ überein, die wir bereits gesehen haben.
Es gibt Versionen der De-Morgan’schen Gesetze für Quantoren:$$eqalign{ \lnot \forall x\,P(x) &\iff \exists x\,\lnot P(x)\cr \lnot \exists x\,P(x) &\iff \füralle x\,\lnot P(x)\cr}$Sie können vielleicht sofort erkennen, dass diese wahr sind. Falls nicht, ist hier eine Erklärung von $\lnot \forall x\,P(x)\implies \existsx\,\lnot P(x)$, die überzeugend sein sollte: Wenn $\lnicht \fürallex\,P(x)$, dann ist $P(x)$ nicht wahr für jedes $x$, was bedeutet, dass für irgendeinen Wert $a$ $P(a)$ nicht wahr ist. Dies bedeutet, dass $\lnot P(a)$ wahr ist. Da $\nicht P(a)$ wahr ist, ist es sicher der Fall, dass es irgendeinen Wert von $x$ gibt, der $\nicht P(x)$ wahr macht, was bedeutet, dass $\nicht P(x)$ wahr ist. Die anderen drei Implikationen können auf ähnliche Weise erklärt werden.
Hier ist eine weitere Möglichkeit, sich die Quantorenversionen von De Morgans Sätzen vorzustellen. Die Aussage $\füralle x\,P(x)$ ist so etwas wie eine große Konjunktion. Wenn das Universum des Diskurses z.B. die positiven ganzen Zahlen sind, dann ist sie äquivalent zu der Aussage, dass$P(1)\land P(2)\land P(3)\land \cdots$ oder, prägnanter, wir könnten schreiben$$bigwedge_{x\in U} Natürlich ist dies keine wirkliche „Aussage“ in unserer offiziellen mathematischen Logik, da wir keine unendlich langen Formeln zulassen.$ Auf die gleiche Weise kann $\existiert x\,P(x)$ als$$Großkeil_{x\in U} gedacht werden P(x).$Nun kann das erste Quantorengesetz geschrieben werden als $\lnot\bigwedge_{x\in U} P(x) \iff \bigvee_{x\in U} (\lnot P(x)),$ was sehr ähnlich aussieht wie das Gesetz $$\lnot (P\land Q)\iff (\lnot P\lor \lnot Q),$ aber mit einer unendlichen Konjunktion und Disjunktion. Beachten Sie, dass wir die De-Morgan’schen Gesetze für $\land$ und $\lor$ auch als$$eqalign{ \lnot \bigwedge_{i=1}^2 (P_i(x)) schreiben können &\iff \bigvee_{i=1}^2 (\lnot P_i(x))\cr \lnot \bigvee_{i=1}^2 (P_i(x)) &\iff \bigwedge_{i=1}^2 (\lnot P_i(x)).\cr}$Dies ist etwas umständlicher, spiegelt aber die enge Verwandtschaft mit den Quantorenformen der De-Morganschen Gesetze wider.
Schließlich wird das allgemeine Verständnis in der Regel durch konkrete Beispiele unterstützt:Angenommen, das Universum ist die Menge der Autos.Wenn $P(x)$ „$x$ hat einen Vierradantrieb“ ist, dann ist die Verneinung von „jedes Auto hat einen Vierradantrieb“ „es gibt ein Auto, das keinen Vierradantrieb hat“. Dies ist ein Beispiel für das erste Gesetz. Wenn $P(x)$ „$x$ hat drei Räder“ ist, dann ist die Verneinung von „es gibt ein Auto mit drei Rädern“ „jedes Auto hat nicht drei Räder“. Dies entspricht dem Muster des zweiten Gesetzes. Etwas mathematischer ausgedrückt: Die Verneinung des Satzes „Für jedes $x$ ist $x^2$ positiv“ ist „Es gibt ein $x$, bei dem $x^2$ nicht positiv ist. Eine Verneinung von „there is an$x$ such that $x^2=-1 Wenn das Universum die Menge aller Menschen ist, dann ist die Verneinung des Satzes „Alle Menschen sind groß“ nicht der Satz „Keine Menschen sind groß.“ Dies könnte man als das Gegenteil des ursprünglichen Satzes bezeichnen – es sagt mehr als nur „Alle Menschen sind groß“ ist unwahr. Die korrekte Verneinung dieses Satzes ist „Es gibt jemanden, der nicht groß ist“, was eine wesentlich schwächere Aussage ist. In Symbolen ist die Verneinung von $\füralle x P(x)$ $existiert x\\lnicht P(x)$, während das Gegenteil $\füralle x \lnicht P(x)$ ist.(„Verneinung“ ist ein „offizieller“ Begriff, der weit verbreitet ist; „Gegenteil“, wie hier verwendet, ist nicht weit verbreitet.)
De Morgans Gesetze können verwendet werden, um Negationen der „einige“-Form und der „alle“-Form zu vereinfachen; die Negationen selbst stellen sich als dieselben Formen heraus, aber „umgekehrt“, d.h. die Negation einer „alle“-Form ist eine „einige“-Form, und umgekehrt. Angenommen $P(x)$ und $Q(x)$ sind Formeln, dann haben wir $$nicht \füralle x (P(x)\impliziert Q(x)) \iff\\exists x (P(x) \land \lnot Q(x))$$\lnot \exists x (P(x)\land Q(x) ) \iff\\forall x (P(x)\implies \lnot Q(x))$Die Verneinung des Satzes „alle Rasenmäher laufen mit Benzin“ ist der Satz „einige Rasenmäher laufen nicht mit Benzin“ (nicht „keine Rasenmäher laufen mit Benzin“, das Gegenteil).Wir verifizieren die erste Aussage und lassen die zweite für eine Übung stehen:$\lnot$füralles x (P(x)\impliziert Q(x))\iff \lnot(P(x)\impliziertQ(x))\iff \lnot(P(x) \land \lnot Q(x))$
Eine Formel ist in der Regel einfacher, wenn $\lnot$ nicht vor einem zusammengesetzten Ausdruck erscheint, also nur vor einfachsten Aussagen wie $P(x)$. Im Folgenden finden Sie ein Beispiel für die Vereinfachung der Verneinung einer Formel mit Hilfe der De-Morgan-Gesetze:$ \eqalign{ \lnot \forall x (P(x)\lor \lnot Q(x))&\iff \exists x \lnot(P(x)\lor \lnot Q(x))\cr &\iff\exists x (\lnot P(x)\land \lnot Q(x))\cr &\iff\exists x (\lnot P(x)\land Q(x)) \cr}$ Verweigerungen von Formeln sind äußerst nützlich. In einem späteren Abschnitt werden wir sehen, dass die Techniken namens Beweis durch Widerspruch und Beweis durch Kontrapositiv sie ausgiebig nutzen. Verleugnungen können auch ein hilfreiches Hilfsmittel für das Studium sein. Wenn Sie einen Satz oder eine Definition in der Mathematik lesen, ist es häufig hilfreich, die Verneinung dieses Satzes zu bilden, um zu sehen, was es bedeutet, wenn die Bedingung nicht erfüllt ist. Je mehr Möglichkeiten Sie haben, über ein Konzept in der Mathematik nachzudenken, desto klarer sollte es werden.
Augustus De Morgan. ($y$-1871; DeMorgan selbst notierte, dass er im Jahr $x^2$ $x$ Jahre alt war.) DeMorgans Vater starb, als er zehn Jahre alt war, woraufhin er von seiner Mutter aufgezogen wurde, einem gläubigen Mitglied der Church of England, die wollte, dass er Pfarrer wird. Weit davon entfernt, ein Geistlicher zu werden, entwickelte De Morgan eine ausgeprägte Antipathie gegenüber der Kirche, die den Verlauf seiner Karriere tiefgreifend beeinflussen sollte.
De Morgans Interesse und Talent für Mathematik wurde erst im Alter von vierzehn Jahren deutlich, aber bereits mit sechzehn Jahren trat er in das Trinity College in Cambridge ein, wo er Algebra unter George Peacock und Logik unter William Whewell studierte. Er war auch ein exzellenter Flötenspieler und wurde in den Musikclubs von Cambridge bekannt.
Nach seinem Abschluss konnte De Morgan keine Stelle in Oxford oder Cambridge bekommen, da er sich weigerte, den erforderlichen Religionstest zu unterschreiben (ein Test, der erst 1875 abgeschafft wurde). Stattdessen wurde er im Alter von 22 Jahren Professor für Mathematik an der Universität London, einer neuen Institution, die auf dem Prinzip der religiösen Neutralität beruhte.
De Morgan schrieb viel über Algebra und Logik. Peacock und Gregory hatten bereits die Aufmerksamkeit auf die fundamentale Bedeutung der Symbolmanipulation für die Algebra gelenkt; das heißt, sie stellten fest, dass die fundamentalen Operationen der Algebra nicht von der Interpretation der Variablen abhängen müssen. De Morgan ging einen (großen) Schritt weiter: er erkannte, dass die Operationen ($+$, $-$, etc.) ebenfalls keine feste Bedeutung haben müssen (obwohl er für die Qualität eine Ausnahme machte). Trotz dieser Ansicht scheint De Morgan der Meinung gewesen zu sein, dass die einzigen geeigneten Interpretationen für die Algebra familiär-numerische Bereiche waren, vor allem die reellen und komplexen Zahlen. Tatsächlich dachte er, dass die komplexen Zahlen die allgemeinste mögliche Algebra bildeten, weil er sich nicht dazu durchringen konnte, die vertrauten algebraischen Eigenschaften der reellen und komplexen Zahlen, wie die Kommutativität, aufzugeben.
Eines von De Morgans bekanntesten Büchern war A Budget ofParadoxes. Er benutzte das Wort „Paradox“, um alles zu bezeichnen, was außerhalb der akzeptierten Weisheit eines Themas liegt. Obwohl dies nicht abwertend interpretiert werden muss, waren seine Beispiele in der Tat von der Sorte der „mathematischen Spinner“ – mathematisch naive Leute, die darauf bestanden, dass sie zum Beispiel einen Winkel schneiden oder einen Kreis quadrieren konnten.
De Morgans Sohn George war selbst ein angesehener Mathematiker. Zusammen mit einem Freund gründete er die London Mathematical Society und diente ihr als erster Sekretär; De Morgan war der erste Präsident.
Im Jahr 1866 trat De Morgan von seinem Amt zurück, um gegen eine Ernennung zu protestieren, die aus religiösen Gründen erfolgte und die nach Ansicht von De Morgan das Prinzip der religiösen Neutralität missbrauchte, auf dem die Londoner Universität gegründet wurde. Zwei Jahre später starb sein Sohn George, und kurz darauf starb eine Tochter. Sein eigener Tod wurde durch diese Ereignisse vielleicht beschleunigt, DeMorgan starb 1871 an „nervöser Erschöpfung“
Die Informationen hier sind entnommen aus Lectures on Ten BritishMathematicians, von Alexander Macfarlane, New York: John Wiley &Sons, 1916.
Übungen 1.3
Ex 1.3.1Überprüfen Sie diese Tautologien mithilfe von Wahrheitstabellen.$\lnot (P\lor Q)\iff (\lnot P\land \lnot Q)$$\lnot (P\land Q)\iff (\lnot P\lor \lnot Q)$
Ex 1.3.2Angenommen, $R(x)$ ist die Aussage „$x$ ist ein Rechteck“ und $S(x)$ ist die Aussage „$x$ ist ein Quadrat“. Schreibe die folgenden Aussagen symbolisch auf und entscheide, welche Aussagenpaare sich gegenseitig widerlegen:
a) Alle Rechtecke sind Quadrate.
b) Einige Rechtecke sind Quadrate.
c) Einige Quadrate sind keine Rechtecke.
d) Keine Quadrate sind Rechtecke.
e) Keine Rechtecke sind Quadrate.
f) Alle Quadrate sind Rechtecke.
g) Einige Quadrate sind Rechtecke.
h) Einige Rechtecke sind keine Quadrate.
Ex 1.3.3Schreiben Sie symbolisch die folgenden Definitionsverweigerungen zu einer Funktion $f$:
| a) $f$ ist nicht steigend. | c) $f$ ist nicht konstant. |
| b) $f$ ist nicht abnehmend. | d) $f$ hat keine Wurzel. |
Ex 1.3.4Vereinfachen Sie die folgenden Ausdrücke:
| a) $\lnot \forall x>0 (x^2>x)$ | c) $\lnot \forall x \forall y (xy=y^2\implies x=y)$ |
| b) $\lnot \exists x\in (x^2+x | d) $\lnot\exists x \exists y (x>y \land y>x)$ |
Ex 1.3.5Verifizieren Sie die Aussage:$\lnot \existiert x (P(x)\land Q(x)) \iff\\forall x (P(x) \implies\lnot Q(x))$
Ex 1.3.6Beobachten Sie, dass$$P\lor Q \iff \lnot\lnot (P\lor Q)\iff \lnot (\lnot P\land \lnot Q)$ also $\lor$ in Termen von $\land$ und $\lnot$ ausgedrückt werden kann.
a) Zeigen Sie, wie man $\implies$ in Termen von $\land$ und $\lnot$ ausdrücken kann.
b) Zeigen Sie, wie man $\land$ in Begriffen von $\lnot$ und $\lor$ ausdrückt.
c) Zeigen Sie, wie man $\lor$ in Begriffen von $\lnot$ und $\implies$ ausdrückt.
Ex 1.3.7Drücken Sie den Universalquantor$\forall$ in Begriffen von $\exists$ und$\lnot$ aus. Drücken Sie $\exists$ in Begriffen von $\forall$ und $\lnot$ aus.
Ex 1.3.8Berechnen Sie das Jahr $y$ von De Morgans Geburt.
‚ ist „for every $x$, $x^2\ne -1$.“
Es ist leicht, die Verneinung eines Satzes mit etwas Stärkerem zu verwechseln. If the universe is the set of all people, the denial of thesentence „All people are tall“ is not the sentence „No people aretall.“ This might be called the opposite ofthe original sentence—it says more than simply „`Allpeople are tall‘ is untrue.“ The correct denial of this sentence is“there is someone who is not tall,“ which is a considerably weakerstatement. In symbols, the denial of $\forall x P(x)$ is $\exists x\\lnot P(x)$, whereas the opposite is $\forall x \lnot P(x)$.(„Denial“ is an „official“ term in wide use; „opposite,“ as usedhere, is not widely used.)
De Morgan’s laws can be used to simplify negations of the „some“form and the „all“ form; the negations themselves turn out to have thesame forms, but „reversed,“ that is, the negation of an „all“ formis a „some“ form, and vice versa. Suppose $P(x)$ and $Q(x)$ are formulas.We then have$$\lnot \forall x (P(x)\implies Q(x)) \iff\\exists x (P(x) \land \lnot Q(x))$$$$\lnot \exists x (P(x)\land Q(x) ) \iff\\forall x (P(x)\implies \lnot Q(x))$$The denial of the sentence „all lawn mowers run ongasoline“ is the sentence „some lawn mower doesnot run on gasoline“ (not „no lawn mowers run on gasoline,“ the opposite).We verify the first statement and leave the second for an exercise:$$\lnot \forall x (P(x)\implies Q(x))\iff \exists x \lnot(P(x)\impliesQ(x))\iff \exists x (P(x) \land \lnot Q(x))$$
A formula is usually simpler if $\lnot$ does not appear in front ofany compound expression, that is, it appears only in front of simplestatements such as $P(x)$. The following is an example of simplifyingthe denial of a formula using De Morgan’s laws:$$ \eqalign{ \lnot \forall x (P(x)\lor \lnot Q(x))&\iff \exists x \lnot(P(x)\lor \lnot Q(x))\cr &\iff\exists x (\lnot P(x)\land \lnot \lnot Q(x))\cr &\iff\exists x (\lnot P(x)\land Q(x)) \cr}$$ Denials of formulas are extremely useful. In a later section we willsee that the techniques called proof by contradiction and proof bycontrapositive use them extensively. Denials can also be a helpfulstudy device. When you read a theorem or a definition in mathematicsit is frequently helpful to form the denial of that sentence to seewhat it means for the condition to fail. The more ways you thinkabout a concept in mathematics, the clearer it should become.
Augustus De Morgan. ($y$–1871; DeMorgan himself noted that he was $x$ years old in the year $x^2$.) DeMorgan’s father died when he was ten, after which he was raised by hismother, a devout member of the Church of England, who wanted him to bea minister. Far from becoming a minister, De Morgan developed apronounced antipathy toward the Church, which would profoundlyinfluence the course of his career.
De Morgan’s interest in and talent for mathematics did not becomeevident until he was fourteen, but already at sixteen he enteredTrinity College at Cambridge,where he studied algebra under George Peacockand logic under William Whewell. He was alsoan excellent flute player, and became prominent in musical clubs atCambridge.
On graduation, De Morgan was unable to secure a position at Oxford orCambridge, as he refused to sign the required religious test (a testnot abolished until 1875). Instead, at the age of 22, he becameProfessor of Mathematics at London University, a new institutionfounded on the principle of religious neutrality.
De Morgan wrote prolifically about algebra and logic. Peacock andGregory had already focused attention on thefundamental importance to algebra of symbol manipulation; that is,they established that the fundamental operations of algebra need notdepend on the interpretation of the variables. De Morgan went one(big) step further: he recognized that the operations ($+$, $-$, etc.)also need have no fixed meaning (though he made an exception forequality). Despite this view, De Morgan does seem to have thought thatthe only appropriate interpretations for algebra were familiarnumerical domains, primarily the real and complex numbers. Indeed, hethought that the complex numbers formed the most general possiblealgebra, because he could not bring himself to abandon the familiaralgebraic properties of the real and complex numbers, likecommutativity.
One of De Morgan’s most widely known books was A Budget ofParadoxes. He used the word `paradox‘ to mean anything outside theaccepted wisdom of a subject. Though this need not be interpretedpejoratively, his examples were in fact of the `mathematical crank’variety—mathematically naive people who insisted that they couldtrisect the angle or square the circle, for example.
De Morgan’s son George was himself a distinguished mathematician. Witha friend, he founded the London Mathematical Society and served as itsfirst secretary; De Morgan was the first president.
In 1866, De Morgan resigned his position to protest an appointmentthat was made on religious grounds, which De Morgan thought abused theprinciple of religious neutrality on which London University wasfounded. Two years later his son George died, and shortly thereafter adaughter died. His own death perhaps hastened by these events, DeMorgan died in 1871 of `nervous prostration.‘
The information here is taken from Lectures on Ten BritishMathematicians, by Alexander Macfarlane, New York: John Wiley &Sons, 1916.
Exercises 1.3
Ex 1.3.1Verify these tautologies using truth tables.$$\lnot (P\lor Q)\iff (\lnot P\land \lnot Q)$$$$\lnot (P\land Q)\iff (\lnot P\lor \lnot Q)$$
Ex 1.3.2Suppose $R(x)$ is the statement „$x$ is a rectangle,“ and $S(x)$ is the statement „$x$ is a square.“ Write the followingsymbolically and decide which pairs of statements are denials of eachother:
a) All rectangles are squares.
b) Some rectangles are squares.
c) Some squares are not rectangles.
d) No squares are rectangles.
e) No rectangles are squares.
f) All squares are rectangles.
g) Some squares are rectangles.
h) Some rectangles are not squares.
Ex 1.3.3Write symbolically the following denials of definitions concerning a function $f$:
| a) $f$ is not increasing. | c) $f$ is not constant. |
| b) $f$ is not decreasing. | d) $f$ does not have a root. |
Ex 1.3.4Simplify the following expressions:
| a) $\lnot \forall x>0 (x^2>x)$ | c) $\lnot \forall x \forall y (xy=y^2\implies x=y)$ |
| b) $\lnot \exists x\in (x^2+x | d) $\lnot\exists x \exists y (x>y \land y>x)$ |
Ex 1.3.5Verify the statement:$$\lnot \exists x (P(x)\land Q(x)) \iff\\forall x (P(x) \implies\lnot Q(x))$$
Ex 1.3.6Observe that$$P\lor Q \iff \lnot\lnot (P\lor Q)\iff \lnot (\lnot P\land \lnot Q)$$so $\lor$ can be expressed in terms of $\land$ and $\lnot$.
a) Show how to express $\implies$ in terms of $\land$ and $\lnot$.
b) Show how to express $\land$ in terms of $\lnot$ and $\lor$.
c) Show how to express $\lor$ in terms of $\lnot$ and $\implies$.
Ex 1.3.7Express the universal quantifier$\forall$ in terms of $\exists$ and$\lnot$. Express $\exists$ in terms of $\forall$ and $\lnot$.
Ex 1.3.8Compute the year $y$ of De Morgan’s birth.