Специальность 230100.62 Контрольная работа по дискретной математике (стр. 16 )

а) ,

б) , где — множество цифр .

Задача 5. Три подруги Маша, Даша и Саша решили устроить праздник для своих однокурсников, и каждая составила свой список приглашенных. Оказалось, что у Маши и Саши в списках есть 5 общих друзей, у Даши и у Маши — трое, у Даши и у Саши — только двое, причем один из них есть и в Машином списке. Список Маши был самый длинный — 15 человек, в списке Даши — 7 человек, а у Саши — 10. Сколько гостей оказалось в общем списке? Сколько гостей есть в Машином списке, но нет в Дашином и Сашином?

Задача 6. Проверьте, являются ли отношение на множестве рефлексивным, антирефлексивным, симметричным, антисимметричным, транзитивным, эквивалентным, отношением порядка (строгого или нестрогого).

.

Укажите матрицу отношения и постройте граф.

Задача 7. Операция на множестве задана таблицей Кэли. Проверьте, является ли эта операция коммутативной, ассоциативной, существуют ли единичный и обратный элементы?

Вычислите .

Задача 8. Дана переключательная функция

А) .

Постройте таблицу истинности. Найдите СДНФ и СКНФ. Постройте полином Жегалкина. Проверьте, является ли функция монотонной. Проверьте, является ли функция линейной. Проверьте, является ли функция самодвойственной. Проверьте, является ли функция сохраняющей 0. Проверьте, является ли функция сохраняющей 1. Выясните, образует ли функционально полную систему. Если нет, то можно ли добавлением к функции получить функционально полную систему. Минимизируйте ДНФ и КНФ для с помощью карты Карно. Постройте соответствующие контактные схемы.

Б) . Минимизируйте ДНФ и КНФ для с помощью карты Карно.

Задача 9. Дан нагруженный граф.

А) Будем считать граф ненагруженным.

Определите степени всех вершин графа. Запишите матрицу смежности вершин. Укажите мосты и точки сочленения, если они есть. Проверьте, является ли граф эйлеровым, гамильтоновым, двудольным. Запишите соответствующие определения и критерии. Запишите какой-нибудь маршрут от до . Укажите какой-нибудь простой цикл. Постройте дерево, покрывающее граф.

Б) Будем считать граф нагруженным.

Постройте минимальное соединение графа и найдите его длину (вес). Используя алгоритм Дейкстры, найдите кратчайший путь от до .

ВОПРОСЫ К ЭКЗАМЕНУ

ДИСКРЕТНАЯ МАТЕМАТИКА

(заочники)

(СПЕЦИАЛЬНОСТЬ 230100. 2012 — 2013 УЧЕБНЫЙ ГОД)

Операции над множествами. Их свойства. Отношения на множествах. Бинарные отношения и способы их задания. Специальные виды бинарных отношений. Мощность конечного множества. Формула включений и исключений. Операции на множествах. Примеры. Бинарные операции. Виды бинарных операций. Булевы алгебры. Примеры. Определение графа. Части графа. Задание неориентированного графа с помощью матриц. Задание ориентированного графа с помощью матриц. Изоморфизм графов. Маршруты, цепи, циклы связного графа. Расстояния в графе. Диаметр и радиус графа. Центр графа и диаметральная цепь. Кратчайший путь на ненагруженном графе. Кратчайший путь на нагруженном графе. Алгоритм Дейкстры. Эйлеровы графы. Критерий эйлеровости. Гамильтоновы графы. Некоторые условия для гамильтоновости графов. Лес и деревья. Цикломатическое число графа. Задача о минимальном соединении. Алгоритм Крускала. Переключательные функции и способы их задания. Переключательные функции одной и двух переменных. Булевы формулы. Свойства булевых формул. Аналитическое представление переключательных функций. СДНФ и ДНФ. СКНФ и КНФ. Контактные схемы. Понятие о минимизации булевых функций. Карты Карно. Минимизация булевых функций с помощью карт Карно. Алгебра Жегалкина. Полиномы Жегалкина. Функционально полные системы. Примеры. Замкнутые классы. Примеры. Линейные функции. Замкнутость класса линейных функций. Двойственные и самодвойственные функции. Монотонные функции. Критерий монотонности булевых функций. Замкнутость класса монотонных функций. Теоремы Поста о функциональной полноте. Базис булевых функций.