Основные правила преобразования формул алгебры логики

Аналитическое задание конечных автоматов

Автомат с пятью исходными состояниями

Пример 2. Автомат задан в виде табл. 1.5.4.

Таблица 1.5.4

В этом автомате два 1-эквивалентных класса.

Проведем разбиение состояний на эти классы (табл. 1.5.5.).

Таблица 1.5.5

При подаче β из состояние 1 автомат переходит в класс II, а из 3 и 4 в класс I, которые различимы при любом входном воздействии. В итоге получим таблицу разбиения (табл. 1.5.6).

Таблица 1.5.6

Дальнейшее разбиение невозможно. Таким образом, получена результирующая таблица состояний (табл. 1.5.7).

Таблица 1.5.7

Рассмотренные автоматы называются синхронными. В синхронных автоматах все состояния являются устойчивыми, так как в них автомат может находиться неограниченно долго, поскольку переход в следующее состояние возможен после подачи очередного тактового сигнала.

Существуют и асинхронные автоматы, в которых нет синхронизации или тактирующих сигналов. Асинхронный автомат задерживается неограниченно долго только в устойчивых состояниях. Устойчивое состояние характеризуется тем, что в следующий момент времени при продолжающем действовать управлении автомат вновь стремится к этому состоянию, т.е. если состояние x^* устойчивое при управлении u^*, то

.

Может оказаться, что при некотором управлении автомат постоянно будет неустойчивым, превращаясь в генератор. Ввиду ограничений в смене управлений асинхронный автомат менее управляем, чем синхронный.

Можно выделить следующие достоинства аналитического представления конечных автоматов:

· компактность записи по сравнению с табличным, графовым или матричным заданиями;

· простота моделирования работы конечных автоматов на ЭВМ;

· аналитическое представление необходимо при синтезе структуры автомата, так как при таком задании функции функциональных преобразователей выражаются через элементарные функции, реализуемыми простыми элементами.

Для формального описания цифровых управляющих устройств широко применяется аппарат алгебры логики.

Логической (булевой) переменной называется величина, которая может принимать только два значения.

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

Различные комбинации значения входных переменных функций называются наборами.

Функция является полностью заданной, если указаны ее значения для всех наборов. Сопоставляя каждому набору значение функции можно задать функцию с помощью таблицы, называемой таблицей истинности или таблицей соответствия.

Для аналитической записи функций алгебры логики можно использовать различные множества элементарных функций, требуется только, чтобы они составляли функционально полную систему, т.е. систему, с помощью которой можно записать любую функцию. Как правило, используют ОФПС (основная функционально полная система), включающую операции &, Ú и инверсию (табл. 1.6.1).

Для более глубокого изучения вопросов аналитического представления систем можно обратиться к Хаггарти Р. Дискретная математика для программистов. М.: Техностфера, 2012 – 400 с.

Таблица 1.6.1

x	y	x & y	x Ú y

Правила преобразования формул, предназначенных для упрощения выражений и перехода от табличного задания функции к аналитическому следующие: