Lösungsvorschläge zu Thema 1

Zusammenfassung

Die Antwort lautet Nein. Um das zu sehen, kann man sich beispielsweise die Anzahl der Buchstaben ansehen. MEU hat drei Buchstaben, also ist die Länge des Ausgangsworts ungerade. Bei jeder der erlaubten Umformungen (R 1), (R 2) und (R 3) ändert sich die Wortlänge entweder gar nicht oder um 2, also um eine gerade Zahl. Addiert oder subtrahiert man von einer ungeraden Zahl eine gerade Zahl, erhält man stets wieder eine ungerade Zahl. In diesem Beispiel ist also die Eigenschaft, ob die Wortlänge gerade oder ungerade ist, eine Invariante. Da die Länge des Zielwortes MU gleich 2 ist, also eine gerade Zahl, kann man MEU mit den gegebenen Regeln nicht in MU umformen.