Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Минимизация систем булевых функций

 

Задача минимизации систем булевых функций хорошо исследована в ФПСБФ Рассмотрим один из наиболее распространенных методов минимизации.

Пусть задана система полностью определенных булевых функций в ДНФ, например:

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

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

Пример: пусть система булевых функций задана таблицей истинности. Найти МДНФ системы булевых функций.

Представим функции в СДНФ:

1. Построим полное множество А элементарных конъюнкций системы, указывая, какой функции принадлежит каждая конституэнта "1".

 

2. Построим СДНФ функции , конституэнтами "1" которой являются все элементы множества А. Найдем СкДНФ функции .

Выполним все склеивания:

1-2:

2-3:

4-6:

5-6:

Если конституэнты единицы не принадлежат одной и той же функции системы, склеивание не производится.

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

3. Строим импликантную матрицу Квайна.

 
 

- ядро функции :

в данном случае ядро совпадает с МДНФ функции .

МДНФ системы булевых функций:

Недостаток метода: большая трудоемкость операций склеивания и поглощения с признаками.


Глава 9

Абстрактная теория автоматов

 

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

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

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

По способу формирования функции выхода выделяют 3 типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат.

Эти автоматы описываются системой уравнений:

автомат Мили: автомат Мура:

 

С-автомат:

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

- любому входному слову из букв (слову длиной ) соответствует выходное слово той же длины,

- двум входным словам, в которых первые букв совпадают, соответствуют выходные слова с совпадающими первыми буквами, если перед подачей входных слов, автомат находился в одном и том же состоянии.

 
 

Функции и , описывающие работу автомата Мили, можно задать с помощью таблиц переходов и выходов. По этим таблицам можно определить реакцию автомата на любое входное слово.

 

В таблице 1 приведены произвольная последовательность входных сигналов и соответствующие ей последовательности состояний и выходных сигналов автомата, заданного таблицей переходов и выходов.


Более наглядным является представление автоматов Мили с помощью графов. Граф автомата состоит из узлов (вершин) соединенных ветвями (ребрами). Узлы графа отождествляются с состояниями автомата, а ветви отмечаются входными сигналами, вызывающими переход автомата по данной ветви, и выходными сигналами, соответствующими такому переходу.

Два автомата, у которых совпадают как входные, так и выходные сигналы, называются эквивалентными. если для любого входного слова выходное слово одного автомата совпадает с выходным словом другого автомата.

Для любого автомата Мили можно построить эквивалентный автомат Мура и наоборот. Для этого:

1) поставим каждой паре автомата Мили состояние автомата Мура;

2) во множество состояний автомата Мура включим начальное состояние автомата Мили. Если автомат Мили имеет состояний и входных сигналов, то эквивалентный автомат Мура будет иметь состояний.

Из таблицы видно, что состояние автомата Мили совпадает с состояниями автомата Мура, т.е.

, ,

Значения функции выходов для эквивалентного автомата Мура определяются соотношением:

при

Для начального состояния значение выходного сигнала выбирается произвольно. Т.о. переходы и выходные сигналы эквивалентного автомата Мура определяются таблицей:

 
 

 

Задача перехода от автомата Мура к эквивалентному автомату Мили решается очень просто. Если и – функции переходов и выходов автомата Мура, то функции переходов и выходов эквивалентного автомата Мили определяются соотношениями:

;

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

Частичными автоматами называются автоматы, на входы которых некоторые последовательности сигналов никогда не подаются (запрещенные входные слова)

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

На абстрактном этапе автомат задается таблицами или графом или каким-нибудь другим способом. На структурном этапе автомат понимают как структурную схему, состоящую из набора простейших автоматов и ФПС логических элементов.

 

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...