Was würdet ihr antworten auf: "Erklären Sie die Begriffe Korrektheit und Vollständigkeit allgemein"?
ein Prädikat P auf eine Menge M ist bekannt (nicht unbedingt entscheidbar)
gesucht ist ein Verfahren, das bestimmt ob ein Element aus M P erfüllt,
(auch nicht unbedingt entscheidbar)
das Verfahren berechnet das Prädikat P2,
zunächst gibt es keine Aussage ob dieses mit P übereinstimmt,
Ziel ist also P(x) <-> P2(x)
(oder zumindest P(x) -> P2(x) oder P(x) <- P2(x))
das Verfahren gilt (im Sinne der Verwendung) als korrekt wenn
P2(x) -> P(x)
das Verfahren gilt (im Sinne der Verwendung) als vollständig wenn
P2(x) <- P(x)
oder sprachlicher ;)
diese Begriffe charakterisieren ein Verfahren zur Bestimmung der Eigenschaft X von Elementen einer Menge,
das Verfahren ist korrekt,
wenn nur Elemente mit der Eigenschaft X den Test erfolgreich durchlaufen
das Verfahren ist vollständig,
wenn alle Elemente mit der Eigenschaft X den Test erfolgreich durchlaufen