Porschen mitschriften digital PDF

Preview

Summary

1 Aussagenlogik Basis: Aussagenlogik [AL] Definition (Aussage, Wahrheitswert [WW]) Aussage ist Satz, einer künstlichen oder menschlichen Sprache, der entweder Wahr oder Falsch ist. Wahre Aussage wird Wahrheitswert wahr (1) zugeordnet. Falsche Aussage wird Wahrheitswert falsch (0) zugeordnet. Beispie...

Description

WI - B05 - Mathematik für Wirtschaftsinformatiker

1

Aussagenlogik • Basis: Aussagenlogik [AL] • Definition (Aussage, Wahrheitswert [WW]) • Aussage ist Satz, einer künstlichen oder menschlichen Sprache, der entweder Wahr oder Falsch ist. • Wahre Aussage wird Wahrheitswert wahr (1) zugeordnet. • Falsche Aussage wird Wahrheitswert falsch (0) zugeordnet.

Beispiele • “In Berlin steht der Kölner Dom.“ (0) • “Durch Köln fließt der Rhein.“ (1) • “47 > 11“ (1) • “Jede gerade Zahl > 2, ist Summe zweier Primzahlen.“ (?) (beachte zugehöriger WW ist garantiert, aber unbekannt Aussage liegt vor.) • “Dieser Satz ist falsch!“ weder (0) noch (1) also keine Satz (nicht Aussage)

1.1

Aussageform

• ist Satz, der Platzhalter (=Variable) enthält. • wird zu einer Aussage falls für jede vorkommende Variable ein (passender) Wert eingesetzt wird. Wahrheitswert der sich so ergebenden Aussage hängt ab vom eingesetzten Werten. Beispiele • “Der Gärtner ist der Mörder.“ • “y ist Primzahl.“ • “x > y“

1.2

Aussage-Verknüpfungen

1.2.1 NEGATION ( ¬ ): • zu Aussage A: ¬A “nicht A“ • ¬ A kann als Aussageform betrachtet werden. Wobei A Variable für Wahrheitswert ist, d.h. A kann 0 oder 1 als Wert annehmen. • AL-Variable: G Boole: Boolsche Variable A 1 0

¬A 0 1

13.10.2010 - 20.10.2010

www.studiWI.de

Seite 1/ 6

WI - B05 - Mathematik für Wirtschaftsinformatiker 1.2.2 KONJUNKTION ( ∧ ): • zu AL-Variable A, B: A ∧ B “A und B“ A 1 1 0 0

B 1 0 1 0

A∧B 1 0 0 0

1.2.3 DISJUNKTION ( ∨ ): • AL-Variable A, B:A ∨ B “A oder B“ A 1 1 0 0

B 1 0 1 0

A∨B 1 1 1 0

1.2.4 IMPLIKATION ( ⇒ ): • AL-Variable A, B: A ⇒ B “aus A folgt B“ synonym “A impliziert B“ – A heißt Prämisse (= Voraussetzung) – B heißt Folgerung A 1 1 0 0

B 1 0 1 0

A⇒B 1 0 1 1

1.2.5 ÄQUIVALENT ( ⇔ ): • AL-Variable A, B: A ⇔ B • “A ist äquivalent zu B“ synonym “A gleichwertig mit B“ synonym “A genau dann, wenn(gdw.) B“ A 1 1 0 0

B 1 0 1 0

A⇔B 1 0 0 1

Beispiel • A: “Köln liegt am Rhein“ • B: “47 < 11“ “A ⇒ B“ : (0) “B ⇒ A“ : (1) Vorsicht: Korrekte Implikation heißt nicht korrekte Prämisse A: 1 = −1 : (0) B: 12 = (−1)2 : (1) (A ∧ (A ⇒ B)) ⇒ B “modus ponens“(setzende Schlußregel) 13.10.2010 - 20.10.2010

www.studiWI.de

Seite 2/ 6

WI - B05 - Mathematik für Wirtschaftsinformatiker

