Математический аппарат инженера

одну больше или меньше, то достаточно ограничиться попарным сравнением s-кубов одного класса с s-кубами соседнего класса.

На втором шаге при извлечении экстремалей и образовании минимального покрытия используется таблица покрытий. Ее строки соответствуют простым импликантам, а столбцы — конституентам единицы дизъюнктивной совершенной нормальной формы данной функции, которые представляются 0-кубами (вершинами) комплекса кубов. В клетку таблицы записывается метка, если простая импликанта в данной строке покрывает вершину в данном столбце. Экстремалям соответствуют те строки таблицы, которые содержат единственную метку в каком-либо столбце. Удаляя строки экстремалей и все столбцы, в которых эти строки имеют метки, получаем более простую таблицу. На основе этой таблицы выбираем простые импликанты, которые дополняют выделенное множество экстремалей до минимального покрытия функции.

Пример минимизации функции. Рассмотрим в качестве примера функцию четырех переменных у = f(х₁, х₂, х₃, х₄), заданную таблицей соответствия

Ей соответствует дизъюнктивная совершенная нормальная форма y = x̅₁x̅₂x₃x₄ ∨ x̅₁x₂x̅₃x̅₄ ∨ x̅₁x₂x̅₃x₄ ∨ x̅₁x₂x₃x₄ ∨ x₁x̅₂x̅₃x₄ ∨ x₁x̅₂x₃x₄ ∨ x₁₂x̅₃x̅₄ ∨ x₁x₂x̅₃x₄ . Множество 0-кубов после разбиения и упорядочения записывается следующим образом:

.

Объединяя кубы и отмечая те из них, которые покрываются кубами большей размерности, имеем:

; .

- 552 -

Простым импликантам соответствуют неотмеченные кубы.Составляем таблицу покрытия Z, которому соответствует сокращенная форма y = x̅₁x₃x₄ ∨ x̅₁x₂x₄ ∨ x̅₂x₃

x₄ ∨ x₁x̅₂x₄ ∨ x₁x̅₃x₄ ∨ x₂x₃ .

→ K0 ------- ↓ Z	0 1 0 0	0 0 1 1	0 1 0 1	1 0 0 1	1 1 0 0	0 1 1 1	1 0 1 1	1 1 0 1	Обозначения импликант
0 x 1 1		v				v			A
0 1 x 1			v			v			B
x 0 1 1		v					v		C
1 0 x 1				v			v		D
1 x 0 1				v				v	E
x 1 0 x	v		v		v			v	F

Извлекаем единственную экстремаль (х10х), которой соответствует минитерм x₂x̅₃ и упрощаем таблицу к виду:

→ K10 ------- ↓ Z1	0 0 1 1	1 0 0 1	0 1 1 1	1 0 1 1
0 x 1 1	v		v
0 1 x 1			v
x 0 1 1	v			v
1 0 x 1		v		v
1 x 0 1		v

В качестве дополнительных целесообразно выбрать кубы (0x11) и (10x1), так как они совместно с экстремалью (x10x) образуют покрытие функции, минимальная форма которой имеет вид: y = x̅₁x₃x₄ ∨ x₁x̅₂x₄ ∨ x₂x̅₃ . Соответствующее этой функции

- 553 -

минимальное покрытие иллюстрируется на четырехмерном кубе и на карте Карно.

@@@@@@@

6. Конечные автоматы

1. Основные определения. В контактных и логических схемах значения выходных переменных определяются только комбинацией значений переменных на входах в данный момент времени. Поэтому их называют комбинационными схемами. В более общем случае выходные переменные могут зависеть от значении входных переменных не только в данный момент, но и от их предыдущих значений. Иначе говоря, значения выходных переменных определяются последовательностью значений входных переменных, в связи, с чем схемы с такими свойствами называют последовательностными. Если входные и выходные переменные принимают значения из конечных алфавитов, то оба типа схем объединяются под названием конечные автоматы.

Пусть X_i - алфавит входной переменной х_i, а Y_i – алфавит выходной переменной y_i. Конечный автомат с n входами и m выходами характеризуется входным алфавитом Х = Х₁ × Х₂ × ... Х_n и выходным алфавитом Y = Y₁ × Y₂ × ... Y_m, причем символами входного алфавита служат слова x = (x₁, x₂, …, x_n) длины n, а символами выходного алфавита - слова y = (y₁, y₂, …, y_m) длины m, где x_i ∈ X_i и y_i ∈ Y_i. Особого внимания заслуживают конечные автоматы с двузначным структурным алфавитом, зависимости между входными и выходными переменными которых выражаются булевыми санкциями. Их значение обусловлено тем, что любая информация может быть представлена в двоичных кодах (двоично-десятичные коды чисел, телетайпный код в технике

- 564 -

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