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

БЕЗ ПАМЯТИ

Цель работы: освоение методики аналитического и экспериментального исследования конечного автомата без памяти с двоичными входами и выходами, его формального описания и исследования с помощью функций алгебры логики (ФАЛ); овладение навыками аналитического оперирования с ФАЛ (доказательство тождеств, построение СДНФ, ДНФ), реализация системы ФАЛ в форме логической сети.

Задание

1. Выполнить цикл упражнений по аналитическому преобразованию ФАЛ, доказательству тождеств на основе свойств элементарных ФАЛ, принципа двойственности, теоремы Де - Моргана, формул разложения.

2. Для заданного на ЭВМ (5хm) - полюсника с двоичными входами и выходами составить на основе эксперимента таблицу соответствия входных и выходных слов, являющуюся также таблицей истинности для системы m ФАЛ (здесь m – число студентов в бригаде).

3. Исследовать аргументы каждой из полученных ФАЛ на существенность (фиктивность). При обнаружении фиктивных аргументов записать эти ФАЛ как функции только существенных аргументов.

4. Образовать СДНФ и СКНФ, полученных в п. 3 ФАЛ. Упростить полученные ФАЛ с использованием операций поглощения и склеивания.

5. Упростить полученные ФАЛ с помощью карт Вейча.

6. Составить переключательные схемы и логические сети из логических элементов НЕ, ИЛИ, И, соответствующие каждой окончательной ДНФ, полученной в п. 4, и оценить количественно сложность каждой.

7. Составить отчет, отражающий выполнение п.п. 1 - 6. Ответить на контрольные вопросы.

1. Упражнения по аналитическим преобразованиям ФАЛ предусматривают использование свойств элементарных ФАЛ (коммутативность, ассоциативность, дистрибутивность, идемпотентность и др.); операций склеивания и поглощения; принципа двойственности; правил и теоремы Де - Моргана.

Конкретные задания индивидуального характера выдаются преподавателем. Для подготовки к их выполнению необходимо усвоить теоретический материал [ 2, с. 24-31].

Затем выполняются упражнения по приложению аналитического аппарата ФАЛ к анализу переключательных схем и решению логических задач (по указанию преподавателя).

2. Экспериментальное составление таблицы соответствия входных и выходных слов конечного автомата без памяти.

Каждому входу заданного на ЭВМ конечного автомата ставится в соответствие двоичная логическая переменная х_i (i = 1, 2,..., n), а каждому выходу – двоичная логическая переменная y_l (l = 1, 2,..., m), после чего составляется таблица, в которой перечисляются в порядке возрастания все n ‑ разрядные двоичные входные слова – j -е входные наборы (для n = 4 см. табл. 1.1). Здесь j есть десятичный номер соответствующего двоичного входного набора при чтении последнего сверху вниз.

Таблица 1.1

t

x1

x2

x3

x4

y1

y2

^· ^· ^·

ym

Эксперимент состоит в последовательном задании на входах "черного ящика" значений каждого входного слова < , , …, > с номером j (j = 0,1,2,..., 2 ⁿ –1), фиксации на выходах соответствующего выходного слова и заполнении нижней части табл. 1.1. Полученная таблица может рассматриваться как таблица истинности для системы из m n -местных ФАЛ:

(1.1)

3. Исследование существенности аргументов ФАЛ и их упрощение.

Факт существенности или фиктивности одного любого аргумента x_i ФАЛ устанавливается на основе анализа множества Т₀ и Т₁ этой функции после исключения из наборов i -го символа [2, с.13]. Если после его исключения в множествах Т₀ и Т₁ обнаружатся одинаковые, то переменная x_i – существенная, в противном случае - фиктивная.

Если обнаружено, что аргумент x_i фиктивный, то его можно исключить из рассмотрения, после чего таблица, задающая ФАЛ, (типа табл. 1.1) упрощается.

Необходимо исследовать существенность всех аргументов x_i для всех m ФАЛ, описывающих заданный конечный автомат. При обнаружении фиктивных аргументов у какой-либо ФАЛ следует составить для нее свою таблицу истинности, не содержащую фиктивных аргументов.

4. Образование СДНФ и СКНФ должно быть осуществлено для всех ФАЛ, описывающих заданный конечный автомат и упрощенных исключением фиктивных аргументов, на основе применения алгоритмов, описанных в работе [2, с. 36-37].

Полученные СДНФ приводят к эквивалентным ДНФ, применением возможных "склеиваний" и "поглощений" с помощью карт Вейча.

Карта Вейча (диаграмма Карно) – своеобразная форма табличного задания ФАЛ, когда множество всех наборов T представляется множеством 2ⁿ клеток некоторой прямоугольной таблицы (карты), внутри каждой из которых отмечается факт истинности ФАЛ на соответствующем наборе. Благодаря специальной разметке, устанавливающей связь клеток карты Вейча с наборами множества T₁, клетки (блоки клеток), соответствующие склеиваемым минтермам оказываются “соседними”, что существенно облегчает поиск и склеивание минтермов в целях упрощения ДНФ.

Для n = 2‚3‚4 карты Вейча с разметкой представлены на рис. 1.1.

Рис. 1.1.

Каждая клетка n – местной ФАЛ должна иметь “ n ” соседних, поэтому карта Вейча для n = 3 предусматривает объединение вертикальных границ карты (образно: наклеивание карты на цилиндр) для n = 4 – объединение горизонтальных границ (наклеивание на тор) для n = 5 в дополнение к вышеизложенному для каждого 16-клеточного блока “соседними” являются клетки с одинаковыми координатами.

Использование карт Вейча эффективно при ручной минимизации ДНФ для ФАЛ 3-х‚ 4-х и 5-ти аргументов. Пример при n = 4 представлен на рис. 1.2.

Рис. 1.2.

5. Переключательные схемы и логические сети, соответствующие полученным ранее упрощенным ДНФ, составляются на основе регламентированного порядка выполнения логических операций с применением переключателей и логических элементов НЕ, ИЛИ, И, возможно, многовходовых [2, с. 51-52].

6. Отчет по работе, составляемый один на бригаду, должен содержать задание, материалы по выполнению всех пунктов задания, причем по п.п. 3, 4, 5, 6 – индивидуальные для каждого члена бригады.

Контрольные вопросы:

1. Сколько существует различных n -местных ФАЛ?

2. Какие аргументы называются фиктивными?

3. Каков алгоритм проверки аргумента на фиктивность?

4. Что такое СДНФ, ДНФ (СКНФ, КНФ)?

5. Как построить СДНФ, СКНФ?

6. Каковы свойства элементарных ФАЛ?

7. В чем суть операции склеивания и поглощения?

8. Что такое переключательные функции и логические сети?

9. Как определяется сложность логической сети?

Задание для упражнений по аналитическому преобразованию ФАЛ

1. Доказать аналитически справедливость соотношений:

_

1) Х v ХY = X v Y;

_ _

2) Х v ХY = X v Y;

Дата добавления: 2017-01-13