Zum Inhalt springen

Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Arbeitsblatt 4



Übungsaufgaben

Es sei  Γ={p,¬q,r→s}⊆LV  (p,q,r,s seien Aussagenvariablen). Welche der folgenden Aussagen lassen sich aus Γ ableiten?

p→q,¬p→q,p→¬q,¬p→¬q,r→q,(r→q)→¬p,(s→p)→(r→¬q),(¬q→¬p)→s.



Zeige, dass man aus Γ={p} unendlich viele Aussagen ableiten kann, die keine Tautologien sind.



Es sei  Γ⊆LV  eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge V. Zeige die folgenden Regeln für die Ableitungsbeziehung (dabei seien α,β,γ,αi Aussagen).

  1. Konjunktionsregel: Γ⊢α∧β genau dann, wenn Γ⊢α und Γ⊢β.
  2. Kettenschlussregel: Wenn Γ⊢α→β und Γ⊢β→γ, dann auch Γ⊢α→γ.
  3. Modus ponens: Wenn Γ⊢α und Γ⊢α→β, dann ist auch Γ⊢β.
  4. Wenn Γ⊢α, so auch Γ⊢β→α.
  5. Wenn Γ⊢α1,…,Γ⊢αn und Γ⊢α1∧…∧αn→β, dann auch Γ⊢β.
  6. Widerspruchsregel: Wenn Γ⊢α und Γ⊢¬α, dann auch Γ⊢β.
  7. Fallunterscheidungsregel: Wenn Γ⊢α→β und Γ⊢¬α→β, dann auch Γ⊢β.



Es sei Γ⊆LV eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge V und es seien α,β∈LV. Zeige, dass

Γ∪{α}⊢β

zu

Γ⊢α→β

äquivalent ist.



Es sei Γ⊆LV eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge V und es sei α∈LV. Es gelte

Γ⊬α.

Zeige, dass dann

Γ∪{¬α}

widerspruchsfrei ist.



Es sei  Γ⊆LV  eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge V. Zeige, dass die Ableitungsbeziehung Γ⊢α die Folgerungsbeziehung Γ⊨α impliziert.



Es sei V={p,q,r} eine Aussagenvariablenmenge. Welche der folgenden Aussagen aus LV lassen sich aus  Γ=V  ableiten?

  1. p,
  2. p∧q→r,
  3. ¬p∧q→r,
  4. ¬p∧¬q→¬r,
  5. p→(q→r),
  6. p→(q→¬r),
  7. ¬q.



Es sei  Γ⊆LV  eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge V und α∈LV. Es gelte Γ⊢α. Zeige, dass es dann auch eine endliche Teilmenge  Δ⊆Γ  mit Δ⊢α gibt.



Es sei LV die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge V und es sei λ eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation I. Zeige, dass I⊨ maximal widerspruchsfrei ist.



Führe die Einzelheiten im Beweis zu Lemma 4.7 für die Implikation durch.



Es sei Γ⊆LV eine widerspruchsfreie, aber nicht maximal widerspruchsfreie Aussagenmenge, die unter Ableitungen abgeschlossen sei. Zeige, dass Γ nicht durch die Hinzunahme von endlich vielen Aussagen zu einer maximal widerspruchsfreien Aussagenmenge aufgefüllt werden kann.




Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei Γ={p,¬q→r}⊆LV (p,q,r seien Aussagenvariablen). Welche der folgenden Aussagen lassen sich aus Γ ableiten?

p→q,¬q→p,¬p→r,¬q→r∧p,¬r→q,r→(q→¬p).



Aufgabe (3 Punkte)

Es sei Γ⊆LV eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge V. Zeige, dass folgende Aussagen äquivalent sind.

  1. Γ ist widersprüchlich.
  2. Für jedes β∈LV ist Γ⊢β und Γ⊢¬β.
  3. Es ist Γ⊢=LV.



Aufgabe (4 Punkte)

Es sei p eine Aussagenvariable und α∈LV eine Aussage, in der die Variable p nicht vorkommt. Es gelte

{p}⊢α.

Zeige, dass bereits

⊢α

gilt.



Aufgabe (3 Punkte)

Es sei V eine Aussagenvariablenmenge. Konstruiere eine Ausdrucksmenge Γ⊆LV, die abgeschlossen unter Ableitungen und nicht maximal widerspruchsfrei ist, die aber die Eigenschaft besitzt, dass für jede Aussagenvariable p sowohl (Γ∪{p})⊢ als auch (Γ∪{¬p})⊢ maximal widerspruchsfrei ist.



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2016) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)