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

подробное решение

Вариант 3 В задачах 1–10, а) требуется, используя правила де Моргана, привести к ДНФ выражение, содержащее конъюнкции, дизъюнкции и отрицания, и затем сократить ДНФ, если это возможно. Для этих задач есть точный алгоритм решения: “понижение” отрицания по правилам де Моргана до тех пор пока они не окажутся над одной переменной. После этого раскрываем скобки (используя естественные свойства конъюнкций, дизъюнкций и отрицаний, а также поглощение) и затем сокращаем ДНФ по правилу Блейка. Задача 3а. Привести выражение к ДНФ, а затем сократить ее (если это возможно). Задача 13б. Пусть имеется выражение . Требуется записать L в виде ДНФ, а затем перейти к СДНФ. Задача 23. Пусть требуется для функции f(x, y, z) = ((x ~ z) + y) (x| yz): а) составить таблицу истинности, б) написать для неё СДНФ или СКНФ (если это возможно), в) сократить СДНФ по карте Карно. Задача 33. В задачах 41–50 требуется в данных наборах из 4 или 5 функций найти базисы и полные наборы функций (полные наборы – это наборы функций, содержащих базис). Задача 43. Пусть имеется набор функций: f1(x, y, z)=x(y~z), f2(x, y, z) = x (x+y), f3(x, y, z) = (x  z) y, f4(x, y, z) = . Задача 53. Дан орграф. Имеется 1 ориентированное ребро: (4–5); i=3, j=4. В задачах 61–70 требуется, расставляя пометки в графе с заданным потоком с помощью алгоритма, описанного в теореме Форда – Фалкерсона, найти максимальный поток между вершиной с номером 1 и вершиной с максимальным номером. При этом если улучшенный поток окажется максимальным, то нужно указать то минимальное сечение, которому равен наш поток (если же улучшенный поток не окажется максимальным, то нужно снова его улучшать до тех пор, пока он не окажется максимальным). Задача 63. На рисунке (а) изображен граф с данными пропускными способностями ребер, при этом вершина номер 1 является “источником”, а вершина 6 – стоком. На рисунке (б) изображен тот же граф, но на ребрах его задан поток, удовлетворяющий свойствам 1–4, который надо либо увеличить, либо доказать, что он является максимальным.

-