Begriffe aus der Theoretischen Informatik (Teil I)
 (die man als Informatikstudent kennen sollte :-)

Klaus-Peter Neuendorf, 25. Februar 2000

Eine Möglichkeit die Begriffe und ihre Definitionen  nachzuschlagen, bietet auch das Logikskript (HTML (zip/pkzip gepackt) [1.4 MB]) in der neuen HTML-Version von Stefan Roch, welche auch eine Volltext-Suche im Offline Modus gestattet. 
(Meine lokale Kopie ist hier.)

Mein Vorschlag zur Nutzung dieses Materials beinhaltet folgende Schritte:

1. Drucke Dir die Begriffsliste mindestens 2-mal aus: 
	- Liste1  zur Kontrolle 
	- Liste2  mit Zwischenräumen zum Vervollständigen

2. Überprüfe anhand von Liste1, ob Du eine Vorstellung von der Bedeutung eines Begriffes hast. Wenn nicht, oder bei Unsicherheit nachschlagen und in Kurzform in Liste2 notieren.

3. Nenne, oder besser  notiere 1-2 Beispiele, die Dir sofort einfallen und überprüfe ihre Eigenschaften.

4. Gehe solange zu 2. bis Du nichts mehr nachschlagen brauchst!

Mengenlehre

Menge M

Element

Antinomie

Axiomatische Mengenlehre

Stufenkalkül

disjunkte Mengen

leere Mengen (∅^((n)))

Allmengen (E^((n)))

Potenzmenge  𝒫 (M)

geordnetes Paar

Kreuzprodukt

Relationale Strukturen

Inklusion

Relation (in und über M)

reflexiv

irreflexiv

symmetrisch

antisymmetrisch

asymmetrisch

transitiv

Äquivalenzrelation

Zerlegung

Hauptsatz über Äquivalenzrelationen (R  ⇔  (Subscript[𝔐, R]))

Halbordnung (refl., irrefl.)

Korrespondenzen (aus, auf, Verkettung, Inversion)
(verschiedene Darstellungen (0/1-Matrizen, Abb.))

reflexiv-transitive Hülle  <R>  einer Relation R über A

Hüllenoperator auf  𝒫 (A) (mit Endlichkeitssatz)

Abbildungen, injektive, surjektive, bijektive

Algebraische Strukturen

Mengenalgebra

Durchschnitt, Vereinigung, Komplement (Boolsche Operationen)

Absorptionsgesetze

Verband (distributiv, komplementär)

Verband der Äquivalenzrelationen (feiner- und gröber-Relation)

Boolsche Algebra

Dualitätstheorem der Mengenalgebra

Differenz, symmetrische Differenz

Halbgruppen, Gruppen, Ringe

Kongruenzrelationen

Natürliche Zahlen

endliche Mengen

unendliche Mengen

Kardinalzahlen

Wörter

Worthalbgruppe

Erzeugendensystem (freies)

freie Halbgruppe

Homomorphismus (Isomorphismus)

Induktive Definitionen und Beweise

Algebren

Kodierungstheorie

Relationen über Worthalbgruppen

Sprachen

Grammatiken (kontextfrei)

Ableitbarkeitsrelation

Übungstabelle zum Ausfüllen mit Eigenschaften und Operationen für Relationen   (Subscript[R, 1])  und  (Subscript[R, 2])   in  M

Fülle für gegebene Relationen (Subscript[R, 1])und (Subscript[R, 2]) in einer gegebenen Menge M, die folgende Tabelle aus! Dabei ist für Zeilen der Form (x) jeweils eine Menge als Lösung anzugeben, während für Zeilen der Form x) als Antwort auf die Frage nach dem Zutreffen der Eigenschaft ja bzw. nein einzutragen ist.

({{ , Eigenschaft,       (Subscript[R, 1])      ,       (Subscript[R, 2])      ,   (Subscript[R, 1])∘(Subscript[R, 2])   ,      (((Subscript[R, 1]))^(-1))     ,   (Subscript[R, 1])⋃(Subscript[R, 2])  ,   (Subscript[R, 1])⋂(Subscript[R, 2])  ,    (Subscript[R, 1])\[Cross](Subscript[R, 2])  }, {(a), Relation,  ,  ,  ,  ,  ,  ,  }, {(b), Definitionsbereich,  ,  ,  ,  ,  ,  ,  }, {(c), Bildbereich,  ,  ,  ,  ,  ,  ,  }, {d), von,  ,  ,  ,  ,  ,  ,  }, {e), auf,  ,  ,  ,  ,  ,  ,  }, {f), über,  ,  ,  ,  ,  ,  ,  }, {g), reflexiv,  ,  ,  ,  ,  ,  ,  }, {h), irreflexiv,  ,  ,  ,  ,  ,  ,  }, {i), transitiv,  ,  ,  ,  ,  ,  ,  }, {j), symmetrisch,  ,  ,  ,  ,  ,  ,  }, {k), antisymmetrisch,  ,  ,  ,  ,  ,  ,  }, {l), asymmetrisch,  ,  ,  ,  ,  ,  ,  }, {m), Äquivalenzrelation,  ,  ,  ,  ,  ,  ,  }, {(n), zugeh. Zerlegung,  ,  ,  ,  ,  ,  ,  }, {o), Halbordnung,  ,  ,  ,  ,  ,  ,  }, {p), Abbildung,  ,  ,  ,  ,  ,  ,  }, {q), injektiv,  ,  ,  ,  ,  ,  ,  }, {r), surjektiv,  ,  ,  ,  ,  ,  ,  }, {(s), reflexiv - transitive
Hülle,  ,  ,  ,  ,  ,  ,  }, {(t), zur trans .  Relation
geh. Halbordnung,  ,  ,  ,  ,  ,  ,  }, {(u), zu t)geh. Zerlegung,  ,  ,  ,  ,  ,  ,  }, {(v), Äquivalenzrela-
tions-Hülle,  ,  ,  ,  ,  ,  ,  }, {(w), zu v)geh. Zerlegung,  ,  ,  ,  ,  ,  ,  }})

Aussagenlogik

Aussagen
Aussagenfunktionen  
Wahrheitsfunktionen (extensionale)

Syntax des AK 
X Alphabet
AV Aussagenvariablen
ausd  Ausdrücke 
Vorrangregeln \((¬ \(\(,\)\(\(∧\)\(\(,\)\(\(∨\)\(\(,\)\(\(->\)\(\(,\)\(↔\)\)\)\)\)\)\)\))\)

Schaltalgebra
KANF
ANF
KNF
Elementarkonjunktion 
Fundamentalkonjunktionen
Implikanden 
Primimplikanden (wesentliche in Bezug auf ...)
optimale ANF

Semantik des AK 
Variablenbelegung β
Wert eines Ausdrucks H bei β
Modell einer Menge von Ausdrücken
von H repräsentierte Wahrheitsfunktion (Subscript[Φ, H])
Elementarkonjunktion
β erfüllt H
H ist erfüllbar
H ist (allgemein-)gültig
H ist kontradiktorisch
erf - Korrespondenz
X fol H - Korrespondenz des Folgerns
fl -Operator (Eigenschaften: Hüllenoperator,  Endlichkeitssatz)
ef - Menge von Ausdrücken
ag - Menge von Ausdrücken
kt - Menge von Ausdrücken
Ableitbarkeitstheorem und Deduktionstheorem für das Folgern

Logikkalküle
[X,A,S,F] (4 Eigenschaften sowie 3 Eigenschaften von F)
Bsp. Aussagenkalkül
semantisch (F (∅)  =  S) oder syntaktisch (F ((Subscript[S, 0]))  =  S) definierte Satzmenge
Kalkül heißt entscheidbar, ...

Aussagenlogisches Schließen
Schlußregeln (Rechtfertigung)
Ableiten mit Abtrennen und Einsetzen
aba
abe
ab
axa - Axiome
LINDENBAUMscher Ergänzungssatz
Semantische Äquivalenz von Ausdrücken
KKNF
Klauseln
Cut-Relation (Schnittregel)
Y ⊢ H
Widerspruchsfreiheit 
Vollständigkeit 
Nichtableitbarkeit
(semantisch, klassisch, syntaktisch)
Endlichkeitssätze
Dualitätstheoreme für Mengenterme

