Определение. Пусть множества Л и В таковы, что из принадлежности х е А следует, что х е В. Тогда говорят, что А есть подмножество В, и обозначают это как А = 2?. Соответствующая диаграмма Венна изображена на рпс. 1.8. Далее, если существует элемент В, который нс принадлежит А, то А называют собственнъщ подмножеством В п записывают в виде А с: В. Это означает, что в некотором смысле ВА, но, как мы впоследствии увидим, та - Рис. 1.8 кие термины могут вводить в больше, чем
заблуждение. Следовательно, при употреблении этого термина требуется проявлять осторожность. Эти отношения могут также быть записаны в обратном порядке, или
Определение. Пусть множества Л и В таковы, что из принадлежности х е А следует, что х е В. Тогда говорят, что А есть подмножество В, и обозначают это как А = 2?. Соответствующая диаграмма Венна изображена на рпс. 1.8. Далее, если существует элемент В, который нс принадлежит А, то А называют собственнъщ подмножеством В п записывают в виде А с: В. Это означает, что в некотором смысле ВА, но, как мы впоследствии увидим, та - Рис. 1.8 кие термины могут вводить в больше, чем
заблуждение. Следовательно, при употреблении этого термина требуется проявлять осторожность. Эти отношения могут также быть записаны в обратном порядке, или
В=>'А и В=зА;
тогда говорят, что В —(собственное) надмножество А.
Очевидно, что для любого множества А справедливы следующие три соотношения:
0<sA, As A, A'=S,
Второе из них является наиболее важным. Говорят, что множества А и В эквивалентны (записывается как А =• == В), если
^sB и 5s A.
Это означает, что все элементы А являются элементами В, а все элементы В—элементами А. II
Используя определение эквивалентности множеств, докажем теперь идентичность некоторых множеств, разобрав серию пз пяти примеров. Они являются примерами доказательств. Поэтому мы обязаны кратко рассмотреть вопрос о том, почему следует заботиться о доказательствах в компьютерной пауке. Строго говоря, как это обычно делается, мы должпы доказать что-либо только одпп раз. Затем мы исходим пз того, что эта часть ипформации является правильной и, следовательно, может рассматриваться как факт. Однако, как бывает в большинстве аспектов вычислительной науки, метод, которым мы получаем результат, по крайней мере так же важен, как и сам результат. После анализа доказательства становятся ясными сделанные предположения и последствия, к которым они приводят, а также становятся понятными процессы вывода, которые можно использовать при решении других задач. (Аналогично проведению эксперимента на ЭВМ с подобными структурами данных при их использовании в программировании.)
Можно также заметить, что доказательства теорем формируют основу всех решающихся автоматически задач, но это будет обсуждаться позднее. Рассмотрим несколько примеров.
В примере 4.1 непосредственно доказывается справедливость следующих двух соотношений;
а) АГ\(ВиС)е(АПВ)\)(АГ\С);
б) (AГ}B){J(AПC)C=AП(B^}C].
Каждое из этих доказательств состоит из последовательности утверждений вида
“если Р, то Q”
(если справедливо Р, то справедливо и Q). Для удобства запишем это утверждение как “Р с*- Q” и будем читать
“из Р следует Q”.
Следовательно, если имеется последовательность Р0, Р,,..., Р„ такая, что Ро ^ P1, p1 ^ P2,..., Pn-i -*- Р“ (из Ро следует р|, из р) следует Ps, ..., из P„-i следует Р„), то мы имеем прямое доказательство Ро с> Рп.
Пример 4.1. Относительно множеств А, В и С докажем, что
' А П(В\]С)=(А ПД)и(Л ПС)'.
Доказательство.
хеД П(В[}С)^ хеА и хе(В\}С}^
(Такая группировка необходима, так как скобки означают, что объединение следует вычислить перед_ пересечением.) ,
=<• х е А п (х е В плп х <= С) =>'
^ (х е= А и х е В) или {х s А и х е С]=>
^ [х е А П В) пли (х е А Л С)^ х е (Л П В) U (Л П С),
У>
Таким образом,
А П(5и C)s(A П B)\j{A ПС).
Сейчас необходимо доказать включение s в обратную сторону:
же (А П В) U (Л П С) =>
'=> (х е А П В) или (х е А П С) =>
=^(х е А и х (= В) или (х <= А п х •= С)^-
^ x<s А а (хе В или х е С) =>
^ х<=А u xeBUC^ .с е А П (5 U CJ.
Следовательно,
(A n5)U(A Л С) s Л П (5 U С'). Поэтому
'А П (В U С) = (А П В} U (А П С). II
В этом частном случае вторая часть доказательства точно совпадает с первой, и, следовательно, можно записать
xf=An(B\JC)^>-xe=A и деДиС ит. д.
Здесь символ “-<=”'” (“Р -*3”- Q”} означает, что Р => Q и Q "> Р. Он может читаться как “тогда и только тогда” (иногда также читают “если и только если”) и означает эквивалентность двух утверждений Р и Q. Однако не всегда так просто обратить аргумент и следствие. В общем случае мы должны провести доказательства в обе стороны раздельно. Заметим также, что эквивалентность может быть легко получена (хотя и не доказана) из подходящей диаграммы Венна, однако не всегда можно начертить диаграмму, относительно которой можно быть уверенным, что она настолько отвечает требованиям, насколько необходимо. Поэтому непосредственное доказательство необходимо. Это доказательство зависит от внутренних взаимосвязей между значениями “и” и “или” и, следовательно, может быть выбрано для каждого случая своим. Далее, когда будут определены некоторые алгебраические структуры, мы покажем, что это не составляет трудностей.
Примеры 4.2—4.5 также используют прямые доказательства, однако эти доказательства записаны в несколько другом виде.
Пример 4.2. Относительно данного множества S дополнение любого множества А{А'=-§} единственно.
Доказательство. Предположим, что существует два множества В п С, каждое из которых удовлетворяет требованиям дополнения А, т. е.
ДПЛ==СП^=0 ы 5иЛ-С1М--<Г. Тогда
В = 5 Л S = 5 П (С U AJ= (5 П С) U (5 Л Л) -
= (Д Л С)U 0 = fi П С;
поэтому
хеВ=>хеВ a xeC^BsBf\C=>BsB u ^ С.
Однако мы знаем, что В е В, Поэтому отсюда следует, что
Бег С.
Аналогично (меняя ролями В и С) получаем
CsB,
откуда
В = С, т. е. В = С =А', и А' единственно, //
Приведенный выше пример содержит в себе основной математический подход, употребляемый для доказательства единственности,— сначала предполагается, что существуют два таких объекта, а затем доказывается, что они совпадают.
В следующем примере мы опять прибегнем к предположениям об “или”, чтобы иметь возможность написать выражение А U В U С как А U (В U С) или (Л U В) U С, когда это будет более удобно для требуемых преобразований.
Пример 4.3, Даны множества А, В и С такие, что
AUBUC^y е. А, В а. С попарно не пересекаются. Тогда
• И' = В U С, В' = А U С и С' = Л U С.
Доказательство.
Л U Д U С ° И U (Д U С)" S, 'А П (5 U С) = (Л Л 5) U (Л П 6') - S3 u 0 = 0.
Следовательно, В U С удовлетворяет условиям для А', которое единственно. Поэтому А '=В U С,В' и С'. // Аналогично проводятся доказательства для