Propagacja jednostki

Propagacja jednostek ( UP ) lub propagacja ograniczeń boolowskich ( BCP ) lub reguła jednoliterowa ( OLR ) to procedura zautomatyzowanego dowodzenia twierdzeń , która może uprościć zestaw klauzul (zwykle zdaniowych ) .

Definicja

Procedura jest oparta na klauzulach jednostkowych , tj. klauzulach składających się z pojedynczego literału , w koniunkcyjnej postaci normalnej. Ponieważ każda klauzula musi być spełniona, wiemy, że ten literał musi być prawdziwy. Jeśli zestaw klauzul zawiera klauzulę jednostkową , pozostałe klauzule są uproszczone przez zastosowanie dwóch następujących zasad: ${\ displaystyle l}$

$jest$ $jest$ niż sama klauzula jednostkowa) zawierająca usuwana (klauzula jest spełniona, jeśli );
w każdej klauzuli, która zawiera $}$ $\ neg$ ten literał jest usuwany ( może przyczynić się do jego spełnienia).

Zastosowanie tych dwóch zasad prowadzi do powstania nowego zestawu klauzul, który jest równoważny ze starym.

Na przykład następujący zestaw klauzul można uprościć przez propagację jednostek, ponieważ zawiera klauzulę unit ${\ displaystyle a}$ .

\ Displaystyle \ {a \ vee b, \ neg a \ vee c, \ neg c \ vee d, a \}}

Ponieważ $,$ tę $można$ całkowicie usunąć Ponieważ $usunąć$ negację literału w zdaniu jednostkowym, ten literał można Klauzula jednostkowa ${\ displaystyle a}$ nie jest usuwany; spowodowałoby to, że wynikowy zestaw nie byłby równoważny z oryginalnym; ta klauzula może zostać usunięta, jeśli jest już przechowywana w innej formie (patrz sekcja „Korzystanie z modelu częściowego”). Efekt propagacji jednostek można podsumować w następujący sposób.

${\ Displaystyle \ {}$	${\ Displaystyle a \ vee b,}$	${\ Displaystyle \ neg a \ vee c,}$	${\ Displaystyle \ neg c \ vee re,}$	${\ displaystyle a}$	${\ styl wyświetlania \}}$
	(REMOVED)	( ${\ Displaystyle \ neg a}$ usunięte)	(bez zmian)	(bez zmian)
${\ Displaystyle \ {}$		${\ displaystyle c,}$	${\ Displaystyle \ neg c \ vee re,}$	${\ displaystyle a}$	${\ styl wyświetlania \}}$

$_$ klauzul _ Nowa klauzula jednostkowa $,$ $d}$ $displaystyle$ , co przekształciłoby w .

Propagacja i rozdzielczość jednostek

Drugą zasadę propagacji jednostek można postrzegać jako ograniczoną formę rozwiązania , w której jeden z dwóch rozwiązań musi być zawsze klauzulą jednostkową. Jeśli chodzi o rozdzielczość, propagacja jednostek jest poprawną regułą wnioskowania, ponieważ nigdy nie tworzy nowej klauzuli, która nie wynikała ze starych. Różnice między propagacją jednostek a rozdzielczością są następujące:

rozdzielczość jest pełną procedurą odrzucania, podczas gdy propagacja jednostek nie jest; innymi słowy, nawet jeśli zestaw klauzul jest sprzeczny, propagacja jednostek może nie generować niespójności;
dwóch klauzul, które zostały rozwiązane, generalnie nie można usunąć po dodaniu wygenerowanej klauzuli do zestawu; wręcz przeciwnie, klauzula niejednostkowa związana z propagacją jednostek może zostać usunięta, gdy do zbioru zostanie dodane jej uproszczenie;
rozdzielczość generalnie nie obejmuje pierwszej reguły stosowanej w propagacji jednostek.

Rachunki rozdzielczości, które obejmują subsumpcję, mogą modelować regułę pierwszą przez subsumpcję, a regułę drugą przez krok rozdzielczości jednostkowej, po którym następuje subsumpcja.

Propagacja jednostek, stosowana wielokrotnie podczas generowania nowych klauzul jednostkowych, jest kompletnym algorytmem spełnialności dla zbiorów zdaniowych klauzul Horna ; generuje również minimalny model dla zestawu, jeśli jest zadowalający: patrz spełnialność Horna .

Korzystanie z częściowego modelu

Klauzule jednostkowe, które występują w zbiorze klauzul lub mogą być z niego wyprowadzone, mogą być przechowywane w postaci modelu cząstkowego (ten model cząstkowy może zawierać również inne literały, w zależności od aplikacji). W tym przypadku propagacja jednostek odbywa się na podstawie literałów modelu częściowego, a klauzule jednostkowe są usuwane, jeśli ich literały znajdują się w modelu. W powyższym przykładzie klauzula jednostkowa ${\ displaystyle a}$ dodana do modelu częściowego; za uproszczenie zestawu klauzul przebiegałoby wówczas jak powyżej, z tą różnicą, że klauzula jednostkowa za $\ displaystyle a}$ jest teraz usuwany z zestawu. Otrzymany zestaw klauzul jest równoważny pierwotnemu przy założeniu ważności literałów w modelu cząstkowym.

Złożoność

Bezpośrednia implementacja propagacji jednostek zajmuje czas kwadratowy całkowitego rozmiaru zbioru do sprawdzenia, który jest zdefiniowany jako suma rozmiarów wszystkich klauzul, gdzie rozmiar każdej klauzuli jest liczbą zawartych w niej literałów.

Propagację jednostek można jednak przeprowadzić w czasie liniowym, przechowując dla każdej zmiennej listę klauzul, w których zawarty jest każdy literał. Na przykład powyższy zestaw można przedstawić, numerując każdą klauzulę w następujący sposób:

\ Displaystyle \ {1: a \ vee b, 2: \ neg a \ vee c, 3: \ neg c\vee d,4:a\}}

a następnie przechowywanie dla każdej zmiennej listy klauzul zawierających zmienną lub jej zaprzeczenie:

{\ Displaystyle a: 1 \ 2 \ 4}

{\ Displaystyle b: 1}

{\ Displaystyle c: 2 \ 3}

{\ Displaystyle d: 3}

Ta prosta struktura danych może być zbudowana w czasie liniowo w rozmiarze zbioru i pozwala bardzo łatwo znaleźć wszystkie klauzule zawierające zmienną. Propagację jednostek literału można przeprowadzić wydajnie, skanując tylko listę klauzul zawierających zmienną literału. Mówiąc dokładniej, całkowity czas wykonywania propagacji jednostek dla wszystkich klauzul jednostkowych jest liniowy w rozmiarze zestawu klauzul.

Zobacz też

Dowling, William F.; Gallier, Jean H. (1984), „Algorytmy czasu liniowego do testowania spełnialności zdań formuł Horna”, Journal of Logic Programming , 1 (3): 267–284, doi : 10.1016 / 0743-1066 (84) 90014- 1 , MR 0770156 .
H. Zhang i M. Stickel (1996). Wydajny algorytm propagacji jednostek. W Proceedings of the Four International Symposium on Artificial Intelligence and Mathematics .