Дискретная математика

/

1. Для заданных множеств U = {3, 4, 5, 7} A = {3, 4, 5} B = {4, 5} C = {3, 7}, найдите мощность следующих множеств: .

Решение. Число элементов в конечном множестве называется его мощностью. Поэтому найдём, из каких элементов состоят множества и посчитаем количество элементов в них:

1) , , . Значит, .

2) , . Значит, .

3) , . Значит, .

4) , , . Значит, .

Ответ: , , , .

2. Докажите тождество A (B З--C) = (A B) И--(A C) с помощью диаграмм Эйлера -Венна.

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

B З--C A (B З--C)

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

A B A C (A B) И--(A C)

Сравнивая закрашенные области, видим, что A (B З--C) и (A B) И--(A C) на диаграммах Эйлера-Венна изображаются одинаково, поэтому A (B З--C) = (A B) И--(A C).

Ответ: тождество верно.

3. Дано декартово произведение множеств 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].

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

«Неверно, что ветер дует тогда и только тогда, когда идет дождь».

Решение. Выделим простые (элементарные) высказывания «ветер дует», «идет дождь» и заменим их логическими переменными X, Y соответственно. Тогда исходное высказывание символически изображается . Его таблица истинности имеет вид:

Ответ:

6. Определите вид логической формулы (тавтология, противоречие или выполнимая) : (x®--y) Щ--( y®--z) Щ--().

а) с помощью таблицы истинности.

Решение. Составим таблицу истинности данной формулы:

Таблица истинности для противоречия содержит только значения 0 в итоговом столбце. Значит, наша формула является противоречием.

Ответ: противоречие.

6. На одном заводе работают три друга: слесарь, токарь и плотник. Их фамилии: Борисов, Иванов, Семенов. Профессии и фамилии названы в произвольном порядке. У слесаря нет ни братьев, ни сестер, и он самый младший из друзей. Семенов женат на сестре Борисова, он старше токаря. Назовите фамилии слесаря, токаря и плотника.

Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание. Из условия задачи следует, что у Борисова сестра, значит, он не слесарь; Семенов старше токаря, значит, он не слесарь; получаем, что слесарь - Иванов; Семенов старше токаря, значит, Семенов не токарь; получили, что токарь - Борисов, плотник - Семенов.

Ответ: слесарь - Иванов, токарь - Борисов, плотник - Семенов.

7. Нарисуйте граф G(V, E) с множеством вершин V =--{a, b, c, d, e, f , g, h}--и ребер E =--{ac, ag, ah, bc, bh, cd, ch, eh, gh, fg}.

Решение.

8. Даны графы 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)}.

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.

3) Матрицы инцидентности:

4) Матрицы смежности:

5) Маршрут для G1: 1, 4, 3, 2

6) Подграфы графа G2:

9. Хор состоит из 10 участников. Сколькими способами можно в течение трех дней выбрать по 6 участников, так, чтобы каждый день были различные составы хора?

Решение. Посчитаем, сколькими способами можно составить различные группы по 6 участников из 10 участников хора: групп.

В первый день мы можем выбрать любую из 210 групп, во второй день можем выбрать любую из 209 групп, в третий день можно выбрать любую из 208 групп, тогда в течение трех дней имеется 210.209.208=9129120 возможностей.

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

Ответ: 9129120 (или )