Aktuelle Literatur wie Artikel aus Fachzeitschriften, dem Handbook of Satisfiability, etc. wird in der Vorlesung bekannt gegeben.
1) Aussagen- und Praedikatenlogik:
a) Syntax, Normalformen und Normalformtransformationen,
b) Semantik, Evaluierung einer gegebenen Formel bzgl. einer
gegebenen Interpretation, Konzept der logischen Folgerbarkeit
(entailment) auch unter Theorien, Ueberfuehrung von Validity,
Entailment, Equivalence und Satisfiablity ineinander,
Beweisverfahren (Tableau, Sequenzsysteme oder NK anwenden
koennen)
2) Einfache Beweise fuehren:
a) Prinzip des Induktionsbeweis (+ einfache Beispiele)
b) Einfache Beispiele zur Abschaetzung von Laufzeiten und
Speicherbedarf (Beispiel: Zeige, dass die Zeitkomplexitaet der
Breitensuche bei fixem Verzweigungsgrad b und Tiefe d in O(b^d)
liegt. Erwartet wird ein formal korrekter Beweis
inkl. Erklaerungen wie O-Notation.)
Die Vorkenntnisse entstammen der LVAen Theoretischer Informatik und
Logik (TIL), den formalen Methoden, AlgoDat und einfuehrenden
Mathematikveranstaltungen. Fuer einen Teil der Logikkenntnisse
koennen u.U. das TIL Skriptum und die Folien von Block Satisfiability (SAT)
unter http://www.logic.at/lvas/fminf/ nuetzlich sein.