Шаг 2. Выделение столбцов, содержащих одну метку.

Если в каких-нибудь столбцах составленной таблицы имеется только одна метка, то строки, в которых стоят эти метки, определяют простые импликанты, которые не могут быть исключены из сокращенной ДНФ, т. к. без них не может быть получено покрытие всех элементарных конъюнкций СДНФ. Они являются существенными и обязательно входит в минимальную ДНФ. Поэтому из таблицы покрытий исключаются строки, соответствующие существенным импликантам, и столбцы элементарных конъюнкций СДНФ, покрывемые этими существенными импликантами.

Шаг 3. Вычеркивание лишних столбцов.

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

Шаг 4. Вычеркивание лишних существенных импликантов.

Если после выбрасывания некоторых столбцов в результате шага 3, в таблице появляются строки, в которых нет ни одной метки, то простые импликанты, соответствующие этим строкам, исключаются из дальнейшего рассмотрения, т. к. они не покрывают оставшиеся в рассмотрении элементарные конъюнкции СДНФ.

Шаг 5. Выбор минимального покрытия существенными импликантами.

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

Пример 4.20.

Продолжим предыдущий пример.

1. Составляем таблицу покрытий. Для формулы, булевой функции с СДНФ:

f(x1, x2, x3) = Шx1&x2&x3V x1&Шx2&Шx3 V x1&Шx2&x3 V x1&x2&x3

мы получили равносильную ей сокращенную ДНФ:

F1(x1, x2, x3) = x2&x3 V x1&Шx2 V x1&x3.

Каждой элементарной конъюнкции x1s1&x2s2&...&xnsn, (xi si = xi, если si = 0 и xisi = Шxi, если si = 1, i = 1, 2, ... ,n), входящей в СДНФ, можно сопоставить набор переменных из нулей и единиц. Этот наборы идентифицируют столбцы. Каждому простому импликанту из сокращенной ДНФ также можно сопоставить набор из нулей, единиц и прочерков, где 0 означает, что переменная берется с отрицанием, 1 - переменная берется без отрицания, “ - ” - переменная отсутствует. Для нашего примера получим следующую таблицу (таблица 4.6) из 4 столбцов, соответствующих 4 элементарным конъюнкциям СДНФ F(x1, x2, x3, x4) и 3 строк, соответствующих 3 простым импликантам сокращенной ДНФ F1(x1, x2, x3, x4).

Таблица 4.6

	011	100	101	111
-11	*			*
10-		*	*
1-1			*	*

2. Выделяем столбцы, содержащие одну метку - это 1-ый и 2-ой столбцы. Импликант x2&x3 (ему соответствует 1-ая строка) является существенным. Он покрывает две элементарные конъюнкции СДНФ: Шx1&x2&x3 и x1&x2&x3 (им соответствуют 1-ый и 4-ый столбцы). Импликант x1&Шx3 (ему соответствует 2-ая строка) тоже является существенным. Он покрывает две элементарные конъюнкции СДНФ: x1&Шx2&Шx3 и x1&Шx2&x3 (им соответствуют 2-ой и 3-ий столбцы).

Все указанные строки (1-ую и 2-ую) и столбцы (1-ый, 2-ой, 3-ий и 4-ый) вычеркиваем из таблицы покрытий. После этого все элементы таблицы окажутся вычеркнутыми. Следовательно, два существенных импликанта x2&x3 и x1&Шx3 покрывают все элементарные конъюнкции СДНФ.

Итак, минимальная ДНФ для нашей функции имеет вид:

F2(x1, x2, x3) = x2&x3 V x1&Шx2 .

Рассмотрим еще один пример нахождения минимальной ДНФ булевой функции.

Пример 4.21.

Пусть булева функция задана таблицей

Таблица 4.7

x1 x2 x3 x4	f(x1, x2, x3, x4)
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 0

Применим вначале алгоритм Квайна - Мак-Класки для нахождения сокращенной ДНФ.

Очевидно, в силу алгоритма 4.3, данная функция имеет следующую формулу в СДНФ:

F(x1, x2, x3, x4) = Шx1&Шx2&x3&x4 V Шx1&x2 &Шx3 &x4 V Шx1&x2&Шx3&Шx4 V

Шx1&x2&x3&x4Vx1&Шx2&Шx3&x4Vx1&Шx2&x3&x4Vx1&x2&Шx3&Шx4Vx1&x2&Шx3&x4.

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

Группы A0 нет.

Группа A1:

0 1 0 0

Группа A2:

0 0 1 1

0 1 0 1

1 0 1 0

1 1 0 0

Группа A3:

0 1 1 1

1 0 1 1

1 1 0 1

Группы A4 нет.

Производим попарное сравнение наборов переменных, входящих в соседние группы.

При сравнении групп A1 и A2:

вместо (0 1 0 0) и (0 1 0 1) получим (0 1 0 -);

вместо (0 1 0 0) и (1 1 0 0) получим (- 1 0 0);

При сравнении групп A2 и A3:

вместо (0 0 1 1) и (0 1 1 1) получим (0 - 1 1);

вместо (0 0 1 1) и (1 0 1 1) получим (- 0 1 1);

вместо (0 1 0 1) и (0 1 1 1) получим (0 1 - 1);

вместо (0 1 0 1) и (1 1 0 1) получим (- 1 0 1);

вместо (1 0 0 1) и (1 0 1 1) получим (1 0 - 1);

вместо (1 0 0 1) и (1 1 0 1) получим (1 - 0 1);

вместо (1 1 0 0) и (1 1 0 1) получим (1 1 0 -).

После этого этапа массив R пуст, т. к. все наборы участвовали в образовании наборов с прочерками, а массив P = P(1) включает следующие наборы:

(0 1 0 -);

(- 1 0 0);

(0 - 1 1);

(- 0 1 1);

(0 1 - 1);

(- 1 0 1);

(1 0 - 1);

(1 - 0 1);

(1 1 0 -).

Теперь попарно сравниваются между собой наборы с прочерками. Наборы с одним прочерком, не участвовавшие в образовании наборов с двумя прочерками, помещаются в массив R.

Для нашего примера

вместо (0 1 0 -) и (1 1 0 -) получим (- 1 0 -);

вместо (- 1 0 0) и (- 1 0 1) получим (- 1 0 -)

После этого этапа в массив R попадают наборы, не участвовавшие в образовании наборов с двумя прочерками:

(0 - 1 1);

(- 0 1 1)

(0 1 - 1);

(1 0 - 1);

(1 - 0 1);

Массив P(2) состоит из набора с двумя прочерками:

(- 1 0 -).

Набор с двумя прочерками один и процедура сравнения заканчивается. Поэтому все наборы из P(2) попадают в массив R, который после этого включает наборы:

(0 - 1 1);

(- 0 1 1)

(0 1 - 1);

(1 0 - 1);

(1 - 0 1);

(- 1 0 -).

Сокращенная ДНФ имеет вид:

F1(x1, x2, x3, x4) = Шx1&x3&x4 V Шx2&x3&x4 V Шx1&x2&x4 V x1&Шx2&x4 V x1&Шx3&x4 x2&Шx3.

Найдем теперь минимальную ДНФ с помощью таблицы покрытий (алгоритм 4.7).

Составляем таблицу покрытий.

Для нашего примера получим следующую таблицу (таблица 4.8) из 8 столбцов, соответствующих 8 элементарным конъюнкциям СДНФ F(x1, x2, x3, x4) и 6 строк, соответствующих 6 простым импликантам сокращенной ДНФ F1(x1, x2, x3, x4).

Таблица 4.8

	0011	0100	0101	0111	1001	1011	1100	1101
0-11	*			*
-011	*					*
01-1			*	*
10-1					*	*
1-01					*			*
-10-		*	*				*	*

Выделяем столбцы, содержащие одну метку - это 2-ой и 7-ой столбцы. Оба этих столбца определяют один и тот же импликант x2&?x3 (ему соответствует 6-ая строка), который является существенным. Он покрывает следующие четыре элементарные конъюнкции СДНФ: ?x1&x2&?x3&x4, Шx1&x2&Шx3&Шx4, x1&x2&Шx3&Шx4, x1&x2&Шx3&x4 (им соответствуют 2-ой, 3 - ий, 7 - ой и 8 - ой столбцы). Все указанные строки и столбцы вычеркиваем из таблицы покрытий. После этого таблица примет вид:

Таблица 4.9

	0011	0111	1001	1011
0-11	*	*
-011	*			*
01-1		*
10-1			*	*
1-01			*

В полученной таблице нет одинаковых столбцов. В полученной таблице нет пустых строк. Выбираем такую совокупность существенных импликантов, которая покрывает все столбцы и содержит наименьшее количество букв. Для нашей таблицы это импликанты Шx1&x3&x4 и x1&Шx2&x4 (1 - ая и 4 - ая строки таблицы 4. 9), т. к. они покрывают все оставшиеся столбцы.

Итак, минимальная ДНФ для нашей функции имеет вид:

F2(x1, x2, x3, x4) = Шx1&x3&x4 V x1&Шx2&x4 V x2&Шx3 .

4.9 Применение алгебры булевых функций к релейно-контактным схемам

Рассмотрим электрические релейно-контакные схемы, главный элемент которых - электромагнитное реле.

Пусть x1, x2, ... , xn - набор контактов в схеме. Контакты могут быть размыкающими и замыкающими. Контакт называется замыкающим, если он замыкается при подаче напряжения. Контакт называется размыкающим, если он размыкается при подаче напряжения. Один и тот же контакт в схеме может быть как замыкающим, так и размыкающим.

Каждой последовательно- параллельной схеме сопоставим функцию проводимости:

f(x1, x2, ... , xn) =

Функция проводимости схемы, состоящей из одного элемента x, для замыкающего контакта есть f(x) = x, а для размыкающего контакта f(x) = ?x.

