bulevy-funktsii-i-postr.-log.-skhem (Методические документы)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИРОССИЙСКОЙ ФЕДЕРАЦИИМОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, РАДИОТЕХНИКИ ИЭЛЕКТРОНИКИМИРЭАЕ.И. ИСМАГИЛОВАБУЛЕВЫ ФУНКЦИИ И ПОСТРОЕНИЕЛОГИЧЕСКИХ СХЕМУЧЕБНОЕ ПОСОБИЕпо курсу «Дискретная математика»для студентов, обучающихся по направлениям09.03.01 «Информатика и вычислительная техника»,11.03.03 «Конструирование и технология электронных средств»,11.03.04 «Электроника и наноэлектроника»МОСКВАМИРЭА2015УДК 519.1 (075)ББК 22.176я73И 87Утверждено редакционно-издательским советом МИРЭА в качестве учебного пособия для студентовПодготовлено на кафедре общенаучных дисциплинРецензенты: к.ф-м.н.

Т.А. Кузнецова, к.ф-м.н. Ф.М. СабироваИсмагилова Е.И.И 87 Булевы функции и построение логических схем: учебноепособие / Е.И. Исмагилова — М.: МИРЭА, 2015. — 160 с.ISBNУчебное пособие предназначено для студентов МИРЭА первого курса, изучающих дисциплину «Дискретная математика» иобучающихся по направлениям подготовки 09.03.01, 11.03.03,11.03.04.В пособии рассмотрены основы булевой алгебры, полнотасистем булевых функций, минимизация нормальных форм, приложение булевой алгебры к синтезу логических схем. По каждойтеме даны теоретические сведения (основные определения и теоремы), приведены подробно разобранные решения типовых задач, приложены задачи для самостоятельного решения.Материал пособия позволяет самостоятельно разобраться нетолько в математической, но и в схемотехнической сущности булевых функций, выработать практические навыки необходимыедля дальнейшего изучения специальных дисциплин.ISBN 978-5-7339-© Исмагилова Е.И., 2015© МИРЭА, 2015Для описания алгоритмов работы цифровых устройств необходим соответствующий математический аппарат.

Такой аппаратдля решения задач формальной логики в середине прошлого векаразработал ирландский математик Джорж Буль (1815 – 1864).Этот математический аппарат получил название булевой алгебры.1. Интерпретация булевой функцииВходные полюсыx1x2…ЦифровоеустройствоВыходной полюсyxn1.1. Обобщённая схема логического устройства.Рассмотрим некоторое цифровое устройство (рис.1.1.), содержащее входные полюсы, на которые извне поступают сигналы,и выходной полюс, с которого снимают сигнал.

Сигналы на полюсы поступают в виде высокого или низкого потенциала. Если высокому потенциалу поставить в соответствие 1, а низкому – 0, токаждый из полюсов цифрового устройства может находиться водном из двух состояний (0 или 1). Чтобы различать входные ивыходные полюсы, их упорядочивают и обозначают разными переменными. На рис.1.1.

входные полюсы цифрового устройстваобозначены x1, x2 ,..., xn , выходной - y . Введение переменныхпозволяет в любой момент времени каждой комбинации состояний входных полюсов поставить в соответствие п-разрядныйнабор  x1, x2 ,..., xn  , состоящий из нулей и единиц, а выходномуполюсу соответствующий одноразрядный набор  y  .3Определение 1.1. Набор  x1, x2 ,..., xn  , где xi 0,1 , 1  i  n ,называют двоичным набором, а его элементы xi - компонентами.Кратко набор  x1, x2 ,..., xn  обозначают x n или x .Чтобы описать поведение цифрового устройства, необходимопостроить таблицу зависимости между входными и выходнымидвоичными наборами.

Возникает вопрос: сколько строк и столбцов должна содержать эта таблица?Чтобы определить количество строк, необходимо посчитатьсколько существует всевозможных п-разрядных двоичных наборов xn   x1, x2 ,..., xn  . Для этого упорядочим наборы, присвоивим определённые номера.Определение 1.2. Номер набора xn   x1, x2 ,..., xn  – это число   x 2 xnni 1in i.В качестве примера упорядочим множество 3-х разрядныхдвоичных наборов x3   x1, x2 , x3  .Набор x3   x1, x2 , x3  000 001 010 011100Номер набора3 xi  23i  0  22  0  21  0  20  0i 13 xi  23i  0  22  0  21  1 20  1i 13 xi  23i  0  22  1 21  0  20  2i 13 xi  23i  0  22  1 21  1 20  3i 13 xi  23i  1 22  0  21  0  20  4i 141013 xi  23i  1 22  0  21  1 20  5i 13110 xi  23i  1 22  1 21  0  20  6111 xi  23i  1 22  1 21  1 20  7i 13i 1Всего 3-х разрядных двоичных наборов 8  23 .Утверждение 1.1.

На множестве 0,1 можно построить ровно 2n различных двоичных наборов длины п.Доказательство. Проведём индукцию по длине набора n .Для n  1 можно построить различных наборов из одной буквы 2  21 . При построении различных наборов из двух букв, длякаждого набора из одной буквы существует ровно 2 возможностидобавить одну букву в конец (рис.1.2). Поэтому различных наборов длины n  2 получаем 2  2  22 .n 1n2001101Рис.1.2. Построение различных наборов издвух букв на множестве.Предположим, что для наборов длины  n  1 утверждениевыполняется, тогда существует ровно 2n1 различных наборовдлины  n  1 .

Для каждого набора длины  n  1 существует ровно 2 возможности добавить одну букву в конец. Так как наборовдлины  n  1 всего 2n1, то различных наборов длины n получится 2  2n 1  2n. Утверждение доказано.□5Теперь можно определить количество строк и столбцов втаблице, описывающей поведение цифрового устройства:количество строк = 2n + строка для заголовка,гдеколичествоп-разрядныхдвоичныхнаборов2n xn   x1, x2 ,..., xn  ;количество столбцов = столбец для номера набора + количество входных переменных + столбец для выходной переменной.Получаем, что для цифрового устройства, представленногона рис.1.1, таблица 1.1, определяющая зависимость выходной переменной y от совокупности входных переменных  x1, x2 ,..., xn  ,имеет количество строк, равное 2n  1 и количество столбцов,равное 1  n  1  n  2 .№x1 x201…00…100…2n  2 12n  1 1Таблица 1.1.y… xn 1 xn…………00…00011……1  2n  21 …11 2n 1При построении таблицы 1.1: наборы  x1, x2 ,..., xn  выписываются в порядке возрастания ихномеров (сверху вниз); через i 0,1 0  i  2n  1 обозначается значение выход-ной переменной y на i -ом наборе.Построенная таблица 1.1 называется таблицей истинности.Если обозначить через E2 = {0, 1} – основное множество, ачерез B n   x1, x2 ,..., xn  / i xi  E2  - множество всех п-6разрядных двоичных наборов, то таблица истинности описываетотображение множества Bn в множество E2.Определение 1.3.

Отображение f  x1,..., xn  : Bn  E2 называется всюду определённой булевой функцией и записываетсяy  f  x1, x2 ,..., xn  или y  f x n . Таким образом, поведение цифрового устройства (рис.1.1.)описывается булевой функцией y  f  x1, x2 ,..., xn  .2. Логические элементыОпределение 2.1. Под логическим элементом будем понимать цифровое устройство, реализующее некоторую булевуфункцию f  x1, x2 ,..., xn  .Для логического элемента введём условное графическое обозначение, которое показано на рис.2.1.Входыx1x2fВыход…xnРис. 2.1. Условное графическое обозначение логического элемента, реализующего булеву функцию.Любой логический элемент характеризуется:1) наличием одного или нескольких входов, на которые подаются входные сигналы (входные переменные);2) наличием выхода, на котором формируется выходной сигнал (выходная переменная).3) определённой булевой функцией f  x1, x2 ,..., xn  , котораяотображает зависимость выходного сигнала от входных сигналов.73.

Булевы функции Множество всех булевых функций f x nобозначают Р2 .При этом обычно полагают, что n  0 .Так как в таблице булевой функции f  x1, x2 ,..., xn  ( n  1)стандартное расположение наборов идёт в порядке возрастанияих номеров (сверху вниз) (табл.

3.1.), то функцию f x n удобно задать двоичным набором её значений  , ,..., , которыйобозначают  2f   0 ,1,...,или f  x    , ,...,.2 1 0nnn№x1 x201…00…100…2n  1 12n 11012n 1Таблица 3.1.n… xn 1 xn f x …………00…10101…1… 2n 1По утверждению 1.1, количество различных двоичных набоnров  2f   0 ,1,...,2n 1nдлины 2n равно 22 . Сколько сущеnствует различных двоичных наборов  2f , столько и булевыхфункций, зависящих от n переменных.

Поэтому число функций,nзависящих от n переменных, равно 22 .Булевы функции f  x1, x2 ,..., xn  , зависящие от n переменных, называют п-местными.Нульместные булевы функции0Число нульместных булевых функций равно 22  2 . Этимифункциями являются константы 0 и 1.8Одноместные булевы функции1Число булевых функций от одной переменной равно 22  4 .Обозначим эти функции через  j  x  , где j  0,1, 2,3 . В таблице 3.2 представлено множество всех булевых функций одной переменной.Таблица 3.2.х  0 1  2  30 0 0 1 11 0 1 0 1Описание множества булевых функций от одной переменнойдано в таблице 3.3.Таблица 3.3.Двоичный наборФормулафункции0  x   01.

0  x    00 1  x   x2. 1  x    01№3. 2  x   10 2  x   x4. 3  x   113  x   1Название функцииКонстанта 0Тождественная функцияИнверсия (отрицание переменной х, функция НЕ)Константа 1Если значения функции не зависят от значений переменной х,то говорят, что х – фиктивная переменная. Среди функций, зависящих от одной переменной  j  x  , переменная х является фиктивной для констант 0 и 1.Для некоторых булевых функций существуют стандартныеграфические изображения логических элементов, которые называют вентилями.Вентиль, реализующий инверсию, показан в таблице 3.4. Ввентилях кружок на выходе применяется для обозначения инвертирования сигнала.9Таблица 3.4.НазваниевентиляГрафическое обозначениеПример реализуемойфункцииИнвертор НЕYXX 0 1Y 1 0Двухместные булевы функции2Число булевых функций двух переменных равно 22  16 .x1 x2 f 0 f1 f 2 f3 f 4 f5 f 6 f 7 f8 f9 f10 f11Таблица 3.5.f12 f13 f14 f15001111000101000000010010001101000101011001111000100110101011110111101111В таблице 3.5 представлено множество всех булевых функций двух переменных, которые обозначены через fi  x1, x2  , гдеi  0,1,...,15 .