Logik; Ableitbarkeit von Zeichenfolgen

Neue Frage »

Studentu Auf diesen Beitrag antworten »
Logik; Ableitbarkeit von Zeichenfolgen
Hallo Community,
die Angabe zu meiner Frage ist zwar etwas länger, die Lösungen sollten aber nicht so schwierig sein, wenn man das System versteht (was bei mir bislang leider noch nicht der Fall ist).
Also:
Wir betrachten Zeichenfolgen (Strings), die aus den Zeichen 1, +, = zusammengesetzt sind. Auch die leere Folge gilt als Zeichenfolge, sie hat Länge 0 und wird mit oder bezeichnet. Gewisse Zeichenfolgen zeichnen wir als "ableitbar" aus.
Gewisse Zeichenfolgen nennen wir "Axiome"; Axiome A schreiben wir in der Form an. Wir lesen dies als "A ist ableitbar". Eine "Regel", die wir in der Form schreiben, lesen wir als "wenn ableitbar sind, dann auch B".
Die Menge der ableitbaren Zeichenfolgen ist die kleinste Menge M, die alle Axiome enthält und unter allen Regeln abgeschlossen ist. (Das heißt: Wann immer wir eine Regel haben, deren "Voraussetzungen" in M liegen, muss auch die "Folgerung" B in M liegen.




a) Wir betrachten ein Ableitungssystem mit dem einzigen Axiom und den Regeln (für jede Zeichenfolge A) und für beliebige Zeichenfolgen A, B. Zeige, dass die Zeichenfolgen 11 + 11 = 1111 und 11111 + 11 = 1111111 ableitbar sind.

b) Zeige, dass folgende Zeichenfolgen alle nicht ableitbar sind: 1 + 1 + 1 = 111, 1 + 1 = 111, 1=1.

b+) Gib ein Kriterium an, das entscheidet, ob eine vorgegebene Zeichenfolge ableitbar ist.
(Hierbei ist entweder b) oder b+) wesentlich einfacher zu lösen als das jeweils andere und nur an der Lösung des einfacheren Unterpunktes bin ich interessiert.)

c) Gib ein möglichst einfaches Ableitungssystem an, in dem eine Zeichenfolge der Form (also n aufeinanderfolgende 1er) genau dann ableitbar ist, wenn n eine Primzahl ist. ("möglichst einfach" bedeutet hierbei, dass die Axiome und Regeln einem einfachen Schema folgen; das Schema " ist Axiom genau dann, wenn n Primzahl ist" ist nicht einfach).

c+) Gib ein möglichst einfaches Ableitungssystem an, in dem eine Zeichenfolge der Form genau dann ableitbar ist, wenn n>1 ist und keine Primzahl ist.
(Hierbei ist entweder c) oder c+) wesentlich einfacher zu lösen als das jeweils andere und nur an der Lösung des einfacheren Unterpunktes bin ich interessiert.)






Schon allein a) schaffe ich einfach nicht.
Wegen der Regel gilt zwar, dass aus der Ableitbarkeit von 11 auch die Ableitbarkeit von 1111 folgt, aber 11 + 11 = 1111 zu begründen, bekomme ich nicht hin. unglücklich
Hat jemand eine Idee, wie das Ganze funktioniert?
HAL 9000 Auf diesen Beitrag antworten »
unklar
Zitat:
Original von Studentu
a) Wir betrachten ein Ableitungssystem mit dem einzigen Axiom und [...]

b) Zeige, dass folgende Zeichenfolgen alle nicht ableitbar sind: 1 + 1 + 1 = 111, 1 + 1 = 11, 1=1.

Erstaunt1 Es wird direkt per Axiom festgelegt, dass 1 + 1 = 11 ableitbar ist, und dann sagst du, man soll nachweisen, dass es nicht ableitbar ist???
Studentu Auf diesen Beitrag antworten »

Hallo HAL 9000,
danke für deine Beteiligung!
Nein, das ist natürlich Quatsch, ich habe einen Tippfehler eingebaut. Es ist nachzuweisen, dass 1 + 1 = 111 nicht ableitbar ist. Ich werde das gleich entsprechend editieren. Entschuldigung für die Verwirrung!!!!!
Studentu Auf diesen Beitrag antworten »

Ist sonst noch etwas unklar?
HAL 9000 Auf diesen Beitrag antworten »

Nicht missverstehen: Ich wollte nur auf eine Unstimmigkeit in der Aufgabenstellung hinweisen, d.h., mein Beitrag sollte NICHT bedeuten, dass ich schon ernsthaft über die Lösung nachgedacht habe.
Studentu Auf diesen Beitrag antworten »

Okay.

