Niejednoznaczność i logika

17

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

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ϕwLϕ

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. xϕ(x)xϕ(x)ϕ(x)
  • byłby niejednoznaczny, gdyby istniał model zarówno ϕ 0, jak i ϕ 1 , lub jeśli ϕ i jest niejednoznaczny. ϕ0ϕ1ϕ0ϕ1ϕ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?

Arthur MILCHIOR
źródło

Odpowiedzi:

11

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.

Andrej Bauer
źródło
Tak naprawdę nie myślałem o dowodach. Jestem bardziej przyzwyczajony do (skończonej) teorii modelu. Chcemy dowiedzieć się, które zestawy są modelami formuły, a które nie. (Szczególnie w przypadku formuły, jaka jest złożoność stwierdzenia, czy zbiór jest modelem, czy nie, a dla formuły możliwej do udowodnienia, a więc tautologii, złożoność wynosi O (1), ponieważ każdy zbiór jest modelem). Ale bardzo dziękuję za odpowiedź.
Arthur MILCHIOR
2
Cóż, aby dodać analogię: teoria modeli polega na logice, czym jest semantyka dla języków. Teoria modeli przypisuje znaczenie teoriom logicznym, podczas gdy semantyka przypisuje znaczenie językom. Czasami najlepiej nie mieszać jabłek i pomarańczy, nawet jeśli jesteś do tego przyzwyczajony.
Andrej Bauer,
7

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.

Vijay D.
źródło
4

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(ϕ)M1,M2|M1ϕM2ϕM1ψM2ψ

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 ϕϕψϕ .

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

Marc Hamann
źródło
ϕ
Tak, to powinno być „jako formuła”. Naprawiłem to. Jeśli chodzi o rozróżnianie modeli skończonych, druga sytuacja jest taka, że ​​istnieje tylko jeden zaakceptowany model skończony dla twojego języka (być może do pewnego stopnia izomorfizm). To jest przeciwieństwo dwuznaczności.
Marc Hamann
Myślę, że to rzeczywiście byłaby „dwuznaczność”. Po prostu tak o tym nie myślałem. Głównie dlatego, że pod względem językowym nie byłoby to naprawdę interesujące. Ale z logicznego punktu widzenia, jeśli ma to sens
Arthur MILCHIOR
Nie jestem pewien, czy część językowa musi być nudna. Mam więcej pomysłów na ten temat, ale myślę, że zabrałoby nas to poza zakres tego forum. ;-)
Marc Hamann
0

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

DanielC
źródło
1
Dziękuję za Twoją odpowiedź. Ale jak mówisz, tak naprawdę nie widzę związku z informatyką. W szczególności wszechświat jest lub nie jest wzorem formuły, tak naprawdę nie ma tu żadnych niejasności. W przeciwieństwie do automatów, dwuznaczność jest czymś, co jest dobrze zdefiniowane, i znany jest algorytm decydujący, czy automat jest dwuznaczny, k-niejednoznaczny czy jednoznaczny. (tylko nad jakimś automatem)
Arthur MILCHIOR
Masz całkowitą rację, prawdopodobnie nie powinienem był wskakiwać na to pytanie i trzymać się czai. Jestem tylko notobem w CS (kończę studia licencjackie w logice / filozofii nauki i czystej matematyce). Dziękuję za informację.
DanielC
0

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.

Kaveh
źródło
Kaveh, nie jestem pewien, czy zgadzam się, że charakterystyka złożoności opisowej bez obliczeń jest w 100% słuszna. Szczegóły obliczeniowe są bardzo ważne dla zrozumienia, w jaki sposób konkretna logika przechwytuje klasę złożoności. Zaletą jest to, że po wykonaniu prób i zrozumieniu, jak to działa, można odłożyć obliczenia na bok i skoncentrować się na szczegółach logicznych przy użyciu standardowych metod logicznych.
Marc Hamann
Ta sama uwaga à Mark. Złożoność opisowa jest również znana jako teoria bazy danych, słownictwo będące strukturą bazy danych oraz modele teorii oparte na zawartości bazy danych. Dlatego cieszymy się, że możemy obliczyć i ustalić, czy baza danych przestrzega formuły.
Arthur MILCHIOR,
@Marc, ale nie ma zamierzonego sposobu obliczenia, jest to charakter czysto opisowy . Oczywiście możesz połączyć go z algorytmami (i ich obliczeniami) w innych ustawieniach, ale ma to drugorzędne znaczenie. Jak powiedziałem, klasy złożoności (npZAdo0) odpowiadają językom opisowym (np faO), problemy obliczeniowe odpowiadają zapytaniom, ale AFAIK nie ma nic odpowiadającego algorytmom lub obliczeniom o złożoności opisowej (co nie jest zaskakujące, biorąc pod uwagę, że jest to również część teorii modeli).
Kaveh
1
@Kaveh, robię nieco subtelny punkt, ale myślę, że jest ważny, ponieważ wydaje się być często źle rozumiany (na przykład przez nieudane próby P = NP?). Nie ma instrumentu bazowego, dość algorytm brute-force, która leży u podstaw korespondencja języka logicznego i klasa złożoności. Praca z logiką pozwala nie myśleć o szczegółach tego algorytmu co sekundę, ale piękno i genialność dowodów Fagina, Immermana, Vardiego i innych polega właśnie na opisywaniu tych algorytmów. Ludzie, którzy zupełnie ich nie widzą, zwykle mają kłopoty.
Marc Hamann
1
@Kaveh, myślę, że się rozumiemy i podzielamy szacunek dla tej dziedziny. „Brute-force” nie było zamierzone jako podstawa dla podstawowych algorytmów, po prostu wyjaśniając, że mówimy o czymś nieco bardziej abstrakcyjnym niż to, co ktoś, kto, powiedzmy, pracuje nad optymalizacją algorytmu, może uważać za algorytm.
Marc Hamann