Учебное пособие 1161

ФГБОУ ВО «Воронежский государственный технический университет»

Кафедра компьютерных интеллектуальных технологий проектирования

XXX-2016

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению практических работ по дисциплине «Дискретная математика»

для студентов направления подготовки бакалавров 09.03.02 «Информационные системы и технологии» (профиль «Информационные системы и технологии в машиностроении») очно-заочной формы обучения

Воронеж 2016

0

1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

Теоретические сведения

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

Множества будем обозначать заглавными буквами латинского алфавита; объекты, которые образуют множества, будем называть элементами множества и обозначать малыми буквами латинского алфавита. Если элемент x принадлежит множеству X, то этот факт записывается в виде x , иначе x ..

Множество, содержащее конечное число элементов, называется конечным; в противном случае множество называется бесконечным. Количество элементов конечного множества называется мощностью и обозначается =n, если множество X

содержит n элементов. Если множество не содержит ни одного элемента, то оно называется пустым и обозначается .

Для произвольных множеств X и Y можно определить два типа отношений – отношение равенства и отношение включения.

Два множества считаются равными, если они состоят из одних и тех же элементов. Принято обозначение X=Y, если X и Y равны, и X Y- иначе.

Если каждый элемент множества X является элементом множества Y, то говорят, что X включено в Y и обозначают

: (x x ).

Вэтом случае говорят, что множество X является подмножеством множества Y. В частности X и Y могут совпадать, поэтому называется также отношение нестрогого включения.

Если и , то говорят, что X есть собственное подмножество Y и обозначают , отношение между мно-

1

жествами в этом случае называется отношением нестрогого включения.

Невключение подмножества X в множество Y обозначает-

ся ( ).

Заметим, что если X является подмножеством Y и наоборот, то X и Y состоят из одних и тех же элементов, поэтому

( и ).

Для каждого множества X существует множество, элементами которого являются различные подмножества множества X. Такое множество называется семейством множества и обозначается p(X) [1, 2].Так как включено в любое множество, то

p( ).

Пример. Пусть x1, x2 , x3 . Тогда

p( ) x1 , x2 , x3 , x1,x2 , x1,x3 , x2 ,x3 , x1,x2 ,x3 , .

Если в рамках некоторого рассуждения рассматриваются подмножества некоторого множества, то оно называется универсальным, или универсумом и обозначается U [7].

Множество может быть задано различными способами [1, 2, 6]: перечислением элементов в скобках (для конечных множеств) или указанием их свойств, однозначно определяющих принадлежность элементов данному множеству, при этом используется запись

X={x x обладает свойством P(x)}

(выражение в скобках читается: множество всех элементов x, которые обладают свойством P(x). Так, множество натуральных чисел N={1,2,…} может быть описано следующим образом:

N={i если целое i N, то i 1 N,i 1}.

2

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

Объединением множеств X и Y называется множество, все элементы которого являются элементами множества

Пересечением множеств X и Y называется множество

, элементы которого являются элементами обоих мно-

жеств X и Y: ={x | x X и x Y}.

Очевидно, что выполняются включения ;

.

Дополнением множества X называется множество всех

тех элементов x, которые не принадлежат множеству X: ={x | x U и x X}.

Разностью множеств X и Y называется множество X\Y всех тех элементов X, которые не принадлежат Y:

X\Y={x x и x }=X Y .

Абсолютное дополнение множества Х представляется с помощью операции относительного дополнения следующим

образом =U\X.

Симметричной разностью множества X и Y называется множество ( \ ) ( \ ).

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

1., (коммутативность);

2.( ) ( ) , ( ) ( )

(ассоциативность);

3.( ) ( ) ( ),

( ) ( ) ( ) (дистрибутивность);

4., ;

5.U U, U ;

6.U, (комплиментарность);

7 . , (идемпотентность);

3

8., (законы де Моргана);

9.X (двойное отрицание);

10.( ) , ( ) (з-н поглощения).

Декартовым (прямым) произведением множеств X и Y на-

зывается множество упорядоченных пар вида

{(x,y) x и y }.

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

Задача 1.

Пусть на универсуме E={a, b, c, d, e, f, g} определены множества X={a, c, d, f}, Y={b, d, e, f}. Найти X Y, X Y, , X\Y, Y\X, X Y.

Решение. X Y={ a, b, c, d, e, f}, X Y={d, f}, ={b, e, g}, X\Y={a, c}, Y\X={b, e}, X Y={a, b, c, e}.

Задача 2.

Равны ли следующие множества:

1){2, 4, 5} и {2, 4, 5, 2};

