Skolem postać normalna

W logice matematycznej formuła logiki pierwszego rzędu jest w postaci normalnej Skolema, jeśli jest w postaci normalnej prenex z tylko uniwersalnymi kwantyfikatorami pierwszego rzędu .

formułę pierwszego rzędu można przekształcić w postać normalną Skolema, nie zmieniając jej spełnialności w procesie zwanym Skolemizacją (czasami zapisywanym jako Skolemnizacja ). Otrzymana formuła niekoniecznie jest równoważna oryginalnej, ale jest z nią równoważna : jest spełnialna wtedy i tylko wtedy, gdy oryginalna jest spełnialna.

Redukcja do postaci normalnej Skolema to metoda usuwania kwantyfikatorów egzystencjalnych ze zdań logiki formalnej , często wykonywana jako pierwszy krok w automatycznym dowodzie twierdzeń .

Przykłady

Najprostsza forma Skolemizacji dotyczy egzystencjalnie skwantyfikowanych zmiennych, które nie mieszczą się w zakresie uniwersalnego kwantyfikatora. Można je zastąpić po prostu tworząc nowe stałe. Na przykład $Displaystyle \ istnieje x P (x)}$ $stałą$ $gdzie$ jest nową (nie wystąpić gdziekolwiek indziej we wzorze).

Mówiąc bardziej ogólnie, Skolemizacja jest wykonywana przez zastąpienie każdej egzystencjalnie określonej ilościowo zmiennej ${n})}$ $x_$ \ którego symbol funkcji $nowy$ . Zmienne tego terminu są następujące. Jeśli formuła jest w postaci normalnej prenex , to ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$ to zmienne, które są uniwersalnie kwantyfikowane i których kwantyfikatory poprzedzają kwantyfikatory ${\ displaystyle y}$ . Ogólnie rzecz biorąc, $\ istnieje y}$ to zmienne, które są kwantyfikowane uniwersalnie (zakładamy, że pozbywamy się kwantyfikatorów egzystencjalnych w kolejności, więc wszystkie kwantyfikatory egzystencjalne przed usunięte) i takie, że ${\ displaystyle$ występuje w zakresie ich kwantyfikatorów. Funkcja ${\ displaystyle f}$ wprowadzona w tym procesie nazywana jest funkcją Skolema (lub stałą Skolema , jeśli ma zerową wartość ), a termin nazywany jest terminem Skolema .

Na przykład wzór ${\ Displaystyle \ forall x \ istnieje y \ forall zP (x, y, z)}$ nie jest w normalnej postaci Skolema, ponieważ zawiera kwantyfikator egzystencjalny ${\ displaystyle \ istnieje y}$ . $Displaystyle$ zastępuje , gdzie $f (x)}$ ${\ Displaystyle y}$ y jest nowym symbolem funkcji i usuwa kwantyfikację ponad ${\ displaystyle y}$ . Otrzymany wzór to ${\ Displaystyle \ forall x \ forall zP (x, f (x), z)}$ . Termin $Skolem$ $zawiera$ ale \ $}$ $y}$ istnieje jest w zakresie ${\ displaystyle \ forall x}$ , ale nie w zakresie ${\ displaystyle \ forall z}$ ; ponieważ ta formuła jest w postaci normalnej prenex, jest to równoważne z powiedzeniem, że na liście kwantyfikatorów poprzedza ${\ displaystyle x}$ ${\ displaystyle y}$ podczas gdy ${\ displaystyle z}$ nie. Formuła uzyskana przez to przekształcenie jest spełnialna wtedy i tylko wtedy, gdy oryginalna formuła jest spełniona.

Jak działa Skolemizacja

Skolemizacja polega na zastosowaniu równoważności drugiego rzędu wraz z definicją spełnialności pierwszego rzędu. Równoważność umożliwia „przesunięcie” kwantyfikatora egzystencjalnego przed kwantyfikator uniwersalny.

{\ Displaystyle \ forall x \ istnieje yR (x, y) \ iff \ istnieje f \ forall xR (x, f (X))}

Gdzie

{\ displaystyle f (x)}

