Kapitel 2 - Elementare Grundlagen Flashcards
Logik, Mengen, vollständige Induktion, Relationen und Abbildungen (33 cards)
Definiere den Begriff “Negation”!
Ist A eine Aussage, so können wir ihr eine negierte Aussage Nicht-A zuweisen, deren Wahrheitswert dem umgedrehten Wert von A entspricht.
Was versteht man unter Konjunktion?
Eine Konjunktion ist die Verknüpfung zweier Aussagen (Wahrheitswerte) mittels UND-Operator. Dabei ist die resultierende Aussage wahr, wenn die beiden verknüpften Aussagen wahr sind, sonst falsch.
Was versteht man unter Disjunktion?
Eine Disjunktion ist die Verknüpfung zweier Aussagen (Wahrheitswerte) mittels ODER-Operator. Dabei ist die resultierende Aussage falsch, wenn die beiden verknüpften Aussagen falsch sind, sonst wahr.
Was versteht man unter Implikation?
Die Verknüpfung zweier Aussagen mittels =>, wobei “A => B” als “Aus A folgt B” oder “A impliziert B” gelesen wird. Der Wahrheitswert der resultierenden Aussage ist falsch wenn A wahr und B falsch ist, sonst wahr.
Was versteht man unter Äquivalenz?
Die Verknüpfung zweier Aussagen mittels <=>, wobei “A <=> B” als “A ist äquivalent zu B” gelesen wird. Der Wahrheitswert der resultierenden Aussage ist wahr, wenn die Wahrheitswerte von A und B jeweils übereinstimmen, sonst falsch.
Was passiert, wenn eine Aussage doppelt negiert wird?
Doppelte Negation hebt sich auf. Somit ist eine Aussage der Form “Nicht(Nicht A)” äquivalent zu “A”.
Nenne die Kommutativgesetze in der Logik!
A ODER B = B ODER A bzw A UND B = B UND A
Nenne die Assoziativgesetze in der Logik!
(A ODER B) ODER C = A ODER (B ODER C)
bzw
(A UND B) UND C = A UND (B UND C)
Nenne die Distributivgesetze in der Logik!
A UND (B ODER C) = (A UND B) ODER (A UND C) bzw A ODER (B UND C) = (A ODER B) UND (A ODER C)
Beweise!
Wenn für eine natürliche Zahl n ihr dritte Potenz n^3 durch 2 teilbar ist, dann ist auch n durch 2 teilbar.
Die Aussage hat die Form A => B mit:
A = “Für die natürliche Zahl n ist n^3 durch 2 teilbar.”
B = “Die natürliche Zahl n ist durch 2 teilbar.”
Beweis durch Widerspruch:
Angenommen A wahr => Aussage wahr, wenn B wahr
Angenommen B ist falsch. -> n ist ungerade
-> n schreibbar als n = 2k + 1 mit k aus den nat. Zahlen
Folglich:
n^3 = (2k+1)^3=8k^3+12k^2+6k+1 = 2(4k^3+6k^2+3k)+1
= 2k’+1 mit k’ := 4k^3+6k^2+3k aus den nat. Zahlen.
Folglich: n^3 ungerade => A falsch
-> Widerspruch
Definiere den Begriff der Teilmenge!
Wenn für eine Menge A gilt, dass alle ihre Elemente in einer anderen Menge B vertreten sind, dann gilt “A ist Teilmenge von B” bzw auch “B ist Obermenge von A”.
Besonderheit: Jede Menge ist auch Teilmenge von sich selbst. Insbesonder gilt:
(A TM B) UND (B TM A) => A = B
Was ist die Potenzmenge einer Menge?
Die Potenzmenge 2^A einer Menge A ist die Menge aller Teilmengen von A.
Sei A eine Menge. Wie mächtig ist deren Potenzmenge?
Die Mächtigkeit der Potenzmenge von A beträgt
|2^A| = 2^|A|
Definiere den Begriff Schnittmenge!
Die Schnittmenge zweier Mengen A und B ist die Menge, die alle Elemente enthält, die sowohl in A, als auch in B enthalten sind.
Wann sind zwei Mengen disjunkt?
Wenn die Schnittmenge zweier Mengen A und B leer ist, werden die Mengen A und B als disjunkt bezeichnet.
Definiere den Begriff Vereinigungsmenge!
Die Vereinigungsmenge zweier Mengen A und B ist die Menge, die alle Elemente enthält, die entweder in A oder in B enthalten sind.
Definiere den Begriff Differenzmenge!
Die Differenzmenge A\B zweier Mengen A und B ist die Menge, die alle Elemente enthält, die in A, aber nicht in B vorhanden sind.
Beweise! Für Mengen gelten die Kommutativgesetze.
Behauptung 1: A schnitt B = B schnitt A
Behauptung 2: A vereinigt B = B vereinigt A
Beweis 1:
A schnitt B
= {x|x aus A UND x aus B}
= {x|x aus B UND x aus A}
= B schnitt A
Beweis 2:
A vereinigt B
= {x|x aus A ODER x aus B}
= {x|x aus B ODER x aus A}
= B vereinigt A
Beweise! Für Mengen gelten die Assoziativgesetze.
Behauptung 1:
(A schnitt B) schnitt C = A schnitt (B schnitt C)
Behauptung 2:
(A vereinigt B) vereinigt C = A vereinigt (B vereinigt C)
Beweis 1:
(A schnitt B) schnitt C
= {x|x aus (A schnitt B) UND x aus C}
= {x|(x aus A UND x aus B) UND x aus C}
= {x|x aus A UND (x aus B UND x aus C)}
= {x|x aus A UND x aus (B schnitt C)}
= A schnitt (B schnitt C)
Beweis 2:
(A vereinigt B) vereinigt C
= {x|x aus (A vereinigt B) ODER x aus C}
= {x|(x aus A ODER x aus B) ODER x aus C}
= {x|x aus A ODER (x aus B ODER x aus C)}
= {x|x aus A ODER x aus (B vereinigt C)}
= A vereinigt (B vereinigt C)
Beweise! Für Mengen gelten die Distributivgesetze.
Behauptung 1:
A vereinigt (B schnitt C) = (A vereinigt B) schnitt (A vereinigt C)
Behauptung 2:
A schnitt (B vereinigt C) = (A schnitt B) vereinigt (A schnitt C)
Beweis 1:
A vereinigt (B schnitt C)
= {x|x aus A ODER x aus (B schnitt C)}
= {x|x aus A ODER (x aus B UND x aus C)}
= {x|(x aus A ODER x aus B) UND (x aus A ODER x aus C)}
= {x|(x aus A vereinigt B) UND (x aus A vereinigt C)}
= (A vereinigt B) schnitt (A vereinigt C)
Beweis 2:
A schnitt (B vereinigt C)
= {x|x aus A ODER x aus (B vereinigt C)}
= {x|x aus A ODER (x aus B UND x aus C)}
= {x|(x aus A ODER x aus B) UND (x aus A ODER x aus C)}
= {x|(x aus A schnitt B) UND (x aus A schnitt C)}
= (A schnitt B) vereinigt (A schnitt C)
Nenne die Regeln von De Morgan (und beweise sie, wenn zeitlich möglich)!
Voraussetzungen: A, B, S Mengen; A,B TM S
Regel 1:
S(A vereinigt B) = S\A schnitt S\B
bzw
(A vereinigt B)-Komp = A-Komp schnitt B-Komp
Regel 2:
S(A schnitt B) = S\A vereinigt S\B
bzw
(A schnitt B)-Komp = A-Komp vereinigt B-Komp
[Komp = Komplement]
Beweis 1:
S(A vereinigt B)
= {x|x in S UND x nichtIn (A vereinigt B)}
= {x|x in S UND NICHT(x in A ODER x in B)}
= {x|x in S UND (x nichtIn A UND x nichtIn B)}
= {x|x in S UND x nichtIn A UND x nichtIn B}
= {x|(x in S UND x nichtIn A) UND (x in S UND x nichtIn B)}
= {x|x in S\A UND x in S\B}
= S\A schnitt S\B
Beweis 2:
S(A schnitt B)
= {x|x in S UND x nichtIn (A schnitt B)}
= {x|x in S UND NICHT(x in A UND x in B)}
= {x|x in S UND (x nichtIn A ODER x nichtIn B)}
= {x|(x in S UND x nichtIn A) ODER (x in S UND x nichtIn B)}
= {x|x in S\A ODER x in S\B}
= S\A vereinigt S\B
Negiere folgende Aussagen!
a) Für alle x aus M gilt: A(x
(b) Es gibt ein x aus M, sodass gilt: A(x)
(a) Es gibt ein x aus M, sodass gilt: NICHT(A(x))
b) Für alle x aus M gilt: NICHT(A(x)
Beweise mit vollständiger Induktion!
Die Summe der dritten Potenzen von drei aufeinanderfolgenden natürlichen Zahlen
ist stets ganzzahlig durch 9 teilbar.
Behauptung:
Für alle a,b,c aus Nat mit a=b+1 und b=c+1 gilt:
9 | a^3+b^3+c^3 [a | b => sprich: a teilt b], bzw
Für alle n aus Nat gilt:
9 | n^3+(n+1)^3+(n+2)^3
Beweis:
Induktionsanfang (n=0):
0^3+1^3+2^3 = 0+1+8 = 9
9 | 9 => gilt für n=0
Indutionsschritt (n -> n+1):
z.z.: 9 | (n+1)^3+(n+2)^3+(n+3)^3
(n+1)^3+(n+2)^3+(n+3)^3
= (n+1)^3+(n+2)^3+n^3+3n^23+3n3^2+3^3
= n^3+(n+1)^3+(n+2)^3+9n^2+27n+27
[laut IV gilt: 9 | n^3+(n+1)^3+(n+2)^3, also kann man schreiben n^3+(n+1)^3+(n+2)^3 = 9k mit k aus Nat]
= 9k+9n^2+27n+27 = 9(k+n^2+3n+3) = 9k’ (k’ aus Nat)
=> 9 | (n+1)^3+(n+2)^3+(n+3)^3 q.e.d.
Wann heißt eine Abbildung/Funktion f : X -> Y injektiv?
Eine Abbildung/Funktion f : X -> Y heißt injektiv, wenn für alle x,y aus X gilt:
f(x) = f(y) => x = y
[“Jedes b aus Y hat höchstens ein Urbild.”]
