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

1. Доказать .

Решение:

,

.

Следовательно, .

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

Решение:

,

.

3. Проверить, что отношение есть отношение эквивалентности.

Решение:

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

а) рефлексивность: , т.к. .

б) симметричность: означает, что . Следовательно, . т.к.

в) транзитивность: и означает, что и . Тогда . Следовательно, .

Аксиомы отношения эквивалентности выполнены, поэтому отношение является отношением эквивалентности.

4. Какую мощность имеет множество.

а) множество А всех конечных последовательностей из 0 и 1.

Множество А счетно, т.к. существует биекция с множеством натуральных чисел N: Всякому натуральному числу соответствует его единственная двоичная запись, представляющая из себя элемент множества А. С другой стороны, всякой конечной последовательности соответствует единственное натуральное число. По теореме Кантора-Бернштейна следует, что А и N равномощны.

б) множество В всех бесконечных последовательностей 0 и 1.

Всякой бесконечной последовательности 1 и 0 соответствует подмножество M в N:

.

Иными словами всякая бесконечная последовательность 0 и 1 есть характеристическая функция некоторого подмножества в N. Это соответствие является биекцией. Следовательно В равномощно с множеством подмножеств множества N. Множество подмножеств множества N имеет мощность континуум, следовательно В имеет мощность континуум.

5. Построить таблицу истинности формулы A=(P~ .

Решение:

P	Q	R	P~Q		(P~		(P~
Л	Л	Л	И	И	И	И	И
Л	Л	И	И	И	И	И	И
Л	И	Л	Л	Л	И	Л	Л
Л	И	И	Л	И	И	Л	Л
И	Л	Л	Л	И	И	И	И
И	Л	И	Л	И	И	И	И
И	И	Л	И	Л	Л	Л	И
И	И	И	И	И	И	Л	Л

6. Проверить, что формула является тавтологией.

~ .

Составим таблицу истинности формулы

P	Q			~
Л	Л	И	И	И
Л	И	И	И	И
И	Л	Л	Л	И
И	И	И	И	И

Формула тождественно истинна, следовательно является тавтологией.

7. Привести к СКНФ, СДНФ .

Получим СДНФ с помощью преобразований:

применяя формулу расщепления к двум последним элементарным конъюнкциям в полученной формуле, получаем СДНФ:

.

Получим СКНФ с помощью преобразований:

.

Чтобы получить СКНФ, применим формулу расщепления :

.

8. Составить схему из элементов x, y, z так, чтобы на выходе появлялся сигнал, если замкнуты хотя бы два контакта.

Решение:

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

Искомая схема соответствует булевой функции .

Для нее может быть построена следующая переключательная схема:

9. Записать отрицание формулы .

отрицание:

.

10. Сколько существует способов осветить комнату n лампочками, работающими независимо.

Решение:

Для каждой лампочки возможно два состояния: включена и не включена.

Всего число возможных вариантов включения лампочек равно .

11. Вычислить

а) .

б) .

12. Сколькими способами можно расставить 5 человек на 6 местах.

На каждое место можно поставить только одного человека и каждого человека только на одно место. Для первого человека мы можем выбрать место 6 способами. Для второго уже пятью и т.д. Всего получается способов.

13. Сколько существует четырехзначных чисел, у которых каждая следующая цифра больше предыдущих.

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

Получаем, что нам нужно просто посчитать число сочетаний 4 цифр из 9 (кроме 0).

Искомых чисел всего 105.

14. Найти наибольший коэффициент многочлена

Решение: Коэффициенты многочлены находятся с помощью формулы бинома Ньютона :

Чтобы найти наибольший из коэффициентов нужно их посчитать при всех k от 1 до 8:

1:

2:

3:

4:

5:

6:

7:

8:

9:

Получаем, что наибольший коэффициент многочлена равен 1792.

15. Доказать, что .

Решение:

.

16. Граф задан таблицей смежности:

а) Изобразить граф.

б) Найти матрицу инцидентности.

Пронумеруем ребра

Составим матрицу инцидентности:

в) в графе 10 ребер.

степени вершин:

1-ая: 4

2-ая: 3

3-ая: 1

4-ая: 1

5-ая: 2

6-ая: 2

7-ая: 2

8-ая: 5

4) Является ли граф Эйлеровым?

Чтобы граф был Эйлеровым, необходимо и достаточно. чтобы все степени вершин графа были четными. Для нашего графа это не так (например 8-ая вершина). Граф не является Эйлеровым.

5) Является ли граф Гамильтоновым?

Вершины 3 и 4 имеют степень 1. Поэтому гамильтонова цепь должна начинаться и заканчиваться в этих вершинах. Пусть вершина 3 начало. Тогда начало гамильтонова пути должно выглядить как 3-5-. Из вершины 5 можно попасть только в вершину 8, поэтому начало гамильтонова пути должно иметь вид 3-5-8-. Вершина 4 является завершающей вершиной предполагаемой гамильтоновой цепи. В нее можно попасть только из вершины 1. Получаем, что гамильтонова цепь должна иметь вид:

3-5-8-x-y-z-1-4, где x, y, z – вершины 2, 6 и 7.

получаем, что для существования гамильтонова пути, вершина 6 должна быть смежной либо с вершиной 2, либо с вершиной 7. Но это не так, следовательно граф не является гамильтоновым.

6) Является ли граф плоским?

Граф является плоским. Дадим соответствующее изображение графа: