Az elsőrendű logika töredékei

Eredeti címe:

Fragments of First-Order Logic

Könyv tartalma:

Az elsőrendű logika egy mondata kielégíthető, ha valamilyen struktúrában igaz, és véges kielégíthető, ha valamilyen véges struktúrában igaz. Felmerül a kérdés, hogy létezik-e algoritmus annak meghatározására, hogy egy adott elsőrendű logikai formula kielégíthető, vagy éppen végesen kielégíthető.

Erre a kérdésre 1936-ban Church és Turing (a kielégíthetőségre), 1950-ben pedig Trakhtenbrot (a véges kielégíthetőségre) adott nemleges választ. Ezzel szemben a kielégíthetőségi és a véges kielégíthetőségi problémák algoritmikusan megoldhatók az elsőrendű logika korlátozott részhalmazaira - vagy, ahogy mi mondjuk, töredékeire -, ami ma jelentős érdeklődésre tart számot az informatikában. Ez a könyv naprakész áttekintést nyújt a kutatás fő tengelyeiről, feltérképezi az elsőrendű logikában való döntés határait, és feltárja a kifejezőerő és az érvelés bonyolultsága közötti kompromisszumot.

A három részre osztott könyv azt vizsgálja, hogy az elsőrendű logika mely töredékeire létezik hatékony módszer a kielégíthetőség vagy véges kielégíthetőség meghatározására.

Továbbá, ha ezek a problémák eldönthetők valamilyen töredékre, mekkora a számítási komplexitásuk? Az I. rész a rendelkezésre álló formulák halmazának szűkítésével meghatározott töredékekre összpontosít.

A tárgyalt témák közé tartozik az arisztotelészi szillogisztika és rokonai, a kétváltozós töredék, az őrzött töredék, a kvantor-prefixumos töredékek és a fodrozott töredék. A II. rész a számláló kvantorokkal rendelkező logikákat vizsgálja.

Az arisztotelészi szillogisztika De Morgan-féle numerikus általánosításával kezdve haladunk a kétváltozós töredék számoló kvantorokkal és annak őrzött altöredékével, kifejtve az utóbbi alkalmazását a strukturált adatokra vonatkozó lekérdezésválaszolás problémájára. A III. rész a szemantikai megszorításokkal jellemezhető logikákkal foglalkozik, amelyek korlátozzák bizonyos predikátumok elérhető értelmezéseit.

A propozicionális modális logikát és a gradált modális logikát véve alapul, visszatérünk a kétváltozós elsőrendű logika és rokonainak kielégíthetőségi problémájához, de ezúttal bizonyos megkülönböztetett bináris predikátumokkal, amelyek értelmezése ekvivalencia- vagy tranzitív relációként korlátozva van. A művet a tulajdonképpeni elsőrendű logika határait kissé átlépve a fákon értelmezett logikákról szóló fejezet zárja.