Заметим также, что определение объединения использует включение “или”, называемое так потому, что оио включает “и” так, что
{1, 2} U {2, 3}={1, 2, 3}, {1, 2} П {2, 3} = {2}.
Элементы в пересечении множеств (в данном случае это — единственное число 2) включаются в объединение, Это обычная математическая договоренность, и существует пример, в котором математическое значение является более точным, чем при общем употреблении.
Пример 2.1. В предположении, что каждый день или дождливый, или ясный, математическим (или логическим) ответом на вопрос
“Ясно или дождливо сегодня?”
Заметим также, что определение объединения использует включение “или”, называемое так потому, что оио включает “и” так, что
{1, 2} U {2, 3}={1, 2, 3}, {1, 2} П {2, 3} = {2}.
Элементы в пересечении множеств (в данном случае это — единственное число 2) включаются в объединение, Это обычная математическая договоренность, и существует пример, в котором математическое значение является более точным, чем при общем употреблении.
Пример 2.1. В предположении, что каждый день или дождливый, или ясный, математическим (или логическим) ответом на вопрос
“Ясно или дождливо сегодня?”
16
будет “Да”.
Определение. Разность множеств А и В (также называемая дополнением В до А) записывается в виде А\В и определяется соотношением
А\В={х: х е А и х/еВ}.
Поэтому, если А={1, 2, 3} и В = [2,3, 4} то A\B={1} и В\А = {4}.
Следующее определение включено для полноты. Хотя мы будем редко использовать его непосредственно, однако, как мы увидим в дальнейшем, этот оператор имеет большое значение в машинной арифметике.
Определение. Симметрическая разность множеств A и B, т. е. A??? B, определяется как
Л???B=(A U B)\(A ??? B).
Возможно, читателя запутали обозначения U, ???, \, ???, или, наоборот, он поверил, что они настолько элементарны, что не имеют никакого практического применения, Следующие примеры помогут в этом разобраться.
Припер 2.2. Предположим, что мы имеем две программы, называемые Р и Q, и что A — множество всех значений данных, доступных Р, а В — множество всех значений данных, доступных Q. Тогда A ??? В —Р и Q; А U В — множество всех данных, доступных по крайней мере или Р, или Q; множество всех данных, доступных
А \В -- множество всех данных, доступных Р, но недоступных Q; В\А — множество всех данных, доступных Q, но недоступных Р; А ??? В — множество всех данных, доступных только одной из программ Р или Q.
Чтобы полностью определить А и В, мы должны знать некоторые данные о вычислениях, связанные с Р и Q. В нашем случае достаточно сказать, что они производятся на некоторой конечной ЭВМ.
Перед дальнейшим изложением будет удобно определить два специальных множества, Первое из них — пустое множество.
Определение. Пустое множество (обозначается ???) есть множество, обладающее свойством
x ??? 0 при любом х.
Второе множество, определение которого зависит от задачи, называют универсальным множеством,
2 Д. Кук, Г. Бейэ 17
Определение. Универсальное множество (обозначается ???} есть множество всех рассматриваемых в данной задаче элементов.
Ограничение ??? в этом случае помогает избежать трудностей, подобных тем, которые возникали при рассмотрении “множества” F примера 1.1; в любом случае большинство элементов несущественно в каждой данной задаче. Например, размеры “Английского словаря”, несомненно, неинтересны, если рассматривается поведение отдельной программы на Фортране.
Определение. Два множества А и В не пересека-ются, если А ??? В ==???.
Определение. В каждом случае, когда ??? задано, определим дополнение множества А (обозначается А'}, как
'A'==???\A={x: х???А}.
Из определений ???, ??? и А' следует справедливость тождеств
'А U 'А'=???, 'A ??? A'=???.
В § 4 будет показано, что для данного ??? эти тождества достаточны, чтобы однозначно определить А'. Пример 2.3. Пусть
???={1.2,3,4}, 'А ={1, 3,4}.B={2,3}, С ={1,4}.
Из определений легко найти, например, А', В ??? С, С\А и т. д. Однако может понадобиться исследовать более сложные выражения, включающие две или более операций. Поскольку в этих случаях встает вопрос, как определить порядок, в котором мы должны осуществлять элементарные операции над множествами, будем использовать скобки. Каждое выражение, заключенное в скобки, должно быть выполнено перед тем, как его результат может быть использован в других вычислениях. Например, в (А П В)' пересечение ({3}) вычисляется раньше, чем дополнение ({1,2,4}). Этого соглашения, очевидно, достаточно. Однако, чтобы избежать такого множества скобок, мы не будем требовать скобок, когда хотим произвести операцию дополнения перед любой из операций с множествами (U, ???, ???, ???}. Поэтому А???В' означает А ???(В') и т, д. Следовательно,
А ??? B'=A ??? {1,4} ={1,4}, (А ??? В} '={3}'= {1,2, 4}, (B\A)UC=={2}UC={1,2,4}.//
18
Читатель может быть удивлен, почему изложение построено на понятии множества, а не числа. Действительно, до сих пор мы использовали числа только как элементы множеств. Это делалось лишь для того, чтобы читатель познакомился с объектами, с которыми ему при-дется работать. Дело в том, что существуют множества более сложные, чем числа; мы можем получить числа из множеств, но пе наоборот. Однако для многих приложений последующей теории необходимо сделать точные утверждения о некоторых специальных множествах чи-сел. Чтобы обеспечить основу, с помощью которой будут конструироваться такие множества, определим множество N целых положительных чисел (натуральных чисел):
N={1,2,3, ...).
Точное определение множества N вместе с арифметическими операциями + и * и его упорядочивание будут даны ниже. Однако в настоящей главе мы будем предполагать, что читатель знаком с некоторыми свойствами N. Аналогично Z определяют как множество всех целых чисел:
Z={..., - 2, - 1, О, 1, 2, ...).
Конечно, множества N и Z не могут быть выписаны явно (они достаточно велики), но в настоящее время мы должны понимать "..." как “и так далее”.
Рассмотрим теперь множество
A={1, 2, ..., п}-={х: x???N,1<=x<=n}.
Оно имеет п элементов. Будем говорить, что мощность (или размер, норма, длина} этого множества есть п. Это обозначается как
Ш == card (/4)== п.
Далее любое множество В, которое имеет то же число элементов, что и А, имеет такую же мощность, и, конечно, эти элементы не надо пересчитывать. Для небольших множеств достаточно легко пересчитать элементы, но для других множеств (например, N) это может быть невозможно. Далее мы дадим строгое, но в то же время неформальное правило для вычисления количества элементов.
Определение. Говорят, что множество Х конечно, если Х == 0 или если для некоторого п ??? N существует множество {1, 2, .,., п} такое, что оно имeет то же самое
19
число элементов, что и X. Если Х <> ??? и никакого п не может быть найдено, то Х называют бесконечным.
Сейчас, когда мы ввели некоторые определения, можно сформулировать несколько упражнений. Чтобы сделать множества легко записываемыми, мы снова будем использовать числа и буквы для элементов, но будем помнить, что те же операции могут быть применены к произвольным множествам.
Упражнение 1.2,
1. Пусть
^={1,2,3,4}, Х={1,5}, У "{1,2, 4), Z={2,5).
Найти множества:
а) ХП Г; б) (XnZ)U У;
в) XU(7nZ);r) {XU Y)f\(X\JZ];
д) (XU7)';e) ГПГ;ж) (X О У)';
з) (XU r)UZ; и) Х1)(Уи2); к) X\Z;
л) (X\Z)U(y\Z). 2. Пусть
^ ° {а, Ь, с, d, e, / }, B={/,е,с,a},
Найти множества:
а) А\С\ б) В\С; в) С\В;
г) А\В; д) A'U5; e) В Л А';
ж) А ПС; з) СП А; и) САЛ.
3. Даны два произвольных множества А и В такие, что А ??? В = ???. Что представляют собой множества А\В п B\A?
4. Даны два произвольных множества С и D такие, что С П D'•=???0. Что можно сказать ????????? ?
5. Дано произвольное множество X. Найти множества:
а) ХПХ'; б) XUX'; в) Х\Х'.
6. Какие из следующих утверждений справедливы:
а) 0 е0; б) 0-{0}; в) |{0}| "1;
г) {{0}}е{{{0}}}; д) |{{0})|"2? Это вопрос коварный. Хотя это может показаться простым или надуманным, пустое множество и его свойства являются достаточно важными. Если вы не совсем уверены в ответе, проработайте вопрос, используя аналогию портфеля вместо множества. Таким образом, {{}, {)} — портфель, содержащий два пустых портфеля, и, следовательно, |{{}, (}}| =2 и т, д,
20
7. Пусть М и N — два конечных компьютера (см. пример 2.2) с фиксированными программами. Далее пусть А — множество значений данных, доступных М и таких, что если х ??? A и машина М работает с входным словом х, то М останавливается и выдает результат. Аналогично пусть В — множество значений данных, которые приводят N' к остановке и выдаче результата. Если любой элемент А доступен М и N, что мы может сказать об элементах B'? Объяснить эту ситуацию с помощью символов п пояснить бесполезность этой информации.
8. Объяснить в терминах множеств, почему пример 2.1 верен.
9. При определении операции объединения подчеркивалось, что мы использовали включение “или”. Как в терминах множеств можно выразить исключающее “или”?
10. Часто в вычислениях будут использоваться арифметические операции для образования новых множеств. Так, если А а В — множества чисел, то
'А + В =• {х; х = а + Ь, а ег А, Ь е В}. Аналогично определяются операции *,—",/ между множествами чисел. Найти следующие множества:
11. Для того чтобы быть в состоянии применить технику операций с множествами к конкретной задаче, мы неизбежно должны на некотором этапе взять “нематематическое” утверждение и перевести его в математическое. Обычно (но не всегда) это делает описание более компактным. Однако математическое выражение будет всегда математически строгим, тогда как исходное выражение может таким не быть. (Где это случается, требуется найти, чего же недостает в первоначальной формулировке.) Теперь надо:
а) попытаться сформулировать следующие утверждения на языке множеств;
— даны множества А, В и С; определить множество, включающее в себя только два из этих множеств;
— решить предыдущую задачу при условии, что А,В и С взаимно не пересекаются;
— даны множeства V, W, Y, X и Z. Определить множество, включающее по крайней мере два из множеств V, W, Х и Y и не включающее Z;
б) аналогично описать словами следующие множества:
(Jf){K[]L))'[l(H\L], (P[)RUQ)\(Pr\(Q\f{)], {(E\F)[}[F\E))'[)G.