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