Сводка определений и основных фактов

Математическая логика

сводка определений и основных фактов

Н

е

б

о

л

ь

ш

о

е

п

р

е

д

и

с

л

о

в

и

е

Этот файл составлен по конспекту лекций В.А. Захарова, сделанного небезызвестной Валей Глазковой, при этом часть определений была слегка переформулирована в более читаемую форму. Предполагается, что всех материалов, представленных здесь, хватит для успешной подготовки к теоретической части экзамена по матлогике на 3 потоке 4 курса ВМиК МГУ. Для практики требуется все-таки порешать задачи и пописать на Прологе ☺. В ближайшее время я планирую сделать задачник, а, если дойдут руки, то и полный конспект захаровских лекций. Если Вы обнаружите опечатки или неточности, немедленно сообщайте мне по адресу grgr@later.ru (большое спасибо Андрею Чернышеву a.k.a. Dr. Andrew за уже найденные глюки).

Важно

:

данный

документ

не

является

истиной

в

последней

инстанции

,

хотя

на

звание

таковой

и

претендует

☺

,

поэтому

в

нем

могут

содержаться

неточности

и

даже

ошибки

!

Будьте

внимательны

!

1.

К

л

а

с

с

и

ч

е

с

к

а

я

л

о

г

и

к

а

п

р

е

д

и

к

а

т

о

в

п

е

р

в

о

г

о

п

о

р

я

д

к

а

Определение. Предикат – форма, при помощи которой задаются отношения между объектами и субъектами

Слово «предикат» происходит от латинского «предсказывать».

Предикаты нулевого порядка – без использования кванторов.

Предикаты первого порядка – кванторы используются только по отношению к предметам

Предикаты высшего порядка – кванторы используются по отношению к функциям.

Определение. Алфавит (сигнатура) КЛП – это набор счетных множеств:

1. предметных переменных, которое обозначается как Var

;

2. предметных констант, которые соответствуют именам предметов и обозначаются как Const;

3. функциональных символов Func, где k

_i – местность функционального символа, причем 1 (в противном случае функциональный символ является константой);

4. предикатных символов, которые используются для обозначения отношений между предметами и обозначаются Pred, где l

_i – местность предикатного символа (если 0, то данный предикатный символ обозначает утверждение, не зависящее от каких-либо предметов).

Служебные символы – это:

- логические связки: &, ∨, →, ¬;

- кванторы: ∀ (всеобщности) и ∃ (существования);

- знаки препинания: ( ) ,

Слова в алфавите – это цепочки символов.

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

1) любая переменная является термом;

2) любая константа является термом;

3) если f – k-местный функциональный символ, а - термы, то

также будет являться термом;

4) других термов нет.

Множество всех термов обозначается как Term.

Запись используется для обозначения терма, в котором содержатся только переменные из множества {

}.

Если t – терм, то выражением будем обозначать множество всех переменных, которые содержатся в терме t.

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

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

1)

е

с

л

и

P

–

m-

м

е

с

т

н

ы

й

п

р

е

д

и

к

а

т

,

а

-

т

е

р

м

ы

,

т

о

з

а

п

и

с

ь

в

и

д

а

б

у

д

е

т

я

в

л

я

т

ь

с

я

ф

о

р

м

у

л

о

й

(

а

т

о

м

а

р

н

о

й

ф

о

р

м

у

л

о

й

);

2) если ψ и ϕ - формулы, то формулой также будет являться любое выражение вида

,

,

,

,

;

3) если ϕ - формула, а х – предметная переменная, то формулой также будет являться любое выражение вида

,

;

4) никаких других формул нет.

В формулах наибольший приоритет имеют кванторы и отрицание, затем конъюнкция, дизъюнкция и импликация.

Множество всех формул обозначается как Form.

Определение. Областью действия кванторов называется формула ϕ из выражения

или

. При этом вхождение переменной х в этих выражениях называется связанным.

Если вхождение переменной не связанное, то оно называется свободным.

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

Запись

обозначает множество всех свободных переменных, входящих в формулу ϕ.

Определение. Если множество

пусто, то формула ϕ называется замкнутой формулой (предложением).

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

Определение. Интерпретация – математическая конструкция, которая позволяет описывать все многообразие воображаемых миров. Интерпретацией будем называть алгебраическую систему

, которая состоит из следующих компонент:

- - область интерпретации (предметное множество, универсум), которое представляется всеми возможными предметами воображаемого мира;

-

- отображение

(предмет в мире I, носящий имя константы с)

-

- отображение

;

-

- отображение

.

Таким образом, все элементы нашего языка приобретают четкий математический смысл.

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

Определение. Пусть I – интерпретация, ϕ - формула от n переменных, d₁, d₂, …, d_n – набор предметов. Тогда отношением выполнимости называется следующее отношение:

, которое обозначает «формула ϕ в интерпретации I выполняется на значениях d₁, d₂, …, d_n ее свободных переменных» и определяется следующим образом:

1. Значение терма на данной интерпретации:

Е

с

л

и

t

–

т

е

р

м

,

d

₁

, d

₂

,

…

, d

_m

–

п

р

е

д

м

е

т

ы

,

т

о

-

э

т

о

п

р

е

д

м

е

т

и

з

о

б

л

а

с

т

и

и

н

т

е

р

п

р

е

т

а

ц

и

и

,

к

о

т

о

р

ы

й

я

в

л

я

е

т

с

я

з

н

а

ч

е

н

и

е

м

т

е

р

м

а

:

- если t = x_i, то будет равен d

_i;

- если t – это константа с, то

;

- если , то

.

2. Отношение выполнимости формул

Если ϕ - атомарная формула вида , то выполнимость этой формулы эквивалентна истинности интерпретации предиката Р.

Если ϕ - формула вида

,

,

,

, то ее выполнимость эквивалентна

1) в случае

:

2) в случае

:

3) в случае

:

4) в случае

:

.

Если ϕ - формула вида

,

, то ее выполнимость эквивалентна

1) в случае

:

,

2) в случае

:

.

Определение. Формула ϕ называется выполнимой в интерпретации I, если для некоторого набора предметов d₁, d₂, …, d_n

.

Определение. Формула ϕ называется истинной в интерпретации I, если для любого набора предметов d₁, d₂, …, d_n

.

Определение. Формула ϕ называется невыполнимой (или противоречивой) в интерпретации I, если она не является выполнимой (т.е. если эта формула соответствует тождественно ложному утверждению).

Определение. Формула ϕ называется общезначимой, если она является истинной в любой интерпретации. Общезначимость формулы обозначается |=ϕ.

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

Определение. Пусть - множество замкнутых формул. Тогда интерпретация I называется моделью для множества Г, если любая формула из Г выполнима в данной интерпретации.

О

п

р

е

д

е

л

е

н

и

е

.

П

у

с

т

ь

ϕ

₀

–

з

а

м

к

н

у

т

а

я

ф

о

р

м

у