Einführung in die Logikverifikation erster Ordnung

9

Ich versuche mir verschiedene Ansätze zur Softwareüberprüfung beizubringen. Ich habe einige Artikel gelesen. Soweit ich gelernt habe, verwendet die Aussagenlogik mit Zeit im Allgemeinen die Modellprüfung mit SAT-Lösern (in laufenden - reaktiven Systemen), aber was ist mit der Logik erster Ordnung mit Zeit? Verwendet es Theorembeweiser? Oder kann es auch SAT verwenden?

Hinweise auf Bücher oder Artikel für Anfänger in dieser Angelegenheit werden sehr geschätzt.

FELIPE N.
quelle
2
Zunächst einmal willkommen bei CS: SE. Obwohl ich kein Experte in diesem Bereich bin, scheinen Sie mehrere Themen gleichzeitig zu behandeln und viele Löcher zu hinterlassen. Mach dir keine Sorgen; Das mache ich die ganze Zeit. Werfen Sie einen Blick auf Software-Verifizierung, dann Formale Verifizierung, dann Modellprüfung und formale Software-Verifizierung: Modellprüfung und Theoremprüfung
Guy Coder

Antworten:

9

Die Logik erster Ordnung ist unentscheidbar, daher hilft die SAT-Lösung nicht wirklich. Es gibt jedoch Techniken zur begrenzten Modellprüfung von Formeln erster Ordnung. Dies bedeutet, dass nur eine feste Anzahl von Objekten berücksichtigt werden kann, wenn versucht wird, festzustellen, ob die Formel wahr oder falsch ist. Dies ist natürlich nicht vollständig, aber wenn ein Gegenbeispiel gefunden wird, ist es wirklich ein Gegenbeispiel.

Das Tool Alloy ist ein Tool, mit dem Modelle in Logik erster Ordnung beschrieben werden können (obwohl die Oberflächensyntax auf relational beschriebenen Modellen basiert) und die begrenzte Modellprüfung verwendet, um Lösungen zu finden. Unter der Haube wird ein SAT-Löser verwendet. Eine Legierungserweiterung ermöglicht Modelle mit zeitlichem Charakter, obwohl sie technisch keine zeitliche Logik unterstützt.

Wenn Sie beispielsweise die Programmkorrektheit weiter untersuchen möchten, können Sie sich die Tools zur Programmüberprüfung ansehen. Diese basieren im Allgemeinen auf der Hoare-Logik (zum Nachdenken über Vor- und Nachbedingungen), möglicherweise erweitert um die Trennungslogik (zum Nachdenken über Haufen). Diese Logiken sind im Allgemeinen unentscheidbar, daher ist ein gewisses Maß an Interaktion zwischen dem Menschen und dem Verifizierungswerkzeug erforderlich. Einige Beispielwerkzeuge sind:

Dave Clarke
quelle
10

Nachdem ich Ihre Frage gelesen hatte, konnte ich nur sehen und hatte genug Wissen, um die Themen miteinander zu verknüpfen, indem ich eine Reihe von Artikeln auf hoher Ebene gab, die einen Drilldown von der Softwareüberprüfung durchführten und schließlich versuchten, Modellprüfung und Theoremprüfung zu vereinen. Hoffentlich hat mein Kommentar das getan:

Schauen Sie sich Software-Verifikation, dann Formale Verifikation, dann Modellprüfung und Formale Software-Verifikation an: Modellprüfung und Theoremprüfung

Dave hat eine gute Antwort gegeben, für die ich dem ersten Teil der Frage nicht viel mehr gerecht werden kann als Dave, da ich auch neu darin bin.

Da dies Ihre erste Frage auf einer SE- Site ist, habe ich keine Antwort, sondern einen Kommentar gegeben, weil eine Antwort hier nicht nur eine Reihe von Links sein kann, sondern eine schriftliche Antwort geben und Links zur Unterstützung der Antwort verwenden muss. also ein Kommentar statt einer Antwort.

In Bezug auf:

Hinweise auf Bücher oder Artikel für Anfänger in dieser Angelegenheit werden sehr geschätzt.

Bücher, die ich vorschlagen und verwenden würde, sind:

Gegenwärtig kann ich nicht mehr auf Theorembeweise eingehen, weil ich immer noch die Vor- und Nachteile und Unterschiede jedes einzelnen lerne, aber diejenigen, auf die ich mich konzentriere, sind

  • HOL Light wegen des Buches von John Harrison.
  • Coq, weil es auf der Konstruktionsrechnung basiert
  • Isabelle, weil es auf der Vereinigung höherer Ordnung basiert.

    Diese Proof-Assistenten verfügen normalerweise auch über Bücher, sind aktuell, beliebt, Open Source, werden gepflegt und haben aktive Support-Communities.

Hinweis: Ich habe worldcat.org verwendet, um auf die Bücher zu verweisen, aber Sie können sie mithilfe der Look-Inside-Funktion von Amazon überprüfen.

Guy Coder
quelle
Um viele Änderungen an der Antwort zu vermeiden, werde ich hinzugefügte Informationen als Kommentare ablegen und sie in Zukunft in die Antwort einrollen. Für den Versuch, die vielen Ähnlichkeiten und Unterschiede zwischen Beweisassistenten zu klären. Google für Freek Wiedijk; Ich finde seine Papiere sehr nützlich.
Guy Coder
Vielen vielen Dank für Ihre ausführliche und gründliche Antwort. Zum Hinzufügen Ihrer Kommentare zu Büchern und zum Bereitstellen eines Links zum kostenlosen Buch. Auch hier kann ich Ihnen nicht genug danken :-)
FELIPE N.