ISBN ___________________

Р 93

Рецензенты:

доктор технических наук,

профессор Нижегородского государственного

технического университета им. Р.Е. Алексеева

В.В. Андреев

кандидат технических наук,

доцент Нижегородского государственного

технического университета им. Р.Е. Алексеева

В.Е. Гай

Р 93 Рыжкова, М.Н., Дискретная математика: учеб. пособие для студентов образовательной программы 010400.62 Прикладная математика и информатика / М.Н. Рыжкова, А.В. Макаров. - Муром: Изд.-полиграфический центр МИ ВлГУ, 2013. – 115 с.: ил.+ 20 табл. - Библиогр.: 12 назв.

ISBN ___________________

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

Пособие предназначено для студентов образовательной программы 010400.62 – «Прикладная математика и информатика».

УДК 510 (075.8)

Предисловие. 6

1. Элементы математической логики. 7

1.1. Логические связки и их таблицы истинности. 7

1.2. Свойства логических операций. 8

1.3. Функции алгебры логики и их свойства. 10

1.4. Совершенные формы.. 12

1.5. Многочлены Жегалкина. 14

Примеры решения задач. 15

Упражнения. 23

Вопросы для самоконтроля и повторения. 27

2. Множества и отображения. 28

2.1.Множества. 28

2.2. Операции над множествами. 29

2.3. Свойства операций над множествами. 30

2.4. Отображения множеств. 31

Примеры решения задач. 32

Упражнения. 36

Вопросы для самоконтроля и повторения. 39

3. Элементы комбинаторного анализа. 40

Примеры решения задач. 43

Упражнения. 45

Вопросы для самоконтроля и повторения. 48

4. Элементы теории графов. 49

4.1. Основные понятия теории графов. 49

4.2. Основные операции над графами. 52

4.3. Матрицы графов. 54

4.4. Мосты, деревья. 55

4.5. Алгоритмы построения минимального остовного дерева. 59

4.6 Задача о кратчайшем пути и алгоритм Дейкстры для ее решения. 60

4.7. Дерево кратчайших путей. 61

4.8. Гамильтоновы циклы и гамильтоновы графы.. 62

4.9. Эйлеровы циклы и эйлеровы графы.. 62

Примеры решения задач. 63

Упражнения. 75

Вопросы для самоконтроля и повторения. 80

5. Теория кодирования. 81

5.1. Основные понятия теории кодирования. 81

5.2. Проблема взаимной однозначности. 82

5.3. Коды Хемминга. 83

Примеры решения задач. 85

Упражнения. 89

Вопросы для самоконтроля и повторения. 91

6. Теория автоматов. 92

6.1. Основные понятия теории автоматов. 92

6.2. Способы задания конечного автомата. 93

Примеры решения задач. 95

Упражнения. 99

Вопросы для самоконтроля и повторения. 106

7. Задания для самостоятельной работы.. 107

Библиографический список. 117

Предисловие

Дискретная математика — область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях. К числу таких структур могут быть отнесены конечные группы, конечные графы, а также некоторые математические модели преобразователей информации, конечные автоматы, машины Тьюринга и так далее. Помимо указанных конечных структур, дискретная математика изучает некоторые алгебраические системы, бесконечные графы, вычислительные схемы определённого вида, клеточные автоматы и т. д.

Содержание данного учебного пособия соответствует требованиям государственного образовательного стандарта по дисциплине «Дискретная математика» для направления подготовки 010400.62 – «Прикладная математика и информатика».

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

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

1. Элементы математической логики

1.1. Логические связки и их таблицы истинности

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Основным понятием алгебры логики является высказывание. Высказывание (пропозиция) – это предложение, относительно которого имеет смысл говорить истинно оно или ложно. Высказыванием является утвердительное повествовательное предложение, которое формализует некоторое выражение мысли. Высказывание обычно имеет только одно логическое значение. Так, например, предложение "6 – четное число" следует считать высказыванием, так как оно истинное. Предложение "Рим — столица Франции" тоже высказывание, так как оно ложное.

Пусть X — высказывание. Если оно истинно, то пишут | X | = 1, если ложно, то | X | = 0.

Из простых высказываний различными способами может быть составлено новое высказывание, называемое составным, в то время как те высказывания, из которых оно состоит, называются простыми составляющими или компонентами.

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

Каждой строке таблицы истинности взаимно однозначно соответствует набор составляющих высказываний и соответствующее значение составного высказывания. Наборы из нулей и единиц в таблице истинности имеют стандартное расположение (в порядке возрастания):

Существует несколько логических операций, с помощью которых из простых высказываний можно получить составные.

Отрицание - высказывание, которое истинно, когда X ложно, и ложно, когда X истинно.

Конъюнкция X Ù Y – высказывание, которое истинно только в том случае, когда X и Y оба истинны.

Дизъюнкция X Ú Y – высказывание, которое истинно, если хотя бы одно из них истинно.

Импликация X ® Y – высказывание, которое ложно тогда и только тогда, если X истинно, а Y – ложно.

Эквивалентность X « Y – высказывание, которое истинно тогда и только тогда, когда X и Y оба истинны или оба ложны.

Штрих Шеффера (антиконъюнкция): .

Стрелка Пирса (антидизъюнкция): .

Сумма по модулю два (антиэквивалентность): .

X	Y		X Ù Y	X Ú Y	X ®Y	X « Y

1.2. Свойства логических операций

Алгебра логики позволяет легко преобразовывать логические выражения с помощью свойств логических операций:

- Идемпотентность дизъюнкции и конъюнкции (идемпотентность означает свойство чего-либо (объекта), которое проявляется в том, что повторное действие над объектом не изменяет его)

X Ú X « X,

X Ù X « X.

- Коммутативность дизъюнкции и конъюнкции

X Ú Y « Y Ú X,

X Ù Y « Y Ù X.

- Ассоциативность дизъюнкции и конъюнкции

X Ú (Y Ú Z)« (X Ú Y)Ú Z,

X Ù (Y Ù Z)« (X Ù Y)Ù Z.

- Дистрибутивность операций дизъюнкции и конъюнкции относительно друг друга

X Ú (Y Ù Z)« (X Ú Y) Ù (X Ú Z),

X Ù (Y Ú Z)« (X Ù Y) Ú (X Ù Z).

- Двойное отрицание

- Закон де Мо́ргана

,

.

- Склеивание

(X Ú Y) Ù (X Ú ) « X,

(X Ù Y) Ú (X Ù ) « X.

- Поглощение

X Ú (X Ù Y) « X,

X Ù (X Ú Y) « X.

- Действие с логическими константами 0 и 1

X Ú 0« X,

X Ù 0« 0,

X Ú 1« 1,

X Ù 1« X,

X Ù « 0.

- Закон исключения третьего

X Ú « 1.

1.3. Функции алгебры логики и их свойства

Логической (булевой) функцией (или просто функцией) n переменных y = f(x₁, x₂, …, x_n) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

Булевы функции одной и двух переменных называют элементарными. Рассмотрим значения таких функции с помощью таблиц истинности.

- Функция одной переменной

1). Функции f₁(x) и f₄(x) при любых значениях x равны соответственно 0 и 1, и называются константами.

2). Функция f₃(x) совпадает с переменной x и называется тождественной:

f₃(x) = x.

3). Функция f₂(x) принимает значения, противоположные значениям переменной x и называется отрицанием:

f₂(x) =

- Функция двух переменных

1). Функции f₁ и f₁₆ являются константами 0 и 1 соответственно.

2). Функции f₄, f₆, f₁₁, f₁₃ существенно зависят только от одной переменной:

f₄ = x f₆ = y f₁₁ = f₁₃ =

3). Функция f₂ = x Ù y – конъюнкция.

4). Функция f₈ = x Ú y – дизъюнкция.

5). Функция f₁₀ = x « y – эквивалентность.

6). Функция f₇ = x Å y – сумма по модулю два.

7). Функция f₁₄ = x ® y – импликация.

8). Функция f₁₂ = y ® x – конверсия.

9). Функция f₁₅ = x | y – штрих Шеффера.

10). Функция f₉ = x ¯ y – стрелка Пирса.

11). Функции f₃ и f₅ – логически несовместимы с операциями конверсии и импликации и называются функциями запрета.

Булеву функцию любого числа переменных можно задать формулой, содержащей функции одной или двух переменных посредством подстановки одних булевых функций вместо переменных в другие булевы функции, т.е. посредством суперпозиции булевых функций.

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

x Ù x = x Ù x = 0 x Ù 0 = 0 x Ù 1 = x

x Ú x = x Ú x = 1 x Ú 0 = x x Ú 1 = 1

x Å x = 0 x Å = 1 x Å 0 = x x Å 1 =

Для конъюнкции и дизъюнкции справедливы тождества:

x₁ Ú Ù x₂ = x₁ Ú x₂;

x₁ Ù( ₂ Ú x₁) = x₁ Ù x₂.

1.4. Совершенные формы

Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных x₁, x₂, …, x_n называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны относительно переменных x₁, x₂, …, x_n.

СДНФ легко построить, если функция задана таблицей истинности (см. пример 5), но если функция задана формулой, то ее СДНФ можно получить без построения таблицы истинности.

Построение СДНФ осуществляется в два этапа:

- сначала строится ДНФ

- затем ДНФ преобразовывается в СДНФ.

Чтобы преобразовать формулу в ДНФ необходимо выполнить следующие действия:

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

2). Заменить знак отрицания, относящийся к выражениям, на знак отрицания, относящийся к переменным, используя законы де Моргана:

3). Избавиться от знаков двойного отрицания.

4). Применить к операциям конъюнкции и дизъюнкции свойства дистрибутивности и законы поглощения, упростить формулу.

Полученную ДНФ преобразовывают в СДНФ, превращая правильные элементарные конъюнкции в полные. Если в правильную элементарную конъюнкцию не входит, например, переменная y, то нужно домножить эту конъюнкцию на скобку вида (y Ú ) = 1 и раскрыть скобки. Повторить операцию столько раз, сколько нужно, что бы все правильные элементарные конъюнкции стали полными. Если появятся одинаковые конъюнкции, то убрать лишние (y Ú y = y).

Совершенной конъюнктивной нормальной формой (СКНФ) относительно переменных x₁, x₂, …, x_n называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильны и полны относительно переменных x₁, x₂, …, x_n.

СКНФ легко построить, если функция задана таблицей истинности (см. пример 5.), но если функция задана формулой, то ее СКНФ можно получить без построения таблицы истинности.

Построение СКНФ осуществляется в два этапа:

- сначала строится КНФ

- затем КНФ преобразовывается в СКНФ.

Чтобы преобразовать формулу в КНФ необходимо выполнить следующие действия:

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

2). Заменить знак отрицания, относящийся к выражениям, на знак отрицания, относящийся к переменным, используя законы де Моргана.

3). Избавиться от знаков двойного отрицания.

4). Применить к операциям конъюнкции и дизъюнкции свойства дистрибутивности и законы поглощения, упростить формулу.

Полученную КНФ преобразовывают в СКНФ, превращая правильные элементарные дизъюнкции в полные. Если в правильную элементарную дизъюнкцию не входит, например, переменная y, то нужно прибавить логически к этой дизъюнкции выражение вида (y Ú ) = 0 и воспользоваться законом дистрибутивности. Если появятся одинаковые дизъюнкции, то убрать лишние (y Ù y = y).

1.5. Многочлены Жегалкина

Полиномом Жегалкина называется многочлен (полином), являющийся суммой константы и различных одночленов, в которые каждая из переменных входит не выше, чем в первой степени.

Общий вид полинома Жегалкина:

где a Î {0, 1}, число слагаемых равно 2ⁿ, где n – число переменных.

Первый способ получения многочлена Жегалкина:

- Находят множество двоичных наборов, на которых функция равна 1.

- Составляют СДНФ.

- В СДНФ каждый знак Ú заменяют на Å.

- Упрощают полученное выражение, используя тождество:

Å x = 1.

- В полученной формуле заменяют отрицание на = x Å 1.

- Раскрывают скобки, приводят подобные члены, используя тождество x Å x = 0, x Å 0 = x.

Второй способ построения полинома Жегалкина с помощью треугольника Паскаля:

верхняя сторона такого треугольника есть строка значений исходной функции. В каждой строке, начиная со второй, любой элемент треугольника равен «сумме по модулю два» двух соседних элементов предыдущей строки. Рассмотрим левую сторону треугольника Паскаля. Единицам этой стороны соответствуют наборы значений переменных исходной функции. Соединив знаком конъюнкции переменные, имеющие значение единицы в наборах, и, соединив их знаком суммы по модулю два, получим полином Жегалкина.

Третий способ построения многочлена Жегалкина методом неопределенных коэффициентов:

- Необходимо составить систему линейных уравнений относительно 2ⁿ неизвестных коэффициентов, содержащих 2ⁿ уравнений, решением которых являются коэффициенты многочлена Жегалкина. В качестве примера рассмотрим функцию трех переменных:

f(x, y, z) = a₀ Å a₁x Å a₂y Å a₃z Å a₄xy Å a₅xz Å a₆yz Å a₇xyz.

f(0, 0, 0) = a₀

f(0, 0, 1) = a₀ Å a₃

f(0, 1, 0) = a₀ Å a₂

f(0, 1, 1) = a₀ Å a₂ Å a₃ Å a₆

f(1, 0, 0) = a₀ Å a₁

f(1, 0, 1) = a₀ Å a₁ Å a₃ Å a₅

f(1, 1, 0) = a₀ Å a₁ Å a₂ Å a₄

f(1, 1, 1) = a₀ Å a₁ Å a₂ Å a₃ Å a₄ Å a₅ Å a₆ Å a₇.

- Далее приравнивают соответствующие значения функции из таблицы истинности и находят значения коэффициентов.

- Подставляют коэффициенты в формулу, упрощают (остаются только те слагаемые, коэффициент при которых равен 1).

Примеры решения задач

1). Составить таблицу истинности для выражения:

Решение:

Расставим порядок действий:

1 -

2 -

3 -

4 -

5 -

6 -

X	Y	Z

2). Доказать эквивалентность выражений

X Ù (X Ú Z) Ù (Y Ú Z) « (X Ù Y) Ú (X Ù Z).

Составим таблицы истинности для левой и правой частей

Т.к. значения функций одинаковы, то эквивалентность функций доказана.

3). Функции f(x, y) и g(x, y) заданы таблицами истинности:

Построить таблицу истинности для суперпозиции

h (x₁, x₂, x₃) = f(g(x₁, x₃), g(x₂, x₁)).

4). Упростить формулу:

f = x Ú x Ú y Ú y Ù z Ú Ù x

a). Применим свойство идемпотентности: x Ú x = x, y Ú y = y:

f = x Ú y Ù z Ú Ù x

b). Применим свойство коммутативности: x Ú y = y Ú x

f = x Ù x Ú y Ù z Ú

c). Применим свойство поглощения x Ù x Ú y = x:

f = x Ù z Ú

d). Применим свойства из п. 12: z Ú = 1; 1 Ù x = x:

f = x

5). Построить СДНФ и СКНФ формулы

f (x, y, z) = x « ( Å ( )).

Построим таблицу истинности:

x	y	z					Å (	x « ( Å ( ))

Найдем СДНФ по таблице:

(0, 0, 0) -

(1, 0, 1) -

(1, 1, 0) -

СДНФ: Ú Ú

Теперь преобразуем формулу:

f (x, y, z) = x « ( Å ( )):

a).

b). y Å ( ) = y Å ( ) = y( ) Ú =

= y( ) Ú (zx Ú ) = y Ú zx Ú

c). Раскроем скобки и используем свойство идемпотентности:

y Ú zx Ú =

d). x « ( Å ( )) =

e). Применим закон де Моргана к инверсии во втором слагаемом, раскроем скобки и упростим, используя правило поглощения и идемпотентности:

f). Тогда получим:

g). Получили СДНФ: f (x, y, z) = .

Найдем СКНФ по таблице:

(0, 0, 1): ,

(0, 1, 0): ,

(0, 1, 1): ,

(1, 0, 0): ,

(1, 1, 1):

Тогда СКНФ:

f (x, y, z) = ( )( )( )( )( ).

Теперь преобразуем формулу f (x, y, z) = x « ( Å ( )):

a).

b).

c).

Избавимся от отрицания и применим правила поглощения и идемпотентности:

Получили СКНФ:

f (x, y, z) = ( )( )( )( )( ).

6). Построить полином Жегалкина функции f (x, y, z), заданной таблицей истинности:

Первый способ:

a). Построим СДНФ:

b). Заменим Ú на Å:

c). Упростим, используя операцию дистрибутивности и тождество Åx=1:

d). Заменим = x Å 1:

e). Заменим x Å x = 0, x Å 0 = x

Второй способ:

a). В пятом столбце строится треугольник Паскаля:

- первая строка заполняется самой функцией

- значения второй строки получаются суммой Å двух элементов первой строки:

1 Å 1 = 0, 1 Å 0 = 1, 0 Å 0 = 0, 0 Å 1 = 1, 1 Å 0 = 1, 0 Å 0 = 0,
0 Å 0 = 0,

- так же заполняем все остальные строки.

b). Заполним последнюю колонку конъюнкциями элементов, которые в первых трех столбцах равны 1.

c). Соединим знаком Å те конъюнкции, строки которых с левой стороны треугольника равны 1:

3-Треттий способ:

a). Построим многочлен Жегалкина для функции трех переменных:

f(x, y, z) = a₀ Å a₁x Å a₂y Å a₃z Å a₄xy Å a₅xz Å a₆yz Å a₇xyz

и систему уравнений, позволяющих найти коэффициенты:

f(0, 0, 0) = a₀

f(0, 0, 1) = a₀ Å a₃

f(0, 1, 0) = a₀ Å a₂

f(0, 1, 1) = a₀ Å a₂ Å a₃ Å a₆

f(1, 0, 0) = a₀ Å a₁

f(1, 0, 1) = a₀ Å a₁ Å a₃ Å a₅

f(1, 1, 0) = a₀ Å a₁ Å a₂ Å a₄

f(1, 1, 1) = a₀ Å a₁ Å a₂ Å a₃ Å a₄ Å a₅ Å a₆ Å a₇

b). Приравняем к значениям функции и вычислим коэффициенты:

a₀ = 1,

a₀ Å a₃ = 1, 1 Å a₃ = 1, a₃ = 0,

a₀ Å a₂ = 0, 1 Å a₂ = 0, a₂ = 1,

a₀ Å a₂ Å a₃ Å a₆ = 0, 1 Å 1 Å 0 Å a₆ = 0, a₆ = 0,

a₀ Å a₁ = 1, 1 Å a₁ = 1, a₁ = 0,

a₀ Å a₁ Å a₃ Å a₅ = 0, 1 Å 0 Å 0 Å a₅ = 0, a₅ = 1,

a₀ Å a₁ Å a₂ Å a₄ = 0, 1 Å 0 Å 1 Å a₄ = 0, a₄ = 0,

a₀ Å a₁ Å a₂ Å a₃ Å a₄ Å a₅ Å a₆ Å a₇ = 0,

1 Å 0 Å 1 Å 0 Å 0 Å 1 Å 0 Å a₇ = 0, a₇ = 1.

c). Выпишем коэффициенты и подставим их в функцию:

a₀ = 1, a₁ = 0, a₂ = 1, a₃ = 0, a₄ = 0, a₅ = 1, a₆ = 0, a₇ = 1.

Упражнения

1). Составить таблицу истинности для логических выражений

1.1

1.2

1.3

1.4

1.5

1.6

1.7

1.8

1.9

1.10

2). Упростить логические выражения

2.1

2.2

2.3

2.4

2.5

2.6

2.7

2.8

2.9

2.10

3). Проверить эквивалентность формул

3.1

3.2

3.3

3.4

3.5

3.6

3.7

3.8

3.9

3.10

4). Выразить с помощью суперпозиций следующие функции. В случае невозможности выражения доказать это:

4.1

4.2

4.3

4.4

4.5

4.6

4.7

4.8

5). Привести формулу к КНФ

5.1

5.2

5.3

5.4

5.5

5.6

5.7

5.8

5.9

5.10

6). Привести формулу к СКНФ

6.1

6.2

6.3

6.4

6.5

6.6

6.7

6.8

6.9

6.10

7). Привести формулу к ДНФ

7.1

7.2

7.3

7.4

7.5

7.6

7.7

7.8

7.9

7.10

8). Привести формулу к СДНФ

8.1

8.2

8.3

8.4

8.5

8.6

8.7

8.8

8.9

8.10

9).Построить многочлен Жегалкина

9.1

9.2

9.3

9.4

9.5

9.6

9.7

9.8

9.9

9.10

10). Проверить линейность функции

10.1

10.2

10.3

10.4

10.5

10.6

10.7

10.8

10.9

10.10

Вопросы для самоконтроля и повторения

Что такое высказывание? Простое и составное высказывание.

1. Какими способами можно получить из простого высказывания составное? Что такое логические связки и какие они бывают?

2. Что такое таблица истинности?

3. Перечислите свойства логических операций.

4. Что такое функция алгебры логики и каковы ее свойства?

5. Как задаются функции одной и двух переменных?

6. Что такое нормальные формы, совершенные нормальные формы? Перечислите способы их построения.

7. Что такое полином Жегалкина и как он строится?

2. Множества и отображения

2.1.Множества

Множество - один из ключевых объектов математики, в частности, теории множеств и логики.

Понятие множества обычно принимается за одно из исходных (аксиоматических) понятий, то есть не сводимое к другим понятиям, а значит и не имеющее определения.

Объекты, из которых состоит множество, называют элементами множества или точками множества. Множества чаще всего обозначают большими буквами латинского алфавита, его элементы — маленькими. Если а – элемент множества А, то записывают а Î А (а принадлежит А). Если а не является элементом множества А, то записывают а ∉ А (а не принадлежит А).

Если множество состоит из элементов a₁, a₂,… a_n, то пишут a₁, a₂,… a_n Î А или А = { a₁, a₂,… a_n}. При этом порядок перечисления элементов значения не имеет.

Множество A является подмножеством множества B, если любой элемент, принадлежащий A, также принадлежит B, пишут A Ì B. Множество B в таком случае называется надмножеством множества A, и этот факт часто записывают: B É A.

Множества, содержащие в качестве элементов другие множества, называются семействами или классами.

Множества, не содержащие ни одного элемента, называются пустыми и обозначаются Æ. Множества, содержащие один элемент – единичные множества.

2.2. Операции над множествами.

Что бы представить операции над множествами, можно пользоваться диаграммами Эйлера-Венна. Прямоугольник здесь обозначает универсальное множество, а круги – его подмножества (рис. 1.1).

Рис. 1.1	Рис. 1.2

1). Дополнением к множеству А называется множество элементов, которые не содержатся в А. Обозначается (рис. 1.2).

2). Пересечением множеств А и В называется множество элементов, принадлежащих и А и В. Обозначается А Ç В (рис. 1.3).

Рис. 1.3	Рис. 1.4

Если А и В ­– непустые множества, пересечение которых пусто, т.е. А Ç В = Æ, то их называют непересекающимися (рис. 1.4).

3). Объединением множеств А и В называется множество элементов, принадлежащих либо А либо В либо обоим. Обозначается А È В (рис. 1.5).

Рис. 1.5	Рис.1.6

4). Разностью множеств А и В называется множество элементов, принадлежащих А, но не принадлежащих В. Обозначают А \ В (рис. 1.6).

2.3. Свойства операций над множествами

Множества, его подмножества и законы сочетания подмножеств образуют алгебраическую систему, которая называется булевой алгеброй.

1). Идемпотентность:

A È A = A,

A Ç A = A.

2). Коммутативность:

A È B = B È A,

A Ç B = B Ç A.

3). Ассоциативность:

A È (B È C)= (A È B)È C,

A Ç (B Ç C)= (A Ç B)Ç C.

4). Дистрибутивность:

A È (B È C)= (A È B) Ç (A È C),

A Ç (B Ç C)= (A Ç B) È (A Ç C).

5). Законы поглощения:

A È (A Ç B) = A,

A Ç (AÈB) = A.

6). Свойства нуля:

A È Æ= A,

A Ç Æ= Æ,

.

7). Свойства единицы:

A È U = U,

A Ç U = A,

.

8). Инволютивность:

.

9). Законы де Моргана:

,

.

10). Свойства дополнения:

,

.

2.4. Отображения множеств

Пусть X и Y - множества. Отображением f из множества X в множество Y мы будем называть правило, по которому каждому