русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Алгебра множеств

В этом параграфе мы опишем некоторые способы получения новых множеств из уже имеющихся. Эти способы обычно называются операциями над множествами. Основные свойства этих операций и связи между ними принято называть алгеброй множеств.

Определение. Объединением (суммой) двух множеств A и B называется множество (его принято обозначать ) состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из этих множеств - либо A, либо B.

На языке кванторов мы будем записывать эту операцию следующим образом:


Пример.  Рассмотрим множества A = {1, 2, 3, 4},  B = {1,3,5}, C = {5,6}. Тогда, согласно введенному определению получаем:


Аналогично определяется объединение (сумма)  множеств A1,A2, ..., An. Объединением этих множеств называется множество, обозначаемое , состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из этих множеств.

Достаточно часто для наглядного изображения этих операций над множествами используют, так называемые, круги Эйлера (диаграммы Венна). Множества при таком подходе изображают кругами, а результат операции закрашивают или заштриховывают. Вот так выглядит результат операции объединения двух множеств.
sum
Определение. Пересечением (произведением) двух множеств A и B называется множество (его принято обозначать ) состоящее из всех тех и только тех элементов, которые принадлежат каждому из множеств A и B.

На языке кванторов мы будем записывать эту операцию следующим образом:


Пример.  В рамках введенных в предыдущем примере определений множеств A, B, C мы получаем:


Также как мы делали раньше, можно определить пересечение (произведение) конечного числа множеств.

На кругах Эйлера пересечение множеств выглядит следующим образом:
prod
Бывает удобно ввести понятие "универсального" множества U, которое по предположению содержит все используемые нами множества.
Введенные операции над множествами обладают свойствами коммутативности:


и свойством ассоциативности:


       

справедливость этих свойств следует из самих определений операций пересечения и объединения множеств, поэтому, обычно, скобки в таких групповых операциях опускают.
Имеет место также закон взаимной дистрибутивности:


Перейдем к новой операции над множествами. Эта операция определяется только для двух множеств.

Определение. Разностью двух множеств A и B называется множество (его обычно обозначают A\B или A-B), состоящее из тех и только тех элементов, которые принадлежат множеству A и не принадлежат множеству B.


На кругах Эйлера
dif
Пример. В рамках введенных в предыдущем примере определений множеств A, B, C справедливы следующие результаты


A\B = {2,4};    B\C = {1,3};    A\C = A.

Почти очевидно следующее свойство, которое также можно принять за определение разности двух множеств:


Определение. Симметрической разностью множеств A и B называется множество обозначаемое через A triaB и определяемое следующим образом:


На кругах Эйлера эта операция выглядит вот как
sdif
Пример.


a)    ;

b)    .

Кроме того, справедливо следующее свойство:


.

Доказательство этого свойства, как и других утверждений о равенстве каких-либо множеств, состоит в том, чтобы предположив принадлежность некоторого элемента x множеству из левой части равенства доказать, что этот же самый элемент принадлежит множеству, стоящему в правой части равенства и наоборот.

Перейдем к доказательству. Пусть , что по определению симметрической разности означает, что . Здесь возможны два варианта: либо , либо . В первом случае мы получаем: откуда очевидно следует, что . Ситуация, когда  рассматривается аналогично.   

Итак, мы доказали, что если некоторый элемент x принадлежит множеству из левой части равенства, то из этого следует, что он принадлежит множеству, стоящему в правой части равенства. Теперь нам необходимо доказать обратное включение.
Пусть . Здесь возможны 2 ситуации: либо . Давайте, рассмотрим первый случай: пусть . Второй случай доказывается аналогично.     

Итак, мы полностью доказали заявленное свойство. При доказательстве подобных утверждений огромную роль играет то свойство, что если некоторый элемент x принадлежит некоторому множеству X, то он очевидно будет принадлежать и объединению множества X с произвольным другим множеством.
Достаточно часто оказывается удобным ввести понятие "универсального" множества U, которое содержит все рассматриваемые нами множества.

Определение. Множество U\A называется дополнением множества A (до универсального множества) и обозначается через `.

Принцип двойственности. Пусть Ak, k = 1,...,n - некоторые подмножества универсального множества U, тогда имеют место следующие равенства:

 

 


Эти равенства связывающие операции пересечения и объединения множеств и их дополнений до универсального множества обычно называют соотношениями принципа двойственности.

Докажем первое соотношение:


Заметим, что в приведенном доказательстве все утверждения об элементе x соединены знаками , что позволяет одновременно строить доказательство утверждения в обе стороны.

Справедливость второго соотношения доказывается аналогично.

Пример.  Определим следующие множества: A - множество четных натуральных чисел; B - множество нечетных натуральных чисел; C - множество натуральных чисел, не больше 10. В качестве "универсального" множества мы будем рассматривать множество натуральных чисел n. Наша задача состоит в том, чтобы описать следующие множества:

 

 

 

 

Решение.
1) Множество

 

 

- это множество нечетных натуральных чисел, т.е. множество B
2) Каждое натуральное число является либо четным, либо нечетным, поэтому . Следовательно,

Если теперь считать, что в нашем распоряжении имеется универсальное множество U, то операции  можно определять друг через друга и фактически ввести некоторый базис операций в алгебре множеств.

Примеры.
1)  
2)
3)

Просмотров: 15648

Вернуться в оглавление:Дискретная математика




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.