Aussagenlogik und Beweisprinzipien – Mathe Studium 1. Semester Arbeitsblatt Lösungen zum Herunterladen als PDF

← Zurück zu den Aufgaben

1. Lösung zu Aufgabe 1

   a) Aussage, falsch: \(91=7\cdot13\).
   b) Aussage, wahr: Ein Quadrat reeller Zahlen ist nie negativ.
   c) Keine Aussage, denn eine Aufforderung hat keinen Wahrheitswert.
   d) Keine Aussage, sondern eine Aussageform: Der Wahrheitswert hängt von \(x\) ab (wahr für \(x=4\), sonst falsch). Erst ein Quantor („es gibt ein \(x\)“ oder „für alle \(x\)“) macht sie zur Aussage.

2. Lösung zu Aufgabe 2

   a) \(\neg A\wedge B\): f, f, w, f. Nur in der dritten Zeile ist \(A\) falsch und \(B\) wahr.
   b) \(A\Rightarrow\neg B\): Zeile 1: \(w\Rightarrow f\) ergibt f; Zeile 2: \(w\Rightarrow w\) ergibt w; Zeile 3: \(f\Rightarrow f\) ergibt w; Zeile 4: \(f\Rightarrow w\) ergibt w. Ergebnis: f, w, w, w.
   c) \(A\Leftrightarrow B\): w, f, f, w. Genau in einer Zeile wahr ist nur \(\neg A\wedge B\).

3. Lösung zu Aufgabe 3

   a) Wahr: Die Voraussetzung \(2+2=5\) ist falsch, daher ist die Implikation wahr (ex falso quodlibet).
   b) Wahr: Voraussetzung wahr, Folgerung „\(7\) ist prim“ ebenfalls wahr.
   c) Falsch: Voraussetzung wahr, Folgerung falsch.
   d) Wahr: Die Voraussetzung \(3<2\) ist falsch.

4. Lösung zu Aufgabe 4

   a) \(\neg(x>2\wedge x\text{ gerade})\equiv x\le2\) oder \(x\) ungerade.
   b) \(\neg(x\le1\vee x\ge5)\equiv x>1\) und \(x<5\), also \(1<x<5\).
   c) Negation einer Implikation ist \(A\wedge\neg B\): „\(x\) ist durch \(6\) teilbar und nicht durch \(3\) teilbar“. Diese Aussage ist nie wahr, die ursprüngliche Implikation also stets wahr.
   d) \(0<x<4\) heißt \(x>0\wedge x<4\). Negation: \(x\le0\) oder \(x\ge4\).

5. Lösung zu Aufgabe 5

   a) Negation: \(\exists x\in\mathbb R:\ x^2\le0\). Die Ausgangsaussage ist falsch (Gegenbeispiel \(x=0\)).
   b) Negation: \(\forall n\in\mathbb N:\ n^2\ne2n\). Die Ausgangsaussage ist wahr mit \(n=2\), denn \(4=4\).
   c) Negation: \(\exists x\ \forall y:\ x+y\ne0\). Die Ausgangsaussage ist wahr: Zu jedem \(x\) wählt man \(y=-x\).
   d) Negation: \(\forall y\ \exists x:\ x+y\ne0\). Die Ausgangsaussage ist falsch: Zu jedem festen \(y\) liefert \(x=1-y\) den Wert \(x+y=1\ne0\).

6. Lösung zu Aufgabe 6

   a) Umkehrung: „Wenn \(n\) gerade, dann durch \(4\) teilbar“ – falsch (\(n=2\)). Kontraposition: „Wenn \(n\) ungerade, dann nicht durch \(4\) teilbar“ – wahr, wie das Original.
   b) Umkehrung: „Wenn \(x^2>9\), dann \(x>3\)“ – falsch (\(x=-4\)). Kontraposition: „Wenn \(x^2\le9\), dann \(x\le3\)“ – wahr, wie das Original.
   c) Das Original ist falsch (\(n=2\)). Umkehrung: „Wenn \(n\) ungerade, dann Primzahl“ – falsch (\(n=9\)). Kontraposition: „Wenn \(n\) gerade, dann keine Primzahl“ – falsch (\(n=2\)), wie das Original.

7. Lösung zu Aufgabe 7

   a) Drei Aussagen: \(2^3=8\) Zeilen. Zeilen \((K,P,S)\): www: w; wwf: w; wfw: w; wff: f; fww: w; fwf: f; ffw: w; fff: f.
   b) In 5 von 8 Zeilen (www, wwf, wfw, fww, ffw).
   c) \(K=w,\ P=f,\ S=f\): \(K\wedge P=f\) und \(S=f\), also \(Z=f\) – die Tür bleibt zu.
   d) \(\neg Z\equiv\neg(K\wedge P)\wedge\neg S\equiv(\neg K\vee\neg P)\wedge\neg S\): Karte oder PIN fehlt, und der Sicherheitsdienst bestätigt nicht.

8. Lösung zu Aufgabe 8

   a) \(\forall s\in S:\ M(s)\Rightarrow L(s)\).
   b) \(\exists s\in S:\ M(s)\wedge\neg L(s)\): „Es gibt jemanden mit Mahnung, der kein Buch ausgeliehen hat.“
   c) \(\exists s:\ L(s)\wedge\neg M(s)\). Das ist nicht die Negation von a), sondern eine andere Aussage: \(L\) und \(M\) sind vertauscht.
   d) \(\forall s:\ \neg L(s)\Rightarrow\neg M(s)\): „Wer kein Buch ausgeliehen hat, hat auch keine Mahnung.“

9. Lösung zu Aufgabe 9

   a) Tautologie: Beide Seiten haben die Wertefolge w, f, w, w.
   b) Keine Tautologie: links w, f, w, w, rechts w, w, f, w; sie unterscheiden sich in den Zeilen wf und fw. Die Umkehrung ist nicht äquivalent.
   c) Tautologie: Beide Seiten sind nur in der Zeile wf wahr (f, w, f, f).
   d) Keine Tautologie: In der Zeile wf ist die Voraussetzung \(A\vee B\) wahr, die Folgerung \(A\wedge B\) falsch.

10. Lösung zu Aufgabe 10

    a) Seien \(m=2a+1\), \(n=2b+1\). Dann \(mn=4ab+2a+2b+1=2(2ab+a+b)+1\), ungerade. \(\square\)
    b) \(n+(n+1)+(n+2)=3n+3=3(n+1)\), also durch \(3\) teilbar. \(\square\)
    c) \(n=2k+1\): \(n^2=4k^2+4k+1=4k(k+1)+1\). Da \(k(k+1)\) das Produkt zweier aufeinanderfolgender Zahlen und damit gerade ist, ist \(4k(k+1)\) durch \(8\) teilbar. \(\square\)

11. Lösung zu Aufgabe 11

    a) Kontraposition: Ist \(n\) ungerade, so ist \(n^2\) ungerade. Mit \(n=2k+1\): \(n^2=2(2k^2+2k)+1\). \(\square\)
    b) Kontraposition: Ist \(3\nmid n\), so \(3\nmid n^2\). Fall \(n=3k+1\): \(n^2=3(3k^2+2k)+1\). Fall \(n=3k+2\): \(n^2=3(3k^2+4k+1)+1\). In beiden Fällen bleibt der Rest \(1\). \(\square\)
    c) Kontraposition: Ist \(a\) gerade oder \(b\) gerade, so ist \(ab\) gerade. Mit \(a=2k\) gilt \(ab=2(kb)\). \(\square\)

12. Lösung zu Aufgabe 12

    a) Angenommen \(\sqrt3=\frac pq\) mit teilerfremden \(p,q\). Dann \(p^2=3q^2\), also \(3\mid p^2\), nach Aufgabe 11 auch \(3\mid p\), \(p=3r\). Es folgt \(9r^2=3q^2\), also \(q^2=3r^2\) und \(3\mid q\) – Widerspruch zur Teilerfremdheit. \(\square\)
    b) Angenommen, \(s>0\) wäre die kleinste positive Zahl. Dann ist \(\frac s2>0\) und \(\frac s2<s\) – Widerspruch. \(\square\)
    c) Angenommen, es gäbe sie. Dann ist \(x^2=4y+2\) gerade, also ist \(x\) gerade, \(x=2m\), und \(4m^2=4y+2\). Dividiert man durch 2, folgt \(2m^2=2y+1\): links gerade, rechts ungerade – Widerspruch. \(\square\)

13. Lösung zu Aufgabe 13

    a) Falsch: \(n=40\) liefert \(1600+40+41=1681=41^2\). Für \(n=0,\dots,39\) ergibt die Formel Primzahlen, daher täuscht die Regel.
    b) Falsch: \(a=b=1\) ergibt \((1+1)^2=4\ne2\).
    c) Wahr: Gerade Zahlen größer als \(2\) haben den Teiler \(2\) und sind nicht prim.
    d) Falsch: Für \(x=-2\) ist \(\sqrt4=2\ne-2\). Richtig ist \(\sqrt{x^2}=|x|\).

14. Lösung zu Aufgabe 14

    a) \(\exists\varepsilon>0\ \forall N\ \exists n\ge N:\ |a_n-a|\ge\varepsilon\).
    b) Es gibt eine Toleranz \(\varepsilon\), sodass zu jedem \(N\) noch ein späteres Folgenglied mindestens \(\varepsilon\) von \(a\) entfernt liegt.
    c) Wähle \(\varepsilon=1\). Zu jedem \(N\) gibt es ungerade \(n\ge N\) mit \(|(-1)^n-1|=2\ge1\). \(\square\)
    d) \(\varepsilon=1\) genügt: Ist \(a\ge0\), liegen alle ungeraden Folgenglieder (\(-1\)) mindestens \(1+a\ge1\) von \(a\) entfernt; ist \(a<0\), tun das alle geraden (\(+1\)) mit Abstand \(1-a>1\). Jeder Kandidat scheitert.

15. Lösung zu Aufgabe 15

    a) Aussage von \(X\): \(\neg R_X\vee\neg R_Y\).
    b) Ist \(X\) Lügner, dann ist seine Aussage falsch, also gilt \(R_X\wedge R_Y\), insbesondere \(R_X\) – im Widerspruch zu „\(X\) ist Lügner“.
    c) Also ist \(X\) Ritter, seine Aussage ist wahr, und wegen \(R_X\) muss \(\neg R_Y\) gelten: \(Y\) ist Lügner.
    d) Die Aussage wäre \(\neg R_X\wedge\neg R_Y\). Wäre \(X\) Ritter, müsste sie wahr sein und \(\neg R_X\) enthalten – Widerspruch. Also ist \(X\) Lügner, seine Aussage ist falsch, und damit ist nicht beides Lüge: \(Y\) ist Ritter.

16. Lösung zu Aufgabe 16

    a) \(Q\): Zeile ww: \(A\vee B=w\), aber \(\neg(A\wedge B)=f\), also f; Zeile wf: w und w, also w; Zeile fw: w; Zeile ff: \(A\vee B=f\), also f. Ergebnis f, w, w, f.
    b) \(Q\) ist das ausschließende Oder (XOR): genau dann wahr, wenn sich \(A\) und \(B\) unterscheiden. Es liefert das Summenbit im Halbaddierer.
    c) Nach De Morgan ist \(\neg(A\wedge B)\equiv\neg A\vee\neg B\); einsetzen liefert die Behauptung.
    d) \(2^8=256\) Zeilen.

