Файл: Анализ и синтез комбинационных схем.doc

Федеральное агентство железнодорожного транспорта

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

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

«петербургский государственный университет путей сообщения»
Кафедра «Автоматика и телемеханика на железных дорогах»

АНАЛИЗ И СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ

Методические указания по курсу

«Теория дискретных устройств»

№1

Санкт-Петербург

ПГУПС

2011

1Цель работы

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

2Основные понятия

2.1Понятие комбинационной схемы и функции алгебры логики

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

Комбинационная логическая схема имеет n входов и один выход y (рис. 1). Входы и выходы являются двоичными, т. е. могут принимать только два значения: 0 или 1. Внутренняя структура КС построена также на двоичных элементах.

Рис. 1. Комбинационная схема с n входами
Примером двоичного входа является кнопка x, которая может быть нажата (x = 1) или не нажата (x = 0), а примером двоичного выхода – лампочка y, которая может гореть (y = 1) или не гореть (y = 0).

Математическим аппаратом для описания КС являются ФАЛ (булевы функции). ФАЛ от n переменных f(x₁, x₂, …, x_n) можно задать с помощью таблицы истинности (табл. 1).

Таблица 1

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

№	x₁	x₂	x₃	y
0	0	0	0	1
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	0
6	1	1	0	1
7	1	1	1	0

Таблица содержит восемь строк, каждая из которых соответствует одному из возможных состояний всех трех кнопок x₁, x₂, x₃. Значение y в строке определяет состояние лампочки при данном состоянии входов (рис. 2). Например, запись в строке № 0 означает, что если все три кнопки не нажаты (x₁= x₂= x₃=0), то лампочка горит (y=1).

Рис. 2. Комбинационная схема
Особенностью ФАЛ является то, что все переменные и сами функции принимают только два значения. Областью определения ФАЛ от n переменных является множество двоичных наборов, число которых равно 2ⁿ. Каждому двоичному набору сопоставляется нулевое или единичное значение функции. Соответственно областью значений ФАЛ является множество {0, 1}.

Задать ФАЛ можно перечислением тех двоичных наборов, на которых функция равна 1. Эти наборы называются разрешенными. Например, функция y из таблицы 1 задается множеством (000, 011, 100, 110). Каждый двоичный набор N есть некоторое двоичное число, которое может быть переведено в десятичное по формуле:

(1)

где i – номер разряда, i = 0, 1, 2, …, n;

C_i – коэффициент при i-м разряде, C_i= 0или 1;

2ⁱ – вес i-го разряда.

Например,

.

В таблице 1 в левом крайнем столбце приведены десятичные эквиваленты двоичных чисел. Таким образом, ФАЛ можно задать также с помощью множества десятичных чисел, соответствующих разрешенным двоичным наборам. Например, функция y из таблицы 1 задается следующим множеством: (0,3,4,6).

Можно показать, что число ФАЛ от nпеременных равно

. Это число быстро растет с ростом n. Поэтому уже при n = 4 практически нет возможности изучить каждую функцию. Однако оказывается, что в этом нет необходимости. Существуют три функции, называемые инверсия (НЕ – логическое отрицание), дизъюнкция (ИЛИ – логическое сложение) и конъюнкция (И – логическое умножение), с помощью которых можно выразить все другие ФАЛ от любого числа переменных. Данные три функции образуют функционально полную систему функций, или базис.

Функции И, ИЛИ, НЕ задаются соответственно таблицами 2, 3, 4, из которых следует их содержательный смысл. Функция И равна 1 только тогда, когда обе переменные равны 1. Обозначается следующим образом:

(2)

Функция ИЛИ равна 1, если хотя бы одна из переменных равна 1. Обозначается следующим образом:

(3)

Функция НЕ принимает значение, противоположное значению входной переменной. Обозначается следующим образом:

(4)
Таблица 2

Таблица истинности функции И

№	x₁	x₂	y
0	0	0	0
1	0	1	0
2	1	0	0
3	1	1	1

Таблица 3

Таблица истинности функции ИЛИ

№	x₁	x₂	y
0	0	0	0
1	0	1	1
2	1	0	1
3	1	1	1

Таблица 4

Таблица истинности функции НЕ

№	x	y
0	0	1
1	1	0

Введение специальных знаков логических операций И, ИЛИ, НЕ позволяет задавать ФАЛ в алгебраической форме.

Рассмотрим, например, функцию

(5)

Для того чтобы перейти от алгебраической записи ФАЛ к таблице истинности, используют аксиомы алгебры логики, вытекающие непосредственно из таблиц 2, 3, 4:

(6)

(7)

(8)

Рассчитаем, например, значение функции (5) при x₁=1, x₂=0, x₃=1:

(9)

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

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

в таблице истинности выбираются все наборы, на которых функция равна 1;
выписываются конъюнкции, соответствующие этим наборам. При этом, если переменная x₁входит в данный набор как 0, то она записывается с отрицанием, в противном случае она записывается без отрицания;
все полученные конъюнкции соединяются между собой знаками дизъюнкции.

Применение данного алгоритма к таблице 1 дает следующий результат:

(10)

Полученная форма записи ФАЛ называется дизъюнктивной совершенной нормальной формой (ДСНФ).

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

в таблице истинности выбираются все наборы, на которых функция равна 0 (такие наборы называются запрещенными);
выписываются дизъюнкции, соответствующие этим наборам. При этом, если переменная x₁входит в данный набор как 0, то она записывается без отрицания, в противном случае она записывается с отрицанием;
все полученные дизъюнкции соединяются между собой знаками конъюнкции.

Применение данного алгоритма к таблице 1 дает следующий результат: