Bool'sche Algebra

 A v B Vereinigung der Mengen A und B
A ∪ 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

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.

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).
 

allgemeines Blockschaltbild logischer Schaltungen

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