Mehrdeutigkeit und Logik

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 .$w$$k$$w$$k$$w$

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$$\phi$$w$$L$$\phi$

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. $\exists x \phi(x)$$x$$\phi(x)$$\phi(x)$
• wäre mehrdeutig, wenn es ein Modell von ϕ 0 und ϕ 1 gibt , oder wenn ϕ i mehrdeutig ist. $\phi_0\lor\phi_1$$\phi_0$$\phi_1$$\phi_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?

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.

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.

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

$ambiguous(\phi) \implies \exists M_1,M_2 | M_1 \vDash \phi \wedge M_2 \vDash \phi \wedge M_1 \vDash \psi \wedge M_2 \nvDash \psi$

In Worten, es gibt verschiedene Modelle Ihrer Grammatik, die als eine Formel codiert sind, die durch eine Formel , möglicherweise eine Unterformel von .& psgr; $\phi$$\psi$$\phi$

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. ;-)

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).

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.