2){1, 2} и {{1,2}};

3){1, 2, 3} и {{1}, {2}, {3}}.

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

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

2)Нет. Так как, например, элемент 1 из первого множества не имеет себе равного во втором множестве. Второе множество состоит из единственного элемента – множества {1, 2}.

3)Нет. Так как элементами первого множества являются числа 1, 2, 3, а элементами второго множества являются множества, состоящие из одного элемента {1}, {2}, {3}.

Задача 3.

Множество задано перечислением элементов А={2, 4, 6, 8, …, 32}. Задайте множество с помощью характерного для его элементов свойства.

Решение. Множества А представляет собой множество четных натуральных чисел от 2 до 32, поэтому это множество можно записать в виде

А={x N / x =2n, n=1,…, 16}.

Задача 4.

Доказать A (B C) = (A B) (A C).

Решение. Чтобы доказать равенство двух множеств X = Y нужно доказать, что X Y и X Y. Докажем, что A (B C) (A B) (A C). Для доказательства этого включения выберем произвольный элемент из множества A (B C) и покажем, что он принадлежит множеству (A B) (A C). Итак, пусть x A (B C). Тогда x A и x B C. Если x B, то x A B, а значит, x (A B) (A C). Если x C, то x A C, а значит, x (A B) (A C). Таким образом, A (B C) (A B) (A C).

Теперь докажем, что (A B) (A C) A (B C). Пусть x (A B) (A C). Если x A B, то x A и x B, отсюда следует, что x A и x B C, т.е. x A (B C). Если x A C, то x A и x C. Отсюда следует, что x A и x B C, т.е. x A (B C).

Итак, (A B) (A C) A (B C). Таким образом, получили, что

A (B C) (A B) (A C) и (A B) (A C) A (B C), а это значит, что эти два множества равны.

Решение подобных задач можно оформить в более формализованном виде, используя “{” для системы высказываний,

5

объединенных союзом “и”, “[”- для системы высказываний, объединенных союзом «или».

Задача 5.

Доказать тождество (A \ B)\C (A \C)\(B \C). Решение. Используя свойства операций над множествами,

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

(A\C)\(B\C) (A C) (B C) (A C) (B C)

(A C) (B C) (A C B) (A C C)

(A C B) (A ) (A C B) A C B

A \ B \C

Задача 6.

Доказать тождество B (A\ B) .

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

Никакой элемент x не может одновременно принадлежать самому множеству и его дополнению, поэтому мы пришли к противоречию.

Задача 7. Упростить выражение

(A B Y X) (A Y) (B Y) (Y X).

Решение.

(A B Y X ) (A Y ) (B Y ) (Y X ) (A B

Y X) (Y (A B X)) (Y (A B X))

(Y (A B X )) Y ((A B X ) (A B X ))

Y E Y .

6

Задача 8. Доказать закон де Моргана . Решение. С одной стороны,

x .

Сдругой стороны,

x x x .

Так как и , то

, что и требовалось доказать.

Задачи и упражнения

1.Докажите тождество (А B) (А B)= А .

2.Докажите, что B (A\C) (B A)\(B C).

3.Упростите (A B) (A B) (A B).

4.Докажите тождество

[(A X) (B X)] (A X) (B X).

5.Упростите A\((A B) \ B).

6.Докажите закон поглощения X (X Y) X .

7.Докажите, что X (Y\ X) .

8.Решить систему соотношений относительно множества

Хи указать условия совместности системы

B\ X AB X CA B C

7

2. БИНАРНЫЕ ОТНОШЕНИЯ

Теоретические сведения

В множестве X n-местным или n-арным отношением называется подмножество R n-й декартовой степениn = .... заданного множества, R n , называется носителем отношения [2, 6, 7]. Одноместное отношение называется унарным, или свойством, и соответствует подмножеству множества X. Особую роль в приложениях играют бинарные отношения R Х Х. Каждому бинарному отношению можно поставить в соответствие матрицу бинарного отношения, которую также будем обозначать через R= rij n n(n ) и

элементы которой rij определяются по следующему правилу:

1, если (xi,xj ) R

rij =

0, если (xi,xj ) R

Свойства бинарных отношений Отношение R называется

рефлексивным, если для х Х (х, х) R;

антирефлексивным, если х Х (х, х) R; симметричным, если для х, у Х ((х,у) R (у,х) R);

антисимметричным, если для х, у Х ((х, у) R (у, х) R); транзитивным, если для x, у, z ((х, у) R и (у, z) R (x, z) R.

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

Пусть на множестве Х задано отношение U тогда

8