Неоднозначность и логика

17

В теории автоматов (конечных автоматов, автоматов с выталкиванием, ...) и в сложности существует понятие «неоднозначность». Автомат является неоднозначным, если существует слово по крайней мере, с двумя различными принимающими сериями. Машина является неоднозначной, если для каждого слова принятого машиной, существует не более различных прогонов, чтобы принять . $w$ $k$ $w$ $k$ $w$

Это понятие также определено для контекстно-свободных грамматик: грамматика неоднозначна, если существует слово, которое может быть получено двумя различными способами.

Также известно, что многие языки имеют хорошую логическую характеристику по сравнению с конечными моделями. (Если язык регулярный, существует монадическая формула второго порядка над словами, так что каждое слово из является моделью , аналогично NP, если эквивалентно формулам второго порядка, где все квантификаторы 2-го порядка являются экзистенциальными .) $L$ $\phi$ $w$ $L$ $\phi$

Следовательно, мой вопрос находится на краю двух областей: есть ли какой-либо результат или даже каноническое определение «неоднозначности» формул данной логики?

Я могу представить несколько определений:

$\exists x \phi(x)$ является неоднозначным, если существует не более одного такого, что выполняется и что является неоднозначным. $x$ $\phi(x)$ $\phi(x)$
$\phi_0\lor\phi_1$ будет неоднозначным, если существует модель как и , или если неоднозначна. $\phi_0$ $\phi_1$ $\phi_i$
Формула SAT была бы не однозначной, если существует не более одного правильного назначения.

Следовательно, мне интересно, является ли это общеизвестным понятием, иначе может быть интересно попытаться провести исследование по этой теме. Если это понятие известно, может ли кто-нибудь дать мне ключевые слова, которые я мог бы использовать для поиска информации по данному вопросу (поскольку «логическая неоднозначность» дает много несвязанных результатов), или ссылки на книгу / pdf / article?

lo.logic automata-theory regular-language nondeterminism finite-model-theory Артур МИЛКИОР
источник

11

Правила в грамматике и правила вывода в логике могут рассматриваться как производственные правила, которые дают нам «новый материал» из «известного материала». Точно так же, как может быть много способов создать (или проанализировать) слово по отношению к грамматике, так же может быть много способов создать (или доказать) логическую формулу. Эту аналогию можно провести дальше. Например, некоторые логические системы допускают нормальные формы доказательств. Точно так же некоторые грамматики допускают канонические деревья разбора.

Поэтому я бы сказал, что ваши примеры из логики идут не в ту сторону. Правильная аналогия

"дерево разбора": "слово" = "доказательство": "логическая формула"

Фактически, достаточно общий вид грамматики сможет выразить типичные логические правила логического вывода, так что грамматически правильные слова будут точно доказуемыми формулами. В этом случае разбор дерева будут на самом деле быть доказательством.

В противоположном направлении, если мы хотим придумать очень общие правила вывода (которые не обязательно имеют традиционный логический вкус), то каждая грамматика будет выражаться в виде системы аксиом (терминалов) и правил вывода (продукций). И еще раз мы увидим, что доказательство - это то же самое, что и дерево разбора.

Андрей Бауэр
источник

Я действительно не думал о доказательствах. Я более привык к (конечной) теории моделей. Мы заботимся о том, чтобы выяснить, какие наборы являются моделями формулы, а какие нет. (В частности, для формулы, какова сложность определения, является ли набор моделью или нет, и для доказуемой формулы, следовательно, тавтологии, сложность составляет O (1), поскольку все наборы являются моделями). Но большое спасибо за ваш ответ.

Артур МИЛЬЧИОР

2

Ну что ж, добавим аналогию: теория моделей - это логика, а семантика - языки. Теория моделей присваивает смысл логическим теориям, а семантика присваивает смысл языкам. Иногда лучше не смешивать яблоки и апельсины, даже если вы к этому привыкли.

Андрей Бауэр

7