1.3

AL Formel

• Jede AL-Variable ist eine AL-Formel heißen atomare Formeln • Werden AL-Formeln gemäß AL-Verknüpfung (1.2) zusammengesetzt ergeben sich wiederum AL-Formeln, solange sich endlich große Objekte ergeben. • nichts anderes führt zu einer AL-Formel

1.4

AL-Formel ist Aussageform

die dadurch zur Aussage wird, dass jeder vorkommenden AL-Variablen ein Wahrheitswert zugewiesen wird. Der Wahrheitswert der sich so ergebenden Aussage ist eindeutig durch AL-Verknüpfung festgelegt. 1.4.1 Beispiel: Modellierung • Schließung der Tür zu Bank-Schließfächern. • Soll nur öffnen, falls elektronischen Schlüssel zweier verschiedener Personen verwendet werden. • AL-Variable P1 : 0 Strom fließt nicht; 1 Strom fließt P2 : 0 Strom fließt nicht; 1 Strom fließt Schließformel: P1 ∧ P2

1.5

Tautologie

AL-Formel heißt Tautologie, falls jede Zuweisung von Wahrheitswert zu in AL-Formeln vorkommenden AL-Variablen eine wahre Aussage liefert.

1.6

Tautologien

A, B, C AL-Variablen oder AL-Formeln: 1.6.1 Satz vom geschlossenen Dritten A ∨ ¬A = 1 A ∧ ¬A = 0 1.6.2 Satz vom Widerspruch ¬(A ∧ ¬A) 1.6.3 doppelte Verneinung ("Nicht-Nicht-Raucher") ¬(¬A) ⇔ A 1.6.4 Kommutativität von ∧, ∨ (A ∧ B) ⇔ (B ∧ A) (A ∨ B) ⇔ (B ∨ A)

13.10.2010 - 20.10.2010

www.studiWI.de

Seite 3/ 6

WI - B05 - Mathematik für Wirtschaftsinformatiker 1.6.5 Assoziativität A ∧ (B ∧ C) ⇔ (A ∧ B) ∧ C ⇔ A ∧ B ∧ C A ∨ (B ∨ C) ⇔ (A ∨ B) ∨ C ⇔ A ∨ B ∨ C 1.6.6 Distributivität A ∧ (B ∨ C ) ⇔ (A ∧ B) ∨ (A ∧ C ) A ∨ (B ∧ C ) ⇔ (A ∨ B) ∧ (A ∨ C ) 1.6.7 de Morgan Regeln (A = ¬F ) ¬(A ∧ B) ⇔ (¬A ∨ ¬B) ¬(A ∨ B) ⇔ (¬A ∧ ¬B) 1.6.8 Kontraposition (A ⇒ B) ⇔ (¬B ⇒ ¬A) “Wenn es regnet, dann wird Straße nass“ “Wenn Straße trocken, dann regnet es nicht“ A B ¬A ¬B A ⇒ B ¬B ⇒ ¬A F 1 1 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1.6.9 modus ponsens (A ∧ (A ⇒ B)) ⇒ B 1.6.10 Idem Potenz (A ∧ A) ⇔ A (A ∨ A) ⇔ A 1.6.11 Tautologien begründen Beweistechniken F = (¬A ⇒ B ) ⇔ (A ∨ B ) F = (A ⇒ B ) ⇔ (¬A ∨ B ) A B ¬A A ∨ B ¬A ⇒ B 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 0

13.10.2010 - 20.10.2010

F 1 1 1 1

www.studiWI.de

Seite 4/ 6

