Universität Ulm, Fakultät für Informatik, Abtl. Künstliche Intelligenz up: weitere Lehrveranstaltungen

Maschinelles Beweisen mit PVS

Unterlagen zur Vorlesung im WS'04/05


 Termin

 

Vorlesung:
Do. 14:15 - 15:45 Uhr in O 27 / 2203
Prof. Dr. F. W. von Henke, O 27 / 450
Sprechstunde: nach der Vorlesung oder n.V.

Übungen:
An Stelle von Übungen wird parallel zur Vorlesung ein Praktikum mit dem Spezifikations- und Verifikationssystem PVS angeboten.
Ansprechpartner:
Holger Pfeifer, O 27 / 446
Sprechstunde: n.V.

 Inhalt der Vorlesung

 

Die Vorlesung beschäftigt sich mit Methoden des logischen Schließens und ihrer Unterstützung in einem maschinellen Beweissystem. Im Zentrum der Vorlesung stehen Anwendungsbeispiele sowohl aus dem Software- als auch dem Hardware-Bereich, sowie deren Modellierung und Analyse im Spezifikations- und Verifikationssystem PVS.

Insbesondere werden folgende Themen behandelt:
  • Grundlegende Begriffe formaler deduktiver Systeme
  • Beweismethoden für Prädikatenlogik
  • Induktive Strukturen und Induktionsbeweise
  • Beweisen in Logik höherer Ordnung
  • Simplifikation, Entscheidungsprozeduren, BDDs

Die Übungen zur Vorlesung finden in Form eines Praktikums (mit Praktikumsschein) statt. Die Vorlesung vermittelt die konzeptionellen Grundlagen, die dann im Praktikum anhand von konkreten Anwendungsbeispielen vertieft werden. Hörern der Vorlesung wird zur Vertiefung und praktischen Anwendung der erlernten Modellierungs- und Analysemethoden die Teilnahme am Praktikum empfohlen.

 Vorlesungsfolien

 
1. Einführendes     [PDF]
2. Spezifikation in PVS (I)        3. Sequenzen-Kalkül     [PDF]
4. Spezifikation in PVS (II)      5. Lambda-Kalkül und Logik höherer Stufe     [PDF]
6. Rekursive Funktionen und Induktion     [PDF]
7. Abstrakte Datentypen     [PDF]
8. Das Typsystem von PVS     (Teil 1) [PDF], (Teil 2) [PDF]
6a. Induktion - Nachtrag     [PDF]
      Einschub: Fallstudie Compiler-Verifikation     [PDF]

 Übungs- und Praktikumaufgaben

  Anleitung zu PVS

Übungsaufgaben

Lösungsvorschläge

Die Lösungsvorschläge werden als PVS-Dump-Dateien bereitgestellt. Diese müssen innerhalb von PVS mit dem Kommando M-x undump-pvs-files ausgepackt werden.

 Materialien

 
PVS zum Download:
Ausführliche Anleitung und Installationshinweise finden sich auf der Seite zum PVS Mirror in Ulm.
Hinweis: Die angebotenen tar-Archive sind zwischen 1 MB und 13 MB groß.

Eine detailierte Dokumentation ist z. Zt. nur für eine Vorgänger-Version verfügbar, enthält aber alle wichtigen Informationen. Erhältlich als pvs-2.4-doc.tgz (komprimiertes tar-Archiv, 2.8 MB).

Dateien zur PVS-Demo: in einem leeren Verzeichnis abspeichern und dort PVS aufrufen.

 Technisches

  Typ: Vorlesung im Hauptstudium (2V)
  Zuordnung:  Theoretische und mathematische Methoden der Informatik, Praktische und Angewandte Informatik (Kernfach)
Künstliche Intelligenz (Vertiefungsgebiet)


Abtl. KI Startseite Hilfe Mail an Webmaster H. Pfeifer - geändert: 08.12.04