Digtech3_2.pdf

(460 KB) Pobierz
Grundlagen der Booleschen Algebra
Digitaltechnik
Digitaltechnik
Andreas König
Professur Technische Informatik
Fakultät Informatik
Technische Universität Chemnitz
Wintersemester 2001/2002
© Andreas König Folie 3-1
Grundlagen der Booleschen Algebra
Digitaltechnik
Rekapitulierung zu Kapitel 2
Grundlagen der Informationsrepräsentation in digitalen Systemen
Verschiedene Kodierungen optimiert für Randbedingungen, wie:
•
•
•
•
•
Kompaktheit
Fehlersicherheit
Übertragbarkeit
Speicherbarkeit
Kompatibilität zu den Anforderungen des Nutzers (MMK)
Schwerpunkt:
Zahlendarstellung, -konversion und Arithmetik
Darstellung prinzipieller Algorithmen
Vorbereitung für die Umsetzung in Recheneinheiten durch konkrete
(optimierte) Schaltwerke
© Andreas König Folie 3-2
Grundlagen der Booleschen Algebra
Digitaltechnik
Vorlesungsgliederung:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Einführung
Kodierung und Arithmetik
Grundlagen der Booleschen Algebra
Entwurf zweistufiger kombinatorischer Logik
Zieltechnologien und Technologieanpassung
Zeitliches Verhalten kombinatorischer Schaltnetze
Entwurf sequentieller Schaltwerke
Funktionsblöcke digitaler Rechner und Systeme
Entwurf von Systemen der Digitaltechnik
Ausblick
© Andreas König Folie 3-3
Grundlagen der Booleschen Algebra
Digitaltechnik
Kapitelgliederung:
3.
Grundlagen der Booleschen Algebra
3.1 Algebraische Strukturen
3.2 Schaltalgebra
3.3 Boolesche Elementaroperationen
3.4 Schaltfunktionen
3.5 Hauptsatz der Schaltalgebra
3.6 Basissysteme
3.7 Entwicklungssatz der Schaltalgebra
3.8 Unvollständig definierte Funktionen
3.9 Negative Logik
3.10 Weitere Beschreibungsformen
© Andreas König Folie 3-4
Algebraische Strukturen
Grundlagen der Booleschen Algebra
Digitaltechnik
Die Schaltwerke der Digitaltechnik unterliegen den Regeln der
sogenannten
Schaltalgebra
Diese soll im folgenden motiviert und dann im Detail vorgestellt und
angewendet werden
Eine detailliertere und profundere Darstellung des mathematischen
Hintergrunds ist z.B. in [Lipp 99], Kap. 5 zu finden
Weiterhin: Vorlesung
Diskrete Mathematik
Im vorhergehenden Kapitel wurden implizit Mengen (z.B. Zeichen-
vorrat) eingeführt
Auf
Mengen
M und zugehöriger Potenzmenge P(M) sind Operationen,
wie
Schnittmenge
∩
oder
Vereinigungsmenge
∪
definiert, die
bestimmten Regeln genügen
Ein solches Gebilde aus Operanden und Regeln wird
algebraische
Struktur
genannt bzw. für Mengen als Operanden
Mengenalgebra:
MA
=
[
P
(
M
)
,
∩
,
∪
,
C
M
,
∅
,
M
]
© Andreas König Folie 3-5
Algebraische Strukturen
Grundlagen der Booleschen Algebra
Digitaltechnik
Eine Vielzahl algebraischer Strukturen angebar, deren Eigenschaften
sich nach Definition von Operanden und Operatoren unterscheiden
Viele dieser Algebren rückführbar auf wenige Grundtypen
Interpretationen gegebener Grundtypen
Zentrale Rolle: Algebren die auf die Arbeiten von G. Boole (1815-1864)
zurückgehen (Boolesche
Algebren)
Eine Boolesche Algebra:
BA
=
K
,
T
,
⊥
, ,
O
,
I
[
]
Menge K mit zwei zweistelligen Verknüpfungen T und
⊥,
einstelliger
Relation
und zwei universellen Schranken O und I wobei für die
Elemente aus K eine Reihe von Regeln gelten
Satz 3.1:
Ist P(M) die Potenzmenge einer beliebigen Menge M, so ist
das Verknüpfungsgebilde [P(M),∩,
∪,C
M
,
∅,M]
stets eine Boolesche
Algebra
Satz 3.2:
Bei jeder Booleschen Algebra gilt für die Menge K: |K|=2
n
(n=1,2,....)
© Andreas König Folie 3-6
Algebraische Strukturen
Grundlagen der Booleschen Algebra
Digitaltechnik
Notation von Mengenoperationen in tabellarischer Form:
∪
∅
M
∅
∅
M
M
M
M
∩
∅
M
∅
∅
∅
M
∅
M
C
M
∅
M
M
∅
Abtraktion von einer speziellen Mengeninterpretation ( |P(M)=2|,
∅=0,
M=1 sowie
∩
= T und
∪
=
⊥):
⊥
0
1
0
0
1
1
1
1
T
0
1
0
0
0
1
0
1
0
1
1
0
Nächste
Boolesche Algebra
ist vierwertig (|K|= 2
2
=4)
© Andreas König Folie 3-7
Algebraische Strukturen
Grundlagen der Booleschen Algebra
Digitaltechnik
Bei einer
Booleschen Algebra
gilt allgemein das
Dualitätsprinzip:
• Wird in einem Satz unter alleiniger Verwendung der Operatoren
T,
⊥
und
eine Vertauschung von T mit
⊥
bzw. umgekehrt vorgenommen so
erhält man den sog. Dualen Satz
• Enthält der Satz die neutralen Elemente O und I so müssen auch
diese vertauscht werden
• Wichtige Aussage für Beweisführungen und Anwendung
Boolescher
Algebren
Begründung von Regeln auf axiomatische Weise von großer
mathematischer Bedeutung
Huntington erreichte dies für Boolesche Algebren
Für eine Grundmenge K und beliebige Elemente a, b, c aus K stellte er
ein System aus fünf Axiomen auf (Huntingtonsche
Axiome)
© Andreas König Folie 3-8
Algebraische Strukturen
Grundlagen der Booleschen Algebra
Digitaltechnik
H1:
Abgeschlossenheit
a,b
∈K
aTb
∈
K
a
⊥
b
∈
K
Das Ergebnis der Anwendung der Operatoren T,
⊥
ist stets in K.
H2:
Kommutativ-Gesetz
a,b
∈K
aTb=bTa
a
⊥
b=b
⊥
a
Die Reihenfolge der Operanden ist vertauschbar, die Operatoren T,
⊥
sind
kommutativ.
H3:
Distributiv-Gesetz
a,b,c
∈K
(a
⊥
b) T c = (a T c )
⊥
(b T c )
(a T b)
⊥
c = (a
⊥
c ) T (b
⊥
c )
Jeder der beiden Operatoren T,
⊥
distribuiert über den anderen.
© Andreas König Folie 3-9
Algebraische Strukturen
Grundlagen der Booleschen Algebra
Digitaltechnik
Existenz eines neutralen Elements
a, I
∈K
O, a
∈K
ITa=a
O
⊥
a=a
Zu jedem Operator T,
⊥
existiert ein neutrales Element, so dass jedes
beliebige Element aus der Menge K bezüglich des Operators T,
⊥
unverändert belassen wird.
H5:
Komplement
a,k
∈K
aTk=O
a
⊥
k=I
Zu jedem Element a aus der Menge K gibt es ein Element
a
= k ebenfalls
aus K, das komplementär zu a ist. Die Verknüpfung von k mit a durch T,
⊥
führt zum neutralen Element O, I.
H4:
© Andreas König Folie 3-10

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin