Контрольная работа по "Дискретной математике"

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ФИНАНСОВЫЙ УНИВЕРСИТЕТ

ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ

 

 

 

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА

 

по дисциплине «Дискретная математика»

 

Вариант (5)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 1

Доказать равенство, используя свойства операций над множествами.

 

Решение:

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

Равенство доказано.

Задача 2

Пусть имеется множество A={1,2,3,4}, на этом множестве определены отношения RÍA2и PÍA2.

а) Определить, является ли отношение P рефлексивным.

б) Построить графические представления отношений R, P, P◦R.

в) Найти области определения и множества значений для отношений R, P, P◦R.

Отношения R, P:

R={(x,y)| x2³ 12y},  P={(x,y)| x+3yделится на 4}

 

Решение:

Множество А2 - декартово произведение, где A={1,2,3,4}, А= :

{(1,1),(1,2),(1,3),(1,4),

(2,1),(2,2),(2,3),(2,4),

(3,1),(3,2),(3,3),(3,4),

(4,1),(4,2),(4,3),(4,4)}

Бинарное отношение R на множестве А называется рефлексивным, если для всякого выполняется .

Бинарным отношением на множестве А2 называется любое подмножество декартова произведения множества А2. Бинарное отношение можно задать указанием всех пар, для которых это отношение выполняется, или графически. Соответственно:

R={(4,1)}, где  область определения ={4},множество значений ={1},

P={(1,1),(2,2),(3,3),(4,4)}, где  область определения ={1,2,3,4},множество значений ={1,2,3,4},

Отношение P: (x+3y делится на 4).

Это отношение является рефлексивным, т.к.

 

P◦R={(4,1)}, где  область определения ={4},множество значений ={1}.

Графические представления отношений R, P, S=P◦R:

Задача 3

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

1122345678900

 

Решение:

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

1) На первом месте единица: 1***, где на место *** выбираются 3 цифры  из набора 122345678900. Это могут быть либо 2 двойки и любая цифра из множества {1,3,4,5,6,7,8,9,0}, либо 2 нуля и любая цифра из множества {1,2,3,4,5,6,7,8,9}, либо 3 любые цифры из множества {1,2,3,4,5,6,7,8,9,0}. Всего таких чисел будет:

2) На первом месте двойка: 2***, где на место *** выбираются 3 цифры  из  набора 112345678900. Это могут быть либо 2 единицы и любая цифра из множества {2,3,4,5,6,7,8,9,0}, либо 2 нуля и любая цифра из множества {1,2,3,4,5,6,7,8,9}, либо 3 любые цифры из множества {1,2,3,4,5,6,7,8,9,0}. Всего таких чисел будет:

2) У чисел из этой группы  на первом месте стоят не единица, не двойка и не ноль, а одна из цифр множества {3,4,5,6,7,8,9}. Первую цифру можно выбрать 7 способами, оставшиеся 3 цифры выбираются из набора 1122345678900 с учетом того, что одна из цифр множества {3,4,5,6,7,8,9} уже выбрана. Это могут быть либо 2 единицы и любая цифра из множества {2,3,4,5,6,7,8,9,0} без той цифры из этого множества, которая стоит на первом месте; либо 2 двойки и любая цифра из множества {1,3,4,5,6,7,8,9,0} без той цифры из этого множества, которая стоит на первом месте; либо 2 нуля и любая цифра из множества {1,2,3,4,5,6,7,8,9} без той цифры из этого множества, которая стоит на первом месте, либо 3 любые цифры из множества {1,2,3,4,5,6,7,8,9,0} без той цифры из этого множества, которая стоит на первом месте. Всего таких чисел будет:

Всего четырехзначных чисел будет:

.

Задача 4

Управление имеет а предприятий, из них а1 предприятий выпускают продукцию А, а2 – продукцию B, a3 – продукцию С. Продукцию А и В выпускают а4 предприятий, В и С – а5 предприятий, А и С – а6 предприятий. Все виды продукции выпускают а7 предприятий. Сколько предприятий

а) выпускают ровно один вид продукции А, В или С?

б) не выпускают ни одного из указанных видов продукции?

а	а1	а2	а3	а4	а5	а6	а7
151	80	90	70	40	50	20	3

 

Решение:

а) Пусть А – предприятия, выпускающие продукцию А, В – предприятия, выпускающие продукцию В, С – предприятия, выпускающие продукцию С, D – предприятия, выпускающие ровно один вид продукции А, В или С. Тогда .

=80+90+70-2×40-2×50-2×20+3×3=29.

 

б) Пусть А – предприятия, выпускающие продукцию А, В – предприятия, выпускающие продукцию В, С – предприятия, выпускающие продукцию С, D – предприятия, выпускающие продукцию А, В или С. Тогда .

=80+90+70-40-50-20+3=133.

Тогда количество предприятий, не выпускающих ни одного из указанных видов продукции, будет равно:

151-133=18.

Задача5

Найти количество положительных трехзначных чисел:

а) не делящихся ни на одно из чисел a,b,c;

б) делящихся ровно на одно число из чисел a,b,c.

а	b	c
3	8	20

Решение:

а) Пусть U – множество всех положительных трехзначных чисел от 100 999; А – множество положительных трехзначных чисел, делящихся на 3; В – множество положительных трехзначных чисел, делящихся на 8; С – множество положительных трехзначных чисел, делящихся на 20; D – множество положительных трехзначных чисел, не делящихся на 3, 8, 20. Найдем мощности этих множеств.

• Мощность множества А. Так как трехзначные числа – это числа от 100 до 999, то мощность множества А будет равна разности мощности множества всех чисел от 1 до 999, делящихся на 3, и мощности множества чисел от 1 до 99, делящихся на 3. Количество чисел от 1 до 999, делящихся на 3:

Количество чисел от 1 до 99, делящихся на 3:

Значит, .

• Мощность множества В:

• Мощность множества С:

Найдем теперь мощности пересечений множеств.

• Сначала определим количество чисел, делящихся на 3 и на 8 (наименьшее общее кратное 24):

• Количество чисел, делящихся на 3 и на 20 (наименьшее общее кратное 60):

• Количество чисел, делящихся на 8 и на 20 (наименьшее общее кратное 40):

• Количество чисел, делящихся на 3, 8 и 20 (наименьшее общее кратное 120):

Мощность множества всех положительных трехзначных чисел от 100 до 999:

Тогда мощность множества положительных трехзначных чисел, не делящихся на 3, 8, 20:

Таким образом, 509 трехзначных положительных чисел не делятся ни на одно из чисел 3, 8, 20.

б) Количество чисел, делящихся только на 3:

Количество чисел, делящихся только на 8:

Количество чисел, делящихся только на 20:

Общее количество чисел:

256+61+16=333

Таким образом, 333 трехзначных положительных числа делятся ровно на одно число из чисел 3, 8 или 20.

 

Задача7

Граф G задан списком ребер (каждый элемент списка – это тройка чисел: номера двух смежных вершин и вес ребра, их соединяющего). Требуется

а) Нарисовать граф G.

в) Найти матрицу смежности графа G.

г) Обозначить ребра и найти матрицу инцидентности графа.

 

Список ребер с весами

(1,5,3), (1,6,6), (1,7,8), (2,5,9), (2,6,7), (2,7,2), (3,5,1), (3,6,3) (3,8,4), (4,7,6),      (4,8,1)

 

Решение:

Матрица смежности A(G):

 

Матрица инцидентности I(G), элементы которой задаются следующим образом:

В каждом столбце матрицы инцидентности только два элемента отличные от 0 (или один, если ребро является петлей).