Интерпретация

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

· Несущее множество ,

· Семантическая функция , отображающая

· каждый -арный функциональный символ из в -арную функцию ,

· каждый -арный предикатный символ из в -арное отношение .

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

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

· , если — переменная,

·

В таком же духе определяется отношение истинности формул на относительно

· , тогда и только тогда, когда ,

· , тогда и только тогда, когда — ложно,

· , тогда и только тогда, когда и истинны,'

· , тогда и только тогда, когда или истинно,

· , тогда и только тогда, когда влечет ,

· , тогда и только тогда, когда для некоторой подстановки , которая отличается от только на переменной ,

· , тогда и только тогда, когда для всех подстановок , которые отличается от только на переменной .

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

Свойства и основные результаты[править | править исходный текст]

Логика первого порядка обладает рядом полезных свойств, которые делают ее очень привлекательной в качестве основного инструмента формализации математики. Главными из них являются полнота (это означает, что для любой замкнутой формулы выводима либо она сама, либо ее отрицание) и непротиворечивость (ни одна формула не может быть выведена одновременно со своим отрицанием). При этом если непротиворечивость более или менее очевидна, то полнота — нетривиальный результат, полученный Гёделем в 1930 году (теорема Гёделя о полноте). По сути теорема Гёделя устанавливает фундаментальнуюьэквивалентность понятий доказуемости и общезначимости.

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

Согласно теореме Лёвенгейма — Скулема если множество формул имеет модель, то оно также имеет модель не более чем счетной мощности. С этой теоремой связан парадокс Скулема, который, однако, является лишь мнимым парадоксом.