5.2.2. Синтаксис исчисления предикатов

Термом является всякая функциональная константа, переменная и всякая функциональная форма.

Функциональная форма – это функциональная константа от непустого множества аргументов, в которой на места аргументов подставлены термы. Если f – функциональная константа, зависящая от n аргументов (n-местная функциональная константа), и ,…, – термы, то функциональная форма представляется выражением f( ,…, ).

Атом – это предикатная форма, в том числе предикатная форма пустого множества аргументов, то есть элементарное высказывание, или равенство типа = , где , – термы.

Предикатная форма – это предикатная константа, зависящая от m аргументов, в которой на места аргументов подставлены термы. Если P – предикатная m-местная константа и ,…, – термы, то предикатная форма представляется выражением P( ,…, ).

Фразами исчисления предикатов являются формулы. Дадим индуктивное определение формулы.

Атом есть формула.

Если А – формула, то А – формула.

Если А и В – формулы, то (А  В), (А  В), (А  В), (А ~ В) – формулы.

Если А – формула и x – переменная, то x А и x А – формулы.

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

КАДР

5.2.3. Семантика исчисления предикатов

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

Интерпретация I формулы – это тройка <D, , > со следующими свойствами:

D – непустое множество, область интерпретации.

– система функций такая, что для каждой функциональной n-местной константы f задается отображение  D и для каждой предикатной m-местной константы задается отображение  {и,л}.

представляет интерпретацию переменных и индивидных констант: каждой переменной сопоставляется элемент из D и каждой индивидной константе сопоставляется элемент из D.

Остановимся на интерпретации выражения x (A(x)). Всем другим переменным формулы А присваиваются определенные значения из D, а для переменной x выясняется, существует ли хотя бы одно значение из D такое, что при уже выбранных значениях других переменных формула А принимает значение и.

Выражение x (A(x)) интерпретируется следующим образом. Всем другим переменным формулы А присваиваются определенные значения из D, а для переменной x выясняется, будет ли формула А принимать значение и при любом значении x  D и уже выбранных значениях остальных переменных.

Формула А исчисления предикатов называется истинной при интерпретации I, если она принимает значение и при этой интерпретации.

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

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

КАДР