1.5. Логика предикатов

Логика предикатов  раздел алгебры логики, являющийся основой построения формальных логико-математических языков. Используется при построении интеллектуальных систем, таких как машинный перевод текстов с одного языка на другой, сочинение музыки, стихов и т.д., т.е. таких систем, которые не контролируются полностью заданной программой и потоком входных данных, а допускают возможность выработки программой самостоятельных критериев, связанных с особенностями алгоритмов. Чтобы формальный язык имел такие возможности, ему требуется более разнообразный алфавит по сравнению с алфавитом логики высказываний. Это разнообразие обеспечивается введением предметной области, содержащей объекты произвольной природы, а также предикатных и функциональных символов, которые существенно расширяют выразительные возможности логики предикатов по сравнению с логикой высказываний.

Рассмотрим логику предикатов первого порядка. Понятие предиката вводится в теории множеств: n-местным предикатом называют n-местное отношение на множестве элементов предметной области, которому поставлено в соответствие множество упорядоченных n-ок, элементами которых являются объекты из предметной области, на которых это отношение истинно. В отличие от пропозициональных переменных логики высказываний, принимающих значение в множестве {0,1} ({истина, ложь}), переменные в логике предикатов принимают все возможные значения в предметной области (пробегают предметную область). Отношения объектов предметной области, определенные на естественном языке, могут быть представлены на языке логики предикатов в виде предложений, удовлетворяющих определенным требованиям. Рассмотрим синтаксис и семантику логики предикатов.

1.5.1. Исходные символы языка логики предикатов

Исходные символы языка логики предикатов делятся на шесть групп:

V - множество предметных переменных, V={х₁, x₂, …, x_n};

С - множество предметных констант, С={с₁,с₂,...};

S-множество логических связок, S={0,1, &, , , , , }; здесь 0 и 1 - логические символы, означающие «ложь» и «истина», & - символ конъюнкции или логического умножения,  -дизъюнкция или логическое сложение,  - символ логического отрицания,  символ импликации или логического следования,  - символ эквивалентности;

F-множество функциональных символов, F= ; - _i -местная функция;

R-множество предикатных символов, - _i-местный предикатный символ.

множество вспомогательных символов {, (, ) }.

В языке логики предикатов определяется понятие предметной области D такой, что сС: с есть наименование объекта в предметной области D; хV, означает, что х «пробегает» весь диапазон возможных значений из D. Установление связи между элементами языка логики предикатов и предметной областью D производится с помощью функции интерпретации I.

Функциональные символы из множества F суть операции над некоторыми операндами, определенными над предметной областью D.

Предикатные символы есть отношения, определенные также в предметной области D.

Сигнатурой языка L_ называется множество =CFR, если

• FR=,

• fF  (: FN);

• rR  (: RN),

т.е. отображение  ставит в соответствие каждому функциональному символу и каждому предикатному символу натуральное число, являющееся местностью этого функционального или предикатного символа. Иначе, (f) и (r)  есть число аргументов функционального или предикатного символа. Например, если f⁽²⁾ есть«+», т.е. f(x,y)=х+у, то (f)=2; если f = Sin (х), то (f)=1.

Если предикатный символ r есть < в выражении вида х<у, то (r)=2.

Мощность множества RF называется мощностью сигнатуры .

Алгебраической системой сигнатуры , обозначается M=(D,) называется упорядоченная пара, содержащая непустое множество D (предметную область) и объекты сигнатуры , если каждому n-местному предикатному (функциональному) символу из  сопоставлен n-местный предикат (функция) той же местности на D, а каждой предметной константе из  сопоставлен некоторый элемент из D. Если сигнатура не содержит функциональных символов, то алгебраическая система называется моделью. Множество D называется несущим множеством алгебраической системы.

Пусть ₁  ₂, тогда модель Ф₁= (D; ₁) называется обеднением модели Ф₂=(D; ₂), и, соответственно, Ф₂ есть обогащение Ф₁, если интерпретация всех символов сигнатуры ₁ совпадает с интерпретацией этих символов в сигнатуре ₂.

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

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