Карты Карно –
координатный способ представления
булевых функций.
При данном способе
задания таблица истинности функции
представляется в виде координатной
карты состояний, которая содержит 2n
клеток (по числу входных наборов булевой
функции n переменных). Переменные функции
разбиваются на две группы так, что одна
группа определяет координаты столбца
карты, а другая – координаты строки.
При такoм способе
построения каждая клетка определяется
значениями переменных, соответствующих
определенному двоичному набору. Внутри
каждой клетки карты Карно ставится
значение функции на данном наборе.
Переменные в строках и столбцах
располагаются так, чтобы соседние клетки
карты Карно различались только в одном
разряде переменных, т.е. были соседними.
Поэтому значения переменных в столбцах
и в строках карты образуют соседний код
Грея. Такой способ представления очень
удобен для наглядности при минимизации
булевых функций.
Карты Карно были
изобретены в 1952 г. Эдвардом В. Вейч’ем
и усовершенствованы в 1953 г. Морисом
Карно, физиком из “Бэлл Лабс”Метод
карт Карно применим к минимизации
булевых функций до 6-ти переменных (до
4 переменных на плоскости) и до 6 – в
трехмерной интерпретации.
===================================================================================
8. Построение сднф по карте карно. 9. Построение скнф по карте карно
Правила минимизации
с использованием карт Карно
1. В карте Карно
группы единиц (для получения ДНФ) и
группы нулей (для получения КНФ) необходимо
обвести четырехугольными контурами.
Внутри контура должны находится только
одноименные значения функции. Этот
процесс соответствует операции склеивания
или нахождения импликант данной функции.
2. Количество клеток
внути контура должно быть целой степенью
двойки (1, 2, 4, 8, 16…).
3. При проведении
контуров крайние строки карты (верхние
и нижние, левые и правые), а также угловые
клетки, считаются соседними (для карт
до 4-х переменных).
4. Каждый контур
должен включать максимально возможное
количество клеток. В этом случае он
будет соответствовать простой импликанте.
5. Все единицы
(нули) в карте (даже одиночные) должны
быть охвачены контурами. Любая единица
(нуль) может входить в контуры произвольное
количество раз.
6. Множество
контуров, покрывающих все 1 (0) функции
образуют тупиковую ДНФ (КНФ). Целью
минимизации является нахождение
минимальной из множества тупиковых
форм.
7. В элементарной
конъюнкции (дизъюнкции), которая
соответствует одному контуру, остаются
только те переменные, значение которых
не изменяется внутри обведенного
контура. Переменные булевой функции
входят в элементарную коньюнкцию (для
значений функции 1) без инверсии, если
их значение на соответствующих координатах
равно 1 и с инверсией – если 0. Для значений
булевой функции, равных 0, записываются
элементарные дизьюнкции, куда переменные
входят без инверсии, если их значение
на соответствующих координатах равно
0 и с инверсией – если 1.
====================================================================================
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Расположение термов в карте Карно для функции 4 переменных, изображённой на плоскости и на поверхности тора. Изображение на поверхности тора наглядно показывает соседство первой и последней строк таблицы и крайнего правого и крайнего левого столбцов. Отмеченные точками клетки являются соседними.
Ка́рта Ка́рно (куб Ка́рно, диагра́мма Ка́рно, ка́рта Ве́йча) — графический способ представления булевых функций с целью их удобной и наглядной ручной минимизации[1].
Является одним из эквивалентных способов описания или задания логических функций наряду с таблицей истинности или выражениями булевой алгебры. Преобразование карты Карно в таблицу истинности или в булеву формулу и обратно осуществляется элементарным алгоритмом.
Удобство и наглядность такого представления логической функции обусловлено тем, что логические термы, к которым могут быть применены операции попарного неполного склеивания и элементарного поглощения группируются в карте Карно в виде визуально очевидных прямоугольных массивов, содержащих в своих ячейках одинаковые значения (нули и единицы).
Карты Карно можно рассматривать как развертку на плоскость n-мерного булева куба, причем размерность этого гиперкуба совпадает с количеством переменных представляемой функции, а каждая вершина гиперкуба взаимно однозначно соответствует одной клетке карты Карно. Графически карта Карно изображается в виде прямоугольника или квадрата из ячеек, число которых равно 
, причем любые две соседние ячейки по вертикали или горизонтали или, иными словами — в окрестности фон Неймана описывают термы, различающиеся только по одной переменной — с логическим отрицанием и без логического отрицания. Также соседним являются первая и последняя строки, крайний левый и крайний правый столбцы таблицы, поэтому таблица Карно является фактически разверткой логического гиперкуба на поверхность тороида. Возможно построение самых различных карт для одной и той же функции, удовлетворяющих условию: геометрическое соседство ячеек в смысле фон Неймана — логическое соседство термов — то есть с расстоянием Хэмминга между термами соседних ячеек равным 1. Любая из таких таблиц одинаково удобна для минимизации функции, но обычно переменные по строкам и столбцам в карте Карно упорядочивают по рефлексивному коду Грея из-за мнемоничности и наглядности.
История[править | править код]
Карты Карно были предложены в 1952 году Эдвардом В. Вейчем[2] и усовершенствованы в 1953 году физиком из «Bell Labs» Морисом Карно (Maurice Karnaugh), чтобы упростить проектирование цифровых систем[3].
Основные принципы[править | править код]
Карта Карно представляет собой таблицу истинности, отформатированную особым образом, пригодным для наглядной ручной минимизации. Результатом минимизации является либо дизъюнктивная нормальная форма (ДНФ), либо конъюнктивная нормальная форма (КНФ). В первом случае работа ведётся с клетками карты, где находятся единицы, во втором — с клетками, где находятся нули. В исходной карте, как и в таблице истинности, каждая единица соответствует одному терму cовершенной дизъюнктивной нормальной форме (СДНФ), а каждый ноль — одному терму cовершенной конъюнктивной нормальной форме (СКНФ).
Рядом расположенные группы единиц или нулей на карте Карно объединяют в прямоугольные области или «склейки» размером 
клеток. Каждая такая группа в итоговой логической формуле будет соответствовать одному терму (если считать, что операция логического «ИЛИ» — это «суммирование», а операция логического «И» — это «перемножение», то один терм соответствует одному слагаемому в случае ДНФ, или одному сомножителю в случае КНФ), содержащему 
переменных, это группирование обычно называют «склейкой»[4]. Таким образом, работа с картой сводится к выделению оптимального набора нескольких групп единиц (нулей) и преобразование их в логическое выражение.
Принципы минимизации[править | править код]
Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами, содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть поглощению. Например:
Аналогично для КНФ:
Возможность поглощения следует из очевидных равенств:
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для функций многих логических переменных может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.
Булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе не более чем различных термов. Все эти элементарные термы можно представить в виде некоторой структуры, топологически эквивалентной 
-мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.
На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:
В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.
Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:
В общем случае можно сказать, что 
термов, принадлежащие одной что 
-мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются переменных.
Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость, как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел записанных в лексикографическом порядке (00 01 10 11), а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.
Аналогичным образом можно работать с логическими функциями большего числа переменных.
Стили представления карт Карно[править | править код]
Традиционно существует несколько стилей представления карт Карно. Часто в шапке и левой колонке проставляются численные значения переменных, подобно тому, как они указаны в таблице истинности (а). В этом стиле наиболее очевидно, что карта Карно является своеобразной формой представления таблицы истинности. Однако клетки карты Карно следуют в несколько ином порядке, чем строки в таблице истинности, так как в таблице истинности принято строки упорядочивать в лексикографическом нарастании двоичных чисел. Например, в карте Карно для четырёх переменных порядок следования ячеек карты и строк таблицы истинности совпадёт, если переставить местами третий-четвёртый столбцы и третью-четвёртую строки карты.
Каждая строка таблицы истинности и каждая клетка карты Карно соответствует одному слагаемому ДНФ, поэтому в шапке и левой колонке карты можно указывать вхождения переменных (прямые и инверсные), как они выглядят в СДНФ (б). Существует сокращённый вариант этого стиля представления, где во вспомогательных строках и колонках указывается, в каком виде, прямом или инверсном, представлена каждая переменная в соответствующей строке или столбце карты (в).
Наконец, в некоторых случаях на краях карты линиями указываются столбцы и строки, где соответствующая переменная представлена в прямом виде (г).
а) 
б) 
в) 
г) 
Порядок работы с картой Карно[править | править код]
Исходной информацией для работы с картой Карно является таблица истинности минимизируемой функции. Таблица истинности содержит полную информацию о логической функции, задавая её значения на всех возможных 2n наборах входных переменных X1 … Xn. Карта Карно также содержит 2n клеток, каждая из которых ассоциируется с уникальным набором входных переменных X1 … Xn. Таким образом, между таблицей истинности и картой Карно имеется взаимно однозначное соответствие, и карту Карно можно считать соответствующим образом отформатированной таблицей истинности.
В данном разделе в качестве примера используется функция четырёх переменных, заданная таблицей истинности, изображённой на рис. 2а. Карта Карно для той же функции изображена на рис. 2б.
Рис. 2. Пример работы с картой Карно
Принципы склейки[править | править код]
Прямоугольную область в карте Карно, которая состоит из 2k одинаковых значений (единиц или нулей в зависимости от того, какую форму нужно получить) будем называть склейкой, группой или областью. Распределение всех имеющихся в карте Карно нулей (единиц) по склейкам будем называть покрытием. С целью минимизации булевой функции необходимо построить такое покрытие карты Карно, чтобы количество склеек было минимальным, а размер каждой склейки максимально возможным. Для этого необходимо руководствоваться следующими правилами.
- Склейку клеток одной и той же карты Карно можно осуществлять как по единицам (a), так и по нулям (б). Первое необходимо для получения ДНФ, второе — для получения КНФ.
a) 
б) 
- Склеивать можно только прямоугольные области с числом единиц (нулей), являющимся целой степенью двойки (1, 2, 4, 8, 16, 32… клетки).
- Рекомендуется выбирать максимально возможные области склейки. Если область склейки не является максимально возможной, это не будет ошибкой, однако ДНФ (КНФ) не получится минимальной.
- В некоторых ситуациях в раскладке образуется изолированная единица или ноль, которую невозможно включить в какую-либо область. В этом случае единица (ноль) склеивается «сама с собой». Нельзя оставлять «висячие» единицы (нули), так как это приведёт к некорректной записи выражения для функции.
- Все единицы (нули) должны попасть в какую-либо область.
- Область, которая подвергается склейке, должна содержать одинаковые значения — только единицы или только нули.
- Для карт Карно с числом переменных 3 и 4 применимо следующее правило: крайние клетки каждой горизонтали и каждой вертикали граничат между собой и могут объединяться в прямоугольники (топологически карта Карно представляет собой тор). Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для 4 переменных. Для карт Карно с числом переменных менее 3 это правило не имеет смысла, так как крайние клетки и так граничат между собой; для карт Карно с числом переменных более четырёх правила смежности более сложные.
- Одна ячейка карты Карно может входить сразу в несколько областей. Это следует из очевидного свойства булевых функций: повторение уже существующего слагаемого (сомножителя) не влияет на функцию:
- Не следует без нужды включать клетку во все возможные склейки, это не является ошибкой, но усложняет формулу. С точки зрения минимальности ДНФ (КНФ) число склеек должно быть как можно меньше (каждая дополнительная склейка порождает дополнительный терм), а число клеток в склейке должно быть максимально возможным (чем больше клеток в склейке, тем меньше переменных содержит терм. Склейка размером 2k клеток порождает терм с n–k переменными)[4].
- В отличие от СДНФ и СКНФ, ДНФ и КНФ не всегда единственны. Для некоторых функций существует несколько эквивалентных друг другу ДНФ (КНФ), которые соответствуют разным способам покрытия карты Карно прямоугольными областями. Очень часто две различные ДНФ (КНФ) имеют одинаковую сложность, что не позволяет сделать однозначный выбор минимальной формулы.
Карты с неопределёнными значениями[править | править код]
На практике встречаются случаи, когда при некоторых значениях аргументов булева функция не определена. Например, булева функция описывает цифровое устройство, у которого некоторые сочетания входных сигналов физически невозможны или же при некоторых значениях входных сигналов реакция устройства не имеет значения. В таких случаях говорят о «неопределённых условиях», а функция такого вида называется «частично определённой» или просто «частичной»[5].
На рисунке показано цифровое устройство F с четырьмя двоичными входными сигналами 
. Входными сигналами могут быть показания датчиков, работающих на замыкание и следовательно имеющих только два значения — «включено» (1) и «выключено» (0). Предположим, что в силу особенностей конструкции устройства 2-й и 4-й датчики не могут сработать одновременно, то есть сочетание сигналов 
физически невозможно. В этом случае значение функции в четырёх клетках карты Карно не имеет значения, что условно показано символом «×».
Такие клетки могут произвольным образом включаться в любые склейки, а также могут не включаться ни в какие склейки, то есть их по желанию можно доопределять и как 1, и как 0[5].
Преобразование карты в формулу[править | править код]
Когда все склейки на карте Карно определены, необходимо преобразовать полученную карту Карно в формулу. При этом руководствуются следующими принципами:
- Каждая склейка на карте Карно является слагаемым ДНФ при склеивании по единицам и сомножителем КНФ при склеивании по нулям.
- Если склейка охватывает 2k клеток, то ей будет соответствовать слагаемое из n–k сомножителей в ДНФ и сомножитель с n-k слагаемыми в КНФ. Например, при минимизации функции 4 переменных склейка из 4 единиц будет соответствовать слагаемому из двух сомножителей.
- В карте Карно для каждой переменной существуют две зоны, каждая из которых занимает ровно половину клеток карты. В одной зоне переменная присутствует в прямом виде, в другой — в инверсном. Если склейка целиком лежит в одной из этих зон, соответствующая переменная присутствует в слагаемом (сомножителе). Если склейка лежит одновременно в двух зонах, то данная переменная испытывает поглощение и не присутствует в слагаемом (сомножителе).
Описание[править | править код]
Карта Карно может быть построена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности, представленная в виде матрицы в 2-мерном виде.
Каждая клетка этой карты соответствует одной строке в классической таблице истинности и обозначается строкой переменных с инверсиями и без инверсий. Например, пусть в таблице истинности для функции 4 переменных 
одна из строк имеет вид: 0 1 1 0 | 1, тогда клетка в карте Карно, соответствующая этой строке, будет иметь имя 
и в этой клетке ставится 1. Указание имён клеток в карте Карно обычно выполняется дополнительной строкой сверху и дополнительным столбцом слева.
Существенно, что в карте Карно соседние клетки обязательно имеют соседние, в смысле расстояния Хэмминга коды, то есть расстояние Хэмминга между соседними клетками равно 1, и различаются только состоянием — с инверсией или без, одной и только одной из переменных. Соседними клетками считаются клетки, примыкающие друг к другу стороной, также соседними клетками считаются клетки крайнего левого и крайнего правого столбцов и клетки первой и последней строк. Таком образом, карта Карно на плоскости топологически эквивалентна поверхности тора в трёхмерном пространстве, или гипертору в пространстве с размерностью на 1 больше размерности соответствующей многомерной карты Карно.
Так как перестановка переменных в логической функции не изменяет саму функцию, то есть, например, 
или, что то же самое, — перестановка столбцов переменных в таблице истинности не изменяет функцию, существует несколько вариантов отображения таблицы истинности на карту Карно с сохранением «соседства» клеток. Но практически наиболее часто карту Карно заполняют, используя нарастающий код Грея для обозначения строк и столбцов. Такой подход гарантирует порождение карты Карно с избеганием субъективных ошибок.
При заполнении карты на пересечении строки и столбца проставляется соответствующее значение из таблицы истинности — 0 или 1. После того как карта заполнена, приступают к минимизации.
Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки, которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ).
- Объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала ( целое число = 0…) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули;
- Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
- Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну;
- Область должна быть как можно больше, а количество областей как можно меньше;
- Области могут пересекаться;
- Возможно несколько вариантов покрытия.
Далее берём первую область и смотрим, какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных; если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое, что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например (для Карт на 2 переменные):
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|||||||||
|
|
Для КНФ всё то же самое, только рассматриваем клетки с нулями, неменяющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной.
Так, для Карты Карно на рис. 1, выражение в формате ДНФ будет иметь вид:
В формате КНФ:
Так же из ДНФ в КНФ и обратно можно перейти, использовав Законы де Моргана.
Примеры[править | править код]
Пример 1[править | править код]
У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдёт гулять на улицу, тогда и только тогда, когда ему разрешат хотя бы двое родственников.
Для краткости обозначим родственников Коли через буквы:
мама — X1
папа — X2
дедушка — X3
бабушка — X4
Условимся обозначать согласие родственников единицей, несогласие — нулём. Возможность пойти погулять обозначим буквой f, Коля идёт гулять — f = 1, Коля гулять не идёт — f = 0.
Составим таблицу истинности:
Перерисуем таблицу истинности в 2-мерный вид:
Переставим в ней строки и столбцы в соответствии с кодом Грея (последний и предпоследний столбец меняют местами). Получили Карту Карно:
Заполним её значениями из таблицы истинности (первая строка не соответствует таблице истинности, так как f=0 и разрешения на гулять нет):
Минимизируем в соответствии с правилами:
- Все области содержат 2^n клеток;
- Так как Карта Карно на четыре переменные, оси располагаются на границах Карты и их не видно (подробнее смотри пример Карты на 5 переменных);
- Так как Карта Карно на четыре переменные, все области симметрично осей — смежные между собой (подробнее смотри пример Карты на 5 переменных);
- Области S3, S4, S5, S6 максимально большие;
- Все области пересекаются (необязательное условие);
- В данном случае рациональный вариант только один.
Теперь по полученной минимальной ДНФ можно построить логическую схему:
Из-за отсутствия в наличии шестивходового элемента ИЛИ, реализующего функцию дизъюнкции, пришлось каскадировать пяти- и двух-входовые элементы (D7, D8).
Составим мин. КНФ:
См. также[править | править код]
- ДНФ
- КНФ
- СДНФ
- СКНФ
- Минимизация логических функций методом Куайна
- Минимизация комбинационных схем
- en:Espresso heuristic logic minimizer
- Метод Куайна — Мак-Класки
Примечания[править | править код]
- ↑ Гивоне Д. Россер Р. (1983), с. 67—76.
- ↑ Veitch E. W. (May 1952).
- ↑ Karnaugh M. (November 1953).
- ↑ 1 2 Гивоне Д. Россер Р. (1983), с. 69.
- ↑ 1 2 Гивоне Д. Россер Р. (1983), с. 75.
Источники[править | править код]
- Veitch E.W. (May 1952) A Chart Method for Simplifying Truth Functions. Proceedings, Association for Computing Machinery, Pittsburgh, Pa., May 2, 3, 1952, pp. 127—133. DOI:10.1145/609784.609801.
- Karnaugh M. (November 1953) The Map Method for Synthesis of Combinational Logic Circuits. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics. 72 (5): 593—599. DOI:10.1109/TCE.1953.6371932.
- Токхейм Р. Основы цифровой электроники: Пер. с англ. — М.: Мир, 1988. — 392 с.. ил. (Глава 4, страницы 88—95)
- Гивоне Д. Россер Р. Микропроцессоры и микрокомпьютеры: Вводный курс: Пер. с англ. — М.: Мир, 1983.— 464 с., ил.
Ссылки[править | править код]
- Using Karnaugh maps in practical applications, Разработка схемы управления светофором.
Программное обеспечение
- Karnaugh Minimizer, Коммерческое Windows-приложение (часто работает некорректно, например для этого уравнения: 0,1,5,8,10,13).
- Logic Minimizer, Коммерческое Windows-приложение, но можно сделать, чтобы запускалось на Unix.
- Kmap minimizer Онлайн-приложение (Flash).
- GKMap, свободное ПО на SourceForge.net.
- Karnaugh Map Minimizer, бесплатное (но часто некорректно работающее) ПО на SourceForge.net.
- Gorgeous Karnaugh, коммерческое ПО Gorgeous Karnaugh для минимизации по картам Карно.
Видео[править | править код]
- Карты Карно. Лекция. Youtube.
Минимизация булевых функций
Ясно, что при разработке логических схем, немаловажной является задача минимизации количества используемых элементов (другими словами, логических операций).
В связи с этим, возникает задача минимизации логических функций в некотором классе формул. В частности, в классах ДНФ и КНФ.
- Минимальная ДНФ
- Такая ДНФ, которая содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей ДНФ.
- Минимальная КНФ
- Такая КНФ, которая содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей КНФ.
Процесс нахождения минимальных форм, собственно, и называется минимизацией. В простых случаях, для минимизации достаточно тождественных преобразований. В более сложных – используются специальные алгоритмы.
Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя членами, содержащими одинаковые переменные, вхождения которых (с отрицанием и без) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:
[
;overline{x_1};x_2x_3x_4
vee
;overline{x_1};x_2;overline{x_3};x_4 =
;overline{x_1};x_2x_4 (x_3 vee;overline{x_3};) =
;overline{x_1};x_2x_4 mathbin{&}1 =
;overline{x_1};x_2x_4.
]
Аналогично для КНФ:
[
(;overline{x_1};vee x_2vee x_3vee x_4)
(;overline{x_1};vee x_2vee;overline{x_3};vee x_4) =
;overline{x_1};vee x_2vee x_4vee x_3;overline{x_3}; =
;overline{x_1};vee x_2vee x_4vee 0 =
;overline{x_1};vee x_2vee x_4.
]
Возможность поглощения следует из очевидных равенств
[
A vee;overline{A}; = 1
][
A;overline{A}; = 0.
]
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск членов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей.
Минимизирующие карты Карно
- Карта Карно
-
Графический способ минимизации булевых функций. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как построенная соответствующим образом таблица истинности функции.
Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.
Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.
В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.
Булевы функции (N) переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе (2^N) различных элементарных членов.
Элементарные члены СДНФ или СКНФ образуют структуру, топологически эквивалентную (N)-мерному кубу. Действительно, если рассматривать набор значений функции (x_1,,ldots,,x_N) как (N)-мерный вектор ({x_1,,ldots,,x_N}), мы получим набор точек, лежащих на ортах (N)-мерной системы координат, и удаленных друг от друга на (1). Другими словами, мы получим (N)-мерный гиперкуб с ребром (1).
Например, для функции двух переменных, заданной таблицей истинности:
| (x_1) | (x_2) | (f(x_1,x_2)) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
можно построить эквивалентный ей квадрат:
0 01 1 11 0 00 1 10
Или, если обозначить вершины соответствующими элементарными конъюнкциями и выделить вершины, конъюнкции которых входят в СДНФ:
0 x̅₁x₂ 1 x₁x₂ 0 x̅₁x̅₂ 1 x₁x̅₂
Или СКНФ:
0 x₁∨x̅₂ 1 x̅₁∨x̅₂ 0 x₁∨x₂ 1 x̅₁∨x₂
Можно заметить, что члены, находящиеся на одной стороне квадрата, могут быть склеены. Соответственно, если составляется ДНФ, то операции производятся только над вершинами, в которых функция имеет значение (1) (по правилам построения СДНФ). Если же составляется КНФ, то над вершинами, в которых функция имеет значение (0) (по правилам построения СКНФ).
При этом, сохраняются переменные, значение которых на стороне постоянно.
В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.
Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации. Например, четыре члена, принадлежащие одной грани куба, объединяются в один с поглощением двух переменных:
[
;overline{x_1};;overline{x_2};;overline{x_3};
vee
x_1;overline{x_2};;overline{x_3};
vee
;overline{x_1};;overline{x_2};x_3
vee
x_1;overline{x_2};x_3
=]
[ =
;overline{x_2}; (;overline{x_1};;overline{x_3}; vee;overline{x_1};x_3 vee x_1;overline{x_3}; vee x_1x_3)
= ;overline{x_2}; (;overline{x_1}; vee x_1)(;overline{x_3}; vee x_3) = ;overline{x_2};
]
В общем случае можно сказать, что (2^K) членов, принадлежащие одной (K)–мерной грани гиперкуба, склеиваются в один член, при этом поглощаются (K) переменных.
Карта Карно представляет собой развертку гиперкуба на плоскость. Например, трехмерный куб из предыдущего примера можно развернуть следующим образом:
1 x̅₁x̅₂x̅₃ 1 x̅₁x̅₂x₃ 0 x̅₁x₂x̅₃ 0 x̅₁x₂x₃ 0 x₁x₂x₃ 0 x₁x₂x̅₃ 1 x₁x̅₂x₃ 1 x₁x̅₂x̅₃
Карта Карно является представлением такой двумерной развертки в виде таблицы.
| (_{x_3}backslash^{x_1x_2}) | (00) | (01) | (11) | (10) |
|---|---|---|---|---|
| (0) | (1) | (0) | (0) | (1) |
| (1) | (1) | (0) | (0) | (1) |
В этой карте самые левые ячейки смежны самым правым.
Ясно, что на одной (K)-мерной грани могут лежать (2^K) вершин. Следовательно, в карте Карно выбираются группы по (2^K) смежных ячеек, и в результирующую ДНФ или КНФ входят только те переменные, которые неизменны в рамках данной группы. Общее число членов соответствует числу групп в карте Карно, а число неизменных переменных обратным образом зависит от количества элементов в группе. Как следствие, группы необходимо выбирать как можно более большими. Следует отметить, что одна комбинация переменных может входить в несколько групп.
Для функций четырех переменных, требуется развертка 4-мерного гиперкуба. Карта Карно в таком случае имеет вид:
| (_{x_3x_4}backslash^{x_1x_2}) | (00) | (01) | (11) | (10) |
|---|---|---|---|---|
| (00) | (f(0,0,0,0)) | (f(0,1,0,0)) | (f(1,1,0,0)) | (f(1,0,0,0)) |
| (01) | (f(0,0,0,1)) | (f(0,1,0,1)) | (f(1,1,0,1)) | (f(1,0,0,1)) |
| (11) | (f(0,0,1,1)) | (f(0,1,1,1)) | (f(1,1,1,1)) | (f(1,0,1,1)) |
| (10) | (f(0,0,1,0)) | (f(0,1,1,0)) | (f(1,1,1,0)) | (f(1,0,1,0)) |
В данном случае, все крайние ячейки смежны друг другу. Это можно себе представить, натянув эту развертку на тор (“бублик”):
Возможно так же построение карт Карно для функций 5 и 6 переменных, однако работа с ними значительно затрудена. Для числа переменных, большего 6, использование карт Карно попросту непрактично.
Пример
Рассмотрим функцию, имеющую следующую таблицу истинности:
| (x_1) | (x_2) | (x_3) | (x_4) | (f(x_1, x_2, x_3, x_4)) |
|---|---|---|---|---|
| 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 |
Перепишем эту таблицу в виде карты Карно:
| x₃x₄x₁x₂ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 0 | 0 |
| 01 | 1 | 0 | 0 | 0 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 1 | 1 | 1 | 0 |
Легко выделяются три группы. Исходя из этого, записывается ДНФ:
(;overline{x_1};;overline{x_2};;overline{x_3};)(vee)(;overline{x_1};;overline{x_4};)(vee)({x_2}{x_3})
Метод Куайна-МакКласки
Метод Куайна-МакКласси строится на основе того же аппарата, что и карты Карно, однако оказывается более практичным для большего количества переменных.
Алгоритм заключается последовательной склейке, и затем редукции результата.
Склейка
Сначала элементарные члены совершенной формы записываются в двоичной форме в таблицу, где группируются по количеству единиц.
Затем, члены, которые отличаются одной переменной (одним битом), могут быть склеены. В таком случае единица заменяется на “-”. Очевидно, что склеены могут быть только члены из соседних групп
Члены, которые нельзя склеить, обозначаются звездочкой “*”.
Полученные склеенные члены могут, в свою очередь, так же быть склеены. При этом “-” трактуется как “третье” значение.
Когда никакие члены больше не могут быть склеены, из членов, отмеченных “*”, составляется сокращенная форма, которая не обязательно минимальна. После этого производится редукция.
Редукция
Для редукции, составляется таблица, в строки которой включаются члены сокращенной формы, а в столбцы – члены совершенной.
В ячейках ставится отметка (например, крестик “×”), если соответствующий член сокращенной формы поглощает соответствующий член совершенной формы (т.е. если заголовок строки является частью заголовка столбца).
Выбираются столбцы, содержащие только один “×”. Соответсвтующие им члены сокращенной формы составляют ядро, и должны войти в минимальную форму.
Если ядро не перекрывает все столбцы, то в минимальную форму так же включаются несколько членов сокращенной формы, не входящих в ядро, таким образом, чтобы члены минимальной формы перекрывали все столбцы таблицы.
Пример
Найдем минимальную форму функции
| n | x₁ | x₂ | x₃ | x₄ | f |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 0 | 1 | 1 |
| 6 | 0 | 1 | 1 | 0 | 0 |
| 7 | 0 | 1 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 | 1 |
| 9 | 1 | 0 | 0 | 1 | 0 |
| 10 | 1 | 0 | 1 | 0 | 1 |
| 11 | 1 | 0 | 1 | 1 | 0 |
| 12 | 1 | 1 | 0 | 0 | 1 |
| 13 | 1 | 1 | 0 | 1 | 1 |
| 14 | 1 | 1 | 1 | 0 | 0 |
| 15 | 1 | 1 | 1 | 1 | 1 |
Члены СДНФ в двоичной нотации:
- 0000 = 0
- 0001 = 1
- 0010 = 2
- 0011 = 3
- 0101 = 5
- 0111 = 7
- 1000 = 8
- 1010 = 10
- 1100 = 12
- 1101 = 13
- 1111 = 15
Группировка:
0
- 0000 = 0
1
- 0001 = 1
- 0010 = 2
- 1000 = 8
2
- 0011 = 3
- 0101 = 5
- 1010 = 10
- 1100 = 12
3
- 0111 = 7
- 1101 = 13
4
- 1111 = 15
Склейка 1:
- 0, 1 = 000-
- 0, 2 = 00-0
- 0, 8 = -000
- 1, 3 = 00-1
- 1, 5 = 0-01
- 2, 3 = 001-
- 2,10 = -010
- 8,10 = 10-0
- 8,12 = 1-00
- 3,7 = 0-11
- 5,7 = 01-1
- 5,13 = -101
- 12,13 = 110-
- 7,15 = -111
- 13,15 = 11-1
Группировка 2:
- 0, 1 = 000-
- 2, 3 = 001-
- *12,13 = 110-
- 0, 2 = 00-0
- 1, 3 = 00-1
- 8,10 = 10-0
- 5,7 = 01-1
- 13,15 = 11-1
- 1, 5 = 0-01
- *8,12 = 1-00
- 3,7 = 0-11
- 0, 8 = -000
- 2,10 = -010
- 5,13 = -101
- 7,15 = -111
Склейка 2:
- *0,1,2,3 = 00–
- *0,2,8,10 = -0-0
- *5,7,13,15 = -1-1
- *1,3,5,7 = 0–1
Итого, члены сокращенной формы:
- 12,13 = 110-
- 8,12 = 1-00
- 0,1,2,3 = 00–
- 0,2,8,10 = -0-0
- 5,7,13,15 = -1-1
- 1,3,5,7 = 0–1
Редукция:
| 0 | 1 | 2 | 3 | 5 | 7 | 8 | 10 | 12 | 13 | 15 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 12,13 | × | × | |||||||||
| 8,12 | × | × | |||||||||
| 0,1,2,3 | × | × | × | × | |||||||
| 0,2,8,10 | × | × | × | ⊗ | |||||||
| 5,7,13,15 | × | × | × | ⊗ | |||||||
| 1,3,5,7 | × | × | × | × |
Кружком обведены члены ядра.
Ядро, таким образом, включает члены -0-0 и -1-1. Для получения минимальной формы, нам нужно перекрыть дополнительно столбцы 1, 3, 12. Для этого можно взять, например, 0,1,2,3 = 00– и 12,13 = 110-:
[
f =
;overline{x_2};;overline{x_4}; vee
{x_2}{x_4} vee
;overline{x_1};;overline{x_2}; vee
{x_1}{x_2};overline{x_3};
]
Карта Карно:
| x₃x₄x₁x₂ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 1 | |
| 01 | 1 | 1 | 1 | |
| 11 | 1 | 1 | 1 | |
| 10 | 1 | 1 |
Привет, Вы узнаете про булевы функции, Разберем основные ее виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое
булевы функции, таблица истинности, сднф , скнф, матрица карно, карты карно, карты карно , настоятельно рекомендую прочитать все из категории Теория конечных автоматов.
булевы функции
Булева функция ƒ(X1, Х2,…,Хn) – n-местная функция, аргументы и значения которой принадлежат множеству {0,1}.
Если логические высказывания могут принимать значения истинно или ложно, то для булевой функции аналогами этих значений будут значения 1 или 0. Для булевых функций справедливы таблицы истинности и основные равносильности алгебры высказываний.
Дополнительно вводятся операции:
Х1|Х2=Х1∧Х2 – штрих Шеффера и
X1↓X2=X1vX2- стрелка Пирса.
|
Х1 |
X2 |
¬X1 |
Х1∧Х2 |
X1vX2 |
X1⇒X2 |
Х1⇔Х2 |
X1| X2 |
Х1 ↓ X2 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
Формы представления булевых функций
Дадим определения, необходимые для задания булевых функций.
Элементарная конъюнкция (дизъюнкция) – это логическое произведение (сумма) любого числа независимых логических переменных, входящих в нее с инверсией или без инверсии не более одного раза. Число входных переменных называется рангом элементарной конъюнкции (дизъюнкции).
Соседними называются элементарные конъюнкции (дизъюнкции) одного и того же ранга, содержащие одни и те же переменные, но отличающиеся знаком инверсии одной из переменных.
Дизъюнкция любого числа элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ), например:
(
U b U
) U (
U c ) U 
или b + c +
Конъюнкция любого числа элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ), например:
(a U b U )U (
UU d) U (U) или (a + b + ) (++ d) ( + ) (далее для упрощения восприятия булевых функций будем использовать второй вид записи).
Теоремы разложения (см. п.п. 2.2) можно применить ко всем переменным, определяющим булеву функцию, тогда, например, используя первую теорему разложения для функции трех переменных f(a,b,c), получим:
f(a,b,c) = a·b·c·f(1,1,1) + ·b·c· f (0,1,1) + a··c·f(1,0,1) + a·b··f(1,1,0) + +··c·f(0,0 ,1) + ·b·· f(0,1,0 ) + a··· f(1,0,0) + ··· f(0,0,0).
Каждая элементарная конъюнкция этого выражения составлена из набора всех переменных в прямом или инверсном виде и некоторого коэффициента, принимающего значение функции, если в ней положить равным единице прямое значение соответствующей переменной, а нулю – инверсное. Нетрудно заметить, что при этом по закону нулевого множества элементы с нулевым значением функции обратятся в ноль и останутся лишь наборы переменных при единичном значении функции, которые далее будем называть конституентами разложения единицы, или минтермами.
Если применить вторую теорему разложения, то получим форму разложения функции на конституенты нуля:
f(a,b,c) = [a+b+c+f(0,0,0) ] [+b+c+f(1,0,0)] [a++c+f(0,1,0] [a+b++ +f(0,0,1)] U [++c+f(1,1,0)] [+b++f(1,0,1)] [a+++f(0,1,1)] [++ ++ f(1,1,1)].
Здесь, по закону универсального множества, каждая элементарная дизъюнкция с единичным значением функции принимает также единичное значение, и в результате остаются только те дизъюнкции переменных, инверсные значения которых определяют нулевое значение функции. Эти дизъюнкции называются конституентами разложения нуля, или макстермами. Такие методы разложения распространяются на функции с любым числом переменных.
Раскладывая булевы функции на конституенты, мы получаем т.н. совершенные формы. Совершенной дизъюнктивной формой (
сднф ) называется дизъюнкция конституентов единицы (минтермов), а совершенной конъюнктивной формой – конъюнкция конституентов нуля (макстермов).
Любую сколь угодно сложную булеву функцию можно преобразовать в ДНФ или КНФ, а затем в совершенные формы (СДНФ или
скнф ). Для этого необходимо прежде всего, используя теорему де Моргáнa, исключить инверсии над функциями, перейдя к формам, в которых имеются инверсии только над одиночными переменными. Затем с использованием законов булевой алгебры привести логические выражения к дизъюнктивной или конъюнктивной формам. Понятие совершенных форм используется при минимизации функций и для определения равносильности. Две булевы функции считаются равносильными, если их СДНФ и СКНФ полностью совпадают.
Таблица 2.1 Одной из самых распространенных форм представления булевых функций является
таблица истинности (таблица состояний).
|
Переменные |
Функция |
Десятичный эквивалент |
|||
|
a |
b |
c |
d |
Y |
|
|
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
2 |
|
0 |
0 |
1 |
1 |
1 |
3 |
|
0 |
1 |
0 |
1 |
1 |
5 |
|
0 |
1 |
1 |
1 |
0 |
7 |
|
1 |
0 |
0 |
0 |
1 |
8 |
|
1 |
0 |
0 |
1 |
0 |
9 |
|
1 |
1 |
0 |
1 |
0 |
13 |
|
1 |
1 |
1 |
1 |
0 |
15 |
Таблица истинности определяет значение функции для всех возможных состояний входных переменных. Поскольку любая логическая переменная может принимать только два значения – 0 и 1, то для булевой функции «n» входных переменных число значений будет определяться показательной функцией 2n.
Функция является полностью определенной, если для любого набора входных переменных известны ее значения (0 или 1).
Булева функция является не полностью определенной (неполной), если есть один или несколько наборов переменных, при которых значение функции не определено (может быть и 0, и 1) или ее не существует. Такие значения функции называются фиктивными(Ф). Пример задания не полностью определенной функции представлен табл. 2.1.
Каждый набор логических переменных представлен двоичным числом n-го разряда, и ему, следовательно, соответствует определенное десятичное число. Десятичное число, соответствующее двоичному набору логических переменных, называется десятичным эквивалентом. Таким образом, булеву функцию можно представить с помощью десятичных эквивалентов:
Y1 = { 0,1,3,5,8} ; Y0 = {2,7,9,13,15}.
Оставшиеся наборы, не заданные таблицей истинности, по всей вероятности, будут фиктивными YФ = {4,6,10,11,12,14}.
По таблице истинности можно получить совершенные формы записи булевых функций. Так, для записи в виде СДНФ нужно из таблицы выбрать единичные наборы переменных, представить их в виде конституентов единицы и произвести их дизъюнкцию.
СДНФ: 
Для записи в форме СКНФ нужно выбрать из таблицы нулевые наборы переменных, проинвертировать переменные в каждом из этих наборов, представить в виде конституентов нуля и произвести их конъюнкцию.
СКНФ: 
Аналогично можно составить СДНФ и СКНФ по десятичным эквивалентам, определяющим булеву функцию.
СДНФ (совершенная дизъюнктивная нормальная форма)
СКНФ (совершенная конъюнктивная нормальная форма)
Каждая логическая функция имеет одну СДНФ и одну СКНФ.
СДНФ логической функции – это дизъюнкция конституент единицы (минтермов), соответствующих наборам входных переменных, для которых функция равна 1.
В общем случае СДНФ можно представить в форме:
где а1, а2, … , аn – двоичный набор,
СКНФ логической функции – это конъюнкция конституент нуля (макстермов), соответствующих входным наборам, для которых функция равна 0.
В общем случае СКНФ можно представить в форме:
Конституента единицы (нуля) – это элементарная конъюнкция (дизъюнкция), в которую входят все n переменных в прямом или инверсном виде.
Форма представления логической функции, описывающей работу элемента, выбирается из соображений минимизации членов уравнения. СДНФ выбирается в случае, если в таблице истинности для логической функции преобладает число состояний логического нуля, СКНФ – логической единицы
Алгоритм перехода от таблицы истинности логической функции к ее записи в виде СДНФ:
- Выбрать в таблице такие входные наборы, на которых функция обращается в единицу;
- Записать конституенты единицы (минтермы) для выбранных входных наборов;
- Полученные минтермы соединить между собой знаком дизъюнкции.
Алгоритм перехода от таблицы истинности логической функции к ее записи в виде СКНФ:
- Выбрать в таблице такие входные наборы, на которых функция имеет нулевые значения;
- Записать конституенты нуля (макстермы) для выбранных входных наборов;
- Полученные макстермы соединить между собой знаком конъюнкции.
|
Совершенные формы |
Формула |
|
Совершенная конъюнктивная нормальная форма(СКНФ)— конъюнкция конституент нуля |
|
|
Совершенная дизъюнктивная нормальная форма(СДНФ) -дизъюнкция конституент единицы |
где а1, а2, … , аn – двоичный набор,
|
ПРИМЕР :
| Таблица 2.1 | ||
| х1х2х3 | F1 | F2 |
| 000 | 0 | 0 |
| 001 | 1 | 0 |
| 010 | 1 | 0 |
| 011 | 0 | 1 |
| 100 | 0 | 0 |
| 101 | 0 | 1 |
| 110 | 0 | 1 |
| 111 | 1 | 1 |
F1=/x1/x2x3 v /x1x2/x3 v x1x2x3
F2=/x1x2x3 v x1/x2x3 v x1x2/x3 v x1x2x3
Другая известная форма носит название совершенной конъюнктивной нормальной формы (СКНФ). Она строится аналогично СДНФ.
Конституента 0 – функция f(x1, x2, … xn) принимающая значение 0 только на единственном наборе.
Конституента нуля записывается в виде элементарной дизъюнкции всех переменных. Каждому набору соответствует своя конституента 0. Например, набору 0110 переменных х1х2х3х4соответствует конституента нуля х1 v /х2 v /х3 v х4. СКНФ представляется как конъюнкция конституент нуля, соответствующих нулевым наборам функции.”
ПРИМЕР. Для рассмотренных функций в табл. 2.1 построим СКНФ:
F1=(x1 v x2 v x3) (x1 v /x2 v /x3) (/x1 v x2 v x3) (/x1 v x2 v /x3) (/x1 v /x2 v x3)
F2=(x1 v x2 v x3) (x1 v x2 v /x3) (x1 v /x2 v x3) (/x1 v x2 v x3)
матрица карно
Матрица Карно представляет собой специально организованные таблицы соответствия, обладающие тем замечательным свойством, что любые две соседние клетки матрицы определяют «соседние» наборы переменных, т.е . Об этом говорит сайт https://intellect.icu . наборы, отличающиеся значением только одной переменной. Клетки, расположенные по краям матрицы, также являются соседними и обладают этим свойством. Это достигается благодаря кодированию столбцов и строк матрицы специальным циклическим кодом Грея.
Еще одним свойством матриц Карно является то, что при увеличении количества переменных на единицу матрица увеличивается вдвое, поскольку число клеток матрицы определяется показательной функцией «2n».
В клетках матрицы, как в таблице истинности, проставляются значения определяемой булевой функции – 0 или 1. Клетки, соответствующие фиктивным состояниям, обычно оставляют пустыми. Например, на рис. 2.1а представлена матрица Карно, определяющая функцию, заданную таблицей истинности (табл. 2.1). По сути дела, матрица Карно – это та же таблица состояний, но в более компактной форме.
На рис. 2.1b, c, d показаны соответственно матрицы Карно для двух, трех и пяти переменных.
a b c
d
Рис. 2.1.
Карта Карно
Карта Карно (куб Карно, диаграмма Карно) — графический способ представления булевых функций с целью их удобной и наглядной ручной минимизации .
Является одним из эквивалентных способов описания или задания логический функций наряду с таблицей истинности или выражениями булевой алгебры. Преобразование
карты карно в таблицу истинности или в булеву формулу и обратно осуществляется элементарным алгоритмом.
Удобство и наглядность такого представления логической функции обусловлено тем, что логические термы, к которым могут быть применены операции попарного неполного склеивания и элементарного поглощения группируются в карте Карно в виде визуально очевидных прямоугольных массивов, содержащих в своих ячейках одинаковые значения (нули и единицы).
Карты Карно можно рассматривать как развертку на плоскость n-мерного булева куба, причем размерность этого гиперкуба совпадает с количеством переменных представляемой функции, а каждая вершина гиперкуба взаимно однозначно соответствует одной клетке карты Карно. Графически карта Карно изображается в виде прямоугольника или квадрата из ячеек, число которых равно {displaystyle 2^{n}}
, причем любые две соседние ячейки по вертикали или горизонтали или, иными словами — в окрестности фон Неймана описывают термы, различающиеся только по одной переменной — с логическим отрицанием и без логического отрицания. Также соседним являются первая и последняя строки, крайний левый и крайний правый столбцы таблицы, поэтому таблица Карно является фактически разверткой логического гиперкуба на поверхность тороида. Возможно построение самых различных карт для одной и той же функции, удовлетворяющих условию: геометрическое соседство ячеек в смысле фон Неймана — логическое соседство термов — то есть с расстоянием Хэмминга между термами соседних ячеек равным 1. Любая из таких таблиц одинаково удобна для минимизации функции, но обычно переменные по строкам и столбцам в карте Карно упорядочивают по рефлексивному коду Грея из-за мнемоничности и наглядности.
Пример карты Карно
Карты Карно были предложены в 1952 году Эдвардом В. Вейчем и усовершенствованы в 1953 году физиком из «Bell Labs» Морисом Карно (Maurice Karnaugh), чтобы упростить проектирование цифровых систем .
Основные принципы
Карта Карно представляет собой таблицу истинности, отформатированную особым образом, пригодным для наглядной ручной минимизации. Результатом минимизации является либо дизъюнктивная нормальная форма (ДНФ), либо конъюнктивная нормальная форма (КНФ). В первом случае работа ведется с клетками карты, где находятся единицы, во втором — с клетками, где находятся нули. В исходной карте, как и в таблице истинности, каждая единица соответствует одному терму cовершенной дизъюнктивной нормальной форме (СДНФ), а каждый ноль — одному терму cовершенной конъюнктивной нормальной форме (СКНФ).
Рядом расположенные группы единиц или нулей на карте Карно объединяют в прямоугольные области или «склейки» размером 
клеток. Каждая такая группа в итоговой логической формуле будет соответствовать одному терму (если считать, что операция логического «ИЛИ» — это «суммирование», а операция логического «И» — это «перемножение», то один терм соответствует одному слагаемому в случае ДНФ, или одному сомножителю в случае КНФ), содержащему {displaystyle n-a-b}
переменных, это группирование обычно называют «склейкой» . Таким образом, работа с картой сводится к выделению оптимального набора нескольких групп единиц (нулей) и преобразование их в логическое выражение.
Принципы минимизации
Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами, содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть поглощению. Например:
Аналогично для КНФ:
Возможность поглощения следует из очевидных равенств:
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для функций многих логических переменных может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.
Булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своем составе не более чем различных термов. Все эти элементарные термы можно представить в виде некоторой структуры, топологически эквивалентной 
-мерному кубу, причем любые два терма, соединенные ребром, пригодны для склейки и поглощения.
На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:
В случае функции трех переменных приходится иметь дело с трехмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трех переменных и соответствующий ей куб.
Как видно из рисунка, для трехмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:
В общем случае можно сказать, что {displaystyle 2^{k}}
термов, принадлежащие одной что {displaystyle k}
-мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются {displaystyle k} переменных.
Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный прием. Куб, представляющий собой структуру термов, разворачивается на плоскость, как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел записанных в лексикографическом порядке (00 01 10 11), а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.
Аналогичным образом можно работать с логическими функциями большего числа переменных.
Стили представления карт Карно[
Традиционно существует несколько стилей представления карт Карно. Часто в шапке и левой колонке проставляются численные значения переменных, подобно тому, как они указаны в таблице истинности (а). В этом стиле наиболее очевидно, что карта Карно является своеобразной формой представления таблицы истинности. Однако клетки карты Карно следуют в несколько ином порядке, чем строки в таблице истинности, так как в таблице истинности принято строки упорядочивать в лексикографическом нарастании двоичных чисел. Например, в карте Карно для четырех переменных порядок следования ячеек карты и строк таблицы истинности совпадет, если переставить местами третий-четвертый столбцы и третью-четвертую строки карты.
Каждая строка таблицы истинности и каждая клетка карты Карно соответствует одному слагаемому ДНФ, поэтому в шапке и левой колонке карты можно указывать вхождения переменных (прямые и инверсные), как они выглядят в СДНФ (б). Существует сокращенный вариант этого стиля представления, где во вспомогательных строках и колонках указывается, в каком виде, прямом или инверсном, представлена каждая переменная в соответствующей строке или столбце карты (в).
Наконец, в некоторых случаях на краях карты линиями указываются столбцы и строки, где соответствующая переменная представлена в прямом виде (г).
а) 
б) 
в) 
г) 
Порядок работы с картой Карно
Исходной информацией для работы с картой Карно является таблица истинности минимизируемой функции. Таблица истинности содержит полную информацию о логической функции, задавая ее значения на всех возможных 2n наборах входных переменных X1 … Xn. Карта Карно также содержит 2n клеток, каждая из которых ассоциируется с уникальным набором входных переменных X1 … Xn. Таким образом, между таблицей истинности и картой Карно имеется взаимно однозначное соответствие, и карту Карно можно считать соответствующим образом отформатированной таблицей истинности.
В данном разделе в качестве примера используется функция четырех переменных, заданная таблицей истинности, изображенной на рис. 2а. Карта Карно для той же функции изображена на рис. 2б.
Рис. 2. Пример работы с картой Карно
Принципы склейки
Прямоугольную область в карте Карно, которая состоит из 2k одинаковых значений (единиц или нулей в зависимости от того, какую форму нужно получить) будем называть склейкой, группой или областью. Распределение всех имеющихся в карте Карно нулей (единиц) по склейкам будем называть покрытием. С целью минимизации булевой функции необходимо построить такое покрытие карты Карно, чтобы количество склеек было минимальным, а размер каждой склейки максимально возможным. Для этого необходимо руководствоваться следующими правилами.
- Склейку клеток одной и той же карты Карно можно осуществлять как по единицам (a), так и по нулям (б). Первое необходимо для получения ДНФ, второе — для получения КНФ.
a) 
б) 
- Склеивать можно только прямоугольные области с числом единиц (нулей), являющимся целой степенью двойки (1, 2, 4, 8, 16, 32… клетки).
- Рекомендуется выбирать максимально возможные области склейки. Если область склейки не является максимально возможной, это не будет ошибкой, однако ДНФ (КНФ) не получится минимальной.
- В некоторых ситуациях в раскладке образуется изолированная единица или ноль, которую невозможно включить в какую-либо область. В этом случае единица (ноль) склеивается «сама с собой». Нельзя оставлять «висячие» единицы (нули), так как это приведет к некорректной записи выражения для функции.
- Все единицы (нули) должны попасть в какую-либо область.
- Область, которая подвергается склейке, должна содержать одинаковые значения — только единицы или только нули.
- Для карт Карно с числом переменных 3 и 4 применимо следующее правило: крайние клетки каждой горизонтали и каждой вертикали граничат между собой и могут объединяться в прямоугольники (топологически карта Карно представляет собой тор). Следствием этого правила является смежность всех четырех угловых ячеек карты Карно для 4 переменных. Для карт Карно с числом переменных менее 3 это правило не имеет смысла, так как крайние клетки и так граничат между собой; для карт Карно с числом переменных более четырех правила смежности более сложные.
- Одна ячейка карты Карно может входить сразу в несколько областей. Это следует из очевидного свойства булевых функций: повторение уже существующего слагаемого (сомножителя) не влияет на функцию:
- Не следует без нужды включать клетку во все возможные склейки, это не является ошибкой, но усложняет формулу. С точки зрения минимальности ДНФ (КНФ) число склеек должно быть как можно меньше (каждая дополнительная склейка порождает дополнительный терм), а число клеток в склейке должно быть максимально возможным (чем больше клеток в склейке, тем меньше переменных содержит терм. Склейка размером 2k клеток порождает терм с n–k переменными) .
- В отличие от СДНФ и СКНФ, ДНФ и КНФ не всегда единственны. Для некоторых функций существует несколько эквивалентных друг другу ДНФ (КНФ), которые соответствуют разным способам покрытия карты Карно прямоугольными областями. Очень часто две различные ДНФ (КНФ) имеют одинаковую сложность, что не позволяет сделать однозначный выбор минимальной формулы.
Карты с неопределенными значениями
На практике встречаются случаи, когда при некоторых значениях аргументов булева функция не определена. Например, булева функция описывает цифровое устройство, у которого некоторые сочетания входных сигналов физически невозможны или же при некоторых значениях входных сигналов реакция устройства не имеет значения. В таких случаях говорят о «неопределенных условиях», а функция такого вида называется «частично определенной» или просто «частичной» .
На рисунке показано цифровое устройство F с четырьмя двоичными входными сигналами 
. Входными сигналами могут быть показания датчиков, работающих на замыкание и следовательно имеющих только два значения — «включено» (1) и «выключено» (0). Предположим, что в силу особенностей конструкции устройства 2-й и 4-й датчики не могут сработать одновременно, то есть сочетание сигналов 
физически невозможно. В этом случае значение функции в четырех клетках карты Карно не имеет значения, что условно показано символом «×».
Такие клетки могут произвольным образом включаться в любые склейки, а также могут не включаться ни в какие склейки, то есть их по желанию можно доопределять и как 1, и как 0 .
Преобразование карты в формулу
Описание
Карта Карно может быть построена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности, представленная в виде матрицы в 2-мерном виде.
Каждая клетка этой карты соответствует одной строке в классической таблице истинности и обозначается строкой переменных с инверсиями и без инверсий. Например, пусть в таблице истинности для функции 4 переменных 
одна из строк имеет вид: 0 1 1 0 | 1, тогда клетка в карте Карно, соответствующая этой строке, будет иметь имя 
и в этой клетке ставится 1. Указание имен клеток в карте Карно обычно выполняется дополнительной строкой сверху и дополнительным столбцом слева.
Существенно, что в карте Карно соседние клетки обязательно имеют соседние, в смысле расстояния Хэмминга коды, то есть расстояние Хэмминга между соседними клетками равно 1, и различаются только состоянием — с инверсией или без, одной и только одной из переменных. Соседними клетками считаются клетки, примыкающие друг к другу стороной, также соседними клетками считаются клетки крайнего левого и крайнего правого столбцов и клетки первой и последней строк. Таком образом, карта Карно на плоскости топологически эквивалентна поверхности тора в трехмерном пространстве, или гипертору в пространстве с размерностью на 1 больше размерности соответствующей многомерной карты Карно.
Так как перестановка переменных в логической функции не изменяет саму функцию, то есть, например, 
или, что то же самое, — перестановка столбцов переменных в таблице истинности не изменяет функцию, существует несколько вариантов отображения таблицы истинности на карту Карно с сохранением «соседства» клеток. Но практически наиболее часто карту Карно заполняют, используя нарастающий код Грея для обозначения строк и столбцов. Такой подход гарантирует порождение карты Карно с избеганием субъективных ошибок.
При заполнении карты на пересечении строки и столбца проставляется соответствующее значение из таблицы истинности — 0 или 1. После того как карта заполнена, приступают к минимизации.
Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки, которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ).
- Объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала {displaystyle 2^{n}} ( целое число = 0…{displaystyle infty }) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули;
- Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
- Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну;
- Область должна быть как можно больше, а количество областей как можно меньше;
- Области могут пересекаться;
- Возможно несколько вариантов покрытия.
) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули;Далее берем первую область и смотрим, какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных; если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берем следующую область, выполняем то же самое, что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например (для Карт на 2 переменные):
 |
 |
 |
 |
 |
 |
 |
 |
|||||||
 |
 |
 |
 |
 |
 |
 |
 |
|||||||
 |
 |
 |
 |
 |
 |
|||||||||
 |
|
|
|
|
|
|||||||||
 |
 |
 |
 |
 |
 |
|||||||||
 |
 |
Для КНФ все то же самое, только рассматриваем клетки с нулями, неменяющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так, для Карты Карно на рис. 1, выражение в формате ДНФ будет иметь вид:
В формате КНФ:
Так же из ДНФ в КНФ и обратно можно перейти, использовав Законы де Моргана.
Примеры
Пример 1
У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдет гулять на улицу, тогда и только тогда, когда ему разрешат хотя бы двое родственников.
Для краткости обозначим родственников Коли через буквы:
мама — X1
папа — X2
дедушка — X3
бабушка — X4
Условимся обозначать согласие родственников единицей, несогласие — нулем. Возможность пойти погулять обозначим буквой f, Коля идет гулять — f = 1, Коля гулять не идет — f = 0.
Составим таблицу истинности:
Перерисуем таблицу истинности в 2-мерный вид:
Переставим в ней строки и столбцы в соответствии с кодом Грея (последний и предпоследний столбец меняют местами). Получили Карту Карно:
Заполним ее значениями из таблицы истинности (первая строка не соответствует таблице истинности, так как f=0 и разрешения на гулять нет):
Минимизируем в соответствии с правилами:
- Все области содержат 2^n клеток;
- Так как Карта Карно на четыре переменные, оси располагаются на границах Карты и их не видно (подробнее смотри пример Карты на 5 переменных);
- Так как Карта Карно на четыре переменные, все области симметрично осей — смежные между собой (подробнее смотри пример Карты на 5 переменных);
- Области S3, S4, S5, S6 максимально большие;
- Все области пересекаются (необязательное условие);
- В данном случае рациональный вариант только один.
Теперь по полученной минимальной ДНФ можно построить логическую схему:
Из-за отсутствия в наличии шестивходового элемента ИЛИ, реализующего функцию дизъюнкции, пришлось каскадировать пяти- и двух-входовые элементы (D7, D8).
Составим мин. КНФ:
См. также
- ДНФ
- КНФ
- СДНФ
- СКНФ
- Минимизация логических функций методом Куайна
- Минимизация комбинационных схем
- Метод Куайна — Мак-Класки
Надеюсь, эта статья об булевы функции, была вам интересна и не так слона для восприятия как могло показаться, удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое булевы функции, таблица истинности, сднф , скнф, матрица карно, карты карно, карты карно
и для чего все это нужно, а если не понял, или есть замечания,
то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории
Теория конечных автоматов
Диана Загировна Филиппенкова
Эксперт по предмету «Информатика»
Задать вопрос автору статьи
Нормальная форма логической формулы не содержит знаков импликации, эквивалентности и отрицания неэлементарных формул.
Нормальная форма существует в двух видах:
-
конъюнктивная нормальная форма (КНФ) — конъюнкция нескольких дизъюнкций, например, $left(Avee overline{B}vee Cright)wedge left(Avee Cright)$;
-
дизъюнктивная нормальная форма (ДНФ) — дизъюнкция нескольких конъюнкций, например, $left(Awedge overline{B}wedge Cright)vee left(Bwedge Cright)$.
СКНФ
Совершенная конъюнктивная нормальная форма (СКНФ) — это КНФ, удовлетворяющая трем условиям:
-
не содержит одинаковых элементарных дизъюнкций;
-
ни одна из дизъюнкций не содержит одинаковых переменных;
-
каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.
Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.
Правила построения СКНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием.
СДНФ
Совершенная дизъюнктивная нормальная форма (СДНФ) — это ДНФ, удовлетворяющая трем условиям:
-
не содержит одинаковых элементарных конъюнкций;
-
ни одна из конъюнкций не содержит одинаковых переменных;
-
каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.
Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.
Правила построения СДНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.
Примеры нахождения СКНФ и СДНФ
Пример 1
Записать логическую функцию по ее таблице истинности:
Рисунок 1.
Решение:
Воспользуемся правилом построения СДНФ:
Рисунок 2.
Получим СДНФ:
[Fleft(x_1, x_2, x_3right)=left(overline{x_1}wedge overline{x_2}wedge overline{x_3}right)vee left(overline{x_1}wedge overline{x_2}wedge x_3right)vee left(x_1wedge overline{x_2}wedge overline{x_3}right)vee left(x_1wedge overline{x_2}wedge x_3right)vee left(x_1wedge x_2wedge x_3right)]
Воспользуемся правилом построения СКНФ:
Рисунок 3.
Получим СКНФ:
[Fleft(x_1, x_2, x_3right)=left(x_1vee overline{x_2}vee x_3right)wedge left(x_1vee overline{x_2}vee overline{x_3}right)wedge left(overline{x_1}vee overline{x_2}vee x_3right)]
«Построение СКНФ и СДНФ по таблице истинности» 👇
Пример 2
Функция задана таблицей истинности:
Рисунок 4.
Представить эту функцию в виде СДНФ и СКНФ.
Решение:
-
Запишем логическую функцию в СДНФ. Для удобства решения добавим к таблице вспомогательный столбец.
Используя правило составления СДНФ не забываем вводить знак отрицания для переменных со значением 0. Инвертировать нулевые значения переменных обязательно, т.к. иначе они превратят значения конъюнкций в нули основной функции.
Рисунок 5.
Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:
[Fleft(x_1,x_2,x_3,x_4right)=left(overline{x}wedge overline{y}wedge zwedge fright)vee left(overline{x_1}wedge x_2wedge overline{x_3}wedge overline{x_4}right)vee left(overline{x_1}wedge x_2wedge x_3wedge x_4right)vee left(x_1wedge overline{x_2}wedge overline{x_3}wedge overline{x_4}right).]
-
Запишем логическую функцию в СКНФ.
Используя правило составления СКНФ не забываем вводить знак отрицания для переменных со значением 1. Инвертировать единичные значения переменных обязательно, т.к. иначе они превратят значения дизъюнкций в единицы основной функции.
Рисунок 6.
Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:
[Fleft(x_1,x_2,x_3,x_4right)=left(x_1vee x_2vee x_3vee x_4right)wedge left(x_1vee x_2vee x_3vee overline{x_4}right)wedge left(x_1vee x_2vee overline{x_3}vee x_4right)wedge left(x_1vee overline{x_2}vee x_3vee overline{x_4}right)wedge left(x_1vee overline{x_2}vee overline{x_3}vee x_4right)wedge left(overline{x_1}vee x_2vee x_3vee overline{x_4}right)wedge left(overline{x_1}vee x_2vee overline{x_3}vee x_4right)wedge left(overline{x_1}vee x_2vee overline{x_3}vee overline{x_4}right)wedge left(overline{x_1}vee overline{x_2}vee x_3vee x_4right)wedge left(overline{x_1}vee overline{x_2}vee x_3vee overline{x_4}right)wedge left(overline{x_1}vee overline{x_2}vee overline{x_3}vee x_4right)wedge left(overline{x_1}vee overline{x_2}vee overline{x_3}vee overline{x_4}right).]
Находи статьи и создавай свой список литературы по ГОСТу
Поиск по теме
