Completeness

Vollständigkeit ist eine Eigenschaft formaler Systeme bzw. Kalküle. Man unterscheidet semantische Vollständigkeit („Alles, was wahr ist, ist beweisbar.“), klassische Vollständigkeit („Eine der zwei Aussagen \mathit A\, und \neg A ist stets beweisbar.“) und syntaktische Vollständigkeit („Wird eine nicht beweisbare Aussage als Axiom verwendet, so ist die Widerspruchsfreiheit verletzt, d.h. alles wird beweisbar.“).

Semantische Vollständigkeit ist das Pendant zur Korrektheit, in dem Sinn, dass ein Kalkül korrekt ist, wenn jede in ihm beweisbare (ableitbare) Aussage gilt („Alles, was beweisbar ist, ist wahr.“) Ein korrekter Kalkül ist insbesondere widerspruchsfrei, denn in einem Kalkül, der nicht widerspruchsfrei ist, d. h. in dem ein Widerspruch beweisbar ist, ist insbesondere alles, was falsch ist, beweisbar. Wenn ein Kalkül korrekt und vollständig ist, können in ihm genau alle wahren Aussagen abgeleitet werden.

Kurt Gödel bewies, dass die Prädikatenlogik erster Stufe nicht nur korrekt, sondern auch vollständig ist (Gödelscher Vollständigkeitssatz). Er bewies weiter, dass alle Systeme, die so mächtig sind wie die Arithmetik, entweder nicht vollständig oder nicht widerspruchsfrei sind, sowie dass sich Vollständigkeit und Widerspruchsfreiheit eines solchen Systems nicht innerhalb des Systems selbst beweisen lassen (siehe Gödelscher Unvollständigkeitssatz). Ähnliches folgt aus der von Alan Turing formal bewiesenen Unlösbarkeit des Halteproblems.

Funktionale Vollständigkeit von Junktoren

Mit funktionaler Vollständigkeit bezeichnet man die Eigenschaft einer Menge von Junktoren eines logischen Systems, alle Junktoren des Systems darstellen zu können. In der klassischen Aussagenlogik ist zum Beispiel die Junktorenmenge \{\and, \neg\} funktional vollständig, d. h. es lassen sich alle denkbaren Junktoren alleine aus Konjunktion und Negation ausdrücken.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Completeness — Com*plete ness, n. The state of being complete. [1913 Webster] …   The Collaborative International Dictionary of English

  • completeness — index conclusion (outcome), entirety, fait accompli, finality, quorum, totality, whole Burton s Legal …   Law dictionary

  • Completeness — In general, an object is complete if nothing needs to be added to it. This notion is made more specific in various fields. Contents 1 Logical completeness 2 Mathematical completeness 3 Computing 4 …   Wikipedia

  • Completeness — (Roget s Thesaurus) < N PARAG:Completeness >N GRP: N 1 Sgm: N 1 completeness completeness &c. >Adj. Sgm: N 1 completion completion &c. 729 Sgm: N 1 integration integration Sgm: N 1 allness allness GRP: N 2 Sgm …   English dictionary for students

  • completeness — complete ► ADJECTIVE 1) having all the necessary or appropriate parts; entire. 2) having run its full course; finished. 3) to the greatest extent or degree; total. 4) skilled at every aspect of an activity: the complete footballer. 5) (complete… …   English terms dictionary

  • completeness — noun see complete I …   New Collegiate Dictionary

  • completeness — See completely. * * * Concept of the adequacy of a formal system that is employed both in proof theory and in model theory (see logic). In proof theory, a formal system is said to be syntactically complete if and only if every closed sentence in… …   Universalium

  • completeness — noun the state or condition of being complete Ant: incompleteness …   Wiktionary

  • completeness — Intuitively, a logical system is complete if everything that we want can be derived in it. Thus a formalization of logic is complete if all logically valid forms of argument are derivable in the system; a system designed to codify mathematical… …   Philosophy dictionary

  • completeness — (Roget s Thesaurus II) noun The state of being entirely whole: entirety, integrity, oneness, totality, wholeness. See PART …   English dictionary for students


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.