Удаление квантификатора

Устранение кванторов — это концепция упрощения, используемая в математической логике , теории моделей и теоретической информатике . Неформально, квантифицированное утверждение « такое, что » можно рассматривать как вопрос «Когда существует такое, что ?», а утверждение без кванторов можно рассматривать как ответ на этот вопрос. ^[1] $\exists x$ $\ldots$ $х$ $\ldots$

Одним из способов классификации формул является количество количественных оценок . Формулы с меньшей глубиной чередования кванторов считаются более простыми, а формулы без кванторов - наиболее простыми. Теория имеет устранение кванторов, если для каждой формулы существует другая формула без кванторов, эквивалентная ей ( по модулю этой теории). $\альфа$ $\alpha _{QF}$

Примеры

Пример из школьной математики гласит, что квадратичный многочлен с одной переменной имеет действительный корень тогда и только тогда, когда его дискриминант неотрицательен: ^[1]

\exists x\in \mathbb {R} .(a\neq 0\wedge ax^{2}+bx+c=0)\ \ \Longleftrightarrow \ \ a\neq 0\wedge b^{2} -4ac\geq 0

Здесь предложение в левой части включает квантор , а эквивалентное предложение в правой части — нет. $\exists x\in \mathbb {R}$

Примерами теорий, разрешимость которых была доказана с помощью исключения кванторов, являются арифметика Пресбургера , ^[2]^[3]^[4]^[5]^[6] алгебраически замкнутые поля , вещественные замкнутые поля , ^[7]^[8] безатомные булевы алгебры , термальные алгебры. , плотные линейные порядки , ^[7] абелевы группы , ^[9] случайные графы , а также многие их комбинации, такие как булева алгебра с арифметикой Пресбургера и алгебры термов с очередями .

Кванторным элиминатором для теории действительных чисел как упорядоченной аддитивной группы является исключение Фурье – Моцкина ; для теории поля действительных чисел это теорема Тарского–Зейденберга . ^[7]

Устранение кванторов также можно использовать, чтобы показать, что «объединение» разрешимых теорий приводит к новым разрешимым теориям (см. теорему Фефермана-Вота ).

Алгоритмы и разрешимость

Если теория допускает устранение кванторов, то можно ответить на конкретный вопрос: существует ли метод определения для каждого из них ? Если такой метод существует, мы называем его алгоритмом исключения кванторов . Если такой алгоритм существует, то разрешимость теории сводится к определению истинности предложений , свободных от кванторов . Предложения без кванторов не имеют переменных, поэтому их достоверность в данной теории часто можно вычислить, что позволяет использовать алгоритмы исключения кванторов для определения достоверности предложений. $\alpha _{QF}$ $\альфа$

Связанные понятия

Различные теоретико-модельные идеи связаны с устранением кванторов, и существуют различные эквивалентные условия.

Любая теория первого порядка с исключением кванторов является модельно полной . И наоборот, модельно-полная теория, теория универсальных следствий которой обладает свойством амальгамации , имеет устранение кванторов. ^[10]

Модели теории универсальных следствий теории являются именно подструктурами моделей теории . ^[10] Теория линейных порядков не допускает исключения кванторов. Однако теория ее универсальных следствий обладает свойством амальгамации. $Т$ $Т$

Основные идеи

Чтобы конструктивно показать, что теория допускает устранение кванторов, достаточно показать, что мы можем исключить квантор существования, примененный к соединению литералов , то есть показать, что каждая формула вида:

\exists x.\bigwedge _{i=1}^{n}L_{i}

где каждый является литералом, эквивалентен формуле без кванторов. Действительно, предположим, что мы знаем, как исключить кванторы из конъюнкций литералов, тогда если — формула, свободная от кванторов, мы можем записать ее в дизъюнктивной нормальной форме. $L_ {я}$ $F$

\bigvee _{j=1}^{m}\bigwedge _{i=1}^{n}L_{ij},

и использовать тот факт, что

\exists x.\bigvee _{j=1}^{m}\bigwedge _{i=1}^{n}L_{ij}

эквивалентно

\bigvee _{j=1}^{m}\exists x.\bigwedge _{i=1}^{n}L_{ij}.

Наконец, чтобы устранить универсальный квантор

\forall xF

где не кванторно, мы преобразуем его в дизъюнктивную нормальную форму и используем тот факт, что эквивалентно $F$ $\lnot F$ $\forall xF$ $\lnot \exists x.\lnot F.$

Связь с разрешимостью

В ранней теории моделей исключение кванторов использовалось, чтобы продемонстрировать, что различные теории обладают такими свойствами, как разрешимость и полнота . Обычный метод заключался в том, чтобы сначала показать, что теория допускает исключение кванторов, а затем доказать разрешимость или полноту, рассматривая только формулы без кванторов. Этот метод можно использовать, чтобы показать, что арифметика Пресбургера разрешима.

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

Пример: Nullstellensatz для алгебраически замкнутых полей и для дифференциально замкнутых полей . ^{[ нужны разъяснения ]}

Смотрите также

Примечания

^ Аб Браун 2002.
^ Пресбургер 1929.
^ Разум: базовая арифметика Пресбургера — — не допускает исключения кванторов. Нипков (2010): «Арифметика Пресбургера нуждается в предикате делимости (или конгруэнтности) '|' чтобы разрешить устранение квантора». $\langle \mathbb {N},+,0,1\rangle$
^ Гредель и др. (2007, стр. 20) определяют арифметику Пресбургера как . Это расширение допускает исключение кванторов. $\langle \mathbb {N},+,<,0,1,(\equiv _{k})_{k>0}\rangle {\text{where }}x\equiv _{k}y {\text{ тогда и только тогда, когда }}x=y(\mod {k})$
^ Монк 2012, с. 240.
^ Эндертон 2001, с. 188.
^ abc Grädel et al. 2007.
^ Фрид и Джарден 2008, с. 171.
^ Шмелев 1955, стр. 229 описывает «метод устранения количественной оценки»..
^ Аб Ходжес 1993.