Лабораторная работа 2. ОТКДС Ескин (лаба 1.1)

Посмотреть архив целиком

2



МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ).












Лабораторная работа по дисциплине:

"Основы теории конечных динамических систем".


"Исследование и описание

конечного аппарата без памяти".
















Студент: Полунин В.Ю.

Группа: 05–511.


Преподаватель: Ескин В.И.







Москва 2004 г.

Цель работы.


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


Задание:


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


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


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


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


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


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


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


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


Таблица истинности для системы m ФАЛ.


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

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


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

Таблица 1.1

t

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

X1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

X2

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

X3

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

X4

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

Y1

















Y2

































Ym


















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

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



В ходе эксперимента была получена таблица истинности при m = 2 и состоящая из 32-х наборов входных пятиразрядных слов (двоичные числа) на основе компьютерной программы и соответствующие значения логических функци1 для каждого входного набора. Результаты приведены в таблице №1.1.


Таблица №1.1. Таблица соответствия входных и выходных слов. Она же таблица истинности.

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

X1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

X2

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

X3

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

X4

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

X5

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

F8

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

F9

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1


Логическая функция F8 – Монахов В.С.

Логическая функция F9 – Полунин В.Ю.


Рассмотренной выше форма задания ФАЛ в виде табл. 1.1 по существу эквивалентна разбиению множества всех наборов входных пятизначных слов Т на два непересекающихся подмножества: Т0 – наборы, на которых рассматриваемая ФАЛ принимает значение 0, и Т1 – наборы, на которых она принимает значение 1; Т = T0T1, Т0Т1= . Для функции y=f(x1,x2,x3,x4,x5), заданной в табл. 1.1,


 

0

0

0

0

0

0

0

0

0

0

0

0

0

0

 

0

0

0

0

0

0

0

0

1

1

1

1

1

1

Т0:

0

0

0

0

1

1

1

1

0

0

1

1

1

1

 

0

0

1

1

0

0

1

1

1

1

0

0

1

1

 

0

1

0

1

0

1

0

1

0

1

0

1

0

1
















набора

0

1

2

3

4

5

6

7

10

11

12

13

14

15

 

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

 

1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

Т1:

0

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

 

0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

 

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1




















набора

8

9

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31



Проверка существенности (фиктивности) аргументов ФАЛ:


Все аргументы x1, x2,…, xn произвольной n-местной ФАЛ могут быть разделены на две группы: группу существенных аргументов и группу фиктивных аргументов. Аргумент xi функции f(x1,…, xi,…, xn) называется существенным, а функция существенно зависит от аргумента xi, если выполняется соотношение

(1.5)

в противном случае аргумент хi называется фиктивным, а функция f фиктивно зависит(по существу – не зависит) от аргумента хi.


Алгоритм проверки существенности (фиктивности) аргумента конкретной ФАЛ f(x1,…, xi,…,xn) предусматривает проверку возможности отделения множества Т0 от множества Т1 без помощи i-го символа в наборах и заключается в следующем:

  1. n-разрядные наборы, образующие множества Т0 и Т1, выписываются в виде двух столбцов

  1. Из всех n-разрядных наборов множеств Т0 и Т1 исключается i-й символ.

  2. Анализируются полученные множества (n–1)-разрядных наборов T Т; если в этих множествах возникли одинаковые наборы, то это значит, что разделить исходные множества Т0 и Т1 без помощи i-го символа в наборах нельзя, и, следовательно, аргумент хi является существенным, в противном случае хi–фиктивный аргумент.


Первый аргумент:



-

-

-

-

-

-

-

-

-

-

-

-

-

-


0

0

0

0

0

0

0

0

1

1

1

1

1

1

T0 =

0

0

0

0

1

1

1

1

0

0

1

1

1

1


0

0

1

1

0

0

1

1

1

1

0

0

1

1


0

1

0

1

0

1

0

1

0

1

0

1

0

1



-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-


1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

Т1 =

0

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1


0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1


0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1


Аргумент Х1 существенный.


Второй аргумент:



0

0

0

0

0

0

0

0

0

0

0

0

0

0


-

-

-

-

-

-

-

-

-

-

-

-

-

-

T0 =

0

0

0

0

1

1

1

1

0

0

1

1

1

1


0

0

1

1

0

0

1

1

1

1

0

0

1

1


0

1

0

1

0

1

0

1

0

1

0

1

0

1



0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1


-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

Т1 =

0

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1


0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1


0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1


Аргумент Х2 существенный


Третий аргумент.



0

0

0

0

0

0

0

0

0

0

0

0

0

0


0

0

0

0

0

0

0

0

1

1

1

1

1

1

T0 =

-

-

-

-

-

-

-

-

-

-

-

-

-

-


0

0

1

1

0

0

1

1

1

1

0

0

1

1


0

1

0

1

0

1

0

1

0

1

0

1

0

1



0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1


1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

Т1 =

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-


0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1


0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1


Аргумент Х3 существенный.


Четвертый аргумент:



0

0

0

0

0

0

0

0

0

0

0

0

0

0



0