jest funkcją, która odwzorowuje na

displaystyle

y}

.

Intuicyjnie, zdanie „dla każdego $”$ taki , że $x$ jest konwertowane na równoważną formę „ $}$ funkcja $R$ każdy a $y$ $displaystyle$ $}$ tak, że posiada ${\ Displaystyle R (x, f (x))}$ .

Ta równoważność jest użyteczna, ponieważ definicja spełnialności pierwszego rzędu pośrednio egzystencjalnie kwantyfikuje ocenę symboli funkcyjnych. W szczególności $jest$ pierwszego rzędu zadowalająca, jeśli istnieje model $}$ ocena wolnych zmiennych formuły, które oceniają formułę na ${\ displaystyle \ mu$ prawda . Model zawiera ocenę wszystkich symboli funkcyjnych; dlatego funkcje Skolema są niejawnie kwantyfikowane egzystencjalnie. W powyższym przykładzie $x, f (x))}$ $f}$ jest spełniony wtedy i tylko wtedy, gdy istnieje model , który zawiera ocenę dla $M}$ $\ Displaystyle$ , takie, że ${\ Displaystyle \ forall xR (x, f (x))}$ jest prawdziwe dla niektórych ocen jego zmiennych wolnych (w tym przypadku żadnych). Można to wyrazić w drugim rzędzie jako ${\ Displaystyle \ istnieje f \ forall xR (x, f (x))}$ . Przez powyższą równoważność jest to to samo, co spełnialność ${\ Displaystyle \ dla wszystkich x \ istnieje yR (x, y)}$ .

Na poziomie meta spełnialność pierwszego rzędu wzoru $.$ zapisać z niewielkim nadużyciem zapisu ${\ Displaystyle \ istnieje M \ istnieje \ mu ~. ~ (M, \ mu \ modele \ Phi)}$ , gdzie ${\ Displaystyle M}$ jest modelem, ${\ Displaystyle \ mu}$ $to$ jest oceną wolnych zmiennych i oznacza ${\ Displaystyle \ Phi}$ jest prawdziwe w ${\ Displaystyle M}$ pod ${\ Displaystyle \ mu}$ . Ponieważ modele pierwszego rzędu zawierają ocenę wszystkich symboli funkcyjnych, każda funkcja Skolema, która $displaystyle$ , jest domyślnie kwantyfikowana egzystencjalnie przez $\ istnieje M}$ . W rezultacie, po zastąpieniu kwantyfikatorów egzystencjalnych nad zmiennymi kwantyfikatorami egzystencjalnymi nad funkcjami na początku formuły, formuła nadal może być traktowana jako kwantyfikator pierwszego rzędu poprzez usunięcie tych kwantyfikatorów egzystencjalnych. Ten ostatni krok leczenia ${\ Displaystyle \ istnieje f \ forall xR (x, f (x))}$ jako ${\ displaystyle \ forall xR (x, f (x))}$ może zostać uzupełniony, ponieważ funkcje są niejawnie kwantyfikowane egzystencjalnie przez ${\ displaystyle \ istnieje M}$ w definicji spełnialności pierwszego rzędu.