WI - B05 - Mathematik für Wirtschaftsinformatiker nützlich um AL Formeln durch äquivalente Umformungen zu vereinfachen F = (¬A ⇒ B ) ∧ ((A ∧ B ) ⇒ ¬C) ∧ ((C ∨ ¬A) ⇒ ¬B ) F = (A ∨ B) ∧ (¬(¬(A ∧ B) ⇒ ¬C)) ∧ ¬(C ∨ ¬A)V ¬B F = (A ∨ B) ∧ (¬(A ∧ B) ∨ ¬C) ∧ ¬(C ∨ ¬A) ∨ ¬B F = (A ∨ B) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ ((¬C ∧ A) ∨ ¬B) F = (A ∨ B ) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬C ∨ B ) ∧ (A ∨ ¬B ) G = ¬A E = ¬B ∧ ¬C (G ∨ E) ∧ E ⇔ E F = (A ∨ B) ∧ (B ∨ ¬C) ∧ (A ∨ ¬B) F = (A ∨ B) ∧ (A ∨ ¬B) ∧ (¬B ∨ ¬C) F = A ∨ (B ∧ ¬B) ∧ (¬B ∨ ¬C) F = A ∨ (¬B ∨ ¬C) Mit solchen Methoden kann man jede AL Formel in spezielle Gestalt "pressen"(normierte Gestalt)

1.7

KNF, DNF

AL Formel F heißt im : 1.7.1 konjunktiver Normalform(KNF) genau dann, wenn: F = K1 ∨ K2 ∧ K3 ... ∧Kn wobei Ki = (L1 ∨ L2 ∨ ... ∨Lr ) jedes L1 ist entweder AL Variable oder Negative AL Variable n, r; ganze Zahlen Ki heißt Klausel (A1 ∨ A2 ∨ ¬A3 ) ∧ (A1 ∨ ¬A2 ) ∧ ¬A3 | {z } | {z } |{z} K1 ; K2 ; K3 ; L1 = A1 AL Variable A1 , A2 , A3 ,: AL Variable 1.7.2 disjunktiver Normalform(DNF) genau dann, wenn: F = T1 ∧ T2 ∧ T3 ... ∧Tm wobei Ti = (L1 ∨ L2 ∨ ... ∨Ls ) jedes L1 ist entweder AL Variable oder Negative AL Variable m, s; ganze Zahlen 1≤i≤m (A1 ∧ A2 ∧ ¬A3 ) ∨ (A1 ∧ ¬A2 ) ∨ ¬A3 | {z } | {z } |{z} T1 ; T2 ; T3 ;

13.10.2010 - 20.10.2010

www.studiWI.de

Seite 5/ 6

WI - B05 - Mathematik für Wirtschaftsinformatiker

1.8

Normalformensatz

• Jede AL Formel F kann äquivalent umgeformt werden – in eine KNF Formel F1 : F ⇔ F1 – in eine DNF Formel F2 : F ⇔ F2 • Erfüllungsproblem (Komplexitätstheorie) • Eingabe: KNF : F • Ausgabe: ja(F erfüllbar) / nein(F1 ¬ erfüllbar)

1.9

Reales Anwendungsbeispiel

Korrektheits- / Konsistenzprüfungen bei Autobestellungen • AL : XF i Feature 1 bestellt : 1 • AL : XF i Feature 1 nicht bestellt : 0 AL Formel: verknüpfte Features entsprechenden Markterfordernissen bzw. technischen Erfordernissen. • z.B. F = F k ∧ F m ∧ F c ∧ F b ∧ F e ∧ F s • K: Klima; M: Motor; C: Karosserie; B: Bereifung; ... • z.B. Klimatisierungs-Teilformel – xKA : Klimaautomatik – xRM : Klima-Manuell – xRF : Innenraumfassung – xM K : Motor 40PS • FK : (xKA ∨ xK M ) ∧ ¬(xKA ∧ xK M ) ∧ (XM K ⇒ (¬xKA ∧ ¬xK M )) ∧ (xKA ⇒ xRF ) ...

13.10.2010 - 20.10.2010

www.studiWI.de

Seite 6/ 6

WI - B05 - Mathematik für Wirtschaftsinformatiker

1

Mengenlehre

Darstellungsgrundlage der gesamten Mathematik Mengen wichtig in vielen Algorithmen werden durch geeignete Darstellungen modelliert Menge / Relation extrem relevant für DBMS aus heutiger Sicht naive Definition

1.1

Vater der Mengenlehre (G.Cantor, 1845-1918)

Menge M ist Zusammenfassung von bestimmten, wohl unterschiedenen Objekten aus unserer Anschauung oder unseres Denkens zu einem Ganzen. Die zusammengefassten Objekte heißen Elemente der Menge M Schreibweise: “x ∈ M “: x ist Element von M; M = {...}

1.2

Beispiele

1.2.1 Objekte: Buchstaben im Wort (String) Hochschule M1 = {H, O, C, H, S, C, H, U, L, E}

M = {H, O, C, S, U, L, E}

• Mehrfachvorkommen werden ignoriert • Reihenfolge der Elementaufzählung irrelevant M = {O, S, L, E, U, H, C} 1.2.2 M2 = {A, B, C, D, ...Z} Objekt Buschstaben des Alphabets 1.2.3 M3 = {1, 2, 3, ...} “unendliche“ Menge, Menge der natürlichen Zahlen 1.2.4 M4 = {33, 34, 35, ...49} = {x : X ∈ N ∧ x ≥ 33 ∧ x ≤ 49} 1.2.5 wichtige Zahlenmengen • N := {1, 2, 3, ...} natürliche Zahlen • N0 := {0, 1, 2, 3, ...} natürliche Zahlen mit 0 • Z := {..., −3, −2, −1, 0, 1, 2, 3, ...} ganze zahlen • Q := {x : x =

z,z n

∈ Z, n ∈ N} rationale Zahlen (Bruchzahlen)

• R := {x : −∞ < x < ∞} reelle Zahlen 1.2.6 ∅ leere Menge { } einzige Menge, die 0 Elemente enthält

20.10.2010 - 28.10.2010

www.studiWI.de

Seite 1/ 8

WI - B05 - Mathematik für Wirtschaftsinformatiker 1.2.7 Mengen können als Objekte selbst Mengenenthalten • M7 := {1, {1}, {{1}, {2, 3}}} Menge, die die Menge 1 enthält • M8 := {x : x ist Menge der Zahlen einer Lottoziehung } • M8 = {{1, 2, 4, 8, 14, 49}, {13, 17, 5, 21}} Vorsicht! Mall := {x : x ist Menge } → Ausweg : AxiomatischeMengenlehre

1.3

Teilmenge, Obermenge

1.3.1 M heißt Teilmenge von Menge L : M ≤ L, gdw. x ∈ M ⇔ x ∈ L gleichbedeutend mit: x ∈ M ⇒ x ∈ L ∧ x ∈ L ⇒ x ∈ M 1.3.2 Wenn M ≤ L gibt, dann heißt L Obermenge von M 1.3.3 Mengen M und L heißen gleich, gdw. M ≤ L ∧ L ≤ M ⇔ L = M gleichbedeutend mit: x ∈ M ⇒ x ∈ L ∧ x ∈ L ⇒ x ∈ M gleichbedeutend mit: x ∈ M ⇔ x ∈ L

1.4

Potenzmenge

Die Potenzmenge P(M) einer Menge M, ist die Menge sämtlicher Teilmengen von M. P (M ) := {x : x ≤ M }

1.5

Beispiele

1.5.1 M := ∅, P (∅) = {∅} 1.5.2 M = {0, 1} P (M ) = {{0}, {1}, {0, 1}, ∅} {0} ≤ M 1.5.3 M = {r, g, b} P (M ) = {∅, {r}, {g}, {b}, {r, g }, {r, b}, {g, b}, {r, g, b}}

1.6

Hat M n Elemente

(M = {e1 , e2 , ..., en }, n ∈ |N ) dann P (M ) 2n viele Elemente. Beweis: 0 0 0 ... 0 ←→∅ 1 0 0 ... 0 ←→{ e1 } 0 1 0 ... 0 ←→{ e2 } ... 2 ∗ 2 ∗ 2...2 = 2n p.e.d. = Beweis ist abgeschlossen = 

20.10.2010 - 28.10.2010

www.studiWI.de

Seite 2/ 8

WI - B05 - Mathematik für Wirtschaftsinformatiker

1.7

Operationen auf Mengen

1.7.1 Durchschnitt (= Schnittmenge) von Mengen M, L: M ∩ L := {x : x ∈ M ∧ x ∈ L}

∩ korrespondiert zu ∧ 1.7.2 Vereinigung von M, L: M ∪ L := {}x : x ∈ M ∨ x ∈ L}

M ∩L≤M ∪L 1.7.3 Differenzmenge M \ L := {x : x ∈ M ∧ ¬(x ∈ L)}

M \ L(= M − L) 1.7.4 Symmetrische Differenz M △ L := {x : (x ∈ M ∨ x ∈ L) ∧ (x 6∈ M ∩ L)}

△ korrespondiert zu XOR

1.8

wichtige Rechenregeln

sind K,L,M Mengen dann gilt 1.8.1 Kommutativität • M ∩L=L∩M • M ∪L=L∪M 1.8.2 Assoziativität • K ∩ (M ∩ L) = (K ∩ M ) ∩ L • K ∪ (M ∪ L) = (K ∪ M ) ∪ L 1.8.3 Distributivität • M ∩ (L ∩ K) = (M ∩ L) ∩ (M ∩ K) • M ∪ (L ∪ K) = (M ∪ L) ∪ (M ∪ K)

20.10.2010 - 28.10.2010

www.studiWI.de

Seite 3/ 8

WI - B05 - Mathematik für Wirtschaftsinformatiker

1.9

de Morgan

• L ≤ M, K ≤ M • M \ (L ∩ K) = (M \ L) ∪ (M \ K) • M \ (L ∪ K) = (M \ L) ∩ (M \ K ) | {z } | {z } A↑ B↑ Beweis: A≤B B≤A (x ∈ M ) ∧ ¬(x ∈ L ∨ x ∈ K) ⇔ (x ∈ M ) ∧ (x 6∈ L ∧ x 6∈ K) ⇔ (x ∈ M ∧ x 6∈ L) ∧ (x ∈ M ∧ x 6∈ K) ⇔ (x ∈ M \ L) ∧ (x ∈ M \ K) ⇔ x ∈ [(M \ L) ∩ (M \ K)] ⇔x∈B

1.10

Kartesisches Produkt

Seien L, M Mengen, L = 6 ∅ M 6= ∅ Dann heißt LxM = {(x1 , x2 ) : (x1 ∈ L ∧ x2 ∈ M )} Kartesisches Produkt von L und M (= Menge der geordneten Paare der Elemente in L, M) Beispiel L = {x1 , x2 }, M = {x, y} L ∗ M = {(1, x), (1, y ), (2, x), (2, y ), (3, x), (3, y )} |L ∗ M | = |L| ∗ |M | L ∗ M ∗ M ∋ (1, x, x) M ∗ L = {(x, ), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3)} L=M =N N ∗ N = N2 R5 = R ∗ R ∗ R ∗ R ∗ R Beispiel L ∗ M ∗ M = |L ∗ M 2 | = |L| ∗ |M | ∗ |M | = |L| ∗ |M |2 = {(1, x, x), (1, x, y), (1, y, x), (2, x, x), (2, x, y), (2, y, x), (3, x, x), (3, x, y), (3, y, x)}

1.11

Quantor

• ∀ “für alle“ (Allquantor) • ∃ “es existiert“ (Existenzquantor) A(x) (x ∈ M ) ∀x : A(x) für alle x ∈ M gilt A(x) ∃x : A(x) es gibt (mindestens) 1 x, für das A(x) gilt.

20.10.2010 - 28.10.2010

www.studiWI.de

Seite 4/ 8

