Mehrdeutigkeit und Logik

17

In der Automatentheorie (endliche Automaten, Pushdown-Automaten, ...) und in der Komplexität gibt es den Begriff "Mehrdeutigkeit". Ein Automat ist mehrdeutig, wenn es ein Wort mit mindestens zwei verschiedenen Annahmeläufen gibt. Eine Maschine ist k -ambiguous wenn für jedes Wort w von der Maschine akzeptiert es höchstens sind k verschiedene Läufe zu akzeptieren w .wkwkw

Dieser Begriff wird auch für kontextfreie Grammatiken definiert: Eine Grammatik ist mehrdeutig, wenn ein Wort existiert, das auf zwei verschiedene Arten abgeleitet werden kann.

Es ist auch bekannt, dass viele Sprachen eine schöne logische Charakterisierung gegenüber endlichen Modellen haben. (Wenn eine Sprache regulär ist, gibt es eine monadische Formel zweiter Ordnung ϕ über Wörtern, so dass jedes Wort w von L ein Modell von ϕ ist , ähnlich NP, wenn es den Formeln zweiter Ordnung entspricht, in denen Quantifikatoren zweiter Ordnung existieren.)LϕwLϕ

Daher ist meine Frage an den Rändern der beiden Bereiche: Gibt es ein Ergebnis oder sogar eine kanonische Definition der "Mehrdeutigkeit" von Formeln einer gegebenen Logik?

Ich kann mir einige Definitionen vorstellen:

  • ist nicht mehrdeutig, wenn höchstens ein x existiert, so dass ϕ ( x ) gilt und ϕ ( x ) nicht mehrdeutig ist. xϕ(x)xϕ(x)ϕ(x)
  • wäre mehrdeutig, wenn es ein Modell von ϕ 0 und ϕ 1 gibt , oder wenn ϕ i mehrdeutig ist. ϕ0ϕ1ϕ0ϕ1ϕi
  • Eine SAT-Formel wäre nicht mehrdeutig, wenn es höchstens eine korrekte Zuordnung gibt.

Daher frage ich mich, ob es ein bekannter Begriff ist, ansonsten könnte es interessant sein, zu diesem Thema zu forschen. Wenn der Begriff bekannt ist, kann mir jemand Stichwörter geben, mit denen ich nach Informationen in dieser Angelegenheit suchen kann (weil "logische Ambiguität" viele unabhängige Ergebnisse liefert), oder Referenzen zu Büchern / PDFs / Artikeln?

Arthur MILCHIOR
quelle

Antworten:

11

Regeln in einer Grammatik und Folgerungsregeln in der Logik können beide als Produktionsregeln betrachtet werden, die uns "neues Zeug" von "bekanntem Zeug" geben. So wie es viele Möglichkeiten gibt, ein Wort in Bezug auf eine Grammatik zu produzieren (oder zu analysieren), kann es auch viele Möglichkeiten geben, eine logische Formel zu produzieren (oder zu beweisen). Diese Analogie kann weiter gezogen werden. Beispielsweise lassen bestimmte logische Systeme normale Formen von Beweisen zu. Ebenso lassen bestimmte Grammatiken kanonische Analysebäume zu.

Ich würde also sagen, Ihre Beispiele aus der Logik gehen in die falsche Richtung. Die richtige Analogie ist

"Baum analysieren": "Wort" = "Beweis": "logische Formel"

Tatsächlich kann eine hinreichend allgemeine Art von Grammatik typische logische Folgerungsregeln ausdrücken, so dass die grammatisch korrekten Wörter genau die beweisbaren Formeln sind. In diesem Fall ist die Parse - Bäume tatsächlich sein die Beweise.

In der entgegengesetzten Richtung kann jede Grammatik als ein System von Axiomen (Terminals) und Inferenzregeln (Produktionen) ausgedrückt werden, wenn wir gewillt sind, an sehr allgemeine Inferenzregeln zu denken (die nicht unbedingt einen traditionellen logischen Charakter haben). Und noch einmal werden wir sehen, dass ein Beweis dasselbe ist wie ein Analysebaum.

