Zupełność

Zupełność – cecha obiektu, polegająca na tym, że nie trzeba niczego do niego dodawać. To znaczenie jest uściślane w wielu dziedzinach.

Zupełność w logice edytuj

W logice, semantyczna zupełność jest odwrotnością poprawności systemu formalnego. System formalny jest „semantycznie zupełny”, jeśli wszystkie tautologie są twierdzeniami, a „poprawny” gdy wszystkiego jego twierdzenia są tautologiami. Kurt Gödel, Leon Henkin, i Emil Post wszyscy opublikowali dowody zupełności. (Patrz Historia tezy Churcha–Turinga.) System nazywa się niesprzeczny, jeśli nie istnieje w nim dowód zarówno dla P, jak i zaprzeczenia P.

Dla systemu formalnego S w języku formalnym L, S jest semantycznie zupełny, lub po prostu zupełny wtedy i tylko wtedy, gdy, każdy logicznie poprawny wzór z L (każdy wzór będący prawdziwym w ramach każdej interpretacji L) jest twierdzeniem w S. To znaczy że, $\models _{\mathrm {S} }A\ \to \ \vdash _{\mathrm {S} }A$ ^[1].

System formalny S jest silnie zupełny, czy też inaczej mówiąc zupełny silnie, wtedy i tylko wtedy, gdy, dla każdego zbioru założeń T, każdy wzór wynikający semantycznie z T może zostać wyprowadzony z T. To znaczy, że $T\models _{\mathrm {S} }A\ \to \ T\vdash _{\mathrm {S} }A.$

System formalny S jest syntaktycznie zupełny, lub inaczej zupełny dedukcyjnie, czy też maksymalnie zupełny, albo po prostu zupełny wtedy i tylko wtedy, gdy, dla każdego wyrażenia A z języka danego systemu A albo ¬A jest twierdzeniem w S. Mówimy wtedy o zupełności zaprzeczeniowej. Innym słowy, system formalny jest syntaktycznie zupełny wtedy i tylko wtedy, gdy nie można dodać żadnego niewywodzącego się zeń aksjomatu bez wprowadzenia niedorzeczności. Logika z funkcją prawdy predykatów i rachunek predykatów pierwszego rzędu są semantycznie zupełne, lecz nie są syntaktycznie zupełne (np. wyrażenie rachunku zdaniowego składające się z jednej zmiennej „a” ani jego zaprzeczenie nie jest twierdzeniem, ale nie są to tautologie). Twierdzenie Gödla o niezupełności pokazuje że nie ma systemu rekurencyjnie będącego dostatecznie bogatym, tak jak aksjomatyka Peana, który byłby zarówno niesprzeczny, jak i zupełny.

System formalny jest niezupełny dokładnie gdy każde zdanie jest twierdzeniem^[2].

System funktorów zdaniotwórczych jest funkcjonalnie zupełny wtedy i tylko wtedy, gdy można w nim wyrazić wszystkie funkcje predykatywne.

Język jest wyrażeniowo zupełny jeśli można za jego pomocą opisać dziedzinę dla której został on przewidziany.

Język formalny jest zupełny odnośnie do pewnej właściwości wtedy i tylko wtedy, gdy każde zdanie posiadające daną cechę jest twierdzeniem.

Zupełność w matematyce edytuj

W matematyce, „zupełność” jest określeniem przyjmującym różne znaczenia w zależności od danego zagadnienia; nie w każdej sytuacji w której występuje „zupełność” mówi się o „zupełności”.

Przestrzeń metryczna (lub przestrzeń jednostajna) nazywamy zupełną, gdy każdy ciąg Cauchy’ego elementów tej przestrzeni jest zbieżny do pewnego jej punktu.
Miarę nazywamy zupełną, gdy każdy podzbiór zbioru miary zero, czyli każdy tzw. zbiór zaniedbywalny, jest mierzalny (i w konsekwencji miary zero).
Porządek częściowy nazywamy zupełnym, gdy każdy jego ograniczony z dołu podzbiór ma kres dolny.

Zupełność w informatyce edytuj

Dla algorytmów zupełność oznacza że dany algorytm znajduje rozwiązanie jeśli takowe istnieją, a w przeciwnym razie wskazuje brak istnienia rozwiązania.
W obliczeniowej teorii złożoności, problem P jest zupełny dla klasy złożoności C, pod pewnym rodzajem redukcji, jeśli P leży w C, i każdy problem z C da się sprowadzić do P używając danej redukcji. Na przykład każdy problem z klasy NP-zupełne jest zupełny dla klasy NP, jeśli jest redukowalny wielu-do-jednego w czasie wielomianowym.

Odniesienia edytuj

Logika matematyczna (pol.), Andrzej Mostowski niesprzeczność

Przypisy edytuj

↑ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Pres, 1971.
↑ Alfred Tarski, Über einige fundamentale Begriffe der Mathematik, Comptes Rendus des séances de la Société des Sciences et des Lettres de Varsovie 23 (1930), Cl. III, s. 22–29. Tłumaczenie na angielski: Alfred Tarski, Logic, Semantics, Metamathematics, Claredon Press, Oxford, 1956, s. 30–37.

[metalogic-1] Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Pres, 1971.

[2] Alfred Tarski, Über einige fundamentale Begriffe der Mathematik, Comptes Rendus des séances de la Société des Sciences et des Lettres de Varsovie 23 (1930), Cl. III, s. 22–29. Tłumaczenie na angielski: Alfred Tarski, Logic, Semantics, Metamathematics, Claredon Press, Oxford, 1956, s. 30–37.

[1]

[2]