Beispiele für Fragen

Sprechen Sie über Wahrheitsfunktionen und Ausdrücke im AK:
((induktive) Definitionen, ausd, Belegung,  wert, Modell, (Subscript[Φ, H]), Repräsentantentheorem, Normalformen (optimale), Implikanden)

Vergleichen Sie Folgern und Ableiten im AK:
(induktive) Definitionen, fl, ab, Eigenschaften (fl(∅), Hülleneig.,  Endlichkeitsatz (Bew. für ab), Ableitbarkeits- und Deduktionstheorem),  syntaktische Charakterisierung des Folgerns  (axa)

Berechnungstheorie

Grundfragen der Berechnungstheorie:
Was ist ein Algorithmus?
Gibt es algorithmisch unlösbare Probleme?
Formalisierungen des Algorithmenbegriffes
Berechnungs- und Entscheidungsprobleme

Partiell-rekursive Funktionen

Primitiv-rekursive Funktionen

n-stellige zahlentheoretische Funktionen (totale und partielle)

ANF
  1. (Nachfolgerfunktion)
  2. (n-stellige Konstanten)
  3. (Argumentauswahl)

Operationen: Substitution, Primitive Rekursion, (Beschränkter Minimum-Operator)

PRM - primitiv-rekursive Funktionen

Die Peterfunktion (Eigenschaften und Bedeutung)

weitere Operation: Minimum-Operator

PREK - partiell-rekursive Funktionen

REK - allgemein-rekursive Funktionen

Turingmaschinen

Def. und Arbeitsweise von T = [X, Z, (Subscript[z, 0]), δ] mit B = {R, L, N, S}

TM - Turing-berechenbare Funktionen

Äquivalenz der Berechenbarkeitsbegriffe
Beweismethoden (TM-Makros und Gödelisierung normierter TM und ihrer Konfigurationen)

Kleenescher Darstellungssatz (Normalform partiell-rekursiver Funktionen)

Churchsche These

Nichtberechenbare totale Funktionen

Satz von Rice

Prädikatenlogik

Aussageformen
Individuenbereich I
Attribute über I
Funktionen über I
Quantoren
Prädikatenlogische Wahrheitsfunktionen: Om und Ex

Syntax des PK
Die Sprache
X - Alphabet aus 17 Zeichen
V - Menge der Zeichen für Individuenvariablen (Subscript[x, i])
P - Menge der Attributenzeichen (Prädikatensymbole) ((Subscript[A, i])^j)
F - Menge der Funktionszeichen ((Subscript[F, i])^j)
K - Menge der Individuenzeichen (Konstanten) (Subscript[a, i])
Terme:  (Subscript[a, i]), (Subscript[x, i]), ((Subscript[F, i])^j) (_,  ... , _)
AUSD - Menge der  Ausdrücke 
    prädikative: 	 (Subscript[T, 1]) = (Subscript[T, 2]) ,  ((Subscript[A, i])^j) (Subscript[T, 1]) ...  (Subscript[T, j])
    aussagenlogische: 	 ¬ H,  ((Subscript[H, 1])⋄(Subscript[H, 2])) 
    			 mit  \(\(⋄\)\(\ \)\(\(∈\)\(\ \)\({\(∧\)\(\(,\)\(\(∨\)\(\(,\)\(\(->\)\(\(,\)\(↔\)\)\)\)\)\)}\)\)\)
    prädikatenlogische:  Qx H, d.h. ∀ x H oder ∃ x H
Signatur Σ = [K, P, F] - Zeichen für Konstanten, Attribute und Funktionen 
x vollfrei in H
x quantifiziert in H an Stelle n  (H = (Subscript[Z, 1]) Qx H (Subscript[Z, 2]))
x gebunden in H an Stelle n
x frei in H an Stelle n
H ist abgeschlossen (Aussage)

