ТЕОРИЯ ГРАФОВ
Контрольные вопросы и упражнения
Четвертый этап
10. От логической схемы выражения, описывающего работу системы управления, можно непосредственно перейти к принципиальной схеме устройства, так как каждому условному изображению функции на логической схеме соответствует физический элемент, реализующий данную операцию и имеющий несколько вариантов принципиальной схемы в зависимости от элементной базы. Соединения между элементами задаются связями на логической схеме.
Рис. 2.1. Логическая схема
1. Для высказывания А: «Любые два треугольника подобны» сформулируйте отрицание и двойное отрицание. Какие из этих трех высказываний истинны?
2. Даны высказывания: «Я купил велосипед» (А); «Я путешествовал по России» (В) и «Я участвовал в соревнованиях по велосипеду» (С). Сформулируйте высказывания, соответствующие формулам:
А Ù В, А Ù В Ù С, А Ù`С, А Ù В, `В Ù`С.
3. Даны высказывания:
«Четырехугольник MNPQ – параллелограмм» (А);
«Диагонали четырехугольника MNPQ в точке пересечения делятся пополам» (В). Сформулируйте высказывания, соответствующие формулам:
А ® В, В ® А, `А, `В, `А ® В, `В ® А.
4. Составьте таблицы истинности для следующих формул:
F1 = X ® (Y Ú Z) и F2 = (X ®Y) Ú (X ® Z).
5. Покажите, что формулы являются тавтологиями:
F1 = X Ù Y ~ Y Ù X;
F2 = X Ú Y ~ Y Ú X;
F3 = ((X ® Y) Ù X) ® Y.
6. Докажите равносильность формул:
а) F1 = X Ù (Y Ú Z) и F2 = (X Ù Y) Ú (X Ù Z);
б) F1 = X Ú (Y Ù Z) и F2 = (X Ú Y) Ù (X Ú Z);
в) F1 = X Ú Y и F2 =`X Ù`Y;
г) F1 = X Ù Y и F2 =`X Ú`Y;
д) F1 = X ® (Y ® Z) и F2 = (X Ù Y) ® Z;
е) F1 = (X ® Y) Ù (X ® Z) и F2 = X ® (Y Ù Z).
7. Постройте совершенные ДНФ и КНФ функций:
x1 | x2, x1 ¯ x2, x1 ~ x2.
8. Запишите СДНФ и СКНФ для логической функции f(x1, х2, х3), принимающую значение 1 на наборах с номерами: 0, 3, 7. Определите, к каким классам функций относится эта функция.
9. Проверьте справедливость равенств:
а) х =`х Å 1;
б) х1 ® х2 =`х1 Ú x2 .
10. Составьте таблицу свойств логической функции двух переменных. Из таблицы выпишите все полные системы булевых функций.
11. Проверьте линейность логической функции f(x1, x2, x3), принимающей значение 1 на наборах с номерами: 0, 1, 5, 6.
12. Синтезируйте логические схемы функций из задач № 9, 12.
13. Найдите минимальную ДНФ функции f(х1, х2, х3, х4), принимающей значение 1 на наборах с номерами: 0, 1, 2, 5, 6, 7, 8, 12, 13.
14. Приведите примеры:
а) монотонной функции, которая одновременно была бы линейной;
б) самодвойственной функции, которая одновременно была бы линейной;
в) линейной и монотонной функций.
15. Покажите, что функции Шеффера и Пирса не являются ни линейными, ни монотонными, ни самодвойственными.
16. Докажите полноту системы функций å = {Ú, ~ , 0}, состоящей из дизъюнкции, эквивалентности и константы 0.
На практике часто бывает полезно изобразить некоторую ситуацию в виде рисунков, составленных из точек (вершин), представляющих основные ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Таким способом удобно представлять структуру системы, в которой вершины – это блоки, а ребра – связи между блоками. Такие рисунки известны под общим названием графов. Графы встречаются в разных областях под разными названиями: «структуры» в гражданском строительстве, «сети» в электротехнике, «социограммы» в социологии и экономике, «молекулярные структуры» в химии и т.д. Удобны графы и при исследовании систем методом пространства состояний. В этом случае вершины – состояния системы, процесса, ребра – действия, которые могут изменить состояние. При решении оптимизационных задач вершинами могут быть предполагаемые решения, ребрами – правила для их нахождения.
Начало теории графов как математической дисциплины было положено Эйлером в 1736 г., когда им была написана статья о Кенигсбергских мостах. Однако она была единственной в течение почти ста лет. Интерес к этой науке возродился около середины XIX в связи с развитием естественных наук (исследования электрических сетей, моделей кристаллов и структур молекул), формальной логики. Кроме того, оказалось, что многие математические головоломки могут быть сформулированы в терминах теории графов.
Последние 35-40 лет ознаменовали новый период интенсивных разработок теории графов. Появились новые области приложения: системы телекоммуникаций, биология, психология и другие.