С.Н. Селезнева - Основы дискретной математики, страница 2

Если такихэлементов нет (если A ∩ C = ∅), то свойство выполняется.Ответ: свойство (A \ B) \ C = A \ (B \ C) (ассоциативности разности)в общем случае не верно. Но оно будет выполняться для множеств A, B,C, если множества A и C не имеют общих элементов (если A ∩ C = ∅).1.2УпражненияЗадача 1.1.

Обосновать следующие свойства операций ∪, ∩:1) идемпотентность:2) коммутативность:3) ассоциативность:4) дистрибутивность:A ∪ A = A ∩ A = A;A ∪ B = B ∪ A;A ∩ B = B ∩ A;(A ∪ B) ∪ C = A ∪ (B ∪ C);(A ∩ B) ∩ C = A ∩ (B ∩ C);(A ∪ B) ∩ C = (A ∩ B) ∪ (B ∩ C);(A ∩ B) ∪ C = (A ∪ B) ∩ (B ∪ C).Задача 1.2. Обосновать следующие свойства операции :1)2)3)4)A = A;A ∪ B = A ∩ B;A ∩ B = A ∪ B;A ∪ A = U , A ∩ A = ∅.8Задача 1.3. Обосновать следующие свойства операции \:1)2)3)4)A \ A = ∅;A \ B = A \ (A ∩ B);A ∪ (B \ A) = A ∪ B;A \ (A \ B) = A ∩ B;5)6)7)8)(A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B);U \ A = A;A \ B = A ∩ B;(A \ B) \ C = A \ (B ∪ C).Задача 1.4. Выразить принадлежность произвольного элемента множеству D через его принадлежность или непринадлежность множествамA, B, C:1)2)3)4)DDDD= A ∩ B ∪ C;= A ∪ B ∩ C;= A \ B ∪ C;= A \ B ∩ C;5)6)7)8)DDDD= A \ B ∩ C;= A \ B ∪ C;= (A ∪ B) \ C;= (A ∩ B) ∪ C.Задача 1.5.

Объяснить, почему следующие свойства верны для произвольных множеств A, B, C:1)2)3)4)5)6)7)8)A ⊆ A ∪ B и B ⊆ A ∪ B;A ∩ B ⊆ A и A ∩ B ⊆ B;A \ B ⊆ A и (A \ B) ∩ B = ∅;если A ⊆ B, то A ∪ B = B и A ∩ B = A;если A ⊆ B, то A \ B = ∅;если A ⊂ B, то B \ A 6= ∅ и A \ B = ∅;если A ⊆ B и B ⊆ C, то A ⊆ C;A ∩ (B \ C) = (A ∩ B) \ (A ∩ C).Задача 1.6. Объяснить, почему следующие свойства не верны для произвольных множеств A, B, C.

Найти правильное заключение свойства(в 1)-5)) или указать, при каких условиях на множества A, B, C свойствовыполняется (в 6)-8)):1) если A ∪ B = A, то B = ∅;2) если A ∩ B = A, то B = A;3) если A \ B = A, то B = ∅;4) если A\B = C, то A\C = B;5) если A\B = C, то A = B∪C;6) A∪(B\C) = (A∪B)\(A∪C);7) A\(B∪C) = (A\B)∪(A\C);8) A\(B∩C) = (A\B)∩(A\C).Задача 1.7.

Пусть U – множество студентов некоторого вуза. Определим его подмножества: A – множество студентов, которые учатся наотлично“, B — множество студентов, изучающих английский язык, C –”9множество студентов, имеющих спортивный разряд, и D – множествостудентов, состоящих в студенческом профкоме. Выразить формуламинад множествами A, B, C, D следующие множества студентов:1) множество отличников, у которых есть спортивный разряд;2) множество студентов, не являющихся отличниками и не состоящих в профкоме;3) множество студентов, не состоящих в профкоме, но изучающиханглийский язык;4) множество отличников-спортсменов, состоящих в профкоме;5) множество студентов, которые состоят в профкоме, и или являются отличниками, или изучают английский язык;6) множество изучающих английский язык студентов, не являющихся ни отличниками, ни спортсменами;7) множество студентов-спортсменов, которые или не учатся на от”лично“, или не состоят в профкоме;8) множество изучающих английский язык отличников, состоящихв профкоме, но не спортсменов.Задача 1.8.

Обосновать следующие свойства операции ×:1)2)3)4)(A ∪ B) × C = (A × C) ∪ (B × C);(A ∩ B) × C = (A × C) ∩ (B × C);(A \ B) × C = (A × C) \ (B × C);A × (B \ C) = (A × B) \ (A × C).Задача 1.9. 1. Привести пример множеств A и B, для которых A × B 6=B × A.2. При каких условиях на множества A и B верно, что (A × B) ∩(B × A) 6= ∅?3. Доказать, что если множества A и B непусты, то A × B = B × Aтогда и только тогда, когда A = B.4.

Пусть N обозначает множество натуральных чисел, R – множестводействительных чисел, а [a; b] = {x ∈ R | a ≤ x ≤ b} – отрезок действительных чисел от a до b (a, b ∈ R, a ≤ b). Содержательно пояснить,какое множество определено как A × B, если1) A = B = N;2) A = B = R;3) A = {0}, B = R;4) A = R, B = [0; 1].10Задача 1.10. 1. Построить множество A × B, если1) A = ∅, B = {1};2) A = B = {1};3) A = B = {0, 1};4) A = {1, 2, 3}, B = {a, b}.2. Построить множество P (A), если1) A = ∅;2) A = {1};3) A = {0, 1};4) A = {1, 2, a}.Задача 1.11. Выяснить, является ли система множеств A1 , . .

. , Am разбиением множества A, если1) A1 = {0}, A2 = {1, 3}, A3 = {2}, A = {0, 1, 2, 3};2) A1 = {0, 1}, A2 = {1, 2}, A3 = {2, 3}, A = {0, 1, 2, 3};3) A1 = {0, 2}, A2 = {1, 3}, A = {0, 1, 2, 3, 4};4) A1 = {0, 1}, A2 = {2, 3}, A3 = {4, 5}, A = {0, 1, 2, 3, 4}.Объяснить, почему.1.3Конечные множества. Мощность множестваОпределение 1.12. Множество A называют конечным, если оно состоит из конечного числа элементов. Мощностью конечного множестваназывают количество элементов в нем.Обозначение:|A| – мощность множества A.Определение 1.13. Конечные множества A и B называют равномощными, если их мощности равны, то есть если они состоят из одинаковогочисла элементов.Обозначение:|A| = |B| – множества A и B – равномощные.Определение 1.14.

Если по какому-то правилу каждому элементу xмножества A поставлен в соответствие ровно один элемент y из множества B, то задано отображение множества A в множество B.Обозначение:f : A → B – f – отображение множества A в множество B.11Если при отображении f : A → B элементу x ∈ A поставлен в соответствие элемент y ∈ B, то пишут y = f (x) и называют элемент yобразом элемента x при отображении f . Элемент x при этом называютпрообразом (одним из возможных) элемента y.Множество образов всех элементов называется образом множества Aпри отображении f и обозначается f (A).

Множество A называется (полным) прообразом множества C = f (A) ⊆ B при отображении f .Обозначение:f (A) = {y ∈ B | ∃3 x ∈ A : f (x) = y} – образ множества A при отображении f : A → B.Замечание 1.2. Отображение f : A → B можно определить как подмножество декартова произведения A × B с определенным свойством.Если подмножество f ⊆ A × B таково, что для каждого элемента xмножества A ровно одна пара (x, y) принадлежит множеству f , то, значит, каждому элементу x ∈ A поставлен в соответствие ровно один элемент y ∈ B (второй элемент единственной пары (x, y) из f ) и заданоотображение f .Замечание 1.3.

Понятия отображение“ и функция“ – синонимы.””Они несколько отличаются терминологией и областями применения. Если говорят о функции f : A → B, то множество A называют областьюопределения, а множество f (A) ⊆ B – областью (или множеством) значений функции f . Каждый элемент x ∈ A называется значением аргумента (или аргументом), а элемент y = f (x) ∈ B – значением функциипри значении аргумента x.Определение 1.15.

Если при отображении f : A → B для каждогоэлемента y множества B найдется хотя бы один такой элемент x из множества A, что y = f (x), то отображение f называется отображениеммножества A на множество B.Определение 1.16. Отображение f множества A на множество B называется взаимно-однозначным, если для каждого элемента y множества Bнайдется ровно один такой элемент x из множества A, что y = f (x).3знак ∃ – квантор существования – читается существует“, хотя бы для одного“.””12Взаимно-однозначное отображение множества A на множество B называется также взаимно-однозначным соответствием между множествами A и B.Определение 1.17.

Если f : A → B – взаимно-однозначное отображение, то для каждого элемента y множества B есть ровно один такой элемент x из множества A, что y = f (x). Значит, определено отображениемножества B на множество A, которое называется обратным к отображению f и обозначается f −1 .Обозначение:f −1 : B → A – f −1 – обратное отображение к взаимно-однозначномуотображению f : A → B.Теорема 1.1. Конечные множества A и B равномощны, если и толькоесли существует взаимно-однозначное отображение множества A намножество B.Замечание 1.4.

Для бесконечных множеств утверждение теоремы 1.1рассматривается как определение их равномощности. То есть множестваA и B (в том числе и бесконечные) называются равномощными, еслисуществует взаимно-однозначное отображение множества A на множество B.Теорема 1.2. 1. Если |A| = k и |B| = m, то |A × B| = k · m.2. Если |A| = k и n ≥ 2, то |An | = k n .3. Если |A| = k, то |P (A)| = 2k .Пример 1.3. Пусть A = {0, 1}.

Словом длины n в алфавите A назовемпроизвольный элемент множества An , n ≥ 2. Найти количество словдлины n, начинающихся и оканчивающихся на 1.Решение. Пусть α = (1, a2 , . . . , an−1 , 1) ∈ An – слово длины n. Каждыйиз элементов a2 , . . . , an−1 может принимать независимо от других двазначения: 0 и 1. Поэтому количество таких слов равно 2n−2 .Ответ: 2n−2 слов.Пример 1.4. Найти число решений уравненияX ∪ Y = C,где X и Y – неизвестные множества, а C – заданное множество, |C| = k.13Решение.

Заметим, что X, Y ⊆ C. Рассмотрим произвольный элемент x ∈ C. Он может принадлежать или не принадлежать каждомуиз множеств X и Y . Обозначим как 1 и 0 соответственно случаи егопринадлежности и непринадлежности этим множествам. Запишем всевозможные варианты в таблицу и построим соответствующие значениядля его принадлежности множеству X ∪ Y :X0011Y X ∪Y00110111Из таблицы видно, что если x ∈/ X, x ∈/ Y , то x ∈/ X ∪Y . В этом случаеX ∪Y 6= C. Следовательно, в условиях задачи для каждого элемента x ∈C есть 3 возможности принадлежать или не принадлежать множествамX и Y: x∈/ X, x ∈ Y , или x ∈ X, x ∈/ Y , или x ∈ X, Y .Обозначим элементы множества C как c1 , .