FINISH (675729), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

ПРИМЕР: (минимизация булевой функции методом Квайна-Мак-Класки)

1) f⁴(x)=V(0,1,5,7,8,10,12,14,15)

(f=1)

f⁴(x)=&(2,3,4,6,9,11,13)

(f=0)

На этапе получения множества максимальных кубов целесообразно разделить множество ноль - кубов (К°(f)) на ряд подмножеств ,отличающихся количеством единиц .

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

ì 000X ü

ï X000 ÷ K°(f)=C°(f)

ï 0X01 ÷

Z(f)= í 01X1 ý S^a=36

ê X111 ú S^b=45

ê 111X ú

î 1XX0 þ

K¹(f)=C¹(f) S^a=10*3=30

S^b=40

Z(f)=C³(f) S^a=20

S^b=27

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

1. Определение ядра покрытия .

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

Kаждая строка таблицы - максимальный куб(простая импликанта).

Каждый столбец - существенная вершина булевой функции (безразличные наборы не включаются).

Элементы этой таблицы отражают отношение покрытия ,то есть на пересечении i-ой строки и j-ого столбца ставится некоторая отметка в том случае если i-ый максимальный куб покрывает j-ую вершину .

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

единицы(нуля).

Существенные вершины

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

Т(f)={1XX0}

1. Определение множества минимальных покрытий .

На этом этапе из множества максимальных кубов не принадлежащих ядру покрытия ,выделяются такие минимальные подмножества ,с помощью каждого из которых покрываются оставшиеся вершины (не покрытые ядром) .

Реализацию этого этапа целесообразно производить с использованием упрощенной таблицы.

В упрощенной таблице вычеркнуты все кубы принадлежащие ядру и вершины покрываемые ядром.

Для решения задачи 3-го этапа можно использовать один из 3-х методов или их комбинацию:

1. Метод простого перебора

2. Метод Петрика

3. Дальнейшее упрощение.

1)На данном этапе целесообразно ввести обозначение максимальных кубов и существенных вершин.

Максимальные кубы обозначены в таблице А...F

1-ый метод целесообразно применять для упрощенной таблицы небольшого объема .Этот метод не дает гарантии получения всех максимальных покрытий.

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

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

ì Tü ì Tü

C _min¹(f)= êAú C _min ¹(f)= êBú ,...

ïCú êCú

îE þ îE þ

2)Достоинство этого метода-получение всех минимальных покрытий.

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

Y=(AvB)(AvC)(CvD)(DvE)(EvF)=(AvBC)(DvCE)(EvF)=

=(AvBC)(DEvCEvDFvCEF)=

=(ADEvACEvADFvBCDEvBCEvBCDF)

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

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

1. Дальнейшее упрощение состоит в применение двух операций : а)Вычеркивание лишних строк.

б)Вычеркивание лишних столбцов.

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

В дальнейшем рекомендуется построить новую упрошенную таблицу.

В отношении новой таблицы можно использовать один из трех методов: 1) Метод простого перебора.

2)Метод Петрика.

3)Дальнейшее упрощение.

Функциональная полнота системы булевых функций.

Система булевых функций S={y₁,y₂,...,y_m}называется функционально полной ,если с помощью функций этой системы можно выразить любую сколь угодно сложную булеву функцию с использованием метода суперпозиции, возможно многократно.

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

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

1)S₁ ={ù,&,Ú}(булев базис)

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

Система S₁ ={ù,&,Ú} является избыточной так как из нее можно удалить одну из функций (& или Ú) без нарушения функциональной полноты.

Получаемые при этом системы S₂ ={ù,&} и S₃{ù,&,Ú}обычно называют сокращенным булевым базисом .

Недостающие операции( Ú в системе S₂ и & в системе S₃ ) могут быть выражены с помощью следствий из законов

____

Де Моргана : x₁V x₂= _{1 2}

_____

x₁ x₂= ₁ v ₂

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

Системы из одной функции S₄=¯(стрелка Пирса)

S₅=|(штрих Шеффера)

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

2)Базис Жегалкина S₆= {&, Å, 1}

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

Эта связь заключается в следующем :

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

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

Доказательство функциональной полноты некоторой системы

булевых функций можно осуществлять одним из двух способов:

1. С использованием теоремы о функциональной полноте .

2. С использованием конструктивного подхода .

Теорема о функциональной полноте (Пост - Яблонского).

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

1. cохраняющую константу ноль

2. cохраняющую константу единица

3. линейную функцию

4. монотонную функцию

5. самодвойственную функцию.

Замечательные классы булевых функций.

1. Булева функция называется сохраняющей константу ноль , если на нулевом наборе аргументов она принимает значение равное нулю, то есть f(0,0,0,...,0) = 0;

В противном случае функция относится к классу не cохраняющих константу ноль.

К функциям ,сохраняющим константу ноль относятся

f(x₁,x₂)= x₁ v x₂

f(x₁,x₂)= x_{1 *} x₂

К функциям не cохраняющим константу ноль относятся

f(x)= и f(x₁,x₂)=x₁~x₂

2.Булева функция называется сохраняющей константу единица , если на единичном наборе аргументов она принимает значение равное единице, то есть f(1,1,1,...,1)= 1;

В противном случае функция относится к классу не cохраняющих константу единица.

К функциям ,сохраняющим константу единица относятся

f(x₁,x₂)= x₁ v x₂

f(x₁,x₂)= x_{1 *} x₂

Характеристики

Список файлов реферата