Сколем нормальная форма - Skolem normal form

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

Каждый первый заказ формула может быть преобразован в нормальную форму сколем, не изменяя ее выполнимость через процесс, называемый Сколемизация (иногда пишется Сколемнизация). Полученная формула не обязательно эквивалент к исходному, но равноправный с ним: оно выполнимо тогда и только тогда, когда выполнимо исходное.^[1]

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

Примеры

Простейшая форма сколемизации предназначена для экзистенциально количественно определенных переменных, которые не находятся внутри объем универсального квантора. Их можно заменить, просто создав новые константы. Например, ${\displaystyle \exists xP(x)}$ может быть изменен на ${\displaystyle P(c)}$, куда ${\displaystyle c}$ - новая константа (больше нигде в формуле не встречается).

В более общем смысле, сколемизация выполняется путем замены каждой экзистенциально количественной переменной ${\displaystyle y}$ со сроком ${\displaystyle f(x_{1},\ldots ,x_{n})}$ символ функции ${\displaystyle f}$ новый. Переменные этого члена следующие. Если формула в пренекс нормальная форма, ${\displaystyle x_{1},\ldots ,x_{n}}$ являются переменными, которые универсально определены количественно и чьи кванторы предшествуют ${\displaystyle y}$. В общем, это переменные, которые количественно оцениваются универсально (мы предполагаем, что мы избавляемся от экзистенциальных кванторов по порядку, поэтому все экзистенциальные кванторы до ${\displaystyle \exists y}$ были удалены) и такие, что ${\displaystyle \exists y}$ происходит в рамках их кванторов. Функция ${\displaystyle f}$ введенный в этот процесс называется Функция Сколема (или же Постоянная Сколема если это ноль арность ) и термин называется Сколемский термин.

Например, формула ${\displaystyle \forall x\exists y\forall z.P(x,y,z)}$ не находится в нормальной форме Сколема, поскольку содержит квантор существования ${\displaystyle \exists y}$. Сколемизация заменяет ${\displaystyle y}$ с ${\displaystyle f(x)}$, куда ${\displaystyle f}$ является новым функциональным символом и удаляет количественную оценку ${\displaystyle y}$. Полученная формула ${\displaystyle \forall x\forall z.P(x,f(x),z)}$. Сколемский термин ${\displaystyle f(x)}$ содержит ${\displaystyle x}$, но нет ${\displaystyle z}$, потому что квантор, который нужно удалить ${\displaystyle \exists y}$ находится в сфере ${\displaystyle \forall x}$, но не в том ${\displaystyle \forall z}$; поскольку эта формула находится в предваренной нормальной форме, это эквивалентно тому, что в списке кванторов ${\displaystyle x}$ предшествует ${\displaystyle y}$ пока ${\displaystyle z}$ не. Формула, полученная этим преобразованием, выполнима тогда и только тогда, когда исходная формула.

Как работает сколемизация

Сколемизация работает путем применения второго порядка эквивалентность в сочетании с определением выполнимости первого порядка. Эквивалентность дает возможность «переместить» квантор существования перед универсальным.

${\displaystyle \forall x{\Big (}R(g(x))\vee \exists yR(x,y){\Big )}\iff \exists f\forall x{\Big (}R(g(x))\vee R(x,f(x)){\Big )}}$

куда

${\displaystyle f(x)}$ это функция, которая отображает ${\displaystyle x}$ к ${\displaystyle y}$.

Интуитивно понятно, что предложение «для каждого ${\displaystyle x}$ существует ${\displaystyle y}$ такой, что ${\displaystyle R(x,y)}$"преобразован в эквивалентную форму" существует функция ${\displaystyle f}$ отображение каждого ${\displaystyle x}$ в ${\displaystyle y}$ так что для каждого ${\displaystyle x}$ он держит ${\displaystyle R(x,f(x))}$".

Эта эквивалентность полезна, потому что определение выполнимости первого порядка неявно экзистенциально дает количественную оценку по сравнению с оценкой функциональных символов. В частности, формула первого порядка ${\displaystyle \Phi }$ выполнимо, если существует модель ${\displaystyle M}$ и оценка ${\displaystyle \mu }$ свободных переменных формулы, которые вычисляют формулу истинный. Модель содержит оценку всех функциональных символов; следовательно, сколемские функции неявно экзистенциально определены количественно. В приведенном выше примере ${\displaystyle \forall x.R(x,f(x))}$ выполнимо тогда и только тогда, когда существует модель ${\displaystyle M}$, который содержит оценку для ${\displaystyle f}$, так что ${\displaystyle \forall x.R(x,f(x))}$ верно для некоторой оценки его свободных переменных (в данном случае нет). Это может быть выражено во втором порядке как ${\displaystyle \exists f\forall x.R(x,f(x))}$. По указанной выше эквивалентности это то же самое, что выполнимость ${\displaystyle \forall x\exists y.R(x,y)}$.

На мета-уровне выполнимость первого порядка формулы ${\displaystyle \Phi }$ может быть записано с небольшим злоупотреблением обозначениями как ${\displaystyle \exists M\exists \mu ~.~(M,\mu \models \Phi )}$, куда ${\displaystyle M}$ модель, ${\displaystyle \mu }$ оценка свободных переменных, и ${\displaystyle \models }$ Значит это ${\displaystyle \Phi }$ верно в ${\displaystyle M}$ под ${\displaystyle \mu }$. Поскольку модели первого порядка содержат вычисление всех функциональных символов, любая функция Сколема ${\displaystyle \Phi }$ содержит неявно экзистенциально количественно оценивается ${\displaystyle \exists M}$. В результате, после замены экзистенциального квантора над переменными на экзистенциальный квантор над функциями в начале формулы, формула по-прежнему может рассматриваться как формула первого порядка, удалив эти экзистенциальные кванторы. Этот последний шаг лечения ${\displaystyle \exists f\forall x.R(x,f(x))}$ в качестве ${\displaystyle \forall x.R(x,f(x))}$ может быть завершено, потому что функции неявно экзистенциально оцениваются количественно ${\displaystyle \exists M}$ в определении выполнимости первого порядка.

Правильность сколемизации можно показать на примере формулы ${\displaystyle F_{1}=\forall x_{1}\dots \forall x_{n}\exists yR(x_{1},\dots ,x_{n},y)}$ следующее. Этой формуле удовлетворяет модель ${\displaystyle M}$ тогда и только тогда, когда для каждого возможного значения для ${\displaystyle x_{1},\dots ,x_{n}}$ в области модели существует значение для ${\displaystyle y}$ в области модели, которая делает ${\displaystyle R(x_{1},\dots ,x_{n},y)}$ истинный. Посредством аксиома выбора, существует функция ${\displaystyle f}$ такой, что ${\displaystyle y=f(x_{1},\dots ,x_{n})}$. В результате формула ${\displaystyle F_{2}=\forall x_{1}\dots \forall x_{n}R(x_{1},\dots ,x_{n},f(x_{1},\dots ,x_{n}))}$ является выполнимым, потому что у него есть модель, полученная путем добавления оценки ${\displaystyle f}$ к ${\displaystyle M}$. Это показывает, что ${\displaystyle F_{1}}$ выполнимо, только если ${\displaystyle F_{2}}$ также выполнимо. Наоборот, если ${\displaystyle F_{2}}$ выполнимо, то существует модель ${\displaystyle M'}$ это его удовлетворяет; эта модель включает оценку функции ${\displaystyle f}$ так что для каждого значения ${\displaystyle x_{1},\dots ,x_{n}}$, формула ${\displaystyle R(x_{1},\dots ,x_{n},f(x_{1},\dots ,x_{n}))}$ держит. Как результат, ${\displaystyle F_{1}}$ удовлетворяется той же моделью, потому что можно выбрать для каждого значения ${\displaystyle x_{1},\ldots ,x_{n}}$, Значение ${\displaystyle y=f(x_{1},\dots ,x_{n})}$, куда ${\displaystyle f}$ оценивается согласно ${\displaystyle M'}$.

Использование сколемизации

Одно из применений сколемизации - автоматическое доказательство теорем. Например, в метод аналитических таблиц, всякий раз, когда встречается формула, чей ведущий квантор является экзистенциальным, может быть сгенерирована формула, полученная путем удаления этого квантора посредством сколемизации. Например, если ${\displaystyle \exists x.\Phi (x,y_{1},\ldots ,y_{n})}$ встречается в таблице, где ${\displaystyle x,y_{1},\ldots ,y_{n}}$ свободные переменные ${\displaystyle \Phi (x,y_{1},\ldots ,y_{n})}$, тогда ${\displaystyle \Phi (f(y_{1},\ldots ,y_{n}),y_{1},\ldots ,y_{n})}$ может быть добавлен в ту же ветку таблицы. Это добавление не влияет на выполнимость таблицы: каждая модель старой формулы может быть расширена путем добавления подходящей оценки ${\displaystyle f}$, к модели новой формулы.

Эта форма сколемизации является улучшением по сравнению с «классической» сколемизацией в том, что только переменные, которые свободны в формуле, помещаются в термин «сколем». Это улучшение, поскольку семантика таблицы может неявно помещать формулу в объем некоторых универсально количественных переменных, которых нет в самой формуле; эти переменные не входят в термин "сколем", хотя они должны присутствовать в соответствии с исходным определением "сколемизации". Еще одно улучшение, которое можно использовать, - это применение одного и того же символа функции Сколема для формул, которые идентичны вплоть до переименование переменных.^[2]

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

Сколемские теории

В общем, если ${\displaystyle T}$ это теория и для каждой формулы ${\displaystyle F}$ с свободные переменные ${\displaystyle x_{1},\dots ,x_{n},y}$ есть функция Сколема, то ${\displaystyle T}$ называется Сколемская теория.^[3] Например, как указано выше, арифметика с выбранной аксиомой является теория Сколема.

Каждая сколемская теория модель завершена, т.е. каждый основание модели - это элементарная подструктура. Учитывая модель M сколемской теории Т, наименьшая подструктура, содержащая некоторый набор А называется Сколемский корпус из А. Сколемский корпус А является атомный основная модель над А.

История

Нормальная форма Сколема названа в честь покойного норвежского математика. Торальф Сколем.

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

• Гербирование, двойник сколемизации
• Логика предикатного функтора

Примечания

1. «Нормальные формы и сколемизация» (PDF). Макс Планк Институт Информатики. Получено 15 декабря 2012.
2. Р. Хенле. Таблицы и родственные методы. Справочник по автоматическому мышлению.
3. «Множества, модели и доказательства» (3.3) И. Мурдейка и Дж. Ван Остена

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

• Ходжес, Уилфрид (1997), Более короткая модельная теория, Издательство Кембриджского университета, ISBN  978-0-521-58713-6

внешняя ссылка

• «Сколемская функция», Энциклопедия математики, EMS Press, 2001 [1994]
• Сколемизация на PlanetMath.org
• Сколемизация Гектор Зенил, Демонстрационный проект Wolfram.
• Вайсштейн, Эрик В. «СколемизедФорм». MathWorld.