2
16.10.2012

Seite zu MafI1:
http://www.inf.fu-berlin.de/lehre/WS12/mafi1/index.html

Klausurtermin(vermutlich): Letzte Vorlesungswoche oder erste/zweite Woche der Semesterferien/Vorlesungsfreien Zeit

Klaus Kriegel
kriegel@inf.fu-berlin.de
https://www.mi.fu-berlin.de/kvv/lecturer.htm?id=150
http://www.inf.fu-berlin.de/inst/ag-ti/members/kriegel.de.html
Sprechzeiten: Mi: 11:00-12:30 Uhr (R 115)

Abgabe von Übungsblättern in der Arnimallee 3 (treppe hoch) NICHTHT PI
Standardmäßig bis Freitag, Donnerstagsgruppen bis Montag um Zehn.

Logik und diskrete Mathematik

Logik 1:

Aussagen
logische Operationen
Syntax und Semantik
Normalformen
Prädikate
Beweismethoden

Mengenlehre:

Mengen, Operationen
Relationen, Äquivalenzrealtionen
Funktionen
natürliche Zahlen
Abziehbarkeit

Kombinatorik:

Grundregeln
Binomialkoeffizienten
Rekursionen
Schubfachprinzip
Wahrscheinlichkeitsräume

Graphen:

Grundbegriffe
bipartite Graphen
Bäume

Logik2

Resolutionskalkül
Hornformeln
Prädikatenlogik

Aussagenlogik

Aussage

Definition

Eine Aussage ist ein formalsprachliches Gebilde, das entweder wahr oder falsch ist.

Beispiele

"7 ist Primzahl"→wahr
"8+5=12"→falsch
"n ist Primzahl" → keine Aussage(Prädikat)
"Dieser Satz ist falsch"→ keine Aussage
"Jede gerade Zahl ≥ 4 ist Summe von 2 Primzahlen" → Aussage

Negation
Die Negation einer Aussage x wird mit ¬x bezeichnet. Diese Operation kehrt den Wahrheitswert von x um, d.h. man kann sie mit ¬0 = 1 und ¬1 = 0 als Funktion auf den Wahrheitswerten beschreiben.

0 - falsch
1 - wahr

x | ¬x (macht x)
0 | 1
1 | 0

Zur Verknüpfung von zwei Aussagen x und y stehen die folgenden Konstrukte zur Verfügung:
• die Konjunktion x ∧ y, gesprochen “x und y”;
• die Disjunktion x ∨ y, gesprochen “x oder y”;
• die Implikation x → y, gesprochen “aus x folgt y” oder “wenn x, dann y”
• die Aquivalenz x ↔ y, gesprochen “x genau dann, wenn y”,
• die Antivalenz x ⊕ y, gesprochen “entweder x oder y”.

x|    y | x ⋀ y    | x ⋁ y | x → y   | x ↔ y   | x ⊕ y
0|    0 |       0 |      0 |       1 |       1 |       0
0|    1 |       0 |      1 |       1 |       0 |       1
1|    0 |       0 |      1 |       0 |       0 |       1
1|    1 |       1 |      1 |       1 |       1 |       0

18.10.2012

Formeln der Aussagenlogik (FdA)

Definition

Sei Var eine Menge von Variablen (Var={x,y,z,x1,x2....})
Zusätlich die Symbole 0 und 1

Jede Variable aus Var und die Symbole 0 und 1 sind FdA (Primformel)
Ist t eine FdA, dann auch (¬t)
Sind s und t FdA, dann auch (s⋀t), (s⋁t), (s→t), (s↔t) und eventuell (s⊕t)
Jede FdA kann man durch obige Konstruktion aus Primformeln erzeugen.

       Formel(Term) ⟼ Syntaxbaum
                     ((((¬y)⋀z)↔(x→z))⋁(¬x))
                          | --------------------(⋁)------------------------------|
          |-----------↔-----------                                                   ¬
-------⋀-----                   --→--                                                  |
¬             z                  x       y                                                 x
y

Regeln für das Klammernweglassen

Äußere Klammern kann man weglassen
in der Reihenfolge ¬, ⋀, ⋁, →, ↔ nimmt die Bindungskraft ab und die Trennungskraft zu.
Klammern die mit dieser Hierarchie übereinstimmen kann man weglassen

1. Beispiel

:
((((¬y)⋀z)↔(x→z))⋁(¬x)) (kann man relativ einfach anhand der Baumstruktur überprüfen)
//Baum
=> (¬y⋀z↔x→z)⋁¬x

2. Beispiel

:
x⋀y v ¬ z ⋀ u → ¬x ↔ y
(x⋀y v ¬ z ⋀ u → ¬x ↔ y)
((x⋀y v ¬ z ⋀ u → ¬x) ↔ y)
(((x⋀y v ¬ z ⋀ u) → (¬x)) ↔ y)
((((x⋀y) v (¬ z ⋀ u)) → (¬x)) ↔ y)
((((x⋀y) v ((¬ z) ⋀ u)) → (¬x)) ↔ y)

Auswertung von Formeln mit Wahrheitstafeln (Wahrheitswerttabellen)

t= (x⋀¬y))-->(zvx))       t≡(¬x⋁x)
             s1      s2
x|y|z|¬y|x⋀¬y|zvx|s1-->s2
0|0|0|1 |0   |0 |1   |
0|0|1|1 |0   |1 |1   |
0|1|0|0 |0   |0 |1   |
0|1|1|0 |0   |1 |1   |
1|0|0|1 |1   |1 |1   |
1|0|1|1 |1   |1 |1   |
1|1|0|0 |0   |1 |1   |
1|1|1|0 |0   |1 |1   |

Definition

Zwei Formeln s und t sind logisch äquivalent, wenn sie für jede Belegung der Variablen den gleichen Wert bekommen Notation s≡t.
Nachweis durch Wahrheitstafeln möglich.
Alternative: Nutzung der Gesetze und Regeln der sogenannten Boolschen Algebra
Satz:Für beliebige Formeln s,t und r gelten die Folgenden Äquivalenzen

IN DER KLAUSUR DARF EIN MERKZETTEL MIT DEN ENTSPRECHENDEN GESETZEN GENUTZT WERDEN

//Regeln siehe Skript der Vorlesung Seite 7

Beispiel (was nicht im Script steht)
(¬(x⋀y) ⋁ u) ⋀ (¬(y⋁z)⋀¬y
≡ (¬(x⋀y) ⋁ u) ⋀ ¬y (Absorbtion + Kommutativität)
≡ ((¬x ⋁ ¬y) ⋁ u) ⋀ ¬y (deMorgan)
≡ (¬y ⋁ (¬x ⋁ u)) ⋀ ¬y (komm + abs)
≡ ¬y

Weitere Äquivalenzen (vgl Script S. 8)
(1) s→t≡¬s⋁t
(2) s↔t≡(s⋀t)⋁(¬s⋀¬t)
       ≡(¬s⋁t)⋀(¬t⋁s)
(3) (s→(t∧r)≡(s→t)∧(s→r)
(4) s→(t∨r)≡(s→t)∨(s→r)
(5) s∧t→r ≡ (s→r)∨(t→r)
(6) s∨t→r ≡ (s→r)∧(t→r)

Def.: Sei s eine FdA, dann sei s erfüllbar wenn es (mindestens) eine Belegung für die Variablen gibt, für die s den Wert 1 annimmt
    s ist eine Tautologie, wenn s für jede Belegung den Wert 1 annimmt
    s ist eine Kontraktion, wenn s für keine Belegung den Wert 1 annimmt

23.10.2012

Prädikate und Quantoren

Ein Prädikat ist ein formelsprachliches Gebilde, das eine oder mehrere Variablen enthält, so dass bei Belegung aller Variablen durch Objekten aus einem vorher vereinbarten Individualbereich(Universum) eine Aussage (mit Werteberich 0 oder 1) entsteht.

Beispiel: "x ist Hauptstadt aus europ. Land"
U = Menge der Städte in Europa
P(London) -> wahr
P(Bernau) --> falsch

weitere Beispiele:
Q(x) = "x^2 = x"    Bereich N oder Q
R(x,y) = "x<y"      Bereich N oder Q

Q(3) -> falsch
Q(1) -> wahr
R(1,5)->wahr
R(3,2)-> falsch

Quantoren, Alilquantor ∀ für alle x∈U gilt...
           Existenzquantor ∃ es gibt in x∈U, so dass...
∀ x ∈N    Q(x= = "Für alle x∈N gilt x^2=x"
            -> falsch (Gegenbeispiel 3)
∃x∈N    Q(x= = "Es gibt ein x∈N mit x^2=x"
            -> wahr (x = 1)
∀x∈N ∀y∈N R(x,y) -> falsch (x = 3 y = 2)
-> wahr
    "Beweis": x = a finden wir y = a+1    a<a+1 wahr

∀y∈N ∃x∈N R(x,y) ->falsch
    für y =0 gibt es keine kleinere natürliche Zahl
Achtung: ∀x∈Q ∃y∈R R(x,y) ->wahr
         für y=a setze x=a-1

f:R->R
f ist stetig an der Stelle X0
∀ε>0 ∃√>o ∀x |x-x(irgendwas unten rechts vom x)|...

Negation: ¬∀x∈U P(x) ≡ ∃x ¬(P(x))
          ¬∃x∈U P(x) ≡ ∀x ¬(P(x))

Fakt: ∀x P(x) ⋀ ∀xQ(x) ≡ ∀x(P(x) ⋀ Q(x)
      ∃x P(x) ⋁∃xQ(x) ≡ ∃x(P(x) ⋁ Q(x)

Achtung: ∀x P(x) ⋁ ∀xQ(x) ≠ ∀x(P(x) ⋁ Q(x)
         ∃x P(x) ⋀∃xQ(x) ≠ ∃x(P(x) ⋀ Q(x)

∀x∀y R8x,y) ≡ ∀y∀x R(x,y)
∃x∃y R8x,y) ≡ ∃y∃x R(x,y)

⚡⚡

Beweis für Wahrheit einer quantifizierten Aussage
1) In Standardform bringen, so dass alle Quantoren am Anfang stehen
2)Spiel:Ggenspieler darf alle Variablen vom Allquantor belegen
         Beweiser darf geeignete Belegungen für Variablen vom Wxistenzquantor wählen
3)Verifizierung der Aussage

Beispiel: " Für 2 verschiedenene rationale Zahlen gibt es immer eine, die dazwischen liegt." Bereich Q

∀x∀y (x<y) → ∃z(x<z ⋀ z<y)
Beweis:
    1) umformen: ∀x∀y    ¬(x<y) ⋁ ∃z (x<z ⋀ z < y)
                ≡ ∀x ∀y ∃z (x≥y)⋁ ∃z (x<z ⋀ z < y)
                ≡ ∀x ∀y ∃z (x≥y) ⋁ (x<z ⋀ z<y)
    2) Spiel:
        Gegenspieler x=a    y=b
        Beweis: z = (a+b)/ z
    3) Verifikation: Beweis: a ≥ b ⋁ (a<(a+b)/z ⋀ (a+b)/z
< b)
     Fall_1: a ≥ b     fertig
     Fall_2: ¬a≥b -> a<b -> a+a < a+b -> (a+a)/2<(a+b)/2
                     sowie a+b<b+b -> (a+b)/z < (b+b) / z = b

keine weitere Aussage für Bereich N; Beweise, dass die Negation wahr ist
¬(∀x∀y (x<y) -> ∃z (x<z ⋀ z < y))
∃x∃y ¬[(x<y) -> ∃z (x<z ⋀ z < y))]
∃x∃y [¬       ⋁                   ] de morgan
∃x∃y [(x<y) ⋀ ∀z ¬(x<z) ⋁ ¬(z < y)] de morgan
2) Spiel: Beweiser x = 1    y = 2
    Gegenspieler: z = a
3) zu zeigen 1≥a ⋁ a≥z   -> :)

Beweistechniken (25.10.)

Ziel: Nachweis p→q
                p = verweis
                q = behauptung

-direkte Beweise                        p→q≡p→r⋀r→q≡p->r1⋀r1→r2⋀...⋀r_k→q
-indirekte Beweise ->Kontraposition    p→q≡ ¬q→¬p
                    ->Widerspruch       p→q≡p⋀¬q→0
-Fallunterscheidung                    p→q≡(p⋀r→q)⋀(p⋀¬r→q)
Wahrheitstabelle (papierschiff hat keine lust)

25.10.2012
Abgabe in den Fächern in der Mathematik

Satz: Ist a ∈ N eine ungerade Zahl, dann ist (a+1)² durch 4 Teilbar.
Gedanke: wenn a ungerade ist, ist a+1 gerade (durch 2 teilbar) und durch das ² durch 4 teilbar.
Def.: a ∈ N ist ungerade, wenn es ein k ∈ N gibt, so dass a=2k+1
       a ∈ N, b ∈ N+. Dann ist b ein Teiler von a, wenn ein c ∈ N existiert, so dass a=b*c ist
       Notation: b|a

Beweis: a ist ungerade
=> ∃k∈N a     = 2k+1       |Def ungerade
=> ∃k∈N a+1   =(2k+1)+1    |
              =2k+2        |Asso.+Distributivität
              =2(k+1)      |
=> ∃k∈N (a+1)²=(2(k+1))(2(k+1))
              =4(k+1)²
=> 3k' (a+1)²=4k'        |k' = (k+1)²
=> 4|(a+1)²                |Def. Teilbarkeit

Beweis durch Kontraposition: p→q=¬q→¬p
Satz: Ist a² ungerade, dann ist a ungerade
Beweis mit Kontraposition: a gerade → a² ist gerade
    a gerade
⇒ ∃k∈N a = 2k        |
⇒ ∃k∈N a² = (2k)²    |Quadrieren, Assoz. + Kommutativität
⇒        = 2(2k²)
⇒ a² ist gerade      |(Definition Teilbarkeit)

Widerspruchsbeweis: p→q ≡ p⋀¬q→0
Satz: Für jede natürliche Zahl n gilt:
      Ist √n keine ganze Zahl, dann ist √n auch nicht rational,
      also irrational.
Definitionen und Fakten:

√n existiert und ist reell
r ist rational, wenn ein k∈Z, n∈N+ existiert, so dass r= k/n
jede natürliche Zahl besitzt eine eindeutige(!) Zerlegung in Primfaktoren

____________________
Beweis mit Widerspruch:
Annahme: √n ist keine ganze Zahl, aber √n ist rational.
    ⇒ √n = m/(m')    m,m' ∈ N+
      n = p_1^(k_1)*p_2^(k_2)*...*p_l^(k_l)
    wären alle Potenzen k_1 ... k_i gerade, dann wäre √n ganzzahlig, nämlich √n = p_{1}^{(k_{1})/2} * ...p_{i}^{(k_{i})/2} ⇒ Widerspruch
    => mindestens ein k_i ist ungerade

    o.B.d.A.(ohne Beschränkung der Allgemeinheit, ~~ohne Bedenken des Autors~~, ~~offensichtlich Beeinflusst durch Alkohol~~) ist k_1 ungerade

    Betrachten Primzahlzerlegung für m und m'
        m = q1^{i1} * q_{j}^{ij}   m'= r1^(i'1)*....*rj^(i'j)
        √n = m/m' ⇒ n = m²/m'² ⇒ m² * n = m²
        r_1^{2i1}*...*r_j^{2ij}*p_i^{k}*.*p_i^{k1} = q_1^{2i1} * ... * q_j^{2ij}
    [linke Seite = *1; rechte Seite der Gleichung = *2]

        *1 = x∈N                   *2 = x∈N

        p1 tritt in x in ungerade Potenz auf. p_1 tritt in x in gerader potenz auf
        ⇒ Widerspruch zur eindeutigen Primzahlzerlegung von x

_____________________________________________
Beweise mit Fallunterscheidung: p→q ≡ (p⋀r → q) ⋀ (p⋀(¬r) → q)
Satz: Für drei aufeinanderfolgende natürliche Zahlen k, k+1, k+2 ist mindestens eine davon durch 3 teilbar.

Beweis:
Fallunterscheidung nach k mod 3 = Rest beim Teilen von k durch 3:
    Fall1: k mod 3 = 0 ⇒ k ist durch 3 teilbar
    Fall2: k mod 3 = 1 ⇒ k+2 ist durch 3 teilbar
    Fall3: k mod 3 = 2 ⇒ k+1 ist durch 3 teilbar

_____________________________________________
Satz:
Ist p eine Primzahl > 3, dann ist p²-1 durch 24 teilbar.
{--Gedanke: p²-1 ist durch 8 und durch 3 teilbar
                        2*2*2 und durch 3 teilbar--}
Beweis: p²-1 = p²-1² = (p-1)*(p+1) | 3. binomische Formel
   Betrachte: (p-1),p,(p+1)        | Eine ist durch 3 teilbar,
                                     aber nicht p
⇒ 3 | p²-1
⇒ zu zeigen 8|p^2-1
p ist ungerade => 2|p-1 ⋀ 2|p+1

genügt zu zeigen, dass 4|p-1 oder 4|p+1
Fall1: 4|p-1 => fertig
Fall2: 4∤p-1, aber 2|p-1
    dh. p-1 hat beim Teilen durch 4 den Rest 2
     ⇒ p-1 = 4 * l +2     l∈N
     ⇒ p+1 = (p-1)+2
           = 4l+2+2
           = 4l+4
           = 4(l+1)

Boolesche Formeln und Boolesche Funktionen

Syntax und Semantik:

Syntax    - äußere Gestalt
    ~ Boolesche Formeln (/Terme)

Semantik - Bedeutung, Interpretation
    ~ Boolesche Funktionen

Definition: Die Variablen aus der Menge {x,y,z,x1,x2,x3....} und die Symbole 0 und 1 sind Boolesche Formeln(Terme) vom Rang 0. Sie werden Primformeln genannt.
                                        [Eine Primformel ist
                                         einfach eine Variable,
                                         die wahr oder falsch ist]

Ist t eine Boolesche Formel vom Rang k, dann ist (¬t) eine BF vom Rang k+1

{--Rang k: Höhe des Syntaxbaumes bei Herleitung--}

Sind s und t BF vom Rang k und l dann sind (s⋁t) und (s⋀t) BF vom Rang max(k,l)+1
Alle BF können mit den obigen Regeln aus Primformeln gebildet werden.

Anmerkungen:

Man kann Primformeln auch ohne 0 und 1 definieren

-> Verweis: konjunktive/disjunktive Normalform

Regeln zum Weglassen der Klammern wie bei Aussagenlogik. Bei Weglassen von Klammern bei gleichen Operationen wird es als linksassoziative Klammerung interpretiert

                -> u ⋀ x ⋀ y⋀ z = (((u⋀ x)⋀y)⋀z

Syntaxbaum und Rang
in der klammer ist der rang()
                                ⋀(4)
                        ¬(3)            ⋁(1)
                        ⋀(2)          y(0)    z(0)
                   x(0=    ¬(1)
                           y(0)


    Rangebestimmung: bottom up
    Rang = Höhe des Baum = längster Weg von Wurzel zu Blatt

Vorlesung vom 30.10.2012

Strukturelle Induktion
Ist P(t) ein Prädikat über dem Bereich der Boolschen Formeln und ist

P(t) wahr für alle Primformeln t
Folgt aus der Gültigkeit von P(t) und P(s) auch immmer die Gültigkeit von P(t⋀s) sowie P(t⋁s), P(¬t), dann ist P(t) gültig für alle Boolschen Formeln.

Semantik (hatten wir früher schon gemacht, nun aber nicht mehr so einfach):
Def.:
Eine Belegung einer Variablen Var ist eine Funktion w: Var-->|B (|B={0,1})
Für Var_n ={x_1,....,x_n} bezeichnen wir mit
Ω_n die Menge aller Belegungen w: Var_n → V
Beobachtung: Es gibt eine umkehrbare Funktion T_n: Ω_n → |B^n = Menge aller n-Tupel über |B

T_n(w) = (w(x1),w(x2)..., w(xn))
Umkehrfunktion: T_{n}^{-1}:B^{n} → Ω_n

T_n^-1(b_1,...,b_n)=w mit
      w(x_i)=b_i

Auswertung einer Formel unter einer Belegung
T_n = Menge der B formeln über {x1,....xn} und 0, i
W∈Ω_n
ɸ_n:Ω_n x T_n → B
1=ɸ(w,x_i) = w(x_i)            Definition für Primformeln
ɸ(w,0) = 0
ɸ(w,1) = 1

2) Sei ɸ_n(w,t) definiert, dann ist
    ɸ_n(w, !t) = !ɸ_n(w,t)

3) Seien ɸ(w,t), ɸ(w,s) definiert, dann ist
    ɸ(w;s⋀t) = ɸ_n(w,s)⋀ɸ_n(w,t)
    ɸ(w;s⋁t) = ɸ_n(w,s)⋁ɸ_n(w,t)

Beobachtung:
ɸ_n(w,_): T_n → B
    Auswertung aller formeln unter Belegung w
ɸ_n(_,t): Ω_n → B
    Auswertung eines Terms unter allen Belegungen (Wahrheitstafeln)
ɸ_n(T_n^-1(_),t):|B^n-->|B
Ist die Interpretation des Terms t als Boolsche Funktion

Def: Ein n-stellige Boolsche Funktion ist eine Abbildung f:B^{n}→B
Beispiel
Wahrheitstabelle:
B^2|B         x1|x2|f(x1,x2)
0,0|0         0 |0 |0
0,1|1    <=> 0 |1 |1
1,0|0         1 |0 |0
1,1|0         1 |1 |0

B.Formel-->Boolsche Funktion
        <--                   ?
        Im Beispiel !x1^x2
        Allgemeines später
B_n: Menge aller Boolschen Funktionen, die n-stellig sind
(unendlich)
B= U B_n       B_0=|B=Konstante Funktion
n=0

Wie groß ist B_n?
Wie viele Funktionen f:A-->B gibt es wenn |A|=k und |B|=l ist?
Die Anzahl ist l^k
Begründung:A={a1,a2,...,a_k}
f(a1)∈B, f(a2)∈B,...,f(ak)∈B
l Möglichkeiten*lMöglichkeiten* *l Möglichkeiten
-->l^k Möglichkeiten
B_n={f:B^n-->|B)
        |     |
        v     v
       k=2^n   l=2
|B_n|=l^k=2^(2^n)

n     |0|1| 2| 3 | 4 |    5     |
|B_n| |2|4|16|256|65536|4294967296|

Def: Zwei Formeln s,t ∈T_n sind semantisch äquivalent(logisch äquivalent), wenn ɸ_n(w,t)=ɸ(w,s) für alle w∈Ωn

Beobachtung: Für jede Formel tT_n gibt es unendlich viele äquivalente Formeln
t≡t^1≡t^(x1v!x2)
     ≡(t^(x1v!x2))^(x1v!x2)

Def:
Seien s und t Boolsche Terme
Mit s[t/x] bezeichnen wir den Boolschen Term der entsteht, wenn man jedes Vorkommen von x in s durch den Term t ersetzt

s=(x^!y)v(!x) t=!yvz t'=x^z
s[t/x]=((!yvz)^!y)v(!(!yvz)
s[t'/x]=((x^z)^!y)v!(x^z)
s[t/z]=s
Syntaxbaum (mach mal wer)

Subtitutionstheorem: Seien s1=s2 äquivalente Terme, t ein weiterer Term, x eine Variable, dann gilt:
(1) t[s1/x] ≡ t[s2/x]
(2) s1[t/x] ≡ s2[t/x]

(!x^y)^zv!(xvy)
(a)≡((!x^y)^z)v(!x^y)   deMorgan+Doppelte Negation   (2)
(b)≡!x^y                Absorption                   (1)

(a) !(xv!y)≡!x^y t=((!x^y)^z)vu
        s1    s2   t[s1/u)≡t[s2/u]

(b) (x⋀z)⋁x ≡ x
        s1    s2

    t = ¬x⋀y
    s1[t/x] ≡ s2[t/x] (regel (2))

Vorlesung vom 01.11.2012

Konjunktive und disjunktive Normalformen

(KNF und DNF)
                 Auswertung
Boolesche Formeln ---------> Boolesche Funktionen
                  <---------
                      ?

Idee: Beispiel Antivalenz:
x1|x2|x1(antivalenz)x2
0 |0 |0
0 |1 |1
1 |0 |1
1 |1 |1

Aufgabe: Darstellung der Boolschen Formel
    Wann wird f(x1,x2)=1?
            ^
            =
            v
    Wenn (x1=1 und x2=0) oder (x1=0 und x2=1)
        t = (x1 ⋀ ¬x2)⋁(¬x1 ⋀ x2)
_______________________________________________
Wann wird f(x1,x2) = 0?
                ^
                =
                v
        s = (x1 ⋁ x2) ⋀(¬x1 ⋁ ¬x2)


Begriffe:                                                                          __

Ein Literal ist eine Variable oder eine negierte Variable (für ¬xi kann man auch x(mit strich drüber)i schreiben)
Ein minterm (maxterm) ist eine konjunktion von literalen (disjunktion von Lit)
Ist V_{n} = {x1,...xn} festgelegt , dann ist ein ein Minterm (Maxterm) vollständig, wenn jede Variale x: in dem term entweder als x(mit strich drüber)i oder als ¬xi auftaucht
Eine konjunktive (disjunktive) Normalform KNF(DNF) ist eine Konjunktion(Disjunktion)von Maxtermen (Mintermen)

Beispiele: x1^¬x3^x4 ist Minterm
             x1v¬x2vx3v¬x4 ist vollst. Maxterm über M4
             x1 und ¬x3 sind Max- und Minterme

    (x1^¬x3)v(x2^¬x4)vx3 ist DNF
    x1^¬x3^x4            ist KNF und DNF
     (unterstrichenend sind maxterme)
     der ganze "term" ist aber auch ein minterm

Satz: Jede Boolsche Funktion f: B^n->B ist durch eine DNF df und eine KNF kf repräsentierbar, durch

df = ⋁              (x1^{b1} ⋀ x2^{b2} ⋀    ⋀ xn^{bn})
(b1..bn)∈f^{-1}(1)

kf = ⋀               (x1^{¬b1} ⋁ x2^{¬b2}    ⋁ xn^{¬bn})
(b1..bn)∈f^{-1}(0)

wobei x^b = {x falls b=1}
            {¬x falls b=0}

Ausnahmen: Wenn f^{-1}()1 = ∅, dann df=0 und wenn f^{-1}(0) = ∅, dann kf=1

Anmerkung: die formeln df und kf aus dem satz nennt man die kanonische DNF bzw. KNF von f. Es kann wesentlich einfachere (kürzere) Darstellungen von f als KNF/DNF geben.

Beweisidee für df: Betrachte ein (b1,... bn) ∈ f^{-1}(1), dh f(b1,...bn)=!
Sei ω die entsprechende Belegung zu (b1,...,bn) ω=T^{-1}(b1,...bn), dh ω(x1)=b1... ,∪(x1)bn
Dann ist die Auswertung von x1^{b1}⋀ x2^{b2}⋀ ... ⋀ xn^{bn} unter ω gleich 1                       1   ⋀    1   ⋀ ... ⋀ 1 = 1

Für jede andere Belegung ω' ergibt die Auswertung
Das V sorgt dafür, dass df für
    f^{-1}(1)
alle (b1,...bn)∈f^{-1} den wert 1 bekommt.

Für jede Belegung eines (b1,...bn)∈f^{-1}(0) werden alle Minterme in df 0 und damit df selbst auch 0

Beispiel:
x1|x2|x3|f(x1,x2,x3)|Minterme(DNF)|Maxterme(KNF)
0 |0 |0 | 0        | ---------- | x1 ⋁ x2 ⋁ x3
0 |0 |1 | 1        | ¬x1 ⋀¬x2 ⋀x3| --------
0 |1 |0 | 0        | ---------- | x1⋁¬x2⋁x3
0 |1 |1 | 1        | ¬x1⋀x2⋀x3   | --------
1 |0 |0 | 1        | x1⋀¬x2⋀¬x3 | --------
1 |0 |1 | 1        | x1⋀¬x2⋀x3   | --------
1 |1 |0 | 0        | ---------   | ¬x1⋁¬x2⋁x3
1 |1 |1 | 1        | x1⋀x2⋀x3    | --------

WÜRFEL SKIZZE SIEHE SCRIPT SEITE 20

alternativ: KV-Diagramme

Def.: Ein geordnetes Paar ist ein 2 Objekten a,b zugeordneten Konstrukt (a,b) mit der folgenden Eigenschaft:
(a,b) = (c,bd) <=> a = c und b = d

Das Kartesische Produkt von Zwei Mengen A und B besteht aus allen geordneten Paaren (a,b) mit a€A und b€B.
AxB={(a,b)|a€A^b€B

es geht weiter im Pad Mafi Teil 2

Sonderzeichen: ∈, ∉, ≡, ∀, ∃, ∅, ⋂, ⋃, ⋀, ⋁, ¬, →, ↔, ↓, ⇒, ⇔, ⟼, ☇, √, ∤, |, ≥, ≤, ∑, ⊕, ≠, ∪, ⊂, ⊃, ⊆, ⊇, ○, Ā, Ē, Ū, Ō, ⚡, Ω, ɸ, ω, τ, Σ, ℕ, ℤ