Как найти ядровую днф

i) Составляется таблица, в левом столбце которой выписывают импликанты, а в верхней строке – исходные ЭК.

ii) Таблица заполняется следующим образом: на пересечении ставится «+», если соответствующая ЭК поглощается импликантой, в противном случае клетка оставляется пустой.

iii) Заполненная таблица просматривается: ищутся столбцы, содержащие только один «+». Соответствующе «+» импликанты – ядровые, они входят в МДНФ.

iv) Затем из таблицы вычеркиваются сначала строки, содержащие ядровые импликанты, затем столбцы, содержащие «+» от ядровых импликант.

v) Оставшаяся часть таблицы анализируется на предмет выделения тупиковых ДНФ. Принцип следующий: набор импликант каждой тупиковой ДНФ должен покрывать все оставшиеся «+» таблицы.

Из найденных тупиковых ДНФ тривиальным алгоритмом (перебором) выбираются минимальные (их может быть несколько). Дизъюнкции минимальных тупиковых ДНФ с ядровыми импликантами и являются МДНФ (их также может быть не одна).

Пример.

Обе получившиеся импликанты – ядровые. Следовательно, МДНФ =

Отступление: геометрический язык – дуальность.

Изобразим носитель функции из примера на булевом кубе размерности 3:

На первом шаге алгоритма склейками получены импликанты, написанные в третьем столбце, общим числом также 5. Они соответствуют соседним ребрам куба. Таким образом, геометрически склейка – это переход от точек куба к покрывающим их рёбрам. Далее, пара ребер также может быть склеена по несущественной переменной, что на геометрическом языке будет обозначать переход к покрытию 2-гранью. Формально это выглядит следующим образом:

Таким образом, результат минимизации – нахождение покрытия носителя функции ребром и 2-гранью.

Взаимно-однозначное соответствие между точками куба и конституентами единицы очевидным образом продолжается до взаимно-однозначного соответствия между любой импликантой ранга r и гранью размерности n-r, задаваемое формулой:

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

Пример

Теперь можно дать точную формулировку задаче минимизации булевой функции на геометрическом языке: для данного множества N_f найти его покрытие минимальным числом граней максимальной размерности: N_f= N₁ÇN₂Ç…

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

dm_learning

Thu, Mar. 23rd, 2006, 02:03 am
Третий семинар

Тема: Кольца. Булевы функции. Минимизация ДНФ.. Читаем, комментируем, решаем ДЗ.

Исследование группоидов

Рассмотрим ещё один пример группоида и исследуем свойства его бинарной операции. , где .

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

Значит, это полугруппа. При попытке найти нейтральный элемент, получим:

это значит, что нейтральный элемент не существует, и данная алгебра — не моноид.

Кольца, тела и поля

• ;
• ;
• ;
• ;
• ;
• ;
• и .

Другими словами, алгебра является абелевой группой, алгебра — моноидом, а операция умножения дистрибутивна относительно сложния.

Можно доказать, что в кольце имеет место аннулирующее свойство нуля: .

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

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

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

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

• — множество диагональных матриц степени ;
• , — , симметрическая разность множеств, а — , пересечение множеств;
• — множество многочленов от переменной с действительными коэффициентами.

Кольцо вычетов

Важным примером кольца является кольцо вычетов по модулю : . Для разных это кольцо может обладать разными свойствами. Рассмотрим два случая: и .

При имеем следующие таблицы сложения и умножения по модулю 4:

Видно, что элемент 2 является делителем нуля: .

При имеем следующие таблицы сложения и умножения по модулю 5:

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

Можно доказать, что кольцо вычетов является полем тогда и только тогда, когда — простое число.

В кольцах вычетов можно решать уравнения и системы уравнений. Например решим данные уравнения в кольце , для простоты умножение и сложение по модулю 7 будем обозначать стандартными знаками полюса и умножения:

или в кольце вычетов :

Подалгебры

Пусть дана алгебра и множество , такое, что — тоже алгебра с теми же операциями. Тогда — подалгебра .

• группу и её подгруппу ;
• кольцо и его подкольцо .

А вот алгебра не является подгруппой , так как не обладает свойствами группы (является лишь моноидом и соответственно подмоноидом ).

• ;
• , — класс функций, непрерывных на отрезке, ;
• ( — заданный вектор).

Полукольца

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

• ;
• ;
• ;
• ;
• ;
• и ;
• ;

Если операция сложения в полукольце идемпотентна: , то такое полукольцо называют идемпотентным полукольцом, иногда их называют просто полукольцами. Пример такого полукольца:

Действительно, операция взятия минимума идемпотентна и является по ней нейтральным элементом.

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

Пример симметричного полукольца: алгебра подмножеств множества : .

Булевы алгебры

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

Самый распространённым примером булевой алгебры является двухэлементная булева алгебра: . Интересно, что приведённое выше симметричное полукольцо подмножеств множества также является булевой алгеброй, в которой дополнение определяется как .

Также представляет интерес -компонентная булева алгебра:

где операции и определены на булевых векторах из элементов, а и — соответственно нулевой и единичный вектор. Нетрудно показать, что это также булева алгебра.

В -элементной булевой алгебре определяется стандартное отношение порядка (покомпонентное сравнение): . Диаграммы Хассе для этого отношения булевой алгебры первого, второго и третьего порядка показаны на рисунке 1.

Булевы функции

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

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

При существует только две функции-константы: 0 и 1.

Рассмотрим все функции для :

— константы, — тождественная функция, — дополнение.

Рассмотрим все функции для :

— константы, — коньюнкция, — исключающее или, — дизъюнкция, — стрелка Пирса, — эквивалентность, — импликация, — штрих Шефера.

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

Элементарная коньюнкция — формула вида , где при используется дополнение переменной, а при — сама переменная. Пример элементарной коньюнкции: .

Дизъюнктивная нормальная форма — это формула вида , где — элементарная коньюнкция.

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

Карта Карно

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

Например, карта Карно для функции от трёх переменных будет иметь вид:

Отметим, что значение переменных в соседних столбцах и строках карты Карно должны быть сравнимы.

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

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

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

Алгоритм минимизации булевой функции состоит из следующих этапов:

1. Построение карты Карно для заданной функции.
2. Выделение склеек. Склейка — область, покрывающая только единицы на карте Карно, размер которой равен степени двух. Такая область может быть представлена в виде элементарной коньюнкции. При этом необходимо выделять склейки макимально большого размера. Дизъюнкция всех коньюнкций склеек даёт сокращённую ДНФ.
3. Определение ядра. Ядро — набор склеек, каждая из которых покывает единицы, не покрываемые ни одной другой склейкой. Такие склейки нахзывают ядровыми. Если в ядро входят все склейки, то минимальная ДНФ равна сокращённой, конец алгоритма.
4. Если существуют склейки, целиком попадающие в ядро, их можно выбросить. В результате получится ДНФ Квайна.
   1. Если ядро покрывает все единицы, то минимизация закончена.
   2. Если есть единицы, не покрываемые ядерными склейками, то строится функция Патрика: для каждой из таких единиц строится дизъюнкция вида , где — коньюнкция склейки, покрывающецй данную единицу. Такие дизъюнкции объединяются в общую коньюнкцию, которая и носит название функции Патрика. После раскрытия скобок и сокращения получется дизънкция нескольких наборов коньюнкций, каждый из таких наборов представляет собой отдельную альтернативу, покрывающую все единицы, не попавшие в ядро. Каждая такая альтернатива, объединённая с ядром, даёт одну из возможных минимальных ДНФ, или одну из тупиковых ДНФ.

   Рассмотрим пример минимизации булевой функции . На рисунке 2 показана карта Карно для этой функции.

   Всего можно выделить три склейки: , и . В ядро входят и , тогда как может быть выброшена. В данном случае ДНФ квайна и минимальная ДНФ совпадают: .

   На рисунке 3 показана карта Карно похожей функции. В этом случае ядро и не покрывает все единицы функции.

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

   Бывают ситуации, когда в ядро не входит ни одна склейка. Например, для функции, показанной на рисунке 4.

   В этом случае функция Патрика будет иметь шесть сомножителей — по одному на единицу: Ф.П. = = = = = .

   Конспекты лекций по дискретной математике, страница 3

   Документ из архива «Конспекты лекций по дискретной математике», который расположен в категории » «. Всё это находится в предмете «дискретная математика» из раздела «», которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе «лекции и семинары», в предмете «дискретная математика» в общих файлах.

   Онлайн просмотр документа «Конспекты лекций по дискретной математике»

   Текст 3 страницы из документа «Конспекты лекций по дискретной математике»

   Интервал ранга R содержит 2 N — R векторов.

   N – количество рассматриваемых векторов.

   Интервал – носитель элементарной конъюнкции.

   Носитель дизъюнкции двух функций равен объединению носителей этих функций.

   Носитель ДНФ является объединением интервалов.

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

   Интервал для данной функции является максимальным, если он не содержится целиком ни в каком другом допустимом интервале.

   Элементарная конъюнкция, носителем которой является допустимый интервал, называется импликантой.

   ЭК, N – максимальный интервал – простая импликанта.

   Представление носителя в виде объединения максимальных интервалов будем называть покрытием носителя максимальными интервалами.

   Дизъюнкция всех возможных простых импликант называется сокращенной ДНФ функции.

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

   ДНФ, которая соответствует неприводимому покрытию, называется тупиковой ДНФ.

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

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

   Элементарная конъюнкция, соответствующая ядровому интервалу – ядровая импликанта.

   Объединение всех ядровых интервалов – ядро функции.

   Дизъюнкция всех ядровых импликант — ядровая ДНФ.

   Ядро функции обязательно входит в любое неприводимое покрытие.

   Алгоритм получения минимальной ДНФ.

   Выделяем носитель функции.

   Выделяем все возможные интервалы.

   Выписываем все простые импликанты.

   Выделяем ядровый интервал.

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

   С реди тупиковых ДНФ выбираем минимальную.

   Выделение всех возможных интервалов.

   Для булева куба размерности 3 интервалом ранга 1 могут быть 4 вершины, лежащие в одной грани.

   Ранга 2 – любые 2 вершины, соединенные ребром.

   Ранга 3 – любая отдельная вершина.

   Если координата вектора меняет значения, то переменная не входит

   Получили неприводимое покрытие, добавив к ядру недостающие интервалы так, чтобы все единичные вершины были задействованы.

   Сосчитаем ранги тупиковых ДНФ

   D_min = D₁ = D₂

   Метод карт Карно для нахождения минимальной ДНФ

   Карта Карно – плоскостная интерпретация 4-мерного булева куба.

   Считаем, что левый край склеен с правым, а верхний – с нижним.

   Если таблицу Карно свернуть таким образом, то получится тор (torus — геометрическая фигура, напоминающая бублик).

   Правила поиска интервалов.

   Интервалом ранга 1 могут быть 2 соседних строки (2 соседних столбца)

   Интервалом ранга 2 может быть вся строка, весь столбец или квадрат 2х2.

   Интервалом ранга 3 – любые 2 соседние по горизонтали и вертикали клетки.

   Одна отдельно взятая вершина будет интервалом ранга 4.

   Алгоритм – тот же самый.

   Лекция 6

   Метод Квайна – Мак-Клоски для нахождения минимальной ДНФ

   Этот метод удобен для нахождения минимальной ДНФ функции от любого числа переменных.

   Определение. Элементарная конъюнкция K₁ покрывает ЭК K₂, если каждая переменная, входящая в K₁, входит и в K₂.

   K – конъюнкция из других переменных.

   Склеивание двух ЭК

   Идея метода Квайна (алгоритм)

   Выписываются все элементарные конъюнкции из СДНФ функции.

   Проводятся все возможные склеивания между этими ЭК. Полученные новые ЭК сохраняются вместе со старыми.

   Между ними снова проводим все возможные склеивания до тех пор, пока это возможно. В результате среди ЭК появятся все простые импликанты функции.

   Проводим поглощение между всеми получившимися ЭК, то есть оставляем только те ЭК, которые не покрываются никакими другими.

   В результате получаются только простые импликанты. Их дизъюнкция является сокращенной ДНФ. Дальше все идет в соответствии с тривиальным алгоритмом минимизации.

   Формализация Мак-Клоски.

   Каждой ЭК ставим в соответствие булев вектор. (x с отрицанием – 0, без отрицания – 1).

   Выписываем все ЭК из СДНФ функции в формализованном виде в столбец, располагая их в порядке возрастания числа единиц в векторах и разбивая на классы по числу единиц.

   Между ЭК проводим все возможные склеивания. Результат записываем в новый столбец справа, а ЭК, участвовавшие в склеивании, помечаем звездочкой. Склеивать можно только ЭК из соседних классов.

   Для полученного столбца еще раз применяем шаг 2.

   Все ЭК, которые остались непомеченными звездочкой, являются простыми импликантами.

   Строим таблицу Квайна по следующему правилу:

   А) Каждой строке ставим в соответствие простую импликанту П_i.

   Б) Каждому столбцу – ЭК из СДНФ K_j.

   Если П_i.покрывает K_j , то в соответствующей клетке ставим знак +.

   Ищем ядровые импликанты (столбец, содержащий только 1 знак +). Та строка и есть ядровая (строка, в какой этот крестик содержится).

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

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

   Среди всех тупиковых ДНФ выбираем минимальную.

   Лекция 7

   Функционально полные системы функций

   Определение. Система функций 1…f_n> называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из этой системы (т.е. можно представить формулой, куда входят только функции из этой системы).

   Если система полна, и любая ее функция представима в виде суперпозиции функций из системы то и система также полна.

   Мы заменили все функции суперпозицией из 

   Если система функций полна, то будет полной и система, состоящая из двойственных функций.

   Доказательство следует из принципа двойственности.

   Основные типы функционально полных систем.

   X/X = NOT(XX) = NOT(X)

   Одночленом будем называть любое выражение вида

   Многочленом Жегалкина называется сумма по модулю 2 различных одночленов.

   А1X1+А2X2+А3X3+A4X1X2 + A5X1X3+A6X2X3+A7X1X2X3 – общий вид многочлена Жегалкина для трех переменных. Чтобы выписать общий вид многочлена Жегалкина для нужного числа переменных нужно перебрать все возможные конъюнкции переменных и сложить их по модулю 2 друг с другом, а также с переменными, входящими в функцию. Перед каждой конъюнкцией нужно расставить буквенные коэффициенты.

   Любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде многочлена Жегалкина.

   Доказательство на лекции 8.

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

   Лекция 8

   Продолжение темы «Многочлены Жегалкина »

   Любая булева функция представима в виде многочлена Жегалкина (МЖ).

   Из этого следует, что функция представима в виде МЖ.

   ЭК без отрицания 2 n – 1 + 1

   Всего разных многочленов Жегалкина 2 N – 1, где N = 2 n

   Это число совпадает с числом разных булевых функций, отличных от нуля.

   Отсюда следует, что любой булевой функции соответствует единственный многочлен Жегалкина. Теорема доказана полностью.

   Классы функций. Замкнутые и незамкнутые классы. Получение констант и элементарных булевых функций из заданной системы функций

   Определение. Функция называется линейной, если ее многочлен Жегалкина не содержит ни одной конъюнкции переменных.

   Замкнутые классы функций.

   Пусть дан класс функций B (т.е. конечное или бесконечное множество функций),объединенных по общему признаку. Замыканием этого класса (обозначение – [B]) будем называть множество всех суперпозиций функций из класса B.

   Похожие публикации:

   1. Как закрепить столбец в ворде
   2. Как найти скорость в момент приземления
   3. Как найти среднюю температуру
   4. Как найти сумму цифр числа в c