Czy rozstrzyganie propozycji jest kompletnym systemem dowodowym?

To pytanie dotyczy logiki zdań i wszystkie wystąpienia „rozstrzygania” należy interpretować jako „rozstrzyganie zdań”.

To pytanie jest bardzo proste, ale od dłuższego czasu mnie niepokoi. Widzę, że ludzie twierdzą, że rozwiązanie zdań jest kompletne, ale widzę też, że ludzie twierdzą, że rozwiązanie jest niepełne. Rozumiem sens niepełnej rozdzielczości. Rozumiem również, dlaczego ludzie mogą twierdzić, że jest kompletny, ale słowo „kompletny” różni się od sposobu, w jaki używa się go „opisując naturalne odliczenie lub rachunek różniczkowy”. Nawet kwalifikator „zakończone odrzucenie” nie pomaga, ponieważ formuły muszą znajdować się w CNF, a przekształcenie formuły w równoważną formułę CNF lub równoważną formułę CNF poprzez transformację Tseityny nie jest uwzględniane w systemie dowodu.

Solidność i kompletność

Przyjmijmy ustawienie klasycznej logiki zdaniowej z relacją między jakimś wszechświatem struktur a zbiorem formuł i klasycznym Tarskimskim pojęciem prawdy w strukturze. Piszemy jeśli jest prawdziwe we wszystkich rozważanych strukturach. również systemowy system do uzyskiwania formuł z formuł. $\models$ $\models \varphi$ $\varphi$ $\vdash$

System jest dźwięk w stosunku do jeśli kiedykolwiek mamy , mamy także . System jest kompletny w odniesieniu do jeśli kiedykolwiek mamy , mamy również . $\vdash$ $\models$ $\vdash \varphi$ $\models \varphi$ $\vdash$ $\models$ $\models \varphi$ $\vdash \varphi$

Reguła rozstrzygania

Dosłowność to twierdzenie atomowe lub jego negacja. Klauzula jest rozłączeniem literałów. Formuła w CNF jest połączeniem zdań. Reguła rozstrzygania tego potwierdza

Reguła rozstrzygania stwierdza, że jeśli połączenie klauzuli z klauzulą jest zadowalające, klauzula musi być również zadowalająca. $C \lor p$ $\neg p \lor D$ $C \lor D$

Nie jestem pewien, czy sama reguła rozstrzygania może być rozumiana jako system dowodowy, ponieważ nie ma reguł wprowadzania formuł. Zakładam, że potrzebujemy przynajmniej reguły hipotezy, która umożliwia wprowadzenie klauzul.

Niekompletność rozdzielczości

Wiadomo, że rozdzielczość jest dźwiękoszczelnym systemem. Czyli, jeśli możemy czerpać klauzuli ze wzoru stosując rozdzielczość, a następnie . Rozdzielczość jest także całkowitym odrzuceniem, co oznacza, że jeśli mamy , możemy uzyskać z za pomocą rozdzielczości. $C$ $F$ $\models F \implies C$ $\models F \implies \bot$ $\bot$ $F$

Rozważ formułę

$\varphi := p \land q$ i . $\psi := p \lor q$

W systemie Gentzen LK lub przy użyciu naturalnej dedukcji mogę wywnioskować implikację całkowicie w systemie dowodowym. Nie mogę wywnioskować tej implikacji przy użyciu rozdzielczości, ponieważ jeśli zacznę od , nie będzie żadnych rozwiązań. $\varphi \implies \psi$ $\varphi$

Widzę, jak mogę udowodnić ważność tej implikacji za pomocą rozwiązania:

Rozważ formułę $\neg (\varphi \implies \psi)$
Przekształć powyższy wzór w CNF, stosując standardowe reguły dystrybucji lub transformację Tseityny
Wyprowadź z przekształconej formuły przy użyciu rozdzielczości. $\bot$

To podejście jest dla mnie niezadowalające, ponieważ wymaga ode mnie wykonania kroków (1) i (2), które są poza systemem kontroli rozdzielczości. Wydaje się więc, że istnieje bardzo wyraźny sens, w którym rozdzielczość nie jest kompletna w sposób, w jaki mówimy, że naturalna dedukcja lub sekwencyjne rachunki są kompletne.

pytania

Biorąc powyższe pod uwagę, moje pytania są następujące:

Jaki system dowodowy jest brany pod uwagę przy omawianiu rozwiązania? Czy to tylko reguła rozdzielczości? Jakie są inne zasady?
Wydaje mi się bardzo jasne, że rozdzielczość nie jest kompletna w tym sensie, że naturalne odliczenie i kolejne rachunki są kompletne. Czy literatura stwierdzająca, że rozwiązanie jest kompletną terminologią nadużyć tylko dlatego, że sens, w którym rozwiązanie jest zakończone, jest bardziej interesujący niż sens, w którym jest niepełny?
Czy ta różnica w pojęciach kompletności w odniesieniu do rozwiązania i innych kwestii oraz jak je pogodzić została omówiona bardziej szczegółowo w literaturze?
Zdaję sobie również sprawę z tego, że rozdzielczość można sformułować w ramach kolejnych rachunków pod względem reguły cięcia. Czy „słuszny” dowód teoretyczny rozdzielczości jest taki, że jest to fragment rachunku różniczkowego, który wystarcza do sprawdzenia poprawności formuł w CNF?

