Aufgabe 9

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 hasst y).

(a) Agatha, der Butler oder Charles haben Agatha umgebracht:

  U(a,a) ODER U(b,a) ODER (c,a)

(b) Man bringt nur solche Personen um, die man hasst und die man an Reichtum nicht übertrifft.

   "für alle x,y" (U(x,y) → H (x,y) UND ⌐R(x,y))

(Man = "für alle" gilt: Wenn die Person x die Person y umbringt, dann hasst x die Person y und ist nicht reicher als y)

c) Charles mag (:= hasst nicht) alle Personen, die Agatha hasst:

   "für alle x" (H(a,x)
⌐H(c,x))

    (Alle Personen x, die Agatha hasst, hasst Charles nicht)


Aufgabe 10:

Man beweise die Isomorphie der Strukturen und , wobei m1:= {n I "es gibt m" n=2hochm}, M2 :={n I "es gibt m" n=3*m}.

+,* sind die üblichen Funktionen auf N eingeschränkt auf M1 bzw M2

          = Trägermenge
und

heißen isomorph, wenn es eine bijektive Abbildung g von auf gibt mit

"für alle x1,...,xn element M" (fi (x1,...,xn) = fi`(g(x),...,g(xn))

"für alle xq,...,xn element M" (Rj(x1,...,xn) ↔ Rj`(g(x1),...g(xn))

1. Bikektivität angeben:

Zu zeigen: es gibt g bijektive Abbildung von M1 auf M2, so dass "für alle R1,R2 element M1" (g(n1*n2)=g(n1)+g(n2);

Setze g(2hochm) = 3*m

g ist eine bijektive Abbildung von M1 auf M2.

  g(2hochm1*2hochm2)  = g(2hochm1) + g(2hochm2)
       =2hoch(m1+m2)                =3*m1           =3*m2
  = 3*(m1+m2)

Daraus folgt der Isomorphismus!


Aufgabe 11:

Man gebe die Herleitungen der folgenden Formeln an:

(a) A → B → A: (u, ist die Annahme)

      [u: A]
     --------- →+ v  (Pfeileinführung)
     B → A
   ------------- →+ u
   A → B → A

(b) (A→B→C)→B→A→C:

   u: A→B→C                 [v:A]
  -------------------------------------- →- (Pfeilbeseitigung)
                       B→C
                      ---------  → - [w:B]
                          C
                   -------------- →+ v:A
                        A→C
                  --------------- →+ w
                    B→A→C


c) "für alle x" "für alle y"A→"für alle y" "für alle x"A

u:  ["für alle x" "für alle y"A]          x
----------------------------------------------- "für alle" -    "für alle y"A     y
    ---------------------- "für alle y" -
                A
             -------  "für alle" + x    (Variablenbedingung erfüllt, da
          "für alle x" A                           x nicht element FV)
       -------------------- "für alle" +y 
  "für alle y" "für alle x" A
  --------------------------------- →+ u
"für alle x" "für alle y"A → "für alle y" "für alle x"A


d) "für alle x" "für alle y"A(x,y) → "für alle x"A(x,x)

[u: "für alle x" "für alle y"A(x,y)]       x
  ---------------------------------------------- "für alle" -
           
"für alle y"A(x,y)       x
         --------------------------------- "für alle" -
                           A(x,x)
                     --------------------   "für alle" +
                     "für alle x"A(x,x)
  -------------------------------------------------------------- 
→ + u
  "für alle x" "für alle y"A(x,y) → "für alle x"A(x,x)