Ich habe inzwischen eine Idee zu a).
Es gilt ja: "1+1= 11 ist ableitbar" und die Regel "wenn A ableitbar ist, dann auch 1A1".
Deshalb muss doch "1+11 = 111" auch ableitbar sein.
Nun fehlt nur mehr ein Einser, um zu zeigen, dass "11 + 11 = 1111" ist. Dafür muss der alleinstehende 1er irgendwie direkt neben das Gleichheitszeichen kommen, damit man die Regel darauf anwenden kann.
Dürfen wir einfach davon ausgehen, dass "1+11=111" äquivalent ist zu "111=1+11"?
 
 
Studentu Auf diesen Beitrag antworten »

Teil a) hat sich inzwischen gänzlich geklärt.
Ich bräuchte daher nur mehr Hilfe zu b)/b+) und c)/c+).
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von Studentu
Hallo Community,
die Angabe zu meiner Frage ist zwar etwas länger, die Lösungen sollten aber nicht so schwierig sein, wenn man das System versteht (was bei mir bislang leider noch nicht der Fall ist).
Also:
Wir betrachten Zeichenfolgen (Strings), die aus den Zeichen 1, +, = zusammengesetzt sind. Auch die leere Folge gilt als Zeichenfolge, sie hat Länge 0 und wird mit oder bezeichnet. Gewisse Zeichenfolgen zeichnen wir als "ableitbar" aus.
Gewisse Zeichenfolgen nennen wir "Axiome"; Axiome A schreiben wir in der Form an. Wir lesen dies als "A ist ableitbar". Eine "Regel", die wir in der Form schreiben, lesen wir als "wenn ableitbar sind, dann auch B".
Die Menge der ableitbaren Zeichenfolgen ist die kleinste Menge M, die alle Axiome enthält und unter allen Regeln abgeschlossen ist. (Das heißt: Wann immer wir eine Regel haben, deren "Voraussetzungen" in M liegen, muss auch die "Folgerung" B in M liegen.




a) Wir betrachten ein Ableitungssystem mit dem einzigen Axiom und den Regeln (für jede Zeichenfolge A) und für beliebige Zeichenfolgen A, B. Zeige, dass die Zeichenfolgen 11 + 11 = 1111 ableitbar sind.



Aus 1+1 = 11 (axiomatisch vorgegeben) folgt mit der zweiten Regel 1+11=111, indem wir A = "1+1" und B = "11" setzen, dann setzen wir die ganze Zeichenkette "1+11=111" als A und mit der ersten Regel ergibt sich 11+11=1111. Das ist sicherlich der Lösungsweg, oder? Aber woraus ergibt sich, dass man "1+1" für A bzw. "11" für B einsetzen darf, um daran die zweite Regel anzuwenden? Das geht so nicht, weil nach den o.g. Vorgaben eigentlich nur "1+1=11" = A bzw. B sein darf und dann klappt es nicht. ME ist daher die Aufgabe nicht korrekt gestellt.
Studentu Auf diesen Beitrag antworten »

Hallo Pippen,
danke für deinen Beitrag. Genau das, was du geschrieben hast, ist mein Lösungsweg.
Ich kann das Problem, das du in der Formulierung der Angabe siehst, allerdings nicht 100% nachvollziehen, denn es steht ja das, "für beliebe Zeichenfolgen A, B" und, dass Zeichenfolgen aus den Zeichen 1, +, = zusammengesetzt sind. Und genau derartige Zeichenfolgen liegen in dem Beispiel ja vor?

Hast du vielleicht eine Idee, wie c) oder c+) funktioniert?


b) hat sich inzwischen auch geklärt.
Pippen Auf diesen Beitrag antworten »

Zitat:
Original von Studentu
Ich kann das Problem, das du in der Formulierung der Angabe siehst, allerdings nicht 100% nachvollziehen, denn es steht ja das, "für beliebe Zeichenfolgen A, B" und, dass Zeichenfolgen aus den Zeichen 1, +, = zusammengesetzt sind. Und genau derartige Zeichenfolgen liegen in dem Beispiel ja vor?



In deinem Einführungstext steht nur, dass 1,+,= Zeichen sind und das daraus Zeichenfolgen gebildet werden können. Danach wird eine solche Zeichenfolge, nämlich "1+1=11", als axiomatisch eingeführt. Damit kann auch nur "1+1=11" in die beiden Schemen eingesetzt werden, die ja nur für abgeleitete bzw. axiomatisch eingeführte Zeichenfolgen gelten. Wie und woher man "1+1" in A einsetzen darf, erschließt sich mir nicht. Da fehlt der Hinweis, dass bei einer Zeichenfolge mit "=" alles links und rechts ebenfalls eine Zeichenfolge ist. Dann würde es klappen.
Studentu Auf diesen Beitrag antworten »

Jetzt verstehe ich deinen Einwand, Pippen, da hast du vollkommen Recht.
Da das Beispiel sonst aber nicht lösbar wäre, denke ich, die Angabe war schon so gemeint, nur einfach unrichtig formuliert.


Ich habe hier die Lösung für c) gefunden https://math.stackexchange.com/questions...-iff-n-is-prime
aber ich verstehe die Notation nicht. Kann jemand nachvollziehen, was gemeint ist?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »