Минимизация функционального представления

МНОЖЕСТВ.

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

С = f (Ai)

f – функция переводит элементы Ai во множество С.

Если пересечение множеств обозначать как функциональную операцию Р , то

Р (А,В) = АВ

На единичном множестве 1 заданы множества А,В,С. В этом случае с помощью известной операции над множествами переводим исходное множество в какое-либо другое.

f (А,В,С) = АВС È А Минимизация функционального представления - №1 - открытая онлайн библиотека С È Минимизация функционального представления - №2 - открытая онлайн библиотека В Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È АВ È AС È Минимизация функционального представления - №2 - открытая онлайн библиотека С È Минимизация функционального представления - №2 - открытая онлайн библиотека В;

Записанное выражение назовем формулой. Определим сложность формулы, как количество, содержащихся в ней исходных множеств. Для приведенного примера сложность =20. При аналазе формул первым вопросом является: «Можно ли уменьшить сложность формулы?» Сделаем это на примере применяя законы дистрибутивности и поглощения

f(А,В,С) = АВС È А Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека В Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È А(В È С) È Минимизация функционального представления - №2 - открытая онлайн библиотека (В È С) =

= АВС È А Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека B Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È В È С = ВÈ А Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È С =

= Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È В È С = Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека =1

f(А,В,С) = АС È Минимизация функционального представления - №1 - открытая онлайн библиотека С È Минимизация функционального представления - №2 - открытая онлайн библиотека ВС È АВС È АВ Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека В Минимизация функционального представления - №3 - открытая онлайн библиотека = АС È Минимизация функционального представления - №1 - открытая онлайн библиотека С È Минимизация функционального представления - №2 - открытая онлайн библиотека В È АВ =

=В È АС È Минимизация функционального представления - №1 - открытая онлайн библиотека С;

Или :

F(А,В,С) = АС È Минимизация функционального представления - №1 - открытая онлайн библиотека С È Минимизация функционального представления - №2 - открытая онлайн библиотека ВС È АВС È АВ Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека В Минимизация функционального представления - №3 - открытая онлайн библиотека = АС È Минимизация функционального представления - №1 - открытая онлайн библиотека С È ВС È АВ Минимизация функционального представления - №3 - открытая онлайн библиотека È È Минимизация функционального представления - №2 - открытая онлайн библиотека В Минимизация функционального представления - №3 - открытая онлайн библиотека = АС È Минимизация функционального представления - №1 - открытая онлайн библиотека С È ВС È В Минимизация функционального представления - №3 - открытая онлайн библиотека = С È В Минимизация функционального представления - №3 - открытая онлайн библиотека

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

СТАНДАРТНЫЕ ФОРМЫ ПРЕДСТАВЛЕНИЙ ФОРМУЛ

МНОЖЕСТВ.

Минимизация функционального представления - №55 - открытая онлайн библиотека На 1 определении М123 совокупность Мi назовем порожд-ми множествами пространства и определим Мi по универсальной формуле:

Мi ; di =1;

Midi = di={0;1}

Минимизация функционального представления - №56 - открытая онлайн библиотека i ; di =0;

Мi = i = {0,1}

Mi; i=0;

Mi, di – первичный термом

Ki = Минимизация функционального представления - №57 - открытая онлайн библиотека idi - конституентой

n - число порожденных множеств.

Перечислим все конституенты нашего примера:

К0 = Минимизация функционального представления - №56 - открытая онлайн библиотека 1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 К1 = Минимизация функционального представления - №56 - открытая онлайн библиотека 1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2М3 К2 = Минимизация функционального представления - №56 - открытая онлайн библиотека 1М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 К3 = Минимизация функционального представления - №56 - открытая онлайн библиотека 1М2М3

К4 = М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 К5 = М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2М3 К6 = М1М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 К3 = М1М2М3

Очевидно, что каждой приведенной коституенте может быть сопоставлено двоичное трехразрядное число , причем каждый разряд будет равен di первичного терма:

К0 = 000; К1 = 001; К2 = 010; К4 =011; К5 = 100; К6 = 110; К7 = 111.

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

двоичное число, то общее количество конституент равно:

N = 2n

1) Выражения, заданные с помощью формул ,могут быть упрощены.

2) Необходимые шаги для упрощения не всегда очевидны и сложность упрощения находится в прямой зависимости от числа аргументов в формуле.

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

Пересечение двух различных конституент - пустое множество.

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

Обозначим этот разряд через i.

Midi *Midi*= Æ

Объединение всех коституент,порожденных множествами Mi на универсальном множестве равно самому универсальному множеству:

