Aufgabe 17

Man leite aus den Annahmen ... die Formeln (1)  ⌐ U(c,a) und (2)  ⌐ U (b,a) her:

Zu (1): Annahme: u: U(c,a) Ziel: F 

( weil  U(c,a) → F = ⌐ U(c,a) )

Zuerst schaut man, mit welchen Annahmen man arbeiten muss. Hier wären das

(d): H (a,a)

(c): ⌐ H (c,a)

(b) ⌐ U (c,a)

erstens:

     (d): H(a,a) UND H (c,a)

          ---------------------------  ( das rechte UND wird beseitigt)

                    H(a,a)                                                     

 zweitens: 

(c) ...

---------- "für alle a" wird beseitigt und für x a eingesetzt

H(a,a) →  ⌐ H (c,a)

---------------------------- H(a,a) beseitigt (da vorher bewiesen)

           ⌐ H (c,a) 

( = H(c,a) → F )

drittens:

(b) ...

---------- für alle wird beseitigt, für x wird c eingesetzt, für y a

U(c,a) → H(c,a) UND ⌐ R(c,a)

 ----------------------------------------- u: U(c,a)

   H(c,a) UND R (c,a)

  ---------------------------- UND-Beseitigung rechts

       H (c,a)                       H(c,a) → F (aus Zweitens)

      ----------------------------------------------------- Pfeilbeseitigung

                                    F

                         ------------------------- Pfeil dazu: + u

                                  ⌐ U (c,a)

  

Anmerkung: man darf das UND erst dann beseitigen, wenn sonst kein Pfeil etc mehr da steht

zu (2): ⌐ U (b,a)

Annahme: u:  U (b,a)   Ziel: F

Aus (f), (d): H(b,a) , H (b,c)

Aus (g):  ⌐ H(b,b)

Aus (e): R (b,a)

Aus (b): ⌐ U(b,a)

            Ma                 Mb                  Mc

          H(b,a)             H(b,b)            H(b,c)

      -------------------------------------------------- + UND (2mal)    

            H(b,a) UND H (b,b) UND H(b,c)

      --------------------------------------------------- + "es gibt"

  (g): "es gibt x ) (H(x,a) UND H(x,b) UND H(x,c))

  ------------------------------------------------------------------  → -

                                         F

 

Zu finden: Ma, Mb, Mc, die die Annahme u: U(b,a) enthalten dürfen

Mb :

erstens:

     (b)...

    ------------------ "für alle"(2mal), x durch b ersetzt,y durch a

 U(b,a) →  H(b,a) UND  ⌐ R(b,a)  

 ---------------------------------------------      → -

         H(b,a) UND ⌐R(b,a)     

     --------------------------------------  UND - (links)

                 ⌐ R(b,a)

 zweitens:

(e) .....

------------ "für alle" - , x wird durch b ersetzt

⌐ R(b,a) →  H(b,b)                               ⌐ R(b,a) (aus erstens)

--------------------------------------------------------------------------------

                                     H(b,b)

Ma: (f) ...                                                     (d) .....

     ---------- "für alle"-,x durch a ersetzt     ----------- UND- links

  H(a,a) → H(b,a)                                        H(a,a)

---------------------------------------------------------------------

                                  H (b,a)


Mc funktioniert genauso!

Bemerkung: Aus (a) folgt: U(a,a)


Aufgabe 18:

Man gebe die Herleitungen der folgenden Formeln an:

(a) (A B) B A

(dabei muss man bedenken, dass man am unteren Ende des Beweisbaumes anfängt. Am besten ist es, wenn man sich zuerst mal alle Annahmen aufschreibt und die Ziele, die man dabei braucht. Mit den Annahmen fängt man anscheinend am besten ganz vorne also links an)

Annahme: u: A B  Zu Zeigen: B A
Annahme: v: B       Zu Zeigen: A (ist gleich wie AF)
Annahme: w: A        Zu Zeigen: F

         u: A B        w: A
        --------------------------  - w
     v: B                   B
  --------------------------   -
                  F

(b) (B B ) ( B A ) A B

Annahme: u: B B
Annahme: v: B A
Annahme: w: A               Zu Zeigen: B

(wieder fängt man also unten mit B an und schaut dann, welche Annahmen von oben man brauchen kann)

       v: B A                  u1: B
       ----------------------------------- - u1
                    A          w: A
                    ----------------  -
                             F
                   --------------- + u1: B
  u: B B           B
  -------------------------------
                        B

Aufgabe 19:

Die Multiplikation für natürliche Zahlen war definiert durch n*0 := 0, n*Sm:= (n*m) + n

Man beweise durch Induktion

(a) 0*n = 0
(b) Sn*m = (n*m) + m

zu (a)

Induktion über n:

Basis: Zu zeigen: 0*0=0
Nach Defitionion ist 0*0=0!

Schritt: n Sn

Induktionshypothese:                               0*n = 0    Zu zeigen:
(nach Defitintion von Multiplikation)   0 * Sn = 0
                                                           0 * n + 0 = 0
(nach Definition von Addition)               0 * n = 0


zu (b): Induktion nach m:

Basis: Zu zeigen: Sn*0 = n*0 + 0
                                 0     =   n*0
                                 0     =     0

Schritt:
Induktionshypothese: "für alle n" (Sn*m = n*m + m)
  
Zu Zeigen:  "für alle n" ( Sn*Sm        =          n*Sm + Sm)
                                    Sn*m + Sn                  S(n*Sm + m)
                                   S(Sn*m + n)              S((n*m + n) + m)

                                          Sn*m + n    =   (n*m + n) + m)

Anmerkung: Es war die Gleichheit := N N B definiert durch (Sn=Sm) := (n=m)   

Aus der Induktionshypothese: Sn*m + n = (n*m + m) + n

Mit Assoziativität und der Kommunitativität der Addition folgt die Behauptung.