Die Mathe-Redaktion [Home] - Neues auf einen Blick 10.06.2023 20:58 [Neues] [Forum] [Suche] - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Prädikatenlogik » Prädikatenlogik erster Stufe und monadische Logik
Autor
Universität/Hochschule J Prädikatenlogik erster Stufe und monadische Logik
Brayn
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2014
Mitteilungen: 262
Wohnort: Kaiserslautern
  Themenstart: 2017-05-05

Hallo ihr Lieben, wir haben in der VL gerade den Satz von Büchi durchgenommen und ich verstehe leider nur sehr wenig. Das Problem ist eigentlich schon der Satz an sich bzw. das was daraus Folgen könnte. Der Satz von Büchi besagt: $ \textit{Eine Sprache ist genau dann MSO-definierbar, wenn sie regulär ist.} $ Quelle. Jetzt wissen wir aber, dass die Prädikatenlogik erster Stufe (FO) weniger mächtig ist als die monadische Logik (MSO). Außerdem wissen wir, dass die Unerfüllbarkeit einer FO Formel semi-entscheidbar ist. Weiter ist aber auch bekannt, dass reguläre Sprachen entscheidbar sind (z.B. mit endlichen Automaten). Wie kann es also sein, dass MSO äquivalent mit einer Klasse von Sprachen ist, die entscheidbar sind? Dann könnte man ja jede FO Formel (die auch eine MSO Formel ist) durch einen endlichen Automaten entscheiden, was aber ein Widerspruch dazu ist, dass eben genau das nicht geht. :( Also irgenwas stimmt da nicht, aber was? Kann mir jemand bitte meinen Fehler zeigen? Liebe Grüße Matthias

   Profil
Brayn
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2014
Mitteilungen: 262
Wohnort: Kaiserslautern
  Beitrag No.1, vom Themenstarter, eingetragen 2017-05-05

Edit: Kann es sein, dass der Fehler darin liegt, dass nicht die Sprache selbst, sondern lediglich ein Wort aus der Sprache entscheidbar ist? Demnach würde ein Wort aus der Sprache eine Belegung der FO Formel repräsentieren. Stimmt das so?

   Profil
Brayn hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]