Всего два замечания. Я надеюсь, что они помогают.

Стандартные определения семантики логики и истины следуют изложению Тарского, следуя по индукции к структуре формулы. Другая возможность состоит в том, чтобы дать основанную на игре семантику как предложено Hintikka. Истина и удовлетворенность - все это определяется стратегиями в игре. Для формул первого порядка можно доказать, что формула верна в понимании Тарского, если и только если в игре Hintikka существует выигрышная стратегия.

На пути к формализации вашего вопроса можно спросить, допускает ли игра несколько стратегий. Существует также интересный вопрос о том, должны ли стратегии быть детерминированными. Хинтикка требовала, чтобы они были детерминированными. Доказательство того, что оригинал Хинтикки и семантика Тарского эквивалентны, требует Аксиомы выбора. Можно также формализовать истину в терминах игр с недетерминированными стратегиями с меньшим количеством осложнений.

Ваш пример теории языка напомнил детерминизм, симуляционные отношения и принятие языка. Симуляция отношений между автоматами подразумевает включение языков между их языками, хотя обратное неверно. Для детерминированных автоматов оба понятия совпадают. Можно спросить, можно ли «плавно» расширить отношения симуляции, чтобы получить эквивалентность языка для недетерминированных автоматов. У Куши Этессами есть очень хорошая статья, показывающая, как это сделать с помощью k-симуляций ( Иерархия вычислимых симуляций за полиномиальное время для автоматов). Интуитивно понятно, что «k» отражает степень недетерминизма, которую может охватить отношение моделирования. Когда 'k' равен уровню недетерминизма в автомате, симуляция и эквивалентность языка совпадают. Эта статья также дает логическую характеристику k-моделирования в терминах полиадической модальной логики и ограниченного переменного фрагмента логики первого порядка. Вы получаете включение языка, детерминизм, игры, модальную логику и логику первого порядка, все в одном пакете бампера.

Виджай Д
источник

4

Это началось как комментарий под ответом Андрея Бауэра, но стало слишком большим.

Я думаю, что очевидное определение неоднозначности с точки зрения теории конечных моделей было бы: $ambiguous(\phi) \implies \exists M_1,M_2 | M_1 \vDash \phi \wedge M_2 \vDash \phi \wedge M_1 \vDash \psi \wedge M_2 \nvDash \psi$

На словах существуют различные модели вашей грамматики, закодированные как формула которые можно различить по некоторой формуле , возможно, под формулу . $\phi$ $\psi$ $\phi$

Вы можете связать это с ответом Андрея о доказательствах через описательную сложность. Сочетание существования кодировки конкретной модели плюс ее принятия соответствующей ТМ в качестве модели данной формулы является доказательством того, что аксиомы и выводы (и, следовательно, эквивалентная грамматика), закодированные в этой формуле, являются согласованными.

Чтобы сделать это полностью совместимым с ответом Андрея, вы должны сказать, что модель «генерируется» формулой, действующей в качестве фильтра на пространстве всех возможных конечных моделей (или чего-то подобного), с кодированием и действием фильтрации на входной модели в качестве «доказательства». Различные доказательства свидетельствуют о неоднозначности.

Возможно, это не популярное мнение, но я склонен думать о теории конечных моделей и теории доказательств как об одном и том же, что видно под разными углами зрения. ;-)

Марк Хаманн
источник

«Из твоей грамматики закодирована формула

», прошу прощения, я не понимаю. Вы имеете в виду «как формула». Насколько я могу судить, вы всегда можете выделить две разные конечные модели.

ϕ

$\phi$

Артур МИЛЬЧИОР

Да, это должно было быть "как формула". Я исправил это. Что касается различения конечных моделей, другая ситуация состоит в том, что существует только одна принятая конечная модель для вашего языка (возможно, вплоть до некоторого понятия изоморфизма). Это противоположность двусмысленности.

Марк Хаманн

