Геометрическое и кубическое представление переключательных функций (до 90 минут)

Двоичный набор s ₁ s ₂… s_n (s_i =0 или s_i =1) можно рассматривать как n -мерный вектор (s ₁, s ₂,…, s_n), определяющий точку n -мерного векторного пространства. Множество наборов, на которых определена переключательная функция f (x ₁, x ₂, …, x_n), можно представить вершинами n -мерного куба (n -куба), в которых f =1.

Пример геометрического представления функции f (x ₁, x ₂, x ₃) = Ú {3, 4, 5, 6, 7}, принимающей значение 1 на двоичных наборах с номерами 3, 4, 5, 6 и 7, дан на рис.4.5,а.

На рис.12.1,а изображен трехмерный куб (3-куб), у которого отмечены вершины 011, 100, 101, 110 и 111, на которых рассматриваемая функция равна единице. Каждую вершину n -куба можно трактовать как 0-куб. Таким образом, мы можем представить функцию f (x ₁, x ₂, x ₃) = Ú{3, 4, 5, 6, 7} множестом 0-кубов: f (x ₁, x ₂, x ₃) = Ú{011, 100, 101, 110, 111}.

Два 0-куба, отличающиеся по одной координате, называются соседними. Пара соседних 0-кубов образует 1-куб. Если заменить координату, по которой различаются соседние 0-кубы, на символ X, то получим запись соответствующего 1-куба. Символ X означает, что соответствующая координата в записи соответствующего 1-куба может принимать любое значение – 0 или 1. Например, 0-кубы (011,111) соседние. Эти 0-кубы образуют 1-куб X11 (рис.12.1,б). Рассматриваемую функцию можно представить множеством 1-кубов: f (x ₁, x ₂, x ₃) = Ú{10X, 1X0, X11, 1X1, 11X }.

В общем случае пара соседних r -кубов образует (r +1)-куб. В записи r -куба используется r символов X для координат, принимающих любые значения. Очевидно, что r -куб имеет 2 ^r вершин. Для рассматриваемой функции вершины 100, 101, 110 и 111 образуют 2-куб 1XX (рис.12.1,б). Множество r -кубов, покрывающих все вершины, на которых f =1, называется кубическим покрытием f, или кубическим комплексом f.

Для рассматриваемого примера представление f в виде кубического комплекса имеет вид f (x ₁, x ₂, x ₃) = Ú{X11, 1XX}.

Легко установить соответствие между кубическим представленим булевых функций и их представлением в дизъюнктивной нормальной форме. Например, 1-куб X11, входящий в кубический комплекс f (x ₁, x ₂, x ₃), можно рассматривать как запись импликанты x ₂ x ₃.

Лекция №13.

МИНИМИЗАЦИЯ СТРУКТУРЫ КОНЕЧНОГО АВТОМАТА.

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

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

Методы абстрактной минимизации конечных автоматов

Теорема Мура

Текст лекции

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