WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 |
И. Л. Ерош ДИСКРЕТНАЯ МАТЕМАТИКА БУЛЕВА АЛГЕБРА, КОМБИНАЦИОННЫЕ СХЕМЫ, ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Учебное пособие 2001 УДК 519.6(075) ББК 22.19 E78 Ерош И. Л.

Е78 Дискретная математика. Булева алгебра, комбинационные схемы, преобразования двоичных последовательностей: Учеб. пособие/СПбГУАП.

СПб., 2001. 30 c.

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

Пособие ориентировано на студентов технических университетов, аспирантов и преподавателей дисциплины “Дискретная математика“ технических вузов.

Рецензенты:

кафедра радиосистем Санкт-Петербургского электротехнического университета;

канд. техн. наук доц. В. Н. Сасковец Утверждено редакционно-издательским советом университета в качестве учебного пособия СПбГУАП, 2001 © И. Л. Ерош, 2001 © 2 Предисловие Цифровые устройства (цифровые автоматы) обычно делятся на два класса: автоматы без памяти (однотактные автоматы, комбинационные схемы) и автоматы с памятью (многотактные автоматы). Комбинационные схемы составляют основу дискретных вычислительных и управляющих устройств. Они могут выполнять как самостоятельные функции: преобразователи кодов, дешифраторы и т. п., – так и входить в состав цифровых автоматов с памятью, реализуя функции переключения элементов памяти в новые состояния, выработку логических и управляющих сигналов. Сами элементы памяти могут быть построены в виде комбинационных схем с обратными связями.

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

1. БУЛЕВЫ ФУНКЦИИ И КОМБИНАЦИОННЫЕ СХЕМЫ 1.1. Понятие о булевых функциях.

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

Алгебра Буля оказалась очень удобным и эффективным математическим аппаратом для анализа и синтеза комбинационных схем.

Булевы функции определяют логику работы комбинационных схем следующего вида:

xx2 Комбинационная xсхема... F(x1, x2,..., x ) n x n где x1– xn, F { 0, 1}. Рассмотрим частные случаи.

Пусть n = 1, тогда входной сигнал x может принимать только два значения – 0 и 1, а выходной сигнал F(x) может обеспечивать четыре различных реакции на выходе. Таблица, в которой каждому набору входных сигналов сопоставляется значение выходного сигнала, называется таблицей истинности функции.

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

Таблица F1 = const 0, F2 = x, функция повторения x, F4 = const 1, F3 – инверсия аргуменмента x, x F1 F2 F3 Fобозначаемая x или x и называемая иног0 0 0 1 да “не x”, “отрицание x”.

При n = 2 получаем таблицу истинности 1 0 1 0 16 различных функций двух аргументов (табл. 2).

Таблица x1 x2 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 Среди функций двух аргументов имеются уже известные функции F0 и F15, соответственно, “константа 0” и “константа 1” – функции, не зависящие от аргументов, иногда называемые функции нуль аргументов. Функции F3 = x1 и F5 = x2 – функции повторения, соответственно, аргументов x1 и x2. Функции F12 = x1 и F10 = x2 – функции инверсии, соответственно, аргументов x1 и x2. Эти функции считаются функциями одного аргумента.

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

F1 – конъюнкция аргументов x1 и x2, обозначается: F1 = x1 & x2 = = x1 x2 = x1 x2 = x1 x2. Допустимыми являются все виды приведенных обозначений, но поскольку эта функция называется логическое умножение, функция “И”, то, как и в обычной алгебре, знак умножения часто опускается.

F7 – дизъюнкция аргументов x1 и x2, обозначается: F7 = x1 x2 = = x1 + x2. Обычно используют только первый вид обозначения. Эта функция называется логическое сложение, функция “ИЛИ”, но знак сложения “+” практически не используется.

Для приведенных функций в таблице имеются инверсии. Так, F14 = F (штрих Шеффера), F8 = F7 (стрелка Пирса), но поскольку функции Fи F8 играют очень важную роль в вычислительной технике, они будут рассмотрены подробнее ниже.

Новыми функциями также являются F9 и F6. Первая называется функцией совпадения (эквиваленция) и обозначается обычно F9 = x1 x2.

Вторая функция является ее инверсией и называется функцией сложения по модулю 2, т. е. F6 = = = x1 x2.

F9 x1 xФункции F13 и F11 называются функциями импликации и обозначаются, соответственно, F13 = x1 x2 и F11 = x2 x1 (словесное обозначение: F13 – “ x1 влечет x2”; F11 – “ x2 влечет x1”). Функции импликации играют очень важную роль в математической логике, так как описывают логику всех теорем достаточности, которые формулируются в виде:



“Если выполняется условие A, то следует B”. При построении комбинационных схем эти функции практически не используются.

Функции F2 и F4 из табл. 2 являются инверсиями функций импликации, соответственно F13 и F11.

1.2. Булевы функции трех аргументов Функции трех аргументов задаются на восьТаблица ми наборах. Количество функций трех аргуменx2 x3 F xтов равно 28 = 256.

Одной из функций трех аргументов является 0 0 0 мажоритарная функция. Таблица истинности этой 0 0 1 функции имеет следующий вид (табл. 3).

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

1.3. Булевы функции n аргументов.

СДНФ и СКНФ Булева функция n аргументов задается на 2n наборах. Число таких n функций равно.

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

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

– все полученные конъюнкции объединяются знаками дизъюнкции.

Например, для мажоритарной функции аналитическое выражение будет иметь вид F = x2 x3 x1 x3 x1x2 x1 x2 x3. (1) x1 x2 xАналитическое выражение функции вида (1) называют совершенной дизъюнктивной нормальной формой (СДНФ), при этом под совершенной формой понимают аналитическое выражение функции, когда во все конъюнкции входят все аргументы, т. е. все конъюнкции имеют ранг n;

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

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

– каждому нулю в таблице истинности ставится в соответствие дизъюнкция ранга n, где n – число аргументов функции; рангом дизъюнкции называют число аргументов, входящих в дизъюнкцию, причем в этой дизъюнкции аргумент входит без инверсии, Таблица если в соответствующем наборе он принимает значение 0, и с инверсией, если приниx2 x3 F F мает значение 1; x– все полученные дизъюнкции объединя0 0 0 1 ются знаками конъюнкции.

0 0 1 0 Возьмем, например, функцию F, представ0 1 0 1 ленную следующей таблицей истинности (табл. 4).

0 1 1 1 СДНФ этой функции представляет собой 1 0 0 0 шесть конъюнкций ранга 3, объединенные 1 0 1 1 знаками дизъюнкции, т. е. достаточно гро1 1 0 1 моздкое выражение. В то же время СКНФ 1 1 1 1 этой функции будет выглядеть так:

F = (x1 x2 ) ( x2 x3). (2) x3 xВ выражении (2) имеются две дизьюнкции, объединенные знаком конъюнкции.

1.4. Элементарные преобразования булевых выражений Часто преобразование булевых выражений выполняется с целью упрощения последних или, как говорят, с целью их минимизации. Легко обосновываются следующие правила минимизации:

– поглощения: x xy = x; x(x y) = x;

– склеивания: xy x y = x;

– обобщенного склеивания: xz y z xy = xz y z;

– x x y = x y.

Покажем, как можно применить правило склеивания для минимизации мажоритарной функции. Аналитическое выражение перепишем в следующем виде:

F = x2 x3 x1 x3 x1 x2 x1 x2 x3 x1 x2 x3 x1 x2 x3. (3) x1 x2 xПовторение конъюнкции x1x2x3 не меняет значение функции, так как Y Y = Y, где Y – любое булево выражение. Тогда, склеивая 1-й и 4-й члены, 2-й и 5-й, 3-й и 6-й, получаем эквивалентное выражение F = x2 x3 x1 x3 x1 x2. (4) Выражение (4) будет дизъюнктивной, нормальной формой функции, так как в каждую из конъюнкций входят не все аргументы функции.

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

Кроме того, так же просто обосновывается преобразование, называемое правилом де Моргана:

а) ;

x1x2 = x1 xб). (5) x1 x2 = x1 xПокажем, как применить правило де Моргана для вывода формулы СКНФ. В табл. 4 имеется значение функции, инверсной к F, т. е. F. Эта функция имеет только две единицы, поэтому СДНФ ее будет представлять собой две конъюнкции, каждая ранга 3, объединенные знаком дизъюнкции:

F = x3 x1. (6) x1 x2 x2 xПроинвертируем левую и правую части выражения (6) и применим к правой части правило де Моргана, тогда получим F = (x1 x2 ) ( x2 x3).

x3 xВ результате получена формула СКНФ функции F.

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

Области в диаграмме Вейча обозначим следующим образом: подчеркнутые столбцы или строки будут соответствовать истинному значению аргумента, а не подчеркнутые – ложному. Тогда диаграмма Вейча мажоритарной функции примет вид xxxИз полученной диаграммы Вейча легко выписывается минимальное выражение для мажоритарной функции F = x2 x3 x1 x3 x1 x2.





Возьмем некоторую функцию F четырех аргументов, диаграмма Вейча которой имеет вид B A 11 D C Эта функция принимает значение 1 на пяти наборах, отмеченных на диаграмме единицами. На остальных наборах функция принимает значение 0. СДНФ этой функции содержала бы пять конъюнкций каждая ранга 4, объединенные знаками дизъюнкций. Однако из диаграммы Вейча легко выписывается минимальное выражение функции в дизъюнктивной нормальной форме F =.

AC BC D Области в диаграмме Вейча обозначаются так, чтобы две соседние клетки соответствовали бы “склеивающимся” конъюнкциям (т. е. конъюнкциям, отличающимся значением только одного аргумента). Так, например:

.

ABC D ABC D = AC D Это обеспечивает наглядность минимизации.

В общем случае области в диаграммах Вейча для функций большого числа аргументов обозначаются кодом Грэя.

Таблица Особенностью этого кода является то, что две 0000 соседние комбинации отличаются значением только одного аргумента. Обычный двоичный код это0001 му условию не удовлетворяет.

0010 Код Грэя используется в цифровых кодовых дат0011 чиках, что позволяет сделать ошибку равномерной при смещениях токосъемников, при этом ошиб0100 ка равна 2-m где m – число двоичных разрядов ко0101 дового датчика. Это свойство кода Грэя исполь0110 зуется для обозначения областей в диаграммах 0111 0100 Вейча.

В табл. 5 приведен код Грэя для четырех аргу1000 ментов (разрядов). Если требуется построить код 1001 Грэя на меньшее число разрядов, то его легко по1010 лучить из имеющейся таблицы путем “вырезания” соответствующей части. Так, в приведенной 1011 таблице показано, как получить двухразрядный код 1100 Грэя. Если требуется построить код Грэя на пять 1101 разрядов, то код в таблице следует зеркально от1110 1001 разить вниз и добавить еще один разряд, причем в первой половине в этом разряде будут стоять нули, 1111 а во второй – единицы. Аналогично строятся коды Грэя на любое число разрядов.

П р и м е р. Минимизировать функцию семи аргументов, заданную диаграммой Вейча:

D C B A 11 11 11 1 1 1 G 1 1 1 F E Минимальное выражение в дизъюнктивной нормальной форме имеет вид F = AC E F AE F G ABC E F.

П р и м е р ы д л я п р а к т и ч е с к и х з а н я т и й.

1. Доказать с помощью диаграмм Вейча равенства, которые использовались для минимизации (поглощения и склеивания, а также правило де Моргана).

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

а) abcd abcd abcd abcd abcd abcd = ;

б) abc ab c abd bde =.

1.6. Минимизация частично определенных булевых функций Диаграммы Вейча могут использоваться для минимизации не только так называемых полностью определенных логических функций (когда функция в таблице истинности принимает только два значения: 0 или 1), но и для случая частичных (не полностью определенных) функций. При построении реальных цифровых устройств контроля и управления комбинационные схемы описываются, как правило, не полностью определенными булевыми функциями. Очень часто функции не определены на большом числе наборов. В таблице истинности и, следовательно, в диаграммах Вейча такие функции кроме 0 и 1 будут содержать еще и “–”; это означает, что такой набор никогда на вход устройства не поступает. Следовательно, поведение комбинационной схемы при таком наборе не имеет значения, и на месте “–” может быть произвольно поставлена либо 1, либо 0.

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

Пусть задана диаграмма Вейча некоторой не полностью определенной функции:

B A 1– – 1– D –– –C Приведенная функция имеет прочерки в шести клетках, в каждой из которых может быть поставлена как 1, так и 0. Следовательно, существует 26 = 64 различных способов доопределения булевой функции.

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

F = AC B D.

П р и м е р ы д л я п р а к т и ч е с к и х з а н я т и й.

Доопределить функцию и выисать минимальное выражение из диаграмм Вейча:

а) б) c B b A a 11 – 1 – – – –– 1 1 – 1 – e D – 1 – C 1 – 1 d – 1 1 – в) c b a –– 1 1 – – e 1 – 1 – – – – d 1.7. Проверка равенств в булевой алгебре Для того чтобы доказать равенство двух функций в булевой алгебре, например, F(x1, x2, …, xn) = P(x1, x2, …, xn), необходимо и достаточно показать, что на всех наборах аргументов x1, x2, …, xn левая часть равенства совпадает с правой.

Например:

(AB BC) BD = (B AC D).

Для доказательства этого равенства построим диаграммы Вейча для левой и правой части равенства. Левая часть равенства B B B B B A A A A A 11 1 1 1 1 1 11 1 1 1 1 11 11 1 1 1 1 1D 11 1 1 C AB BC ABBC BD ABBCBD Правая часть равенства B B A A 1 1 1 1 1 1 1 1 1 D 11 1 C Поскольку диаграмма Вейча для левой части совпадает с диаграммой для правой, то имеет место приведенное выше равенство.

П р и м е р ы д л я п р а к т и ч е с к и х з а н я т и й.

Упростить булевы выражения:

а) (YZ / XZP) = ;

XYZ X P б) ;

(AB AC D) (BC AC D) = в) M(ABC, ACD, BDAC) =.

Под M(X, Y, Z) понимается мажоритарная функция от аргументов X, Y, Z, где последние – любые аргументы или булевы выражения.

Pages:     || 2 | 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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