Andrej Bauer
quelle
Ich habe nicht wirklich über Beweise nachgedacht. Ich bin eher an (endliche) Modelltheorien gewöhnt. Wir müssen herausfinden, welche Mengen Modelle einer Formel sind und welche nicht. (Insbesondere für eine Formel ist die Komplexität zu ermitteln, ob eine Menge ein Modell ist oder nicht, und für beweisbare Formeln, also Tautologien, ist die Komplexität 0 (1), da alle Mengen Modelle sind). Aber vielen Dank für Ihre Antwort.
Arthur MILCHIOR
2
Nun, um Analogie hinzuzufügen: Modelltheorie ist Logik, was Semantik für Sprachen ist. Die Modelltheorie weist logischen Theorien Bedeutung zu, während die Semantik den Sprachen Bedeutung zuweist. Manchmal ist es am besten, Äpfel und Orangen nicht zu mischen, auch wenn Sie daran gewöhnt sind.
Andrej Bauer
7

Nur zwei Bemerkungen. Ich hoffe sie helfen.

Die Standarddefinitionen der Semantik einer Logik und der Wahrheit folgen Tarskis Darstellung, wobei die Formelstruktur eingeführt wird. Eine andere Möglichkeit besteht darin, spielbasierte Semantik zu geben, wie von Hintikka vorgeschlagen. Wahrheit und Erfüllbarkeit werden alle in Bezug auf Strategien in einem Spiel definiert. Für Formeln erster Ordnung kann man nachweisen, dass eine Formel unter Tarskis Begriff wahr ist, und zwar nur dann, wenn es im Hintikka-Spiel eine Gewinnstrategie gibt.

Um Ihre Frage zu formalisieren, kann man sich fragen, ob das Spiel mehrere Strategien zulässt. Es gibt auch die interessante Frage, ob die Strategien deterministisch sein sollten. Hintikka verlangte von ihnen, deterministisch zu sein. Der Beweis, dass Hintikkas Original und Tarskis Semantik gleichwertig sind, erfordert das Axiom of Choice. Man kann die Wahrheit auch in Form von Spielen mit nicht deterministischen Strategien mit weniger Komplikationen formalisieren.

Ihr sprachtheoretisches Beispiel erinnerte an Determinismus, Simulationsbeziehungen und Sprachakzeptanz. Eine Simulationsbeziehung zwischen Automaten impliziert die Einbeziehung von Sprachen zwischen ihren Sprachen, obwohl das Gegenteil nicht wahr ist. Bei deterministischen Automaten stimmen die beiden Begriffe überein. Man kann sich fragen, ob es möglich ist, Simulationsbeziehungen auf "reibungslose" Weise zu erweitern, um die Sprachäquivalenz für nicht deterministische Automaten zu erfassen. Kousha Etessami hat ein wirklich nettes Paper, das zeigt, wie man dies mit k-Simulationen macht ( Eine Hierarchie von Polynom-Zeit-berechenbaren Simulationen für Automaten)). Intuitiv spiegelt das "k" den Grad des Nichtdeterminismus wider, den die Simulationsbeziehung erfassen kann. Wenn 'k' dem Grad des Nichtdeterminismus im Automaten entspricht, stimmen Simulation und Sprachäquivalenz überein. Dieser Aufsatz gibt auch eine logische Charakterisierung von k-Simulationen im Hinblick auf polyadische Modallogik und ein beschränktes variables Fragment von Logik erster Ordnung. Sie erhalten Spracheinbeziehung, Determinismus, Spiele, Modallogik und Logik erster Ordnung in einem Stoßfängerpaket.

Vijay D
quelle
4

Dies begann als Kommentar unter der Antwort von Andrej Bauer, wurde aber zu groß.

ambiguous(ϕ)M1,M2|M1ϕM2ϕM1ψM2ψ

