Hausübungen

Gliederung

  1. 15. Oktober 2007
  2. 22. Oktober 2007
  3. 29. Oktober 2007
  4. 5. November 2007
  5. 12. November 2007
  6. 19. November 2007
  7. 26. November 2007
  8. 3. Dezember 2007
  9. 10. Dezember 2007
  10. 7. Januar 2008
  11. 14. Januar 2008
  12. 21. Januar 2008
  13. 28. Januar 2008

Verwandte Seiten

  1. Die Lehrveranstaltung
  2. Logikrechner
  3. Logikübergang
  4. Christian Gottschall

15. Oktober 2007

Freiwillige Hausübung zum Nachdenken und zum Erwerb von Pluspunkten:

Bild eines kauenden Schafes
  1. Überlegen Sie, ob Sie eine Wahrheitstafel für den einstelligen Junktor (Satzoperator) "Es ist möglich, dass" aufstellen können, wie er zum Beispiel im Satz "Es ist möglich, dass es morgen regnet" auftritt. Schreiben Sie auf oder zeichnen Sie, was Ihnen dabei durch den Kopf geht, und demonstrieren Sie anschließend gegen die Aufgabenstellung.
  2. Gedenken Sie des zweistelligen, Kausalität ausdrückenden Konnektivs "weil", wie es z.B. im Satz "Die Erde wurde zerstört, weil sie einer intergalaktischen Schnellstraße im Weg stand" auftritt. Gelingt es Ihnen, für dieses Konnektiv eine Wahrheitstabelle aufzustellen? Und wenn ja, warum nicht?
  3. Können Sie bereits eine Wahrheitstabelle für die Aussage ~(P ∧ Q) aufstellen?

22. Oktober 2007

Bild eines schlafenden Katers

  1. Versuchen Sie bitte, für einige der folgenden Aussagen Wahrheitstabellen aufzustellen.
    Wenn Sie Lust dazu haben, dann können Sie Ihre Lösungen mit den zentralen Verarbeitungen meines Logikübergangs überprüfen. (Neiiin! Überprüfen hab ich gesagt, nicht lösen...)

    1. (P → Q) ∨ (Q → P)
    2. P ∧ ~P
    3. P ∨ ~P
    4. ~(P ∧ ~P)
    5. (P → Q) ∧ (R → P) (schwierig!)
    6. ((P → Q) ∧ ((Q → R) ∧ (R → S))) → (~S → ~P) (Sehr schwierig! Mit dem Logikübergang lösen: Hier fest niedermausen und auf der erscheinenden Seite die Schaltfläche "Verarbeitung" wählen.)

  2. Welche der folgenden Argumente sind gültig?
    Erinnern Sie sich daran, dass ein Argument genau dann gültig ist, wenn unter der Voraussetzung, dass alle Prämissen wahr sind, auch die Konklusion wahr ist.

    1. P ∧ Q also Q ∧ P
    2. P ∨ Q also P
    3. P ∧ ~P also P → Q (schwierig - mehr eine Denksportaufgabe)
    4. P, Q also R ∨ ~R (auch mehr eine Denksportaufgabe)
    5. P → Q, P also Q
    6. P → Q, ~Q also ~P

29. Oktober 2007

Bild einer trinkenden Gans
  1. Welche Eigenschaften haben die folgenden Aussagen?
    1. P → (Q → P)
    2. P→(Q ∨ P)
    3. (Q ∨ P) → P
    4. ~((P → (Q → R)) → ((P → Q) → (P → R))) (schwierig)
    5. P ∨ (Q ∨ R)
    6. (P → ~P) → ~P
    7. ~(P → P)
  2. Welche der folgenden Argumente sind gültig?
    1. P ∧ Q also P
    2. P → Q also ~P ∨ Q
    3. P → Q also ~(P ∧ ~Q)
    4. ~P ∨ Q also P → Q
    5. ~(P ∧ ~Q) also P → Q
    6. P also P ∧ Q
    7. ~(P ∧ ~P) also P ∧ ~P

5. November 2007

Hinweis: Es sind diesmal recht viele Beispiele. Sie müssen natürlich nicht alle lösen - am besten wählen Sie aus jeder Gruppe zwei oder drei Stück aus.