I= Минимизация функционального представления - №70 - открытая онлайн библиотека (Mi È Минимизация функционального представления - №56 - открытая онлайн библиотека i)

n=1 M1, Минимизация функционального представления - №56 - открытая онлайн библиотека 1 M1+ Минимизация функционального представления - №56 - открытая онлайн библиотека 1=I

n=k Минимизация функционального представления - №74 - открытая онлайн библиотека j = I

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

1. Проиллюстрируем на графическом примере:

(универсальное множество I, внутри М1-квадрат, М2-треугольник, М3-круг).

 
  Минимизация функционального представления - №75 - открытая онлайн библиотека

В дополнение к рассматриваемым свойствам ,рассмотрим сколько множеств на I можно образовать из конституент.

Для этого произвольному множеству сопоставим m-разрядное двоичное число,где m-длина конституент. При этом 0-отсутствие конституенты, 1-присутствует.

Так например, двоичному числу

01101001 соответствует множество, из объединенных 0,3,5,и 6 конституент.

Вместо двоичных чисел можно использовать их десятичный эквивалент:

d = 1+23+25+26 = 1+8+32+64 = 40+ 65 = 105

Если любому, образованному из конституент, множеству соответствует m-разрядное двоичное число, то таких множеств может быть 2m,а так как число конституент = 2n , где n-число образованных множеств,то общее число, которое образуется из конституент = 22^n

Для иллюстрации это количество -256.

Рассмотрев понятие конституент зададимся вопросом:»Как конституенты связаны с функциями от образующих множеств?»

МАТЕМАТИЧЕСКИЕ УТВЕРЖДЕНИЯ.

Множество Mi равно объединению всех конституент ,содержащих Mi

Рассмотрим равенство:

I = Минимизация функционального представления - №76 - открытая онлайн библиотека j-1

Возьмем пересечение левых и правых частей с Mi

Mi = Минимизация функционального представления - №76 - открытая онлайн библиотека j-1Mi

Рассмотрим выражение Кj,Mi. Для него возможны два случая:

1.Kj не содержит в себе Mi, Ki*Mi = Æ

2.Kj Ì Mi , Kj*Mi =Kj

Следовательно, Mi можно представить в виде:

Мi = Минимизация функционального представления - №78 - открытая онлайн библиотека l

kl -конституенты,содержащие Mi.

ТЕОРЕМА.

Любая функция от порождающих множеств представима в виде объединения конституент.

Из аксиоматичного построения следует,что все операции представимы через операции объединения и отрицания.

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

Для доказательства рассмотрим объединение произвольно образованных множеств Mi и Мк.

Согласно утверждению (Mi È Мк) ,записывающихся в виде:

Минимизация функционального представления - №79 - открытая онлайн библиотека Мi È Мк = Минимизация функционального представления - №80 - открытая онлайн библиотека j+ Минимизация функционального представления - №81 - открытая онлайн библиотека l Мi È Мк = Минимизация функционального представления - №82 - открытая онлайн библиотека j

при этом М – различно,так как различно число совпадающих конституент в представлениях множеств Mi иМк.

Остается доказать,что дополнения к объединению конституент в свою очередь есть объединение конституент .

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

Рассмотрим пример:

Функция от множеств А,В,С

f(A,В,С) = А(В È ((С Минимизация функционального представления - №83 - открытая онлайн библиотека А)\В)) = А(В È ((С Минимизация функционального представления - №2 - открытая онлайн библиотека È С Минимизация функционального представления - №2 - открытая онлайн библиотека )\В)) = А(В È (С Минимизация функционального представления - №2 - открытая онлайн библиотека È Минимизация функционального представления - №3 - открытая онлайн библиотека А) Минимизация функционального представления - №1 - открытая онлайн библиотека ) =

А(В È С Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека È Минимизация функционального представления - №3 - открытая онлайн библиотека А Минимизация функционального представления - №1 - открытая онлайн библиотека ) = АВ È Минимизация функционального представления - №3 - открытая онлайн библиотека А Минимизация функционального представления - №1 - открытая онлайн библиотека = А Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È АВС È АВ Минимизация функционального представления - №3 - открытая онлайн библиотека

Из пересечения АВ получена АВС È Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека С. Ясно ,чтобы получит трех-разрядную конституенту, необходимо до термов АВ добавить С, а так как произв-но множество М:

Минимизация функционального представления - №100 - открытая онлайн библиотека М(С È Минимизация функционального представления - №3 - открытая онлайн библиотека ) = МС È М Минимизация функционального представления - №3 - открытая онлайн библиотека АВ = АВС È АВ Минимизация функционального представления - №3 - открытая онлайн библиотека