0

0

0

0

0

0

0

1

1

1

1

1

1


T0 =

0

0

0

0

1

1

1

1

0

0

1

1

1

1



-

-

-

-

-

-

-

-

-

-

-

-

-

-



0

1

0

1

0

1

0

1

0

1

0

1

0

1



0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1


1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

Т1 =

0

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1


-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-


0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1


Аргумент Х4 существенный.


Пятый аргумент.



0

0

0

0

0

0

0

0

0

0

0

0

0

0


0

0

0

0

0

0

0

0

1

1

1

1

1

1

T0 =

0

0

0

0

1

1

1

1

0

0

1

1

1

1


0

0

1

1

0

0

1

1

1

1

0

0

1

1


-

-

-

-

-

-

-

-

-

-

-

-

-

-



0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1


1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

Т1 =

0

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1


0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1


-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-


Аргумент Х5 фиктивный.


Упрощенные наборы (без фиктивных аргументов) будут иметь вид:



0

0

0

0

0

0

0


X1

T0 =

0

0

0

0

1

1

1


X2


0

0

1

1

0

1

1


X3


0

1

0

1

1

0

1


X4











набора

0

2

4

6

10

12

14





0

1

1

1

1

1

1

1

1


X1

Т1 =

1

0

0

0

0

1

1

1

1


X2


0

0

0

1

1

0

0

1

1


X3


0

0

1

0

1

0

1

0

1


X4













набора

8

16

18

20

22

24

26

28

30





Совершенная дизъюнктивная нормальная форма.


Образовываем множество Т1 наборов, на которых функция принимает значение 1.



0

1

1

1

1

1

1

1

1

Т1 =

1

0

0

0

0

1

1

1

1


0

0

0

1

1

0

0

1

1


0

0

1

0

1

0

1

0

1











набора

8

16

18

20

22

24

26

28

30


Выписываем все минтерны максимального ранга, соответствующие наборам Т1:


F8(4) = X1X2X3X4;

F16(4) = X1X2X3X4;

F18(4) = X1X2X3X4;

F20(4) = X1X2X3X4;

F22(4) = X1X2X3X4;

F24(4) = X1X2X3X4;

F26(4) = X1X2X3X4;

F28(4) = X1X2X3X4;

F30(4) = X1X2X3X4;


f(X1X2X3X4) = F8(4) v F16(4) v F18(4) v F20(4) v F22(4) v F24(4) v F26(4) v F28(4) v F30(4) =


= x1x2x3x4 V x1x2x3x4 V x1x2x3x4 V x1x2x3x4V x1x2x3x4V x1x2x3x4 V


V x1x2x3x4V x1x2x3x4V x1x2x3x4


Карта Вейча (диаграмма Карно).


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

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




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

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


Преобразовываем полученную СДНФ при помощи карт Вейча.





X1

X1



X2

1

1

0

1

X4


1

1

0

0

X4


X2

1

1

0

0


1

1

0

0

X4



X3

X3

X3






На основе карты Вейча получаем преобразованную ФАЛ, эквивалентная ДНФ:


f(X1X2X3X4) = X1 V (X2X3 X4).


Переключательная схема:








Логическая схема:



Совершенная конъюнктивная нормальная форма.


Образовываем множество Т0 наборов, на которых функция принимает значение 0.



0

0

0

0

0

0

0

T0 =

0

0

0

0

1

1

1


0

0

1

1

0

1

1


0

1

0

1

1

0

1









набора

0

2

4

6

10

12

14


Ф31-0(4) = Ф31(4) = X1 v X2 v X3 v X4;

Ф31-2(4) = Ф29(4) = X1 v X2 v X3 vX4;

Ф31-4(4) = Ф27(4) = X1 v X2 vX3 v X4;

Ф31-6(4) = Ф25(4) = X1 v X2 vX3 vX4;

Ф31-10(4) = Ф21(4) = X1 vX2 v X3 vX4;

Ф31-12(4) = Ф19(4) = X1 vX2 vX3 v X4;

Ф31-14(4) = Ф19(4) = X1 vX2 vX3 vX4;


f(X1X2X3X4) = Ф31(4) * Ф29(4) * Ф27(4) * Ф25(4) * Ф21(4) * Ф19(4) =

= (X1 v X2 v X3 v X4) * (X1 v X2 v X3 vX4) * (X1 v X2 vX3 v X4) * (X1 v X2 vX3 vX4) *

(X1 vX2 v X3 vX4) * (X1 vX2 vX3 v X4) * (X1 vX2 vX3 v X4)



Преобразовываем полученную СКНФ при помощи карт Вейча.





X1

X1



X2

1

1

0

1

X4


1

1

0

0

X4


X2

1

1

0

0


1

1

0

0

X4



X3

X3

X3




Получаем функцию:

f(X1X2X3X4) = X1X3 V X1X3 X4 V X1X2X4.

Переводим в конъюнктивную форму:

Эквивалентная функция ДНФ:

f(X1X2X3X4) = (X1 v X3)(X1vX3 v X4)(X1 v X2 v X4).







