Екі айнымалы логика - Two-variable logic

Жылы математикалық логика және Информатика, екі айнымалы логика болып табылады фрагмент туралы бірінші ретті логика қайда формулалар тек екеуінің көмегімен жазуға болады айнымалылар.[1] Бұл фрагмент әдетте онсыз зерттеледі функция белгілері.

Шешімділік

Сияқты екі айнымалы логикаға қатысты кейбір маңызды мәселелер қанағаттанушылық және соңғы қанағаттанушылық, болып табылады шешімді.[2] Бұл нәтиже екі айнымалы логика фрагменттерінің шешімділік қабілеттілігі туралы нәтижелерді жалпылайды, мысалы сипаттау логикасы; дегенмен, екі айнымалы логиканың кейбір фрагменттері әлдеқайда төмен есептеу күрделілігі олардың қанағаттанушылығы проблемалары үшін.

Керісінше, функционалды белгілері жоқ бірінші ретті логиканың үш айнымалы фрагменті үшін қанағаттанушылық шешілмейді.[3]

Сандық көрсеткіштер

Функционалдық таңбалары жоқ бірінші ретті логиканың екі айнымалы фрагменті тіпті қосылған кезде де шешілетіні белгілі санауыштар,[4] және осылайша бірегейліктің өлшемі. Бұл әлдеқайда күшті нәтиже, өйткені үлкен сандық мәндерді санау сол логикада көрінбейді.

Санақ кванторлары ақырлы айнымалы логиканың мәнерлілігін жақсартады, өйткені олар түйін бар деп айтуға мүмкіндік береді. көршілер, атап айтқанда . Сандық өлшемдерді есептемей айнымалылар бірдей формула үшін қажет.

Weisfeiler-Leman алгоритміне қосылу

Екі айнымалы логика мен Weisfeiler-Leman (немесе түстерді нақтылау) алгоритмі арасында берік байланыс бар. Екі графикті ескере отырып, кез-келген екі түйіннің түсі нақтыланған тұрақты түсте болады, егер олар бірдей болса типі, яғни олар екі айнымалы логикада бірдей формулаларды санаумен қанағаттандырады.[5]

Әдебиеттер тізімі

  1. ^ Л.Хенкин. Таңбалардың тек ақырғы санын қамтитын логикалық жүйелер, Есеп, Монреаль университетінің математика бөлімі, 1967 ж
  2. ^ Э.Градель, П.Г. Колаитис және М.Варди, Екі айнымалы бірінші ретті логикаға қатысты шешім туралы, Бюллетень символикалық логика, 3-том, No1 (наурыз, 1997), 53-69 бб.
  3. ^ Кахр, Эдуард Ф. Мур және Хао Ванг. Entscheidungsproblem ∀ ∃ жағдайына дейін азайтылды, 1962, олардың ∀ ∃ ∀ формулалары тек үш айнымалыны қолданатынын ескере отырып.
  4. ^ Э.Градель, М.Отто және Э.Розен. Санаумен екі айнымалы логика шешімді болып табылады., IEEE информатикадағы логика бойынша он екінші жылдық симпозиум материалдары, 1997 ж.
  5. ^ Гроэ, Мартин. «Сипаттамалық күрделілік теориясындағы ақырлы айнымалы логика». Symbolic Logic бюллетені 4.4 (1998): 345-398.