Карта Карно (815677)
Текст из файла
Карта Карно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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
