Формулы исчисления предикатов

Опишем, как строятся формулы исчисления предикатов.

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

Определение. Если - n-местный предикатный символ и - термы, то - атомарная формула.

Определение. Если А – формула, то (А), - формулы. Если А и В – формулы, то ; А&В; - формулы. Если А(х) – формула, содержащая переменную х, то и - формулы. Других формул нет.

Замечание 1. Вместо знака отрицания часто удобнее пользоваться знаком .

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

Пусть, например, P(x) = «x – блестящий знаток математической логики». Тогда запись означает «не всякий x является блестящим знатоком математической логики», а смысл формулы таков: «всякий x не является блестящим знатоком математической логики».

Замечание 3. Если перед предикатом от нескольких переменных поставить квантор для одной из них, переменная под знаком квантора перестает быть аргументом предиката.

Пример 1. Пусть Р(х, у) = «х делит у», . Тогда «7 делит 5» - ложное высказывание; «2 делит 6» - истинное. Формула уже задает одноместный предикат: «Всякое натуральное число делит у». Какое бы значение у из области определения не подставлять в эту формулу, всегда получится ложь. Формула представляет собой функцию переменной х: «существует число, которое делится на х». Это истина для всякого натурального х.

А формулы , , , уже вообще не зависят от аргументов х и у. Эти формулы представляют собой высказывания: «существуют такие натуральные числа, что одно из них делит другое» - истина; «существует натуральное число, которое делит всякое натуральное число» - истина (1 делит все натуральные числа); «всякое натуральное число делит все остальные натуральные числа» - ложь; «у всякого натурального числа есть делители» - истина (простое число делится на 1 и само на себя).

Если предложение Р(х, у) сформулировать в виде «х делит у и , » то высказывание становится ложным.

Пример 2. Высказывание - это истинное высказывание, утверждающее коммутативность сложения. Высказывание - истинно, достаточно положить у = х. Высказывание - ложно. Одного и того же значения у для всех значений хне существует.

Примеры решения задач

Пример 1. Пусть Р(х) = «х – простое число», Е(х) = «х – четное число», Q(x) = «x – нечетное число», D(x, y) = «x делит y». Универсум D – множество целых чисел.

Перевести на русский язык:

P(7), E(2)&P(2), ,

.

Решение: P(7) = «7 – простое число», E(2)&P(2) = «2 – четное и простое число», = «всякое число, которое делится на 2 - четное», = «всякое число, делящееся на четное число, само четно».

Пример 2. Ниже помещены четыре предложения на русском языке, за которыми следуют столько же формул исчисления предикатов. Соединить в пары эти предложения, чтобы члены пары были эквивалентны. В скобках указаны обозначения соответствующих предикатов.

1. Все судьи – юристы (J(x), L(x), от английского judge – судья, lawyer - юрист).

2. Некоторые юристы – жулики (S(x), от английского swindler - мошенник).

3. Ни один судья не является жуликом.

4. Некоторые юристы восхищаются только судьями (A(x, y), от английского admire - восхищаться).

1!

2!

3!

4!

Решение: 1 – 3!; 2 – 2!; 3 – 4!; 4 – 1!

Справедливость заключений вида «для всех» и «для некоторых», основанных на такого же вида посылках, можно неформально проверять, считая посылки верными, при помощи диаграмм Эйлера-Венна. Всякое утверждение вида «для всех» означает включение одного множества в другое. Утверждение вида «для некоторых» означает непустое пересечение множеств.

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

Пример 3. Проверить правильность (ложность) умозаключения при помощи диаграмм Эйлера-Венна.

Некоторые адвокаты богаты. Некоторые врачи богаты. Значит некоторые врачи – адвокаты.

Решение: Универсум – множество всех людей. Пусть А – множество богатых людей, В – множество адвокатов, С – множество врачей. В посылках говорится о непустом пересечения множеств А и В; А и С. В заключении утверждается, что Ø, так ли это? На построенной диаграмме показана возможность пустого пересечения множеств В и С, заключение неверно.

Ø; Ø; ВС = Ø заключение ложно

Переведем посылки и заключения на язык исчисления предикатов. Пусть А(х) = «х - богат», В(х) = «х - адвокат», С(х) = «х - врач». Дано: ; . Верно ли, что ?

Пример 4. проверить правильность умозаключения при помощи диаграмм Эйлера-Венна.

Все поэты счастливы. Некоторые поэты ленивы. Значит, некоторые ленивые люди счастливы.

Решение: Пусть А – множество поэтов, В – множество счастливых людей, С – множество ленивых людей, универсум – множество всех людей.

Дано: Ø. Верно ли, что Ø?

Из диаграмм Эйлера-Венна следует, что непустое пересечение АС принадлежит множеству В, поэтому ВС заведомо не пусто.

Ø Ø, заключение верно.

На языке исчисления предикатов: если верно, что и , то верно также, что .