Функция проводимости схемы, состоящей из двух последовательно соединенных контактов x и y (рис. 4. 1) есть f(x, y) = x&y.

Рис. 4. 1

Функция проводимости схемы, состоящей из двух параллельно соединенных контактов x и y (рис. 4. 2) есть f(x, y) = x V y.

Рис. 4. 2

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

Пример 4.22.

Найдем функцию проводимости схемы, изображенной на рис. 4. 3.

Рис. 4.3

f(x, y, z) = (y&z) V (x&Шy&z) V (Шx&Шy&z) є (y&z) V (Шy&z) є z.

Эквивалентная схема изображена на рис. 4.4.

Рис 4.4

Контрольные вопросы к теме 4

1. Выберите правильный вариант ответа 1 - 4 для следующих вопросов:

а) Сколько существует различных булевых функций n переменных? б) Сколько существует различных наборов переменных для булевой функции n переменных?

Варианты ответа: 1) 2n; 2) 22; 3) n2; 4) n!.

2. Какое из следующих утверждений верно:

а) Переменные булевой функции и сама булева функция принимают значения 0 или 1;

б) Переменные булевой функции принимают значения 0 или 1, а значения самой булевой функции совпадают с множеством действительных чисел;

в) Значения переменных булевой функции совпадают с множеством действительных чисел, а сама булева функция принимает значения 0 или 1;

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

3. Выберите правильный вариант ответа 1 - 4 для следующих вопросов:

а) Сколько может быть различных ДНФ у булевой функции?

б) Сколько может быть различных СДНФ у булевой функции?

в) Сколько может быть различных КНФ у булевой функции?

г) Сколько может быть различных СКНФ у булевой функции?

Варианты ответа:

1 - ноль или одна; 2 - ноль или бесконечно много; 3 - ноль или одна; 4 - одна; 5 - одна или бесконечно много.

4. В какой из нормальных форм (ДНФ, СДНФ, КНФ, СКНФ) находится данная формула булевой функции трех переменных f(x, y, z):

а) xVy&z; б) x&y&z; в) (xVy)&(xVШz); г) xVyVz; д) Шx&y&z V y&Шz; е) xVШy; ж) x&z.

5. Какая релейно-контактная схема соответствует функции проводимости f(x) = (xVy)&(xVШz)?

Ответы на контрольные вопросы

Тема 1

1. Да.

2. Если АВ.

3. Пустое множество.

4. Да. Например, множество целых чисел эквивалентно множеству четных чисел.

5. Мощность множества точек отрезка [0, 1] больше. Это множество имеет мощность континнуума, а множество натуральных чисел является счетным множеством.

Тема 2

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

2. Рефлексивного.

3. Для симметричного.

4. Для транзитивного.

5. Например, отношение параллельности прямых есть отношение эквивалентности. Пусть x и y - углы наклона прямых x и y с осью абсцисс. Тогда отношение = {x, y x y} есть отношение частичного порядка.

6. Функция может быть задана таблицей, формулой, рекурсивной процедурой, с помощью описания.

7. б).

Тема 3

1. б).

7. Нет. Только для неориентированного графа.

8. Нужно сложить все элементы матрицы и полученную сумму разделить на 2.

10. Нет.

11. а) и б).

12. Нет.

15. Да .

16. а), д)

17. г).

18. Нет.

19. Нет.

21. г).

22. n - 1.

23. Наименьшее - n - 1 (дерево), наибольшее - n( n - 1) 2 (полный граф).

24. Наименьшее - 0 (несвязный граф), наибольшее - n( n - 1) 2 (полный граф).

25. Нет.

27. Одну.

28. Нет.

29. Нахождение минимального пути.

30. Нахождение минимального пути.

31. Нахождение минимального остовного дерева.

32. Нахождение минимального остовного дерева.

33. Нахождение минимального остовного дерева.

34. Нахождение минимального остовного дерева.

Тема 4

1. а)22; б) 2n.

2. а).

3. а) бесконечно много; б) ноль или одна; в) бесконечно много; г) ноль или одна.

4. а)ДНФ; б)ДНФ, СДНФ, КНФ; в)КНФ; г)ДНФ, КНФ, СКНФ; д)ДНФ; е)ДНФ, КНФ; ж)ДНФ, КНФ.

11. а) и б).

Указания к выполнению лабораторных работ

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

Чтобы приступить к выполнению лабораторной работы необходимо запустить систему с помощью файла run.bat; выбрать в главном меню пункт "Обучающие программы"; указать раздел; выбрать пункт "Упражнения".

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

Лабораторная работа №1. Основные понятия. Ориентированные графы

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

Лабораторная работа №2. Основные понятия. Неориентированные графы

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

Лабораторная работа №3. Экстремальные пути в графах

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

Контрольные задания по курсу "Дискретная математика"

1. Раздел «Множества»

Вариант № 1

