Упрощение и минимизация логических функций

МИНИСТЕРСТВО ЭНЕРГЕТИКИ И УГОЛЬНОЙ ПРОМЫШЛЕННОСТИ

СЕВАСТОПОЛЬСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ ЯДЕРНОЙ ЭНЕРГИИ И ПРОМЫШЛЕННОСТИ

Кафедра КС

Вычислительная работа №1

По дисциплине: Прикладная Теория Цифровых Автоматов

На тему: «Минимизация логических функций »

Вариант №22

Выполнил:

Студент 513 класса

Шевчук В.И.

Проверил:

К.т.н., доцент кафедры КС

Моисеев Д.В.

Севастополь– 2013 г.

СОДЕРЖАНИЕ

 

ПЕРЕЧЕНЬ ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ.. 3

ВВЕДЕНИЕ. 4

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 5

1.1 ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫЛОГИКИ.. 5

1.2 УПРОЩЕНИЕ И МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ.. 6

1.3 РЕАЛИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ.. 7

2. РЕАЛИЗАЦИЯ ПРАКТИЧЕСКОГО ЗАДАНИЯ.. 9

2.1 ЦЕЛЬ РАБОТЫ.. 9

2.2 ЗАДАНИЕ 1. 9

2.3 ЗАДАНИЕ 2. 10

ВЫВОД.. 17

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.. 18

 

 

 

ПЕРЕЧЕНЬ ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ

 

СДНФ - Соверше́нная дизъюнкти́вная норма́льная фо́рма

СКНФ - Соверше́нная конъюнкти́вная норма́льная фо́рма

ДНФ - Дизъюнкти́вная норма́льная фо́рма

КНФ - Конъюнкти́вная норма́льная фо́рма

 

ВВЕДЕНИЕ

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

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Основные понятия алгебры логики

 

 

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

При проектировании логических схем в качестве математического аппарата применяется алгебра логики или "булева" алгебра. Алгебра логики в качестве аргументов использует логические переменные. Логические переменные и функции от них могут быть либо истинными (равными единице), либо ложными (равными нулю).Основными операциями или функциями алгебры логики являются операции "И" (конъюнкция), "ИЛИ" (дизъюнкция) и "НЕ" (отрицание).

Аксиомы и теоремы алгебры логики.

	A=1, если A¹0	A=0, если A¹1
	0·0=0	1+1=1
	1·1=1	0+0=0
	1·0=0	0+1=1
	=1	=0
	A+0=A	A·1=A
	A+1=1	A·0=0
	A+A=A	A·A=A
	=	=A
	A+ =1	A· =0
	A·(A+B)=A	A+A·B=A
12.	= · ·	= + + - Теорема де Моргана

Теорема де Моргана наглядно доказывается через составление таблиц истиности и их сравнений.

 

Законы алгебры логики

 

Закон коммутативности:

для умножения АВ=ВА

для сложения А+В=В+А

Закон ассоциативности:

для умножения А(ВС)=(АВ)С

для сложения А+(В+С)=(А+В)+С

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

умножения по отношению к сложению А(В+С)=АВ+АС

сложения по отношению к умножению А+ВС=(А+В)(А+С)

 

Аксиомы и теоремы, записанные слева, двойственны аксиомам и теоремам, записанным справа, Двойственность определяется, как изменение всех знаков операции »И» на знаки операции «ИЛИ», всех знаков операции «ИЛИ» на знаки операции «И», всех нулей на единицы и всех единиц на нули. Двойственность является одним из основных свойств алгебры логики и означает, что если F(A,B,C) и F (A,B,C) - двойственные функции то

=F (, , )

Упрощение и минимизация логических функций

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

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

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

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

Минтермы логической функции отмечаются единицами в

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

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

Примечание: количество соседних отмеченных минтермов в группе должно быть пропорционально ; объединенные в группы минтермы на картах Карно (отмеченные клетки) должны образовывать либо форму квадрата, либо форму прямоугольника.