Snl Boolesche Algebra

Front 1

Boolesche Algebra als Körper

Back 1

Boolesche Algebra ist das Rechnen in der Restklasse ℤ₂ und da 2 eine Primzahl ist, ist (ℤ₂, +, · ) ein (kommutativer) Körper.

Aus der Additions- bzw. Multiplikationstabelle geht hervor, welche booleschen Operationen den zahlenmässigen Operationen entsprechen:
+ Addition ↔ XOR ⊕
· Multiplikation ↔ AND ·

Der Körper Körper (ℤ₂, +, · ) wird gleichwertig mit den Symbolen der booleschen Algebra beschrieben:
( { 0, 1 }, ⊕, · )

Die Verwendung des Malzeichens · für das boolesche AND entspricht exakt der zahlenmässigen Multiplikation in ℤ₂.

Aber Achtung: Das beliebte Pluszeichen + wird in der booleschen Algebra für das OR verwendet (häufiger benötigt als XOR, welches der zahlenmässigen Addition in ℤ₂ entspräche). Somit ist ( { 0, 1 }, +, · ) KEIN Körper, denn es gibt kein inverses Element zu + (OR) für Wahrheitswert 1.

Front 2

Eine n-dimensionale boolesche Funktion in m Variablen.

Back 2

m und n ∈ N beliebig, aber beide ≠ 0

m Input Bits (die Input Variablen)
n Output Bits (die Output Variablen)

Wird als Wahrheitstabelle dargestellt.
Für m = 3 (Input Bits x) und n = 2 (Output Bits y) bedeutet das z.B:
y₁ = f₁(x₁, x₂, x₃)
y₂ = f₂(x₁, x₂, x₃)

Das gäbe eine Wahrheitstabelle mit 5 Spalten:
x₁ x₂ x₃ y₁ y₂

Front 3

Back 3

AND

z wird 1 wenn:
x = 1 ⋀ y = 1

Front 4

Back 4

OR
"mindestens eine 1"

z wird 1 wenn:
x = 1 ⋁ y = 1

Front 5

Back 5

NOT

z wird 1 wenn:
¬(x = 1)

Front 6

Back 6

NAND

z wird 1 wenn:
¬(x = 1 ⋀ y = 1)

Front 7

Back 7

NOR

z wird 1 wenn:
¬(x = 1 ⋁ y = 1)

Front 8

Back 8

XOR
"genau eine 1"

z wird 1 wenn:
(x = 1 ⋀ y = 0) ⋁ (x = 0 ⋀ y = 1)

Front 9

Back 9

XNOR

z wird 1 wenn:
(x = 0 ⋀ y = 0) ⋁ (x = 1 ⋀ y = 1)

Front 10

product term

Back 10

x · y

Variables combined with boolean AND.

Front 11

sum of products (SOP) expression

Back 11

x · y + a · b · c + f · g · h

A set of product terms combined with boolean OR.

Front 12

sum term

Back 12

x + y

Variables combined with boolean OR.

Front 13

product of sums (POS) expression

Back 13

(x + y) · (a + b + c) · (f + g + h)

A set of sum terms combined with boolean AND.

Front 14

Minterm

Back 14

"Invert the 0 values, combine with AND."
Produce 1 for one specific set of input variables.

A product term that has a truth table with exactly one 1.
(It produces the minimum number of 1 values).

The table shows the minterms for the specific values of the input variables x, y and z on the same line.
For example:
The minterm x · y' · z produces 1 exactly and only for the input values (0, 1, 0). No other combination of input values results in 1.

Front 15

Minterm-Darstellung einer Funktion F(x, y, z)

Back 15

1) Minterm bestimmen für jede Kombination von Input Variablen, die 1 geben soll.

2) Alle diese Minterme mit OR verknüpfen (canonical sum of products expression).

Fürs Beispiel im Bild ist die Minterm-Darstellung:
x' · y · z' + x · y · z'

Front 16

Maxterm

Back 16

"Invert the 1 values, combine with OR."
Produce 0 for one specific set of input variables.

A sum term that has a truth table with exactly one 0.
(It produces the maximum number of 1 values).

The table shows the maxterms for the specific values of the input variables x, y and z on the same line.
For example:
The maxterm x + y' + z' produces 0 exactly and only for the input values (0, 1, 1). No other combination of input values results in 0.

Front 17

Maxterm-Darstellung einer Funktion F(x, y, z)

Back 17

1) Maxterm bestimmen für jede Kombination von Input Variablen, die 0 geben soll.

