Как найти минимальную днф метод карт

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

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

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

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

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

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

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

Карта Карно — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку 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 выражение в формате ДНФ будет иметь вид:

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

Минимальная ДНФ булевой функции

На этой странице вы найдете готовые примеры по булевой алгебре, связанные с минимизацией нормальных формул булевой функции (обычно это задания вроде «найти минимальную ДНФ…»). Помимо минимальной ДНФ, в процессе решения могут быть найдены тупиковые и сокращенные ДНФ, ядерные импликанты (и ядро функции), функция Патрика и т.п.

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

Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.

Другие примеры решений о булевых функциях:

Задачи и решения о минимизации ДНФ булевых функций

Задача 1. Применяя равносильные преобразования привести булеву функцию $f=(bar x to bar y)to (yz to bar xz)$ к минимальной ДНФ.

Задача 2. Для заданной логической функции:
$$F= overline {(bar A vee Bcdot bar C)} cdot overline{( overline {(B downarrow C)}cdot D} $$
— найти дизъюнктивную нормальную форму;
— составить таблицу истинности и построить диаграмму Карно;
— получить минимальную дизъюнктивную нормальную форму;
— от минимальной дизъюнктивной нормальной формы перейти к конъюнктивной нормальной форме.

Задача 3. Для функции $f(x_1,x_2,x_3,x_4)$, заданной списком номеров наборов из $Nf$ методом Квайна найти сокращенную и минимальные ДНФ.
Список номеров: 0,1,2,3,6,7,8,9,11,15.

Задача 4. С помощью карт Карно найдите сокращенную, все тупиковые и минимальные ДНФ или КНФ булевой функции f(x1,x2,x3,x4), заданной вектором своих значений.
(1100 0101 0011 0011)

Задача 5. Найти минимальные КНФ булевых функций, зависящих от аргументов $A, B, C, D$. В квадратных скобках указаны неопределенные состояния

$$f = ( 1, 2, 5, 6, 14), [4, 9, 11, 12, 15].$$

Задача 6. Найти минимальные ДНФ и КНФ булевых функций, зависящих от аргументов $A, B, C, D$

$$f = (1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15).$$

Задача 7. Для булевой функции $f(x, y, z)$ найти методом преобразования минимальную ДНФ. По таблице истинности построить СКНФ. По минимальной ДНФ построить релейно-контактную схему.

$$f(x,y,z)=(bar x vee bar y)wedge (bar y vee bar z) to (bar x vee bar z)$$

Задача 8. Переключательная функция от трех аргументов задана номером в десятичной системе счисления. Получить номер ПФ в двоичном, восьмеричном и шестнадцатеричном кодах, таблицу истинности, определить СДНФ, СКНФ, символическую форму функции с восьмеричной нумерацией наборов. Минимизировать функцию по кубу соседних чисел и карте Карно. Определить свойства функции. Реализовать функцию переключательной схемой на функциональных элементах в базисах а) И, ИЛИ, НЕ, б) И-НЕ, в) ИЛИ-НЕ.

Задача 9. Для булевой функции f, заданной в таблице 1:
а) найти сокращённую ДНФ;
б) найти ядро функции;
в) получить все тупиковые ДНФ и указать, какие из них являются минимальными;
г) на картах Карно указать ядро и покрытия, соответствующие минимальным ДНФ.

Задача 10. Двумя способами: с помощью карты Карно и методом Квайна найти сокращенную, ядровую и все минимальные дизъюнктивные нормальные формы булевой функции $f$, заданной вектором значений 0101101001001110. Построить минимальную функциональную (над системой ${vee, wedge, neg}$ ) и минимальную контактную схемы для функции $f$.

Решение задач о минимальной ДНФ на заказ

Выполняем для студентов очников и заочников решение заданий, контрольных и практических работ о минимизации булевых функций. Также оказываем помощь в сдаче тестов. Подробное оформление, таблицы, графики, пояснение, использование специальных программ при необходимости. Стоимость примера от 150 рублей, оформление производится в Word, срок от 2 дней.

Сокращенная и минимальная ДНФ

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

Минимальная ДНФ — такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.

Сокращенная ДНФ

Определение:

Сокращенная ДНФ (англ. reduced disjunctive normal form) — форма записи функции, обладающая следующими свойствами: любые два слагаемых различаются как минимум в двух позициях, ни один из конъюнктов не содержится в другом.

Например:
содержится в .

Функцию можно записать с помощью сокращенной ДНФ не единственным способом.

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

Минимальная ДНФ

Определение:

Минимальная ДНФ (англ. minimal disjunctive normal form) — такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.

Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная — минимальна.
Например, запись является минимальной ДНФ для медианы (она же сокращенная, как видно в примере выше); а запись — не минимальная, но сокращенная ДНФ.

Минимизация ДНФ

Рассмотрим несколько способов минимизации дизъюнктивных нормальных форм:

Визуализация гиперкубами

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

Описание алгоритма	Пример
Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины, то в эту вершину мы помещаем закрашенный чёрным кружок.	Вершине с координатами соответствует конъюнкт , он равен единице при и )
В противном случае мы помещаем в вершину закрашенный белый кружок.	Для такой ДНФ: мы получим следующий гиперкуб (см. рисунок)
Далее обработка гиперкуба идёт следующим образом: пока у нас есть незакрашенные вершины, мы выбираем грань, либо вершину, либо ребро, на которых больше всего закрашенных чёрным вершин и ещё не обработанных вершин.
Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой.	Грань, на которой лежат закрашенные вершины и мы можем записать как конъюнкт .
Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами	Ребро, соединяющее закрашенные вершины и мы можем записать как конъюнкт .
И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный .	Вершину мы бы переписали как конъюнкт .

В итоге нашу изначальную ДНФ можно записать как .

Карты Карно

Построим следующую таблицу , где — число переменных:

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

Теперь покрываем прямоугольниками (длины сторон которых — степени двойки ()) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки.

Для карт Карно на примере это выглядело бы так:

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

То есть, в этом примере получаем: 

Метод Квайна

Этот метод основан на применении двух основных операций:

• Операция попарного неполного склеивания:

• Операция элементарного поглощения:

(где — некоторая элементарная конъюнкция, то есть конъюнкт, в который каждая из переменных входит не более одного раза)

Например:

Пусть , тогда:

• Операция попарного неполного склеивания:

• Операция элементарного поглощения:

Метод состоит в последовательном выполнении всех возможных склеиваний и затем всех поглощений частей СДНФ пока это может быть осуществимо.

Описание алгоритма

• Исходным является множество пар вида или
• Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины (где — число аргументов).
• Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины (общая часть «» имеет длину )
• В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества (по длине):
  • подмножество элементарных конъюнкций длины (оставшиеся)
  • подмножество элементарных конъюнкций длины
• Если множество элементарных конъюнкций длины не пусто, то заново выполняются операции неполного попарного склеивания и элементарного поглощения для конъюнкций длины и так далее.

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

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

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

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

Пример

Функция от четырёх аргументов задана следующей таблицей:

Набор
Значение исходной функции

Проведём операции неполного склеивания и поглощения:

№	Элементарная конъюнкция	Поглощение

№ склеивания	Результат

На данном шаге все элементы вида или участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому элементы сокращённой ДНФ на этом шаге не получены.

№	Элементарная конъюнкция	Поглощение

№ склеивания	Результат

На данном этапе получаем элементы сокращённой ДНФ и

№	Элементарная конъюнкция	Поглощение

Обе элементарные конъюнкции на данном шаге являются элементами сокращённой ДНФ.

В результате выполнения алгоритма мы получаем следующую сокращённую ДНФ:

Переход от сокращённой формы к минимальной:

• Единицы ДНФ, покрываемые элементами или обозначаются «+». Пары и , попадающие в ядро помечаются «*».
• Единицы функции, которые покрываются только каким-то одним конъюнктом из системы элементов сокращённой ДНФ, помечаются “>”.
• Единицы функции, покрываемые ядром, но не покрываемые только каким-то одним конъюнктом из системы элементов сокращённой ДНФ помечаются “>>”.

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

См. также

• ДНФ
• КНФ

Источники информации

• Минимизация логических функций методом Куайна — Википедия
• Метод Квайна
• Карта Карно — Википедия
• Минимизация булевых функций в классе ДНФ
• Минимизация ДНФ методом Квайна

Определение.
Функцияотnаргументовназывается булевой функцией (или функцией
алгебры логики), если каждому наборуона ставит в соответствие число.

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

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

Карта
Карно для функции f(x,y,z) = (00110001)
представлена на рисунке.

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

Внутренняя
часть карты состоит из 8 клеток, в каждой
из которых записано значение функции
на определенном наборе значений
аргументов. Данная функция обращается
в единицу только на трех наборах –
(010), (011) и (110), поэтому её СДНФ имеет вид
.
Каждое из трех слагаемых в этой сумме
соответствует определенной клетке,
содержащей единицу. Например, слагаемоеобращается в единицу на наборе (010), ему
соответствует клетка, содержащая единицу
и стоящая на пересечении второго столбца
и первой строки карты Карно (на рисунке
эта клетка закрашена). Однако, если две
соседние клетки, отвечающие наборам
(010) и (011), объединить в прямоугольник,
то в СДНФ дизъюнкцию первых двух слагаемых
можно будет заменить одним слагаемым.
В результате получаем более простую
ДНФ.
Если же область единиц функции «покрыть»
горизонтальным прямоугольником из двух
соседних клеток (010) и (110) и клеткой (011),
то получим формулу,
также являющуюся ДНФ исходной функции.
Однако минимальная ДНФ соответствует
покрытию области единиц сразу обоими
прямоугольниками и имеет вид.

Чтобы
получить минимальную ДНФ, надо найти
такое покрытие области единиц в карте
Карно, которое удовлетворяет следующим
требованиям:

• покрывающие
  фигуры – это квадраты или прямоугольники,
  каждый из которых стоит из 1, 2, 4 или 8
  клеток;

• фигуры
  могут пересекаться, но их количество
  должно быть минимально возможным (т.е.
  чем меньше разных фигур используется,
  тем проще получается ДНФ);

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

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

27. Замкнутые классы булевых функций т0, т1, l, лемма о нелинейной функции.

Определение.
Функцияотnаргументовназывается булевой функцией (или функцией
алгебры логики), если каждому наборуона ставит в соответствие число.

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

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

Определение.
Т₀
— класс всех булевых функций, сохраняющих
константу
0, содержит ровно
различных функций отn
переменных. Является замкнутым классом.

Определение.Т₁
— класс булевых функций, сохраняющих
константу 1, содержит ровно
различных функций отn
переменных. Является замкнутым классом.

Определение.
Булева функция
называетсялинейной
функцией, если она представима линейным
полиномом Жегалкина, т.е. в виде суммы
,
где,i=0,1,…,n.
Класс всех линейных функций – L,
является замкнутым классом. Количество
различных линейных функций от n
переменных равно
.

Лемма.Из любой нелинейной функции, подставляя
вместо её аргументов константы 0 и 1, а
также функциии,
можно получить конъюнкциюили дизъюнкцию.

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

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

Занятие 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)