то просто получим из АВ трехразрядную конституенту.

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

Если в представлении функции участвовали конституенты меньшей длины, то оно называется норм. формой Кантора (НФК).

Для получения РФК нужно минимизании СНФК любым (аналитическим, графическим,графо-аналитическим способом).

Назовем интервалами универсального пространства ранга n все коституенты длина l =1, n

Если какая-либо С1 (интерв.) = С2È С3, то говорят что С1 включает в себя С2 и С3 или С1 покрывает С2 и С3

Из этого следует , что функция ,представленная в СНФК равна:

f (A,В,С) = Минимизация функционального представления - №104 - открытая онлайн библиотека j= Минимизация функционального представления - №105 - открытая онлайн библиотека l

где Cl - интервалы,покрывающие все конституенты Кj .

Если рассмотреть предыдущий пример,то можно заметить ,что f(А,В,С):

f (A,В,С) = АВ È А Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека

где, АВ покрывает АВС и АВ Минимизация функционального представления - №3 - открытая онлайн библиотека , а втор. совпадает с А Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека .

ГРАФИЧЕСКАЯ МИНИМИЗАЦИЯ ФУНКЦИИ ОТ

ТРЕХ ПЕРЕМЕННЫХ.

Введем геометрическое представление интервалов при n=3.

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

 
  Минимизация функционального представления - №111 - открытая онлайн библиотека

Сопоставим коституенты с их двоичным эквивалентом:

000 – Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека ; 001 – Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека C; 010 – Минимизация функционального представления - №2 - открытая онлайн библиотека В Минимизация функционального представления - №3 - открытая онлайн библиотека ; 011 – Минимизация функционального представления - №2 - открытая онлайн библиотека ВС; 100 – А Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека ;

101 – А Минимизация функционального представления - №1 - открытая онлайн библиотека С; 110 – АВ Минимизация функционального представления - №3 - открытая онлайн библиотека ; 111 – АВС.

Рассмотрим более сложные интервалы:

Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека В Минимизация функционального представления - №3 - открытая онлайн библиотека = Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека

О – О , где - - отсутствие разряда

Геометрически - сопоставляется ребро соединения вершины 000 и 010.

Запишем соответствие ребер интервала:

-00 = Минимизация функционального представления - №1 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека ; -01 = Минимизация функционального представления - №1 - открытая онлайн библиотека С; -10 = В Минимизация функционального представления - №3 - открытая онлайн библиотека ;

0-0 = Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №3 - открытая онлайн библиотека ; 0-1 = Минимизация функционального представления - №2 - открытая онлайн библиотека С; 1-0 = А Минимизация функционального представления - №3 - открытая онлайн библиотека ;

00- = Минимизация функционального представления - №2 - открытая онлайн библиотека Минимизация функционального представления - №1 - открытая онлайн библиотека ; 01- = Минимизация функционального представления - №2 - открытая онлайн библиотека В; 10- = А Минимизация функционального представления - №1 - открытая онлайн библиотека ;

-11 = ВС; 1-1 = АС; 11- = АВ.

По аналогии ребра конституенты можно объеденить в грань.

АВ È В Минимизация функционального представления - №3 - открытая онлайн библиотека È Минимизация функционального представления - №2 - открытая онлайн библиотека В È ВС = В

Соответствия граней:

--0 = Минимизация функционального представления - №3 - открытая онлайн библиотека ; --1 = С

-0- = Минимизация функционального представления - №1 - открытая онлайн библиотека ; -1- = В;

0-- = Минимизация функционального представления - №2 - открытая онлайн библиотека ; 1-- = А.

Для представления функции на кубе ,участвующие интервалы выделяются.

Минимизация функционального представления - №148 - открытая онлайн библиотека 111 110

101 100

001 000

f(A,В,С) = С È В Минимизация функционального представления - №3 - открытая онлайн библиотека

Минимизация функционального представления - №150 - открытая онлайн библиотека 111 B 110

В этом примере видно,что конституенты Минимизация функционального представления - №2 - открытая онлайн библиотека В Минимизация функционального представления - №3 - открытая онлайн библиотека и

Минимизация функционального представления - №2 - открытая онлайн библиотека ВС покрытые Минимизация функционального представления - №2 - открытая онлайн библиотека В

101 100 и Минимизация функционального представления - №2 - открытая онлайн библиотека В Минимизация функционального представления - №3 - открытая онлайн библиотека и АВ Минимизация функционального представления - №3 - открытая онлайн библиотека покрытые В Минимизация функционального представления - №3 - открытая онлайн библиотека можно покрыть одним

