ВОПРОСЫ и ответы К ЭКЗАМЕНУ. Ответы к экзамену комбинаторный признак умножения. Количество битовых строк длины
 Скачать 2.8 Mb.
|
|
18. Булеан множеств. Количество элементов булеана конечного множества (с доказательством). Булеаном множества X называется множество всех подмножеств множества X, включая его само и пустое множество. Булеан конечного множества конечен, причем количество элементов булеана 2A равно 2n, где n – количество элементов множества A. Теорема о мощности булеана.Пусть A - конечное множество мощности n , тогда мощность его булеана равна 2n : |Б(A)| = 2n . Доказательство. Установим соответствие между множествами Б(A)и En по правилу: подмножеству  поставим в соответствие набор длины n из нулей и единиц, в котором на местах с номерами i1, . . . , is стоят единицы, а на остальных местах нули. Это соответствие является взаимооднозначным, поэтому |Б(A)| = |En| = 2n . Теорема доказана.В качестве примера приведенного в доказательстве теоремы соответствия рассмотрим случай n = 3 . Пусть A = {α, β, γ}, тогда Б(A) = {ø, {α}, {β}, {γ}, {α, β}, {α, γ}, {β, γ}, {α, β, γ}}; E3 = (0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 1) . Соответствие между E3 и Б(A) может быть установлено 8! различными способами (оно равно числу перестановок из элементов множества E3 ). В данном случае элементы множества E3 записаны так, что эле- менту, стоящему на k -ом месте,  в Б(A) соответствует k -ый элемент множества  соответствует (0, 0, 1) , {α, β} — (1, 1, 0) и т. д.Отметим следующее свойство булеана: Б(A∪B) = {A1 ∪B1|A1 ∈ Б(A), B1 ∈ Б(B)}. Действительно, пусть произвольное множество C∈ Б(A∪B) , т. е. C⊆A∪B . Обозначим через A1 = C ∩ A , B1 = C ∩ B . Тогда A1 ⊆A , B1 ⊆B и C = A1 ∪B1 , где A1 ∈ Б(A) , B1 ∈ Б(B) . Докажем обратное включение. Если A1 ∈ Б(A) , B1 ∈ Б(B) , тоA1 ⊆A ,B1 ⊆B . ТогдаA1 ∪B1 ⊆A∪B⇒A1 ∪B1 ∈ Б(A∪B) . 19. Декартово произведение двух и нескольких множеств. Кортежи. Арифметическое n-мерное точечное пространство. Понятие кортежа, как и понятие множества, является одним из основных математических понятий, поэтому для него также не существует определения через другие понятия. Интуитивно кортеж можно определить какупорядоченныйнабор компонентов. Кортежи одинаковы (равны), если они состоят из одних и тех же компонентов, причем порядок этих компонентов также одинаков. Компоненты кортежей обычно перечисляются в круглых скобках. Например,a= (3, 8, 2) – кортеж. Числа 3, 8, 2 – его компоненты. Другой пример кортежа –c= (8, 2, 3). Кортежиaиc– разные. В кортеже могут быть одинаковые элементы. Например,x= (8, 3, 2, 3) иy= (3, 8, 2, 3) – кортежи, причем разные. Количество компонентов в кортеже называется его длиной. Например, длина кортежейaиcравна трем, а кортежейxиy– четырем. Кортежи из двух компонентов называют парами, из трех – тройками, и т.д. Простейший пример кортежа – вектор, задающий координаты точки на плоскости или в пространстве. Очевидно, что, например, точки на плоскости с координатами (5, 7) и (7, 5) – разные. Как и для множеств, компоненты кортежей могут быть любыми (не только числами). Например, перечень студентов учебной группы, упорядоченный по их среднему баллу за время учебы, можно считать кортежем. Декартовым (или прямым) произведением множествAиBназывается множество, состоящее из всех тех и только тех пар (т.е. кортежей длины 2), первый компонент которых принадлежит множествуA, а второй – множествуB. Декартово произведение множествAиBобозначается какA×B. Аналогично определяется произведение трех, четырех и т.д. множеств. Декартово произведение множествА1,А2, ...,Аr– это множество всех тех и только тех кортежей длиныr, первый компонент которых принадлежит множествуА1, второй – множествуА2, ...,r-й – множествуАr. Такое декартово произведение обозначается как  .Декартово произведение множества на само это множество называется декартовым квадратом. Аналогично можно говорить о декартовой третьей степени и т.д. n-мерным арифметическим пространством называется совокупность всевозможных упорядоченных наборов из n вещественных чисел, над которыми введены две операции: 1) сложение наборов; 2) умножение наборов на вещественные числа. Операция сложения: Пусть даны некоторые наборы x = (x1, x2, …, xn ) и y = (y1, y2, …, yn), xiyi – вещественные числа: x + y = z = (x1 + y1, x2 + y2,…, xn + yn) Свойства сложения: x + y = y + x – коммутативность (x + y) + z = x + (y + z) = y + (x + z) – ассоциативность $! (существует единственный) 0 = (0, 0, …, 0) , x + 0 = x "x $!y, что x + y = 0, т. е. y – набор, противоположный x. Операция умножения на число x = (x1, x2 … xn), λ Î R λhx = xhλ = w = (λx1, λx2, … λxn) Свойства умножения на число: λhx = xhλ – коммутативность μh(λx) = (μλ)hx 1hx = x 0hx = (0, 0, …, 0). Совместные свойства операций: λx + λy = λ(xy) дистрибутивность μx + λx = (μ + λ )x x + y = 0 Û y = (-1)hx – набор противоположный набору х. 20. Диаграммы Эйлера - Венна основных операций над множествами. Диаграмма Эйлера-Венна — геометрическая схема, которая используется для моделирования множеств и для схематичного изображения и отношений между ними.Диаграмма позволяет наглядно отразить различные утверждения о множествах. При использовании этого метода универсальное множество изображается в виде прямоугольника, подмножества изображают кругами. Диаграммы нашли свое применение в математике, логике, менеджменте и других прикладных направлениях. Построение диаграммы Эйлера-Венна — это изображение большого прямоугольника, который представляет универсальное множество U. Внутри прямоугольника изображаются замкнутые фигуры, обозначающие множества. Если множеств не более 3, то изображаются круги, и эллипсы, если множеств 4. Фигуры пересекаются в наиболее общем случае, требуемом задачей, что обозначается соответствующим образом. Предположим, что на диаграмме изображен круг, представляющий множество А. Область в середине круга множества А отражает истинность выражения А, в то время как область вне круга обозначает ложь. Логическая операция будет отображаться на диаграмме при помощи штриховки тех областей, в которых ее значения истинны. В соответствии с алгеброй логики, конъюнкция множеств А и B будет истинна только тогда, когда истинны оба множества. Тогда на диаграмме будет отмечена область пересечения множеств. С помощью диаграмм Эйлера-Венна можно доказать все законы алгебры, представляя их графически. Это возможно через выполнение следующего алгоритма: В первую очередь необходимо начертить диаграмму, заштриховав все множества, находящиеся в левой части равенства. Следующим шагом будет начертание другой диаграммы и штриховка всех множеств, которые находятся в правой части равенства. В случае, когда на диаграммах заштрихована одна и та же область, торжество истинно. 21. Теорема об основных свойствах операций над множествами. Теорема 1:Для любых множестви следующие утверждения являются равносильными: 1)  ;2)  ;3)  .Доказательство:Докажем сначала, что  .Если , то - очевидно. Докажем второе следствие. По определению операции пересечения множеств имеем: . Нужно получить обратное включение. Если удовлетворяется равенство , тогда , откуда . Если , то . Значит, по свойству антисимметричности отношения включения: . Покажем, что . По определению , но по условию , значит .Аналогично можно показать, что выполняются и обратные утверждения. Теорема 2:(свойства операций над множествами):Для любых множествА, В, Симеют место следующие равенства: 1)  ; (идемпотентность);2)  ; (коммутативность);3)  ; (ассоциативность);4)  ; (дистрибутивность);5)  ; .Доказательство:Доказательства подобных утверждений можно проводить с помощью диаграмм Эйлера-Венна, или с помощью рассуждений. Докажем для примера одно из утверждений(5): .Для доказательства равенства нужно показать, что если произвольный элемент принадлежит левой части, то он принадлежит и правой части. Теорема 3:Для любых множестви имеют место следующие утверждения: 1)  ;2)  ;3)  ;4)  (законы де Моргана).Доказательство:Докажем некоторые утверждения. 1) Покажем, что если произвольный элементпринадлежит левой части, то он принадлежит и правой части равенства и наоборот. Пусть  , это возможно тогда и только тогда, когда . Из последнего по определению разности множеств имеем: и . Значит, по определению дополнения имеем: и . Последнее равносильно тому, что . Следовательно, по определению операции пересечения. Таким образом, выполнено равенство: . Оно означает, что дополнение к дополнению множества , есть само множество .3) Докажем один из законов де Моргана. Пусть  . Это возможно тогда и только тогда, когда . Используя свойства операций над множествами (теорема 2), преобразуем разность: . Последнее означает, что . Что и требовалось доказать.Замечание:В теории множеств очень распространённым являетсясоотношение двойственности.Оно заключается в следующем. Если в каждом из перечисленных свойств операций над множествами поменять между собой символыи , и , и , то в результате снова получится одно из этих свойств. Отсюда вытекает, что каждой теореме, которая может быть выведена из перечисленных свойств, соответствует другая, двойственная ей теория. Теорема 4:Пусть- конечное множество, содержащее элементов:  . Тогда множество всех подмножеств множества содержит элементов.Доказательство:Для доказательства можно использовать свойства биномиальных коэффициентов. Формула бинома Ньютона имеет следующий вид:  . Применим её для нашего случая: . Здесь - это число подмножеств, не содержащих элементов (т.е. пустое множество); - это число одноэлементных подмножеств; - число всех двухэлементных подмножеств и т. д., - это само множество . Значения биномиальных коэффициентов могут быть взяты из соответствующих строк треугольника Паскаля. Таким образом, будет посчитано количество всех подмножеств данного множества.Замечание:Для произвольного множествамножество всех его подмножеств часто обозначают . Заметим, что множество всех подмножеств любого множестваотносительно операций объединения, пересечения, дополнения обладает всеми свойствами, перечисленными выше. Этими же свойствами обладает и всякая конечная или бесконечная система множеств, если только для любого множества этой системы его дополнение принадлежит этой системе, и для любой пары множеств данной системы их пересечение и объединение также принадлежат этой системе. Простейшей такой системой может служить система из двух множеств  .В математике встречаются и другие объекты, кроме множеств, для которых определены операции «сложения», «умножения» и «дополнения», удовлетворяющие свойствам операций над множествами (коммутативность, ассоциативность и др.). Такие системы впервые изучал в 1847 г. английский математик Дж. Буль, поэтому такие системы называютбулевыми алгебрами. |