Дискретная математика
1. Для заданных множеств U = {3, 4,
5, 7} A = {3, 4, 5} B = {4, 5} C = {3, 7}, найдите мощность следующих множеств:
.
Решение. Число элементов в конечном
множестве называется его мощностью. Поэтому найдём, из каких элементов состоят
множества и посчитаем количество элементов в них:
) , , . Значит, .
) , . Значит, .
) , . Значит, .
) , , . Значит, .
Ответ: , , , .
. Докажите тождество A \ (B Ç C) = (A \ B)
È (A \ C) с
помощью диаграмм Эйлера -Венна.
Решение. Построим множество,
соответствующее левой части заданного тождества (множества представлены
закрашенной областью):
Ç C A \ (B Ç C)
Построим множество, соответствующее
правой части заданного тождества (множества представлены закрашенной областью):
\ B A \ C (A \ B) È (A \ C)
Сравнивая закрашенные области,
видим, что A \ (B Ç
C)
и (A \ B) È (A \ C) на
диаграммах Эйлера-Венна изображаются одинаково, поэтому A \ (B Ç C) = (A \ B)
È (A \ C).
Ответ: тождество верно.
. Дано декартово произведение
множеств A´ D = {(a,1), (a, 3), (b,1), (b, 3),
(c,1), (c,1)}. Выпишите
множества A и D.
Решение. В условии задачи допущена
опечатка, так как по определению «Прямым произведением (или декартовым
произведением) двух непустых множеств X ´ Y называется множество всех упорядоченных пар
(x; y) , где xÎ X , y ÎY .».
Поэтому если декартово произведение содержит пары (a,1), (a, 3), то множество D
обязательно должно содержать элементы 1 и 3, но тогда в декартовом произведении
обязательно должны быть пары (c,1), (c,3). Значит, правильное условие:
Дано декартово произведение множеств
A´ D = {(a,1), (a, 3), (b,1), (b, 3),
(c,1), (c,3)}. Выпишите
множества A и D.
Так как в упорядоченных парах
декартового произведения на первых местах видим элементы a, b, c, то A = { a, b, c }. Так как
в упорядоченных парах декартового произведения на вторых местах видим элементы
1, 3, то D = { 1, 3}.
Ответ: A = { a,
b, c }, D = { 1, 3}.
4. Отображение f : R ® R действует по правилу .
Найдите образ f [- 3,1].
Решение. Пусть f - функция из
множества Х в множество Y . Тогда элементы уÎY называются образом x при отображении f.
Отрезок [-3,1] можно представить как
объединение двух множеств: [-3,1] = [-3,0] U
(0,1]. Отрезок [-3,0] отображается аналитическим выражением f (x) = x -1,
поэтому f ([-3,0]) = = [-4,-1]. Полуинтервал (0,1] отображается аналитическим
выражением f (x) = x2 +1, поэтому f ((0,1]) = (1,2]. Окончательно образ имеет
следующий вид f [-3,0]= [-4; -1] U (1;2]
.
Ответ: f [-3,0]= [-4; -1] U (1;2].
. Запишите следующее высказывание в
символической форме, обозначив за переменные элементарные высказывания, и
укажите соответствующую таблицу истинности.
«Неверно, что ветер дует тогда и
только тогда, когда идет дождь».
Решение. Выделим простые
(элементарные) высказывания «ветер дует», «идет дождь» и заменим их логическими
переменными X, Y соответственно. Тогда исходное высказывание символически
изображается . Его таблица истинности имеет вид:
|
|
|
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
Ответ:
. Определите вид логической формулы
(тавтология, противоречие или выполнимая) : (x® y) Ù ( y® z)
Ù ().
а) с помощью таблицы истинности.
Решение. Составим таблицу истинности
данной формулы:
x
|
y
|
z
|
x® y
|
y® z
|
|
|
(x® y) Ù ( y® z) Ù ()
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
Таблица истинности для противоречия содержит
только значения 0 в итоговом столбце. Значит, наша формула является
противоречием.
Ответ: противоречие.
. На одном заводе работают три друга: слесарь,
токарь и плотник. Их фамилии: Борисов, Иванов, Семенов. Профессии и фамилии
названы в произвольном порядке. У слесаря нет ни братьев, ни сестер, и он самый
младший из друзей. Семенов женат на сестре Борисова, он старше токаря. Назовите
фамилии слесаря, токаря и плотника.
Решение. Составим таблицу и отразим в ней
условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от
того, ложно или истинно соответствующее высказывание. Из условия задачи
следует, что у Борисова сестра, значит, он не слесарь; Семенов старше токаря,
значит, он не слесарь; получаем, что слесарь - Иванов; Семенов старше токаря,
значит, Семенов не токарь; получили, что токарь - Борисов, плотник - Семенов.
|
слесарь
|
токарь
|
плотник
|
Борисов
|
0
|
1
|
0
|
Иванов
|
1
|
0
|
0
|
Семенов
|
0
|
0
|
Ответ: слесарь - Иванов, токарь - Борисов, плотник
- Семенов.
. Нарисуйте граф G(V, E) с множеством вершин V = {a,
b, c, d, e, f , g, h} и ребер E = {ac,
ag, ah, bc, bh, cd, ch, eh, gh, fg}.
Решение.
. Даны графы G1 и G2. Выпишите для каждого графа
множества вершин и ребер. Определите степень каждой вершины. Найдите матрицы
смежности и инцидентности. Укажите для графа G1 какой-либо маршрут из вершины
1. Укажите для графа G2 подграфы.
логический
истинность граф матрица
Решение. 1) Выпишем множества вершин и ребер:
Для G1 V = {1, 2, 3, 4} и
E = {(1,1),
(1,4), (2,2), (2,3), (3,4)};
Для G2 V = {1, 2, 3} и
E = {(1,1),
(1,2), (1,3), (2,2), (3,2)}.
) Определим степени вершин:
Для G1 deg(1) = deg(2) = 3, deg(3)
= deg(4)
= 2;
Для G2 deg(11 ) = 1, deg(12 ) = 3,
deg(21) =
3,
deg(22 ) = 1, deg(31 ) =1, deg(32 ) = 1.
) Матрицы инцидентности:
) Матрицы смежности:
) Маршрут для G1: 1, 4, 3, 2
) Подграфы графа G2:
. Хор состоит из 10 участников.
Сколькими способами можно в течение трех дней выбрать по 6 участников, так,
чтобы каждый день были различные составы хора?
Решение. Посчитаем, сколькими
способами можно составить различные группы по 6 участников из 10 участников
хора: групп.
В первый день мы можем выбрать любую
из 210 групп, во второй день можем выбрать любую из 209 групп, в третий день
можно выбрать любую из 208 групп, тогда в течение трех дней имеется
210.209.208=9129120 возможностей.
Если же не учитывать порядок
выбранных групп, то возможностей будет
Ответ: 9129120 (или )