001 000 интервалом В.

f(A,В,С) = С È В

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

МИНИМИЗАЦИЯ ФУНКЦИИ ТРЕХ ПЕРЕМЕННЫХ

ГРАФИЧЕСКИМ СПОСОБОМ.

f(M123) = Минимизация функционального представления - №56 - открытая онлайн библиотека 1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2М3 + Минимизация функционального представления - №56 - открытая онлайн библиотека 1М2М3 + М1М2М3 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3

Минимизация функционального представления - №148 - открытая онлайн библиотека 111 110

101 100

001 000

f(M123) = Минимизация функционального представления - №56 - открытая онлайн библиотека 1М3 + М2М3 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3

МИНИМИЗАЦИЯ ФУНКЦИИ С ПОМОЩЬЮ КАРТ

КАРНО.

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

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

Идея: развернуть куб на плоскости

000 001 011 010 000

       

100 101 111 100 100

Минимизация функционального представления - №168 - открытая онлайн библиотека Исходя из развертки куба , строится таблица:

Минимизация функционального представления - №169 - открытая онлайн библиотека М1 М2М3 00 01 М3 11 10

   
Минимизация функционального представления - №170 - открытая онлайн библиотека 1    

Минимизация функционального представления - №171 - открытая онлайн библиотека М1

М2

Построенная таблица – карта КАРНО.

В ней отмечены конституенты,присутствующие в функции, подобно тому, как отмеченные вершины куба объеденены в ребра и грани.

Объед. и еден. карты (интервалы).

Объединение единиц в интнрвалы в карте иначе называют склеиванием.

Этапы заполнения карты КАРНО.

1. Все конституенты , присутствующие в функции заносятся в карту с помощью единиц в соответствующие клетки.

2. Выделяют интервалы на карте по следующим принципам:

а) в один интервал объединяют только соседние единицы по вертикали или горизонтали;

б) в один интервал можно объеденить 2к единиц, где k=0,1,2,3,4,….

в) карта циклически замкнута по вертикали и горизонтали.

г) в выделенный интервал объединено максимально возможное количество единиц.

Всего на карте выделено 3 интервала, в каждый входят те минитермы в которых он полностью находится.

Запишем минимальную функцию:

f(M123) = М1М3 + М2М3 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3

Пример:

Минимизировать функцию:

f(M123)= Минимизация функционального представления - №56 - открытая онлайн библиотека 1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 + Минимизация функционального представления - №56 - открытая онлайн библиотека 1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 М3 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 М3 + М1М2М3 +

+ Минимизация функционального представления - №56 - открытая онлайн библиотека 1М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 + М1М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3

Минимизация функционального представления - №169 - открытая онлайн библиотека 00 01 М3 11 10

 
Минимизация функционального представления - №170 - открытая онлайн библиотека 1

Минимизация функционального представления - №171 - открытая онлайн библиотека М1

М2

f(M123) = Минимизация функционального представления - №56 - открытая онлайн библиотека 2 + М1 + Минимизация функционального представления - №56 - открытая онлайн библиотека 3

При правильном объединении функцию больше минимизировать невозможно.

Минимизация функционального представления - №190 - открытая онлайн библиотека Карта Карно для 4-х переменных:

М1М2 М3М4 00 01 11 10

Минимизация функционального представления - №191 - открытая онлайн библиотека 00      
    М2
Минимизация функционального представления - №192 - открытая онлайн библиотека 11      
    М1

Минимизация функционального представления - №193 - открытая онлайн библиотека Минимизация функционального представления - №194 - открытая онлайн библиотека М3

М4

f(M123) = М1М4 + М2М4 + Минимизация функционального представления - №56 - открытая онлайн библиотека 1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 4

Пример:

Минимизация функционального представления - №198 - открытая онлайн библиотека f(M1234 ) (3,4,5,7,9,11,12,13 конституенты)

М1М2 М3М4 00 01 11 10

       
   
     
     

3 - 0011 4 - 0100 5 - 0101 7 - 0111 9 - 1001

11- 1011 12 - 1100 13 - 1101

f(M1234 )= М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3+ Минимизация функционального представления - №56 - открытая онлайн библиотека 1М3М4 1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2М4

Карты Карно для 5-ти переменных:

Минимизация функционального представления - №202 - открытая онлайн библиотека Минимизация функционального представления - №203 - открытая онлайн библиотека Минимизация функционального представления - №204 - открытая онлайн библиотека М4 М5