Я предполагаю, что это действительно было бы "двусмысленностью". Я просто не думал об этом, как это. Главным образом потому, что с точки зрения языка это было бы не очень интересно. Но с логической точки зрения, если имеет

смысл

Я не уверен, что языковая часть должна быть скучной. У меня есть больше идей по этому поводу, но я думаю, что это выведет нас за рамки этого форума. ;-)

Марк Хаманн

0

Не уверен насчет вопроса, относящегося к CS, но попробуйте найти термин «неопределенность и логика». В философии логики неоднозначность обычно отличают от неопределенности (см., Например, здесь ), и я думаю, что вы ищете неясность (поскольку неопределенность определяется как термины, в которых существуют пограничные случаи). Главная книга в этой области - «Неопределенность» Тимоти Уильямсона (но также см. Библиографию на сайте Стэнфорда выше).

DanielC
источник

1

Спасибо за ваш ответ. Но, как вы говорите, я не очень вижу связи с информатикой. В частности, вселенная является или не является моделью формулы, здесь нет никакой неопределенности. Вместо этого, над автоматами неоднозначность - это то, что четко определено, и существует известный алгоритм для определения, является ли автомат двусмысленным, k-неоднозначным или однозначным. (только над каким-то автоматом)

Артур МИЛЧИОР

Вы совершенно правы, я, вероятно, не должен был вмешиваться в этот вопрос и придерживаться скрытности. Я только новичок в CS (собираюсь закончить мой курс по логике / философии науки и чистой математике). Спасибо за информацию, хотя.

DanielC

0

Я (также) согласен с Анрей.

Я думаю, что описательная сложность - это характеристика без вычислений (что делает ее интересной по-своему), и, следовательно, примеры вычислительной неоднозначности из теории формальных языков (автоматы / грамматики / ...), которые вы рассматривали, находятся в совершенно другой области , В описательных языках сложности соответствуют классам сложности, а запросы (на языке) соответствуют вычислительным задачам (не алгоритмам). Не существует предполагаемого способа проверки / вычисления запроса AFAIK, поэтому, если вы не ищете неоднозначность вычислений, IMHO, эти примеры вводят в заблуждение.

Кава
источник

Каве, я не уверен, что согласен с тем, что безошибочная характеристика описательной сложности на 100% верна. Вычислительные детали очень важны для понимания того, как конкретная логика захватывает класс сложности. Преимущество состоит в том, что, как только вы сделали свои доказательства и поняли, как они работают, вы можете отложить вычисления и сосредоточиться на логических деталях, используя стандартные логические методы.

Марк Хаманн

То же самое замечание а Марк. Описательная сложность также известна как теория базы данных, словарь, являющийся структурой базы данных, и модели теории, определяющие содержание базы данных. Следовательно, мы рады, что мы можем вычислить и выяснить, соответствует ли база данных формуле.

Артур МИЛЬЧИОР

A C^{0}

$\mathbf{AC^0}$

F O

$\mathbf{FO}$

1

@Kaveh, я делаю слегка тонкое замечание, но я думаю, что оно важно, поскольку его часто неправильно понимают (например, неудачные попытки P = NP?). Там вне лежащая в основе, достаточно алгоритм грубой силы , которая лежит в основе соответствия логического языка и класса сложности. Работа с логикой позволяет вам не задумываться о деталях этого алгоритма каждую секунду, но красота и гениальность доказательств Фагина, Иммермана, Варди и других заключаются именно в описании этих алгоритмов. Люди, которые полностью упускают их из виду, обычно попадают в беду.

Марк Хаманн

1

@Kaveh, я думаю, что мы понимаем друг друга и разделяем наше уважение к полю. «Грубая сила» не была задумана как незначительная часть базовых алгоритмов, просто давала понять, что мы говорим о чем-то немного более абстрактном, чем то, что кто-то, кто делает, скажем, работу по алгоритмической оптимизации, может воспринимать как алгоритм.

Марк Хаманн

Неоднозначность и логика

Ответы: