Aufgabe 13

Man formalisiere folgende Aussagen ( "für alle x": für alle Personen x; a: Agatha; b: Butler; c: Charles; U(x,y): x hat y umgebracht; R(x,y): x ist reicher als y; H(x,y): x haßt y)

(a) Agatha hasst sich selbst und Charles:

      H(a;a) UND H(a,c)

(b) Der Butler hasst alle Personen, die nicht reicher sind als Agatha:

     "für alle x gilt" ( ⌐ R(x;a) → H(b,x))
     
      ( Für alle Personen x gilt: Wenn x nicht reicher ist, als Agatha, dann hasst der Butler b die Person x)

(c) Jeden, den Agatha hasst, hasst auch der Butler:

     "für alle x gilt" (H(a,x)
H(b,x))
 
     (Wenn Agatha die Person x hasst, dann hasst auch der Butler die Person x. Das für alle x steht hier für "jeden"

(d) Niemand hasst sowohl Agatha als auch den Butler als auch Charles.

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

    (es gibt keine Person x, die Agatha und den Butler und Charles hasst)

 oder:

     "für alle x" (H(x,a) UND H(x,b) UND H(x,c) 
F )

     (die aussage: "Jede Person x hasst Agatha, den Butler und Charles" ist falsch)


Aufgabe 14:

Aus der Klausel Eq+: "für alle x" Eq(x,x) der Leibniz Gleichheit und dem Verträglichkeitslemma (VL)"für alle x,y"(Eq(x,y)
A(x) A(y)) mit jeweils einer geeigneten Formel beweise man informal:

(a) Eq(x,y)
Eq(y,x)                          (Symmetrie von Eq);
(b) Eq(x,y) 
Eq(y,z)  Eq(x,z)        (Transitivität von Eq).

Ferner gebe man in beiden Fällen die entsprechende Herleitung an.

zu (a):

(Man nimmt hier das Verträglichkeitslemma und setzt dann das geeignete ein)

  VL: .....                                                    x
 ------------------------------------------------------- "für alle" -
"Für alle y"(Eq(x,y)
Eq(x,x)Eq(y,x))  y
-------------------------------------------------------"für alle"-

  Eq(x,y)
Eq(x,x) Eq(y,x)                          (siehe unten)   
--------------------------------------- 
- [u:Eq(x,y)]       -----------
       Eq(x,x)
 Eq(y,x)                                            Eq(x,x) 
      ----------------------------------------------------------------------
-                                              Eq(y,x)
                             -------------------------
+ u
                              Eq(x,y) 
Eq(y,x)

(Anmerkung: das Eq(x,x) wird vorher wie folgt hergeleitet:

                                             Eq+:"für allex"Eq(x,x)
                                        ----------------------------------- "für alle"-
   ......                                              Eq(x,x)
--------------------------------------------------------------------
                           Eq(x,y)  Eq(y,x)   
                            ----------------------
                                        ....    

Zu (b):

(So wie ich das jetz versteh, hat er die Variablen des VL umgeändert, so dass für das VL entsteht:
"für alle y,z" (Eq(y,z)
A(y)  A(z));
Mit der Variable x ergibt sich dann folgendes:
"für alle x,y,z" (Eq(y,z) 
 Eq(x,y)  Eq(x,z))
bin mir aber nicht sicher, ob das so stimmt, wie ich mir das denk)


   VL: ...                           x,y,z
   ------------------------------------ "für alle"-
   Eq(y,z)
Eq(x,y)Eq(x,z)                      v:Eq(y,z)
   -----------------------------------
- v
         Eq(x,y) 
Eq(x,z)                             u:Eq(x,y)
       -------------------------- 
- u
                    Eq(x,z)


Aufgabe 15

Die Negation ⌐ A war definiert durch A 
F. Man gebe Herleitungen der folgenden Formeln an:

(a) A
⌐⌐A,
(b) ⌐⌐⌐A 
⌐A

zu (a):

    [v: 
A]           [u:A]
    -----------------------
-
                 F
           ----------
 +u
           
F
           (=
A)
         --------------  
 +v
         A 
A

zu (b)

                                [u1:
A]            [u2: A]
                              -------------------------------  
-
                                                   F
                                               ---------  
+u1
    (=
A F)                           A F
    u: 
A                             (= A)
 ----------------------------------------------- 
+ u2
                          F
                        ------
+u2
                       A
  F
                        (=
A)
                  -----------------
                 
 A     A
   

Aufgabe 16:

Man beweise die Kürzungsregel für +, also n+k=m+k→n=m

Den Beweis (durch Induktion über k) führe man

(a) informal durch:

Induktion über k. Basis: Zu zeigen:

     n+0 = m+0   → (Implikation) n=m
     =n        =m

Schritt: k → k+1

Induktionshypothese (IH): n+k=m+k → n=m

Zu zeigen:

     n + k+1 = m + k+1
     S(n+k)  =  S(m+k)
                   ↑
       (Gleichheit über N)  
       n + k   =  m + k           (Rekursionsformel:Das ist die IH)

b) durch Angabe einer Herleitung:

Induktionshypothese: n+k=m+k
→ n=m = A(k)

Axiom:
Ind:K,A: "für alle n,k,m"(A(0)
             "für alle k"(A(k`)
→A(k`+1))→A(k`)     n m k`
 ------------------------------------------------------------------- "für alle"-

 A(0)
→"für alle k"(A(k`)→A(k`+1))→A(k`)            A(0)
------------------------------------------------------------------------
→-
    "für alle k"(A(k`)→A(k`+1))→A(k`)                 ° siehe unten
 --------------------------------------------------------------------------------
                               A(k`)
  ----------------------------------------------------    "für alle" + (3mal)
  "für allen" "für alle m" "für alle k`" A(k`)

                                                          =n+k`=m+k`
→n=m


 °: "für alle k" (A(k`)
→A(k`+1))


  M0:         u:   n+0   =   m+0
   Def +:             n     =     m
                 --------------------------
→+u
                        n=m
→ n=m
                               A(0)

M(k+1):    Induktionshypothese: A(k)
                  n+k - m+k
→ n=m
        ---------------------------------------------------------
→ + IH
             (n+k=m+k
→n=m)→(n+k=m+k→n=m)
                                                               wegen Def+ und Def=
                                                 n+k+1=n+k+1