Пример 9. Для данной булевой функции

Для данной булевой функции:

а) составить таблицу значений;

б) используя таблицу значений, составить функцию, двойственную к данной;

в) записать двойственную функцию в виде совершенной дизъюнктивной нормальной формы (СДНФ) и совершенной конъюнктивной нормальной формы (СКНФ).

Решение на примере функцииf(x,y,z) = (y→xz) (z½ ).

Пример 10.

Для данной булевой функции трёх переменных, заданной таблично, составить сокращенную ДНФ (привести как геометрическое, так и аналитическое решение).

Пример решения

x	y	z	f(x,y,z)

Пример 11.

С помощью алгоритма Прюфера восстановить по вектору дерево. Нарисовать диаграмму. Сделать проверку.

Пример решения. (1, 2, 2, 1, 4, 4, 4).

Пример 12.

По данной матрице смежности неориентированного графа

а) нарисовать диаграмму;

б) восстановить матрицу инцидентности;

в) определить степени всех вершин;

г) проверить, имеются ли среди вершин графа точки сочленения, а среди его рёбер – мосты.

Пример решения

№вершины