Логика первого порядка

Логика первого порядка

План:

Введение

1 Определение 2 Аксиоматика
2.1 Вывод формул и теорем 2.2 Пример вывода
3 Примеры теорий первого порядка
3.1 Теория групп 3.2 Теория абелевых групп
4 Семантика 5 Свойства
5.1 Корректность и полнота 5.2 Компактность 5.3 Неразрешимость

Литература

Введение

Логика первого порядка

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

1. Определение

Языки логики первого порядка строятся на основе: множества функциональных символов и множества предикатных символов . С каждым функциональным и предикатным символом связана арность (число Агрумент). Кроме того, используются дополнительные символы:

Символы переменных, обычно и т. д., Пропозициональные связи: , Кванторы : всеобщности и существования , Служебные символы: скобки и запятая.

Перечисленные символы вместе с символами из и образуют Алфавит логики первого порядка. Сложные конструкции определяются индуктивно :

Терм - это символ переменной, или имеет вид , Где - Функциональный символ арности , А - Термы. Атом - имеет вид , Где - Предикатный символ арности , А - Термы. Формула - это либо атом, или одно из следующих конструкций: , Где - Формулы, а - Переменная.

Переменная называется связанной в формуле , Если имеет вид или , Или может быть представлена ??в одной из форм , Причем уже связана в , и .

Если не связана в , Ее называют несвязанной в . Формулу без несвязанных переменных называют замкнутой формуле. Теорией первого порядка называют произвольное множество замкнутых формул.

2. Аксиоматика

Следующая система логических аксиом логики первого порядка содержит все аксиомы исчисления высказываний (в приведенном случае - аксиомы Лукасевича) и две дополнительные аксиомы:

, , Если не присутствует в в незвязаному состоянии

В четвертой аксиоме - Формула, полученная в результате подстановки терма вместо переменной в формуле . Подстановка некоторого терма вместо переменной возможна не во всех случаях. Условия существования такой подстановки и ее результат можно определить индуктивно.

Если - Атомарная формула, то терм может заменить произвольную переменную этой формулы. Результат сказывается . Если имеет вид тогда подстановка вместо возможна только тогда, когда такая подстановка возможна для формулы и тогда равна Если имеет вид , Тогда подстановка вместо возможна только тогда, когда такая подстановка возможна для формул и тогда равна Если имеет вид , Тогда подстановка вместо возможна в двух случаях:

Переменная встречается в формуле только в связанном состоянии. переменная не встречается в терме и подстановка вместо возможна в формуле Тогда результат определяется следующим образом: Если равна , То равна Если не равна , То равна

Кроме того есть два правила вывода:

Modus ponens :

Правило обобщения (GEN):

Эти аксиомы и правила вывода являются схемами и можно заменять произвольными формулами.

В этой аксиоматике используются только две пропозициональные связи: и квантор всеобщности . Другие пропозициональные связки и квантор существования можно определить следующим образом:

обозначает обозначает обозначает

Все приведенные выше аксиомы называются логическими. Если не существует других аксиом, то такую ??формальную систему называют исчислением предикатов первого порядка. Исчисление предикатов первого порядка является примером теории первого порядка. Все теории первого порядка определяются подобно исчисления предикатов первого порядка, однако они имеют дополнительные аксиомы, которые еще называют собственными Аксом теории.

2.1. Вывод формул и теорем

Пусть некоторое множество формул языка первого порядка, а - Некоторая заданная формула. Тогда говорят, что формула выводится из множества формул (Обозначается ), Если существует такая конечная последовательность формул , Где для каждой формулы :

является аксиомой, или принадлежит множеству или выводится из предыдущих формул последовательности с помощью одного из правил вывода.

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

Множество формул называется непротиворечивой, если для произвольной формулы не выполняется одновременно и .

2.2. Пример вывода

Докажем, что

Пример вывода
Номер	Формула	Способ получения
1		Гипотеза
2		Правило обобщения и 1
3		Гипотеза
4		2, 3 и modus ponens
5		Правило обобщения и 4.

3. Примеры теорий первого порядка

3.1. Теория групп

В этом случае имеем один функциональный символ арности 0 (обозначим его ), Один функциональный символ арности 2 (обозначим его ) И один предикатный символ арности 2 (обозначим его ). Также писать и вместо и .

Собственные формулы теории:

( ассоциативность) (Свойство нейтрального элемента) (Существование обратного элемента) ( рефлексивность равенства) (Симметричность равенства) ( транзитивность равенства) (Подстановка равенства)

3.2. Теория абелевых групп

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

4. Семантика

В классической логике интерпретация формул логики первого порядка задается на модели первого порядка, определяется следующими данными:

Базовая множество , Семантическая функция , Что отражает

каждый -Арный функциональный символ с в -Арну функцию , каждый -Арный предикатный символ с в -Арное отношения .

Предположим - Функция, отображающая каждую переменную в некоторый элемент из , Которую и будем называть подстановкой. Интерпретация терма на относительно подстановки задается индуктивно:

, Если - Переменная,

Подобным образом определяется истинность формул относительно

, Тогда и только тогда, когда , , Тогда и только тогда, когда - Ложно, , Тогда и только тогда, когда и истинные, ' , Тогда и только тогда, когда или истинно, , Тогда и только тогда, когда с следует , , Тогда и только тогда, когда для некоторой подстановки , Которая отличается от только на переменном , , Тогда и только тогда, когда для всех подстановок , Которые отличаются от только на переменном .

Формула , Истинная на , Что сказывается , Если , Для всех подстановок . Формула называется общезначимых, (обозначается ), Если для всех моделей . Формула называется выполняемой, если хотя бы для одной .

5. Свойства

5.1. Корректность и полнота

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

5.2. Компактность

Некоторая множество формул является исполняемой тогда и только тогда, когда выполняемыми есть все ее конечные подмножества.

5.3. Неразрешимость

В отличие от логики высказываний логика первого порядка является неразрешимой при наличии по крайней мере одного предиката арности не менее 2 (за исключением равенства), то есть нет эффективного метода определения "существует или не существует вывода некоторой формулы?" в определенной теории первого порядка.

См.. также

Исчисление высказываний Квантор Правило резолюций Исчисление секвенций Логика второго порядка Теорема Льовенгейма-Сколема Нормальная форма Сколема

Литература

Основы теоретической логики. М., 1947 Введение в метаматематику. М., 1957 . Введение в математическую логику. М., 1976 Элементы математической логики. М., 1959 Введение в математическую логику, т. I. М., 1960 "Философский словарь" / Под ред. . - 2.Виды., Перераб. и доп. - М.: Глав. Ред. Уре, 1986.

http://nado. *****