Минимизация булевых функций

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

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

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

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

Приведенные Минимизация булевых функций определения иллюстрируются на рис. 3.9, где сокращенное покрытие (см. рис. 3.9а,) и малые покрытия (рис. 3.9б) и (см. рис. 3.9, б) выражаются последующим образом:

Рис. 3.9 Сокращенное ( ) и малые покрытия ( , ) функции (а – сокращенное, б, в - малые)

Сокращенная форма представляет собой дизъюнкцию 4 обычных импликант, т. е. Экстремалями являются обыкновенные импликанты и ,которым соответствуют Минимизация булевых функций 1-кубы ( ) и ( ), а отмеченные верхушки - и либо соответственно (100) и (010).

Способ Квайна – Мак-Класки.Этот способ употребляется в случаях, когда функция задана в дизъюнктивной совершенной форме (либо таблицей истинности). Приведение в сокращенной форме осуществляется поочередным применением операций склеивании , где – конъюнкции переменных, хороших от . Огромному количеству конституент единицы, представленных в Минимизация булевых функций начальной форме, соответствует совокупа 0-кубов К0, а операции склеивания – объединения 2-ух 0-кубов, которые отличаются только одной координатой. Результатом такового объединения является 1-куб, в каком разные координаты начальных 0-кубов изменены эмблемой . Сравнивая попарно все 0-кубы. Получаем огромное количество 1-кубов К1. Применяя к К1 операцию склеивания, находим огромное количество 2-куюов К2 и т Минимизация булевых функций. д. Этот процесс длится до того времени, пока получаемое из Кs еще одно Кs+1 не окажется пустым обилием. В итоге огромное количество К0 преобразуется в комплекс кубов , при этом .

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

На втором шаге при извлечении экстремалей и образовании малого покрытия употребляется таблица покрытия. Ее строчки соответствуют Минимизация булевых функций обычным импликантам, а столбцы – конституентам единицы дизъюнктивной совершенной обычной формы данной функции, которые представляются 0-кубами (верхушками) комплекса кубов. В клеточку таблицы записывается метка, если обычная импликанта в данной строке покрывает верхушку в данном столбце. Экстремалям соответствуют те строчки таблицы, которые содержат единственную метку в каком-либо столбце Минимизация булевых функций. Удаляя строчки экстремалей и все ее столбцы, в каких эти строчки имеют метки, получаем более ординарную таблицу. На базе этой таблицы избираем обыкновенные импликанты, которые дополняют выделенное огромное количество экстремалей до малого покрытия функции.

Пример минимизации функции способом Квайна.Разглядим в качестве примера функцию от 4 переменных:

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

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

.

Обычным импликантам соответствуют неотмеченные кубы. Составляем таблицу покрытия , которому соответствует сокращенная форма:


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


Какие кубы избрать в качестве дополнительных? В каждом столбце мы должны избрать по одной метке. Если мы в первом столбце Минимизация булевых функций избираем метку, подобающую ( ), то в 3-ем столбце также необходимо избрать метку, соответственному этому же однокубу. Тогда во 2-м и в четвертом столбцах целенаправлено избрать метку, подобающую однокубу ( ). Избранные дополнительные однокубы вместе с экстремалью ( ) образуют покрытие функции, малая форма которой имеет вид: .

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

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

На карте Карно контура будут последующими:

Ясно, что 1-ый вариант предпочтительней, т.к. в него заходит наименьшее количество слагаемых.

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

Приведем пример для той же функции.

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


Для того чтоб функция приняла значение равное единице, довольно того, чтоб только какая-нибудь одна импликанта на строке приняла единичное значение.

Сначала оставляем наименьшую импликанту (10), которая перекрывает единицы в строчках 2,3,10,11. Потом обращаемся к 9-ой строке, что отвечает импликанте (101). Осталось разглядеть 12, 13 и 14 строчки. Общей для их является импликанта (011).

3.2. Задание

1. В Минимизация булевых функций таблице 1 заданы номера конституент, на которых логическая функция воспринимает значение, равное единице (номера конституент соответствуют функции ). Нужно провести ее минимизацию последующими способами:

- конкретных преобразований (с внедрением законов);

- при помощи n – мерного куба;

- карты Карно;

- таблиц Квайна.

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

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

Таблица 2.-

Номера конституент 1
-
-
-
-
-
-

3. Логическую функцию вашего варианта табл.2 запишите в СКНФ номерами конституент 0. Как необходимо видоизменять способы минимизации чтоб приспособить их к СКНФ? Произведите минимизацию вашей функции, записанной в СКНФ способами Карно и Квайна.

4. В табл.3 задана функция от 5 переменных номерами конституент Минимизация булевых функций 0 (номера конституент взять из без помощи других составленной таблицы истинности для функции). Нужно провести ее минимизацию способом Карно и Квайна (результаты способов минимизации должны совпасть). Выстроить логические схемы в базисах {не-или, не-и} для малой формы.

Таблица 3.-

Номера конституент 0
- - - -
- - - -
- - -
- - - -
- - - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- -
- -
- - -
- -
- - -
- -
- - -
- - -
- - -
- -
- - -

3.3. Контрольные вопросы

3.3.1. Дайте определение логической однородной функции.

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

3.3.3. Какая операция (закон) лежит в базе всех способов минимизации.

3.3.4. Дайте определение логического элемента. Что такое базис?

Лабораторная работа № 4

Тема: «Конечные автоматы с памятью»

Цель: Приобретение практических способностей синтеза конечных автоматов.

4.1. Теоретические сведения [1].

Главные определения.

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

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

Пусть – алфавит входной переменной , а – алфавит выходной переменной . Конечный автомат с n входами и m выходами характеризуется входным алфавитом и выходным алфавитом , при этом знаками входного алфавита Минимизация булевых функций служат слова длины n, а знаками выходного алфавита – слова длины m, где и .

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

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

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

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

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

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

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

Конечный автомат М определяется 2-мя характеристическими функциями Минимизация булевых функций:

;

,

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


Рис.4.1 Блок-схема конечного автомата

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

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

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

Представления конечных автоматов.Автомат может быть задан разными методами, к примеру, методом словесного описания его функционирования либо перечислением частей множеств , , , с Минимизация булевых функций указанием отношений меж ними. При анализе и синтезе конечных автоматов употребляют стандартные формы представления: таблицы, графы и матрицы. Элементы огромного количества , , комфортно пронумеровать порядковыми числами, начиная с нуля, к примеру: , и . Тогда характеристические функции и можно представить 2-мя таблицами, строчки которых соответствуют состояниям, а столбцы – входам. 1-ая таблица, именуемая таблицей переходов Минимизация булевых функций, соответствует функции , и ее клеточки заполняются номерами состояний , в которые перебегает автомат при воздействии , и состоянию в данный тактовый момент. 2-ая таблица, именуемая таблицей выходов, соответствует функции , и ее клеточки заполняются номерами выходов в данный тактовый момент, которые соответствуют воздействию и состоянию в тот же момент. К примеру, для данных Минимизация булевых функций множеств , , такие таблицы могут иметь вид:

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

3/0 3/1 3/1 3/0 2/0 2/0 2/0 0/0 1/0 1/0 2/1 0/1 3/0 3/1 3/1 1/1

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

На рис. 4.2 показан граф, построенный в согласовании с приведенной выше таблицей переходов. Потому что из состояния 0 автомат перебегает в состоянии 1,2 и 3, то из верхушки 0 графа Минимизация булевых функций исходят дуги к верхушкам 1, 2 и 3. При всем этом переход в состояние 1 совершается под воздействием 2 и ему соответствует выход 0, потому дуга из вершин 0 и 1 помечается как 2/0. Переход в состояние 2 совершается под воздействием 1 и ему соответствует выход 0, потому дуга из верхушки 0 в 2 помечается как 1/0. Переходы в состояние 3 совершаются под воздействиями 0 и 3 и Минимизация булевых функций им обоим соответствует выход 0, потому дуга из верхушки 0 в 3 помечается как дизъюнкция . Аналогично определяются и другие дуги графа. Так рассматриваемый автомат перебегает из состояния 2 в 2 под воздействиями 1 и 2, которым соответствуют выходы 0 и 1. Как следует, петля при верхушке 2 помечается как .

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

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

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

Отсюда видно, что комбинационная схема обязана иметь четыре входа, надлежащие входным переменным , и переменным состояния , , также три выхода, надлежащие переменным состояния , и выходной переменной Минимизация булевых функций . Синтезировав комбинационную схему, подобающую приобретенной таблице и введя два элемента задержки ЭЗ1 и ЭЗ2, получим структурную схему автомата (рис. 4.3).

Рис. 4.3 Структурная схема конечного автомата

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

Отличительной особенностью триггера как многофункционального устройства является свойство запоминания двоичной инфы. Под памятью триггера Минимизация булевых функций предполагают способность оставаться в одном из 2-ух состояний и после прекращения деяния переключающего сигнала. Приняв одно из состояний за «1», а другое за «0», можно считать, что триггер хранит (помнит) один разряд числа, записанного в двоичном коде.

Характеристическое уравнение триггера: , где

- значение выходной переменной на ( ) - м такте;

- значение входной переменной на - м такте Минимизация булевых функций;

- значение выходной переменной на - м такте.

Типы триггеров: RS, JK, D, T

R (Reset – сброс) – вход для раздельной установки триггера в состояние «0» (Q=0, ØQ=1);

S (Set – установка) – вход для раздельной установки триггера в состояние «1» (Q=1, ØQ=0);

J (Jerk – неожиданное включение);

К (Kill – неожиданное отключение);

Т (Toggel – релаксатор) счетный вход триггера;

D (Delay Минимизация булевых функций – задержка, Drive - передача) информационный вход для установки триггера в «0» либо «1»;

RS – триггер


ministerstvo-obrazovaniya-i-nauki-respubliki-kazahstan.html
ministerstvo-obrazovaniya-i-nauki-rk.html
ministerstvo-obrazovaniya-i-nauki-rossijskoj-federacii-metodicheskie-rekomendacii-po-napisaniyu-i-oformleniyu-kursovih.html