17. Lösung zu Aufgabe 17

    a) \(n^3-n=n(n^2-1)=(n-1)\,n\,(n+1)\).
    b) Von zwei aufeinanderfolgenden Zahlen ist eine gerade. Rest von \(n\) modulo \(3\): Ist er \(0\), ist \(n\) teilbar; ist er \(1\), ist \(n-1\) teilbar; ist er \(2\), ist \(n+1\) teilbar. Weitere Fälle gibt es nicht.
    c) Da \(2\) und \(3\) teilerfremd sind, ist das Produkt durch \(2\cdot3=6\) teilbar. \(\square\)
    d) \(n=7\): \(343-7=336=6\cdot56\). \(n=-4\): \(-64+4=-60=6\cdot(-10)\).

18. Lösung zu Aufgabe 18

    a) Aus \(\log_23=\frac pq\) folgt \(2^{p/q}=3\).
    b) Potenzieren mit \(q\): \(2^p=3^q\).
    c) Die linke Seite ist gerade (\(p\ge1\)), die rechte ungerade, da ein Produkt ungerader Zahlen ungerade ist (Aufgabe 10a). Widerspruch. \(\square\)
    d) Widerspruchsbeweis. Wegen \(2^1<3\) ist \(\log_23>1>0\), ein positiver Bruch lässt sich mit \(p,q\ge1\) schreiben.

19. Lösung zu Aufgabe 19

    a) R1: \(\neg A_1\Rightarrow\neg A_2\); R2: \(A_2\Rightarrow L\); R3: \(\neg L\).
    b) Kontraposition von R2: \(\neg L\Rightarrow\neg A_2\). Mit R3 folgt \(\neg A_2\): Lena hat Analysis 2 nicht belegt.
    c) Nein. R1 sagt nur etwas für den Fall \(\neg A_1\); aus \(\neg A_2\) folgt nichts über \(A_1\), denn das wäre die Umkehrung von R1.
    d) Umkehrung von R2: \(L\Rightarrow A_2\). Wegen \(\neg L\) ist diese Regel nicht anwendbar; über \(A_2\) könnte man dann nichts schließen. Ja, b) ändert sich.

20. Lösung zu Aufgabe 20

    a) Die ersten Schritte (Multiplikation mit \(a\), Subtraktion von \(b^2\), Faktorisieren) sind korrekte Folgerungen.
    b) Gekürzt wurde der Faktor \(a-b=0\). Division durch null ist nicht erlaubt; die Gleichung \(x\cdot0=y\cdot0\) gilt für alle \(x,y\).
    c) Mit \(a\ne b\) darf gekürzt werden; dann ist aber die Voraussetzung \(a=b\) im nächsten Schritt nicht mehr erfüllt – der Beweis ist leer.
    d) Aus \(1=-1\) folgt durch Quadrieren \(1=1\): Die Folgerung ist wahr, die Ausgangsaussage falsch. Nur umkehrbare Schritte (Äquivalenzen) dürfen rückwärts gelesen werden.

21. Lösung zu Aufgabe 21

    a) Angenommen, jedes Fach enthielte höchstens ein Objekt. Dann gäbe es höchstens \(n\) Objekte, im Widerspruch zu \(n+1\) Objekten. \(\square\)
    b) Angenommen, an jedem Tag haben höchstens \(4\) Personen Geburtstag. Dann gäbe es höchstens \(4\cdot365=1460\) Personen, aber es sind \(1466>1460\) – Widerspruch.
    c) Die Reste bei Division durch \(12\) sind \(0,\dots,11\): 12 Fächer für 13 Zahlen. Zwei Zahlen haben denselben Rest, ihre Differenz ist durch \(12\) teilbar. \(\square\)
    d) Nein: Die Zahlen \(0,1,\dots,11\) haben paarweise Differenzen von \(1\) bis \(11\), keine ist durch \(12\) teilbar.