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

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Сибирский государственный индустриальный университет»

Кафедра автоматизированного электропривода и промышленной электроники

Курсовая работа

по дисциплине «Основы микропроцессорной техники»

Тема

«Минимизация булевых функции и комбинационных схем»

Новокузнецк, 2016

Задание на курсовую работу

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

2.Минимизировать одним из известных методов с обоснованием.

3.Составить принципиальную схему в базисе И-НЕ для четного варианта либо ИЛИ-НЕ для нечетного в соответствии с ГОСТом.

4.Составить схему релейно-контактного эквивалента логического устройства, поставив в соответствие логической переменной X замыкающий контакт, X-размыкающий, функции F-исполнительное устройство (обмотку реле).

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

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

Таблица 1- Задание для курсовой работы

Содержание

Введение

1. Основные понятия булевой алгебры

2. Системы задания булевых функций

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

3.1 Метод Квайна - Мак-Класки

3.2 Метод карт Карно

Выполнение задания

Заключение

Список используемой литературы

Введение

Конституентой единицы (коньюнктивным термом) называется функция F(x1,x2,...,xn), принимающая значение единицы только на единственном наборе.

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

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

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

Например. Выпишем СДНФ для функций, заданных таблицей истинности (таблица 2).

Таблица 2- Таблица истинности

(1)

? СКНФ (2)

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

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

Конституента нуля записывается в виде элементарной дизъюнкции всех переменных. Каждому набору соответствует своя конституента нуля. К примеру, набору 0110 переменных x₁,x₂,x₃,x₄ соответствует конституента нуля .

СКНФ представляется как конъюнкция конституент нуля, соответствующих нулевым наборам функции.

1.Основные понятия булевой алгебры

Главное понятие алгебры логики - высказывание. Высказывание - это связное повествовательное предложение, о котором можно сказать, что оно истинно или ложно.

Всякое высказывание разрешено обозначить символом x и считать, что , если высказывание истинно, а - если высказывание ложно. Истинному высказыванию соответствует утверждение - «Да», ложному высказыванию - утверждение - «Нет».

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

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

Булевой функцией от n аргументов называется любая функция F(x1,x2,…,xn) от n аргументов, заданная на множестве и принимающая значение в том множестве .

2.Системы задания булевых функций

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

При табличном способе булева функция F(x1,…,xn) задается таблицей истинности (таблица 3 и 4). В левой части, которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах.

Под двоичным набором понимается состав значений аргументов x1,x2,…,xn булевой функции F. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В таблице 3 и 4 перечислены все двоичные наборы соответственно длины 3 и 4.

Таблица 3 Таблица 5

Таблица 6 - Таблица истинности булевой функции

1. В СДНФ функции F заменим все конституенты единицы их двоичными номерами: F = 0000?0001?0010?0110?1110?1111

2. Образуем группы двоичных номеров. Признаком образования і-й группы является і единиц в двоичном номере конституенты единицы (таблица 7).

3. Склеим номера из соседних групп таблицы 7. Склеиваемые номера обозначим звездочками (номер отмечается в том случае, если участвует в склеивании хотя бы один раз). На месте разрядов, по которым произошло склеивание, проставляются прочерки. Результаты склеивания занесем в таблицу 8.

4. Имеем пять простых импликант: 000-; 00-0; 0-10; -110; 111-.

Таблица 7 Таблица 8

Таблица 9 - Импликантная матрица

5. Строим импликантную матрицу (таблица 9). По таблице определяем совокупность простых импликант - 000- ,0-10 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам:

(3)

3.2 Карты Карно

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

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

При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. К примеру, для функции двух переменных А и В (рисунок 3) карта Карно имеет вид:

Рисунок 3 - Карта Карно для булевой функции двух переменных

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

В примере на рисунке 3 пара единиц верхней строки охватывается импликантой В (т.е. обе клетки имеют общий аргумент В). Пара единиц правого столбца накрывается импликантой B, как общей для обеих клеток. Следовательно, минимальная ДНФ функции F(A,B) = В ? B.

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

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

. (4)

Карта Карно, состоящая из 2³ = 8 клеток, может быть размечена, как показано на рисунке 4.

Рисунок 4 - Карта Карно для трёх переменных

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

. (5)

Выполнение задания

Таблица 10 - Таблица истинности

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

Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные:

если значение переменной равно 0, то записывается сама переменная;

если значение переменной равно 1, то записывается инверсия этой переменной

Соединить элементарные дизъюнкции знаком конъюнкции.

- СКНФ

Минимизация СКНФ с помощью Карты Карно (рисунок 5):

Рисунок 5 - Карта Карно для четырех переменных.

-

МКНФ

По закону де - Моргана (закон общей инверсии ( )) инвертируем МКНФ:

Запишем функцию в МКНФ:

Исходя из задания, логические элементы представляет в виде замыкающих контактов, а - в виде размыкающих контактов. Логическую функцию F представляем в виде обмотки реле. Из данных условий построим схему релейно-контактного эквивалента логического устройства (рисунок 7):

Составляем программу на языке Паскаля:

program Proxy;

var{описание переменных величин} X1, X2, X3, X4, Y1, Y2, Y3, Y4,F: boolean{оператор логический (булевский)};

begin{оператор начала}

write{Оператор вывода} ('Введите значение переменной X1:');

readln{Оператор ввода};

write{Оператор вывода} ('Введите значение переменной X2:');

readln{Оператор ввода};

write{Оператор вывода} ('Введите значение переменной X3:');

readln{Оператор ввода};

write{Оператор вывода} ('Введите значение переменной X4:');

readln{Оператор ввода};

Y1:={оператор присваивания}X2 and X3 and (not X4);

Y2:={оператор присваивания}(not X1) and X2 and X4;

Y3:={оператор присваивания} (not X1) and (not X2) and (not X3);

Y4:={оператор присваивания} X1 and (not X2) and X3;

F:={оператор присваивания}Y1 and Y2 and Y3 and Y4;

writeln(F){Оператор вывода};

end.{оператор окончания}

Заключение

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

Список используемой литературы

1. Владимиров Д.А., Булевы алгебры - М., Издательство «Наука» 1969.

2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.

3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.

4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.

5. Новиков Ю.В. Основы микропроцессорной техники: учебное пособие / Ю.В.Новиков, П.К.Скоробогатов. - 4- е изд., испр.- М.: Интернет - Унивеситет Информационных Технологий; Бином. Лаборатория знания, 2009. - 357с.

Размещено на Allbest.ru