АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Анализ автоматов без памяти

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

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

Анализ автомата выполняется в такой последовательности:

1) введение переменных на выходе всех элементарных автоматов и составление системы логических уравнений для всех выходов;

2) решение системы логических уравнений и получение зависимости , где - двоичные аргументы, представляющие собой входные переменные анализируемого автомата; y – выходная функция, реализуемая автоматом;

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

4) составление таблицы функции .

Рассмотрим методику анализа автомата на примере.

Задача 16. Структурная схема дискретного автомата имеет вид, показанный на рис.38. Необходимо найти выходную функцию, реализуемую автоматом, в виде СДНФ и таблицы. Упростить структурную схему автомата, если это возможно.

Рис. 38

Будем анализировать автомат в последовательности, изложенной выше.

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

; ; ; ; .

2. Получим зависимость методом подстановки:

.

3. Преобразуем функцию в СДНФ:

4. Представим искомую функцию в виде таблицы.

Из выражения функции в виде СДНФ видно, что она принимает значение единицы на следующих наборах аргументов: 110, 100, 010. Таким образом, конституентами единицы являются и . Искомая функция представлена в табл.2.

Таблица 2

Из выражения для искомой функции видно, что она может быть упрощена. Так как то Тогда автомат будет иметь вид, показанный на рис.39.

Рис. 39

Из рисунка видно, что путём упрощения формулы удалось число элементарных автоматов уменьшить на два.

Методические рекомендации

Пример 1. Функция задана табл.3. Необходимо её представить в виде СДНФ и СКНФ, а затем найти минимальную форму.

Таблица 3

Функция принимает единичное значение на четырёх наборах аргументов: 010, 011, 110, 111. Тогда конституентами единицы, соответствующими данным наборам, будут , ,

, , а СДНФ запишется в следующем виде:

.

Функция принимает нулевые значения на наборах аргументов 000,

001, 100, 101. Тогда конституентами нуля будут а СКНФ запишется в виде

Теперь минимизируем функцию, записанную в виде СДНФ:

Сгруппируем конституенты и и вынесем за скобки общие члены. Тогда получим

В правильности полученного результата можно убедиться, анализируя табл.3. Из таблицы видно, что функция является тавтологией , и действительно,

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

Из формулы видно, что если то Функция также принимает нулевое значение, если и Она примет нулевое значение и при наборе аргументов так как на этом наборе будет тождественно равно 0. При наборе аргументов и функция принимает единичное значение. Действительно:

Функция представлена табл.4.

Таблица 4

Из таблицы видно, что функция имеет единичное значение на наборах 011 и 111, конституенты единицы на этих наборах будут и Тогда СДНФ функции запишется в виде

Пример 3. Двоичная функция трёх аргументов задана формулой

Необходимо представить функцию в виде СДНФ и в табличной форме.

На основании теоремы де Моргана Тогда Домножим первый дизъюнктивный член на а второй - на и раскроем скобки:

Так как СНДФ содержит четыре конституенты единицы, то функция принимает единичное значение также на следующих четырёх наборах: 110, 101, 100, 001. Данная функция представлена в виде табл.5.

Таблица 5

Дата добавления: 2015-09-27 | Просмотры: 881 | Нарушение авторских прав