Aufgabe 21

(a) Unter alleiniger Verwendung der Teilbarkeitsrelation formalisiere man die Eigenschaft einer natürlichen Zahl d, der  größte gemeinsame Teiler zweier natürlicher Zahlen n,m zu sein

RggT(d,n,m) := d|n UND d|m UND
                                                      "für alle q"(q|n→q|m→q|d)

(b) Entsprechend formalisiere man die Eigenschaft einer natürlichen Zahl k, das kleiste gemeinsame Vielfache zweier natürlicher Zahlen n,m zu sein

Rkgv(k,n,m):= n/k UND m/k UND "für alle q"(n|q→m|q→k|q)

(c) Man beweise: Zu beliebigen natürlichen Zahlen n,m gibt es höchstens ein kleinstes gemeinsames Vielfaches k

Annahme:
Rkgv(k1,n,m) und Rkgv(k2,n,m);

Zu zeigen: k1=k2

n|k1 UND m|k1 UND "für alle q"(n|q m|q k1|
q)

n|k2 UND m|k2 UND "für alle q"(n|q m|q k2|q)

Genügt zu zeigen (nach Lemma (g)):

k1
|k2 und k2|k1

Aus (2): n
|k2 und m|k2
Aus (1): (mit k2 für q): n
|k2  m|k2 → k1| k2
Aus (2): n
|k1 m|k1 k2|k1


Aufgabe 22

Man gebe Herleitungen der folgenden Formeln an:

(a) ⌐"es gibt x" A  → "für alle x"
A
(b)  "für alle x"
⌐A  ⌐"es gibt x" A

Hinweis: Man verwende die Einführungs- bzw. Beseitigungsregel

                                                                          [u:A]

              | M                             | M                       | N             
  r         A(r)                       "es gibt x"A              B
----------------- "es gibt"+  ------------------------------ "es gibt"x,u-
"es gibtx"A(x)                                    B                  (mitVariablen-
                                                                                bedingungen)

Variablenbedingung: Die Herleitung N darf keine offenen Annahmen außer u:A enthalten, in denen x frei vorkommt, und auch in B darf x nicht frei vorkommen.

N hängt nur über die Annahme u:A von x ab!

zu (a):
                                                x [v:A]
                                       ----------------------- "es gibt" +
        u: ⌐"es gibt x"A          "es gibt x"A
        ------------------------------------------------
                                     F
                                   ---- → v+
                                    ⌐A
                          --------------------- "für alle x"+ (Variablenbed.)
                            "für alle x" ⌐A
         --------------------------------------------------
                ⌐"es gibt x"A → "für alle x" ⌐A

(Variablenbedingung: in v: A kam x frei vor, da x element FV( "es gibt x"A) schon unabhängig)


Zu (b):

                    [u: "für alle x" 
⌐A]            x
                   ------------------------------------  "für alle" -
                                    ⌐A                                          [w:A]
            ------------------------------------------------------------------ →-
                  [v:"es gibt x"A                       F
                 ----------------------------------------- "es gibt" - x,w
                                           F
                               ----------------------  →+ v
                                ⌐ "es gibt x" A
                   ----------------------------------------- 
→+ u
                    "für alle x" 
A "es gibt x"A


Aufgabe 23

Die Potenzfunktion hatten wir definiert durch die Berechnungsregeln n°:=1, nhochSm:=(nhochm)*n.
Man beweise:

(a) 1hochm = 1,
(b) (n*m)hochk = nhochk*mhochk,
(c) (nhochm)hochk = nhoch(m*k).

zu (a):

Induktion über m

Schritt m → m+1

      1hochSm = 1
      1hochm*1          (nach Induktionshypothese)
              1

zu (b):

Induktion über k, Basis

Schritt k → Sk

Zu zeigen:

          (n*m)hochSk                =       nhochSk*mhochSk
       ( n*m)hochk * n * m                nhochk * n * mhochk * m
IH: nhochk* mhochk * n * m   

(c) Hilfsbehauptung nhoch(m+k) = nhochm*nhochk

Induktion über k; Basis

Schritt k → Sk

Zu zeigen:   

                       nhoch(m+Sk)       =      nhochm * nhochSk  
(Def +)           nhochS(m+k)               nhochm*nhochk*n          
(Def Potenz) nhoch(m+k)*n      
       (IH)        nhochm*nhochk*n


Damit beweisen wir (c), durch Induktion (k) Basis,

Schritt k → Sk

Zu zeigen:

                             (nhochm)hochSk     =      nhoch(m*Sk)
(DefPotenz)(nhochm)hochk*nhochm    nhoch(m*k)+m (Def*)
         (IH)        nhoch(m*k)*nhochm          nhoch(m*k)*nhochm
                                                                                      (Hilfsbe
                                                                                      hauptung)
                                                                   nhoch(m*k)*nhochm



Aufgabe 24:

Sei f eine Variable vom Typ N
→ N

(a) Man definiere durch ANgabe der Berechnungsregeln Funktionen ∑ und ∏ vom Typ N
(N→N)→N mit

        ∑n*f     =     ∑ f*i             ∏n*f    =     ∏ f*i
                            i<n                

Berechnungsregeln:

  ∑ 0f:=0, ∑(Sn)f:= ∑ nf + fn
  
∏ of:=1. ∏ (Sn)f:= ∏ nf * fn

(b) Sei h: N→N definiert durch hn:=n; Man beweise:

  2*(∑nh) = n*(n+1)

Zu zeigen:   2*∑(Sn)h = n(n+1), d.h.
                      2 * ∑  i    = n(n+1)
                          i<Sn

Induktion über n; Basis;

Zu zeigen: 2 * ∑ i = 0*(0+1)
                        i<1         =0
                         =0

Schritt: Induktionshypothese:   2 * ∑ i = n(n+1)
                                                       i<n+1

Zu zeigen:

             2 *
∑ i    =   (n+1)(n+2)
                i<n+2

        2*(
∑i+n+1)  =   (n+1)(n+2)
            i<n+1

IH: n(n+1)+2n+2  =   n² +3n +2
     = n² +3n +2