Poprawność skolemizacji można pokazać na przykładowym wzorze ${\ Displaystyle F_ {1} = \ forall x_ {1} \ kropki \forall x_{n}\exists yR(x_{1},\dots ,x_{n},y)}$ w następujący sposób. Ta formuła jest spełniona przez model wtedy i tylko wtedy, gdy dla każdej możliwej wartości dla ${\ displaystyle M}$ ${\ Displaystyle x_ {1}, \ kropki, x_ {n}}$ w dziedzinie modelu istnieje wartość dla ${\ Displaystyle y}$ w dziedzinie modelu, która sprawia, że ${\ Displaystyle R (x_ {1}, \ kropki, x_ {n}, y)}$ prawda. Zgodnie z $fa$ wyboru istnieje taka funkcja że ${\ Displaystyle y = f (x_ {1}, \ kropki, x_ {n})}$ . W rezultacie formuła ${\ Displaystyle F_ {2} = \ forall x_ {1 }\kropki \forall x_{n}R(x_{1},\kropki,x_{n},f(x_{1},\kropki,x_{n}))}$ jest zadowalający, ponieważ ma model uzyskany przez dodanie oceny do $}$ $\ displaystyle M$ . To pokazuje, że $tylko$ $jest$ wtedy, gdy . ${\ displaystyle F_ {2}$ , jeśli jest zadowalający, to istnieje model , który go spełnia; $}$ ten model zawiera ocenę funkcji ${\ Displaystyle f}$ takie, że dla każdej wartości ${\ Displaystyle x_ {1}, \ kropki, x_ {n}}$ , wzór ${\ Displaystyle R (x_ {1}, \ kropki, x_ {n}, f (x_ {1}, \ kropki, x_ {n})}$ } W rezultacie ${\ displaystyle F_ {1}$ jest spełniony przez ten sam model, ponieważ można wybrać dla każdej wartości ${\ Displaystyle x_ {1}, \ ldots, x_ {n}}$ , wartość ${\ Displaystyle y = f (x_ {1}, \ kropki, x_ {n})}$ , gdzie jest oceniany $Displaystyle$ z $M'}$ .

Zastosowania Skolemizacji

Jednym z zastosowań Skolemizacji jest zautomatyzowane dowodzenie twierdzeń . Na przykład w metodzie tablic analitycznych , ilekroć pojawia się formuła, której wiodącym kwantyfikatorem jest kwantyfikator egzystencjalny, można wygenerować formułę uzyskaną przez usunięcie tego kwantyfikatora za pomocą Skolemizacji. Na przykład, jeśli ${\ Displaystyle \ istnieje x. \ Phi (x, y_ {1}, \ ldots, y_ {n})}$ występuje w tableau, gdzie ${\ Displaystyle x, y_ {1}, \ ldots, y_ {n}}$ są wolnymi zmiennymi ${\ Displaystyle \ Phi (x, y_ { 1},\ldots ,y_{n})}$ , potem ${\ Displaystyle \ Phi (f (y_ {1}, \ ldots, y_ {n}), y_ {1}, \ ldots, y_ {n})}$ można dodać do tej samej gałęzi tablicy. To $dodanie nie$ spełnialności tableau: każdy model starej formuły można rozszerzyć, dodając odpowiednią ocenę do modelu nowej formuły.

Ta forma Skolemizacji jest ulepszeniem w stosunku do „klasycznej” Skolemizacji, ponieważ tylko zmienne, które są wolne we wzorze, są umieszczane w terminie Skolema. Jest to ulepszenie, ponieważ semantyka obrazów może pośrednio umieszczać formułę w zakresie niektórych uniwersalnie skwantyfikowanych zmiennych, których nie ma w samej formule; zmienne te nie występują w terminie Skolema, podczas gdy zgodnie z pierwotną definicją Skolemizacji byłyby tam. Innym ulepszeniem, które można zastosować, jest zastosowanie tego samego symbolu funkcji Skolema dla formuł, które są identyczne, aż do zmiany nazwy zmiennej.

Innym zastosowaniem jest metoda rozwiązywania logiki pierwszego rzędu , w której formuły są reprezentowane jako zestawy klauzul rozumianych jako powszechnie kwantyfikowane. (Na przykład patrz paradoks pijącego .)

Ważnym wynikiem w teorii modeli jest twierdzenie Lowenheima-Skolema, które można udowodnić poprzez Skolemizację teorii i zamknięcie pod wynikowymi funkcjami Skolema.

Teorie Skolema

Ogólnie rzecz biorąc, $}$ dla każdej formuły wolnymi zmiennymi $T$ symbol funkcji $się$ $który$ $jest$ udowodnioną funkcją Skolema dla nazywa teorią Skolema .

Każda teoria Skolema jest modelem kompletnym , tzn. każda podstruktura modelu jest podstrukturą elementarną . Biorąc pod uwagę model M teorii Skolema T , najmniejsza podstruktura zawierająca pewien zbiór A nazywana jest Skolemowym kadłubem A . Kadłub Skolema A jest atomowym modelem pierwszym nad A .