Минимизация функционального представления - №169 - открытая онлайн библиотека М1М2 М3М4М5 001 М3 011 010 110 111 101 100

               
Минимизация функционального представления - №206 - открытая онлайн библиотека 01            
Минимизация функционального представления - №207 - открытая онлайн библиотека М2 11            
М1 10            

При выделении интервалов необходимо соблюдать дополнительные правила:

1) Все интервалы должны быть симметричны относительно исходных размеров карт;

2) Если 2 единицы находятся симметрично границы раздела они считаются соседними.

f(М12345) = М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 М5 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 М4 М5 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 М3М4 Минимизация функционального представления - №56 - открытая онлайн библиотека 5

f(М12345) = Минимизация функционального представления - №56 - открытая онлайн библиотека 1 М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 Минимизация функционального представления - №56 - открытая онлайн библиотека 4М5 + Минимизация функционального представления - №56 - открытая онлайн библиотека 1 М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 М4 М5 +

+ М1М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 Минимизация функционального представления - №56 - открытая онлайн библиотека 4 М5 + М1 М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 М4 М5 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 Минимизация функционального представления - №56 - открытая онлайн библиотека 4 М5 +

+ М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 М4 М5 + Минимизация функционального представления - №56 - открытая онлайн библиотека 1 М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 М4 Минимизация функционального представления - №56 - открытая онлайн библиотека 5 + М1 М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 М4 Минимизация функционального представления - №56 - открытая онлайн библиотека 5 +

+ Минимизация функционального представления - №56 - открытая онлайн библиотека 1М2М3 М4 Минимизация функционального представления - №56 - открытая онлайн библиотека 5 + М1 М2М3 М4 Минимизация функционального представления - №56 - открытая онлайн библиотека 5 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2М3 М4 М5 +

+ М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2М3 Минимизация функционального представления - №56 - открытая онлайн библиотека 4 М5

Минимизация функционального представления - №202 - открытая онлайн библиотека

М1М2 М3М4М5 001 011 010 110 111 101 100

               
       
       
       

f(М12345) = М2 Минимизация функционального представления - №56 - открытая онлайн библиотека 3 М5 + М2 М4 Минимизация функционального представления - №56 - открытая онлайн библиотека 5 + М1 Минимизация функционального представления - №56 - открытая онлайн библиотека 2 М5

Аппарат работы с картами и их преимущество.

1) Простота применения .

2) Наглядность расположения интервалов.

Недостатки:

1) Сложность работы возростает намного быстрее, чем увеличивается число элементов функции.

2) Трудоемкость алгоритмизации.

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

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

МИНИМИЗАЦИЯ ФУНКЦИИ МЕТОДОМ КВАЙНА.

Максимальный интервал Ia , который не содержится ни в каком другом интервале Ia Ë Iк

где Iк - все интервалы функции, кроме Ia .

Рассмотрим функцию, заданную в СНФК:


N Ki F

В левой части двоичный эквивалент конституент,а в правой присутствует ли она в функциональном представлении или нет.

Кроме интервалов,представленные конституентами выделим другие интервалы более крупные.

Минимизация функционального представления - №240 - открытая онлайн библиотека Минимизация функционального представления - №241 - открытая онлайн библиотека 001 0х1

011 х11

100 1х0 - максимальные интервалы относительно конституент.

110 11х

Лемма.

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

Доказательство:

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

М = А + В Минимизация функционального представления - №2 - открытая онлайн библиотека = А + В

В – максимальный интервал

В Минимизация функционального представления - №2 - открытая онлайн библиотека Ì В - не максимальный интервал

Вычеркиванием терма Минимизация функционального представления - №2 - открытая онлайн библиотека – получим максимальный интервал.

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

Минимальной формой – называется тупиковаяформа, минимальной сложности

Выражения для максимальных интервалов называются простыми импликантами.

ТЕОРЕМА.

Все тупиковые ,а следовательно и минимальные формы содержатся в объединении всех простых импликант.

Доказательство:

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

Следовательно, тупиковой и минимальной формой есть объединение некоторых простых импликант из множества всех простых импликант.

Согласно вышеуказанной теореме 1-й шаг метода Квайна состоит в выделении простых импликант функции и составлении таблицы.

Строки соответствуют простым импликантам.

Столбцы – конституентам функции.

 
0х1      
х11      
1х0      
11х      

Если конституента содержится соответственном максимальном интервале, то в клетке ставится 1, если нет, то клетка остаётся пустой.

2-й шаг

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

1. Элементы подмножества суммарно покрывают все конституенты функции.

2. При вычеркивании любого элемента подмножества свойство 1 не выполняется.

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

ТЕОРЕМА

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

Доказательство:

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