Разделы презентаций


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

Содержание

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

Слайды и текст этой презентации

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

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

Слайд 2Определение: Преобразование логических функций с целью упрощения их

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

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

Методы минимизации:
Метод непосредственных преобразований логических функций.
Метод неопределенных коэффициентов.
Аналитические методы (метод Квайна, метод Квайна – Мак-Класки)
Метод минимизирующих карт (карты Карно, диаграммы Вейча)

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

Слайд 3Метод непосредственных преобразований логических функций
Логическая функция подвергается упрощению непосредственно с

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

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

Слайд 4Если некоторая логическая функция φ (в частном случае элементарное произведение)

равна нулю на тех же наборах, на которых равняется нулю

другая функция f, то говорят, что функция φ входит в функцию f. Другими словами, функция φ входит в функцию f тогда, когда она накрывает нулями все нули функции f, а единицы функции f могут быть накрыты как нулями, так и единицами функции φ.
Очевидно, что «Константа ноль» входит во все функции, а в «Константу единица» входят все функции.
Функцию φ, входящую в данную функцию f, называют ее импликантой.
Простыми (первичными) импликантами логической функции f называют такие элементарные произведения или элементарные суммы, которые сами входят в данную функцию, но никакая собственная часть этих произведений не входит в функцию f.
Собственной частью называют произведение, полученное путем исключения из данного произведения одного или нескольких сомножителей.
Если некоторая логическая функция φ (в частном случае элементарное произведение) равна нулю на тех же наборах, на

Слайд 6Дизъюнкция всех простых импликант называется сокращенной дизъюнктивной нормальной формой (СкДНФ)

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

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

Слайд 7Метод получения сокращенной дизъюнктивной нормальной формы логической функции называется методом

Квайна.
Теорема Квайна. Если в совершенной дизъюнктивной нормальной форме логической функции

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

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

Слайд 8Этапы преобразования ФАЛ по методу Квайна :
Провести в СДНФ функции

все возможные операции неполного склеивания конституент единицы. В результате этого

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

Слайд 9Пример. Минимизировать функцию, заданную в СДНФ:
- СкДНФ

Пример. Минимизировать функцию, заданную в СДНФ:- СкДНФ

Слайд 10Импликантная матрица
Для поиска тупиковых форм функции пользуются методом импликантных матриц.


Существо метода заключается в следующем: составляется импликантная матрица, колонки которой

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

Слайд 11 Вначале из всех простых импликант выбираются существенные импликанты, которые только

одни покрывают какие-либо конституенты единицы данной функции (в колонке матрицы

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

Слайд 12- существенная импликанта
- существенная импликанта
Тупиковые формы:
Минимальные формы:

- существенная импликанта- существенная импликантаТупиковые формы:Минимальные формы:

Слайд 13Метод Квайна-Мак-Класки.
1. Каждая конъюнкция в СДНФ представляется

своим двоичным набором., где переменной, входящей в произведение в прямом

виде ставится в соответствие единица («1»), в инверсном – нуль («0»).
2. Вся совокупность номеров наборов разбивается на группы в зависимости от числа единиц, имеющихся в номерах наборов (0-группа, 1-группа, 2-группа и т.д.).
3. Сравниваются элементы двух соседних группы, отличающиеся на одну единицу.
При этом устанавливается возможность склейки двух наборов из этих групп, делается необходимая пометка и пишется результат склейки.
4. Процесс продолжается до тех пор, пока возможны склейки.
5. Все несклееные наборы, а также конечные результаты склейки дают простые импликанты.
Метод Квайна-Мак-Класки.   1. Каждая конъюнкция в СДНФ представляется своим двоичным набором., где переменной, входящей в

Слайд 14ПРИМЕР. f(a,b,c,d)СДНФ = ∑(3,7,8,10,11,12,15)

Решение
Этап 1.
Выписать двоичное представление наборов, образующих СДНФ

данной функции:
(0011, 0111, 1000, 1010, 1011, 1100, 1111)
Этап 2.
Разбить полученные

двоичные коды на группы, содержащие одинаковое количество единиц в коде. Для ФАЛ, зависящих от n переменных, таких групп может быть n+1 (ни одной единицы в коде, одна единица, две единицы, ... , n единиц в коде). Расположить группы по возрастанию (или убыванию) количества единиц. Если количество получившихся групп меньше n+1, то отсутствующие группы пометить как пустые:
ПРИМЕР. f(a,b,c,d)СДНФ = ∑(3,7,8,10,11,12,15)РешениеЭтап 1.Выписать двоичное представление наборов, образующих СДНФ данной функции:(0011, 0111, 1000, 1010, 1011, 1100,

Слайд 15Этап 3.
Сравнить каждый код из одной группы с каждым кодом

из соседних групп. Если найдены два кода, отличающиеся только в

одном разряде (то есть они могут “склеиваться”), то пометить эти коды каким-либо особым символом, например " * ", и в новую группу поместить код, сохраняющий значение в совпадающих разрядах и имеющий какой-либо особый символ, например "-", на месте несовпадающего разряда. При этом образуется n-1 новая группа кодов. Если код попадает в несколько “склеек”, то он символом * может помечаться только один раз.
Эта процедура повторяется для вновь образованных групп до тех пор, пока возможна процедура “склеивания“ элементов соседних групп. Максимальное возможное число шагов на этом этапе равно n. На всех шагах, начиная со второго, необходимо следить за тем, чтобы два “склеиваемых” кода представляли собой термы, зависящие от одних и тех же логических переменных, то есть знаки "-" у них должны находиться в одних и тех же позициях. При появлении в одной группе нескольких одинаковых импликант для дальнейшего анализа следует оставить лишь одну из них.
Этап 3.Сравнить каждый код из одной группы с каждым кодом из соседних групп. Если найдены два кода,

Слайд 16Последовательность выполнения шагов этапа 3

Последовательность выполнения шагов этапа 3

Слайд 17Этап 4.
Составить импликантную матрицу.

Этап 4.Составить импликантную матрицу.

Слайд 18Этап 5. Найти существенные импликанты функции.
Для рассматриваемой функции существенными импликантами

будут - -11 и 1-00, так как только первичная импликанта

--11 позволяет покрыть минтерм 0011 исходного набора, а первичная импликанта 1-00 необходима для покрытия минтерма 1100.


Этап 5. Найти существенные импликанты функции.Для рассматриваемой функции существенными импликантами будут  - -11 и 1-00, так

Слайд 19Этап 6. Найти тупиковые дизъюнктивные нормальные формы и выбрать из

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

минимальные дизъюнктивные формы:
f1МДНФ = c d v acd v abd
- -1 1 1- 0 0 1 0 - 0
f2МДНФ = c d v acd v ab с
- -1 1 1- 0 0 1 0 1 -
Этап 6. Найти тупиковые дизъюнктивные нормальные формы и выбрать из них минимальные ДНФ.Рассматриваемая функция имеет две различные

Слайд 20МИНИМИЗИРУЮЩИХ КАРТ (КАРТЫ КАРНО ИЛИ ДИАГРАММЫ ВЕЙЧА)
Карты Карно (их разновидностью

являются диаграммы Вейча) являются графическим представлением таблиц истинности. Поэтому они

строятся или по таблице истинности анализируемой функции, или же по ее СНДФ.
Диаграммы Вейча представляет собой прямоугольник, разбитый на квадраты, число которых равно общему числу наборов для данной функции n переменных, т.е. оно равно 2n. Так, для функции 3-х переменных квадратов будет 8, 4-х - 16 и т.д.
Каждый квадрат соответствует определенному набору или терму, причем наборы располагаются так, чтобы соседние наборы или термы, как по горизонтали, так и по вертикали, отличались бы только значением одной переменной: в одном квадрате она с инверсией, а в другом, соседнем - без. Причем, надо учесть, что квадраты, расположенные на противополжных концах каждой строки или столбца, также являются соседними.
Функцию в СНДФ наносят на карту, отмечая, например, знаком 1 квадраты, соответствующие тем наборам, на которых функция равна единице, т.е. в СНДФ функции есть соответствующий минтерм. Остальные квадраты отмечаются знаком 0.
МИНИМИЗИРУЮЩИХ КАРТ (КАРТЫ КАРНО ИЛИ ДИАГРАММЫ ВЕЙЧА)Карты Карно (их разновидностью являются диаграммы Вейча) являются графическим представлением таблиц

Слайд 21Диаграмма Вейча для функции 3-х переменных
Диаграмма Вейча для функции 4-х

переменных

Диаграмма Вейча для функции 3-х переменныхДиаграмма Вейча для функции 4-х переменных

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

последней колонок, то тогда склеивающиеся между собой конституэнты единицы или

нуля в диаграммах Вейча будут расположены в соседних клетках. При этом прямоугольники, покрывающие 2k соседних клеток, описывают имликанту (имплиценту), имеющую ранг (n-k), где n – число переменных, от которых зависит функция.
Клетки, содержащие в диаграмме Вейча единицы, будем называть 1-клетками, а клетки, содержащие нули – 0-клетками. Основное свойство диаграмм Вейча заключается в том, что любая первичная импликанта ранга (n-m) образует на ней прямоугольник и только прямоугольник 1-клеток площадью 2m, где n – количество переменных, от которых зависит функция. Такие прямоугольники называют m-кубами (m=0,1,…,n.; 0-кубу соответствует минтерм, а n-кубу – константа "единица"). Так любая пара единиц в соседних клетках диаграммы Вейча для логической функции трех переменных представляется импликантой второго ранга. Четыре единицы, образующие прямоугольник, выражаются одной переменной (с отрицанием или без него).
Чтобы записать первичную импликанту, представляющую собой некий m-куб на диаграмме Вейча, необходимо просто составить конъюнкцию тех переменных, которые в пределах данного m-куба сохраняют постоянные значения (только прямые или только инверсные).
Если данную таблицу рассматривать как цилиндр, образованный соединением первой и последней колонок, то тогда склеивающиеся между собой

Слайд 23Получение минимальной ДНФ с помощью диаграмм Вейча сводится к отысканию

минимального числа m-кубов максимального размера, состоящих из 1-клеток, и со-ставлению

дизъюнкции импликант, соответствующих этим m-кубам (каждая 1-клетка должна войти хотя бы в один m-куб, любая 1-клетка может входить одновременно в несколько различных m-кубов).
При получении МДНФ с помощью диаграммы Вейча необходимо обратить внимание на следующее:
m-кубу, покрывающему 2m 1-клеток, соответствует первичная импликанта, не зависящая от m переменных, причем исключаются те m переменных, которые в прямоугольной области на диаграмме Вейча, состоящей из 1-клеток, имеют различное значение (прямое и инверсное);
прямоугольные области на диаграмме Вейча, используемые при минимизации, могут состоять только из 2m соседних клеток, где m = 0,1,…,n;
каждая клетка на диаграмме Вейча, вне зависимости от способа разметки этой диаграммы, имеет ровно n соседних клеток; в связи с этим диаграмма Вейча представляется нанесенной на поверхность соответствующего тела (цилиндра – для случая трех переменных, тора – для случая четырех переменных);
поиск минимального покрытия 1-клеток следует начинать с выбора тех 1-клеток, которые могут войти в один и только один m-куб, а затем выбранные таким образом 1-клетки покрываются m-кубами максимального размера; если после этого на диаграмме остаются 1-клетки, не вошедшие ни в один из m-кубов, то следует рассмотреть несколько вариантов покрытий этих клеток с целью минимизации результата.
Получение минимальной КНФ проводится аналогичным образом по отношению к 0-клеткам.
Получение минимальной ДНФ с помощью диаграмм Вейча сводится к отысканию минимального числа m-кубов максимального размера, состоящих из

Слайд 24Пример. Минимизировать функцию, заданную в СДНФ:
Минимальные формы:

Пример. Минимизировать функцию, заданную в СДНФ:Минимальные формы:

Слайд 25Пример. Минимизировать функцию, заданную в СКНФ:
f(a,b,c,d)СКНФ = ∏(2,3,5,6,7,10,11,13,14)
Минимальная форма:






Пример. Минимизировать функцию, заданную в СКНФ:f(a,b,c,d)СКНФ = ∏(2,3,5,6,7,10,11,13,14) Минимальная форма:

Слайд 26Неполностью определенные ФАЛ
Неполностью определенной ФАЛ от n переменных называется функция,

заданная на множестве наборов, меньше чем 2n.
Каждая строка таблицы истинности

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

Слайд 27ПРИМЕР. Получить методом диаграмм Вейча минимимальную дизъюнктивную нормальную форму неполностью

определенной ФАЛ, заданой в следующем виде:
f(a,b,c,d) = ∑(0,5,8,12,15), Х(1,2,3,10.13,14)





ПРИМЕР. Получить методом диаграмм Вейча минимимальную дизъюнктивную нормальную форму неполностью определенной ФАЛ, заданой в следующем виде:f(a,b,c,d) =

Слайд 28Получим МКНФ этой же функции:
f(a,b,c,d) = ∑(0,5,8,12,15), Х(1,2,3,10.13,14)
f(a,b,c,d) = &(4,6,7,9,11),

Х(1,2,3,10.13,14)



Получим МКНФ этой же функции:f(a,b,c,d) = ∑(0,5,8,12,15), Х(1,2,3,10.13,14)f(a,b,c,d) = &(4,6,7,9,11), Х(1,2,3,10.13,14)

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика