Кук Д., Бейз Г. - Компьютерная математика, страница 4

Даны два произвольных множества С и 0 такие, что С П В' И. Что можно сказать о С П В и С 0 М 5, Дано произвольное множество Х, Найти множества: а) ХП Х', б) Х 0 Х'; в) Х~Х'. 6. Каине из следующих утверждений справедливы: а) Ож И; б) Э (О); в) !(Ю! 1( г) ((И)) ж(ИИ))); д) !(И)Н 2) Это вопрос коварный. Хотя это может показаться простым или надуманным, пустое множество и его свойства явля- ются достаточно вал~ными.

Если вы не совсем уверены в ответе, проработайте вопрос, используя аналогию порт- феля вместо множества, Таким образом, Н), (И вЂ” порт- фель, содержащий два пустых портфеля, и, следователь- но,!((), (Н! 2 и т. д, 20 7. Пусть М и )«' — два конечных компьютера (см. пример 2.2) с фиксированными программами. Далее пусть А — множество значений данных, доступных М и таких, что если х «еА и машина М работает с входным словом х, то М останавливается и выдает результат. Аналогично пусть  — множество значений данных, которые приводят У к остановке и выдаче результата. Если любой элемент А доступен М и У, что мы может сказать об злементах В'1 Объяснить эту ситуацию с помощью символов и пояснить бесполезность этой информации.

8. Объяснить в терминах множеств, почему пример 2А верен, 9. Прн определении операции объединения подчеркивалось, что мы испольэовали включение «или», Как в терминах множеств можно выразить исключающее «или»1 10. Часто в вычислениях будут использоваться арифметичоские операции для образования новых множеств. Так, если А и  — множества чисел, то А + В (хл х а + Ь, а «э А, Ь ж В). Аналогично определяются операции «, —, l между множествами чисел. Найти следующие множества: а) (1, 2) + (1, 3); е) (1,2)Ч1,3); б) (1,2) О (1,3); ж) (2, 4)/(2); в) (1,2) «(1,3); а) (2,4Н2); г) (1,2) О (1,3); и) (2,4) — (2).

д) (1,2) — (1,3); 11. Для того чтобы быть в состоянии применить технику операций с множествами к конкретной задаче, мы неизбежно должны на некотором этапе взять «нематематическое» утверждение и перевести его в математическое. Обычно (но не всегда) зто делает описание болев компактным. Однако математическое выражение будет всегда математически строгим, тогда как исходное выражение может таким не быть.

(Где это случается, требуется найти, чего я~е недостает в первоначальной формулировке.) Теперь надо: а) попытаться сформулировать следующие утверждения на языке мноясеств: — даны множества А, В и С; определить множество, включающее в себя только два из этих множеств; — решить предыдущую задачу при условии, что А, В и С взаимно не пересекаются; «1 — даны множества Р, И', Г, Х и Я. Определить множество, включающее по крайней мере два из мпожеств У, И', Х и У и не включающее 3; б) аналогично описать словами следующве множества: рп(кнц) и(н~ц, (р и Е и др(р П(д~в) ), ((Е~Е)0(Г~Е))' 0 б. й 3. Диаграммы Венна Уже можно было заметить некоторые специфические свойства операций над мно>кествамн, в особенности то свойство, что одно и то же множество молгет быть определено различными путями.

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

1Л го математика Джона Венка) и строят, как зто описано ниже. Во-первых, начертим большой прямоугольник, представляющий д' (рис, 1А). Во-вторых, начертим круги (или какие-либо другие подходящие замкнутые кривые) внутри прямоугольника, чтобы прецставить множества. Они должны пересекаться в наиболее общем случае, требуемом в задаче, и должны быть соответствующим образом обозначены (рис. 1.2). Точки, которые лежат внутри различных областей диаграммы, сейчас могут рассматриваться как элементы соответствующих множеств. Если число элементов в множествах мало, тогда отдельные элементы могут быть записаны внутри подходящих областей, как это показано в примере 3.1.

Пример 3.1. Пусть Ю- (Ь, с,д,е), А =(б,с, А),  — (с, е), Соответствующая диаграмма изображена па 22 рис. 1.3. Этот рисунок полностью иллюстрирует пример 3.1, обеспечивая анание элементов д'. Если же, например, А ж Ю, тогда неясно, что предполагалось изобразить на диаграмме. В тех случаях, когда используются Рис, 1.2 Рас. ьв болев сложные конструкции множеств, следует избегать изображения кх в виде диаграмм. Имея построенную подходящим образом диаграмму, мы можем заштриховать определенные области для обозначения вновь образованных множеств. П р и м е р 3.2. Чтобы представить множество А 0(В' П С), начнем с общей диаграммы, показанной на рпс.

1.4. Заштрихуем В' диагональными линиями в одном направлении, а С диагональными линиями в другом Рпс, 1,3 Рас, 1.4 направлении (рнс. 1.5), Площадь с двойной штриховкой представляет собой мнолсество В' П С. На новой копии диаграммы заштрихуем эту область горизонтальными ляннямп, а А вертикальными. Вся заштрихованная на рис. 1.6 область представляет множество А 0(В'() С). Если в отдельных случаях мы имеем дополнительную информацию о рассматриваемых множествах, то ее можно использовать для упрощения днаграммы Ванна.

23 Пример 3.3. Пусть А ДВ=О; зто соответствует диаграмме на рис. 1,7. г' Заметим, что в большинстве случаев множества содержат довольно много элементов, и, следовательно, эти влементы не могут быть представлены отдельно, Поэтому Рас. $.6 Рвс, 1.7 более удобно в атом случае говорить о кап<дом из множеств как о делом и не упоминат отдельных элементов. Упражнение 1,3.

1. Начертить диаграмму, иллюстрирующую построение множеств, рассматриваемых в задаче 1 упражнения 1.2. 2. Как можно представить следующие множества, используя диаграммы Венка; (А, (АИ, ((а), И), (Х, У, 2), где Х (х: х 1 или (х — 2)жХ), У (х: х 3 илп(х — 3)ы У), 2 (х: х 2 или (х — 2)ыЙГ $ 4. Подмножества и доказательства Операции пересечения, объединения, разности н дополнения позволяют нам формировать новые множества. Однако, как правило, мы не можем сказать, как одно множество соотносится с другими. Например, пусть даны два множества Х и У; пересечение ХП У в некотором смысле «меньше» (или по крайней мере не больше), чем Х.

Действительно, все влементы множества Х й У принадлежат также множеству Х, Из этого наблюдения можно формально определить равенство множеств и различных выражений для того же самого множества. С по- 24 мощью этих определений ьсы также в состоянии написать подходящие логические доказательства вансных фактов, относящихся к мнонсествам. Зти результаты, хотя и очевидны, обеспечивают подходящие ситуации, в которых можно ввести некоторые из основных способов доказательств, используемых в дальнейшем. Определение. Пусть множества А п В таковы, что из принадлежности х ввА следует, что х си В, Тогда говорят, что А есть подмножество В, и обозначают это как А ш В.

Соответствующая дкаграмма Венна изображена на рпс. 1.8. Далее, если существует элемент В, который не принадлежит А, то А называют собственным подмножеством В и записывают в виде А ~В. Это означает, что в некотором смысле В больше, чем А, но, как мы впоследствии увидим, та- Рис. 1.8 кпе термины могутвзодпть в заблуждение. Следовательно, при употреблении этого термина требуется проявлять осторожность. Зти отношения могут также быть записаны в обратном порядке, или В~А и ВнэА; тогда говорят, что  — (собственное) надмножество А.

Очевидно, что для любого множества А справедливы следующие три соотношения: сиснА, А жА А ЯЮ Второе из иих является наиболее важным. Говорят, что множества А и В эквивалентны (записывается как А = В), если 4шВ и ВаА. Зто означает, что все элементы А являются элементами В, а все элементы  — элементами А. э" Используя определение эквивалентности множеств, до. кажем теперь идентичность некоторых множеств, разобрав серию из пяти примеров.

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

(Аналогично проведению эксперимента на ЭВМ с подобными структурами данных при их использовании в программировании,) Можно таня«е заметить, что доказательства теорем формируют основу всех решающихся автоматически задач, но это будет обсуждаться позднее.

Рассмотрим несколько примеров. В примере 4А непосредственно доказывается справедливость следующих двух соотношений: а) А П(В 0 С) ж(А П В) 0(А П С); б) (А П В)0(А П С)шА П(ВУ С)'. Каждое из зтих доказательств состоит из последовательности утверждений вида «если Р, то Чз (если справедливо Р, то справедливо и Ч). Для удобства запишем зто утверждение как «Р:. 9» и будем читать «из Р следует чэ. Следовательно, если имеется последовательность Р«, Рь..., Р„такая, что Р««' Рп Р~ «Р«, " ., Р -1 1" Р (из Р« следует Рп из Р1 следует Р«, ..., из Р„1 следует Р„), то мы имеем прямое доказательство Р« " Р„. Пример 4Л. Относительно множеств А, В и С докажем, что А П (В 0 С) (А П В) 0 (А П С).