Выводы:


В ходе лабораторной работы было выполнено:

- составление таблицы истинности для системы из m ФАЛ;

- исследование аргументов одной из полученных ФАЛ (F9) на существенность и фиктивность;

- образование СДНФ и СКНФ, полученных ранее ФАЛ;

- упрощение ФАЛ с помощью карт Вейча;

- составление переключательной схемы и логической сети из логических элементов (не, или, и), соответствующие каждой окончательной ДНФ, полученных в результате упрощения;

- количественная оценка сложности.


В результате освоены:

- методика экспериментального исследования конечного автомата без памяти (КАБП) с двоичными входами и выходами;

- формальное описание и исследование КАБП с помощью функций алгебры логики (ФАЛ);

- Также были получены навыки аналитического оперирования с ФАЛ (построение СДНФ, ДНФ) и реализации ФАЛ в форме логической сети.


В процессе анализа установлено:

- При исследовании аргументов полученной ФАЛ из пяти переменных переменная х5 -фиктивная, остальные (х1, х2, х3, х4) – существенные, в результате ФАЛ, как функция только существенных переменных, состоит из четырех переменных (х1, х2, х3, х4).

В результате образования СДНФ и ее упрощения с помощью карты Вейча была получена функция:


f(X1X2X3X4) = X1 V (X2X3 X4).


для которой была составлена переключательная схема и логическая сеть, при этом была проведена количественная оценка сложности:

и – 2

или - 5

не – 2

Всего – 9


В результате образования СКНФ и ее упрощения с помощью карты Вейча, была получена функция:


f(X1X2X3X4) = (X1 v X3)(X1vX2 v X4)(X1 v X2 v X3).

для которой была составлена переключательная схема и логическая сеть, при этом была проведена количественная оценка сложности:

и – 2

или - 1

не – 1

Всего – 4

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


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

Количество различных ФАЛ, зависящих от n аргументов, определяется числом различных способов, которыми можно заполнить нижнюю строку таблицы истинности элементами 0 и 1, и равно 2 (для n= 4 оно равно 216=65336).


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

Все аргументы x1, x2,…, xn произвольной n-местной ФАЛ могут быть разделены на две группы: группу существенных аргументов и группу фиктивных аргументов. Аргумент xi функции f(x1,…, xi,…, xn) называется существенным, а функция существенно зависит от аргумента xi, если выполняется соотношение

(1.5)

в противном случае аргумент хi называется фиктивным, а функция f фиктивно зависит(по существу – не зависит) от аргумента хi.


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

Алгоритм проверки существенности (фиктивности) аргумента конкретной ФАЛ f(x1,…, xi,…,xn) предусматривает проверку возможности отделения множества Т0 от множества Т1 без помощи i-го символа в наборах и заключается в следующем:

  1. n-разрядные наборы, образующие множества Т0 и Т1, выписываются в виде двух столбцов

  1. Из всех n-разрядных наборов множеств Т0 и Т1 исключается i-й символ.

3. Анализируются полученные множества (n–1)-разрядных наборов T Т; если в этих множествах возникли одинаковые наборы, то это значит, что разделить исходные множества Т0 и Т1 без помощи i-го символа в наборах нельзя, и, следовательно, аргумент хi является существенным, в противном случае хi–фиктивный аргумент.


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


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


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

Свойством коммутативности обладают следующие двухместные ФАЛ:

конъюнкция

; (2.1)

дизъюнкция

; (2.2)

функция Шеффера

; (2.3)

функция Вебба

; (2.4)

сложение по модулю 2

; (2.5)

эквиваленция

Ассоциативность функции fi означает допустимость изменения порядка выполнения однотипных операций

сочетательный закон.

Свойством ассоциативности обладают следующие двухместные ФАЛ:

конъюнкция

; (2.7)

дизъюнкция

; (2.8)

сложение по модулю 2

; (2.9)

эквиваленция

; (2.10)


Представляет интерес применение по отношению к двухместным ФАЛ операций отождествления аргументов f(х,х) и переименования аргументов f(,x); f(x,); f(x,0); f(0,x); f(x,1); f(1,x), предусматриваемых при суперпозиции. Ниже приводится перечень соответствующих формул для всех элементарных ФАЛ, доказательство их предлагается выполнить самостоятельно:

Дистрибутивность функции fi относительно функции fj означает допустимость изменения порядка выполнения разнотипных операций в форме

распределительный закон.

Среди двухместных ФАЛ свойством дистрибутивности обладают: конъюнкция относительно дизъюнкции

; (2. 16)

дизъюнкция относительно конъюнкции

; (2.17)

конъюнкция относительно сложения по модулю 2

. (2.18)



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


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


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


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


 Здесь и далее принимаем, что при отсутствии указаний на приоритетность в порядке выполнения операций конъюнкция имеет преимущество (выполняется раньше) перед дизъюнкцией и сложением по модулю 2, это позволяет упростить запись в направлении уменьшения числа скобок.


Случайные файлы

Файл
comp.doc
122851.rtf
59457.rtf
110284.rtf
100003.rtf