In Worten, es gibt verschiedene Modelle Ihrer Grammatik, die als eine Formel codiert sind, die durch eine Formel , möglicherweise eine Unterformel von .& psgr; & phiv;ϕψϕ

Sie können dies mit Andrejs Antwort auf Beweise durch Descriptive Complexity verbinden. Die Kombination aus der Existenz einer Kodierung eines bestimmten Modells und seiner Akzeptanz durch ein geeignetes TM als Modell einer gegebenen Formel IST ein Beweis dafür, dass die in dieser Formel kodierten Axiome und Folgerungen (und damit eine äquivalente Grammatik) konsistent sind.

Um dies vollständig mit Andrejs Antwort zu vereinbaren, müsste man sagen, dass das Modell durch die Formel "generiert" wird, die als Filter für den Raum aller möglichen endlichen Modelle (oder ähnliches) mit der Codierung und Aktion des Filterns fungiert auf dem Eingangsmodell als "Beweis". Die eindeutigen Beweise zeugen dann von der Mehrdeutigkeit.

Dies mag keine populäre Meinung sein, aber ich neige dazu, die Finite-Modell-Theorie und die Beweis-Theorie aus verschiedenen Blickwinkeln als dasselbe zu betrachten. ;-)

Marc Hamann
quelle
"Von Ihrer Grammatik eine Formel verschlüsselt ", ich bitte um Verzeihung, ich verstehe nicht. Meinst du "als Formel". Soweit ich das beurteilen kann, kann man immer zwei verschiedene endliche Modelle unterscheiden. ϕ
Arthur MILCHIOR
Ja, das hätte "als Formel" sein sollen. Ich habe es behoben. Was die Unterscheidung endlicher Modelle betrifft, besteht die andere Situation darin, dass es nur ein akzeptiertes endliches Modell für Ihre Sprache gibt (möglicherweise bis zu einer gewissen Vorstellung von Isomorphismus). Das ist das Gegenteil von Mehrdeutigkeit.
Marc Hamann
Ich denke, das wäre in der Tat "Mehrdeutigkeit". Ich habe nur nicht so darüber nachgedacht. Vor allem, weil dies sprachlich nicht wirklich interessant wäre. Aber aus logischer Sicht, wenn es
Sinn
Ich bin mir nicht sicher, ob der Sprachanteil langweilig sein muss. Ich habe mehr Ideen dazu, aber ich denke, es würde uns über den Rahmen dieses Forums hinausbringen. ;-)
Marc Hamann
0

Sie sind sich nicht sicher, welche Frage auf CS zutrifft, aber suchen Sie nach dem Begriff Unbestimmtheit und Logik. In der Philosophie der Logik wird Mehrdeutigkeit normalerweise von Unbestimmtheit unterschieden (siehe hier zum Beispiel), und ich denke, was Sie suchen, ist Unbestimmtheit (als Unbestimmtheit werden Begriffe definiert, bei denen es Grenzfälle gibt). Das Hauptbuch in diesem Bereich ist Timothy Williamsons Vagueness (siehe auch die Bibliographie auf der Stanford-Site oben).

DanielC
quelle
1
Vielen Dank für Ihre Antwort. Aber wie Sie sagen, sehe ich keinen wirklichen Zusammenhang mit der Informatik. Insbesondere ein Universum ist oder ist kein Modell einer Formel, hier gibt es eigentlich keine Unbestimmtheit. Stattdessen ist Mehrdeutigkeit über Automaten gut definiert, und es gibt bekannte Algorithmen, um zu entscheiden, ob ein Automat mehrdeutig, k-mehrdeutig oder eindeutig ist. (nur über eine Art Automat)
Arthur MILCHIOR
Sie haben vollkommen recht, ich hätte mich wahrscheinlich nicht auf diese Frage einlassen und mich auf das Lauern beschränken sollen. Ich bin nur ein Noob bei CS (kurz vor Abschluss meines Studiums in Logik / Wissenschaftsphilosophie und reiner Mathematik). Vielen Dank für die Informationen.
DanielC
0

