Niejednoznaczność i logika

W teorii automatów (automaty skończone, automaty wypychające, ...) i złożoności występuje pojęcie „dwuznaczności”. Automat jest dwuznaczny, jeśli istnieje słowo z co najmniej dwoma odrębnymi przebiegami akceptującymi. Maszyna jest k- dwuznaczna, jeśli dla każdego słowa w zaakceptowanego przez maszynę istnieje co najwyżej k różnych przebiegów do zaakceptowania w .$w$$k$$w$$k$$w$

Pojęcie to zdefiniowano także w gramatyce bezkontekstowej: gramatyka jest dwuznaczna, jeśli istnieje słowo, które można wyprowadzić na dwa różne sposoby.

Wiadomo również, że wiele języków ma ładną logiczną charakterystykę w stosunku do modeli skończonych. (Jeśli język jest regularny, istnieje monadyczna formuła drugiego rzędu ϕ nad słowami, tak że każde słowo w z L jest modelem ϕ , podobnie NP, jeśli jest równoważne formułom drugiego rzędu, w których istnieją kwantyfikatory drugiego rzędu.)$L$$\phi$$w$$L$$\phi$

Stąd moje pytanie leży na obrzeżach dwóch domen: czy istnieje jakikolwiek wynik, a nawet kanoniczna definicja „dwuznaczności” formuł danej logiki?

Mogę sobie wyobrazić kilka definicji:

• nie jest niejednoznaczne, jeśli istnieje co najwyżej jeden x taki, że ϕ ( x ) utrzymuje, a ϕ ( x ) jest niejednoznaczny. $\exists x \phi(x)$$x$$\phi(x)$$\phi(x)$
• byłby niejednoznaczny, gdyby istniał model zarówno ϕ 0, jak i ϕ 1 , lub jeśli ϕ i jest niejednoznaczny. $\phi_0\lor\phi_1$$\phi_0$$\phi_1$$\phi_i$
• Formuła SAT byłaby niejednoznaczna, jeśli istnieje co najwyżej jedno prawidłowe przypisanie.

Dlatego zastanawiam się, czy jest to dobrze znane pojęcie, w przeciwnym razie interesujące może być przeprowadzenie badań na ten temat. Jeśli to pojęcie jest znane, czy ktoś mógłby podać mi słowa kluczowe, których mógłbym użyć do wyszukiwania informacji w tej sprawie (ponieważ „dwuznaczność logiczna” daje wiele niepowiązanych wyników), lub odniesienia do książek / pdf / artykułów?

Reguły w gramatyce i reguły wnioskowania w logice można traktować zarówno jako reguły produkcji, które dają nam „nowe rzeczy” z „znanych rzeczy”. Tak jak może istnieć wiele sposobów na utworzenie (lub parsowanie) słowa w odniesieniu do gramatyki, tak może istnieć wiele sposobów na wytworzenie (lub udowodnienie) logicznej formuły. Analogię tę można wyciągnąć dalej. Na przykład niektóre systemy logiczne dopuszczają normalne formy dowodów. Podobnie niektóre gramatyki dopuszczają kanoniczne drzewa analizujące.

Powiedziałbym więc, że twoje przykłady z logiki idą w złym kierunku. Prawidłowa analogia to

„parsuj drzewo”: „słowo” = „dowód”: „formuła logiczna”

W rzeczywistości wystarczająco ogólny rodzaj gramatyki będzie w stanie wyrazić typowe reguły wnioskowania logiki, tak że poprawne gramatycznie słowa będą dokładnie możliwymi do udowodnienia formułami. W tym przypadku drzewo wyprowadzenia rzeczywiście być dowody.

W przeciwnym kierunku, jeśli chcemy myśleć o bardzo ogólnych regułach wnioskowania (które niekoniecznie mają tradycyjny logiczny smak), wówczas każda gramatyka będzie wyrażana jako system aksjomatów (terminali) i reguł wnioskowania (produkcji). I jeszcze raz zobaczymy, że dowód jest tym samym, co parsowanie drzewa.

Tylko dwie uwagi. Mam nadzieję, że pomogą.

Standardowe definicje semantyki logiki i prawdy są zgodne z prezentacją Tarskiego, a następnie indukowane przez strukturę formuł. Inną możliwością jest zastosowanie semantyki opartej na grze, jak sugeruje Hintikka. Prawda i satysfakcja są zdefiniowane w kategoriach strategii w grze. W przypadku formuł pierwszego rzędu można udowodnić, że formuła jest prawdziwa pod pojęciem Tarskiego, tylko wtedy, gdy istnieje strategia wygrywająca w grze Hintikka.

W celu sformalizowania pytania można zapytać, czy gra dopuszcza wiele strategii. Istnieje również interesujące pytanie, czy strategie powinny być deterministyczne. Hintikka wymagała od nich determinizmu. Dowód, że oryginał Hintikki i semantyka Tarskiego są równoważne, wymaga Aksjomatu Wyboru. Można także sformalizować prawdę w kategoriach gier z niedeterministycznymi strategiami o mniejszej liczbie powikłań.

Twój przykład teorii języka przypomniał determinizm, relacje symulacyjne i akceptację języka. Relacja symulacji między automatami oznacza włączenie języka między ich językami, chociaż odwrotność nie jest prawdą. W przypadku automatów deterministycznych oba pojęcia są zbieżne. Można zapytać, czy możliwe jest „płynne” rozszerzenie relacji symulacji w celu uchwycenia równoważności języka dla automatów niedeterministycznych. Kousha Etessami ma naprawdę fajny artykuł pokazujący, jak to zrobić za pomocą symulacji k ( Hierarchia obliczeń wielomianowych w czasie dla automatów). Intuicyjnie „k” odzwierciedla stopień niedeterminizmu, jaki może uchwycić relacja symulacji. Kiedy „k” jest równe poziomowi niedeterminizmu w automacie, symulacja i równoważność językowa pokrywają się. Artykuł ten podaje także logiczną charakterystykę symulacji k pod względem poliadycznej logiki modalnej i ograniczonego fragmentu zmiennej logiki pierwszego rzędu. Włączenie języka, determinizm, gry, logika modalna i logika pierwszego rzędu - wszystko w jednym pakiecie zderzaka.

Zaczęło się od komentarza pod odpowiedzią Andreja Bauera, ale stało się zbyt duże.

Myślę oczywiste definicja niejednoznaczności z punktu widzenia teorii modelu skończonych widzenia byłoby: m b i g u o u s ($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$

Innymi słowy, istnieją odrębne modele gramatyki zakodowane jako formuła którą można odróżnić za pomocą jakiejś formuły ψ , być może pod-formuły $\phi$$\psi$$\phi$ .

Możesz połączyć to z odpowiedzią Andreja na dowody poprzez złożoność opisową. Kombinacja istnienia kodowania określonego modelu plus jego akceptacja przez odpowiednią TM jako model danej formuły JEST dowodem, że aksjomaty i wnioskowania (a zatem i równoważna gramatyka) zakodowane w tej formule są spójne.

Aby uczynić to w pełni kompatybilnym z odpowiedzią Andreja, należy powiedzieć, że model jest „generowany” przez formułę działającą jako filtr na przestrzeni wszystkich możliwych modeli skończonych (lub coś w tym rodzaju), z kodowaniem i działaniem filtrowania w modelu wejściowym jako „dowód”. Odrębne dowody świadczą o dwuznaczności.

To może nie być popularny sentyment, ale mam tendencję do myślenia o teorii modeli skończonych i teorii dowodu jako tej samej rzeczy widzianej pod różnymi kątami. ;-)

Nie jestem pewien, czy pytanie dotyczy CS, ale spróbuj wyszukać termin Nieokreśloność i logika. W filozofii logiki dwuznaczność zwykle odróżnia się od niejasności (patrz na przykład tutaj ) i myślę, że to, czego szukasz, jest niejasne (ponieważ niejasność jest definiowana jako terminy, w których występują przypadki graniczne). Główną książką w tej dziedzinie jest niejasność Timothy'ego Williamsona (ale także patrz bibliografia na stronie Stanford powyżej).

Ja (również) zgadzam się z Anrejem.

Myślę, że złożoność opisowa to charakterystyka bez obliczeń (co czyni ją interesującą na swój sposób), a zatem przykłady dwuznaczności obliczeniowej z teorii języków formalnych (automaty / gramatyki / ...), które sprawiły, że wyglądasz na zupełnie inną dziedzinę . W złożoności opisowej języki odpowiadają klasom złożoności, a zapytania (w języku) odpowiadają problemom obliczeniowym (nie algorytmom). Nie ma zamierzonego sposobu sprawdzania / obliczania zapytania AFAIK, więc jeśli nie szukasz obliczeniowej dwuznaczności, IMHO te przykłady wprowadzają w błąd.