Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2016 / Logik und Diskrete Strukturen / Material / Skript zu aussagenlogischen Beweisen


Inhaltsbereich

Skript zu aussagenlogischen Beweisen

Prof. Hofmann's Notizen zu den ersten beiden Vorlesungen; da diese so nicht im Buch enthalten sind. Für die weiteren Vorlesung über diskrete Strukturen wird es keine solche Notizen mehr geben (siehe Buch); erst wieder zum Vorlesungsteil über Logik.

Plain Text icon proofs.txt — Plain Text, 13 KB (13788 bytes)

Dateiinhalt

Junktoren
=========

Mathematische Aussagen werden durch die aussagenlogischen Junktoren zu
neuen Aussagen verbunden.

Junktoren: /\ und, \/ oder, => Implikation, "wenn dann", ~ Negation.
<=> Biimplikation, 

Die Biimplikation versteht sich als Abkuerzung fuer (A=>B) /\ (B=>A)

Die Negation wird eigentlich durch einen Haken notiert. 
Beweise
=======

Waehrend eines Beweises hat man immer einige Annahmen, die man
verwenden darf. Zu den Annahmen gehoeren natuerlich die allgemein
bekannten und gelernten Saetze, aber auch lokale Annahmen, die erst im
Verlaufe des Beweises entstehen und auch wieder verschwinden. Es
besteht eine gewisse Analogie zu Funktions- und Prozedurparametern,
sowie lokalen Programmvariablen.


Beweisregeln fuer durch Junktoren verbundene Aussagen
-----------------------------------------------------


Konjunktion ("und")
-------------------

Ein Beweis von A /\ B besteht aus einem Beweis fuer A und einem fuer B: 


Zeige A/\B

Wir zeigen zunaechst A ...
Nun zeigen wir B ...


Disjunktion ("oder")
--------------------

Ein Beweis von A \/ B besteht aus einem Beweis fuer A oder einem Beweis fuer B.

Zeige A\/B
Wir zeigen A: ....

Alternativ: 

Zeige A\/B
Wir zeigen B: ....



Implikation ("wenn dann")
-------------------------

Ein Beweis von A=>B besteht aus einem Beweis fuer B, wobei A als
Annahme benutzt werden kann.

Zeige A=>B.
Wir nehmen A an (H).
Zeige B....

Hier ist (H) ein Marker fuer die gemachte Annahme. Man kann dann
spaeter darauf zugreifen.

Hat man eine Aussage A als Annahme und muss gerade genau diese zeigen,
dann kann man einfach sagen, dass das zu Zeigende mit der Annahme
folgt.


Beispiel: Sei A eine beliebige Aussage. Man beweise A => A /\ A

Zeige A => A /\ A
Wir nehmen A an (H).
Zeige A /\ A.
   Wir zeigen zunaechst (das erste) A.
      Das ist aber Annahme (H)
   Nun zeigen wir (das zweite) A.
      Das ist ebenso Annahme (H).


Beispiel: Seien A,B beliebige Aussagen. Man beweise A => A \/ B

Zeige A => A \/ B
Wir nehmen A an (H).
Zeige A \/ B
   Wir zeigen A.
   Das ist aber Annahme (H)


Negation ("nicht")
------------------

Um eine Aussage der Form ~A (nicht-A) zu zeigen, nimmt man A an und
muss dann einen Widerspruch herleiten. Einen Widerspruch erhaelt man
immer dann, wenn man sowohl X, als auch ~X fuer irgendeine Aussage
zeigen kann.


Beispiel:

Zeige A => ~~A
Wir nehmen an A (H1).
Zeige ~~A.
Wir nehmen an ~A (H2).
Zeige Widerspruch.
Aus H1 und H2 ergibt sich dieser.



Indirekter Beweis
-----------------

Anstatt eine beliebige Aussage A zu zeigen, kann man auch ~~A zeigen,
also versuchen, aus ~A, der Annahme des Gegenteils, einen Widerspruch
herzuleiten. Das bezeichnet man als *indirekten Beweis*.

Beispiel: 

Zeige ~~A => A.
Wir nehmen an ~~A (H).
Zeige A.
Indirekter Beweis:
Wir nehmen an ~A (H1).
Zeige Widerspruch.
Aus H und H1 ergibt sich dieser.

Beispiel:

Zeige A => ~A => B.  /* ex falso quodlibet */ (nicht gemacht)
Wir nehmen an A (H1) und ~A (H2).
Indirekter Beweis:
Wir nehmen an ~B (H3).
Zeige Widerspruch.
Aus H1 und H2 ergibt sich dieser. 

Zeige A /\ ~A => B. /* ex falso quodlibet */
Wir nehmen an A /\ ~A (H).
Zeige B.
Indirekter Beweis
Annahme ~B
Zeige Widerspruch.
Aus H.1 und H.2


Verwendung von Annahmen mit Junktoren
=====================================


Verwendung einer Konjunktion
----------------------------

Hat man eine Annahme H der Form A /\ B, so kann man neben A /\ B
selbst auch A und B separat abrufen. Diese kann man als H.1 und H.2
bezeichnen.

Beispiel:

Zeige A/\B => B/\A   /* /\ bindet staerker als => */
Wir nehmen an A/\B (H).
Zeige B/\A.
Wir zeigen zunaechst B.
 Das ist H.2.
Wir zeigen nun A.
 Das ist H.1.



Verwendung einer Disjunktion
----------------------------

Hat man eine Annahme der Form A\/B, so kann man das aktuell zu
Zeigende zweimal zeigen, einmal unter der zusaetzlichen Annahme A und
dann noch einmal unter der Annahme B.

Beispiel:

Zeige (B \/ C) => (A => A/\B \/ A/\C) /* Bindereihenfolge ~,/\,\/,=> */
Wir nehmen an B\/C (H).
Zeige  (A => A/\B \/ A/\C).
Wir nehmen an A (H1).
Zeige A/\B \/ A/\C. 
Fuer H ergeben sich zwei Faelle:
1. Fall:  Wir nehmen an B (H2).
Wir zeigen A/\B.
Das ergibt sich aus H1 und H2.
2. Fall: Wir nehmen an C (H3). /* H2 ist nun nicht mehr gueltig */
Wir zeigen A/\C.
Das ergibt sich aus H1 und H3.
QED



Verwendung einer Implikation
----------------------------

Hat man eine Annahme der Form A=>B, so kann man zunaechst einmal
A zeigen und darf dann wieder zum eigentlichen Ziel zurueckkehren, diesmal
aber unter Einfuehrung der Annahme B.

Beispiel:

Zeige (A=>B) => (B=>C) => A=>C
Wir nehmen an A=>B (H1) und B=>C (H2) und A (H3).
Zeige C.
Wir verwenden H2:
   Zunaechst ist B zu zeigen. 
   Wir verwenden H1:
        Zunaechst ist A zu zeigen.
	Das ergibt sich aus H3.
   Wir duerfen nunmehr B (H4) annehmen.
   Also ist B gezeigt (mit H4).
Wir duerfen nunmehr C (H5) annehmen.
Also ist C gezeigt (mit H5).
QED



Schnittregel: Man darf jederzeit eine Behauptung aufstellen, beweisen und dann benutzen.

Beispiel erneut mit Schnittregel:

Zeige (A=>B)=>(B=>C)=>(A=>C)
Annahmen: 
  A=>B (H1)
  B=>C (H2)
  A    (H3)
  Zeige C.
    Zeige zunaechst B.
      Folgt aus (H1) und (H3).
    Annahme B (H5)
    C folgt nun aus (H2) und (H5).
  


Beispiel:

Zeige ((A=>B)=>A)=>A /* Peirce'sche Formel */

