Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число s-кубов которого было бы поменьше, а их размерность s - побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием. Например, для функции из (5) покрытие на рис. 23, а соответствует неминимальной форме y = x̅1x2 ∨ x1x̅2 ∨ x2x3,а покрытия на рис. 23, б и в - минимальным формам y = x̅1x2 ∨ x1x2 ∨ x2x3 и y = x̅1x2 ∨ x1x2 ∨ x1x3.
Отображение функции на n-мерном кубе наглядно и просто при n ≤ 3. Четырехмерный куб можно изобразить, как показано на
а б в
Рис. 214. Покрытие функции y = x̅1x2x̅3 ∨ x̅1x2x3 ∨ x1x̅2x̅3 ∨ x1x̅2x3 ∨ x1x2x3:
а – неминимальное; б, в – минимальное.
рис. 215, где отображены функция четырех переменных и ее минимальное покрытие, соответствующие выражению y = x1x̅3 ∨ x2x4 ∨ x̅1x3x4. Использование этого метода при n > 4 требует настолько сложных построений, что теряются все его преимущества.
Рис. 215. Отображение функции y = x1x̅3 ∨ x2x4 ∨ x̅1x3x4 на четырехмерном кубе
7. Карты Карно. В другом методе графического отображения булевых функций используются карты Карно, которые представляют собой специально организованные таблицы соответствия.
Столбцы и строки таблицы соответствуют всевозможным наборам значений не более двух переменных, причем эти наборы расположены
- 542 -
в таком порядке, что каждый последующий отличается от предыдущего значением только одной из переменных. Благодаря этому и соседние клетки таблицы по горизонтали и вертикали отличаются значением только одной переменной. Клетки, расположенные по краям таблицы, также считаются соседними и обладают этим свойством. Как и в обычных таблицах соответствия (1. 3), клетки наборов, на которых функция принимает значение 1, заполняются единицами (нули обычно не вписывают, им соответствуют пустые клетки). Для упрощения строки и столбцы, соответствующие значениям 1 для некоторой переменной, выделяются фигурной скобкой с обозначением этой переменной.
Между отображениями функции на n-мерном кубе и на карте Карно имеет место взаимно-однозначное соответствие. На карте
- 543 -
Карно s-кубу соответствует совокупность 2 соседних клеток, размещенных в строке, столбце, квадрате или прямоугольнике (с учетом соседства противоположных краев карты). Поэтому все положения, изложенные в (6), справедливы и для карт Карно.
Считывание минитермов с карты Карно осуществляется по простому правилу. Клетки, образующие s-куб, дают минитерм (n - s)-го ранга, в который входят те (n - s) переменные, которые сохраняют одинаковые значения на этом s-кубе, причем значениям 1 соответствуют сами переменные, а значениям 0 - их отрицания. Переменные, которые не сохраняют свои значения на s-кубе, в минитерме отсутствуют. Различные способы считывания приводят к различным представлениям функции в дизъюнктивной нормальной форме.
Использование карт Карно требует более простых построений по сравнению с отображением на n-мерном кубе, особенно в случае четырех переменных. Для отображения функций пяти переменных используются две карты Карно на четыре переменные, а для функций шести переменных - четыре таких карты. При дальнейшем, увеличении числа переменных карты Карно становятся практически непригодными.
Известные в литературе карты Вейча отличаются только другим порядком следования наборов значений переменных и обладают теми же свойствами, что и карты Карно.