1. Фирма имеет 100 предприятий, причем каждое предприятие выпускает хотя бы одну продукцию вида А, В, С. Продукцию всех трех видов выпускают 10 предприятий, продукцию А и В - 18 предприятий, продукцию А и С - 15 предприятий, продукцию В и С - 21 предприятие. Число предприятий, выпускающих продукцию А равно числу предприятий, выпускающих продукцию В и равно числу предприятий, выпускающих продукцию С. Найти число всех предприятий.

2. Упростить: .

3. Является ли множество А = {1, 2, 3} подмножеством множества В = {{1}, {2, 3}}?

4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А В = С.

5. Эквивалентны ли множества A = {x: x2 - 8x + 15= 0} и B = {2, 3}?

Вариант № 2

1. В группе спортсменов 30 человек. Из них 20 занимаются плаванием, 18 - легкой атлетикой и 10 - лыжами. Плаванием и легкой атлетикой занимаются 11 человек, плаванием и лыжами - 8, легкой атлетикой и лыжами - 6 человек. Сколько спортсменов занимаются всеми тремя видами спорта?

2. Упростить: AЗ(AB).

3. В каком случае ААЗВ?

4. Нарисовать диаграмму Эйлера-Венна для множества .

5. Какое из множеств A = {1, 4, 9, 16, 25,…} и B = {1, 1/2, 1/4, 1/6, 1/8,…} имеет большую мощность?

Вариант № 3

1. В студенческой группе 20 человек. Из них 10 имеют оценку “отлично” по английскому языку, 8 - по математике, 7 - по физике, 4 - по английскому языку и по математике, 5 - по английскому языку и по физике, 4 - по математике и по физике, 3 - по английскому языку, по математике и по физике. Сколько студентов группе не имеют отличных оценок?

2. Упростить: (A\B) (A\B).

3. Найти все подмножества множества A= {1, 2, 3, 4).

4

4. Пусть An = {0, 1/2n}. Найти U An.

n=1

5. Доказать, что множества точек контуров всех треугольников эквивалентны.

Вариант № 4

1. В классе 20 человек. На экзаменах по истории, математике и литературе 10 учеников не получили ни одной пятерки, 6 учеников получили 5 по истории, 5 - по математике и 4 - по литературе; 2 - по истории и математике, 2 - по истории и литературе, 1 - по математике и литературе. Сколько учеников получили 5 по всем предметам?

2. Упростить: (AЗB) (AЗB).

3. Является ли множество А = {1, 2, 3} подмножеством множества В = {{1}, {2, 3}}?

4. Нарисовать диаграмму Эйлера-Венна для множества (А \ В) З С

5. Эквивалентны ли множества A = {2x, 0<x< } и B = {2n, n = 1, 2, …}?

Вариант № 5

1. В спортивном лагере 100 человек, занимающихся плаванием, легкой атлетикой и лыжами. Из них 10 занимаются и плаванием, и легкой атлетикой, и лыжами, 18 - плаванием и легкой атлетикой, 15 - плаванием и лыжами, 21 - легкой атлетикой и лыжами. Число спортсменов, занимающихся плаванием, равно числу спортсменов, занимающихся легкой атлетикой, и равно числу спортсменов, занимающихся лыжами. Найти это число.

2. Упростить: (AB) (AB).

3. Найти все подмножества множества A= {1, 2, 3, 4).

4. Нарисовать диаграмму Эйлера-Венна для множества (А \ В) С

5. Доказать, что множества точек контуров всех треугольников эквивалентны.

Вариант № 6

1. Группе студентов предложено три спецкурса: по мультимедиа, искусственному интеллекту и имитационному моделированию. 22 студента записались на спецкурс по мультимедиа, 18 - на спецкурс по искусственному интеллекту, 10 - на спецкурс по имитационному моделированию, 8 - на спецкурсы по мультимедиа и искусственному интеллекту, 15 - на спецкурсы по мультимедиа и имитационному моделированию, 7 - на спецкурсы по искусственному интеллекту и имитационному моделированию. 5 студентов записались на все три спецкурса. Сколько студентов в группе?

2. Верно или неверно равенство: (A \ B) (AЗB) = A?

3. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А В = С.

4. Нарисовать диаграмму Эйлера-Венна для множества (А \ В) (А \ С).

5. Эквивалентны ли множества A = {x: x2-8x+15= 0} и B = {2, 3}?

Вариант № 7

1. Во время сессии 24 студента группы должны сдать три зачета: по физике, математике и программированию. 20 студентов сдали зачет по физике, 10 - по математике, 5 - по программированию, 7 - по физике и математике, 3 - по физике и программированию, 2 - по математике и программированию. Сколько студентов сдали все три зачета?

2. Упростить: (AB) (AЗB).

3. Доказать, что множество точек A= {(x, y): y = x, -, - 1 x 1} несчетно.

4. Нарисовать диаграмму Эйлера-Венна для множества (А \ В) С.

5. Эквивалентны ли множества A = {y: y = x3, 1< x <2} и B = {y: y = 3x, 3< x < }?

Вариант № 8

В группе переводчиков 15 человек владеет английским языком, 19 - французским, 8 - немецким. 9 переводчиков владеют английским и французским языком, 7 - английским и немецким, 6 - французским и немецким. 4 переводчика владеют всеми тремя языками. Сколько переводчиков в группе?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В С) = (А \ В) С?

3. В каком случае ААЗВ?

4. Нарисовать диаграмму Эйлера-Венна для множества () \ (A B).

5. Эквивалентны ли множества A = {x: x2 -3x + 2 = 0} и B = {1, 3}?

Вариант № 9

1. Опрос группы студентов показал, что 70% из них любят ходить в кино, 60% в театр, 30% на концерты. В кино и театр ходят 40% студентов, в кино и на концерты - 20%, в театр и на концерты - 10%. Сколько студентов (в %) ходят в кино, театр и на концерты?

2. Верно или неверно равенство: (AЗB) З (A В) = В?

3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Нарисовать диаграмму Эйлера-Венна для множества А \ (В ЗС).

5. Эквивалентны ли множества A = {x: x3 - 1 = 0} и B = {x: x2 - 3x + 2 = 0}?

Вариант № 10

1. В группе 20 учеников. После медицинского осмотра на дополнительное обследование 14 учеников были направлены к терапевту, 6 - к окулисту, 5 - к ортопеду. К терапевту и окулисту были направлены 3 ученика, к терапевту и ортопеду -3, к окулисту и ортопеду - 2. Сколько учеников были направлены к терапевту, окулисту и ортопеду?

2. Упростить: () \ (A B).

3. Нарисовать диаграмму Эйлера-Венна для множества (A З B) (C \ (A B)).

4. Найти все подмножества множества A= {a, b, c, d}.

5. Эквивалентны ли множества A = {(x, y): y = lnx, 0 < x < } и B = {(x, y): y = sinx, - <x < }?

Вариант № 11

1. При обследовании рынка спроса инспектор указал в опросном листе следующие данные. Из 1000 опрошенных 811 покупают жевательную резинку "Дирол", 752 - "Орбит" , 418 - "Стиморол", 570 - "Дирол" и "Орбит", 356 - "Дирол" и "Стиморол", 348 - "Орбит" и "Стиморол", 297 - все виды жевательной резинки. Показать, что инспектор ошибся.

2. Упростить: (B \ (AB)).

3. Придумать пример множеств А, В, С, так, чтобы выполнялось равенство: А В = С, причем А - конечное множество, В и С - счетные множества.

4. Нарисовать диаграмму Эйлера-Венна для множества A З (B C ) .

5. Пусть A - множество целых чисел, а B - множество четных чисел. Какие из следующих отношений справедливы: а) A =B; б) A B; в) A B; г) A B; д) A B; е) A B.

Вариант № 12

1. Всем участникам автопробега не повезло. 12 из них увязли в песке - пришлось толкать машину, 8 понадобилась замена колеса, у шестерых перегрелся мотор, пятеро и толкали машину и меняли колесо, четверо толкали машину и остужали мотор, трое меняли колесо и остужали мотор. Одному пришлось испытать все виды неполадок. Сколько было участников?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В ЗС) = (А \В) ЗС?

3. Доказать, что множество точек A = {y: y = 2n, n = 1, 2, …} счетно.

4. Нарисовать диаграмму Эйлера-Венна для множества (А \В) ЗС.

5. Эквивалентны ли множества A = {(x, y): y = x3, 1< x <2} и B = {(x, y): y = 3x, 3< x < }?

Вариант № 13

1. Из 10 участников ансамбля шестеро умеют играть на гитаре, пятеро - на ударных инструментах, пятеро - на духовых. Двумя инструментами владеют: гитарой и ударными - трое, ударными и духовыми - двое, гитарой и духовыми - четверо. Один человек играет на всех трех инструментах. Остальные участники ансамбля только поют. Сколько певцов в ансамбле?

2. Верно или неверно равенство: ЗС) = ЗС ЗС ?

3. Записать решение системы неравенств

x-2 > 0

x-5 < 0

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

4. Нарисовать диаграмму Эйлера-Венна для множества З(B C ) .

5. Доказать, что множества A = {(x, y): y = x3, 1< x <2} и B = {y: y = 3x, 3< x < } эквивалентны.

Вариант № 14

1. В одной студенческой группе 10 человек могут работать на Дельфи, 10 - на Паскале, 6 - на Си. По два языка знают: 6 человек - Дельфи и Паскаль, 4 - Паскаль и Си, 3 - Дельфи и Си. Один человек знает все три языка. Сколько студентов в группе?

2. Верно или неверно соотношение: AЗЗC A В?

3. Придумать пример множеств А, В, С, так, чтобы выполнялось равенство: А В = С, причем А, В, и С - счетные множества.

4. Нарисовать диаграмму Эйлера-Венна для множества ЗС).

5. Эквивалентны ли множества A = {y: y = 3x, 0<x< } и B = {y: y = 3n, n = 1, 2, …}?

