книги / Математическая логика и теория алгоритмов. Логика предикатов

2.4. Операции над множествами

Каждый предикат определяет множество. Выясним, какие множе­ ства определяются предикатами, в определении которых участвуют ло­ гические связки. Напомним, что множество {х [ Р(х)} мы полагаем со­ стоящим из всех таких элементов ж, что Р{х) = И (и только из них). При этом х может быть кортежем длины п — в таком случае пре­ дикат Р является n-местным. В частности, {(x i, ...,x n) | И} = Un,

{(хи ... ,хп) \ Л } = 0.

П ример 2.9. Пусть Р — одноместный предикат и р — высказыва­ ние. Тогда:

если р = И; если р = Л; если р = И; если р = Л;

	{х I р} =	С/,	если р = И;
		0 ,	если р = Л;

У праж нение 2 .6 . Докажите, что

если р = И; если р = Л;

если р = И; если р = Л.

Каждая операция над предикатами определяет равносильную опе­ рацию над множествами. Как и для логических операций, для каж­ дой операции над множествами вводится специальный символ. Прежде чем приводить определения, заметим, что принадлежность множеству Л можно рассматривать как характеристическое свойство элементов мно­ жества А. Иначе говоря, А = { х \ х е А),

Определение 2 .1. Объединением множеств Ап В называется мно­ жество

Al) В = {х \ х е AV х € В}.

Определение 2.2. Пересечением множеств Л и В называется мно­ жество

А П В = { х \ х е А Л х € В } .

Определение 2.3. Разностью множеств А и В называется множе­

ство

А \ В = { х \ х е А Л х $ В}.

Определение 2.4. Симметрической разностью множеств А и В называется множество

А Д В = ( А \ В ) и ( В \ А ) .

Определение 2.5. Дополнением множества А называется множе­

ство

А = { х \ ^ ( х е А)} = и \ А .

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

Введённые операции над множествами обладают следующими свой­ ствами.

1. Z = A n A = A u A = A \Â = A.

2. А ПА = А \ А = 0 .

3 . A U A = U.

4.А \ В = А ПВ .

5.Коммутативность операций объединения и пересечения:

A u B = B ü A ,	АГ\В = В П А .
6. Ассоциативность операций объединения и пересечения:
(A U В) U <7 = Л U (В U £7),	( Л П В ) П С = А п ( В п С ) .

7. Дистрибутивность операций объединения и пересечения:

А и { В п С ) = ( л и в ) п ( л и с ) ,

АП {В U С) = (Л П Б) U {А ПС).

8. Законы двойственности^ или законы де Моргана: л С П в ^ л п в , Х п я = л и в .

Приведем для примера доказательство свойства 4. Чтобы множества были равны, необходимо и достаточно, чтобы они были подмножества­ ми друг друга. Значит, нам нужно доказать справедливость соотношений А \В С АП В и АП В Ç Л \ В. Пусть х £ Л \ В, тогда по определению разности х G Л и х £ В, следовательно, х £ Л и х £ В, то есть по опреде­ лению пересечения х £ ЛПВ. Таким образом, любой элемент множества Л \ В является элементом множества Л П В, и значит, А \ В Ç А п В . Первое соотношение доказано. Проведем обратные рассуждения. Если х £ Л П В, то по определению пересечения х £ Л и х ^ В, то есть х £ Л \ В, значит, Л П В Ç Л \ В. Итак, множества Л \ В и Л П В являются подмножествами друг друга, следовательно, они равны.

Упражнение 2.7. Рассуждениями, аналогичными приведенным выше, докажите по одному свойству из пунктов 5-8.

Нетрудно заметить, что свойства 1-8 записываются весьма похоже на свойства логических связок, приведённые в конце подраздела 2.2. Что­ бы сформулировать, в чём именно заключается это сходство, заметим следующее. Рассмотрим равенства множеств, выраженные через опера­ ции объединения, пересечения и дополнения. Если заменить в них мно­ жества Л, В и С высказываниями a, bи с, множество 0 — ложным выска­ зыванием, множество U — истинным высказыванием, а знаки операций объединения, пересечения и дополнения — соответственно дизъюнкцией, конъюнкцией и отрицанием, — получим верные равенства логики выска­ зываний. Наоборот, любое равенство высказываний, выраженное через операции дизъюнкции, конъюнкции и отрицания, обратной заменой об­ ращается в равенство множеств.

Пример 2.10. Пусть Л, В, С — произвольные множества и

S = ( A \ B ) \ C \ A \ ( B \ C ) .

Попробуем упростить это выражение множества S через множества А, В и С. К решению этой задачи можно подойти по-разному. Используем сначала свойства операций над множествами:

S = ( А П В ) Г \ С п А п В п С =

= 1 п ( в п с ) п ( т в п с ) =

= ( l u ( в п с ) ) п (л П (В UÜ)) =

= ( l u ( Б и с ) ) n ( in (SUC)) =

= ( ( lu (в и с)) n i) n ( s u c ) =

=( ( ln l) U ( ( S U C ) n l) ) n ( S U C ) =

=((S UC) n 1 ) n (B U C) =

=((B U C )n ((B U C )n !) =

=( ( B u c ) n ( s u c ) ) n i =

=( ( B n B ) U C ) n l= ( 0 U C ) n l = C n l .

A теперь воспользуемся описанным выше соответствием между опе­ рациями над множествами и логическими связками. Множеству

S = ( A n B ) r \ C n A r \ B n C

ставится в соответствие высказывание

s = *i((a Л -ib) П “>с) Л

Л *ч(Ь Л -пс)).

С помощью таблицы истинности (см. подраздел 2.2) установим, что зна­ чение высказывания s не зависит от значения Ь} а от значений а и с зависит следующим образом:

а	С	S
и	и	и
и	л	л

ли л

лл л

Отсюда ясно, что s = а Л с. А значит, S = А П С.

U

У каждого из приведённых способов упрощения исходного выраже­ ния есть преимущества. Построение таблицы истинности проще с точ­ ки зрения алгоритма решения задачи — не требуется проявлять изоб­ ретательность при использовании свойств операций. С другой стороны, чтобы заполнить таблицу истинности, необходимо было рассмотреть все различные комбинации значений высказываний a, bи с: 1) а = b = с = И; 2) а = b = И, с = Л; Кроме того, полученная таблица не дает одно­ значного ответа на исходный вопрос — нужно ещё понять, какое именно выражение алгебры логики соответствует полученному набору значений И и Л.

У праж нение 2.8. Сколько комбинаций значений высказываний a, b и с необходимо рассмотреть, чтобы построить таблицу истинности из примера 2.10? А если высказывание s выражается не через три вы­ сказывания, а через п?

Понятия подмножество и декартово произведение также можно ввести с помощью логических операций.

Определение 2.6. Множество А является подмножеством мно­ жества В ) если {х | х е А х € В} = U.

Определение 2.7. Декартовым произведением множеств А и В называется множество

А х В = {(х, у) | х € А А у € В}.

Пример 2.11. Справедливо следующее свойство:

{ж I Р(ж)} х {ж I <Э(ж)} = {(ж, у) I Р(х) А <Э(у)}.

Действительно,	оно следует из определения 2.7 с учётом того, что
ж 6 {z | P(z)}	Р(х) = И и у 6 {г | Q{z)}	Q(y) = И.

Задачи

2.1. Докажите справедливость логических законов:

-i(oiV Von) = (-«Oi)A...A(->an);

->{oi A ... A dn) = (->ai) V V (->a„).

Используйте законы де Моргана и метод математической индукции.

2.2. Дайте определение множества

{(я, у) | х е А V у е В}

через множества А х В и U,

2.3.Докажите, что любое сложное высказываниер, составленное из дан­ ных простых высказываний a i, ... , an, логических связок и скобок, можно представить в дизъюнктивной норамальной форме: в виде дизъюнкции

р = ргУ Vрт,

высказываний pi,... ,рШ| каждое из которых является конъюнкцией

Pi = (&1п Л ... Л bin),

где для любой пары (ij) е {1, ... , т} х {1, .. . ,п} либо Ъу = а; , либо bij = ->aj.

2.4.Докажите, что любое сложное высказываниер, составленное из дан­ ных простых высказываний a i , ... , an, логических связок и скобок,

можно представить в конъюнктивной норамальной форме: в виде конъюнкции

p = P i A . . . A p m,

высказываний p i, ... ,pm, каждое из которых является дизъюнкцией

Pi = (Ьа V V bin),

где для любой пары (г, j) е {1,... ,m} х {1, . . . , п} либо by = <ij, либо bij = -«aj.

2.5.Каким может быть число т в задачах 2.4 и 2.3 (все высказывания Pi предполагаются различными)?

Глава III. Язык логики предикатов

Когда-то Аристотель привел следующий простой пример логическо­ го рассуждения: «Все люди смертны. Сократ — человек. Следовательно, Сократ смертен». С тех пор прошло более двух тысячелетий, но пример Аристотеля продолжает кочевать по учебникам логики и философии. Мы тоже не можем устоять перед искушением использовать его в нашей книге.

Итак, из двух посылок: «все люди смертны» и «Сократ — человек», делается вывод, что Сократ смертен. И справедливость этого вывода не вызывает у нас сомнения. Видимо, здесь работает некоторый логический закон.

Можно представить рассуждение следующим образом. Перепишем посылки так: «если х — человек, то х смертен»; «если х — Сократ, то

х— человек». Поскольку их значение зависит от переменной х, они яв­ ляются предикатами, но мы зафиксируем значение переменной, положив

х= Сократ. Получаем высказывания: «если Сократ — человек, то Со­ крат смертен»; «если Сократ есть Сократ, то Сократ — человек». Будем считать эти высказывания истинными. Высказывание «Сократ есть Со­ крат», естественно, тоже истинно. Теперь, дважды применяя правило modus ропепа, получаем: всё в порядке, Сократ смертен.

Рассмотрим другое рассуждение: «Все люди смертны. Все греки — люди. Следовательно, все греки смертны». Вроде бы, все аналогично, но теперь нас интересует не один из греков, а все греки сразу, иначе говоря, множество греков. А чтобы формально рассуждать о множествах, без предикатов и переменных не обойтись. Значит, требуются также прин­ ципиально новые логические операции.

Такие операции, а также символы, которыми они обозначаются в формальных языках, называются квйнторами1*. В отличие от логи­ ческих связок, которые позволяют получать высказывания только со­ единяя между собой более простые высказывания, кванторы позволяют строить новые высказывания используя предикаты ненулевой местности. Для удобной формальной записи рассуждений классической математики оказывается достаточно двух кванторов. К их изучению мы и приступим.15

15От лат. quantum — сколько.

3.1. Кванторы

Символ V называется квантором всеобщности16. Используется он следующим образом. Пусть Р — предикат и х — переменная. Тогда вы­ ражение Vx Р(х) читается «для всех х (имеет место) Р от х» и означает, что свойством Р обладают все предметы из универсального множества.

Второй квантор имеет вид 3 и называется квантором существова­ ния17. Выражение ЗхР(х), где Р — предикат, х — переменная, чита­ ется «существует такое х, что (имеет место) Р от х» и означает, что по меньшей мере один предмет из универсального множества обладает свойством Р.

П ример 3.1. Чтобы записать на формальном языке утверждение «Не все числа делятся на 2», можно использовать квантор всеобщности V и предикат, утверждающий делимость на 2. Введём предикат Р:

Р(х) х делится на 2,

Теперь нужно перевести на формальный язык предложение: «Неверно, что для всех х имеет место свойство: х делится на 2». Используя кван­ тор V и логическую связку получаем: ->VxP(x).

Замечательно, что то же самое утверждение можно записать, ис­ пользуя не квантор всеобщности, а квантор существования. Действи­ тельно, исходное утверждение «Неверно, что все числа делятся на 2» можно переформулировать следующим образом: «Существует число, для которого неверно, что оно делится на 2*. Переводя на формальный язык, получаем: Зх-«Р(х).

Обратим внимание на важное свойство кванторов, которое в рас­ смотренном примере проявилось в следующем. Несмотря на то что вы­ ражения ->VxP(x) и Зх-»Р(х) содержат переменную х, они являются высказываниями — хотя бы потому, что они являются переводами на формальный язык высказывания «Не все числа делятся на 2». А каждое высказывание является либо истинным, либо ложным, что определяется однозначно и от значений каких бы то ни было переменных не зависит. При этом записанное без кванторов утверждение Р(х) высказыванием

1вЭто перевернутый символ А — первая буква немецкого слова aile — всё.

17Это перевернутый символ Б — первая буква немецкого слова existerez. — суще­ ствовать.

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

Пример 3.2. Запишем на формальном языке утверждение «Все числа, делящиеся на 6, делятся и на 3». Оно равносильно следующе­ му: «Для всех х, если х делится на б, то х делится на 3». Определим предикаты Q и R следующим образом:

Q(x) ^ х делится на 5;

R(x) ч=± х делится на 6.

Получаем:

Vx(iï(x) -> Q(x)).

Запишем также утверждение «Не все числа, делящиеся на 3, делятся на 6»:

-»Vx(Q(x) Д(®)).

Оба рассмотренных утверждения можно записать на формальном языке с помощью квантора существования. Действительно, утверждение «Все числа, делящиеся на 6, делятся и на 3» можно переформулировать следующим образом: «Не существует такого числа х, что х не делится на 3 и х делится на б». На формальном языке получаем:

-»3x(-iQ(x) Л R(x)).

Утверждение «Не все числа, делящиеся на 3, делятся на б» можно сфор­ мулировать так: «Существует такое число х, что х делится на 3 и х не делится на 6». На формальном языке получаем:

3x(Q(x) ЛчД(х)).

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

Заметим сначала, что законы де Моргана, которые мы сформулиро­ вали для двух высказываний, согласно задаче 2.1 обобщаются на любое

конечное их число. А именно, если a i, ... , ап — произвольные высказы­ вания, то

"4*1 V V ап) = (-.ai) Л ... А (-•On);

-•(ai Л ... А ап) = (—iai) V V (->Оп).

Действительно, обе части первого равенства истинны, если и только если все высказывания a i , ... ,Оя ложны; обе части второго — если и только если хотя бы одно из высказываний ai,. . . , ап ложно.

Теперь допустим, что универсальное множество содержит конечное число элементов, а именно га. Обозначим их ... ,гап. Тогда, исходя из естественного смысла логических связок Л, V, V, 3, имеем:

VxP(s) = Р(щ) Л ... Л P(un);

3хР(х) я= P(ui) V ... V P(un).

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

VxP(x) = Р(иi) Л ... Л P(un) =

=V V (-yP{un))) = - 1(За:(->Р(а:)).

3хР{х) = Р{щ) V V P(Un) =

= ~'(hp (ui)) Л ... Л ЬР(ип))) = -i(Vx(-nP(a:)).

Полученные равенства естественно использовать и в тех случаях, ко­ гда количество элементов универсального множества бесконечно. А зна­ чит, для произвольных одноместного предиката Р и переменной х имеют место следующие обобщенные законы де Моргана:

-*УхР(х) = 3x-*P(x)i -*3хР(х) = Væ-iP(x).

Проводя в примерах 3.1 и 3.2 преобразования формальных выра­ жений, мы исходили из естественного понимания их смысла. Сейчас мы видим, что эти примеры демонстрировали действие обобщенных законов де Моргана. Причём в примере 3.2 работали также другие уже известные нам свойства логических связок. Эти логические законы можно приме­ нять для преобразования формальных выражений «автоматически», без рассмотрения содержания.