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

Итак, любая дизъюнктивная нормальная форма отображается на n-мерном кубе совокупностью s-кубов, которые покрывают все вершины, соответствующие конституентам единицы (0-кубы). Справедливо и обратное утверждение: если некоторая совокупность s-кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим s-кубам минитермов является выражением данной функции в дизъюнктивной нормальной форме. Говорят, что такая совокупность s-кубов (или соответствующих им минитермов) образует покрытие функции.

Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число s-кубов которого было бы поменьше, а их размерность s - побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием. Например, для функции из (5) покрытие на рис. 23, а соответствует неминимальной форме y = x̅₁x₂ ∨ x₁x̅₂ ∨ x₂x₃,а покрытия на рис. 23, б и в - минимальным формам y = x̅₁x₂ ∨ x₁x₂ ∨ x₂x₃ и y = x̅₁x₂ ∨ x₁x₂ ∨ x₁x₃.

Отображение функции на n-мерном кубе наглядно и просто при n ≤ 3. Четырехмерный куб можно изобразить, как показано на

а б в

Рис. 214. Покрытие функции y = x̅₁x₂x̅₃ ∨ x̅₁x₂x₃ ∨ x₁x̅₂x̅₃ ∨ x₁x̅₂x₃ ∨ x₁x₂x₃:

а – неминимальное; б, в – минимальное.

рис. 215, где отображены функция четырех переменных и ее минимальное покрытие, соответствующие выражению y = x₁x̅₃ ∨ x₂x₄ ∨ x̅₁x₃x₄. Использование этого метода при n > 4 требует настолько сложных построений, что теряются все его преимущества.

Рис. 215. Отображение функции y = x₁x̅₃ ∨ x₂x₄ ∨ x̅₁x₃x₄ на четырехмерном кубе

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

Столбцы и строки таблицы соответствуют всевозможным наборам значений не более двух переменных, причем эти наборы расположены

- 542 -

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

Между отображениями функции на n-мерном кубе и на карте Карно имеет место взаимно-однозначное соответствие. На карте

- 543 -

Карно s-кубу соответствует совокупность 2 соседних клеток, размещенных в строке, столбце, квадрате или прямоугольнике (с учетом соседства противоположных краев карты). Поэтому все положения, изложенные в (6), справедливы и для карт Карно.

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

Использование карт Карно требует более простых построений по сравнению с отображением на n-мерном кубе, особенно в случае четырех переменных. Для отображения функций пяти переменных используются две карты Карно на четыре переменные, а для функций шести переменных - четыре таких карты. При дальнейшем, увеличении числа переменных карты Карно становятся практически непригодными.

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

8. Комплекс кубов. Несостоятельность графических методов при большом числе переменных компенсируется различными аналитическими методами представления булевых функций. Одним из таких представлений является комплекс кубов, использующий терминологию многомерного логического пространства в сочетании со специально разработанной символикой.

Комплекс кубов K(у) функции у = f(х₁, х₂, ..., х_n) определяется как объединение множеств K^s(у) всех ее s-кубов (s = 0, 1, .... n),

- 544 -