Вариант № 15

1. В день авиации на аэродроме всех желающих катали на самолете, планере, дельтаплане. На самолете прокатились 30 человек, на планере - 20, на дельтаплане - 15. И на самолете, и на планере каталось 10 человек, на самолете и дельтаплане - 12, На планере и дельтаплане - 5. Два человека прокатились и на самолете, и на планере, и на дельтаплане. Сколько было желающих прокатиться?

2. Верно или неверно равенство: (A B) \ A = B \ A ?

3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Нарисовать диаграмму Эйлера-Венна для множества ЗС ЗС.

5. Доказать, что множества A = {y: y = lnx, 0 < x < } и B = {y: y = sinx, - <x < } эквивалентны.

Вариант № 16

1. Все грибники вернулись домой с полными корзинами. У десятерых из них в корзинах были белые грибы, у восемнадцати - подберезовики, у двенадцати - лисички. Белые и подберезовики были в шести корзинах, белые и лисички - в четырех, Подберезовики и лисички - в пяти. Все три вида грибов были у двух грибников. Сколько было грибников?

2. Верно или неверно равенство: (A B) \ (AЗB) = AЗЗB?

3. Доказать, что множество точек A= {(x, y): y = x, -, - 1 x 1} несчетно.

4. Нарисовать диаграмму Эйлера-Венна для множества З (B C ) .

5. Пусть A - множество точек отрезка [0, 1], а B - множество всех точек числовой оси. Какие из следующих отношений справедливы: а) A =B; б) A B; в) A B; г) A B; д) A B; е) A B.

Вариант № 17

1. Все туристы взяли в поход консервы. Шесть человек взяли тушенку, пять - сгущенку, восемь - кашу (с мясом). У троих в рюкзаках была тушенка и сгущенка, у двоих - тушенка и каша, у троих - сгущенка и каша, и только в одном рюкзаке лежали все три вида консервов. Сколько было туристов?

2. Верно или неверно равенство: ЗС = С \ (С З (AB))?

3. Пусть A - множество решений уравнения x2 - 3x + 2 = 0. Записать это множество двумя различными способами.

4. Нарисовать диаграмму Эйлера-Венна для множества (B?C) \ A .

5. Эквивалентны ли множества A = {x: x2 -3x + 2 = 0} и B = {2, 3}?

Вариант № 18

1. Было опрошено 70 человек. В результате опроса выяснили, что 45 человек знают английский язык, 29 - немецкий и 9 - оба языка. Сколько человек из опрошенных не знает ни английского, ни немецкого языков?

2. Верно или неверно равенство: (A B) \ (AЗB) = AЗЗB?

3. Найти все подмножества множества A= {x, y, z}.

4. Нарисовать диаграмму Эйлера-Венна для множества ЗС.

5. Счетно ли множество {(x, y): y = 3x, 0<x< }?

Вариант № 19

1. В туристической группе 10 человек знают английский язык, 10 - итальянский, 6 - испанский. По два языка знают: 6 человек - английский и итальянский, 4 - английский и испанский, 3 - итальянский и испанский. Один человек знает все три языка. Сколько туристов в группе?

2. Упростить .

3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Нарисовать диаграмму Эйлера-Венна для множества С \ (С З (AB)).

5. Эквивалентны ли множества A = { 2n, n = 1, 2, …} и B = {n2, n = 1, 2, …}?

Вариант № 20

1. Предприятие объявило набор рабочих на должности токаря, слесаря и сварщика. В отдел кадров обратились 25 человек. Из них 10 человек владели профессией токаря, 15 - слесаря, 12 - сварщика. Профессией и токаря и слесаря владели 6 человек, и токаря, и сварщика - 5 человек, и слесаря и сварщика - 3 человека. Сколько человек владеют всеми тремя профессиями?

2. Верно или неверно равенство: \ = \ ?

3. Привести примеры множеств А, В и С , для которых одновременно выполняются равенства А В С = А и А З В З С = С.

4. Нарисовать диаграмму Эйлера-Венна для множества \ .

5. Можно ли построить взаимно-однозначное соответствие между множеством рациональных чисел отрезка [0, 1] и множеством рациональных чисел из этого интервала? Ответ обосновать.

Вариант № 21

1. Оказалось, что в группе туристов 15 человек были раньше во Франции, 19 - в Италии, 8 - в Германии. 9 туристов были во Франции и в Италии, 7 - во Франции и в Германии, 6 - и в Италии, и в Германии. 4 туриста были во всех трех странах. Сколько туристов были хотя бы в одной из трех стран?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В З С) = (А \ В) З--?

3. Привести примеры множеств А и В, для которых равенство В =

а) выполняется; б) не выполняется.

4. Нарисовать диаграмму Эйлера-Венна для множества А З (В ).

5. Найти мощность множества точек окружности с центром в точке (0, 0) и радиусом 1.

Вариант № 22

