Kann mir jemand helfen, das Gesetz von De Morgan zu beweisen? In meiner Logikklasse verwenden wir ein sehr einfaches Regelwerk für Ableitungen und ich kann beim besten Willen nicht herausfinden, wie ich damit das Gesetz beweisen kann. Es sind keine Hausaufgaben; Mein TA gab mir zusätzliche Probleme zum Üben für das Midterm. Übrigens, ich weiß, dass dieser Artikel dieselbe Frage stellt, aber ich verstehe die Notation nicht, daher weiß ich nicht, ob sie auf dieselben Regeln beschränkt sind.
Beweisen Sie p&q <-> ~(~pV~q) und/oder pvq <-> ~(~p&~q) nur mit diesen Regeln: &Intro/Elim, vIntro/Elim, ~Intro/Elim, ->Intro/Elim, <->Intro/Elim. Bitte verwenden Sie auch diese Notation.
Soweit ich das beurteilen kann, sollte der Beweis so aussehen:
|pVq Hyp
|-
||~p&~q Hyp[for ~Intro]
||-
||~p &Elim[~p^~q]
||q **I'm not sure how to prove that ~p -> q with the limited rules**
||~q &Elim[~p^~q]
|~(~p&~q) ~Intro[~p&~q, q, ~q]
Du bist auf dem richtigen Weg.
Aus der Annahme [a] : ¬p ∧ ¬q leiten Sie ¬p und ¬q korrekt durch ∧-Elimination ab:
1) p ∨ q --- Prämisse
2) ¬p ∧ ¬q --- angenommen [a]
3) ¬p --- aus 2) durch ∧-Elim
4) ¬q --- aus 2) durch ∧-Elim
5) p --- angenommen [b] für ∨-Eliminierung
6) ⊥ --- Widerspruch, aus 3) und 5)
7) q --- angenommen [c] für ∨-Eliminierung
8) ⊥ --- Widerspruch, aus 4) und 7)
9) ⊥ --- aus 1), 5)-6) und 7)-8) durch ∨-Elimination, Entladung von [b] und [c]
10) ¬(¬p ∧ ¬q) --- aus 2) und 9) durch ¬-Einleitung, die Annahme [a] auflösend
(p ∨ q) → ¬(¬p ∧ ¬q) --- aus 1) und 10) per →-Einleitung.
Um zu beweisen:
¬(¬p ∧ ¬q) → (p ∨ q) ,
wir brauchen :
1) ¬(¬p ∧ ¬q) --- Prämisse
2) ¬(p ∨ q) --- angenommen [a]
3) p --- angenommen [b]
4) p ∨ q --- durch ∨-Einführung
5) ¬p --- aus 3) durch ¬-Einleitung und den Widerspruch zwischen 2) und 4), Entladung [b]
6) q --- angenommen [c]
7) p ∨ q --- durch ∨-Einführung
8) ¬q --- aus 6) durch ¬-Einleitung und den Widerspruch zwischen 2) und 7), Entladung [c]
9) ¬p ∧ ¬q --- aus 5) und 8) per ∧-Einleitung
10) ¬¬(p ∨ q) --- aus 2) durch ¬-Einleitung und den Widerspruch zwischen 1) und 9), Entladung [a]
11) (p ∨ q) --- aus 10) durch doppelte Negation -Elimination
¬(¬p ∧ ¬q) → (p ∨ q) --- aus 1) und 11) per →Einführung.
virmaior
Cort Ammon