3.2. Исчисление предикатов

Исчисление предикатов первого порядка – это формальная теория K, в которой определены :

1. Алфавит:

• Связки: (основные), & , ( дополнительные).

• Служебные символы: (,).

• Кванторы , .

• Предметные константы a,b,c,….

• Предметные переменные x, y, z,….

• Символы предикатов P,Q,R,….

• Символы функций f, g, h,….

Константы, переменные, функторы – называются термами.

2. Формулы. Слово называется формулой, если оно имеет следующий синтаксис:

1) Р(х₁,…,х_n) – атомарная формула (А).

Вхождения переменных в атомарную формулу называются свободными.

2) Если А – формула, то - тоже формула.

3) Если А и В – формулы, то - формулы.

4) Если А – формула, содержащая свободную переменную х, то - формулы.

Слово является формулой, если это следует из 1-4.

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

Пример

- х – свободная переменная, у – связанная переменная.

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

3. Аксиомы (логические).

1) Любая система аксиом исчисления высказываний.

А1:

А2:

А3:

2) Собственные аксиомы.

P1: ,

P2: ,

где t – терм.

4. Правила вывода.

1. ,

2. - введение квантора общности,

3. - введение квантора существования.

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

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

Интерпретация I исчисления предикатов K с областью интерпретацией M – это набор функций, который сопоставляет:

• каждой предметной константе a элемент I(a)M;

• каждому n-местному функтору f операцию I(f):MⁿM.

• каждому n-местному предикату Р отношение I(P) Mⁿ.

Для нас имеют смысл только интерпретированные предикаты, т. е. те, которым поставлены в соответствие некоторые отношения (для одноместных предикатов – свойства).

Пример.

Рассмотрим 3 формулы.

1. P(x,y)

2.

3.

В качестве области интерпретации возьмем множество целых положительных чисел и интерпретируем P(x,y) как отношение .

Тогда формула 1 – это предикат . Он принимает значение истинно при любых a,b принадлежащих множеству целых положительных чисел, если .

Формула 2 – это предикат, который принимает значение истинно при x=1, т. е. он выражает свойство, что для каждого положительного целого числа y .

Формула 3 – это предикат, который всегда будет истинен. Он выражает свойство: существует положительное целое число y, для которого .

Формула называется истинной, если она выполняется на любом наборе элементов М.

Формула называется ложной, если она не выполняется на любом наборе элементов М.

Формула общезначима (тавтология), если она истинна в любой интерпретации.

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

3.4. Основные равносильности для предикатов

Пусть формулы А и В имеют одно и то же множество свободных переменных (в том числе и пустое).

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

Формулы А и В равносильны на множестве М, если они равносильны во всех интерпретациях, заданных на множестве М.

Формулы А и В равносильны ( ),если они равносильны на всех множествах.

• Для формул логики предикатов сохраняются все равносильности логики высказываний.

• Перенос квантора через отрицание

• В ынос квантора за скобки

	Q – не зависит от х
	Q – зависит от х
	только в одну сторону!

Пусть P(x) – x пошел в театр, Q(x) – x пошел в кино, тогда

.

Но .

Аналогично, пусть P(x) – x делится на 2, Q(x) – x делится на 3, тогда

, но

.

• Перестановка одноименных кванторов

1. Перестановка разноименных кванторов

• Переименование связанных переменных

  х, у принадлежат одной предметной области

• Отбрасывание квантора

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

Доказательство.

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

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

3. Для исчисления высказываний доказано правило транзитивности:

4. Из 1 и 2 по правилу транзитивности получаем:

5. Введение квантора существования (правило вывода исчисления предикатов ):

6. Введение квантора общности (правило вывода исчисления предикатов

):

7. Преобразуем связанную переменную {y/z}

8. Преобразуем связанную переменную {x/v}

Таким образом, теорема доказана.