1. Группе студентов из 30 человек была предложена контрольная работа из трех задач. Первую задачу решили 15 студентов, вторую - 13, третью - 12. Первую и вторую задачи решили 7 человек, первую и третью - 6, вторую и третью - 5 человек. Все три задачи решили 2 студента. Сколько студентов из группы не решили ни одной задачи?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В С) = (А \ В) З ?

3. Привести пример двух бесконечных множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Нарисовать диаграмму Эйлера-Венна для множества А З В З .

5. Найти мощность множества точек гиперболы y = при x ( 3, ).

Вариант № 23

1. Анализ историй болезней группы из 20 детей показало, что 10 детей болели ветрянкой, 6 - корью, 5 - свинкой. Ветрянкой и корью болели 3 ребенка, ветрянкой и свинкой - 3, корью и свинкой - 2. Всеми тремя болезнями болел один ребенок. Сколько детей не болели ни одной из перечисленных болезней?

2. Верно или неверно равенство: ?С) = ЗЗ С?

3. Доказать, что множество точек A= {(x, y): y = x+1, - 1 x 1} несчетно.

4. Нарисовать диаграмму Эйлера-Венна для множества (BЗC) \ A .

5. Пусть A - множество точек отрезка [1, 2], а B - множество точек интервала (0, 3). Какие из следующих отношений справедливы: а) A =B; б) A B; в) A B; г) A B; д) A B; е) A B.

Вариант № 24

1. В книжный киоск привезли для продажи 100 книг Пушкина, Лермонтова и Тургенева. Книги Пушкина купили 60 человек, книги Лермонтова - 50, книги Тургенева - 30 человек. Книги Пушкина и Лермонтова купили 40 человек, книги Пушкина и Тургенева - 20, книги Лермонтова и Тургенева - 10 человек. Пять человек купили книги всех трех писателей. Сколько человек не купили ни одной из перечисленных книг?

2. Верно или неверно равенство:\ = \ ?

3. Привести примеры множеств А, В и С таких, что равенство А В С = С

а) справедливо; б) несправедливо.

4. Нарисовать диаграмму Эйлера-Венна для множества \ .

5. Можно ли построить взаимно-однозначное соответствие между множеством натуральных чисел N и множеством действительных чисел отрезка [0, 1]? Ответ обосновать.

Вариант № 25

1. Группа научных работников состоит из 100 человек. Из них 70 человек владеют английским языком, 50 - немецким, 40 - французским, 30 - английским и немецким, 25 - английским и французским, 15 - французским и немецким. Хотя бы один язык знает каждый научный работник. Сколько человек владеют всеми тремя языками?

2. Упростить: (A \ (A?B)) В.

3. Привести примеры множеств А, В и С так, чтобы A B, В С.

4. Нарисовать диаграмму Эйлера-Венна для множества \ .

5. Можно ли утверждать, что множество всех положительных пятизначных чисел счетно? Ответ обосновать.

Вариант № 26

1. На курсы иностранных языков записалось 100 человек. Оказалось, что 70 человек будут изучать английский язык, 60 человек - французский и 30 человек - немецкий. Английский и французский собираются изучать 40 человек, английский и немецкий - 20, французский и немецкий - 10. Сколько студентов будут изучать все три языка?

2. Упростить равенство: (A З С )\ (С З (A B)).

3. Привести пример двух различных бесконечных множеств А и В, таких, что мощность множества А равна мощности множества В.

4. Нарисовать диаграмму Эйлера-Венна для множества ЗС).

5. Эквивалентны ли множества A = {x: x3 - 1 = 0} и B = {x: x2 - 3x + 2 = 0}?

Вариант № 27

В команде бегунов десять спортсменов бегают на длинные дистанции, восемнадцать - на средние, двенадцать - на короткие. На длинные и средние дистанции бегают пять спортсменов, на средние и короткие - шесть. На длинные и короткие дистанции не бегает никто. Сколько бегунов в команде?

2. Верно или неверно равенство: С) = С?

3. В каком случае A B = А З--В?

4. Нарисовать диаграмму Эйлера-Венна для множества (BЗC ) .

5. Можно ли утверждать, что множество всех положительных чисел имеет меньшую мощность, чем множество всех действительных чисел? Ответ обосновать.

Вариант № 28

1. В студенческой группе 25 человек. Чтобы получить допуск на экзамен по данному курсу необходимо защитить курсовую работу, выполнить лабораторную работу и сдать зачет. 15 студентов защитили курсовую работу, 20 выполнили лабораторную работу, 17 сдали зачет. Защитили курсовую работу и выполнили лабораторную работу 12 человек. Защитили курсовую работу и сдали зачет 13 человек. Выполнили лабораторную работу и сдали зачет 16 человек. Сколько студентов допущено к экзамену?

2. Упростить: З ().

3. Привести пример двух бесконечных множеств А и В, таких, что мощность множества А меньше мощности множества В.

4. Нарисовать диаграмму Эйлера-Венна для множества \ .

5. Эквивалентны ли множество рациональных чисел отрезка [0, 1] и множество рациональных чисел из этого интервала? Ответ обосновать.

Вариант № 29

1. В классе 20 детей. Из них 10 дополнительно занимаются в музыкальной школе, 6 - теннисом, 5 - китайским языком. Музыкальную школу и занятия по теннису посещают три ребенка, музыкой и китайским языком занимаются трое, теннисом и китайским языком двое. Всеми тремя видами дополнительных занятий занимается один ребенок. Сколько детей не занимается ни одним из перечисленных занятий?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В С) = (А \В) З?

3. Доказать, что множество точек A = {y: y = 2n, n = 1, 2, …} счетно.

4. Нарисовать диаграмму Эйлера-Венна для множества A ЗЗB .

5. Эквивалентны ли множества A = {(x, y): y = x2, 1< x <2} и B = {(x, y): y = 2x, 3< x < }?

Вариант № 30

1. В цеху имеется 25 станков, которые могут выполнять три вида операций: А, В и С. Из них 10 станков выполняют операцию А, 15 - В, 12 - С. Операции А и В могут быть выполнены на 6 станках, А и С - на 5, В и С - на 3 станках. Сколько станков могут выполнять все три операции?

2. Верно или неверно равенство: \ = \ ?

3. Привести примеры множеств А, В и С , для которых одновременно выполняются равенства А В С = А и А З В З С = С.

4. Нарисовать диаграмму Эйлера-Венна для множества ЗС.

5. Можно ли построить взаимно-однозначное соответствие между множеством действительных чисел отрезка [0, 1] и множеством действительных чисел интервала (0, 1)? Ответ обосновать.

2. Раздел «Отношения. Функции»

Вариант № 1

1. Задано бинарное отношение r--= {<1, 1>, <1, 3>, <3, 1>, <3, 4>, <4, 3>}.

Найти D(r), R(r),--rr,--r---1.-- Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не рефлексивного, не симметричного и транзитивного.

3. Дана функция f(x) = x2 + ex, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 2

1. Задано бинарное отношение r = {<1, 3>, <3, 1>, <3, 4>, <4, 3>, <4, 4>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение ? рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не симметричного, но рефлексивного и транзитивного.

3. Дана функция f(x) = x2 + e-x, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 3

1. Задано бинарное отношение r = {<2, 2>, <2, 3>, <3, 2>, <3, 4>, <4, 1>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение ? рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не транзитивного, но рефлексивного и симметричного.

3. Дана функция f(x) = x + ex, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 4

1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 3>, <4, 4>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x2 + y2 = 25?

3. Дана функция f(x) = x3 + ex, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 5

1. Задано бинарное отношение r = {<1, 2>, <2, 1>, <3, 4>, <4, 3>, <4, 4>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение ?? рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не симметричного, не рефлексивного и транзитивного.

3. Дана функция f(x) = x + e--x, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 6

1. Задано бинарное отношение r = {<2, 2>, <2, 3>, <3, 2>, <3, 1>, <4, 1>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения транзитивного, рефлексивного и антисимметричного.

3. Дана функция f(x) = x + ex, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 7

1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <2, 4>, <4, 2>}.

Найти D(r), R(r), rr,--r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения рефлексивного, симметричного и транзитивного.

3. Дана функция f(x) = x 2 +, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 8

1. Задано бинарное отношение r = {<2, 2>, <2, 3>, <3, 2>, <3, 4>, <4, 2>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения транзитивного, рефлексивного и антисимметричного.

3. Дана функция f(x) = x +, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 9

1. Задано бинарное отношение r = {<1, 2>, <2, 3>, <1, 3>, <1, 1>, <2, 2>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения транзитивного, рефлексивного и симметричного.

3. Дана функция f(x) = sinx +, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 10

1. Задано бинарное отношение r = {<1, 1>, <2, 3>, <1, 3>, <3, 1>, <3, 2>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x = 2y?

3. Дана функция f(x) = lnx +, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 11

1. Задано бинарное отношение r = {<1, 1>, <2, 4>, <1, 4>, <4, 1>, <4, 2>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не транзитивного, не рефлексивного и не симметричного.

3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R R и являющейся сюръективной, инъективной, биективной.

Вариант № 12

1. Задано бинарное отношение r = {<1, 1>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x + y = 100?

3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R R и не являющейся сюръективной, инъективной, биективной.

Вариант № 13

1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 1>, <1, 3>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.

3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R R и являющейся сюръективной, но не инъективной.

Вариант № 14

1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <2, 1>, <2, 4>, <4, 2>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения рефлексивного, симметричного и транзитивного.

3. Дана функция f(x) = x 2, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 15

1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <2, 4>, <4, 2>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

2. Привести пример отношения эквивалентности.

3. Дана функция f(x) = x 2 +, отображающая множество действительных чисел R во множество действительных чисел, R R. Является ли эта функция сюръективной, инъективной, биективной? Почему?

Вариант № 16

1. Задано бинарное отношение r = {<b, b>, <b, c>, <c, b>, <c, a>, <d, a>}.

Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?

...