Дискретная математика 05
1. Выясните, являются ли следующие формулы алгебры логики высказываний тождественно истинными формулами (тавтологиями):
А) 
;
Б) 
В) 
.
А) 
;
Б)
Составим таблицу истинности:
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Тогда 
В) 
.
Ответ: все три формулы являются тавтологиями.
2. Определите, верны ил следующие утверждения для любых множеств А, В, С:
А) 
;
Б) 
.
А)
Преобразуем левую часть:
Тождество верно
Б)
Это также тождество
3. Напишите СДНФ булевой функции, заданной следующей таблицей истинности, а затем упростите получившуюся ДНФ (используя логические эквивалентности)
|
Аргументы функции |
Значение функции | ||
|
Х1 |
Х2 |
Х3 |
У |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
Решение:
Выпишем СДНФ на основе наборов, на которых функция принимает единичные значения:
.
Упростим полученную формулу:
4. На каждом борту лодки должно сидеть по 4 человека. Сколькими способами можно выбрать команду для этой лодки, если есть 31 кандидат, причем 10 человек хотят сидеть на левом борту, 12 – на правом, а 9-ти безразлично где сидеть?
Решение:
5. Пусть множество А содержит n элементов, а некоторое его подмножество В содержит k элементов. Сколько существует множеств С, для которых 
?
Решение:
Множество С должно содержать р элементов, причем 
. Тогда
.
6. Пусть 
– отображение (функция) из множества А во множество В, а 
– соответствующее обратное отображение. Множества 
– произвольные, такие что 
. Какие из следующих равенств верны:
А) 
;
Б) 
;
В) 
;
Г) 
.
Решение:
А) ;
При этом каждому элементу из множества 
(т. е. элементу одного из множеств 
) будет ставиться в соответствие некоторый элемент множества В. Тогда очевидно, что 
.
Наоборот: пусть элемент принадлежит множеству 
, тогда он принадлежит 
или 
и для него существует некоторый элемент во множестве , образом которого он будет, т. е. 
, отсюда , ч. т. д.
Б) – неверно, как показывает пример:
В) – верно аналогично а)
Г) – неверно, как показывает пример: пусть
7. Пусть L – множество всех прямых на плоскости. Являются ли на этом множестве отношениями эквивалентности отношения:
А) отношение параллельности двух прямых;
Б) отношение перпендикулярности двух прямых?
Решение:
Отношение будет отношением эквивалентности, если оно рефлексивно, симметрично, транзитивно.
А) Отношение параллельности можно считать отношением эквивалентности: каждую прямую можно определить как параллельную себе (рефлексивность); если первая прямая параллельна второй, то и вторая будет параллельна первой (симметричность); две прямые параллельные третьей параллельны (транзитивность).
Б) Отношение перпендикулярности нельзя считать отношением эквивалентности: если прямая а перпендикулярна прямой b, а прямая b перпендикулярна прямой с, то прямые а и с будут параллельны (транзитивность не выполнена).
8. Сколько существует 6-значных чисел, в записи которых есть хотя бы одна четная цифра?
Решение:
Всего 6-значных чисел 1000000. Среди них чисел, в которых нет ни одной четной цифры будет 5*5*5*5*5*5=15625 чисел (каждую из цифр можно задать 5 способами, как одну из множества 1,3,5,7,9). Тогда 6-значных чисел, в записи которых есть хотя бы одна четная цифра, существует 1000000-15625=984375.
9. Дан связный граф. В графе 5 вершин, которые имеют степени 4,4,5,5,9. Может ли существовать граф с таким набором степеней вершин?
Решение:
Не может, так как общая сумма степеней вершин должна быть четным числом, а по условию 4+4+5+5+9=27 – нечетное.
10. В некоторой стране 20 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было по-прежнему проехать в каждый?
Решение:
Всего в городе будет 
дорог. Чтобы можно было проехать из одного города в другой, достаточно задать остов графа, т. е. из каждого города должна быть одна дорога. Остов для графа из 20 вершин содержит 19 ребер, т. е. можно закрыть на ремонт 190-19=171 дорог.
11. Дано дерево из 
вершин (
). Всегда ли в таком дереве найдется хотя бы одна вершина степени 2?
Решение:
Нет, как показывает пример:
В нем верхняя вершина имеет степень 3, а нижние – степень 1.
12. Дан полный двудольный граф 
. Существует ли в нем гамильтонов контур? Если да, то какова его длина?
Решение:
Гамильтонов контур – путь, содержащий каждую вершину ровно один раз. Граф является графом Дирака, так как степень каждой вершины равна 6/2=3=р/2 (р=6 – количество вершин). Тогда данный граф гамильтонов. Длина этого контура равна 6:
| < Предыдущая | Следующая > |
|---|
