На этом шаге мы рассмотрим представление объектов в логике предикатов первого порядка.

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

Для представления объектов предметной области в логике предикатов первого порядка используют атомы, константы, переменные, термы, предикаты, кванторы. Определим эти понятия.

Атом - это повествовательное предложение, которое может быть истинно или ложно, но не то и другое одновременно. Атом рассматривают, как единое целое, его структуру и состав не анализируют. Например, "Иванов работает на заводе", "Петров является студентом" и т.п.

Константа - это символ, обозначающее индивидуальный объект или понятие.

Переменная - это символ, используемый в разное время для обозначения различных объектов. Для определения области действия переменных используются кванторы.

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

константа есть терм;
переменная есть терм;
если f есть n-местный функциональный символ и t₁, t₂, ..., t_n - термы, то составной терм f(t₁, t₂,…, t_n) - тоже терм;
никаких других термов, кроме составленных с помощью правил (1) - (3), нет.

Поясним третье правило. Составной терм f(t₁, t₂,..., t_n) состоит из функционального символа и упорядоченного множества термов, являющихся его аргументами. Составной терм обозначает некоторый объект, зависящих от других объектов, представленных его аргументами.

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

Предикатный символ P (предикатная буква) используется для представления отношений между объектами в некоторой области. Если предикатный символ P имеет n аргументов, то P называется n-местным предикатным символом.

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

Предикат состоит из предикатного символа и соответствующего ему упорядоченного множества термов, являющихся его аргументами. Если P есть n-местный предикатный символ и t₁, t₂, ..., t_n - термы, то P(t₁, t₂,…, t_n) - предикат. Таким образом, предикатные символы синтаксически используются для образования формул, а семантически обозначают предикаты.

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

Определение.: Если P есть n-местный предикатный символ языка (n³0) и t₁, t₂,…, t_n - термы, то P(t₁, t₂, ..., t_n) есть атомарная (элементарная) формула языка.

Запись P(t₁, t₂, ..., t_n) означает, что истинно высказывание, гласящее, что объекты t₁, t₂, ..., t_n связаны отношением P.

Поясним сказанное на конкретных примерах. Высказывание "x является отцом y" можно представить с помощью предиката отец(x,y), где отец - предикатный символ; x, y - переменные.

Высказывание "Сын Ивана является братом Степана" можно представить с помощью предиката брат(сын(Иван,x),Степан), где брат - предикатный символ, сын - функциональный символ, Иван и Степан - константы, выражение сын(Иван,x) - терм.

Для построения атомов используются предикатные и функциональные символы, переменные и константы. Из атомарных формул с помощью логических связок Ù (конъюнкции), Ú (дизъюнкции), ~ (отрицания), ® (импликации), « (эквиваленции) и кванторов можно строить сложные формулы языка.

На следующем шаге мы начнем рассматривать кванторы.

Предыдущий шаг Содержание Следующий шаг