WI - B05 - Mathematik für Wirtschaftsinformatiker 1.11.1 für alle n ∈ N gilt Pn n(n+1) i=1 := 2 ∀n : A(n), (n ∈ N) A(n) :

Pn

i=1

:=

n(n+1) 2

Pn

a := a1 + a2 + a3 + ... +an

P26

a := a3 + a4 + a5 + ... +a26

i=1

i=3

1.11.2 es gibt ein n ∈ N, für das gilt n ∈ Q kurz: ∃n : n < (n ∈ N)

Q

1.11.3 es gibt kein n ∈ N, welches für alle m ∈

Q

m < n erfüllt.

kurz: ¬∃n : ∀m : m < n(m, n ∈ N)

1.12

Beweisprinzipien

• Beweise: Tagesgeschäft der Informatik • Korrektheit eines Algorithmus • Expertensysteme / KI : automatisches Beweisen • Chip-/Softwareverifikation 1.12.1 Direkter Beweis • Grundlage: modus ponens (A ∧ (A ⇒ B)) ⇒ B • A wahr: A ⇒ B1 ⇒ B2 ⇒ ... ⇒ B Beispiel Behauptung: Wenn n ∈ N durch 8 teilbar, (A) dann ist n auch durch 4 teilbar (B) Beweis: Sei n ∈ N : n teibar durch 8 dann existiert k ∈ N : n = 8 k = 4 ∗ 2 ∗ k also 4n = 2 ∗ k ∈ N also n teibar durch 4 1.12.2 indirektes Beweisen • Grundlage: Kontraposition • D.h. statt A ⇒ B (mittels m.p.) folgere ¬B ⇒ ¬A (mittels m.p.) Beispiel Behauptung: ist n2 eine ungerade natürliche Zahl, (A) dann ist auch n ∈ N ungerade (B) Beweis: ¬B : n ∈ N gerade dann existiert k ∈ N: n =2∗k ⇒ n2 = 4 ∗ k 2 = 2 ∗ (2k 2 ) n2 = 2 ∗ k 2 ∈ N ⇒ n∗2 ⇒ n2 gerade : ¬A

20.10.2010 - 28.10.2010

www.studiWI.de

Seite 5/ 8

WI - B05 - Mathematik für Wirtschaftsinformatiker 1.12.3 Widerspruchsbeweis • Grundlage: ¬(F ∧ ¬F ) • Um Aussage zu beweisen, nimmt man ¬A wahr an. Führe korrekte Implikation aus: (¬A ⇒ B1 ⇒ B2 ⇒ ... ⇒ 0) wahre Aussage ¬A : 0 ⇔ A : 1 √ Beispiel √Behauptung: 2 6∈ Q, das heißt es gibt keinen Bruch z mit 2 = nz n √ √ ¬A : 2 ∈ Q, dann zn = 2 ohne Kürzungen 2 ⇒ zn2 = 2 ⇔ z 2 = 2 ∗ n2 (z 2 gerade) ⇒ (z gerade) ⇒ ∃k ∈ N : z = 2 ∗ k ⇒ z 2 = (2 ∗ k)2 = 4 ∗ k 2 ⇒ 4 ∗ k 2 = 2 ∗ n2 ⇒ 2 ∗ k 2 = n2 d.h. im Bruch steckt der Faktor 2 keine Kürzung im Bruch √ 2 6∈ Q, Q ≤ R D 6 ∅ √\ Q = 2∈R\Q Behauptung: Wenn n ∈ N gerade, dann ist n + 3 ungerade A↑ ⇒ B↑ Annahme: n + 3 sei gerade ⇒ ∃k ∈ N : n+3=2∗k ⇒n =2∗k−3 ⇒ n2 hat Rest ⇒ n2 6∈ N d.h. n ungerade zur Prämisse ⇒ n + 3 ungerade 1.12.4 Äquivalenz-Beweis • Benutzung der Gestalt A ⇔ B zu zeigen, wird entweder in 2 Schritten ausgeführt A ⇒ B (in einer passenden Strategie) B ⇒ A (in einer passenden Strategie) • oder A ⇔ B1 ⇔ B2 ⇔ ... ⇔ B bei A ⇔ B1 Vorsicht! muss sicher sein 1.12.5 vollständige Induktion Aussage für N0 : A(n), n ∈ N0 , n ≥ n0 Pn i = 1 + 2+ ... +n = A(n), i=1 n ∈ N0 , n ≥ 1(= n0 )

n(n+1) 2

Induktionsanfang Beweise: A(n0 ) P1 1(1+1) A(n0 ) = A(1) : i=1 =1 i=1 2 also A(1) wahr.

20.10.2010 - 28.10.2010

www.studiWI.de

Seite 6/ 8

WI - B05 - Mathematik für Wirtschaftsinformatiker Induktionsschluss A(n) ⇒ A(n + 1) Durchhangeln durch N mit einem Implikation-Schritt Pn+1 P A(n + 1) : i=1 i = ( n+1 i=1 i) + (n + 1) I.A. → =

n(n+1) 2

+ (n + 1)

=

n(n+1)+2(n+1) 2

=

(n+1)∗(n+2) 2

A(1)∨, A(2), A(3) A(1) ⇒ A(2) A(2) ⇒ A(3) Beispiel alle n ∈ N0 : PnSatzi Für A(n) : i=0 2 = 2n+1 − 1 Beweis vollständiger Induktion I.A. : A(0) linke Seite: 20 = 1 rechte Seite: 20+1 − 1 = 1 ⇒ A(0) Induktionsschluss + 1) Pn (n i⇒ nP n+1 i A(n + 1) L.S. i=0 2 ) + 2n+1 2 = ( i=0 ⇒ (da A(n) wahr angenommen): Pn+1 i n+1 − 1 + 2n+1 = 2 ∗ 2n+1 − 1 i=0 2 = 2 = 21 ∗ 2n+1 − 1 = 2n+2 − 1 → R.S.vonA(n + 1) ⇒ A(n + 1) wahr AA(n) = 2n+1 − 1 AA(n) = 2n+2 − 1 somit linke = rechte Seite Pn i an+1 −1 Beispiel Satz i=0 a = a−1 für alle n ∈ N0 (geometrische Summe) a ∈ R, a 6= 1 Beispiel Satz Für alle n ∈ N gilt: h2n ≥ 1 + n2 , wobei: k∈N Pk hk := i=1 h2n =

P2n

1 i

1 i=1 i

=

1 1

+

1 2

+ 13 + ... + k1

=

1 1

+ 12 + ... +21n

hk ’k + e harmonische Zahl“ ( 1i i ∈ N = (1, 21 , 13 , 41 , ...) P∞

1n i=1 i

= ∞n

20.10.2010 - 28.10.2010

www.studiWI.de

Seite 7/ 8

WI - B05 - Mathematik für Wirtschaftsinformatiker Beispiel Ungleichung von Bernoulli ist a ≥ −1 beliebige reelle Zahl, dann : ∀n ∈ N : (1 + a)n ≥ 1 + n ∗ a I.A.c: n = 1 : (1 + a)1 (Esel) 1+a (Gaul) n → n + 1

A(n)

(1 + a)n+1 = (1 + a)n ∗ (1 + a) A(n) wahr →≥ (1 + n ∗ a) ∗ (1 + a) = 1 + a + n ∗ a + n ∗ a2 n ≥ 0 und a2 ≥ 0 = n ∗ a2 ≥ 0 ≥1+n+n∗a 1 + a(n + 1) : A(n + 1) R.S. 

20.10.2010 - 28.10.2010

www.studiWI.de

Seite 8/ 8

WI - B05 - Mathematik für Wirtschaftsinformatiker

1

Relationen und Funktionen

1.1

Abbildung = Funktion

• D : Definitionsbereich; W : Wertebereich • Sind D 6= ∅ Mengen, dann ist Abbildung (= Funktion) f zwischen D und W eine Vorschrift : f : D → W , die jedem xǫD ein eindeutiges f (x)ǫW zuordnet. 1.1.1 Beispiel f : M → L M = {a, b, c, d}, L = {1, 2, 3}

f (a) = 1 f (b) = f (c) = f (d) = 3 nicht erlaubt: f (a) = 2 zusätzliche Abbildung d.h. von jedem x ∈ D = M darf nur ein Pfeil ausgehen es muss von jedem v ∈ D genau ein Pfeil ausgehen 1.1.2 Beispiel f : R → R f : R+ → R R+ := {x ∈ R :} x → f (x) = x2

1.2

Bild

Zu f : D → W und A ≤ D heißt f (A) = {f (x) : x ∈ A} “Bild von A unter f “ f (D) heißt “Bild von f “ 1.2.1 Beispiel f (A), A = {b, c, d } ≤ D = M f (A) = {3}, f(M ) = {1, 3} 1.2.2 Beispiel f : R+ → R R+ : {x ∈ R :≥ 0} √ x → f (x) := x f (R+ ) = R+ f : R+ → R+

28.10.2010 - 04.11.2010

www.studiWI.de

Seite 1/ 13

WI - B05 - Mathematik für Wirtschaftsinformatiker 1.2.3 Beispiel zu a ∈ R bei ist |a| := a, a ≥ 0 und −a, a ≤ 0 der Absolutbetrag von a | − 13| = 13 |0| = 0 f :R→R x → f (x) := |x| Betragsfunktion: f (R) = (Übung) 1.2.4 Beispiel Abstand zweier reeller Zahlen: a, b |a − b| = |b − a| a = −7 b = 13 |a − b| = | − 7 − 13| = | − 20| = 20 |b − a| = |13 − −7| = |13 + 7| = |20| = 20

1.3

binäre Relation

M, L Mengen, M = 6 ∅ , L 6= ∅ Dann heißt R ≤ M ∗ L binäre Relation Sprechweise: (x, y) ∈ R : x (bzw. y) steht in Relation R zu Schreibweise: xRy R = “ ≤ “, M = L = Z ≤⊆ Z2 (2, 3) ∈≤ 2 ≤ 3 (3, 1) 6∈≤ Z2 := {(x, y) : x ∈ Z, y ∈ Z} 1.3.1 Beispiel M = {x : x ist Prof-HTW } L = {y : y ist Kurs-HTW } “Prof leitet Kurs“-Relation R ≤ M ∗ L Prof x leitet Kurs y “(Bannert, Programmierung 1) ∈ R“ oder “Bannert R Programmierung 1“ “(Bannert, Software 3) ∈ R“ “(Swat, Statistik 1) ∈ R“

28.10.2010 - 04.11.2010

www.studiWI.de

Seite 2/ 13

WI - B05 - Mathematik für Wirtschaftsinformatiker 1.3.2 Beispiel f : D → W Funktion kann als binäre Relation aufgefasst werden: Funktionsgraph: Gf = {(x, f (x)) : x ∈ D} ≤ D ∗ W z.B. f (x) = x2 R ∗ R = markierter Bereich

1.3.3 Beispiel nicht erlaubt f (a) = 2 R ≤M ∗L

R = {(a, 1), (a, 2), (b, 2), (c, 2), (d, 1), (d, 2), (d, 3)} ≤ M ∗ L Jede Funktion 1 Variablen ist binäre Relation, aber nicht umgekehrt 1.3.4 Beispiel ≤⊆ Z2 : (x, y) ∈≤ genauso ann wenn x kleiner y oder x = y x ≤ y falls (x, y) ∈≤ 1.3.5 Beispiel Auch mehrstellige Relationen möglich R ≤ M1 ∗ M2 ∗ ... ∗Mn → relationale Datenbank-Tabellen

1.4

Funktion f : M → L heißt:

• injktiv genau dann wenn zu jedem y ∈ L gibt es entweder 0 oder 1 Element in M , die auf y abgebild...