5.0. Grundlagen der Logik - Bool'sche Aussagenlogik und de'Morgan'sche Theoreme history menue Letztmalig dran rumgefummelt: 26.01.19 08:45:00

Eine Hauptaufgabe der mathematischen Logik ist die Untersuchung des formalen Denkens und Schließens mit Hilfe mathematischer Methoden, die z. B. der Algebra und der Algorithmentheorie entnommen sind.
Diese ursprünglich aus der Philosophie stammende Aufgabe ist jedoch nicht ihre einzige; die mathematische Logik umfasst heute eine Vielzahl von Fragestellungen und Anwendungen auf den verschiedensten Gebieten, z. B. in den Naturwissenschaften, in der Schaltalgebra, in der Theorie informationsverarbeitender Systeme, in der Linguistik und in verschiedenen Disziplinen der Gesellschaftswissenschaften wie Philosophie, Rechtswissenschaft und Ethik.
Entscheidende Impulse für die Entwicklung der mathematischen Logik ergaben sich aus der Situation der Mathematik am Ausgang des 19. Jahrhunderts. Diese hatte bis dahin eine Fülle einzelner Resultate gesammelt und schon einen hohen Abstraktionsgrad erreicht, ohne dass über den Inhalt der intuitiv verwendeten Grundbegriffe, z. B. des Mengenbegriffs und des logischen Schließens, ausreichende Klarheit bestand. Neben dem Bedürfnis nach einer zweifelsfreien Begründung des Mengenbegriffs ergab sich zum ersten Male die Notwendigkeit einer Einsicht in das, was Logik und logische Deduktion eigentlich bedeuten.
0. Bool'sche Algebra und deren technische Umsetzung
1. Klemmverhalten logischer Schaltungen
2. Allgemeines zur Logik und Kombinatorik
3. De Morgan'sche Theoreme
4. Schaltungslogik - Torschaltungen
5. Verwandte Themen
6. Übungsaufgaben

die Elektronikseiten

Logo des Bool'schen Aussagenkalküls

begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-)

Wissen für Fortgeschrittene der Informatik

... das ZIP-Archiv komplett auspacken und die .EXE-Datei starten

logische Schaltsymbole

elektrische Werte für die logischen Pegel L und H

der Aufbau von logischen Schaltungen folgt der Bool'schen Algebra und kann nach den de Morgan'schen Theoremen verkürzt werden

Bool'sche Algebra

Eingänge von Logikschaltungen dürfen parallel geschalten werden, wobei lediglich die mögliche Stromabgabe der Quelle zu beachten ist - in der TTL-Technik spricht man von TTL-Lasten, wobei der typische Wert 10 ist (Leitungstreiber erreichen höhere Werte), d. h. an einem Ausgang dürfen max. zehn Eingänge parallel angeschalten werden
Ausgänge von Logikgattern werden typischerweise nicht parallel geschalten - nur besondere Bauelemente lassen dies zu (Tri-State-Ausgänge und Open Colector) und es liegt auch nur selten eine wirkliche Notwendigkeit dazu vor (Bildschirmansteuerungen mit RGB-Signalen sind aber solche Ausnahmefälle)
Linkliste
Verzeichnis der Abkürzungen und Sonderzeichen  
Allgemeines  
n! = 1 - 2 ... n, Fakultät von n
Logik  
0,1 Wahrheitswerte, Dualziffern
f, w Wahrheitswerte
ä oder ¬a Negation (von a)
a ۸  b Konjunktion, logisches UND
a ۷ b Disjunktion, logisches ODER
Mengen  
x e A x ist Element von A
{ } leere Menge
{x E (x)} Menge der Objekte x mit der Eigenschaft E (x)
A s B A ist Teilmenge von B
A 2 B A ist Obermenge von B
   

 A v B Vereinigung der Mengen A und B
A n B Durchschnitt, Schnittmenge der Mengen A und B
A \ B Restmenge, Differenzmenge der Mengen A und B, A ohne B
Ax B Kreuzprodukt, Kartesisches Produkt, Menge aller Paare mit Komponenten aus A bzw. B
AB Produkt der Mengen A und B
A' i-te Potenz der Menge A
A* Vereinigung aller endlichen Potenzen von ;A Formale Sprachen
V* Menge aller Worte mit Zeichen aus V einschließlich des leeren Wortes
V+ = V*\{E}, Menge aller Worte mit Zeichen aus V ohne das leere Wort E leeres Wort
G = (VN, VT, P, S), Grammatik
V,, Menge der nichtterminalen Zeichen oder Symbole
VT Menge der terminalen Zeichen oder Symbole
P -- V x V, Menge der Regeln oder Produktionen
S Startzeichen oder Startsymbol
V = V,, v VT, Menge der Zeichen, Variablen
v -+ w direkte Ableitung
v =~ w Ableitung
L (G) von der Grammatik G erzeugte Sprache
Automaten
A Endlicher Automat K Kellerautomat T Turingmaschine HT Haltentscheidende Turingmaschine zu T
U Universelle Turingmaschine X Eingabealphabet
S Speicher- oder Kelleralphabet
so c S, Kellerleersymbol
B 2 X, Bandalphabet
b c- B, Leerzeichen, blank Y Ausgabealphabet
c- leeres Wort
Z Zustandsmenge zo EZ, Anfangszustand ZE g Z, Endzustandsmenge S Überführungsfunktion S* erweiterte Überführungsfunktion 1~ Ausgabefunktion
I~* erweiterte Ausgabefunktion
L, L,, L2, ... Sprache, language
L (A) vom Endlichen Automaten A akzeptierte Sprache
L (T) von der Turingmaschine T akzeptierte Sprache


0. Bool'sche Algebra und deren technische Umsetzung history menue scroll up
George Boole - englischer Mathematiker

Hier nun muss notwendigerweise der ganze mathematische Randkimskrams aufgeführt werden, der aus tausenden Formeln besteht und von keinem im Normalfall wirklich gelesen. Wenn man allerdings ein Projekt in diesem Sinne am Backen hat, dann sieht die Sache ganz anders aus.

Prinzipien der klassischen Aussagenlogik. Als Aussagen bezeichnet man bestimmte sprachliche Gebilde, die zur Beschreibung und Mitteilung von Sachverhalten dienen. Die klassische Aussagenlogik geht von zwei Voraussetzungen aus.
Nach dem Prinzip der Zweiwertigkeit ist jede Aussage entweder wahr oder falsch. Der hierbei verwendete, auf ARISTOTELES zurückgehende Wahrheitsbegriff bezeichnet eine Aussage dann als wahr, wenn der in ihr behauptete Sachverhalt zutrifft. Das Prinzip der Zweiwertigkeit enthält zwei Prinzipien: 1. Das Prinzip vom ausgeschlossenen Dritten, nach dem jede Aussage wahr oder falsch ist; und 2. das Prinzip vom ausgeschlossenen Widerspruch, nach dem es keine Aussage gibt, die sowohl wahr als auch falsch ist. Die Klasse aller Aussagen zerfällt damit in zwei Teilklassen, die durch die Symbole 1 (wahr) und 0 (falsch) bezeichnet und Wahrheitswerte genannt werden.

Mit Hilfe sprachlicher Partikel, z. B. „nicht", „und", „oder", lassen sich gegebene Aussagen zu komplizierteren Aussagen zusammensetzen. Nach dem zweiten Grundprinzip, dem Extensionalitätsprinzip, ist der Wahrheitswert einer zusammengesetzten Aussage ausschließlich durch die Wahrheitswerte ihrer Komponenten bestimmt und hängt nicht von deren Sinn ab. Infolgedessen lassen sich derartige Verknüpfungen als Funktionen deuten, die n-Tupeln von Wahrheitswerten wieder Wahrheitswerte zuordnen.
Die für die Aussagenlogik gebräuchlichsten Verknüpfungspartikel, ihre Bezeichnung und die ihnen jeweils entsprechende Wahrheitsfunktion sind
Verknüpfungs- Schreibweise Benennung zugeordnete partikel in Funktoren Wahrheitsfunktion
nicht --i Negation non
und A Konjunktion et
oder v Alternative vel
wenn ..., so -> Implikation seq
genau dann ..., wenn H Äquivalenz aeq
Die Wahrheitsfunktionen, p non p p q et (p, q) vel (p, q) seq (p, q) aeq (p, q) deren Argumente und Funktionswerte Wahrheitswerte sind, lassen sich am einfachsten durch ihre Funktionstafeln Darstellung von Funktionen beschreiben

1 0 1 1 1 1 1 1
- 0 1 1 0 0 1 0 0
  - 0 1 0 1 1 0
- 0 0 0 0 1 1
Diese Festlegungen entsprechen nicht ganz der umgangssprachlichen Bedeutung der zugehörigen Partikel, z. B. ist nach dieser Festlegung die Aussage wahr »wenn 2 - 2 = 5, so gibt es auf dem Mond Schnee«, denn sie ist eine Implikation der Form p -. q, in der p, nämlich »2 - 2 = 5«, und auch q, nämlich »auf dem Mond gibt es Schnee«, den Wahrheitswert 0 haben, für die nach der Funktionstafel gilt seq (0, 0) = 1. Diese Festlegungen entsprechen genau dem Gebrauch, der sich in der Mathematik historisch herausgebildet und bewährt hat.
Formuliert man z. B. »wenn a < b, so ist 2a < 26«, so ist dies in der Arithmetik der natürlichen Zahlen wahr. Daher müssen sich auch beim Einsetzen irgendwelcher natürlichen Zahlen für a, b daraus wahre Aussagen ergeben, d. h., es muss z. B. »wenn 4 < l, so 2 - 4 < 2 - l« eine wahre Aussage sein. Akzeptiert man aber diese letzte Aussage als wahr, muss man wegen des Extensionalitätsprinzips auch »wenn 2 - 2 = 5, so gibt es auf dem Mond Schnee« als wahr akzeptieren.
Die Aufgabe der Aussagenlogik besteht in der mathematischen Untersuchung dieser inhaltlich gegebenen Begriffe, die zu diesem Zweck im Rahmen eines Kalküls, des Aussagenkalküls, formalisiert werden. Für seinen Aufbau wird ausgegangen von einer Menge von Grundsymbolen, bei denen folgende Sorten zu unterscheiden sind:
(1) Variable für Aussagen: Pl , p2, ..., p, q, r, s, ... ;
(2) Funktoren --1, A, v, die in dieser Reihenfolge die Funktionen non, et, vel, seq, aeq bezeichnen
(3) technische Zeichen, z. B.
Die Grundobjekte des Aussagenkalküls, die Ausdrücke, werden nun mittels einer induktiven Definition aus der Menge aller Zeichenreihen ausgesondert:
Definition der Ausdrücke
(1) Die Variablen pl, p2, ..., p, q, r, s, ... sind Ausdrücke.
(2) Wenn H, G Ausdrücke sind, so auch -i H, (H A G), (H v G), (H ~ G), (H H G). (3) Nur die vermittels (1) und (2) gebildeten Zeichenreihen sind Ausdrücke.
Diese Definition macht es möglich, von einer vorgelegten Zeichenreihe in endlich vielen Schritten zu entscheiden, ob sie ein Ausdruck ist oder nicht.
Beispiel 1: ((p -. q) A (r v s)) und ((p H q) -. (--i q ~ --1 p)) sind Ausdrücke; (p A -. q) ist kein Ausdruck.
Entsprechend wie für die Zeichen -}- und - für die Operationen Addition und Multiplikation wird für die Funktoren festgelegt, dass in der Reihenfolge --i, A, v, -., H jeder folgende Funktor stärker trennt als jeder vorangehende, z. B. ist p A q ~ r eindeutig als (p A q) -. r zu lesen. Zur Verdeutlichung kann durch einen Punkt unter einem Funktor angegeben werden, dass dieser Funktor stärker trennt als die übrigen gleichbezeichneten (vgl. Beispiel 5, 6, 7).
 

 


1. Allgemeines zur Logik und Kombinatorik history menue scroll up
Hier nun muss notwendigerweise der ganze mathematische Randkrimskrams aufgeführt werden, der aus tausenden Formeln besteht und von keinem im Normalfall wirklich gelesen. Wenn man allerdings ein Projekt in diesem Sinne am Backen hat, dann sieht die Sache ganz anders aus.
Klemmverhalten logischer Schaltungen mit zwei Eingängen und einem Ausgang:
  Eingangspegel Eingangspegel Eingangspegel Eingangspegel    
x1 oder A L L H H    
x2 oder B L H L H Bezeichnung NAND-Logik
y0 L L L L Binärer Durchgang 0
y1 L L L H AND Lösung
y2 L L H L Lösung
y3 L L H H Lösung
y4 L H L L
y5 L H L H
y6 L H H L Antivalenz
y7 L H H H OR-Schaltung
y8 H L L L NOR-Schaltung
y9 H L L H Äqivalenz
y10 H L H L
y11 H L H H Lösung
y12 H H L L
y13 H H L H Implikation
y14 H H H L NAND-Schaltung
y15 H H H H Binärer Durchgang 1

2. Allgemeines zur Logik und Kombinatorik history menue scroll up
Grundsatz logischer Schaltungen: gleicher Input erzeugt immer gleichen Output! Logik ist kein mathematisches Problem sondern eine Frage der Definition und Zuordnung!
Definition logischer Schaltungen:

Logische Schaltungen realisieren logische Verknüpfungen! Das Signal an den Ausgängen folgt immer der Signalbelegung am Eingang und gehorcht dabei den internen Verknüpfungen (Kombinationen). Der Informationsfluss geht nur vom Eingang zum Ausgang und nicht umgekehrt. Dabei wirkt das Ausgangssignal auch nicht auf das Eingangssignal zurück und der zeitlich vorangegangene Zustand der Schaltung spielt keine Rolle - er fließt nicht in das neue Signalverhalten der Schaltung mit ein.
Ein- und Ausgangssignale können nur 0 oder 1 sein, wobei Ausgänge nicht parallel geschalten werden dürfen - es sei denn, sie weisen ein Tri-State-Schaltverhalten auf (Ausnahme).

allgemeines Blockschaltbild logischer Schaltungen

Hier und jetzt folgen die einigen wenigen und wirklich wichtigen Sätze der Logik - beherzige sie einfach - sie sind einfach:
zur Entwicklung logischer Gesamtaussagen werden jeweils nur die wahren oder falschen Aussagen herangezogen und entsprechend logisch verknüpft
alle Einzelaussagen werden UND bzw. ODER-verknüpft - sie müssen ja in ihrer Gesamtheit eine wahre Aussage ergeben - alle wahren Aussagen gemeinsam werden UND bzw. ODER-verknüpft
mittels der de Morgan'schen Theoreme lassen sich Aussagen verkürzen
Schaltungstechnische Realisierung ist aber nur möglich, wenn die Aussage nicht einen Widerspruch in sich enthält, d. h. die logischen Bedingungen dürfen nicht so gestellt sein, das überhaupt keine Aussage möglich ist
mehrere wahre logische Aussagen werden logisch ODER verknüpft
Logikschaltungen sind der technische Ansatz zu dem, was wir Künstliche Intelligenz nennen - 's gibt natürlich auch künstliche Dummheit!!! ;-)
... und so wird eine Logik entwickelt

3. De Morgan'sche Theoreme history menue scroll up
Das nunmehr folgende sind Geheimwaffen der Logikinterpretation und gleichzeitig eigentlich die Kürzungsregeln der Logik. Sie sind klein, es sind nur wenige (also eigentlich nur zwei), aber in denen steckt das Potential zu Ermittlung des IQ's.

Die de Morganschen Gesetze der Aussagenlogik lauten:

NICHT (A UND B) = NICHT A ODER NICHT B

NICHT (A ODER B) = NICHT A UND NICHT B.

de Morgan'schen Theoreme


4. Schaltungslogik - Torschaltungen history menue scroll up
Logische Gatter sind die elementaren Grundbausteine digitaler Schaltungen und Systeme. Sie steuern den Signalfluss durch das gesamte digitale System. Die Bezeichnung Gatter (Tor) weist darauf hin, dass sie durch die am Eingang anliegenden Signale geöffnet und geschlossen werden können und auf diese Weise entweder die Information weiterleiten oder ihre Weiterleitung verhindern. Wir betrachten in diesem Buch ausschließlich Elemente der zweiwertigen (binären) Logik.
Mit nur einem Gattertyp, der eine Verknüpfungsform und eine Negation enthält (z. B. NAND- oder NOR-Gatter) lassen sich alle digitalen Steuerungsfunktionen, d. h. sowohl Kombinations- als auch Folgeschaltungen realisieren. Selbst der umfangreichste Digitalrechner lässt sich (theoretisch) aus einem oder aus wenigen immer wiederkehrenden Grundgattern aufbauen. Aus Aufwandsgründen werden in der Praxis jedoch überwiegend hoch- und höchstintegrierte Schaltkreise (RAMs, ROMS, ALU, Multiplizierer u. a. m.) verwendet. Aus logischer Sicht realisiert jedes elementare Grundgatter (z. B. UND, ODER, NAND, NOR, Negator) eine kombinatorische Verknüpfung. Durch Zusammenschalten mehrerer Grundgatter und Anwenden des Prinzips der Rückkopplung entstehen Folgeschaltungen.
Die logische Funktion von Gattern (d. h. die logische Abhängigkeit zwischen den Ausgangs- und den Eingangssignalen) wird mit Hilfe der Schaltalgebra (Boolesche Algebra) beschrieben. Die Gleichungen der Booleschen Algebra sind darüber hinaus für den Entwurf digitaler Schaltungen und Systeme sowie für deren Vereinfachung (Minimierung der Anzahl von Gattern) von großer Bedeutung.
Im vorliegenden Abschnitt geben wir einen Überblick über allgemeine Eigenschaften und Kenngrößen logischer Grundgatter. Auf die statische und dynamische Berechnung von Transistorstufen und von Gattern wollen wir verzichten, da dies in zunehmendem Maße Anliegen des Schaltkreisherstellers ist.
In digitalen Schaltkreisen werden die beiden logischen Signalwerte 0 und 1 nahezu ausnahmslos durch zwei unterschiedliche Spannungspegel (H-Pegel und L-Pegel) dargestellt (darüber hinaus muss zwischen statischen und dynamischen Logiksystemen unterschieden werden.
Die beiden Pegelwerte (exakter: Pegelbereiche) bezeichnet man mit HIGH (H)-Pegel: Pegelwert ist näher bei + 5Volt. LOW (L)-Pegel: Pegelwert ist näher bei - 0 Volt.
Diese allgemeine Bezeichnung der beiden Pegelwerte hat den Vorteil, dass die konkreten (und bei den zahlreichen Schaltkreisfamilien unterschiedlichen) Pegelwerte hierbei aus Gründen der Allgemeingültigkeit umgangen werden können.

Schaltalgebra

Kanonischen Normalformen

Karnaugh-Veitch-Tafeln

Rechenmaschinenmodelle

Logikschaltungen mit Relais - die hohe Schule

Prof. Heinz Zemanek

Torschaltungs-Logo

ZUSE-Bleche

ZUSEUM in Bautzen

Konrad Zuse

Kombinatorik-Projekt

Kombinatorik

Das Kombinatorik-Projekt

Schaltalgebra

Kanonischen Normalformen

AND-Logik

OR-Logik

Negator-Logik

NAND-Logik

NOR-Logik

Äquivalenz-Logik

Antivalenz-Logik

 

 


5. Verwandte Themen history menue scroll up
Aussagenlogik, Logik und Kombinatorik, Kanonische Normalformen - aber auch die Gesetze zur logischen Schaltungsentwicklung sowie auch ihre Vereinfachung spielen alle in diese Feld der Grundlagen. Hier einige Tipps, um diese näher zu beschnuppern, oder daran vollkommen zu verzweifeln.

Praktischer Entwurf von Logikschaltungen

das "Elektronik-Projekt"

 

logische Grundfunktionen

Logikfunktionen und technologische Fertigungsverfahren

Transistor-Kennlinienfeld

Logikaufgaben

Logiktabelle mit 5 Eingängen und 4 Ausgängen

ROM-Logik

logische Arrays

EPROM-Logik

Mikrocontroller


6. Weblinks history menue scroll up
Also los - machen wir Aussagenlogik und versuchen wir, deduktiv zu folgern: das ist dann eigentlich schon ein Spezialgebiet der Kombinatorik.
http://www.tfh-berlin.de/~msr/pdf-files/VL4.PDF
 
 
 

7. Übungsaufgaben history menue scroll up
Also los - machen wir Aussagenlogik und versuchen wir, deduktiv zu folgern: das ist dann eigentlich schon ein Spezialgebiet der Kombinatorik.
 
 
 
 


zur Hauptseite
© Samuel-von-Pufendorf-Gymnasium Flöha © Frank Rost im Januar 1996

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehemn ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)