Полный текст:
1. Проверить,
является ли тавтологией формула:
Решение.
Чтобы праверить является
ли данная формула тавтологией, упростим ее используя известные ссотношения , , , ,.
В результате получаем:
Следовательно, формула является
тавтологией.
2. Применяя
равносильные преобразования привести булеву функцию & к минимальной
KНФ.
Решение.
Поскольку , получаем
.
Имея в виду
соотношение , получаем
Поскольку , получаем
Поскольку и получаем .
Следовательно, минимальный КНФ функции равен .
3. Построить
конечный детерминированный автомат, минимизировать его, записать канонические
уравнения.
Решение.
Легко видеть, что функция y(t), кoтoрую нужно реализовать, принимает значения , когда и и , когда . Для того, чтобы в памяти автомата сохранилась информация о том, чему было равно
предыдущее входное
значение, помимо начального состояния , введём также состояния и . Если автомат находится в состоянии , это значит, что перед этим на входе была едийица, а если автомат находится в состоянии , это значит, что на входе был 0.
На рисунке представлен соответствующий автомат.
Легко заметить, что получившиеся автомат можно минимизировать.
Поскольку из вершины выходят ребра с теми же метками и того же назначения,
как из , следовательно можно отождествить вершины и следующим образом. удаляаем вешину вместе с выходящими из неё ребрами, а вершинупереименовываем в .
В результате получаем минимальный автомат.