Метод минимизирующих таблиц в синтезе одновыходных комбинационных автоматов. (до 45 минут)

В этом случае исходная логическая функция минимизируемого автомата должна быть задана как С.Д.Н.Ф.

Для этой ф-ии строят таблицу, содержащую возможную конъюнкцию переменных. Эта таблица 2ⁿ стор (n-число аргументов заданной функции) и 2^n-1 столбцов (сами переменные x₁,…,x_n рассматриваются,как конъюнкции в силу соотношений xL1=x).В качестве примера такой минимизации таблицы пусть будет таблица построенная для функций трех аргументов f(x₁,x₂,x₃,x₄).

x1	x2	x3	x1^x2	x1^x3	x2^x3	x1^x2^x3
x1	x2	x3-	x1^x2	x1^x3-	x2^x3-	x1^xx2^x3-
x1	x2-	x3	x1^x2-	x1^x3	x2-^x3	x1^x2^x3
x1	x2-	x3-	x1^x2-	x1^x3-	x2-^x3-	x1^x2-^x3-
x1-	x2	x3	x1-^x2	x1-^x3	x2^x3	x1-^x2^x3
x1-	x2	x3-	x1-^x2	x1-^x3-	x2^x3-	x1-^x2^x3-
x1-	x2-	x3	x1-^x2-	x1-^x3	x2-^x3	x1-^x2-^x3
x1-	x2-	x3-	x1-^x2-	x1-^x3-	x2-^x3-	x1-^x2-^x3-

Порядок применения минимизирующей таблицы:

1. Вычеркиваем все строки таблицы, соответствующие тем конъюнкциям крайнего правого столбца, которые отсутствуют в заданной С.Д.Н.Ф.(так,если заданная логическая функция есть f(x₁,x₂,x₃,x₄)=x1x2x3Ux1x2^--x3Ux1x2^--x3-Ux1^--x2x3Ux1^--x2^--x3Ux1^--x2^--x3^--.То в построенной выше карте следует вычеркнуть 2-ю и 6-ю строки, т.к. в С.Д.Н.Ф нет конъюнкций x1x2x3^—b x1^—x2x3^--)4

2. В оставшихся строках каждого столбца зачеркиваются элементы одинаковые с теми,которые уже зачеркнуты в этом столбце(в рассматриваемом примере зачеркиваем все клетки 1-ого столбца; зачеркиваем все клетки 2-ого столбца, помеченного символом x2;в 3-ем столбце зачеркиваем все клетки с символом x3^--;в 4-ом столбце зачеркиваем все клетки с конъюнкцией x1x2;в 5-ом столбце будут вычеркнуты все клетки с конъюнкциями x1x3^—и x1^—x3^--; в 6-ом столбце зачеркиваем все клетки с конъюнкциями x2x3^--);

3. Из каждой не зачеркнутой строки таблицы выбирается одна конъюнкция с минимальным числом переменных (в нашем примере это конъюнкции x2^—и x3);

4. Записывают М.Д.Н.Ф как дизъюнкцию минимальных конъюнкций(в нашем случае имеем x2^—Ux3).

Замечание М.Д.Н.Ф получается из таблицы после исключения повторяющихся конъюнкций.

Метод минимизации картами Карно (до 45 минут)

В случае если логическая функция комбинационного автомата с одним выходом имеет число аргументов не выше 4-х,то для “ручной” минимизации целесообразно использовать карты Кано(диаграмма Вейга) прямоугольные таблицы соответствия (истинности) специального вида.

В качестве примера зададим картой Карно логическую функцию f(x₁,x₂,x₃,x₄)U₁F(2,6,12,13,14,15).

Имеем:

	x1	x1-
x2					x4-
					x4
x2-
					x4-
	x3-	x3	x3-

В этой карте внизу каждой клетки приводится картеж значений переменных и соответствующее значение логической переменной.

Семестр

Лекция №16.

АВТОМАТЫ И ФОРМАЛЬНЫЕ ЯЗЫКИ.

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

Классы языов по Хомскому

Текст лекции

Дата добавления: 2015-12-01