Semantik des PK
Interpretation [I, g] einer Sprache mit der Signatur [K, P, F]
Belegung f über I
Termauswertung (Subscript[element, I, g]) (T, f)
Wert eines Ausdrucks in der Interpretation [I, g] bei der Belegung f 
	(Subscript[wert, I, g]) (H, f)
((Subscript[([f]), y])^i) Belegung f abgeändert bei (Subscript[x, i]) zu y

Erfüllbarkeit
H ∈ (Subscript[ef, I, g, f])		 H ∈ (Subscript[ef, I, g]) 		H ∈ (Subscript[ef, I])  	H ∈ ef

Gültigkeit
	H ∈ (Subscript[ag, I, g])  		H ∈ (Subscript[ag, I]) 		H ∈ ag

Für Aussagen (spielt Belegung f keine Rolle)
    H ist wahr in g über I  ( H ∈ (Subscript[ef, I, g]) )  ( H ∈ (Subscript[ag, I, g]) )
    H ist falsch in g über I  ( ¬ H ∈ (Subscript[ef, I, g]) )

H ∈ ag  gdw. ¬ H ∉ ef

Entscheidungsproblem des PK  
( Def. und Nachweis für im allgemeinen unentscheidbaren Fall )

Lösbare Fälle des Entscheidungsproblems

Klassenkalkül:  (Subscript[A, j]) x (Ausdrücke ohne ((Subscript[F, i])^j), (Subscript[a, i]), = , ((Subscript[A, i])^(j > 1)) also nur mit einstelligen Attributen und Variablen)

AL Erfüllbarkeit und Gültigkeit
    AE - Menge der AL einfachen Ausdrücke: 
\(\(\(	\)\(T\_1 = T\_2\)\)\), ((Subscript[A, i])^j) (Subscript[T, 1]) ...  (Subscript[T, j]), Qx H 
    ß :  AE → {W, 
            F} (aussagenlogische Belegung)
    H ∈  efa und H ∈ aga (Definition und Entscheidbarkeit)
    ef ⊂ efa und aga ⊂ ag (mit Beispielen)

Folgern und Ableiten im PK
    [g, f] ist Modell von X ⊆ AUSD  in I
    X (Subscript[fol, I]) H
    X fol H

(Subscript[fl, I]) (X) ( Operator hat Hülleneigenschaften, erfüllt das Ableitbarkeits- und das Deduktionstheorem, erhält Allgemeingültigkeit, erfüllt den Endlichkeitssatz)

X abl H (induktive Definition) (7 Regeln: modus ponens, vordere Generalisierung, hintere G., vordere Partikularisierung, hintere P., gebundene Umbenennung, Termeinsetzung)

X abla H (nur mit modus ponens abtrennen)

Eigenschaften von ab und aba 
    \(ab \((∅)\) = \(aba \((∅)\) = ∅\)\)
    Hülleneigenschaften, Endlichkeitssatz, Ableitbarkeitstheorem
    Deduktionstheorem nicht
    ab (ag) = aba (ag) = ag

X abl((Subscript[H, 1]) -> ((Subscript[H, 2]) -> (Subscript[H, 1])))  und  X abl H und (Subscript[x, j]) kommt vor in H, so 
     X abl∀(Subscript[x, j]) H

Schwaches Deduktionstheorem
5  Voraussetzungen (Formen von Ausdrücken alle ableitbar aus X), dann
Wenn (X ⋃ {(Subscript[H, 1])}) abl (Subscript[H, 2]), so X abl (Gen ((Subscript[H, 1])) ->  (Subscript[H, 2]))

fl(X)=ab(ag ⋃ X) (syntaktisches Folgern)

Axiommengen:	 AX  =  AXA  ⋃  AXI
	ag=ab(AX)

PK Schlußregeln
Widerlegen im PK
Pränexe Normalform
Literale und Klauseln
Horn-Klauseln
Herbrand-Modell
Unifikation 
Resolution (Resolvente, rechte und linke Faktoren)
(PROLOG)