Es gelten für Stapelspeicher folgende Operationen:
pop(m) soll das oberste Element e eines
nicht leeren Stapels m entfernen und den neuen Stapel m´ zurück geben.
push(m,e) soll ein neues Datenelement e ∈ ℤ ganz oben in den
Stapel m einfügen und den resultierenden Stapel zurück geben.
Ok, nun die Aufgabe:
Für genau welche Stapel m, bzw. e ∈ ℤ gelten die folgenden Aussagen?
a) pop(push(m,e)) = m
Begründen Sie.
b) push(pop(m),e) = m
Beweisen Sie, dass Ihre Anforderungen an m notwendig ist sind.
c) Beweisen Sie, dass Ihre Anforderungen an m bzw. e aus Teilaufgabe b) hinreichend
sind.
Sie dürfen hierzu ohne Beweis verwenden, dass gilt:
• m = m´ gilt genau für alle Stapel m, m´, mit Mm = Mm´ (Mm = { (a,m(a)) I m(a) ≠ kein Element}
• (A ∪ B) \ B = A für disjunkte Mengen A, B
• (A \ B) ∪ B = (A ∪ B) für beliebige Mengen A, B
• m´(0) = m(0) − 1 für nichtleere Stapel m und m´ = pop(m)
Also zur a) habe ich gedacht, dass die Aussage "(A ∪ B) \ B = A für disjunkte Mengen A, B" gilt aber in der Aufgabenstellung steht explizit, für welche Stapel m, bzw. e. Das gilt doch für alle m und e oder nicht? Hat jemand einen Tipp für mich zur a) oder zu den anderen Teilaufgaben? Was wird mit hinreichend/notwendig gemeint (im Skript steht nichts).
Danke im voraus
