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

Содержание

Слайд 2

Метод Квайна Метод Квайна — способ представления функции в ДНФ или КНФ с

Метод Квайна

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

переменных.
Слайд 3

Преобразование функции можно разделить на два этапа: на первом этапе осуществляется переход от

Преобразование функции можно разделить на два этапа:
на первом этапе осуществляется переход

от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;
на втором этапе — переход от сокращённой формы к минимальной форме.
Слайд 4

Первый этап (получение сокращённой формы). Предположим, что заданная функция представлена в СДНФ. Выполним

Первый этап (получение сокращённой формы).

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

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

а) Формула склеивания б) Формула неполного склеивания в) Формула поглощения

а) Формула склеивания
б) Формула неполного склеивания
в) Формула поглощения

Слайд 6

В результате СДНФ приводится к СкДНФ.

В результате СДНФ приводится к СкДНФ.

Слайд 7

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

Минимальная форма формулы (МДНФ ) получается на основе импликантной матрицы путем

нахождения минимального покрытия этой матрицы.
Слайд 8

Импликанта – это элементарная конъюнкция СкДНФ. Конституента единицы – это элементарная конъюнкция СДНФ.

Импликанта – это элементарная конъюнкция СкДНФ.
Конституента единицы – это элементарная

конъюнкция СДНФ. Импликантная матрица – это матрица импликант и констиуент единиц. (столбцы - конституенты единицы, строки – импликанты). МДНФ может быть несколько.
Слайд 9

Подмножество строк матрицы M является ее покрытием, если в подматрице, образованной этими строками

Подмножество строк
матрицы M является ее покрытием, если в подматрице,

образованной этими строками нет нулевых столбцов.
Покрытие матрицы также называется покрытием столбцов матрицы ее строками.
Слайд 10

Пример 1. Пусть

Пример 1. Пусть

Слайд 11

Тогда 1-я и 2-я строки не покрывают матрицу M: а 1-я и 3-я

Тогда 1-я и 2-я строки не покрывают матрицу M:
а 1-я и

3-я строки – являются покрытием матрицы M:
Слайд 12

ПРИМЕР. Найдем МДНФ формулы:

ПРИМЕР.
Найдем МДНФ формулы:

Слайд 13

Во-первых, осуществим всевозможные склеивания

Во-первых, осуществим всевозможные склеивания

Слайд 14

В результате СкДНФ имеет вид:

В результате СкДНФ имеет вид:

Слайд 15

А импликантная матрица имеет вид

А импликантная матрица имеет вид

Слайд 16

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

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

Слайд 17

Метод минимизирующих карт. Алгоритм метода минимизирующих карт включает в себя следующие этапы: Вычеркнем

Метод минимизирующих карт.

 Алгоритм метода минимизирующих карт включает в себя следующие этапы:
Вычеркнем

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

Отметим конъюнкции, оставшиеся единственными на строке. Вычеркнем строки, в которых присутствуют такие же

Отметим конъюнкции, оставшиеся единственными на строке. Вычеркнем строки, в которых присутствуют

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

ПРИМЕР. Дана СДНФ

ПРИМЕР.  Дана СДНФ

Слайд 20

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

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

- помечены строки, не содержащие конституенты СДНФ.
Слайд 21

Из таблицы вычеркнем те строки, которые не содержат конституенты СДНФ, а также конъюнкции

Из таблицы вычеркнем те строки, которые не содержат конституенты СДНФ, а

также конъюнкции этих строк, содержащиеся в других строках.
Слайд 22

В результате получим:

В результате получим:

Слайд 23

После всевозможного перебора остаются следующие МДНФ:

После всевозможного перебора остаются следующие МДНФ:

Слайд 24

Метод минимизации с помощью карт Вейча.

Метод минимизации с помощью карт Вейча.

Слайд 25

Алгоритм метода карт Вейча включает в себя следующие этапы: Заданная формула приводится к

Алгоритм метода карт Вейча включает в себя следующие этапы:
Заданная формула приводится

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

Единицы, стоящие по вертикали и горизонтали, объединяются (по 2 , по 4 ,

Единицы, стоящие по вертикали и горизонтали, объединяются (по 2 , по

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

Карты Вейча удобны при поиске МДНФ функций двух, трех и четырех переменных.

Карты Вейча удобны при поиске МДНФ функций двух, трех и четырех

переменных.
Слайд 28

Пример для n=2. Функция задана

Пример для n=2.
Функция задана

Слайд 29

Слайд 30

Пример для n=3. Функция задана

Пример для n=3.
Функция задана

Слайд 31

Пример для n=4. Функция задана СДНФ

Пример для n=4.
Функция задана СДНФ

Слайд 32