Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

PPL für jede Zerlegung ?

–1 Punkt
73 Aufrufe

EDIT: Der folgende Beitrag bezieht sich auf eine veraltete Version des Pools; er wird trotzdem nicht zensiert, damit die Diskussion in diesem Thread verständlich bleibt.

Hallo,

die Beweisstruktur in diesem Beweis ist nicht korrekt! Es wird etwas falsches gefolgert:

 

"...Jetzt sei w=xyz beliebige Partition von w. Dann gilt laut PPL:

1) |xy|≤n

2) |y|>0

3)...

"

Diese Folgerung ist doch falsch. Das PPL sagt nämlich, dass es eine Partition gibt, sodass 1-3 gilt. Also insbesondere, dass es nicht für eine beliebige Partition gilt! Sonst müsste es im PPL heißen, dass dies für jede(!) Zerlegung gilt.

lg Adam

 

Gefragt 25, Nov 2014 in PUM-AA von uafjv uafjv Tutor(in) (167,990 Punkte)  
Bearbeitet 25, Nov 2014 von uafjv uafjv

2 Antworten

0 Punkte
 
Beste Antwort
Hallo Adam, hallo Sven,

Adam hat trotzdem mit seiner Anmerkung recht - wir haben das nicht hundertprozentig korrekt formuliert. Wir werden das ändern zu:

"Es seien $x,y,z∈E^∗$ Wörter, sodass gilt: $w=xyz$ und [...] (1), (2), (3)"

(oder so ähnlich).

Viele Grüße

Lukas König
Beantwortet 25, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Hallo,

danke erstmal für die Antwort, die neue Formulierung hört sich gut an.

Ich habe nicht gemeint, dass es nur eine einzige gibt, sondern mindestens eine, aber das war nicht eindeutig herauslesbar. Und dass es Wörter xyz gibt, sodass w=xyz ist wohl selbstverständlich, aber dass diese auch noch 1-3 des PPL erfüllen, stimmt eben nicht für alle. Wir wissen nur, dass min. eine Zerlegung dieser xyz das PPL erfüllt, deshalb müssen wir ja für alle Zerlegungen zeigen, dass sie 1-3 nicht erfüllen können, um den Widerspruchsbeweis zu führen.

Und in meinem Zitat wurde für alle w=xyz gefolgert, dass xyz 1-3 des PPL erfüllen. Wenn dies so wäre, müssten wir nur eine spezielle Zerlegung betrachten :D

lg Adam
Ist Widerspruchsbeweis durch definieren von xy & z zulässig?
0 Punkte

Hallo,

das PPL besagt nicht explizit, dass es EINE Partion gibt, sondern es sagt, dass es Wörter x, y und z mit w = xyz gibt. Das schließt also nicht aus, dass man für x, y und z viele unterschiedliche Wahlen treffen kann und daraus w zusammen setzen kann.

Viele Grüße,

Sven (Tutor)

 

Beantwortet 25, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...