2) Alle diese Maxterme mit AND verknüpfen (canonical product of sums expression).

Fürs Beispiel im Bild ist die Maxterm-Darstellung:
(x + y' + z) · (x + y' + z') · (x' + y + z')

Front 18

Nutzen von Minterm- und Maxterm-Darstellung

Back 18

Sowohl die Minterm- als auch die Maxterm-Darstellung erlauben es, jede beliebige boolesche Funktion aufzubauen, nur mit AND, OR und NOT-Funktionen.

Beides sind logisch gleichwertige Alternativen. Man wählt natürlich diejenige Variante, die kürzer wird. Dies ist aber noch nicht unbedingt die einfachste Darstellung der Schaltung. Mit booleschen Gesetzen kann man möglicherweise weiter vereinfachen.

Front 19

Diese Funktion nur mit Hilfe von OR und NOT darstellen:

z = x AND y

Back 19

Trick: Doppelte Negation

Front 20

Diese Funktion nur mit Hilfe von AND und NOT darstellen:

z = x OR y

Back 20

Trick: Doppelte Negation

Front 21

Wieviele boolesche Funktionen gibt es bei 3 Input Bits und n Output Bits?

Back 21

2^3 Kombinationen von Input Bits, also 8.

2^n Kombinationen von Output Bits.

Die 2^n Output-Bitmuster stehen bei jedem der 8 Input-Bitmuster zur Wahl. Das erste Input-Bitmuster kann auf 2^n verschiedene Output-Bitmuster gemapped werden. Danach das zweite Input-Bitmuster ebenso, etc. Somit (2^n)^8.

Es gibt also soviele Funktionen:
(2^n)^8 = 2^(8·n)

Front 22

Boolesches Dualitätsprinzip

Back 22

Boolesches Dualitätsprinzip: Falls man in einer gültigen booleschen Formel
▪ alle AND durch OR bzw. alle · durch +
▪ alle OR durch AND bzw. alle + durch ·
▪ alle 0 durch 1 und
▪ alle 1 durch 0
ersetzt, erhält man wieder eine gültige boolesche Identität.

Front 23

Assoziativgesetz
1. Form (Primärform)

Back 23

Front 24

Assoziativgesetz
2. Form (Dualform)

Back 24

Front 25

Kommutativgesetz
1. Form (Primärform)

Back 25

Front 26

Kommutativgesetz
2. Form (Dualform)

Back 26

Front 27

Distributivgesetz
1. Form (Primärform)

Back 27

Front 28

Distributivgesetz
2. Form (Dualform)

** WICHTIG **

Back 28

Front 29

De Morgan
1. Form (Primärform)

Back 29

Front 30

De Morgan
2. Form (Dualform)

Back 30

Front 31

schwache Absorption
1. Form (Primärform)

Back 31

Front 32

schwache Absorption
2. Form (Dualform)

Back 32

Front 33

starke Absorption
1. Form (Primärform)

** WICHTIG **

Back 33

Front 34

starke Absorption
2. Form (Dualform)

** WICHTIG **

Back 34

Front 35

Involution
1. Form (Primärform)

Back 35

Primärform und Sekundärform sind bei Involution identisch.

Front 36

Involution
2. Form (Dualform)

Back 36

Sekundärform und Primärform sind bei Involution identisch.

Front 37

Idempotenzgesetz
1. Form (Primärform)

Back 37

Front 38

Idempotenzgesetz
2. Form (Dualform)

Back 38

Front 39

Gesetz vom Komplement
1. Form (Primärform)

Back 39

Front 40

Gesetz vom Komplement
2. Form (Dualform)

Back 40

Front 41

Gesetz der Redundanz
1. Form (Primärform)

** WICHTIG **

Back 41

Front 42

Gesetz der Redundanz
2. Form (Dualform)

Back 42

Front 43

Konsensgesetz
1. Form (Primärform)

** WICHTIG **

Back 43

Beweis:

Wenn xy + x'z (die rechte Seite) 1 ist, dann ist egal ob yz da ist oder wegfällt. Also dafür schon mal OK.

Wenn xy + x'z (die rechte Seite) 0 ist, dann muss auch yz zu 0 werden, damit es auf der rechten Seite wegfallen kann. Zwei Fälle:
a) x = 1 → y muss 0 sein, damit xy + x'z = 0. Daraus folgt auch yz = 0.
b) x = 0 → z muss 0 sein, dami xy + x'z = 0. Daraus folgt auch yz = 0.

Front 44

Konsensgesetz
2. Form (Dualform)

Back 44

Front 45

Neutrales Element
1. Form (Primärform)

Back 45

Front 46

Neutrales Element
2. Form (Dualform)

Back 46

Front 47

Minterm Expansion

F(a,b,c) = a · b + c

(Convert a minimal SOP expression into a canoncial SOP expression)

Back 47

Each of the products that form the sum must be expanded so that it contains all variables.

ab
= ab1
= ab(c + c')
= abc + abc'

c
= c(a + a')
= ac + a'c
= ac(b + b') + a'c(b + b')
= abc + ab'c + a'bc + a'b'c

Finally:
F(a,b,c) = ab + c
= abc + abc' + abc + ab'c + a'bc + a'b'c
= abc + abc' + ab'c + a'bc + a'b'c
[equal products joined with + are redundant, so one of the two abc terms is removed from the sum]

Front 48

Maxterm Expansion

F(a,b,c) = (a + b)c

(Convert a minimal POS expression into a canoncial POS expression)

Back 48

Each of the sums that form the product must be expanded so that it contains all variables.

(a + b)
= (a + b + c'c)
= (a + b + c')(a + b + c)

c
= c + a'a
= (a' + c)(a + c)
= (a' + bb' + c)(a + c + bb')
= (a' + b' + c)(a' + b + c)(a + b' + c)(a + b + c)

Finally:
F(a,b,c) = (a + b)c
= (a + b + c')(a + b + c) (a' + b' + c)(a' + b + c)(a + b' + c)(a + b + c)
= (a + b + c)(a' + b + c)(a + b' + c)(a + b + c')(a' + b' + c)
[equal sums joined with · are redundant, so one of the two a + b + c terms is removed from the product]

Front 49

Minimize from minterm form.

y = a'bc + ab'c' + ab'c + abc' + abc

Back 49

Look for differences in only one variable (= boolean adjacency). E.g. abc' is adjacent to abc and the two terms can be combined as ab(c' + c) using the distributive rule.

a'bc + ab'c' + ab'c + abc' + abc
= a'bc + ab'(c' + c) + ab(c' + c)
= a'bc + ab' + ab
= a'bc + a(b' + b)
= a'bc + a
= bc + a

Front 50

MInimize from maxterm form.

y = (a + b + c)(a + b + c')(a + b' + c)

Back 50

Look for differences in only one variable.

(a + b + c)(a + b + c')(a + b' + c)
= (a + b + cc')(a + b' + c)
= (a + b)(a + b' + c)
= (a + b)((a + c) + b')
= (a + b)(a + c) + (a + b)b'
= a + bc + ab + bb'
= a + ab + bc
= a(1 + b) + bc
= a + bc

Dualform Distributivgesetz:
(a + b)(a + c) = a + bc

Front 51

Vereinfache

ab' + b

Back 51

ab' + b = a + b

Gesetz der Redundanz

Front 52

Vereinfache

(a + b)(b + a')

Back 52

(a + b)(b + a')
= ab + aa' + bb + ba'
= ab + 0 + b + ba'
= ab + a'b + 0 + b
= (a + a')b + b
= 1b + b
= b + b
= b

Front 53

Vereinfache

(a + b)'

Back 53

(a + b)'
= a'b'

De Morgan (Primärform)

Front 54

Vereinfache

(ab)'

Back 54

a' + b'

De Morgan (Dualform)

Front 55

Vereinfache

f + fh' + g'f

Back 55

f + fh' + g'f
= f(1 + h' + g')
= f(1)
= f

Front 56

Vereinfache

(f + g'h')(g + h)

Back 56

(f + g'h')(g + h)
= f(g + h) + g'h'(g+h)
= f(g + h) + g'h'g + g'h'h
= f(g + h) + 0 + 0
= f(g + h)

Front 57

Vereinfache

(f + g)(f' + g' + h')

Back 57

(f + g)(f' + g' + h')
= ff' + fg' + fh' + gf' + gg' + gh'
= 0 + fg' + fh' + gf' + 0 + gh'
= fg' + fh' + gf' + gh'
= fg' + fh' + f'g + gh'
= fh' + f'g + h'g + fg'
[ xy + x'z + yz = xy + x'z → Konsensgesetz]
= fh' + f'g + fg'

Front 58

Vereinfache

f + fg' + fh + fg + gh

Back 58

f + fg' + fh + fg + gh
= f + gh

Das alleinstehende f absorbiert alle f, die in AND Verknüpfungen stehen. Gesetz der starken Absorption (Primärform).