Элементы логики предикатов (стр. 1 )

2. ЭЛЕМЕНТЫ ЛОГИКИ ПРЕДИКАТОВ

2.1. Формулы логики предикатов и их преобразование

Сводка теории

Функция n переменных (n = 1,2,...) с непустой областью определения, множество значений которой содержится во множестве {1,0}, называется n-местным предикатом.

Если область определения n-местного предиката имеет вид , т. е. все независимые переменные пробегают одно и то же множество, то говорят, что предикат определен на множестве М.

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

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

Если F – свойство элементов множества M и F(x) – соответствующий этому свойству предикат (определенный на M), то предложение: «все элементы множества M обладают свойством F» или «каждый (или любой, или всякий) элемент множества M обладает свойством F»- записывается в виде: ; а предложение: «во множестве M существует (или есть, или имеется, или найдется) элемент, обладающий свойством F» – в виде .

Читаются эти выражения так: «Для всякого (или для всех) »; «Существует x такое, что F(x)».

Выражения и называются квантором общности (или всеобщности) и квантором существования соответственно. При этом обычно говорят: «квантор по переменной x».

Можно рассматривать постановку квантора общности и квантора существования перед знаками предикатов («навешивание» кванторов или «квантификация») как особые операции.

Навешивание квантора общности есть операция, сопоставляющая одноместному предикату F(x) высказывание – истинное, если F(x) тождественно-истинен, и ложное в противном случае. Навешивание квантора существования есть операция, сопоставляющая одноместному предикату F(x) высказывание – ложное, если F(x) тождественно ложен, и истинное в противном случае.

Операции навешивания кванторов общности и существования сопоставляют каждому n-местному предикату (n-1)-местные предикаты и соответственно. В последних двух предикатах переменная называется связанной, остальные переменные – свободными (или параметрами).

Логико-математический язык первого порядка (первой ступени) L задается набором из четырех множеств:

a) (индивидные) переменные x, y, z, ...;

b) n-местные (индивидные) функциональные символы F, G, H, ... для каждого n;

c) n-местные (индивидные) предикатные символы P, B, S, ... для каждого n;

d) логические связки и кванторы.

Любой 0-местный функциональный символ является (индивидной) константой, 0-местный предикатный символ – логической (пропозициональной) константой.

Если задан язык L, то можно определить некоторые правильно построенные тексты, составленные из символов L и вспомогательных символов – скобок и запятых. Эти тексты называются выражениями языка L и подразделяются на термы и формулы.

Определение

i) Переменная языка L есть терм;

ii) если – k-местный функциональный символ языка L и - термы, то выражение F() есть терм языка L. Коротко это запишем в виде правила вывода:

.

Это обобщенное индуктивное определение показывает, что каждый терм имеет один и только один вид из следующих двух: переменная или константа (из правила ii как 0-местная функция) языка L, либо функция от термов. Таким образом, термы – это те выражения языка, значениями которых являются индивиды. Роль термов состоит в том, чтобы описывать именные формы и имена индивидов.

Определение

Если P – k-местный предикатный символ языка L, а суть термы, то выражение P() называется атомарной (или элементарной) формулой.

В частности, если P – пропозициональная буква (0-местный предикатный символ), то P сама по себе является атомарной формулой.

Определение

i) Каждая атомарная формула есть формула;

ii) , т. е. если уже построена формула A, то разрешается построить новую формулу ; подобным образом следует трактовать и следующий пункт:

iii) , где – любая логическая связка;

iv) , т. е. если уже построена формула A, и x – произвольная переменная языка L, то разрешается построить новую формулу ; так же следует трактовать и следующий пункт:

v) .

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

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

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

Свободные и связанные переменные играют различные роли в формуле. Во-первых, вместо связанной переменной нельзя подставить конкретное значение – получится бессмысленное выражение. Во-вторых, связанная переменная не имеет самостоятельного значения, ее можно заменить на другую переменную, и смысл формулы от этого не изменится.

Все формулы: , , - выражают один и тот же предикат, одну и ту же функцию от x, z. Такая операция называется переименованием связанной переменной.

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

Например, если в формуле мы решим заменить переменную y на переменную x, то получится формула , которая имеет совершенно иной смысл, чем исходная формула. Формула зависит уже лишь от одного параметра z, а не от двух. Причина состоит в том, что после неудачного переименования связанной переменной y первое вхождение переменной x, которое раньше было свободным, стало связанным. Это явление называют коллизией переменных при переименовании связанных переменных. Коллизия переменных недопустима.

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

Определение

Формулы Ф и Y равносильны (Ф Y), если:

·  множества их свободных переменных совпадают;

·  при любом замещении входящих в формулы Ф и Y предикатных символов конкретными предикатами эти формулы переходят либо в один и тот же предикат, либо в высказывания, имеющие одно и то же истинностное значение (последнее – в случае, когда Ф и Y замкнуты, т. е. множества их свободных переменных пусты).

Разумеется, все вхождения одного и того же предикатного символа как в Ф, так и в Y должны замещаться одним и тем же предикатом.

Определение

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

Замечания

1) Тождественно-истинная формула и тождественно-истинный предикат – не одно и то же. Тождественная истинность конкретного предиката относится только к его области определения, в то время как тождественная истинность формулы – это «абсолютная истинность», истинность для любых предметных областей. Аналогично – для тождественной ложности.

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

3) Отрицание тождественно-истинной формулы есть, очевидно, формула тождественно-ложная, а отрицание тождественно-ложной – тождественно-истинная.

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

I) Перестановка одноименных кванторов:

; (I.1)

. (I.2)

2) Связь между разноименными кванторами:

; (II.1)

. (II.2)

3) Вынесение кванторов за скобки:

;	(где Ф не содержит свободной переменной x)	(III.1)
;	(III.2)
;	(III.3)
.	(III.4)

Замечание

Условие, чтобы формула Ф не содержала свободной переменной x, в соотношениях (III.1 – III.4) является существенным: если оно не выполнено, то соотношения могут нарушаться (после вынесения квантора переменная x в формуле Ф из свободной может превратиться в связанную).

4) Переименование связанных переменных:

;	(вместо x и y можно брать любые другие переменные)	(IV.1)
.	(IV.2)

Замечание

Все введенные равносильности останутся справедливыми, если заменить в них F(x) (соответственно F(x, y)) любой формулой G, содержащей свободную переменную x (соответственно x и y) и, возможно, также и другие свободные переменные.

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

Утверждение 2.1

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

Утверждение 2.2

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

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

Примеры

Пример 2.1

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

а) если х делится на у и у делится на z, то х делится на z;

б) х – простое число.

Решение

а) Разбивая фразу на простые предложения, видим, что используется только одно свойство двух объектов, поэтому введем предикат = « делится на «. Речь идет, очевидно, о делимости нацело, поэтому областью определения предиката будет множество целых чисел: .

Структура всей фразы описывается конструкцией «если..., то...», значит, самой внешней (последней) связкой нашей формулы будет импликация. Посылка этой импликации описывается конъюнкцией простых предложений, поэтому итоговая формула имеет вид:

.

б) Самый простой подход: ввести предикат = « – простое число», который и описывает всю фразу.

Но математические термины должны быть определены однозначно (что такое «простое» число, которое записывается одной цифрой? или которое записано с помощью повторения одной цифры? или которое можно легко запомнить или записать?), поэтому точный смысл этой фразы может быть воспроизведен с помощью строгого определения. То есть « делится только на 1 и на себя» или, еще точнее, «либо , либо и если делится на любое , то, или , или «.

В последней фразе использован предикат делимости (см. пункт а), предикат равенства = «« и квантор всеобщности. Поскольку понятие простого числа обычно вводят только для натуральных чисел, то . Формула, описывающая последнюю фразу, имеет вид:

.

Пример 2.2

Указать свободные и связанные вхождения переменных в формулы:

а) ;

б) ;

в) .

Решение

Проанализируем область действия каждого квантора, отмечая связанные вхождения общей прямой с засечками снизу, а свободные вхождения переменных стрелочкой сверху. Отметим, что в третьей формуле F и G – функциональные символы (в теориях первого порядка аргументом предиката не может выступать другой предикат).

¯ ¯

а) ;

¯ ¯

б) ;

¯

в) .

 

Пример 2.3

Доказать тождественную истинность формул:

а) ;

б) .

Решение

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

а) . Значит, исходная формула тождественно истинна.

б)

.

Значит, исходная формула тождественно истинна.

Пример 2.4

Доказать тождественную ложность формул:

а) ;

б) .

Решение

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

а).

Значит, исходная формула тождественно ложна.

б)

.

Значит, исходная формула тождественно ложна.

Задачи

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

а) «Если произведение двух чисел делится на простое число, то на него делится хотя бы один из сомножителей»;

б) «Через всякую точку, не лежащую на прямой, можно провести прямую, перпендикулярную данной»;

в) «Через каждые две точки можно провести прямую, причем, если эти точки различны, то такая прямая единственна»;

г) «Когда у некоего деятеля денег в избытке, он может воспевать что угодно, в том числе и отсутствие денег»;

д) «Всякий кулик свое болото хвалит, а чужое хает».

2.2. Пусть – одноместный, – двухместный, – трехместный функциональные символы. Являются ли термами следующие слова:

а) ;

б) ;

в) ?

2.3. Пусть , , – те же, что и в задаче 2.2, – одноместный, – трехместный предикатные символы. Являются ли формулами следующие слова:

а) ;

б) ;

в) ;

г) ?

2.4. Выписать все подформулы формулы:

а) ;

б) .

2.5.

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

б) То же для формулы .

в) То же для формулы .

2.6. Доказать тождественную ложность формул:

а) ;

б) .

2.7. Доказать, что:

а) ;

б) .

2.2. Приведение формул к предваренной
нормальной форме (ПНФ)

Сводка теории

Определение

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

Если и B – предваренная формула, то B называют предваренной (нормальной) формой (ПНФ) формулы A.

В частности, не исключается и случай n = 0, т. е. бескванторная формула также считается предваренной.

Теорема 2.1

Для всякой формулы существует ПНФ.

Доказательство. С помощью основных логических законов устраняем в формуле все знаки логических операций, кроме (если таковые имеются).

К полученной формуле последовательно применяем в произвольном возможном порядке преобразования двух типов: А и В.

Преобразование типа А. Находим в формуле некоторую часть (подформулу) Ф, имеющую вид , или , или , или , где F, G(x) – какие-то формулы и G(x) содержит свободную переменную x. Пусть для определенности (в остальных случаях все делается точно так же).

Преобразуем Ф следующим образом: проверяем, содержит ли F переменную x, и если нет, то замещаем Ф на (соотношение (III.1)), если да, то заменяем все вхождения x в вхождениями какой-либо новой переменной, скажем, t, не встречающейся в нашей «боль-шой» формуле (соотношение (IV.1)), и затем заменяем на . Таким же образом поступаем с подформулами остальных трех видов (это возможно ввиду коммутативности конъюнкции и дизъюнкции).

Преобразование типа В. Находим в формуле некоторую подформулу, имеющую вид (или ), где G(x) – формула со свободной переменной x, и заменяем ее на (соответственно на ) по соотношениям (II.1), (II.2).

Применяя преобразования типов А и В, мы шаг за шагом «вытаскиваем наружу» все кванторы и, в конце концов, приходим к формуле, в которой ни один квантор не стоит внутри конъюнкции или дизъюнкции, или вслед за отрицанием. Но в такой формуле квантор может стоять только либо вслед за другим квантором, либо в самом начале формулы, т. е. получена ПНФ для исходной формулы.

Замечания

1) В доказательстве указан практический способ приведения формул к ПНФ. При фактическом приведении удобно «по пути» устранять двойные отрицания всякий раз, когда они возникают (а также производить любые другие упрощения, если они возможны).

2) В силу соотношений II. 1 – II 2 отрицание формулы равносильно формуле , где – квантор, «противоположный» Qi .

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