Так же решение контрольных, написание курсовых и рефератов по другим предметам.

logo

Решение контрольных по математике!!!

Связаться с нами

E-mail: matica@narod.ru

ICQ 229036787, ICQ 320619

 

Home

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

PDF Печать E-mail

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:

 
Яндекс.Метрика
Наверх