Карты Карно Сднф
1 Пример Карты Карно Карта. Представленных в виде СДНФ или СКНФ. Карты Карно предоставляют наглядный способ отыскания таких термов. Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N-мерному.
КАРТЫ КАРНО 2.6. КАРТЫ КАРНО Карты карно (схемы Вейча) это наглядное представление логической функции в виде карты, которая удобна для оптимизации. С каждой из сторон записывается значения комбинаций переменных так чтобы в зтом значении менялся один бит при переходе к следующему. Придумал Морис Карно (Maurice Karnaugh) в 1950 (Bell Labs) Примеры шаблонов карт Карно (для разного числа переменных): В каждой клетке карты карно находится значение функции, которую описывает эта карта на входном наборе соответствующем расположению клетки в карте. Пример заполнения (2 переменных) Собственно сам шаблон карты: x2 - 0 1 +-+-+ 0 x1 +-+-+ 1 +-+-+ Предположим мы хотим сделать карту для функции AND. Берем таблицу истинности: x2 x1 AND -+- 0 0 0 0 1 0 1 0 0 1 1 1 Вносим значения функции в клетки соответствующие входным наборам: x2=0, x1=0 = 0 x2 - 0 1 +-+-+ 0 0 x1 +-+-+ 1 +-+-+ x2=0, x1=1 = 0 x2 - 0 1 +-+-+ 0 0 x1 +-+-+ 1 0 +-+-+ x2=1, x1=0 = 0 x2 - 0 1 +-+-+ 0 0 0 x1 +-+-+ 1 0 +-+-+ x2=1, x1=1 = 1 x2 - 0 1 +-+-+ 0 0 0 x1 +-+-+ 1 0 1 +-+-+ Все карта построенна.
Карты Карно Сднф
Пример заполнения (3 переменных) Попробуем теперь построить карту с 3 переменными. Возьмем для этого функцию XOR.
Конъюнкция
Возможно так же построение карт Карно для функций 5 и 6 переменных, однако работа с ними значительно затрудена. Для числа переменных, большего 6, использование карт Карно попросту непрактично. Пример Рассмотрим функцию, имеющую следующую таблицу истинности: (x1 ) (x2 ) (x3 ) (x4 ) (f(x1, x2, x3, x4) ) 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 Перепишем эту таблицу в виде карты Карно.