Zupełność

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Ogólnie obiekt jest zupełny, gdy nie trzeba niczego do niego dodawać. To znaczenie jest uściślane w wielu dziedzinach.

Zupełność w logice[edytuj | edytuj kod]

W logice, semantyczna zupełność jest przeciwieństwem poprawności systemu formalnego. System formalny jest "semantycznie zupełny", jeśli wszystkie tautologietwierdzeniami, 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 Peano, 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]
  • 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 pewnej właściwości wtedy i tylko wtedy, gdy każde zdanie posiadające daną cechę jest twierdzeniem.

Zupełność w matematyce[edytuj | edytuj kod]

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".

Zupełność w informatyce[edytuj | edytuj kod]

  • 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 reukowalny wielu-do-jednego w czasie wielomianowym.

Odniesienia[edytuj | edytuj kod]

Przypisy

  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, pp. 22–29. Tłumaczenie na angielski: Alfred Tarski, Logic, Semantics, Metamathematics, Claredon Press, Oxford, 1956, pp. 30–37.