Лекции Просолупов

Пусть и таковы, что ( ) и ( ) — тавтологии. Тогда ( )( ) = ( ) — тавтология и ( ), по свойствам операции импликации, тоже тавтология. Следовательно, от любой формулы, выводимой из аксиом 1 и 2, —

тавтология.

В то же время,

(((¬ ¬ ) ((¬ ) )))| = =0 =

=(( ) (( ) ))| = =0 =

=((0 0) ((0 0) 0) = 1 (1 0) = 1 0 = 0.

То есть оператор от аксиомы по схеме 3 не обязательно тавтология. Следовательно,

пользуясь правилом вывода modus ponens из аксиом 1 и 2 нельзя получить любую аксиому схемы 3.

121

Лекция 20. Исчисление предикатов

§51. Пример задачи логики предикатов

Рассмотрим пример.

Пусть есть следующее рассуждение. Посылки:

(1)Всякий, кто находится в здравом уме, может понимать математику.

(2)Ни один из сыновей Гегеля не может понимать математику.

(3)Сумасшедшие не допускаются к голосованию. Заключение:

(4)Никто из сыновей Гегеля не допускается к голосованию.

Формализуем рассуждение.

( ) — находится в здравом уме. Здесь предметная переменная, — предикат;( ) — может понимать математику;( , ) — есть сын ;( ) — допускается к голосованию.

Спомощью этих предикатов можно переписать посылки и заключение:

(1)= ( ( ) ( ));

(2)= ( ( , Гегель) ¬ ( ));

(3)= (¬ ( ) ¬ ( ));

(4)= ( ( , Гегель) ¬ ( )).

Здесь — квантор всеобщности, а "Гегель" — предметная константа.

Как и раньше, будем говорить, что рассуждение верно, если конъюнкция посылок импликация заключение истинна. В нашем примере

Можно отметить следующие отличия от исчисления высказываний:

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

Пример 51.1 . Если раньше мы могли использовать элементарное утверждение="Вася — баскетболист", которое могло быть только истинно или ложно,

то теперь мы бы написали ( ) — " — баскетболист" имея в виду, что ( )

принимает значение 1 для всех из заданного множества, для которых верно свойство "быть баскетболистом".

2) Появились кванторы и для записи выражений "для любых" и

"существует такое" соответственно.

3) В исчислении высказываний формула была логическим законом, если принимала значение "истина" на любом наборе логических констант, подставляемых вместо пропозициональных букв. Теперь мы используем предикаты с переменными

122

из некоторого множества, так что проверить, что формула истинна на всех наборах не так просто. Кроме того, одной и той же формуле можно приписать различные области определения и по-разному определять истинное или ложное значение входящих в нее предикатов на данных аргументах. Здесь нам будет необходимо новое понятие — интерпретация.

Опишем интерпретацию для предикатов из нашего примера. Пусть —

произвольное множество; область интерпретации. , , — его произвольные подмножества. — произвольное подмножество × . — произвольный элемент.

Будем полагать, что в формуле

( ( ( ) ( ))) ( ( ( , Гегель) ¬ ( )))

( (¬ ( ) ¬ ( ))) ( ( ( , Гегель) ¬ ( ))) (31)

предикатам , , и сопоставлены соответственно множества , , и, "Гегелю" сопоставлен элемент , а принимает произвольные значения из .

Тогда ( ) = 1 тогда и только тогда, когда . Аналогично для ( ) и( ). ( , Гегель) = 1 тогда и только тогда, когда ( , ) .

( ( ) ( )) = 1, если .

( ) = 1, если = .

Будем говорить, что вместе с сопоставленными предикатам , , , подмножествами и соответствующим "Гегелю" элементом есть интерпретация

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

Пример 51.2 . Рассмотрим следующую интерпретацию формулы (31): Область интерпретации = N.

Гегель =10.

Легко убедиться, что в данной интерпретации и посылки и заключение истинны. Например, поскольку в данной интерпретации — множество всех

123

чисел кратных четырем, а — множество всех чисел кратных двум, то

и ( ( ) ( )) = 1.

Следовательно = 1 и наше рассуждение является верным в данной интерпретации.

Замечание 51.3 . Заметим, что наше исходное словесное рассуждение на счет сыновей Гегеля не является интерпретацией, поскольку не определена область

интерпретации .

Определение 51.4 . Будем говорить, что формула тождественно истинна (логически общезначима), если ее значение "истина" в любой интерпретации

В общем случае определение, является ли формула логически общезначимой, — алгоритмически неразрешимая задача. Тем не менее, в некоторых частных случаях можно доказать, что формула является тождественно истинной. Покажем это для формулы (31).

Пусть существует интерпретация, в которой наша формула принимает значение "ложь":

( ( ( ) ( ))) ( ( ( , Гегель) ¬ ( )))

( (¬ ( ) ¬ ( ))) ( ( ( , Гегель) ¬ ( ))) = 0.

Тогда, в этой интерпретации все посылки нашего рассуждения истинны, а заключение ложно. Таким образом, существует :

Противоречие доказывает, что такого не существует, что и требовалось доказать.

§52. Формальная теория исчисление предикатов

Определим формальную теорию исчисление предикатов.

1.Алфавит.

1)Предметные переменные: 1, 2, ..., , ...

2)Предметные константы: 1, 2, ..., , ...

Символы логических операций: , ¬. Скобки и запятая: ), (, ,.

2. Формулы.

Формула определяется с использованием понятия "терм".

124

Определение 52.1 .

1)и — термы.

2)Если 1, 2, ..., — термы и — функциональный символ, то ( 1, 2, ..., )

—терм.

3)Других термов нет.

Определение 52.2 .

1)Пусть 1, 2, ..., — термы, — предикатный символ. Тогда ( 1, 2, ..., )

—формула.

2)Если и — формулы и — предметная переменная, то ¬ , и

( ) — формулы.

3) Других формул нет.

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

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

Пример 52.4 .

¬ 21( 1, 1) 2( 3 21( 1, 12( 2, 3)) ( 21( 2, 1) 21( 2, 1))).

В этой формуле переменные 1 свободные, а переменные 2 и 3 — связанные.

Определение 52.5 . Если в формуле нет свободных переменных, она называется замкнутой.

Пример 52.6 . ( 1( 11( 1) 12( 1)) 11( 1)) 12( 1) — замкнутая формула.

В дальнейшем будем писать ( ), подразумевая, что — свободная переменная формулы .

Определение 52.7 . Будем говорить, что терм — свободный для переменнойв формуле ( ), если в нет такой переменной , что переменная в ( ) попадает в область действия квантора .

Пример 52.8 . Пусть ( 1) = 2 21( 1, 2). Тогда терм ′ = 3 — свободный для1 в ( 1), терм ′′ = 12( 2, 3) — не является свободным для 1 в ( 1).

Будем обозначать ( ) формулу, полученную из ( ) подстановкой терма вместо всех вхождений . При этом иногда специально оговаривается, что — свободный для переменной в формуле ( ).

125

Лекция 21. Исчисление предикатов: продолжение

3. Аксиомы.

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

1 ( ( )).

2 (( ( )) (( ) ( ))).

3 ((¬ ¬ ) ((¬ ) )).

4 ( ( ) ( )), где — терм, свободный для в формуле . Если в нет свободной переменной , аксиома принимает вид .

5 ( ( ) ( )), где в нет свободной переменной .

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

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

1)Правило вывода modus ponens (правило отделения): если и произвольные

формулы, то непосредственно выводима из формул и по правилу вывода

modus ponens.

MP = {( , ( ), ) | , — формулы}.

2)Правило Локка (правило обобщения): если — произвольная формула, то из

по правилу обобщения непосредственно выводима формула .

Gen = {( , ) | — формула}.

Замечание 52.9 . Правило Локка можно сформулировать следующим образом: “если свойство принадлежит , где – любой элемент изучаемого множества,

то это свойство принадлежит всем элементам данного множества из его предметной области”

Замечание 52.10 . В алфавит не входят символы , , ≡, . Тем не менее,

мы можем использовать эти символы, как краткую форму записи в некоторых сложных выражениях:

= (¬ ),

= (¬( ¬)),

≡ = (( ) ( )) = (¬(( ) ¬( ))),

= ¬ ¬ .

§53. Интерпретация

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

126

1) Для предметных переменных в интерпретации задается произвольное множество — область интерпретации. Каждая предметная переменная может

принимать произвольное значение из .

2)В интерпретации каждой предметной константе сопоставляется единственный элемент из .

3)Каждому функциональному символу в интерпретации сопоставляется

функция

: × × · · · × → .

Здесь — число аргументов функции, а — номер функции с данным числом

аргументов.

Функциональные символы в частности и термы в общем позволяют косвенно ссылаться на элемент в .

4) Каждому предикатному символу в интерпретации сопоставляется функция

: × × · · · × → {0, 1}.

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

Пример 53.1 . Запишем уравнение = 2 + 2 + 1 на языке предикатов. Область

интерпретации = R. В уравнении есть одно бинарное отношение "=" и действия умножения и сложения над элементами из области интерпретации.

Можно было бы упростить запись использовав другую интерпретацию. Например, введя 11( ) = 2 + 2 + 1, нашу формулу можно будет записать как

( , ) = 21( , 11( )).

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

.

Пусть ( 1 , 2 , ..., ) — формула, 1 , 2 , ..., — все ее свободные переменные.— интерпретация формулы с областью интерпретации .

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

127

функция

: × × · · · × → {0, 1}.

Тогда будем полагать, что

( ( 1 , 2 , ..., )) = ( 1 , 2 , ..., ),

если у нет свободной переменной .

Пусть ( 1 , 2 , ..., ) и ( 1 , 2 , ..., ) — формулы, которым в интерпретациисопоставлены соответственно функции и . Тогда

( ( 1 , ..., ) ( 1 , ..., )) = 1 ( 1 , ..., ) = 1 влечет ( 1 , ..., ) = 1.

Если задана интерпретация, замкнутая формула принимает фиксированное значение — "истина" или "ложь".

Пример 53.2 . Рассмотрим интерпретацию для формулы

( 1) = ¬ 21( 1, 1) 2( 3 21( 1, 12( 2, 3))

( 21( 2, 1) 21( 2, 1))).

Пусть область интерпретации = N, 21 — отношение равенства, 12 — операция умножения, 1 = 1. Тогда формулу можно переписать следующим образом:

( 1) = ( 1 ̸= 1) 2( 3( 1 = 2 · 3) (( 1 = 2) ( 2 = 1))).

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

Пример 53.3 . Пусть задан алфавит:

1)Предметные переменные: 1, 2, ...

2)Предикатные символы 31, 32.

3), ¬, , (, ), ,.

Рассмотрим интерпретацию : = 2 = { | }, где — некоторое множество.

128

Задача: простроить формулы для предикатов

Для одного логического высказывания может существовать много формул описывающих его на формальном языке. Можно предложить, например, такое решение поставленной задачи:

?( 1) = 2 31( 1, 2, 2).=( 1, 2) = 31( 1, 1, 2).( 1, 2) = 32( 1, 2, 1).

1( 1) = ¬ ?( 1) 2( ( 1, 2)

3( 32( 1, 2, 3) ?( 3))).

Определение 53.4 . Будем говорить, что формула выполнима в , если 1

, 2 , ..., : ( 1, 2, ..., ) = 1.

Определение 53.5 . Будем говорить, что формула истинна в , если 1 ,

2 , ..., : ( 1, 2, ..., ) = 1.

Пример 53.6 . Рассмотрим интерпретацию для формулы = ( 1( 11( 1)12( 1)) 11( 1)) 12( 1). Пусть — множество всех когда-либо живших на земле; 11( ) = 1 тогда и только тогда, когда — человек; 12( ) = 1 тогда и

только тогда, когда — смертен; 1 = Сократ.

Тогда формула может читаться следующим образом: "Любой человек

смертен и Сократ — человек. Следовательно, Сократ — смертен."

Формула замкнута и в интерпретации принимает фиксированное значение 1. Таким образом, формула — истинна в данной интерпретации.

Определение 53.7 . Будем говорить, что формула ложна в , если 1 ,

2 , ..., : ( 1, 2, ..., ) = 0.

Определение 53.8 . Будем говорить, что — модель для множества формул, если любая формула будет истинна в .

Определение 53.9 . Будем говорить, что формула выполнима, если существует интерпретация , такая что выполнима в .

Определение 53.10 . — логически общезначима, если истинна в любой интерпретации.

129

Определение 53.11 . Будем говорить, что формула противоречие, если ¬

— логически общезначима.

Определение 53.12 . Будем говорить, что логически влечет ( логическое следствие ), если ( ) — логически общезначима.

Замечание 53.13 . Раньше мы уже приводили определение 53.10 под номером 51.4. Здесь повторяем его, пользуясь строго определенными понятиями.

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

Теорема 53.14 . Пусть — формула исчисления предикатов. Тогда, — логически общезначима тогда и только тогда, когда ИП .

Замечание 53.15 . Поскольку не существует алгоритма, позволяющего определить, является ли заданная формула логически общезначимой, формальная теория исчисление предикатов не является разрешимой.

130