Карта Карно

Карта Карно1Карта КарноКартаКарно́—графическийспособминимизациипереключательных(булевых)функций,обеспечивающийотносительную простоту работы с большими выражениями иустранение потенциальных гонок. Представляет собой операциипопарного неполного склеивания и элементарного поглощения.КартыКарнорассматриваютсякакперестроеннаясоответствующим образом таблица истинности функции. КартыКарно можно рассматривать как определенную плоскую разверткуn-мерного булева куба.Карты Карно были изобретены в 1952 Эдвардом В. Вейчем иусовершенствованы в 1953 Морисом Карно, физиком из «BellLabs», и были призваны помочь упростить цифровые электронные схемы.Рис.

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

Операция попарного склеиванияосуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых(прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кромеодной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменнойподвергнуть склейке. Например:Аналогично для КНФ:Возможность поглощения следует из очевидных равенствТаким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных ксклейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей.Карты Карно предоставляют наглядный способ отыскания таких термов.Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своёмсоставе 2N различных термов.

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

Например,четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваютсяв один терм, при этом поглощаются K переменных.Для упрощения работы с булевыми функциями большого числа переменных был предложен следующийудобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано нарисунке.

Таким образом появляется возможность представлять булевы функции с числом переменных большедвух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) несоответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы,соседствуют между собой.2Карта Карно3Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц дляN=4 и N=5 приведены на рисунке.

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

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

После того как Карта заполнена,можно приступать к минимизации.Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержатединицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули. Сама минимизацияпроизводится по следующим правилам (на примере ДНФ):1. Объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала(целое число = 0…) клеток (помним про то, что крайние строки и столбцы являются соседними междусобой), в области не должно находиться клеток, содержащих нули;Карта Карно2.3.4.5.6.Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну;Область должна быть как можно больше, а количество областей как можно меньше;Области могут пересекаться;Возможно несколько вариантов покрытия.Далее берём первую область и смотрим, какие переменные не меняются в пределах этой области, выписываемконъюнкцию этих переменных; если неменяющаяся переменная нулевая, проставляем над ней инверсию.Берём следующую область, выполняем то же самое, что и для первой, и т.

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

Так дляКартыКарнонарис.1выражениевформатеДНФбудетиметьвид:В формате КНФ:Так же из ДНФ в КНФ и обратно можно перейти использовав Законы де Моргана.ПримерыПример 1У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдёт гулять на улицу, если ему разрешат хотябы двое родственников.Для краткости обозначим родственников Коли через буквы:мама — х1папа — х2дедушка — х3бабушка — х4Условимся обозначать согласие родственников единицей, несогласие - нулём.

Возможность пойти погулятьобозначим буквой f, Коля идёт гулять — f = 1, Коля гулять не идёт — f = 0.Составим таблицу истинности:4Карта Карно5Перерисуем таблицу истинности в 2-х мерный вид:Переставим в ней строки и столбцы всоответствии с кодом Грея. Получили Карту Карно:Заполним её значениями из таблицы истинности:Минимизируемв соответствии с правилами:Карта Карно61. 1. Все области содержат 2^n клеток;2. 2.

Так как Карта Карно на четырепеременные, оси располагаются награницах Карты и их не видно(подробнее смотри пример Карты на 5переменных);3. 3. Так как Карта Карно на четырепеременные, все области симметричноосей — смежные между собой(подробнее смотри пример Карты на 5переменных);4. 4. Области S3, S4, S5, S6 максимальнобольшие;5. 5. Все области пересекаются(необязательное условие);6. 6.

В данном случае рациональныйвариант только один.Теперь по полученной минимальной ДНФ можно построить логическую схему:Из-за отсутствия в наличии шести-входового элемента ИЛИ,реализующего функцию дизъюнкции, пришлось каскадировать пятии двух-входовые элементы(D7, D8).Составим мин. КНФ:Карта Карно7Карта Карно8Пример Карты Карно на пять переменныхИмеем такую таблицу истинности:Карта Карно будет выглядеть следующим образом (для лучшего визуального восприятияв Карту нули не записываем):(на••••примереНеправильноДНФ):— Область S1 — накрыта правильно;— Область S2 — нарушает п.1;— Область S3 — нарушает п.2;-Области S4 и S6 — не выполняют п.3, это не является ошибкой — выражение получится больше чем еслибы S4 и S6 представляли собой одну область;• — Область S5 — нарушает п.1 по кол-ву клеток и по недопустимости нахождения нулей в области.Карта Карно9Правильно, но не оптимально:Этаминимизирована неоптимально, так как можно объединить единицы, входящие в члены S3 и S5.Минимизировав эту Карту получаем следующую ДНФ:Оптимально:картаКарноКарта Карно10Составим минимальную КНФ:Другой вариант той же самой Карты Карно:Ничего не меняется только в строкахзаписано три переменных, а в столбцахдве.Карта Карно11Пример большой Карты Карно на восемь переменныхПредположим, по имеющейся таблице истинности составлена такая Карта Карно:Найдёмминимальную ДНФ:Минимальная КНФ:Карта Карно12Источники и основные авторыИсточники и основные авторыКарта Карно  Источник: http://ru.wikipedia.org/w/index.php?oldid=36798414  Редакторы: AdmiralHood, Altum, Antonix Wayfarer, CaesarIII, Changall, DerLetzteRegenbogen, Dims,Fedorchenko.bogdan, Gvozdet, Jack-ov, Jazz, Loveless, Obersachse, Qldor, Rinatus, VP, Ботильда, Голем, Дмитрий Джус, Синдар, 30 анонимных правокИсточники, лицензии и редакторыизображенийФайл:Karnaugh map Intro.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_Intro.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnaugh map 01.gif  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_01.gif  Лицензия: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Редакторы: AdmiralHoodФайл:Karnaugh map 02.gif  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_02.gif  Лицензия: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Редакторы: AdmiralHoodФайл:Karnaugh map 03.gif  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_03.gif  Лицензия: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Редакторы: AdmiralHoodФайл:Karnaugh map 04.gif  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_04.gif  Лицензия: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Редакторы: AdmiralHoodИзображение:Karnough map 2 1 1.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_1.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 2.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_2.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 3.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_3.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 4.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_4.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 5.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_5.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 6.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_6.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 7.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_7.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 8.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_8.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 9.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_9.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 10.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_10.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 11.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_11.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 12.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_12.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 13.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_13.PNG  Лицензия: Public Domain  Редакторы: Jack-ovИзображение:Karnough map 2 1 14.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_2_1_14.PNG  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Nikolay true table.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Nikolay_true_table.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:2d true table.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:2d_true_table.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnough map 4 empty.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_4_empty.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Nikolay map.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Nikolay_map.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Nikolay map DNF.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Nikolay_map_DNF.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Logic Nikolay.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Logic_Nikolay.PNG  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Nikolay map KNF.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Nikolay_map_KNF.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:~logic Nikolay.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:~logic_Nikolay.PNG  Лицензия: Public Domain  Редакторы: Jack-ovФайл:X5 true table.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:X5_true_table.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnough map 5.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnough map 5 error.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5_error.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnough map 5 right.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5_right.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnaugh map minimize.gif  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnaugh_map_minimize.gif  Лицензия: Creative Commons Attribution-Sharealike3.0,2.5,2.0,1.0  Редакторы: AdmiralhoodФайл:Karnough map 5 KNF.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5_KNF.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnough map 5 turn.png  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_map_5_turn.png  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnough 8 clear.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_8_clear.PNG  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnough 8 DNF.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_8_DNF.PNG  Лицензия: Public Domain  Редакторы: Jack-ovФайл:Karnough 8 KNF.PNG  Источник: http://ru.wikipedia.org/w/index.php?title=Файл:Karnough_8_KNF.PNG  Лицензия: Public Domain  Редакторы: Jack-ovЛицензияCreative Commons Attribution-Share Alike 3.0 Unportedhttp:/ / creativecommons.

org/ licenses/ by-sa/ 3. 0/13.