Beweistechniken


Definition



Eine mögliche Definition von Beweis:
Ein Beweis ist eine Folge von Aussagen so dass jede Aussage entweder elementar ist oder elementar aus den anderen geschlussfolgert werden kann.
Die letzte Aussage ist die zu beweisende.

alternative Betrachtung:

Ein Beweis ist eine Reihe von Argumenten, die dem Leser von der Richtigkeit der Aussage überzeugen.

Direkte Beweise


Beispiel 1


6 teil n => 9 teilt n²

∃k∈Z : n =6*k                   Definition
∃k∈Z : n =2*3*k                Zerlegung
∃k∈Z : n²=(2*3)²*k²          Quadrieren
∃k∈Z : n²=3*3*2*2*k²       Kommutativität und Assoziativität
∃l       : n²=3*3*l                wähle l=2*2*k²
∃l       : n²=9*l
            9 teilt n²                 Definition

Beispiel 2


Erste Binomische Formel: 
∀a,b∈R: (a + b)² = a² + 2ab + b²

möglichst elementarer Beweis: (Vorteil: Maschinenlesbar)
∀a,b,c∈R    : (a + b)*c = a*c + b*c                    Distributivgesetz
∀a,b∈R       : (a+b)(a+b)=a(a+b) +b(a+b)         Einsetzen von c=a+b
∀a,b∈R       : (a+b)(a+b)=aa+ab+ba+bb           Distributivgesetz
∀a,b∈R       : (a+b)² = a² +ab+ba+b²                 Definition von Quadrat-Schreibweise
∀a,b∈R       : (a+b)² = a² +ab+ab+b²                 Kummultativgesetz
∀a,b∈R       : (a+b)² = a² +2a*b+b²                    Addition

einfacher aufgeschrieben:
(a + b)² = (a+b)(a+b)
             = a(a+b)+b(a+b)
             = a² +ab+ab+b²
             = a² +2a*b+b²

Indirekte Beweise


Definition


Wie nehmen eine Aussage an, von der wir eigentlich annehmen, dass sie nicht gilt und generieren daraus einen Widerspruch.
Daraus folgt, dass die Aussage gilt.

Beispiel 1


p → q                       p=1 und q=0
≡ ¬q → ¬p
≡ ¬p ⋁  q      ≡  ¬(p⋀¬q)
≡ (p  ⋀ ¬q )  → 0     falsche Aussage

Beispiel 2


Lemma (

https://de.wikipedia.org/wiki/Hilfssatz

)


Es existiert unendlich viele Primzahlen.

Beweis

(☇ = Widerspruch)
Wir nehmen an (um einen Widerspruch zu erzeugen) dass es nur endlich viele Primzahlen gibt.
Sagen wir p1, p2, ... , pn. Sei k=p1*p2 ... pn+1.
Wir zeigen keine der Primzahlen p1 bis ... pn teilt k.
*STERNCHEN*

Anmerkung: a | b    "a teilt b"    <=> ∃l∈Z : a*l=b

☇ Ausnahme ∃i        :   pi | k
             aber               pi |(p1 ... pn)
             =>                 pi |[k-p1....pn]
             =>                 Pi | 1
Fall 1: k ist selbst prim dann haben einen Widerspruch
Fall 2: k ist in Primzahlen zerlegbar. Von dem ist keine eine p1 ... pn

Beispiel 3


Lemma


Alle nartürlichen Zahlen sind interessant.

Beweis


Wir nehmen an es existieren uninteressante natürliche Zahlen.
M = { n | n uninteressant }
Welche ist die kleineste Zahl in M
Das interessiert mich aber.  ☇

*MITTAGSPAUSE*

Beispiel 4


Lemma


 √2 ist irrational

Beweis ☇


Annahme  √2 ist rational. Das heißt 3ab∈Z : √2= a/b
Das heißt es gibt auch a,b∈Z, welche teilerfremd (?) sind.

Definition


a,b teilerfremd <=> ∀c c|a ud c|b
=> (c=1) oder (c=-1)
=> a/b = √2
=> a  = √2 *b
=> a² = 2*b²                Definition von Teilbarkeit
=> 2 | a²
=> 2 | a            (*)
( => 4 | a² )
=> ∃l:  a  = 2*l       Definition von (*)
=>      a² = 2²*l²     Quadrieren
=>     4l² = 2 b²      Mit der 3. Zeile
=>     2l² = b²        durch 2 teilen
=>     2|b²
=>     2|b 
=> a und haben den gemeinsamen Teiler 2 ☇

Beispiel 5


Lemma


n² gerade => n gerade

Beweis ☇


n ungerade
=> ∃a: n  = 2a+1
=>     n² = 4a²+4a+1
=>     n² = 2(2a²+2a)+1
=> ∃b: n² = 2b+1
=> n² ungerade ☇

Beweise per Fallunterscheidung


Wenn gilt r1 ⋁ r2 ⋁ ... ⋁ rn
Und wir für jedes (ri ⋀ p) → q
Dann gilt azcg p → q

Beispiel


Sei n gerade => n(n+1)(n+2)
ist durch 8 teilbar.

Beweis


Fall 1: 2|n aber 4 ∤ n
        =>∃k∈Z   n = 4k+2
        =>     n+2 = 4k+2
        => 4 teilt (n+2)
        => 8 teilt n(n+1)(n+2) 
           wird nicht geglaubt (elementar zerlegt):
           n(n+1)(n+1) = (4k+2)(n+1)(4k+4)
                       = (2k+1)(n+1)4(k+1)
                       = 8(2k+1(n+1)(k+1)
        => 8 | n(n+1)(n+2)

Fall 2: n     = 4k+4
        n+2   = 4k+6
  n(n+1)(4+1) = 4(k+1)(n+1)(4k+1)
              = 4(k+1)(n+1)2(2k+3)
              = 8(k+1)(n+1)(2k+3)

Wieso gibt es nur diese beiden Fälle ?

n ist gerade 
n ist entweder durch 4 teilbar oder nicht
n=4k+1,4k+2,4k+3,4k+4

Vollständige Induktion


=> Alle Dominosteine werden umgestoßen.

Prinzip


Übung


Feld mit 16 Spalten, 16 Zeilen, also 256 Feldern (bei dem ein Feld gesperrt ist) mit L-Teilen ausfüllen.
Feld: 255 Quadrate sind mit L auszufüllen.

// Viel Spaß beim Zeichnen! =D

Lösungsansätze


Idee 1: Erst kleinere Felder probieren mit L-Formen auszufüllen.
        Probiere 2x2 mit einem gelöschten Feld => klappt
        Probiere 4x4 mit einem gelöschten Feld => klappt
        Probiere 8x8 mit einem gelöschten Feld => klappt
        => Sollte also auch mit einem 16x16 Feld klappen

Allgemeine Aussage


Für jedes Quadrat mit der Seitenlänge 2^n und (2^n)²-1 Feldern lässt sich eine Paketierung mit L-förmigen Bausteinen finden.

(∀n ≥ 1)

Beweis


k = 1

Wie komme ich von dem Einen zum Nächsten?


Wollen wir die Aussage für k+1 zeigen und wir können vorraussetzen, dass die Aussage für k gilt. 

Sei Q so ein Quadrat, dann unterteilen wir dies in 4 Quadrate mit der Seitenlänge 2^k.
In einem dieser Quadrate fehlt genau 1 Feld. Dieses Quadrat können wir paketieren.
Wir legen einen L-Baustein so in die Mitte, dass wir aus jedem der anderen Quadrate genau 1 Feld überdecken. Auch für die kleineren Quadrate wissen wir nun, dass wir sie paketieren können. Wir können aso das gesamte Quadrat mit Seitenlänge 2^(k+1) paketieren.

Begriffsdefinitionen


Übung 2


10.10.2012

Satz


Sei A ein Arrangement von Geraden in der Ebene. Dann kann man sich ergebende Flächen so mit zwei Farben färben, dass keine zwei angrenzenden Flächen die selbe Farbe haben.

//Zeichnung von Geraden

Induktion über die Anzahl der Geraden in der Ebene. (Variable über die die Induktion laufen soll)

Induktionsanfang: Bei einer Geraden gibt es genau zwei Flächen. Es genügen also trivialer Weise zwei Farben.
Induktionsvoraussetzung: Für jedes Arrangement mit k Geraden gilt der obere Satz.
Induktionsbehauptung: Für jedes Arrangement mit (k+1) Geraden gilt der obere Satz.
Induktionsschritt: Sei A ein Geradenarrangement mit (k+1) Geraden und g eine dieser Geraden.


// BILD!!!!

Wir schauen uns das Arrangement B = A ohne g an.

//noch ein Bild

Nach IV können wir B färben wie im Satz oben. Wir fügen g wieder hinzu. Für jede Fläche auf einer Seite von g(siehe Bild) tauschen wir die Farben.

Wir müssen zeigen: keine zwei angrenzenden Flächen haben die selben Farben.

Fall 1: Das gemeinsame Geradenstück der beiden angrenzenden Flächen ist kein Teil von g. Dann hatten die beiden Flächenstücke vorher eine unterschiedliche Farbe. Beide sind auf derselben Seite von g und entweder beide behalten ihre Farbe oder beide tauschen die Farbe. In jedem Falle haben sie immernoch unterschiedliche Farben.

Fall 2: das gemeinsame Geradenstück ist Teil von g. Dann hatten vorher die beiden Flächenstücke die selbe Farbe und da wir von einer der beiden Flächen die Farbe geändert haben, sind beide Flächen unterschiedlich gefärbt.

Direkter Beweis



Jeder Fläche weisen wir die Anzahl t von Geraden zu, welche diese Fläche auf der rechten Seite haben. Wir färben jede Fläche weiß, wenn t ungerade ist und schwarz sonst. Zwei angrenzende Flächen haben eine unterschiedliche Farbe, weil nur für genau eine Gerade g gilt: Die eine Fläche ist links von g und die andere ist rechts von g.


Die Gauß-Summe:
 k
 ∑i    = 1
i=1
IV:
 k
 ∑i    = k*(k+1)/2
i=1

IB:
k+1
 ∑i    =(k+1)*(k+2)/2
i=1

IS:
k+1        k   
 ∑i     =  ∑i +(k+1) = k*(k+1)/2 + k+1    (*)
i=1       i=1

(*) = k*(k+1)+2(k+1)/2= (k+1)(k+2)/2

 1   + 2   +    3+...   +n
+n   +(n-1)+(n-2)+...   +1
(n+1)+(n+1)+(n+1)+...   +(n+1)

= n(n+1)
   n
=> ∑i  = n(n+1)/2
   i=1
   
Wir sind in einem Fernen Land in dem es nur 3 und 4 Peso-Scheine gibt.
Satz: Jede Summe ab 6 Peso kann ausgegeben werden.

IA: 
6=3+3
7=3+4
9=3+3+3

IS:
(6,7,8,...,k)~>(k+1)
(Für k > 8 brauchen wir nur den Schritt und machen ihn auch bloß) ???


Wir wollen nun (k+1) Peso ausgeben

Wir wissen, dass man (k-2) Peso ausgeben kann.
(k-2) Peso und ein 3 Peso-Schen sind zusammen (k+1) Peso.

Bei (k+1)=8 ist (k-2)=5
Hier würde der Schritt nicht funktionieren.

Geometrische Summe



Sei a > 0     n∈ N a/=1

a^0+a^1+a^2+a^3+a^4+ ... a^n = (a^(n+1) -1)/(a-1)

Beweis


IA k=0, 1=a^n = (a^1-1)/(a-1)= 1

Induktionsvoraussetzung: 

 k
 ∑ a^i  = (a^(k-1)-1)/(a-1)
i=0
 = (a^(k-1)-1)/(a-1)
Induktionsbehauptung:

 k
 ∑ a^i  =  (a^(k+2)-1)/(a-1)
i=0
 =  (a^(k+2)-1)/(a-1)
Induktionsschritt: 

 k          k
 ∑ a^i  =   ∑  a^i + a^(k+1) ***
i=0        i=0



*** = (a^(k+1)-1)/(a-1)+a^(k+1)
    = (a^(k+1)-1+(a-1)a^(k+1)/(a-1)
    = (a^(k+1)-1)/(a-1)
    

Übung 3


Lemma


Wenn in einer Gruppe von Tieren ein Tier ein Elefant ist, sind alle Tiere Elefanten.

Beweis per Induktion

: k=1

IS: k~>k+1
 M sei eine Gruppe von (k+1) Tieren.
 Ohne Beschränkung der Allgemeinheit (http://kamelopedia.mormo.org/index.php/O._B._d._A.) ist das erste Tier ein Elefant.
 M1 seien die ersten k Tiere. Aus der IV wir, dass M1 nur aus Eefanten besteht.
 M2 seien alle Tiere bis auf das erste, also auch k viele. Darunter sind auch Elefanten und wir wenden die IV an.
 
 k=5
 {T1,...,T6}=M
 {T1,...,T5}=M1
 {T2,...,T6}=M2
Der Schritt ist richtig von 2 nach 3, von 3 nach 4...usw. aber nicht von 1 nach 2.






Sonderzeichen: ∈, ∉, ≡, ∀, ∃, ∅, ⋂, ⋃, ⋀ , ⋁, ¬, →, ↔, ☇, √, ∤, |, ≥, ≤, ∑

Fehler im Übungszettel


Exponential- und Logarithmusfunktionen



5. 1/(log(10000)10)

Rechnen mit Kongruenzen


4. n³+2n ≡ 0 mod 3
5. n^5-n ≡ 0 mod 5

Literaturempfehlung