lo.logic terminology proof-complexity proof-theory resolution Vijay D.
źródło

(1) Formuły CNF z samą rozdzielczością (lub, jeśli robisz QBF, to formuły QCNF z rozdzielczością i całkowitą redukcją); (2) Tak, jest to obalenie zakończone i wciąż nieco inne znaczenie, mianowicie jeśli to .

ψ ⊨ ⊥

$\psi\models\bot$

ψ ⊢ ⊥

$\psi\vdash\bot$

Radu GRIGore

z grubsza podobne pytanie tutaj. dzięki za wysłanie. Zasadniczo IIUC / AFAIK, rozdzielczość jest używana do systemów o wiele więcej niż logiki 1. rzędu, ale w logice 1st order to „dźwięk / kompletna”, mimo że nie zawsze jest bardzo dobrze opisane, ponieważ często jest to po prostu wykorzystywane do dowodów odrzucenia. w „większych” systemach, w których terminy nie są jedynie zmiennymi boolowskimi, ale np. kwalifikatorami egzystencjalnymi itp., nie jest ono kompletne. dziedzina logiki nie ujednolica zbyt dobrze definicji terminologii, istnieje wiele „przeciążeń” terminów itp.

vzn

Dlatego niektórzy mówią, że jest „ refutationally kompletna”, np L. Bachmair i H. Ganzinger „Rozdzielczość dowodzenie twierdzen,” Handbook of automatycznego wnioskowania, vol. 1, ss. 19–99, 2001.

Trylks,

Pytanie dotyczy kompletności obalającej.

Vijay D

Odpowiedzi:

Jaki system dowodowy jest brany pod uwagę przy omawianiu rozwiązania? Czy to tylko reguła rozdzielczości? Jakie są inne zasady?

Rozwiązanie omawiam w kontekście „klauzul”, które są sekwencjami złożonymi wyłącznie z literałów . Klasyczna klauzula wyglądałaby jak Ale możemy ją również zapisać jako

{ZA}_{1}, \dots, {ZA}_{n} \to b_{1}, \dots, b_{m}

$A_1,\ldots,A_n \to B_1,\ldots,B_m$

pracować tylko z jednostronnymi sekwencjami. Jest konwencjonalnym leczeniu tych jednostronna sequents jakmultisetsz literałów.

\to {\bar{ZA}}_{1}, \dots, {\bar{ZA}}_{n}, b_{1}, \dots, b_{m}

${} \to \bar{A}_1,\ldots,\bar{A}_n, B_1, \ldots, B_m$

LK ograniczony do klauzul ma tylko cztery reguły wnioskowania:

tożsamość
cut (rozdzielczość propozycji)
skurcz (faktoring propozycyjny)
osłabiający

Oczywiste jest, że te cztery reguły są kompletne do dedukcji klauzul, tj.

Propozycja 1 Dla każdego pkt i zestaw klauzul mamy tylko wtedy, gdy . $C$ ${\cal S}$ ${\cal S} \models C$ ${\cal S} \vdash C$

${\cal S} \vdash C$ ${\cal S} \cup N(C) \vdash \bot$ $N(C) = \{\{\bar{A}\} \mid A \in C\}$ $C$

Oczywiste jest, że wtedy i tylko wtedy, gdy . Nasz system czterech reguł jest nadal odpowiedni do udowodnienia przekonwertowanego problemu, ale zauważamy, że nie potrzebujemy już tożsamości i osłabiania. Pozostałe dwie zasady nazywane są „procedurą potwierdzającą rozdzielczość”. ${\cal S} \vdash C$ ${\cal S} \cup N(C) \vdash \bot$

Twierdzenie 2 Dla każdej klauzuli i zestawu klauzul mamy $C$ ${\cal S}$ ${\cal S} \models C$ wtedy i tylko wtedy, gdy używa tylko cięcia i skurczu. ${\cal S} \cup N(C) \vdash \bot$

Problem konwersji problemu na dowody odrzucenia jest dwojaki:

Mamy lepszą okazję, aby poprowadzić wyszukiwanie dowodu, pozwalając prowadzić. $N(C)$
Mamy do czynienia z pełną logiką predykatów, której formuły można przekształcić do CNF aż do zadowalania.

Czy „słuszny” dowód teoretyczny rozdzielczości jest taki, że jest to fragment rachunku różniczkowego, który wystarcza do sprawdzenia poprawności formuł w CNF?

W rzeczy samej!

Uday Reddy
źródło

Dzięki Uday. Jedno pytanie: reguła cięcia nadal zachowuje w konsekwencji klauzule z oryginalnej formuły. W rozdzielczości są one „zoptymalizowane”, z konsekwencją tylko jednej klauzuli. Czy zgodziłbyś się, że ta rozdzielczość jest minimalną lub lokalną regułą, ponieważ wszystkie klauzule nie występują w regule?

