Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Mathematik » Logik, Mengen & Beweistechnik » MSO-Formel
Druckversion
Druckversion
Autor
Universität/Hochschule J MSO-Formel
AlexanderS
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 22.05.2019
Mitteilungen: 34
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-08-14


Hallo,
ich habe folgende Formel:

$$\begin{array}{c}
\varphi:=\exists X \exists Y \min \in X \wedge \max \in Y \wedge \forall x \neg(x \in X \wedge x \in Y) \wedge \\
\forall x(x<\max \rightarrow(x \in X \leftrightarrow x+1 \in Y))
\end{array}$$,

die die Sprache aller Wörter mit gerader Länge auf dem Alphabet
$\{a,b,c\}^+$ repräsentieren soll.

Mein Problem liegt darin, dass ich bei dem Wort $w=abc$ den Knackpunkt der Formel nicht sehe, denn es dürfte ja eigentlich nicht funktionieren.

Grundsätzlich macht mir der Teil $\forall x(x<\max \rightarrow(x \in X \leftrightarrow x+1 \in Y)$ sorgen.


Bei genaueren Überlegen, macht die Formel mit auch Schwierigkeiten für das Wort $v=abcd$ (Alphabet $\{a,b,c,d\}^+$ und Universum {1,2,3,4) also die Positionen im Wort).

Offensichtlich würde ja dann $1\in X$ und $4\in Y$ gelten, aber wenn $1\in X$, dann muss $2\in Y$ liegen. Dann komme ich allerdings mit der Formel nicht mehr weiter, denn $2<max$ aber $2\not \in X$, denn $\forall x \neg(x \in X \wedge x \in Y)$. Macht das Sinn?

Ich wäre sehr dankbar, wenn mir Jemand einmal erklären könnte wie man mit der Formel umgehen soll, bzw wie lautet eigentlich die Belegung?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2005
Mitteilungen: 3639
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-08-15


Hallo AlexanderS,
bei <math>w=abc</math> folgt aus <math>1\in X</math> und dem letzten <math>\forall x(\ldots)</math>, dass <math>2\in Y</math> sein muss. Das steht im Widerspruch zu <math>3\in Y</math>, ebenfalls wegen dem letzten <math>\forall x(\ldots)</math>.

Bei <math>v=abcd</math> funktioniert \(X=\{1,3\}, Y=\{2,4\}\).

Viele Grüße,
  Stefan



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AlexanderS
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 22.05.2019
Mitteilungen: 34
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-08-15


Dankeschön



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AlexanderS hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


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-2020 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]