КАРНАУ КАРТА, Вейча диаграмма

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

Способы нумерации клеток: а — нумерация клеток при n = 4; б — буквенная нумерация клеток.

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

могут располагаться также в клетках, место которых в таблице определяется дополнительными признаками. Эти признаки можно получить, например, исходя из К. к. для . Один из возможных способов нумерации клеток К. к. при показан на рис. а. В некоторых случаях наряду с рассмотренным способом используют также буквенный (рис. б), позволяющий выделять области К. к., в которых значение любой переменной остается постоянным. Буквенная нумерация оказывается удобной, например, при задании булевой ф-ции с помощью К. к., если эта ф-ция представлена совершенной ДНФ и конституэнты записаны в виде произведения переменных, а также при переходе от покрытия конфигурациями единиц, соответствующих элементарным произведениям, к аналитическому представлению при записи этих произведений в виде произведения переменных. В качестве примера на рис. б показано задание с помощью К. к. ф-ции , принимающей единичные значения на наборах с номерами 0—7, 8, 13, 15. На этом же рисунке показано наиболее экономное покрытие конфигурации единиц, соответствующей этой функции, правильными прямоугольниками, состоящими из клеток (0—7), (5, 7, 13, 15) и (8).

Переход от покрытия некоторой булевой ф-ции, заданной с помощью К. к., к ее аналитическому представлению в виде ДНФ связан с отысканием аналитических представлений элементарных произведений, соответствующих всем конфигурациям единиц покрытия и являющихся дизъюнктивными членами этой ДНФ. Такое элементарное произведение составляется из тех и только тех сомножителей , которые обращаются в единицу на всех наборах, охватываемых соответствующим покрытием. Например, показанному на рис. 6 покрытию соответствует ДНФ которая в данном случае является и минимальной.

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

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469]: Еремеев И. С., Подлипенский В. С. Магнитная техника автоматики и кибернетики. К., 1970 [библиогр. с. 399-404]; .