BLATT   >   Grundlagen   >   Digitales Arbeitsmaterialien  |  Grundlagen  |  ÖH-Wahlen  |  Statistiken  |  Unirecht  
    ▸ Übersichten       ▸ Astronomie       ▸ C-Library       ▸ Digitales       ▸ Mathematik       ▸ Periodensystem
Übersichten
    • Größenvorsätze
    • SI-Basisgrößen
    • abgeleitete Größen
    • Konstanten
    • sonstige Einheiten
    • Greek Chars
    • Einheitskonten
    • Funktionsgrafik
    • Wellenformen
    • Zeichensatz

Astronomie
    • Astrophysik
    • Sonnensystem
    • Sternenklassen

C-Library
    • math.h
    • stdio.h
    • stdlib.h
    • string.h
    • time.h

Digitales
    • Aussagelogik
    • Flip-Flops
    • Decoder

Mathematik
    • Algebra
    • Geometrie
    • Trigonometrie
    • Differenzieren
    • Integrieren

Periodensystem
    • Übersicht
    • alphabetisch
    • Aggregatzustand
    • Metall-Eigenschaft
    • Säure-Eigenschaft

Wörterbücher
Aussage-Logik

Ein logischer Ausdruck in der binären Mathematik besteht aus boolschen Variablen, die durch einen Funktor (AND, OR, NOT, ...) zu einer Aussageform gebildet werden. Durch einsetzen von Werten wird die Aussageform zur Aussage. Eine boolsche Variable, wie auch das Ergebnis einer logischen Verknüpfung kann nur zwei Zustände { 0,1 } annehmen.

Beispiel:

   F(A,B) = A and B

     'A' und 'B' sind die boolschen Variablen
     'and' ist der Funktor
     Die Gleichung ist die Aussageform
     Wird bspw. A=1 und B=0 gesetzt, so ergibt sich die Aussage 0 (= Ergebnis der Gleichung)

Es können natürlich auch mehrere Variablen miteinander Verknüpft werden (A and B and C). Da eine Variable nur zwei Zustände annehmen kann, ergeben sich daraus insgesamt 2n mögliche Eingangswerte (bei drei Variablen 23 = 8). Da jede Funktion durch ein Abarbeiten von Verknüpfung aus jeweils zwei Variablen gelöst werden kann, kommt der Verknüpfung aus zwei Variablen eine besondere Beudtung zu.

Wir definieren:

    kanonisches Quadrupel:
    F(1,1), F(1,0), F(0,1), F(0,0)

Beispiele:

Wahrheitstafel für die Konjunktion (and)

Die Konjunktion ist erfüllt (1) wenn sowohl A als auch B erfüllt sind.
Sie wird auch als logisches Produkt bezeichnet.

F(A,B)ABAussage
F(1,1)111
F(1,0)100
F(0,1)010
F(0,0)000

Das kanonisches Quadrupel lautet: 1,0,0,0

Wahrheitstafel für die Disjunktion (or)

Die Disjunktion ist erfüllt (1) wenn zumindest eine Variable erfüllt ist.
Sie wird auch als logische Addition bezeichnet.

F(A,B)ABAussage
F(1,1)111
F(1,0)101
F(0,1)011
F(0,0)000

Das kanonisches Quadrupel lautet: 1,1,1,0

Wahrheitstafel für die Antivalenz (eor)

Die Antivalenz ist erfüllt (1) wenn entweder A oder B erfüllt ist.
Sie wird auch als 'ausschließendes Oder' bezeichnet.

F(A,B)ABAussage
F(1,1)110
F(1,0)101
F(0,1)011
F(0,0)000

Das kanonisches Quadrupel lautet: 0,1,1,0

Weiters gibt es auch eine wichtige Funktion mit nur einer Variable – die Negation, die auch als 'Komplement' bezeichnet wird. Bei dieser Funktion ist das Ergebnis der andere Wahrheitswert.

Wahrheitstafel für die Negation (not)

F(A)AAussage
F(1)10
F(0)01

A =1100  Im Überblick:
  Alle Verknüpfungen von zwei Variablen
B =1010
Nr.ErgebnisFunktionBezeichnung
 00000F(A,B) = 0Konstanz
 10001F(A,B) = not A and not BNOR, Weder-noch
 20010F(A,B) = not A and BInhibition
 30011F(A,B) = not ANegation
 40100F(A,B) = A and not BInhibition
 50101F(A,B) = not BNegation
 60110F(A,B) = A and not B or not A and BEOR, Antivalenz
 70111F(A,B) = not A or not BNAND
 81000F(A,B) = A and BAND, Konjunktion
 91001F(A,B) = A and B or not A and not BÄQ, Äquivalenz
101010F(A,B) = BIdentität
111011F(A,B) = not A or BImplikation
121100F(A,B) = AIdentität
131101F(A,B) = A or not B
141110F(A,B) = A or BOR, Disjunktion
151111F(A,B) = 1Konstanz

Wie aus der Tabelle ersichtlich ist, gibt es auch Funktionen die nur eine Variable (Nr. 3, 5, 10, 12) bzw. keine Variable (Nr. 0, 15) betreffen. Von diesen sechs Triviallösungen ist nur die schon oben beschriebene Negation (Nr. 3, Nr. 5) von Bedeutung.

Die logischen Rechengesetze

Kommutatives Gesetz

A or B  =  B or A
A and B  =  B and A
A äq B  =  B äq A

Assoziatives Gesetz

A or (B or C)  =  (A or B) or C  =  A or B or C
A and (B and C)  =  (A and B) and C  =  A and B and C
A äq (B äq C)  =  (A äq B) äq C  =  A äq B äq C

Distributives Gesetz

A and (B or C)  =  A and B or A and C
A or B and C  =  (A or B) and (A or C)

triviale Sonderfälle

A or not A  = 1      A oder sein Gegenteil trifft immer zu
A and not A  = 0      A und sein Gegenteil kann nie gleichzeitig zutreffen
not not A  = A      Das Gegenteil vom Gegenteil von A (doppelte Verneinung)
A and A  = A      
A or A  = A      

De-Morgan Theorem

not (A or B)  =  not A and not B
not (A or B or C)  =  not A and not B and not C
usw.  =  usw.
not (A and B)  =  not A or not B
not (A and B and C)  =  not A or not B or not C
usw.  =  usw.

Normalform

Vollkonjunktion

k
Kk = ^xv
n
v=0
Volldisjunktion

k
Dk = Vxv
n
v=0

Von einer Vollkonjunktion wird gesprochen, wenn alle Eingangsvariablen – entweder negiert oder nicht-negiert – konjunktiv (and) miteinander verknüpft sind. Eine Volldisjunktion ist die entsprechende disjunktive (or) Verknüpfung. Für beide gilt, dass die Anzahl der Verknüpfungsmöglichkeiten bei 2k liegt.

Durch eine AND-Verknüpfung der Elemente von Volldisjunktion ergibt sich die konjunktive Normalform.

Beispiel für eine konjunktive Normalform

FKNF = (A or B or not C)   and   (not A or B or C)

Durch eine OR-Verknüpfung der Elemente von Vollkonjunktion ergibt sich die disjunktive Normalform.

Beispiel für eine disjunktive Normalform

FDNF = (A and B and not C)   or   (not A and B and C)

Karnaugh-Tafel

Eine Vereinfachung von Schaltungen ergibt sich aus der Anwendung der disjunktiven Normalform mit Karnaugh-Tafeln.

Eine Karnaugh-Tafel für vier Eingangsvariablen (A,B,C,D) hat folgende Form:

not C and not Dnot C and D          C and D          C and not D
not A and not BK0K1K3K2
not A and BK4K5K7K6
     A and BK12K13K15K14
     A and not BK8K9K11K10

Die Variablen sind in der Tafel nach dem Gray-Code angeordnet, d.h., dass sich von einer Zeile bzw. Spalte zur nächsten, nur eine Variable ändert. Karnaugh-Tafel können auch mehr als vier Variablen haben – es muss nur eine gerade Anzahl an Varibalen sein. Dabei gilt, dass die Hälfte der Variablen in den Spalten, die andere in den Zeilen steht.

Beispiel

gegeben ist folgende Wahrheitstafel:
(Primzahlen eines 4-Bit unsigned Integers)

DCBAF(A,B,C,D)
00000
00010
00101
00111
01000
01011
01100
01111
10000
10010
10100
10111
11000
11011
11100
11110

nun wird die Wahrheitstafel in die Karnaugh-Tafel eingetragen:

not C and not Dnot C and D          C and D          C and not D
not A and not B0000
not A and B1000
     A and B1101
     A and not B0011

Jetzt müssen nebeneinander stehende Gruppen einer geraden Anzahl von '1'-Werten zusammengefasst werden. Für die '1'-Werte in der ersten Spalte gilt (B and not C and not D) sowohl für die Variable A=0 wie auch für A=1 – diese Verknüpfung ist als unabhängig von der Variable A. für die anderen Zusammenfassungen muss nur analog vorgegangen werden. In diesem Beispiel erhält man folgende vier Verknüpfungen:

1.)   B and not C and not D
2.)   A and B and not C
3.)   A and C and not D
4.)   A and not B and C

Werden diese noch OR verknüpft erhält man das Endergebnis:

Erg = (B and not C and not D) or
        (A and B and not C) or
        (A and C and not D) or
        (A and not B and C)


Schaltsymbole

neualtusx1x2y
AND
Konjunktion
0
0
1
1
0
1
0
1
0
0
0
1
OR
Disjunktion
0
0
1
1
0
1
0
1
0
1
1
1
NOT
Negation
0
0
1
1
 1
1
0
0
NAND
Antikonjunktion
0
0
1
1
0
1
0
1
1
1
1
0
NOR
Antidisjunktion
0
0
1
1
0
1
0
1
1
0
0
0
XOR
Antivalenz
0
0
1
1
0
1
0
1
0
1
1
0
EQU
Äquivalenz
0
0
1
1
0
1
0
1
1
0
0
1