Lösungen 1 Zum Mathematik-brückenkurs

Transcript

Lösungen 1 zum Mathematik-Brückenkurs für alle, die sich für Mathematik interessieren Carl Hammann, µFSR, TU Dresden Version vom 30. September 2015, Fehler und Verbesserungsvorschläge bitte an [email protected] 1 Mengenlehre und Logik Aufgabe 1.1. Welche der folgenden Ausdrücke sind Aussagen? Begründe! Wenn der Ausdruck eine Aussage ist, entscheide, ob sie wahr oder falsch ist! 1. 1 + 1 = 2 2. In Dresden ist das Wetter gut. 3. Ich mag Mathematik. 4. Johann Sebastian Bach. 5. Pferde sind Paarhufer. 6. Dieser Satz ist eine Aussage. 7. Dieser Satz ist keine Aussage. 8. Dieser Satz ist eine wahre Aussage. 9. Dieser Satz ist eine falsche Aussage. Lösung. Diese Antworten sind nur ein Vorschlag, man könnte sich auch andere Gedanken machen! (Außer vielleicht in Punkt 1 bis 4) 1. wahre Aussage (Wir gehen einfach davon aus, dass dieser Ausdruck das bedeutet, was wir denken, das er bedeutet. Diese Frage verdeutlicht, dass man immer einen Kontext braucht, um entscheiden zu können, ob etwas wahr oder falsch ist.) 2. Hängt vom Ort und vom Zeitpunkt, an dem es gesagt wird, ab. Damit ist es nicht möglich, aus diesem Satz selbst zu erkennen, ob er wahr ist. Also keine Aussage. 1 3. Hängt vom Sprecher ab. Damit ist es nicht möglich, aus diesem Satz selbst zu erkennen, ob er wahr ist. Also keine Aussage. 4. Ist nur ein Name. Damit ist die Frage nach wahr oder Falsch sinnlos. Also keine Aussage. 5. falsche Aussage. Pferde sind Unpaarhufer. 6. wahre Aussage. 7. falsche Aussage. (Dieser und der 6. Satz bilden ein Paar, das aus einer Aussage und ihrer Negation besteht. Wenn also der sechste Satz wahr ist, sollte dieser falsch sein. Allerdings ist es eine Frage, ob man diese Art Selbstbezüglichkeit, die in beiden Sätzen zu Tage tritt, noch für Aussagen zulassen will oder nicht. In diesem Sinne sind insbesondere die Antworten 6 und 7 diskutabel.) 8. keine Aussage, denn man kann nicht sinnvoll entscheiden, ob der Satz wahr oder falsch ist. Wenn er wahr ist, muss seine Negation (also Satz 9) falsch sein. Wir wir gleich erörtern werden, ist das beides aber sinnlos. 9. keine Aussage, denn man kann nicht sinnvoll entscheiden, ob der Satz wahr oder falsch ist: Angenommen, er sei wahr. Dann muss er, um wahr zu sein eine falsche Aussage sein. Wenn man andererseits annimmt, der Satz sei falsch, dann müsste seine Negation wahr sein, also müsste er eine wahre Aussage sein. Aufgabe 1.2. Stelle die Wahrheitstabellen für folgende Aussagen auf: a ⇒ b, b ⇒ a, ¬ a ∨ b, ¬b ⇒ ¬ a, a ⇔ b, ( a ⇒ b) ∧ (b ⇒ a), a ⊕ b, ( a ∨ b) ∧ ¬( a ∧ b). Was fällt dir auf? Formuliere die gefundenen logischen Sachverhalte in natürlicher Sprache und gib Beispiele. Lösung. Die Wahrheitstabelle: a 0 1 0 1 b 0 0 1 1 a⇒b 1 0 1 1 b⇒a 1 1 0 1 ¬a ∨ b 1 0 1 1 ¬b ⇒ ¬ a 1 0 1 1 Es fällt auf, dass 1. ( a ⇒ b) = (¬ a ∨ b) = (¬b ⇒ ¬ a) 2. ( a ⇒ b) 6= (b ⇒ a) 3. ( a ⇔ b) = (( a ⇒ b) ∧ (b ⇒ a)) 4. ( a ⊕ b) = (( a ∨ b) ∧ ¬( a ∧ b)) 2 a⇔b 1 0 0 1 ( a ⇒ b) ∧ (b ⇒ a) 1 0 0 1 a⊕b 0 1 1 0 ( a ∨ b) ∧ ¬( a ∧ b) 0 1 1 0 In natürlicher Sprache bedeutet die erste Gleichheit in 1., dass aus a b folgt, wenn a falsch ist oder b richtig. Ein Beispiel dafür ist, Dr. Frankenstein, der herausfinden will, ob eine Substanz Superkräfte verleiht, seinem Igor eine Dosis gibt und dann sieht, ob sich etwas verändert. Den Fall, dass Igor keine Dosis bekommen hat, muss Dr. Frankenstein nicht überprüfen. Die zweite Gleichheit bedeutet in diesem Beispiel, dass, wenn Igor die Dosis eingenommen hat und keine Superkräfte entwickelt, die Substanz auch nicht wirksam ist. Die nicht-Gleichheit in 2. ist ein wichtiges Caveat: Wenn aus a b folgt, muss nicht auch aus b a folgen! Wenn Dr. Frankensteins Substanz tatsächlich Superkräfte verleiht, muss das nicht heißen, dass jemand mit Superkräften die Substanz auch genommen hat. Die dritte Gleichheit sagt, dass a und b äquivalent sind, wenn aus a b folgt und auch aus b a folgt. So beweist man fast alle Äquivalenzen. Die letzte Gleichheit charakterisisert das exklusive Oder als das „Entweder-Oder“ des alltäglichen Sprachgebrauches. Während also in der Mathematik ein „a oder b“ fast immer a ∨ b meint, also insbesondere, dass auch a und b zutreffen können, schließt das exklusive Oder das aus. Ein Beispiel ist die bekannte Tatsache, dass viele Meschen gereitzt reagieren, wenn ein Mahtematikstudent auf eine Oder-Frage mit „ja“ antwortet: „Kommst du noch mit an die Elbe grillen oder bleibst du lieber zu Hause?“ – „Ja.“ Aufgabe 1.3. Beweise die De Morgan’schen Regeln: ¬( a ∨ b) = ¬ a ∧ ¬b und ¬( a ∧ b) = ¬ a ∨ ¬b für Aussagen a und b. Was bedeuten sie in natürlicher Sprache? Lösung. Betrachte folgende Wahrheitstabelle: a 0 1 0 1 b 0 0 1 1 ¬( a ∨ b) 1 0 0 0 ¬ a ∧ ¬b 1 0 0 0 ¬( a ∧ b) 1 1 1 0 ¬ a ∨ ¬b 1 1 1 0 Damit sind die De Morgan’schen Regeln bewiesen. Die erste Regel bedeutet, dass, wenn man unter einem „guten Konzert“ ein Konzert versteht, das Spaß macht oder neuartige Musik bietet (oder beides, denn unser Oder ist inklusiv!), ein schlechtes Konzert eines ist, das keinen Spaß macht und auf dem nur schon bekannte Musik gespielt wird. Die zweite bedeutet, zum Beispiel, dass, wenn man „gutes Sommerwetter“ als „Sonnenschein und mindestens 25 Grad Celsius“ definiert, das Wetter schlecht ist genau dann, wenn die Sonne nicht scheint oder es kälter als 25 Grad Celsius ist (oder beides). Aufgabe 1.4. Gibt es eine zusammengesetzte Aussage mit Teilaussagen a, b und c (jede mindestens einmal!), die genau die Junktoren ∧ und ∨ benutzt (jeden mindestens einmal!), und bei der Klammersetzung den Wahrheitswert nicht verändert? Begründe! 3 Lösung. Diese Aufgabe soll eine Knobelaufgabe bleiben. Wer eine Lösung findet, darf sie an [email protected] schicken. Aufgabe 1.5. Sei der Individuenbereich die Gesamtheit aller Menschen. Schreibe die folgenden Aussagen mit Quantoren, wobei du nur die Aussagen K ( x, y, z) für „z ist ein Kind von x und y“ und M( x ) für „x ist männlich“ verwendest! Für die Zwecke dieser Aufgabe (und nur dafür) nehmen wir an, dass jeder Mensch entweder männlich oder nicht männlich, was weiblich sei, ist. 1. a ist ein Einzelkind. 2. a ist ein Cousin von b. 3. a hat genau eine Schwester. 4. Niemand ist sein eigener Vater. Lösung. 1. ∀ x, y, z : (K ( x, y, a) ∧ K ( x, y, z)) ⇒ ( a = z)   
2. M ( a) ∧ ∀w, v, x, y : K (v, w, a) ∧ K ( x, y, b) ⇒ ∃s, t : (K (s, t, v) ∧ K (s, t, x )) ∨ 
(K (s, t, v) ∧ K (s, t, y)) ∨ (K (s, t, w) ∧ K (s, t, x )) ∨ (K (s, t, w) ∧ K (s, t, y)) 3. ∀ x, y : K ( x, y, a) ⇒ (∃!z : K ( x, y, z) ∧ ( a 6= z) ∧ ¬ M(z))
4. ∀ x, y, z : (K ( x, y, z) ∧ M ( x )) ⇒ ( x 6= z) Aufgabe 1.6. Schreibe die Aussagen ∃!x : A( x ) und @x : A( x ), wobei du nur die Quantoren ∃ und ∀ verwendest!
Lösung. Es gilt (∃!x : A( x )) = ∃ x : A( x ) ∧ (∀y : (y 6= x ) ⇒ ¬ A( x )) und (@x : A( x )) = (∀ x : ¬ A( x )). Aufgabe 1.7. Verneine die Aussagen ∀ x : A( x ) und ∃ x : A( x )! Welches Prinzip fällt dir auf? Kann man es auch auf eine Aussage wie ∀ x ∃y, z : B( x, y, z) anwenden? Wie verhalten sich die Quantoren @ und ∃!? Lösung. Es gilt ¬(∀ x : A( x )) = (∃ x : ¬ A( x )) und ¬(∃ x : A( x )) = (∀ x : ¬ A( x )). Die Quantoren ∃ und ∀ werden also vertauscht und die Aussage hinter dem Doppelpunkt verneint. Auch Aussagen mit mehreren Vorkommen der Quantoren ∀ und ∃ kann man auf diese Weise negieren, so gilt zum Beispiel ¬(∀ x ∃y, z : B( x, y, z)) = (∃ x ∀y, z : ¬ B( x, y, z)). Die Quantoren ∃! und @ kann man auf diese Weise nicht direkt verneinen, sondern muss zuerst die Umformulierungen aus Aufgabe 1.6 anwenden. 4 Aufgabe 1.8. Gib jeweils beispielhafte Aussagen A( x ) und B( x ) (und einen Individuenbereich) an, die belegen, dass im Allgemeinen (∀ x : A( x ) ∨ B( x )) 6= (∀ x : A( x )) ∨ (∀ x : B( x )) und (∃ x : A( x ) ∧ B( x )) 6= (∃ x : A( x )) ∧ (∃ x : B( x ))! Lösung. Der Individuenbereich sei die Menge aller Autos. Sei A( x ) die Aussage „x fährt schnell“ und B( x ) die Aussage „x ist sparsam“. Die Formel (∃ x : A( x ) ∧ B( x )) 6= (∃ x : A( x )) ∧ (∃ x : B( x )) bedeutet dann, dass die Aussagen „es gibt ein Auto, dass schnell fährt und sparsam ist“ und „es gibt ein sparsames Auto und ein schnelles Auto“ unterschiedlich sind. Sei nun der Individuenbereich die Menge aller Tage des Jahres und A( x ) die Aussage „an x regnet es“ und B( x ) die Aussage „an x scheint die Sonne“. Die Formel (∀ x : A( x ) ∨ B( x )) 6= (∀ x : A( x )) ∨ (∀ x : B( x )) bedeutet dann, die Aussagen „An jedem Tag scheint die Sonne oder es regnet“ und „Das ganze Jahr über scheint die Sonne oder das ganze Jahr über regnet es“ unterschiedlich sind. Aufgabe 1.9. Seien A( x ), B( x ) Aussagen mit A( x ) ⇒ B( x ). Zeige, dass dann { x | A( x )} ⊆ { x | B( x )}! Lösung. Sei x ∈ { x | A( x )}. Dann gilt A( x ). Nach Voraussezung gilt dann auch B( x ), womit x ∈ { x | B( x )}. Aufgabe 1.10. Zeige, dass für zwei Mengen A und B gilt, dass A = B ⇔ ( A ⊆ B) ∧ ( B ⊆ A)! (Diese Eigenschaft wird oft verwendet, um zu zeigen, dass zwei Mengen gleich sind.) Lösung. Wir beweisen die Äquivalenz, indem wir zuerst eine und dann die andere Implikation überprüfen. Diese Vorgehensweise ist „erlaubt“, wie wir uns in Aufgabe 1.2 überlegt haben. Gelte also zunächst A = B. Dann ist für alle a ∈ A auch a ∈ B, also gilt A ⊆ B Ferner gilt auch für alle b ∈ B gilt b ∈ A, also folgt B ⊆ A. Sei nun A ⊆ B und B ⊆ A. Dann gilt wegen A ⊆ B für jedes a ∈ A, dass a ∈ B und wegen B ⊆ A, dass für jedes b ∈ B auch b ∈ A gilt. Damit gilt für beliebiges x, dass x ∈ A ⇔ x ∈ B, also A = B. Aufgabe 1.11. Beweise, dass jede Menge eine Obermenge der leeren Menge ist! Lösung. Sei A eine Menge. Dann gilt für jedes Element a der leeren Menge, dass a ∈ A (es gibt ja keine, also ist nichts zu überprüfen!). Damit ist A ⊇ ∅. Aufgabe 1.12. Beweise, dass die symmetrische Differenz tatsächlich symmetrisch ist, d.h. dass für je zwei Mengen A und B gilt, dass A4 B = B4 A! Dazu kannst du entweder direkt anhand der Definition arbeiten oder die Aussage von Aufgabe 1.10 verwenden oder zuerst (z.B. mit einem Venn-Diagramm) beweisen, dass A4 B = ( A \ B) ∪ ( B \ A) und dann benutzen, dass für beliebige Mengen M und N die Aussage M ∪ N = N ∪ M in offensichtlicher Weise gilt. Lösung. Folgende drei Venn-Diagramme illustrieren, dass A4 B = ( A \ B) ∪ ( B \ A). 5 A B (a) B \ A B A (b) A \ B A B (c) A4 B Wegen der Symmetrie von ∪ gilt also A4 B = ( A \ B) ∪ ( B \ A) = ( B \ A) ∪ ( A \ B) = B4 A. Aufgabe 1.13. Schreibe die Potenzmenge der Menge A := {∅, {∅}} auf! Gibt es eine Menge, deren Potenzmenge A ist? Lösung. Es gilt P( A) = {∅, {∅}, {{∅}}, {∅, {∅}}}. A ist die Potenzmenge der einelementigen Menge {∅}. Aufgabe 1.14. Die Menge A habe n Elemente. Erkläre, warum P( A) dann 2n Elemente hat! Lösung. Es gilt P(∅) = {∅}, also hat P(∅) = 20 = 1 Element und die Behauptung stimmt. Sei also nun A 6= ∅. Wie viele Möglichkeiten gibt es nun eine Teilmenge B von A auszuwählen? – Für jedes Element von A entscheidet man, ob es zu B gehören soll; dafür gibt es zwei Möglichkeiten, nämlich „ja“ oder „nein“. Da diese Entscheidungen für jedes Element von A unabhängig voneinander sind, hat man also 2| · 2 .{z . . 2 · 2} = 2n n-mal Möglichkeiten. Damit hat P( A) gerade 2n Elemente. Aufgabe 1.15. Seien A und B Mengen. Beweise A × B = ∅ ⇔ A = ∅ ∨ B = ∅! Lösung. Sei zunächst A = ∅ ∨ B = ∅. Ohne Einschränkung sei A = ∅. Dann gilt A × B = {( a, b)| a ∈ ∅, b ∈ B} = ∅. Andererseits: Falls A 6= ∅ ∧ B 6= ∅, gibt es ein a0 ∈ A und ein b0 ∈ B also enthält A × B mindestens das Paar ( a0 , b0 ). Aufgabe 1.16. Sei A eine Menge mit n Elementen und B eine Menge mit m Elementen. Wie viele Elemente hat A × B? Begründe! Lösung. A × B hat n · m Elemente. Das kann man so sehen: Man bezeichne die Elemente von A mit a1 , . . . , an und die Elemente von B mit b1 , . . . , bn . Dann enthält für jedes feste ai die Menge A × B alle Paare ( ai , b j ), wobei j ∈ {1, . . . , m}. Das sind also für jedes ai schon m Elemente; weil es aber n verschiedene („verschiedene“ – das ist wichtig, weil dann die Paare auch verschieden sind!) ai gibt, folgt dass es n × m Paare gibt. 6 Aufgabe 1.17. Wir alle kennen aus der Schule das Distributivgesetz der Multiplikation und Addition reller Zahlen: Für a, b, c ∈ R gilt a · (b + c) = a · b + a · c. Für welche der bis jetzt definierten Mengenoperationen gelten auch Distributivgesetze? Wenn Distributivgesetze gelten, gibt sie an! Ebenso wissen wir, dass die Addition reller Zahlen monoton ist, das heißt, für Zahlen a, b, α, β ∈ R gilt a ≤ α ∧ a ≤ β ⇒ a + b ≤ α + β. Welche der bis jetzt definierten Mengenoperationen sind monoton (wobei man natürlich „≤“ mit „⊆“ ersetzen muss)? Du kannst dir, wenn du unsicher bist, mit Venn-Diagrammen helfen. Lösung. Wir bearbeiten hier nur beispielhaft ein Paar der vielen Aufgaben. Wer konkrete Fragen oder Probleme hat, kann sie an [email protected] schicken. Die hier gezeigten Beispiele illustrieren, welche Gedanken man sich machen sollte. Es gilt zum Beispiel für Mengen A, B, C folgendes Distributivgesetz: A × ( B ∪ C ) = A × B ∪ A × C, denn A × ( B ∪ C ) = {( a, b)| a ∈ A ∧ (b ∈ B ∨ b ∈ C )} (warum?) und mit Aufgaben 1.10 und 1.9 folgt die Behauptung (wie?). (Gilt auch ( A ∪ B) × C = ( A × C ) ∪ ( B × C )?) Als Beispiel zweier Mengenoperationen, für die kein Distributivgesetz gilt, betrachte \ und ∩: Für A = {1, 2, 3}, B = {1, 2} und C = {3, 4} gilt A \ ( B ∩ C ) = A \ ∅ = A 6= ∅ = {3} ∩ {1, 2} = ( A \ B) ∩ ( A \ C ). Gilt das Distributivgesetz, in dem die Rollen von ∪ und \ vertauscht sind, also A ∩ ( B \ C ) = ( A ∩ B ) \ ( A ∩ C )? Beispiele monotoner Mengenoperationen sind ∪ und ∩, wie man sich leicht überlegt. Ein Beispiel einer nicht-monotonen Mengenoperation ist \, denn zum Beispiel für A = {1, 2, 3}, B = {2, 3, 4}, C = {1, 2, 3, 4} und D = {1, 2, 3, 4} gilt A \ B = {1} ⊇ ∅ = C \ D aber A ⊆ C und B ⊆ D. Wenn man allerdings nur die linke Menge verändert, ist \ wieder monoton. 7