Ich stimme (auch) Anrej zu.

Ich denke, die deskriptive Komplexität ist eine rechenlose Charakterisierung (was sie auf ihre Weise interessant macht) und daher die Beispiele für mehrdeutige Berechnungen aus der Theorie der formalen Sprachen (Automaten / Grammatiken / ...), die Sie angegeben haben, in einem ganz anderen Bereich zu sein . In der Beschreibung entsprechen Komplexitätssprachen Komplexitätsklassen, und Abfragen (in einer Sprache) entsprechen Rechenproblemen (nicht Algorithmen). Es gibt keine beabsichtigte Methode zum Überprüfen / Berechnen einer AFAIK-Abfrage. Wenn Sie also nicht nach mehrdeutigen Berechnungen suchen, sind diese Beispiele irreführend.

Kaveh
quelle
Kaveh, ich bin mir nicht sicher, ob ich damit einverstanden bin, dass die rechnerlose Charakterisierung der beschreibenden Komplexität zu 100% richtig ist. Die rechnerischen Details sind sehr wichtig, um zu verstehen, wie eine bestimmte Logik eine Komplexitätsklasse erfasst. Der Vorteil ist, dass Sie, sobald Sie Ihre Beweise erstellt haben und wissen, wie es funktioniert, die Berechnung aufheben und sich mit logischen Standardmethoden auf die logischen Details konzentrieren können.
Marc Hamann
Gleiche Bemerkung à Mark. Die beschreibende Komplexität wird auch als Datenbanktheorie bezeichnet. Ein Vokabular ist eine Struktur einer Datenbank, und die Modelle der Theorie bilden den Inhalt der Datenbank. Daher ist es erfreulich, dass wir berechnen und herausfinden können, ob eine Datenbank eine Formel einhält.
Arthur MILCHIOR
@Marc, aber es gibt keine beabsichtigte Art der Berechnung, es ist eine rein beschreibende Charakterisierung. Natürlich können Sie es mit Algorithmen (und deren Berechnungen) in anderen Einstellungen verbinden, aber das ist seiner Natur nach zweitrangig. Wie gesagt, Komplexitätsklassen (zB ) entsprechen beschreibenden Sprachen (zB ), Rechenprobleme entsprechen Abfragen, aber AFAIK gibt es nichts, was Algorithmen oder Berechnungen in der beschreibenden Komplexität entspricht ( was nicht überraschend ist, wenn man bedenkt, dass es auch Teil der Modelltheorie ist). F OAC0FO
Kaveh
1
@Kaveh, ich mache einen etwas subtilen Punkt, aber einen, den ich für wichtig halte, da er häufig missverstanden zu werden scheint (zum Beispiel durch fehlgeschlagene P = NP? -Versuche). Es gibt einen zugrunde liegenden Algorithmus, der ziemlich brachial ist und der der Entsprechung einer logischen Sprache und einer Komplexitätsklasse zugrunde liegt. Wenn Sie mit der Logik arbeiten, müssen Sie nicht jede Sekunde über die Details dieses Algorithmus nachdenken, aber die Schönheit und das Genie der Beweise von Fagin, Immerman, Vardi und anderen liegt in der genauen Beschreibung dieser Algorithmen. Menschen, die sie völlig aus den Augen verlieren, geraten in der Regel in Schwierigkeiten.
Marc Hamann
1
@Kaveh, ich denke wir verstehen uns und teilen unseren Respekt für das Feld. "Brute-Force" war nicht als geringfügig gegenüber den zugrunde liegenden Algorithmen gedacht, um nur zu verdeutlichen, dass es sich um etwas handelt, das etwas abstrakter ist, als jemand, der beispielsweise algorithmische Optimierungsarbeit leistet, dies als Algorithmus auffassen könnte.
Marc Hamann