Выражение СДНФ из вышеприведенного примера можно упростить следующим способом

.

В случае сложных функций от большого числа переменных нахождение соседних выражений и их склеивание указанным выше способом становится затруднительным. Метод матриц Карно (диаграмм Вейча) облегчает процедуру склеивания благодаря тому, что соседние члены СДНФ или СКНФ, для которых возможно склеивание, размещаются на плоскости по соседству в географическом смысле. Для функций n переменных каждая составляющая канонической формы может иметь n соседей. Примеры матриц Карно приведены на рис. 3.2 - 3.4.

X₂ X₂ X₃

0 1 00 01 11 10

X₁ X₁

0 0 1 0 0 1 3 2

1 2 3 1 4 5 7 6

Рис.3.2 - Карты Карно для двух и трех переменных

X₃ X₄

X₁ X₂ 00 01 11 10

0 1 3 2

01 4 5 7 6

11 12 13 15 14

8 9 11 10

Рис. 3.3 - Карта Карно для четырех переменных

X₃ X₄ X₅

X₁ X₂ 000 001 011 010 110 111 101 100

00 0 1 3 2 6 7 5 4

01 8 9 11 10 14 15 13 12

11 24 25 27 26 30 31 29 28

10 16 17 19 18 22 23 21 20

Рис. 3.4 – Карта Карно для пяти переменных

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

Если в двух соседних клетках заполненной матрицы Карно находятся одинаковые символы (0 или 1), то соответствующие этим клеткам выражения можно склеивать, что равносильно устранению переменной, которая в рамках склеиваемой группы меняет значения. Соседние клетки, образующие пары, объединяются замкнутой линией для обозначения возможности склеивания. Возможные варианты склеивания для функций четырех переменных приведены на рис. 3.5.

Рассмотрим пример. Пусть из таблицы истинности получена СДНФ и она минимизируется аналитическим методом посредством склеивания:

Матрица Карно для данного случая будет иметь вид, показанный на рис. 3.6.

Рис. 3.5 - Варианты склеивание для логической функции четырех переменных.

00 01 11 10

00

1 0 0 1

01 0 0 0 0

11 0 0 0 0

1 0 0 1

10

Рис.3.6 - Карта Карно для примера

Методика минимизации логических функций с помощью карт Карно используется при автоматизированном проектировании узлов современных ЭВМ и разработке логических моделей объектов и процессов горно-металлургического производства.

Основные понятия теории конечных автоматов

Конечным автоматом называется система S={A, Q ,V, d, l}, в которой A={a₁,…,a_m}, Q={q₁,…q_n}, V={v₁,…,v_k} - конечные множества (алфавиты); a d : Q x A Þ Q и l : Q x A Þ V - функции, определенные на этих множествах. А называется входным алфавитом, V - выходным алфавитом, Q - алфавитом состояния; d – функцией переходов, l – функцией выходов. Если, кроме того, в автомате S выделено одно состояние, называемое начальным (будем считать, что это состояние q₀), то полученный автомат называется инициальным и обозначается ( S ,q₀ ) ; таким образом, по не инициальному автомату с n состояниями можно n различными способами определить инициальный автомат.

Поскольку функции d и l определены на конечных множествах, их можно задавать таблицами. Обычно две таблицы сводятся в одну таблицу d и l, называемую таблицей переходов - выходов автомата или автоматной таблицей.

Пример. Таблица 3.5 задает функции переходов и выходов для автомата с алфавитами A = { a₁, a₂, a₃}, Q = {q₁, q₂, q₃, q₄}, V = {v₁, v₂}.

Таблица 3.5 - Табличное задание конечного автомата

Еще один распространенный и наглядный способ задания автоматов – ориентированный мультиграф, называемый графом переходов или диаграммой переходов. Вершины графа соответствуют состояниям; если d (q_i, a_j) = q_k и l (q_i, a_j)= v_l, то из q_i в q_k ведет ребро, на котором написаны a_j и v_l . Граф переходов для таблицы 3.5 изображен на рис. 3.7. Кратные ребра не обязательны; например два ребра из q₂ в q₁ можно заменить одним, на котором будут написаны обе пары a₃/v₁ и a₂/v₁ . Для любого графа переходов в каждой вершине q_i выполнены следующие условия, которые называются условиями корректности:

1) для любой входной буквы a_i имеется ребро, выходящее из q_i , на котором написано a_j (условие полноты);

2) любая буква a_j встречается только на одном ребре, выходящем из q_i (условие непротиворечивости или детерминированности).

Для данного автомата S его функции d_S и l_S могут быть определены не только на множестве А всех выходных букв, но и на множестве А* всех входных слов. Для любого входного слова a = (a_j1, a _j2,..., a_jk); d( q_i, a_j1, a_j2,…, a_jk ) = d ( d( ...d( q_i, a_j1), a_j2) ,…, a_jk-₁), a_jk).

		a1/v1

Рис.3.7 - Граф конечного автомата

Другим способом это традиционное определение можно представить следующим образом:

1) d ( q_i , a_j ) задается автоматной таблицей S;

2) для любого слова a Î А* и любой буквы а_j

d( q_i, aa_j ) = d ( d( q_i, a ), a_j).