Как составить мкнф

Занятие 17. Тема «Минимизация функций с помощью карт Карно»

План лекции:

1. Понятие карты Карно

2. Виды карт Карно и метод их заполнение

3. Принципы склейки

4. Правило нахождения МДНФ и МКНФ

Понятие карты Карно

МДНФ – минимальная дизъюнктивная нормальная форма

МКНФ – минимальная конъюнктивная нормальная форма

Метод карт Карно позволяет быстро получить минимальные ДНФ и КНФ.

Карта Карно – это таблица, каждая клетка в ней соответствует набору переменных булевой функции в её таблице истинности. Строки и столбцы карты обозначаются таким образом, чтобы любые соседние клетки по строкам или по столбцам отличались бы между собой значением только одной переменной. Это сделано для того, чтобы было бы возможно применить закон склеивания.

Виды карт Карно и метод их заполнение

Карта Карно для 2-х переменных – квадратная таблица размером (4 ячейки)

х1 х2	0	1
0
1

Ячейки заполняются 0 или 1, полученные в последнем столбце таблицы истинности, соответствующие наборам 00, 01, 10, 11.

Карта Карно для 3-х переменных – прямоугольная таблица размером (8ячеек). Каждая ячейка соответствует наборам 000, 001, 010, 011, 100, 101, 110, 111.

х2х3 х1	00	01	11	10
0
1

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

Карта Карно для 4-х переменных – квадратная таблица размером (16 ячеек). Каждая ячейка соответствует наборам 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.

Карта Карно для 5-х переменных – прямоугольная таблица размером (32 ячейки).

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

Принципы склейки

• Склейку клеток карты Карно можно осуществлять по единицам (если необходимо получить  МДНФ) или по нулям (если требуется МКНФ).

• Склеивать можно только прямоугольные области с числом единиц (нулей) 2ⁿ, где n — целое число.

• Область, которая подвергается склейке, должна содержать только единицы (нули).

• Крайние клетки каждой горизонтали и каждой вертикали также граничат между собой и могут объединяться в прямоугольники. Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для N=4. Если во всех четырёх угловых ячейках стоят единицы (нули), они могут быть объединены в квадрат.

• Все единицы (нули) должны попасть в какую-либо область.

• С точки зрения МДНФ (МКНФ), число областей должно быть как можно меньше (каждая область представляет собой терм), а число клеток в области должно быть как можно больше (чем больше клеток в области, тем меньше переменных содержит терм).

• Области могут пересекаться.

• Область должна располагаться симметрично оси (оси располагаются через каждые четыре клетки) Несмежные области, расположенные симметрично оси, могут объединяться в одну.

Правило нахождения МДНФ (МКНФ).

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

Функции могут быть записаны не формулой, а аналитическим путем, то есть содержать номера наборов из таблицы истинности дизъюнктивно ( работает с 1) или конъюнктивно (& работает с 0). Например, Y= (1,4,8,10,12,14,15). Это означает, что карта Карно из 4-х переменных заполняется единицами в ячейках с номерами 1,4,8,10,12,14,15, а остальные ячейки заполняются нулями.

Пример.

x	y	z							B
0	0	0	1	1	1	1	1	0	1
0	0	1	1	1	0	1	1	0	1
0	1	0	1	0	1	1	1	0	1
0	1	1	1	0	0	0	0	0	0
1	0	0	0	1	1	1	0	0	0
1	0	1	0	1	0	1	0	1	1
1	1	0	0	0	1	1	0	0	0
1	1	1	0	0	0	0	0	1	1

Для нахождения МДНФ

– Составим карту для 3-х переменных и заполним ее 1 из последнего столбца таблицы истинности.

уz х	00	01	11	10
0	1	1		1
1		1	1

– Выделим покрытия по принципам склейки

– Для каждого покрытия составляем элементарную конъюнкцию, зачеркивая столбец с разными значениями и записывая оставшие переменные с инверсией, если все 0 и без инверсии, если все 1.

x y z x y z x y z

0 0 0 0 0 1 1 0 1

0 1 0 1 0 1 1 1 1

МДНФ: у=

Для нахождения МКНФ

– Составим карту для 3-х переменных и заполним ее 0 из последнего столбца таблицы истинности.

уz х	00	01	11	10
0			0
1	0			0

– Выделим покрытия по принципам склейки

– Для каждого покрытия составляем элементарную дизъюнкцию, зачеркивая столбец с разными значениями и записывая оставшие переменные с инверсией, если все 1 и без инверсии, если все 0.

x y z x y z

1 0 0 0 1 1

1 1 0

МКНФ: у=

Задание для самостоятельного выполнения

1. составить карту Карно и найти МДНФ и МКНФ для следующих функций

а)

б)

1. Ответить на контрольные вопросы:

1. Что называется картой Карно?

2. Какие разновидности карт Карно есть?

3. Как заполняются карты Карно?

4. Для чего нужны принципы склейки?.

5. Чем отличается правило нахождения МДНФ от правила нахождения МКНФ?

6. Пользуясь этим и теоретическим материалом учебника М.С. Спирина «Дискретная математика» глава 4 п.4,6,3 стр.180, выполнить 1 задание.

Выполненное задание отправить на адрес электронной почты преподавателя. Имя файла – фамилия студента и номер занятия. (например Петров-17)

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

Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью карт Карно.

Для этого нули карты Карно последовательно покрываются прямоугольниками 4х2, 2х4, 2х2, 4х1, 1х4, 2х1, 1х2 и 1х1. Затем строятся элементарные дизъюнкты МКНФ.

Формула[править]

Введём обозначения:

n — число аргументов функции;

k — число прямоугольников на карте Карно;

(x₁, x₂, …, x_n) — набор аргументов функции;

f(x₁, x₂, …, x_n) — логическая функция;

P_t(x₁, x₂, …, x_n) = {(i₁, l₁); (i₂, l₂); …; (i_m, l_m)} — множество клеток t-прямоугольника;

P_t(x₁, x₂, …, x_n) = 0 — множество клеток t-прямоугольника из нулей;

arg_j(i, l) — значение аргумента x_j в наборе аргументов для клетки (i, l);

f_МКНФ(x₁, x₂, …, x_n) — МКНФ логической функции.

Невозможно разобрать выражение (синтаксическая ошибка): {displaystyle f_{МКНФ}(x_1,x_2,ldots,x_n)=bigcaplimits_{t=1}^kbigcuplimits_{begin{smallmatrix}arg_jleft[P_t(x_1,x_2,ldots,x_n)=0right]=0 & text{или}\arg_jleft[P_t(x_1,x_2,ldots,x_n)=0right]=1 &end{smallmatrix}}y_j,}
где

Примеры построения МКНФ[править]

Пример 1[править]

Строим карту Карно для функции трёх переменных f(x₁, x₂, x₃):

Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.

P₁(x₁,x₂,x₃) = {(1,1);(2,1)}

P₂(x₁,x₂,x₃) = {(2,1);(3,1)}

P₃(x₁,x₂,x₃) = {(2,1);(2,2)}

Невозможно разобрать выражение (синтаксическая ошибка): {displaystyle f_{МКНФ}(x_1,x_2,x_3)=(x_1 lor x_3)land(bar{x}_2 lor x_3)land(x_1 lor bar{x}_2)}

Пример 2[править]

Строим карту Карно для функции четырёх переменных

Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.

Пример 3[править]

Строим трёхмерную карту Карно для функции пяти переменных

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

Другие формы:[править]

• Совершенная дизъюнктивная нормальная форма (СДНФ);
• Совершенная конъюнктивная нормальная форма (СКНФ);
• Минимальная дизъюнктивная нормальная форма (МДНФ);
• Минимальная конъюнктивная нормальная форма (МКНФ);
• Алгебраическая нормальная форма (АНФ).

Ссылки[править]

• Участник:Logic-samara

Алгоритм поиска
МКНФ с использованием карт Карно:

1. Составить карту
   Карно.

2. Обвести контурами
   нулевые ячейки.

3. При записи МКНФ
   переменные, образующие контур,
   инвертируются, объединяются в дизъюнкции,
   а затем – в конъюнкции.

Пример.
Найти
МКНФ функции, заданной таблицей, с
помощью карты Карно.

x	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
y	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
z	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
t	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
f	0	1	0	0	1	0	1	1	0	0	1	1	0	0	1	1

8.5. Минимизация логических функций, представленных в конъюнктивной форме, с использованием правил, аналогичных правилам минимизации логических функций в дизъюнктивной форме

КНФ

КСНФ

СокКНФ

ТКНФ

МКНФ

a)
При табличном задании записать функцию
в виде конъюнкции конституент нуля,
соответствующих наборам, на которых
функция равна нулю. Если функция задана
произвольной КНФ, то применить формулы
развертывания:

b)
Выполнить все возможные операции
неполного склеивания и поглощения:

c)
и d) Построить матрицу,
столбцы которой образуют конституенты
нуля КСНФ, а строки – члены СокКНФ. В
МКНФ должно входить минимальное число
строк, перекрывающих все столбцы.

Пример.
Функция

задана таблицей

x	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
y	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
z	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
t	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
f	0	1	0	0	1	0	1	1	0	0	1	1	0	0	1	1

1
– 2 *
2
– 3 *
3
– 4 4 – 5

1 – 3 2 – 4 3 – 5 4 – 6

1 – 4 2 – 5 3 – 6 4 –
7

1
– 5 *
2
– 6 3 – 7 4 – 8 *

1 – 6 2 – 7 3 – 8

1 – 7 2 – 8

1 – 8

5
– 6 *
6
– 7 7 – 8 *

5
– 7*
6
– 8*

5 – 8

1
– 2 2 – 3 3 – 4 4 – 5 5 – 6 6 – 7 *
7
– 8

1 – 3 2 – 4 3 – 5 4 – 6 5 –
7 6 – 8

1
– 4 2 – 5 3 – 6 4 – 7 5 – 8 *

1 – 5 2 – 6 3 – 7 4 – 8

1 – 6 2 – 7 3 – 8

1 – 7 2 – 8

1 – 8

								
		
					
			
							

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Схемотехника. Минимизация логических функций

Минимизация логических функций является одной из типовых задач в процессе обучения схемотехнике. Посему считаю, что такая статья имеет место быть, надеюсь Вам понравится.

Зачем это нужно?

Сложность логической функции, а отсюда сложность и стоимость реализующей ее схемы (цепи), пропорциональны числу логических операций и числу вхождений переменных или их отрицаний. В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок.

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

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

Минимизация логических функций при помощи карт Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

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

Возможность поглощения следует из очевидных равенств

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

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

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

В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.

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

В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.

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

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

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

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

1. Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2ⁿ (n целое число = 0…) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
2. Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
3. Не смежные области расположенные симметрично оси(ей) могут объединяться в одну;
4. Область должна быть как можно больше, а кол-во областей как можно меньше;
5. Области могут пересекаться;
6. Возможно несколько вариантов накрытия.

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

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

В формате КНФ:

Операция штрих Шеффера

Заметим, что эта функция дуальна по отношению к f₈, поэтому все свойства являются по существу дуально вытекающими из рассмотренных.

(запись функций по нулям)

на основе принципа суперпозиции:

x₁ | x₂ | . . . | x_n = x₁x₂…x_n

Рассмотрим некоторые эквивалентности:

x₁ | x₂ | x₃ = (x₁ x₂)| x₃ = x₁| (x₂ x₃)

x₁ | x₂ | x₃| x₄ = (x₁ x₂)| (x₃ x₄)

Сформулируем правила перехода от ДНФ функции к выражению с использованием операции ” Штрих Шеффера “.

1. заменить все операции дизъюнкции на операции Шеффера
2. заменить все операции конъюнкции на операции Шеффера
3. группы букв, которые соответствуют дизъюнктивным членам, заключить в скобки.

Пример:

То же самое можно утверждать относительно минимальной формы.

В заключение необходимо отметить, что в настоящее время вопросы синтеза функций в одноэлементном базисе приобретают большое значение, так как соответствующие элементы используют операцию Пирса и Шеффера. Однако в полной мере теоретически методы синтеза разработаны не столь детально, как это сделано в базисе “и”, “или”, “инверсия”.

Минимальные конъюнктивные нормальные формы

Как было отмечено, для получения минимальной формы функции нужно построить как МДНФ так и МКНФ.

Рассмотрим построение МКНФ.

В основном методы получения МКНФ аналогичны методам получения МДНФ и поэтому сформулируем лишь правила получения МКНФ:

1. Представить ФАЛ в СКНФ. Если она задана таблицей, то произвести запись функции по нулям, как это было сформулировано ранее. Если дана СДНФ, то из нее легко получить СКНФ:

   ,

   т.е. нужно функцию представить в виде конъюнкции недостающего числа дизъюктивных членов с соответсвенно расставлеными отрицаниями.

2. При задании функции в произвольной конъюктивной форме, применяя

   формулы развертывания:

   

   . . . . . . . . . . . .,

   получить СКНФ.

3. Выполнить все операции неполного склеивания:

   

   и поглощения: , получить сокращенную КНФ.

4. Применить любой из методов минимизации: испытание членов, диаграммы Вейча, метод импликантных матриц.
   • При выполнении метода испытания членов необходимо каждый конъюктивный член приравнять нулю. Найти значения аргументов, которые обращают его в нуль, удалить его из выражения функции и найти значение функции при найденных значениях аргументов. Если функция обратится в нуль, то конъюктивный член является лишним.

     По возможности отбросить одновременно несколько членов, поступить как и при минимизации функции ДНФ.

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