Mathematik für Informatiker (Vorlesung 2)

Mux

Vereinfachte MUX

• 1 Steuerung (Auswahl welcher Input gewählt wird)
• 2 Input
• 1 Ausgabe

Bestimmung der Minterme, wo m=1m=(¬s*¬x₀*x₁)+(¬s*x₀*x₁)+(s*x₀*¬x₁)+ (s*x₀*x₁)Komplexität = 11Vereinfachungm=(¬s*¬x₀*x₁)+(¬s*x₀*x₁)+(s*x₀*¬x₁)+ (s*x₀*x₁)=(¬s*x₁)(¬x₀+x₀) + (s*x₀)(¬x₁+x₁)=¬sx₁+ sx₀Komplexität=3

Prädikatenlogik und Quantoren

• Allquantor: Alle sind – ∀x : A(x)
• Existenzquantor: 1-n Zahlen vorhanden -∃x : A(x)
• Nur eine Zahl x – ∃!x : A(x)

Primzahlen

• Nur eine gerade Primzahl: 2

Negation

Lemma¬ (∀x : A(x)) ⇔ (∃x : ¬A(x))¬ (∃x : A(x)) ⇔ (∀x : ¬A(x)Beispiel∃ x ∈ R⁺: x²= 2Lösung∀ x ∈ R⁺😡²≠ 2Beispiel 9x ist eine gerade PrimzahlBeispiel

¬(∃ x ∈ R: x²= -1) ⇔ ∀x ∈ R: x² ≠ -1

Naive Mengenlehre

1. M={1,2}, N={1,2,3,4}
2. wenn N mehr elemtente als M hat, dann kann es nicht Teilmenge sein
3. M ist eine echte Teilmenge von N ⇔
   1. M ist Teilmenge von N
   2. N enthält wenigstens ein Element, das nicht in M liegt (z.B.: 3∉M, 4∉M)
4. M = N ⇔ (M⊂N ∧ N⊂M)
5. N = {b,y,e,s), M = {b,y,e,s,d) ⇔ N⊂M, d ∈ M, d∉N ⇔ n⊄M
6. Gesucht: alle Teilmengen von M (M={n,e}
   1. {} ⊂ M
   2. {n} ⊂ M
   3. {e} ⊂ M
   4. {n,e} ⊂ M
   • Die Menge aller Teilmengen einer Menge M heißt die Potenzmenge von M, Berechnung P(M)
   • P(M) = {n: N⊂M)
   • P({n,e}) = {{}, {n}, {e}, {n,e}} = 4 Elemente

Berechnung der Teilmengen

M eine Menge mit n Elementen ⇒ Potenzmenge von M hat dann 2ⁿ Elemente