Двухвариантная логика - Two-variable logic

В математическая логика и Информатика, двухвариантная логика это фрагмент из логика первого порядка куда формулы можно написать, используя только два разных переменные.^[1] Этот фрагмент обычно изучается без функциональные символы.

Разрешимость

Некоторые важные проблемы, связанные с логикой двух переменных, например выполнимость и конечная выполнимость, находятся разрешимый.^[2] Этот результат обобщает результаты о разрешимости фрагментов логики двух переменных, таких как некоторые логика описания; однако некоторые фрагменты логики с двумя переменными пользуются гораздо меньшим вычислительная сложность за их проблемы с выполнимостью.

Напротив, для фрагмента логики первого порядка с тремя переменными без функциональных символов выполнимость неразрешима.^[3]

Подсчет кванторов

Фрагмент логики первого порядка с двумя переменными без функциональных символов, как известно, разрешим даже с добавлением подсчет кванторов,^[4] и таким образом количественная оценка уникальности. Это более сильный результат, поскольку счетные кванторы для высоких числовых значений не выражаются в этой логике.

Кванторы подсчета фактически улучшают выразительность логики с конечными переменными, поскольку они позволяют сказать, что существует узел с ${ displaystyle n}$ соседи, а именно ${ Displaystyle Phi = существует х существует ^ { geq n} yE (x, y)}$ . Без подсчета кванторов ${ displaystyle n + 1}$ переменные необходимы для той же формулы.

Подключение к алгоритму Вайсфейлера-Лемана

Между логикой двух переменных и алгоритмом Вайсфейлера-Лемана (или уточнения цвета) существует тесная связь. Учитывая два графа, любые два узла имеют одинаковый стабильный цвет при улучшении цвета тогда и только тогда, когда они имеют одинаковые ${ displaystyle C ^ {2}}$ типа, то есть они удовлетворяют одним и тем же формулам в логике двух переменных со счетом.^[5]

Рекомендации

^ Л. Хенкин. Логические системы, содержащие только конечное число символов, Отчет, факультет математики Монреальского университета, 1967 г.
^ Э. Грэдель, П.Г. Колайтис и М. Варди, К проблеме решения для логики первого порядка с двумя переменными, Бюллетень символической логики, Том 3, № 1 (март 1997 г.), стр. 53-69.
^ А. С. Кар, Эдвард Ф. Мур и Хао Ван. Entscheidungspro Проблема сведена к ∃ ∀ случаю, 1962, отметив, что в их формулах ∃ ∀ используются только три переменные.
^ Э. Гредель, М. Отто и Э. Розен. Логика с двумя переменными со счетом разрешима., Материалы двенадцатого ежегодного симпозиума IEEE по логике в компьютерных науках, 1997 г.
^ Grohe, Мартин. «Логики конечных переменных в описательной теории сложности». Бюллетень символической логики 4.4 (1998): 345-398.

Этот логика -связанная статья является заглушка. Вы можете помочь Википедии расширяя это.

Этот Информатика статья - это заглушка. Вы можете помочь Википедии расширяя это.

[1] Л. Хенкин. Логические системы, содержащие только конечное число символов, Отчет, факультет математики Монреальского университета, 1967 г.

[2] Э. Грэдель, П.Г. Колайтис и М. Варди, К проблеме решения для логики первого порядка с двумя переменными, Бюллетень символической логики, Том 3, № 1 (март 1997 г.), стр. 53-69.

[3] А. С. Кар, Эдвард Ф. Мур и Хао Ван. Entscheidungspro Проблема сведена к ∃ ∀ случаю, 1962, отметив, что в их формулах ∃ ∀ используются только три переменные.

[4] Э. Гредель, М. Отто и Э. Розен. Логика с двумя переменными со счетом разрешима., Материалы двенадцатого ежегодного симпозиума IEEE по логике в компьютерных науках, 1997 г.

[5] Grohe, Мартин. «Логики конечных переменных в описательной теории сложности». Бюллетень символической логики 4.4 (1998): 345-398.

[1]

[2]

[3]

[4]

[5]