4

Работа 1. ИССЛЕДОВАНИЕ И ОПИСАНИЕ КОНЕЧНОГО АВТОМАТА

БЕЗ ПАМЯТИ

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

Задание

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

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

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

4. Образовать СДНФ и СКНФ, полученных в п. 3 ФАЛ.

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

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

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

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

Методические указания

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

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

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

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

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

Таблица 1.1

Переменная t есть десятичный номер соответствующего двоичного входного набора при чтении последнего сверху вниз.

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

(1.1)

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

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

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

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

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

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

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

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

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

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

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

6. Программная реализация заданных преподавателем элементарных ФАЛ выполняется на ПЭВМ с использованием рекомендованных программных средств и должна обеспечивать:

- ввод исходных данных с экрана монитора в режиме диалога;

- контроль исходных данных как по количеству, так и по составу (только 0 или 1);

- вывод на экран дисплея и на печать исходных данных и результатов счета в форме изображающих чисел ФАЛ.

Результаты работы программы должны быть прокомментированы.

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

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

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

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

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

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

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

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

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

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

9. Какие программные средства использовались при реализации системы ФАЛ на ЭВМ?

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