Ein Feuersalamander denkt über die Lösung der letzten Aufgabe nach

  1. Versuchen Sie bitte, für möglichst viele der folgenden Wahrheitswertverläufe je mindestens einen Satz zu finden, der genau diesen Wahrheitswertverlauf hat:

    1. W-F-W-W
    2. F-W-W-W (einfach)
    3. F-F-F-W
    4. F-W-F-F
    5. W-W-F-F (schwierig)
    6. W-W-W-W

    Anmerkung: Der Wahrheitswertverlauf ist vierzeilig, das heißt der gesuchte Satz wird zwei unterschiedliche Satzbuchstaben enthalten müssen.

    Ein Beispiel: den Wahrheitswertverlauf W-F-F-F erzeugen unter anderem die drei Sätze P ∧ Q, ~(P → ~Q) sowie ~(Q → ~P).

  2. Wenn Sie auf dem Gebiet der Wahrheitstabellen noch nicht ganz sattelfest sind beziehungsweise wenn Ihre Wahrheitstabellen bei der letzten Hausübung noch nicht ganz standfest waren, üben Sie bitte noch ein bisschen weiter und stellen Sie für ein paar der folgenden Sätze Wahrheitstabellen auf (schreiben Sie ruhig auch alle komplexeren Zwischenergebnisse auf, man vertut sich dann weniger leicht):

    1. ~(P ∨ Q)
    2. ~P ∨ ~Q
      Wenn Sie den Wahrheitswertverlauf der Sätze 1 und 2 vergleichen, werden Sie sehen, dass es sich um ganz unterschiedliche Sätze handelt (bei der ersten Hausübung haben noch einige Teilnehmer/innen diese beiden Sätze für gleichwertig gehalten).
    3. P ∨ ~Q
    4. ~(~P ∨ Q)
    5. ~(P ∨ ~Q)
    6. (P → Q) ∧ (Q → P)
    7. ~(P ∨ R) ∧ ~(R → P)
      Die beiden letzten Beispiele sind etwas komplizierter, weil es mehr Zwischenergebnisse gibt.

  3. Denksportaufgabe: Wieviele dreistellige Verknüpfungen gibt es in der klassischen Aussagenlogik, und warum haben wir für keine einzige von ihnen ein eigenes Zeichen (=einen eigenen Junktor)?

  4. Wir haben uns heute dreiviertelformal davon überzeugen können, dass die beiden Konnektivmengen {~,∧} sowie {~,v} funktional vollständig sind, das heißt dass sich nur mit den beiden Konnektiven ~ und ∧ einerseits sowie nur mit den beiden Konnektiven ~ und ∨ andererseits jeeeedes Konnektiv ausdrücken lässt.

    1. Ist auch die Konnektivmenge {~,→} funktional vollständig? Um diese Frage positiv beantworten zu können würde es ausreichen, wenn es gelänge, eines der Konnektive ∧ und ∨ mit Hilfe von ~ und → auszudrücken.
    2. Können Sie zeigen, dass der Sheffer-Operator, das heißt der Operator mit der Wahrheitstafel F-W-W-W, alleine ausreicht, um alle anderen Konnektive auszudrücken?

12. November 2007

Ein Schaf wendet Formationsregeln an

  1. Bilden Sie mit Hilfe der Formationsregeln einige wohlgeformte Sätze, die Ihnen besonders gut gefallen.

  2. Welche der folgenden Zeichenketten sind wohlgeformte Sätze der von uns erlernten logischen Sprache, welche der folgenden Zeichenketten sind keine wohlgeformten Sätze der von uns erlernten logischen Sprache, warum sind diejenigen der folgenden Zeichenketten, die wohlgeformte Sätze der von uns erlernten logischen Sprache sind, wohlgeformte Sätze der von uns erlernten logischen Sprache, und warum sind diejenigen der folgenden Zeichenketten, die keine wohlgeformten Sätze der von uns erlernten logischen Sprache sind, keine wohlgeformten Sätze der von uns erlernten logischen Sprache? Und was könnte man denjenigen der folgenden Zeichenketten angedeihen lassen, die keine wohlgeformten Sätze der von uns erlernten logischen Sprache sind, damit sie wohlgeformte Sätze der von uns erlernten logischen Sprache werden?

    1. P ∧∧ Q
    2. P ∧ (Q ∧ R)
    3. (P ∧ (Q ∧ R)
    4. (P ∧ Q) ∨ (Q → P)
    5. (P → (Q → R) → ((P → Q) → (P → R)))
    6. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~P
    7. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~P → Q
    8. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~(P → Q)
    9. ~~~~~~(~~~~~~~~~~~~~~~~~~~~~~P → Q)

  3. Auf Grund der Formationsregel 1 wissen wir, dass die beiden Satzbuchstaben P sowie Q wohlgeformte Sätze der von uns erlernten logischen Sprache sind. Auf Grund der Formationsregel 2 wissen wir, dass wir vor P ein Verneinungszeichen schreiben dürfen und dass die entstehende Zeichenkette, ~P, ebenfalls ein wohlgeformter Satz der von uns erlernten logischen Sprache ist. Auf Grund von Formationsregel 3 wissen wir, dass die Zeichenkette (~P ∧ Q) ebenfalls ein wohlgeformter Satz der von uns erlernten logischen Sprache ist. Wiederum auf Grund von Formationsregel 1 wissen wir, dass die Zeichenkette ~(~P ∧ Q) ein wohlgeformter Satz der von uns erlernten logischen Sprache ist.

    Auf Grund welcher Formationsregeln sind nun die folgenden Ausdrücke wohlgeformte Sätze der von uns erlernten logischen Sprache?

    1. (P → ~Q)
    2. (~P ∨ ~Q)
    3. ((P → Q) ∨ (Q → P))

  4. Schaffen Sie es bereits, ein paar der folgenden Argumente herzuleiten, d.h. die Konklusion zu erzeugen, indem sie die Ihnen bereits bekannten Schlussregeln anwenden? (Selbstverständlich dürfen Sie auch die Ihnen unbekannten Schlussregeln anwenden.)

    1. P, Q |- ((P ∧ Q) ∧ P)
    2. ((P ∧ Q) ∧ R) |- (P ∧ Q)
    3. ((P ∧ Q) ∧ R) |- R
    4. (P ∧ Q), R |- ((P ∧Q) ∧ R)

19. November 2007

Pferde bilden Aussagen in polnischer Notation

  1. Die polnische Notation ist eine sehr einfache Schreibweise, mit der sich logische Ausdrücke (und mathematische Formeln) klammerfrei und gänzlich intuitiv niederschreiben und erfassen lassen. Wenn Sie dieser Aussage zustimmen, dann möchten Sie vielleicht einige Aussagen in polnische Notation übersetzen und einige andere Aussagen rückübersetzen.

    Erinnern Sie sich daran, dass N für die Negation, K für die Konjunktion, A für die Disjunktion ("Alternation") und C für das Konditional steht.

    1. ((P → Q) ∨ (Q → P))
    2. (P ∨ Q)
    3. (Q ∨ P)
    4. ((P ∧ Q) → P)
    5. (P ∧ (Q → P))
    6. ((P → Q) → (~Q → ~P))
    7. CKpqr
    8. CpKqr
    9. CApqAqp
    10. CAApqqp
    11. CpAAqqp
    12. CCpCqrCCpqCpr

  2. Bestimmen Sie bitte den Typ jedes der obigen Sätze, das heißt ermitteln Sie, ob es sich um eine Negation, eine Konjunktion, eine Disjunktion, ein Konditional oder um sonstwas handelt.

    Beispiele: Der zweite und der dritte Satz sind Disjunktionen.

  3. In welcher Notation ist es einfacher, die vorangehende Aufgabe zu lösen? Was ist der Grund dafür?

  4. Wenn Sie Lust dazu haben, Argumente herzuleiten, dann finden Sie vielleicht unter den folgenden einige, die Ihnen zusagen.

    1. (P → Q), (R → Q), (P ∧ R) |- Q
    2. (P → Q), (R → S), (P ∧ R) |- (Q ∧ S)
    3. (P ∧ (Q ∧ R)) |- ((P ∧ Q) ∧ R) (Assoziativität der Konjunktion)
    4. ((P ∧ Q) ∧ R) |- (P ∧ (Q ∧ R) (Assoziativität der Konjunktion)
    5. (P ∧ P) |- P
    6. P |- (P ∧ P)

26. November 2007

Ziegen sind eng mit Schafen verwandt und lieben die Pfeil-Einführung

Wählen Sie aus den folgenden Argumenten ein oder zwei Dutzend und leiten Sie diese her:

  1. P → Q, P ∨ Q |- Q
  2. (P → Q) ∨ (P → R), P |- Q ∨ R
  3. Kpq |- CrKpKrq
  4. (P ∧ Q) ∨ (P ∧ R) |- P ∧ (Q ∨ R) (eines der Distributivgesetze - schwierig)
  5. P ∧ (Q ∨ R) |- (P ∧ Q) ∨ (P ∧ R) (eines der Distributivgesetze - schwierig)
  6. KApqApr |- ApKqr (eines der Distributivgesetze - schwierig)
  7. P ∨ (Q ∧ R) |- (P ∨ Q) ∧ (P ∨ R) (eines der Distributivgesetze - schwierig)
  8. P ∨ Q, Q → R |- (P → R) → R
  9. (P ∨ Q) → R |- P → R
  10. P → R |- (P ∧ Q) → R
  11. (P ∧ Q) → R, R → S |- (P ∧ Q) → S
  12. (P ∨ Q) → R, R → S |- P → S
  13. P → R, Q → R |- (P ∧ Q) → R
  14. P → R, Q → R |- (P ∨ Q) → R

3. Dezember 2007

Allegorie zur Logikprüfung Achtung: Anscheinend gibt es Browser und Betriebssysteme, die das HTML-Tag → (Pfeil nach rechts) nicht korrekt darstellen, sondern statt dessen ein Kästchen anzeigen. Wenn Sie vor einer solchen Softwarekombination sitzen, dann denken Sie sich bitte anstelle aller Kästchen Rechtspfeile.

  1. Versuchen Sie, wenn Sie Lust dazu haben, die folgenden drei klassischen Schlussfiguren herzuleiten, ohne in Ihre heutige Mitschrift zu schielen:

    1. modus ponendo tollens: ~(P ∧ Q), P |- ~Q
    2. modus tollendo ponens: (P ∨ Q), ~P |- Q (Die versprochene Alternativlösung, bei der nicht mit einer vB, sondern mit einem indirekten Beweis begonnen wird, finden Sie im Anschluss.)
    3. modus tollendo tollens: P → Q, ~Q |- ~P

      4. Und hier die versprochene Alternativlösung für den modus tollendo ponens, die sich in der Übungsstunde nicht mehr ausgegangen ist:

       1.  P ∨ Q                                 Prämisse
 2.  ~P                                    Prämisse
 3.     ~Q                               * A
 4.        P                             * A
 5.        ~P                            * 2Reit
 6.        P & ~P                        * 4,5&E
 7.     P -> (P & ~P)                    * 4-6->E
 8.        Q                             * A
 9.        ~Q                            * 3Reit
10.        Q & ~Q                        * 8,9&E
11.           ~(P & ~P)                  * A
12.           Q & ~Q                     * 10Reit
13.        P & ~P                        * 11-12~B
14.     Q -> (P & ~P)                    * 8-13->E
15.     P ∨ Q                            * 1Reit
16.     P & ~P                           * 15,14,7vB
17.  Q                                     3-16~B

  2. Die folgenden Argumente sind relativ einfach herzuleiten:

    1. P, ~Q |- ~(P ∧ Q)
    2. P → Q |- ~Q → ~P
    3. P → Q, Q → R |- ~R → ~P
    4. P ∧ ~P |- R → S
    5. P ∧ ~P |- R ∧ ~R
    6. P → Q |- ~(P ∧ ~Q)
    7. ~(P ∨ Q) |- ~P ∧ ~Q
    8. (P → Q) ∨ (P → R), ~Q, ~R |- ~P

  3. Es ist nicht der Fall, dass die folgenden Argumente relativ einfach herzuleiten sind:

    1. P ∨ Q, ~P → ~Q |- P
    2. |- ~(P ∧ ~P) (Hier liegt die Schwierigkeit nicht in der Herleitung, sondern im Fehlen von Prämissen)
    3. ~(P ∧ ~Q) |- P → Q
    4. ~P ∨ Q |- P → Q
    5. P → Q |- ~P ∨ Q
    6. ~(P ∧ Q) |- ~P ∨ ~Q
    7. |- (P → Q) ∨ (Q → P) (besonders schwer)
    8. |- P ∨ ~P (auch nicht der leichtesten eines)

10. Dezember 2007

Weihnachtsprüfung

Heute waren wir alle sehr brav und haben wir unsere erste Logikprüfung gemacht. Aus diesem Grunde gibt es heute nur eine kleine Hausübung.

Diejenigen, die bei der Prüfung nicht die Aufgaben beider Gruppen gelöst haben, können die jeweils nicht behandelte Gruppe gerne als Quelle zusätzlicher Hausübungsaufgaben heranziehen. Und diejenigen, deren Verlangen nach Herleitungen schon quälend groß geworden ist, finden vielleicht in meinem Übungsskriptum weitere für sie interessante Beispiele.

  1. Versuchen Sie, P ∨ (Q → R) |- ~P → (~Q ∨ R) herzuleiten.

    Achtung: In der ursprünglichen Angabe war ein Tippfehler enthalten und lautete die Konklusion ~R → (~Q v P) (P und R waren also vertauscht). Dieses Argument wäre nicht gültig! Generell können und sollten Sie - wenn Sie Zweifel an der Gültigkeit eines Arguments haben - eine semantische Überprüfung vornehmen, entweder manuell oder mit dem Logikübergang (dort wiederum können Sie kein ganzes Argument auf einmal eingeben, sondern nur einzelne Sätze, aber das macht ja nichts).

  2. Versuchen Sie, (P ∧ Q) → R |- P → (Q → R) herzuleiten.
  3. Versuchen Sie, ~P ∨ Q |- P → Q herzuleiten.

7. Januar 2008

Sehen Sie mit hoffnungsfrohem Blick die folgenden prädikatenlogischen Ausdrücke an. Ermitteln Sie die exakte Bedeutung dieser Ausdrücke, übersetzen Sie diese in die deutsche Sprache und überlegen Sie, worin die Unterschiede, Gemeinsamkeiten und Zusammenhänge dieser Aussagen bestehen.

Wenn Ihr Browser bzw. Ihr Betriebssystem keine Sonderzeichen darzustellen in der Lage ist, finden Sie unter jedem Beispiel eine Übersetzung in Lateinschrift, bei der das große "A" für den Allquantor und das große "E" für den Existenzquantor steht.

  1. ∀x∀yLxy
    (AxAyLxy)
  2. ∀x∀yLyx
    (AxAyLyx)
  3. ∀xLxx
    (AxLxx)
  4. ∀x∃yLxy
    (AxEyLxy)
  5. ∀x∃yLyx
    (AxEyLyx)
  6. ∃xLxx
    (ExLxx)
  7. ∃x∀yLxy
    (ExAyLxy)
  8. ∃x∀yLyx
    (ExAyLyx)
  9. ∃x∃yLxy
    (ExEyLxy)
  10. ∃x∃yLyx
    (ExEyLyx)

14. Januar 2008

Wie wäre es damit, einige der nachfolgenden Argumente herzuleiten?

  1. ∀x(Fx ∧ Gx) |- ∃x(Gx ∧ Fx)
    Ax(Fx & Gx) |- Ex(Gx & Fx)
  2. ∀x∀yLxy |- ∃xLxx
    AxAyLxy |- ExLxx
  3. ∀xFx ∧ ∀xGx |- ∃x(Fx ∧ Gx)
    AxFx & AxGx |- Ex(Fx & Gx)
  4. ∀x(Fx → Gx), ∀x¬Gx |- ∃x¬Fx
    Ax(Fx -> Gx), Ax~Gx |- Ex~Fx

21. Januar 2008

Auch heute habe ich wieder ein paar schöne Beispiele für Sie:

  1. ∃xFx |- ¬∀x¬Fx
    ExFx |- ~Ax~Fx
  2. ∀xFx |- ¬∃x¬Fx
    AxFx |- ~Ex~Fx
  3. ∀x(Fx→Gx), ∃x(Fx∧Gx) |- ∃x(Gx∨Hx)
    Ax(Fx->Gx), Ex(Fx&Gx) |- Ex(Gx&Hx)
  4. &exist(Fx∨Gx) |- ∃xFx∨∃xGx
    Ex(Fx v Gx) |- ExFx v ExGx

28. Januar 2008

  1. ∃x(Fx∧Gx), ∀x(Gx→Hx) |- ∃xHx
    Ex(Fx&Gx), Ax(Gx->Hx) |- ExHx
  2. ∀x(Fx∧Gx), ∀x(Fx→Hx) |- ∀xHx
    Ax(Fx&Gx), Ax(Fx->Hx) |- AxHx
  3. ∀xFxx |- ∀x∃yLyx
    AxFxx |- AxEyLyx
    Hinweis: Verwechseln Sie hinsichtlich der Einschränkungen nicht die Existenzquantorbeseitigung mit der Existenzquantoreinführung - bei letzterer gibt es keinerlei Einschränkungen, insbesondere darf man z.B. von Laa auf ∃xLax schließen (wenn Anton sich selber liebt, dann gibt es jemanden, der Anton liebt).
  4. ∃y∀xLyx |- ∀x∃yLyx
    EyAxLyx |- AxEyLyx
    Hinweis: Von einem indirekten Beweis odgl. würde ich abraten; versuchen Sie lieber eine ∃B.

2008/04/16 21:48:31
christian.gottschall@posteo.de