Übung 6

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Übung 6

Beitrag von robert.n »

Hallo,

ich verstehe nicht so ganz, wieso in der MuLö zu Aufgabe 1b) von Übung 6 in der 2. Sequenz ein \(\neg ?0(x)\) steht statt \(?^+(x)\). Bitte klärt mich jemand auf.

Danke.

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Re: Übung 6

Beitrag von Simon Siegler »

Die Induktion im Lösungsvorschlag folgt in diesem Punkt tatsächlich nicht der Relationenbeschreibung der Datenstruktur, sondern der Relationenbeschreibung der Prozedur. Beide Relationenbeschreibungen definieren die gleiche Relation auf den natürlichen Zahlen, daher ist dieser Fehler in der Aufgabenstellung (auch der entsprechenden Hausübung 4.2) nicht aufgefallen,
allerdings ist die Induktion nach der Relationenbeschreibung der Prozedur in der Regel weniger aufwändig als die Induktion nach der Relationenbeschreibung der Datenstruktur.

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: Übung 6

Beitrag von robert.n »

Dürfen wir auch in der Klausur auf diese Weise vorgehen?

//EDIT:
Und woraus genau besteht \(\large \varepsilon_P\)? Dieses Objekt taucht das erste mal in Kapitel 2 auf, aber ich kann mit den dortigen Informationen in diesem Zusammhang nichts anfangen.
"... beschreibt allgemein eine Beziehung (formal: Relation) zwischen den Ein- und Ausgaben des Programms P". Was kann ich mir im Zusammenhang mit den Beweisen aus bspw. 6.2) darunter vorstellen? Es wird ja mehrfach argumentiert "mit \(\large \varepsilon_P\) folgt (...)".

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Re: Übung 6

Beitrag von Simon Siegler »

robert.n hat geschrieben:Dürfen wir auch in der Klausur auf diese Weise vorgehen?
Da wir diesen Fehler in der Klausur nicht wiederholen werden, können Sie in der Klausur den Induktionsbeweis einfach nach der jeweils angegebenen Relationenbeschreibung führen.
robert.n hat geschrieben: Und woraus genau besteht \(\large \varepsilon_P\)? Dieses Objekt taucht das erste mal in Kapitel 2 auf, aber ich kann mit den dortigen Informationen in diesem Zusammhang nichts anfangen.
"... beschreibt allgemein eine Beziehung (formal: Relation) zwischen den Ein- und Ausgaben des Programms P". Was kann ich mir im Zusammenhang mit den Beweisen aus bspw. 6.2) darunter vorstellen? Es wird ja mehrfach argumentiert "mit \(\large \varepsilon_P\) folgt (...)".
Vermutlich meinen Sie \(\mathcal{E}_P\). Dieses Symbol wird im Skript leider an zwei Stellen mit völlig verschiedenen Bedeutungen verwendet: In Kapitel 2 wie von Ihnen beschrieben und ab Kapitel 11 als \(\mathcal{E}_P := \{\forall x,y:\tau.\;eq_{\tau}(x,y) \equiv true \leftrightarrow x \equiv y \,|\, \text{Typ } \tau \text{ ist in }P\text{ definiert}\}\cup\{\forall x:bool.\;x \equiv true \lor x \equiv false\}\). Die Übungsaufgaben beziehen sich nur auf die letztere Verwendung.

Antworten

Zurück zu „Archiv“