Wir nehmen an (A=>B)=>A (H1).
Zeige A.
Indirekter Beweis: Wir nehmen an ~A (H2).
Zeige Widerspruch.
Wir verwenden H1.
   Zunaechst ist A=>B zu zeigen.
   Wir nehmen an A (H3). 
   Indirekter Beweis: Wir nehmen an ~B (H4).
   Zeige Widerspruch.
   Aus H2 und H3 ergibt sich dieser.
Wir duerfen nunmehr A (H5) annehmen.
Der gesuchte Widerspruch ergibt sich aus H2 und H5.
QED.


Eine Negation verwendet man, wie schon gesagt, um Widersprueche herzuleiten.


Beispiel Kontraposition:
  Zeige (A=>B)=>(~B=>~A)
  Annahme A=>B (H1)
  Annahme ~B   (H2)
  Annahme A    (H3)
  Zeige Widerspruch
  Verwende H1
    Zeige A.
      H3
  Annahme B (H4)
  Widerspruch aus H2,H4
  
    
     --------

Schnittregel
============

Manchmal ist es auch sinnvoll, ein Zwischenergebnis "proaktiv"
herzuleiten, also nicht immer nur auf das aktuelle Ziel
hinzuarbeiten. Solch ein Zwischenergebnis kann dann benannt "(H)" und
im weiteren Verlauf wie eine Annahme verwendet werden. Man bezeichnet
die Anwendung dieses Prinzips als *Schnittregel*.

Beispiel:

Zeige (A=>B) => A => (B=>C) => (B=>D) => D.
Wir nehmen an
A=>B (H1), A (H2), B=>C (H3), B=>D (H4).
Zeige D.
   Wir zeigen zunaechst B:
    Das ergibt sich aus H1 und H2. Wir haben also nunmehr
   B (H5).
   Aus H3 und H5 ergibt sich C.
   C (H6).
   Nun koennen wir H4 verwenden. Wir haben bereits B. Also folgt D.
QED. 


=======
Zeihe p,q in N teilerfremd => ~((p/q)^2=2)
  Annahme p,q in N teilerfremd (H1)
  p^2=2q^2 (H2)
  Zeige Widerspruch.
  Aus H1 ergibt sich 
  2|p (H3)
  Also 2^2|p^2
  Also 2^2|2q^2
  Also 2|q (H4)
  H3 und und H4 stehen im Widerspruch zu H.
  
  
Spezialfall: Fallunterscheidung:

Wir zeigen zunaechst fuer beliebige Aussage A die Aussage A \/ ~A (tertium non datur, Satz vom ausgeschlossenen Dritten)

Zeige A \/ ~A.
Indirekter Beweis:
Annahme ~(A \/ ~A) (H)
Zeige Widerspruch.
Verwende H.
Zeige A \/ ~A.
Zeige ~A.
Annahme A (H1).
Zeige Widerspruch.
Ergibt sich aus H1 und H.
QED.

Nun kann man mit der Schnittregel jederzeit A \/ ~A annehmen und dann
darueber eine Fallunterscheidung machen, also das zu zeigende erst
unter Annahme A und dann nocheinmal unter der Annahme ~A zeigen.

Beispiel:

Zeige ~(A /\ B) => ~A \/ ~B. (De Morgansches Gesetz).
Annahme ~(A /\ B) (H).
Zeige ~A \/ ~B.

Annahme A \/ ~A (H1) /* Zulaessig wg Schnittregel */
Verwende H.
Fall 1: Wir nehmen an A (H2).
  Annahme B \/ ~B (H3) /* Zulaessig wg Schnittregel */
  Fall 1.1: Annahme B (H4).
    Widerspruch aus H4 und H.
  Fall 1.2: Annahme ~B (H5).
    Daraus ergibt sich ~A \/ ~B.
Fall 2: Wir nehmen an ~A (H2).
  Daraus ergibt ich ~A \/ ~B.
QED

In aehnlicher Weise zeigt man auch

A /\ ~(B \/ C) => A /\ ~B \/ A /\ ~C

Beispiel aus der Vorlesung.

     
Quantoren
=========

Eine Aussageform oder Praedikat ist eine Aussage, die einen oder
mehrere Parameter, auch Variablen, enthaelt und deren Wahrheitsgehalt
also von diesen abhaengt. Zum Beispiel: "x ist gerade".

Aussageformen koennen mit den Quantoren All x:M und Ex x:M zu neuen
Aussagen und Aussageformen kombiniert werden.

Beispiel:

Ist n eine ungerade natuerliche Zahl, dann ist auch n^2 ungerade.

In formaler Notation:

All n:N. Ungerade(n) => Ungerade(n^2)       /* Satz 0.5 */

Hier ist also Ungerade(n) eine Aussageform, die eben bezeichnen soll,
dass n ungerade ist.

Wir beachten, dass Satz 0.5 eine Aussage ist und keine Aussageform,
denn die Variable n ist durch den Allquantor *gebunden*.

Wir beweisen jetzt Satz 0.5:

Sei n:N eine feste aber beliebige natuerliche Zahl.
Wir nehmen an Ungerade(n) (H).
Zeige Ungerade(n^2).
Wegen H koennen wir n in der Form n=2k+1 schreiben.
Es ist nun n^2=(2k+1)^2 = 2(2k^2+2k)+1.
Also gilt Ungerade(n^2).
QED.

Wir haben hier folgende Beweisregel fuer den Allquantor benutzt:


Beweisregeln fuer den Allquantor
--------------------------------

Um zu zeigen, dass All x:M.A(x) gilt, nimmt man einen festen aber
beliebigen Wert c:M an und muss dann A(c) zeigen. Oft nennt man, wie
oben, den festen aber beliebigen Wert genauso wie die gebundene
Variable, hier x, man muss das aber nicht tun. Umbenennung empfiehlt
sich insbesondere dann, wenn schon ein anderer Wert dieses Namens in
Kraft ist.


Um eine Annahme der Form All x:M.A(x) zu verwenden, darf man A(c) fuer
ein beliebiges, natuerlich moeglichst guenstig gewaehltes c:M
verwenden.

Statt x:M darf man auch einfach x schreiben, wenn der Bereich aus dem
Zusammenhang klar, oder unerheblich ist.

Hier ein allgemeines Beispiel:

Zeige (All x.(A(x)/\B(x))) => (All x.A(x)) /\ (All x.B(x))
Wir nehmen an All x.(A(x)/\B(x)) (H).
Zeige (All x.A(x)) /\ (All x.B(x)).
Wir zeigen zunaechst All x.A(x).
Sei c fest aber beliebig.
Zeige A(c).
Aus H ergibt sich A(c)/\B(c) (H2).
Das zu zeigende A(c) ist H2.1.
Wir zeigen nun All x.B(x).
...


Beweisregeln fuer den Existenzquantor
-------------------------------------

Will man eine Aussage der Form Ex x:M.A(x) zeigen, so muss man einen
geeigneten Wert c:M (moeglichst geschickt) waehlen und dann A(c) zeigen.

Beispiel:

Zeige Ex n.Ungerade(n).
Wir waehlen n=1:
Zeige Ungerade(1).
Es ist aber 1 = 2*0+1, also gilt Ungerade(1).

Hier haben wir "Expertenwissen" ueber das Praedikat "Ungerade"
einfliessen lassen. Hier koennte man die Formalisierung noch etwas weiter
treiben und definieren:

Ungerade(n) :<=> Ex k:N.n=2k+1

Hier steht N fuer die Menge der natuerlichen Zahlen.
Wir koennen nun den Satz 0.5 noch einmal beweisen, brauchen dafuer aber noch
die Beweisregel fuer die Verwendung existenzquantifizierter Annahmen:

Will man eine Annahme der Form Ex x:M.A(x) verwenden, so kann man
stattdessen eine Annahme der Form A(c), wobei c fuer einen festen aber
beliebigen Wert aus M steht. Man darf sich an dieser Stelle keinen
Wert aussuchen, sondern muss die Annahme eben so verwenden, dass der
Beweis fuer jeden Wert c, ganz gleich welchen, funktioniert.

Das Beispiel sollte dies illustrieren:

Zeige All n:N.Ungerade(n) => Ungerade(n^2).
Sei n:N eine feste aber beliebige natuerliche Zahl.
Zeige Ungerade(n) => Ungerade(n^2).
Wir nehmen an Ungerade(n) (H).
Zeige Ungerade(n^2).
Wir verwenden H /* H sagt ja Ex k:N.n=2k+1
und nehmen daher an n=2k+1 (H1) /* hier ist k fest aber beliebig */
Es ist nun n^2=(2k+1)^2 = 2(2k^2+2k)+1.
Wir schliessen also Ex m:N.n^2=2m+1 /* wobei m=2k+1 gewaehlt wurde */
Das aber ist Ungerade(n^2). 
QED.

An diesem Beispiel sehen wir auch eine weitere implizite Beweisregel.

Man darf jederzeit gleiches durch gleiches ersetzen (hier (2k+1)^2 =
2(2k^2+2k)+1). Manchmal ergeben sich solche Gleichungen auch erst aus
dem Abrufen von Annahmen. 

Hier noch ein weiteres abstraktes Beispiel zum Existenzquantor:

Zeige (Ex x:M.A(x)\/C) => (Ex x:M.A(x)) \/ C
Wir nehmen an Ex x:M.A(x)\/C (H).
   Zeige (Ex x:M.A(x)) \/ C. 
   Sei c:M fest aber beliebig gewaehlt.
   Unter Verwendung von H koennen wir also
   annehmen A(c)\/C (H1).
   Wir verwenden H1:
   1.Fall.
       A(c) (H2).
       Wir zeigen Ex x:M.A(x).
       Das aber folgt aus H2 mit x=c.
   2.Fall
       C (H2).
       Wir zeigen C.
       Das aber ist gerade H2.


Komplizierteres Beispiel: sqrt(2) ist irrational
================================================

Satz: Die reelle Zahl sqrt(2) ist nicht rational, also nicht von der Form
p/q mit p und q aus N und teilerfremd.

Zeige ~Ex p:N.Ex q:N. (All r:N.r|p /\ r|q => r=1) /\ p^2 = 2 * q^2.
Wir nehmen an
Ex p:N.Ex q:N. (All r:N.r|p /\ r|q => r=1) /\ p^2 = 2 * q^2 (H)
Zeige Widerspruch.
Wir fixieren f.a.b. p:N und q:N. sodass
(All r:N.r|p /\ r|q => r=1) /\ p^2 = 2 * q^2 (H1).
Wegen H1.2 gilt 2|p^2 (H2).
Da 2 eine Primzahl ist, gilt auch 2|p (H3).
Also 4|p^2 (H4).
Es folgt 2|q (H5).
Aus H2.1 mit r=2 ergibt sich
2|p /\ 2|q => 2=1.
Mit H3 und H5 liefert das den gewuenschten Widerspruch. 
QED.

Hier wurde mit Gleichheit gearbeitet, z.B. wenn r|a und a=b, dann auch
r|q, und ausserdem einiges an Expertenwissen ueber die Teilbarkeit
verwendet, z.B.  2|ab => 2|a \/ 2|b, weil 2 eine Primzahl ist. Wir
sehen hier, dass dieses Expertenwissen auch in Form logischer Aussagen
formuliert werden kann und es kann auch mit den hier beschriebenen
Methoden formal bewiesen werden. Allerdings braucht man gewisse
unbewiesene Grundannahmen, die Axiome, welche dann nicht mehr bewiesen
werden koennen. Diese sind erstaunlich einfach und wir werden auf ihre
Rolle spaeter noch einmal zurueckkommen.

Allerdings werden wir uns im Hauptteil dieses Kurses erlauben, aus
Schule und Vorlesung bekanntes Expertenwissen ohne weitere
Rechtfertigung in Beweisen zu verwenden, so wie hier geschehen.

Mengen





Artikelaktionen


Funktionsleiste