Prak_alg
.pdfФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
И.Н. Булгакова
ДИСКРЕТНАЯ МАТЕМАТИКА
ЭЛЕМЕНТЫ ТЕОРИИ, ЗАДАЧИ И УПРАЖНЕНИЯ
Часть 1
Учебное пособие для вузов
2-е издание, переработанное и дополненное
Издательско-полиграфический центр
Воронежского государственного университета
2008
Утверждено научно-методическим советом факультета ПММ ВГУ 19 ок- тября 2007 г., протокол № 2
Рецензент к.т.н., доцент кафедры ПО и АИС ф-та ПММ ВГУ И.Е. Воронина
Учебное пособие подготовлено на кафедре математических методов ис-
следования операций факультета ПММ Воронежского государственного университета.
Рекомендуется для студентов 1 курса д/о и в/о, обучающихся по специаль- ности «Прикладная математика и информатика», а также будет полезна всем изучающим дискретную математику.
Для специальностей: 010200 – Прикладная математика и информатика; 351400 – Прикладная информатика в юриспруденции; 351500 – Математи- ческое обеспечение и администрирование информационных систем; 080700 – Бизнес-информатика; 080800 – Прикладная информатика
2
1. ТЕОРИЯ МНОЖЕСТВ И ОТНОШЕНИЙ
1.1 Элементы теории множеств
Под множеством понимается совокупность некоторых объектов (элементов), объединенных некоторым признаком. Множества обычно обозначают большими буквами алфавита Α, Β , Χ ,Υ , Ζ , Ω . Элементы,
входящие в множество, обозначаются малыми буквами a,b, x, y, z,ω . За-
пись x Î Χ означает, что x является элементом множества Χ , а запись x Χ означает, что x не принадлежит множеству Χ . Два множества счи- таются равными, если они состоят из одних и тех же элементов.
Для описания множества пользуются двумя способами. Первый спо- соб состоит в простом перечислении его элементов. Так, запись Α = {0,1,5}
означает, что множество Α состоит из трех чисел 0,1 и 5. Второй способ со- стоит в определении множества с помощью некоторого свойства P, позво- ляющего определить, принадлежит ли данный элемент данному множеству или нет. В этом случае используется коллективизирующее обозначение
Α = {x : P(x)},
которое читается следующим образом: множество Α состоит из всех эле- ментов x , для которых P(x) истинно. Если свойство P относится к эле-
ментам некоторого множества Χ , то будем писать также Α = {x Χ : P(x)}. Например, множество {1,2,3,4,5} можно задать следую-
щим образом:
{1,2,3,4,5}= {x : x − целое число из интервала [1,5]}.
Множество, не содержащее элементов, называется пустым множест- вом и обозначается Æ .
Знаком обозначим отношение включения между множествами, т.е. Α Β , если каждый элемент множества Α есть элемент множества Β . Ес- ли Α Β , то говорят, что множество Α есть подмножество множества Β .
Равенство двух множеств Α и Β означает выполнение двух вклю- чений: Α Β и Β Α .
Если Α Β и Α ¹ Β , то говорят, что Α есть собственное подмно- жество Β и пишут Α Ì Β .
Множество всех подмножеств множества Α называется множест- вом-степенью и обозначается Ρ (Α).
Заметим, что: a) Χ Χ ; б) если Χ ÍΥ , Υ Í Ζ , то Χ Ζ ; в) ес- ли Χ ÍΥ , Υ Í Χ , то Χ =Υ .
Не надо смешивать отношения принадлежности и включения. Хотя 1 {}1 , {}1 {{}1 }, не верно, что 1 {{}1 }, так как единственным элементом
множества {{}1 } является {}1 .
Пустое множество есть подмножество любого множества.
3
Число элементов в множестве Χ обозначается Χ .
Рассмотрим методы получения новых множеств из уже существую-
щих.
Объединением множеств Α и Β называется множество Α È Β , все элементы которого являются элементами множества Α или Β :
Α È Β = {x : x Î Α или x Î Β}.
Пересечением множеств Α и Β называется множество Α Ç Β , эле- менты которого являются элементами и множества Α , и множества Β :
Α Ç Β = {x : x Î Α и x Î Β}.
Очевидно, что выполняются включения
Α Ç Β Í Α Í Α È Β и Α Ç Β Í Β Í Α È Β .
Разностью множеств Α и Β называется множество Α \ Β тех эле- ментов из Α , которые не принадлежат Β :
Α \ Β = {x : x Î Α и x Ï Β}.
Симметричной разностью множеств Α и Β называется множество
Α + Β = Α \ Β È Β \ Α .
Если все рассматриваемые в данный момент множества являются подмножествами некоторого множества U , то множество U называют универсальным для данного рассмотрения.
Дополнением множества Α называется множество
Α = U \ Α .
Для наглядного представления отношений между подмножествами какого- либо универсального множества используются диаграммы Эйлера – Венна.
Операции над множествами имеют следующие приоритеты в поряд- ке убывания: операция взятия дополнения, операция пересечения, опера- ция объединения.
4
Отметим следующие основные законы для операций над множествами:
1.Α È Β = Β È Α ( коммутативность объединения);
2.Α Ç Β = Β Ç Α (коммутативность пересечения);
3.Α È (Β È Μ )= (Α È Β )È Μ (ассоциативность объединения);
4.Α Ç (Β Ç Μ )= (Α Ç Β )Ç Μ (ассоциативность пересечения);
5.Α È (Β Ç Μ )= (Α È Β )Ç (Α È Μ )(1-й закон дистрибутивности);
6.Α Ç (Β È Μ )= (Α Ç Β )È (Α Ç Μ )(2-й закон дистрибутивности);
7.Α È Æ = Α ;
8.Α ÈU = U ;
9.Α Ç Æ = Æ ;
10.Α ÇU = Α ;
11.Α È Β = Α Ç Β ( закон де Моргана);
12.Α Ç Β = Α È Β ( закон де Моргана);
13.Α È (Α Ç Β )= Α (закон поглощения);
14.Α Ç (Α È Β )= Α (закон поглощения).
Рассмотрим методику решения задач по данной теме.
Пример 1. Равны ли следующие множества:
1){2,4,5} и {2,4,5,2};
2){1,2} и 1,2 ;
3){1,2,3} и {{}1 ,{2},{3}};
4){{1,2},3} и {{}1 ,{2,3}}.
Решение. Для доказательства равенства произвольных множеств нужно проверить, что первое множество включено во второе, а второе, в свою очередь, включено в первое, т.е. любой элемент первого множества является элементом второго множества, а любой элемент второго множе- ства является элементом первого множества.
Проверка дает положительный результат для множеств из пункта 1). Это можно наглядно показать на следующей схеме, где стрелочка, идущая от элемента, показывает, какой элемент в другом множестве ему соответствует.
{2,4, 5} |
{2, 4, |
5,2} |
{2, 4, 5,2} |
{2, 4, |
5} |
Множества из пункта 2) неравны, так как, например, элемент 1 из первого множества не имеет себе равного во втором множестве. Второе множество состоит из единственного элемента – множества {1,2}.
5
Множества, указанные в пункте 3), неравны, так как элементами первого множества являются числа 1, 2, 3 , а элементами второго множества являются множества, состоящие из одного элемента {}1 ,{2},{3}.
Пункт 4) сделайте самостоятельно.
Пример 2. Следующие множества заданы перечислением своих эле- ментов, задайте эти множества с помощью характерного для их элементов свойства.
1) Α = {2,4,6,8,...,32};
ì |
Киев,Минск, Кишинев,Таллинн, Вильнюс, Рига,Москва,ü |
|
ï |
Ереван,Тбилиси, Баку,Ташкент, Ашхабад, Душанбе, |
ï |
2) Κ = í |
ý |
|
ï |
Алма-Ата,Фрунзе |
ï |
î |
þ |
Решение. Множество Α представляет собой множество четных на- туральных чисел от 1 до 32, поэтому это множество можно записать в виде
Α = {x Ν : x = 2n, n = 1,...,16}.
Множество Κ представляет собой множество столиц республик бывшего СССР, т.е. это множество можно записать в виде
Κ = {x : x − столица республики СССР}.
Пример 3. Приведите примеры таких множеств Α,Β ,Κ , для которых
1) Α Β, |
Β Κ, |
Α Κ ; |
2) Α Β , |
Β Κ , |
Α Κ ; |
3) Α Β, |
Β Κ, |
Α Κ ; |
4) Α Β , |
Β Κ , |
Α Κ . |
Решение. В качестве примера множеств, удовлетворяющих условию из пункта 1), можно рассмотреть следующие множества
Α = {1,2} , Β = {{1,2} ,1} , Κ = {3,{{1,2} ,1}} .
Пункту 3) удовлетворяют множества
Α = {2,3}, Β = {{}1 ,{2,3}}, Κ = {2,3,4}.
Пункты 2) и 4) рассмотрите самостоятельно.
Пример 4. Докажите следующие тождества:
1)Α \ Β = Α Ç Β ; 2)Α È (Β \ Κ ) = (Α È Β )Ç (Α È Κ );
3)(Α È Β )Ç (Β È Α)= Α ; 4)Β Ç (Α \ Β ) = Æ ; 5)Α Ç (Β + Κ ) = (Α Ç Β )+ (Α Ç Κ ).
Решение. Для доказательства равенства 1) докажем два включения:
Α\ Β Í Α Ç Β ,
ΑÇ Β Í Α \ Β .
Доказательство первого включения проведем по схеме
6
ìx Î Α |
ìx Î Α |
|
|
|
|
|
|
|
|||
x Î Α \ Β Þ í |
Þ í |
|
Þ x Î Α Ç Β , |
||
|
|||||
îx Ï Β |
îx Î Β |
|
|
|
а доказательство второго включения по схеме
|
|
ìx Î Α |
ìx Î Α |
|
|
|
|
|
|||
x Î Α Ç Β Þ í |
|
Þ í |
Þ x Î Α \ Β . |
||
|
|||||
|
|
îx Î Β |
îx Ï Β |
|
Заметим, что в данном примере мы могли рассмотреть не две схемы, а одну, но вместо знака следствия использовать знак равносильности .
Тождество 2 можно также доказать с помощью двух включений, но можно и не использовать данную схему, а опираться на уже доказанное тождество 1) и на основные законы 1–14. Мы приведем данный способ до- казательства, причем вверху над равенствами будем писать либо 1) – это означает, что используется тождество 1), либо номер используемого ос- новного закона. Итак,
Α È (Β \ Κ ) =1) Α È (Β Ç Κ )=5) (Α È Β )Ç (Α È Κ ).
Аналогично можно доказать равенства 3), 4), 5). Для равенства 4) приведем еще один способ доказательства – доказательство от против- ного. Предположим противное, что множество Β Ç (Α / Β ) не пусто, т. е.
существует хотя бы один элемент
ìx Î Β |
ìx Î Β |
ìx Î Β |
||
ï |
ï |
|
|
|
x Î Β Ç (Α \ Β )Þ í |
Þ íìx Î Α Þ íx Î Α . |
|||
îx Î Α \ Β |
ïí |
ï |
|
|
|
|
|||
|
îîx Ï Β |
îx Î Β |
Никакой элемент x не может одновременно принадлежать и самому множеству, и его дополнению, поэтому мы пришли к противоречию.
Пример 5. Пусть Α, Β, Κ – такие множества, что Β Α Κ . Най- дите множество Χ , удовлетворяющее системе уравнений
ìΑ Ç Χ = Β |
. |
|
|
|
í |
|
|
|
|
îΑ È Χ = Κ |
|
|
|
|
Решение. Из первого уравнения следует, что Β Χ , поэтому Χ |
||||
можно представить в виде Χ = Β È Χ ′, где Χ ′ Ç Β = Æ . Из равенств |
||||
′ |
Χ |
′ |
Ç Β = Æ |
|
Α Ç Χ = Β , Χ = Β È Χ |
, |
|
следует, что Α Ç Χ ′ = Æ .
Итак, нам осталось найти множество Χ ′ . Заменим Χ во втором урав- нении на Χ = Β È Χ ′. Получим Α È (Β È Χ ′) = Κ . По ассоциативному за- кону (Α È Β )È Χ ′ = Κ . Из включения Β Α следует, что Α Β = Α , по- этому получаем равносильное уравнение Α È Χ ′ = Κ . Два факта Α Ç Χ ′ = Æ и Α Κ позволяют заключить, что решением последнего урав- нения является множество Χ ′ = Κ \ Α . Окончательно
7
Χ = Β È (K \ Α).
Пример 6. Докажите, что условие Α Β равносильно каждому из следующих условий:
1) Α Ç Β = Α ; 2) Α È Β = Β .
Решение. Докажем, что Α Β равносильно условию 1).
Итак, пусть Α Β , докажем равенство Α Ç Β = Α . Равенство будем доказывать в два включения. Пусть
x Î Α Ç Β Þ x Î Α .
Обратно, пусть
x Î Α ÞΑÍΒ x Î Α, x Î Β Þ x Î Α Ç Β .
Теперь предположим, что выполнено условие 1), докажем, что Α Β . Рассмотрим
x Î Α ÞΑÇΒ =Α x Î Α Ç Β Þ x Î Β .
Равносильность условия Α Β условию 1) мы доказали, равносиль- ность условию 2) докажите самостоятельно.
Пример 7. Докажите для произвольных множеств Α, Β, Κ :
1) |
если Α Β и Α Ç Κ = Æ , то Α Κ Β Κ ; |
2) |
если Β Ç Κ = Æ и Α Ç Κ ¹ Æ , то Α \ Β ¹ Æ . |
Решение. |
|
1) |
Нам нужно доказать, что существует хотя бы один элемент x′ та- |
кой, что x′Î Α È Κ , x′Ï Β È Κ . Нам известно, что Α Β , поэтому суще-
ствует некоторый элемент x* Î Α и x* Ï Β . В силу условия Α Ç Κ = Æ , данный элемент x* Ï Κ . Таким образом, x* Î Α È Κ , x* Ï Β È Κ .
2) Нам нужно доказать, что существует хотя бы один элемент в мно-
жестве Α \ Β . Известно, |
что Α Ç Κ ¹ Æ , поэтому существует |
элемент |
x* Î Α, x* Î Κ , причем, |
в силу условия Β Ç Κ = Æ , данный |
элемент |
x* Ï Β . Итак, мы построили элемент x* Î Α и x* Ï Β .
Пример 8. Докажите, что для произвольных множеств Α, Β спра- ведливо равенство Ρ (Α Ç Β ) = Ρ (Α)Ç Ρ (Β ).
Решение. Доказательство проведем в виде двух включений, объеди- нив их одной записью. Пусть
Χ Î Ρ (Α Ç Β ) Û Χ Í Α Ç Β Û Χ Í Α, Χ Í Β Û Û Χ Î Ρ (Α), Χ Î Ρ (Β ) Û Χ Î Ρ (Α)Ç Ρ (Β ).
8
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Каждое из следующих множеств задайте в виде некоторого интервала числовой прямой:
1){x Î R : $y Î R x2 + y2 = 1};
2) |
ìx Î R : $y Î R x = |
y + 1 |
ü; |
|
|||
|
í |
y2 + 1 |
ý |
|
î |
þ |
3){a Î R : $x Î R 3x2 + 2ax + a < 0} .
2.Вставьте между множествами символ или так, чтобы получилось истинное утверждение.
1) |
{}1 |
{1,{1,2}}; |
2) |
{1,2} |
{1,2,{}1 ,{2}}; |
3){1,2} |
{1,2,{1,2}}; |
|
4) |
{1,2,{}1 ,{ }}; |
|
5) |
{ }; |
|
6) |
{{ }}. |
3.Перечислите элементы каждого из следующих множеств:
1){x : x Í {}1 };
2){x : x Í {1,2,3}};
3){x : x Í Æ}.
4.Докажите следующие тождества:
1)(Α \ Β )È (Α Ç Β ) = Α;
2)Α Ç Β = Α Ç (Α È Β );
3)(Α È Β )\ (Α Ç Β ) = Α + Β;
4)(Α \ Β )È (Α \ Β )= (Α È Β )\ (Α Ç Β );
5)(Α \ Β )È (Α \ Β )= (Β È Α)Ç (Α È Β );
6)Α \ (Α \ Β ) = Α Ç Β;
7)Β È (Α \ Β ) = Α È Β;
8)(Α + Β )+ Κ = Α + (Β + Κ );
9)Α + Α = Æ .
5.Считая Λ универсальным множеством для данного рассмотрения, най-
дите множество Х, удовлетворяющее следующим условиям: 1)Α \ Χ = Α, Α È Χ = Λ;
2)Α Ç Χ = Æ, Α È Χ = Λ; 3)Α \ (Α \ Χ ) = Æ; 4)Α \ Χ = Æ, Α È Χ = Α;
5)Α \ (Α \ Χ ) = Æ, Α Ç Χ = Æ .
9
6. Найдите решение системы уравнений |
|
ìΑ \ Χ = Β |
, |
í |
|
îΧ \ Α = Κ |
|
если известно, что Β Í Α, Α Ç Κ = Æ . |
|
7.Каждое из следующих утверждений либо докажите, либо покажите при помощи диаграмм Эйлера – Венна, что оно не всегда верно:
1)(Α È Β )Ç Κ = Α È (Β Ç Κ );
2)(Α \ Β )È Β = Α;
3)(Α È Β )\ Β = Α;
4)(Α Ç Β )\ Α = Æ;
5)(Α \ Β )È Κ = (Α È Κ )\ (Β È Κ );
6)(Α Ç Β )È (Β Ç Α)Í Β;
7)Β = (Α Ç Β )È (Β Ç Α)Þ Α = Æ .
8.Верно ли, что:
1)Α È Β = Α È Κ Þ Β = Κ ;
2)Α Ç Β = Α Ç Κ Þ Β = Κ ;
3)Α È Β = Α È Κ и Α Ç Β = Α Ç Κ Þ Β = Κ .
9.Докажите:
1.(Α È Β )Ç Κ = Α È (Β Ç Κ ) Û Α Í Κ ;
2.Α = Β Û Α + Β = Æ;
3.Α È Β = Æ Û Α = Β = Æ;
4.(Α È Β )\ Β = Α Û Α Ç Β = Æ;
5.Α \ Β = Α Û Β \ Α = Β;
6.Α È Β = Α \ Β Û Β = Æ;
7.Α \ Β = Α Ç Β Û Α = Æ;
8.Α È Β Í Κ Û Α Í Κ и Β Í Κ ;
9.Α Í Β È Κ Û Α \ Β Í Κ ;
10.Κ Í Α Ç Β Û Κ Í Α и Κ Í Β ;
11.Α Ç Β = Α È Β Û Α = Β ;
12.Α Í Β Í Κ Û Α È Β = Β Ç Κ ;
13.Α Í Β Þ Α \ Κ Í Β \ Κ ;
14.Β Í Α и Κ = Α \ Β Þ Α = Β È Κ ;
15.Α È Β = Α Þ Α Ç Β = Β .
10.Объединением семейства множеств Αi (i Ι ) называется множество
UΑi = {x : $j ÎΙ x Î Α j }.
iΙ
10