Vijay D

@VijayD. Używamy dokładnie reguły cięcia, ale w inny sposób niż Gentzen. Dowody Gentzen miałyby formę

⊢ C

${} \vdash C$

S ⊢ C

${\cal S} \vdash C$

czy mógłbyś również dodać do swojej odpowiedzi coś, co według ciebie jest jednym zdaniem, dokładnym opisem kompletności rozwiązania?

Vijay D

@VijayD. W mojej pierwotnej odpowiedzi były dwa stwierdzenia „jeśli i tylko jeśli”, które były dwiema właściwościami kompletności. Dla jasności zobowiązałem je jako propozycje dla ciebie. (Nie jestem jeszcze pewien, gdzie leży twoje zamieszanie. Być może ma to związek z tym językiem, z którym pracujemy, jak sugerował Kaveh?)

Uday Reddy

@VijayD. Nie sądzę, aby można powiedzieć, że rozdzielczość jest „niekompletna”. W swoim pierwotnym pytaniu powiedziałeś tylko, że transformacje konieczne do przekształcenia formuł zdań w klauzulę są dla ciebie „niezadowalające”. Nie oznacza to, że są „niekompletne”.

Uday Reddy

1)

Jedyną regułą niestrukturalną jest rozdzielczość (atomów).

\frac{φ \lor do, ψ \lor \bar{do}}{φ \lor ψ}

$\varphi\lor C, \psi\lor \overline{C} \over \varphi\lor \psi$

Jednak sama reguła nie daje systemu dowodowego. Zobacz część 3.

2)

$\{\land, \lor, \lnot\}$ $\{\land, \lor, \lnot\}$

O ile istnieje „ładne” tłumaczenie z jednego języka na inny, możemy mówić o kompletności. Najważniejsze jest to, że możemy tłumaczyć formuły z jednego na drugi i na odwrót, skutecznie. Możesz sprawdzić tezę Roberta Reckhow'a, w której zajmuje się kwestią łączności i pokazuje, że w systemach Frege długość dowodów nie zmienia się bardziej niż wielomian, więc w pewnym sensie można wybrać dowolny zestaw odpowiednich łączników, które ci się podobają.

Sytuacja dla rozwiązania jest podobna. Poprzez redukcję z SAT do 3SAT możemy ograniczyć naszą uwagę do CNF, a transformacja może być wykonana bardzo skutecznie.

Zwróć uwagę, że tutaj nie ma rozwiązania problemu, problem dotyczy także innych systemów sprawdzających. Weźmy na przykład Frege o ograniczonej głębokości, gdzie głębokość formuł musi być ograniczona stałą, więc z definicji nie może udowodnić żadnych rodzin formuł o nieograniczonej głębokości.

3)

$P$ $\vdash_P$

$\vdash_P$ $\varphi$ $\pi$ $\pi$ $P$ $\varphi$
$P$ $\varphi$ $\varphi$
$\varphi$ $P$ $\varphi$

Definicja jest bardzo ogólna i wcale nie mówi o strukturze dowodu. Wszystko, co spełnia te warunki, jest systemem dowodu zdaniowego.

Jaką klasę formuły powinniśmy wziąć pod uwagę w tych przedmiotach? Rozważono różne klasy formuł, a pierwszym podejściem do znanego mi problemu jest teza Roberta Reckhow'a, w której pokazuje on, że dopóki interesuje się systemami Frege, nie ma znaczenia, jakiego odpowiedniego zestawu łączników używa każdy z nich są równoważne.

Jeśli chodzi o rozdzielczość, jeśli naprawdę chcemy mieć kompletność wszystkich formuł, a nie tylko CNF, można bez problemu włączyć stałe tłumaczenie wielomianowe z dowolnych formuł do CNF, ponieważ tłumaczenie jest obliczalne w czasie wielomianowym.

$\pi$ $\bot$ $\lnot \varphi$

4)

Rozdzielczość jest w porządku, ale tak też można myśleć o tym, jak wspomniałeś, tj. Możemy oczywiście traktować ją jako zasadę cięcia, gdy formuła cięcia jest dodatnimi atomami, przenosząc atomy ujemne do poprzednika i utrzymując pozytywne w sukcesie:

\frac{\Rightarrow φ, do do \Rightarrow ψ}{\Rightarrow φ, ψ}

$\Rightarrow \varphi, C \hspace{1cm} C \Rightarrow \psi \over \Rightarrow \varphi, \psi$

$G$

ps: Moja odpowiedź pochodzi głównie z teoretycznej złożoności dowodu. Możesz sprawdzić inne perspektywy, takie jak teoria dowodu strukturalnego .

Bibliografia:

Robert A. Reckhow, „ O długości dowodów w rachunku zdań ”, 1976.

Kaveh
źródło

Dziękuję za odpowiedź. Widzę, jak Uday mówi podobne rzeczy, ale stwierdziłem, że łatwiej mi było podążać za jego odpowiedzią.

Vijay D

@VijayD, oczywiście, nie ma problemu. :)

Kaveh