Контрольная работа по дискретной математике, вариант 5.

подробное решение контрольной работы

Решение задач (Вариант 5) В задачах 1–10, а) требуется, используя правила де Моргана, привести к ДНФ выражение, содержащее конъюнкции, дизъюнкции и отрицания, и затем сократить ДНФ, если это возможно. Для этих задач есть точный алгоритм решения: “понижение” отрицания по правилам де Моргана до тех пор пока они не окажутся над одной переменной. После этого раскрываем скобки (используя естественные свойства конъюнкций, дизъюнкций и отрицаний, а также поглощение) и затем сокращаем ДНФ по правилу Блейка. Задача 5a. Привести выражение к ДНФ, а затем сократить ее (если это возможно). Задача 15б. Пусть имеется выражение . Требуется записать L в виде ДНФ, а затем перейти к СДНФ. Задача 25. Пусть требуется для функции f(x, y, z) = : а) составить таблицу истинности, б) написать для неё СДНФ или СКНФ (если это возможно), в) сократить СДНФ по карте Карно. б) составить СДНФ и СКНФ по полученной таблице. В соответствии с теорией разд. 4 СДНФ составляется по единицам таблицы истинности, причем если f(x, y, z) = 1, то если х = 0, в соответствующей конъюнкции в) составим теперь для данной функции карту Карно и попытаемся сократить её. Сначала составим таблицу: Задача 35. В задачах 41–50 требуется в данных наборах из 4 или 5 функций найти базисы и полные наборы функций (полные наборы – это наборы функций, содержащих базис). Задача 45. Пусть имеется набор функций: f1(x,y,z)=(xyz, f2(x,y,z)=xyx, f3(x,y,z)=y+xz, f4(x,y,z)=x+y, f5(x,y,z)=x~(yz). В задачах 51–60 требуется по данному ориентированному графу составить структурную матрицу, а по ней (методами булевой алгебры) найти все пути из вершины i в вершину j, а затем (отрицанием этих путей) найти все сечения между двумя указанными вершинами. Задача 55. Дан орграф. Имеется 4-ре ориентированных ребра: (3–2), (3–4), (2–5) и (1–6); i=3,j=1. В задачах 61–70 требуется, расставляя пометки в графе с заданным потоком с помощью алгоритма, описанного в теореме Форда – Фалкерсона, найти максимальный поток между вершиной с номером 1 и вершиной с максимальным номером. При этом если улучшенный поток окажется максимальным, то нужно указать то минимальное сечение, которому равен наш поток (если же улучшенный поток не окажется максимальным, то нужно снова его улучшать до тех пор, пока он не окажется максимальным). Задача 65. На рисунке (а) изображен граф с данными пропускными способностями ребер, при этом вершина номер 1 является “источником”, а вершина 6 – стоком. На рисунке (б) изображен тот же граф, но на ребрах его задан поток, удовлетворяющий свойствам 1–4, который надо либо увеличить, либо доказать, что он является максимальным.

-