стр. 1
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

IEIENOA?NOAI IA?ACIAAIE? ?INNEENEIE OAAA?AOEE
Naieo-Iaoa?ao?aneee
ainoaa?noaaiiue oieaa?neoao ay?ieinie?aneiai i?eai?ino?iaiey




И. Л. Ерош




ДИСКРЕТНАЯ МАТЕМАТИКА
БУЛЕВА АЛГЕБРА, КОМБИНАЦИОННЫЕ СХЕМЫ,
ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Учебное пособие




Naieo-Iaoa?ao?a
2001
УДК 519.6(075)
ББК 22.19
E78

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



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




Рецензенты:
кафедра радиосистем Санкт-Петербургского электротехнического университета;
канд. техн. наук доц. В. Н. Сасковец




Утверждено
редакционно-издательским советом университета
в качестве учебного пособия




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




3
1. БУЛЕВЫ ФУНКЦИИ И КОМБИНАЦИОННЫЕ СХЕМЫ

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

x1
Комбинационная
x2
x3 схема
... F(x1, x2, ..., xn)
xn


где x1– xn , F ? { 0, 1}. Рассмотрим частные случаи.
Пусть n = 1, тогда входной сигнал x может принимать только два
значения – 0 и 1, а выходной сигнал F(x) может обеспечивать четыре
различных реакции на выходе. Таблица, в которой каждому набору вход-
ных сигналов сопоставляется значение выходного сигнала, называется
таблицей истинности функции.
Для комбинационных схем с одним входом таблицы истинности
всех булевых функций, описывающих логику работы схемы, примут
вид (табл. 1).
4
Таблица 1
F1 = const 0, F2 = x, функция повторения x,
F4 = const 1, F3 – инверсия аргуменмента x,
x F1 F2 F3 F4
обозначаемая ? x или x и называемая иног-
0 0 0 1 1
да “не x”, “отрицание x”.
1 0 1 0 1
При n = 2 получаем таблицу истинности
16 различных функций двух аргументов
(табл. 2).
Таблица 2

x 1 x 2 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 0 0 0 0 0 0 0 0 0 1 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
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Среди функций двух аргументов имеются уже известные функции
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 1
(штрих Шеффера), F8 = F7 (стрелка Пирса), но поскольку функции F14
и F8 играют очень важную роль в вычислительной технике, они будут
рассмотрены подробнее ниже.
5
Новыми функциями также являются F9 и F6 . Первая называется
функцией совпадения (эквиваленция) и обозначается обычно F9 = x1 ? x2.
Вторая функция является ее инверсией и называется функцией сложе-
ния по модулю 2, т. е. F6 = F9 = x1 ? x2 = x1 ? x2 .
Функции F13 и F11 называются функциями импликации и обознача-
ются, соответственно, F13 = x1 > x2 и F11 = x2 > x1 (словесное обозна-
чение: F13 – “ x1 влечет x2”; F11 – “ x2 влечет x1”). Функции импликации
играют очень важную роль в математической логике, так как описыва-
ют логику всех теорем достаточности, которые формулируются в виде:
“Если выполняется условие A, то следует B”. При построении комбина-
ционных схем эти функции практически не используются.
Функции F2 и F4 из табл. 2 являются инверсиями функций имплика-
ции, соответственно F13 и F11 .
1.2. Булевы функции трех аргументов
Функции трех аргументов задаются на вось-
Таблица 3
ми наборах. Количество функций трех аргумен-
x1 x2 x3 F тов равно 28 = 256.
Одной из функций трех аргументов является
0 0 0 0
мажоритарная функция. Таблица истинности этой
0 0 1 0
функции имеет следующий вид (табл. 3).
0 1 0 0
Функция равна 1, если во входном наборе два
0 1 1 1 или три аргумента принимают значение 1, и рав-
на 0 в остальных случаях. Эта функция обладает
1 0 0 0
корректирующей способностью, поэтому на заре
1 0 1 1
развития вычислительной техники были работы,
1 1 0 1
в которых рекомендовалось все комбинационные
1 1 1 1 схемы строить на мажоритарных элементах.
1.3. Булевы функции n аргументов.
СДНФ и СКНФ
Булева функция n аргументов задается на 2n наборах. Число таких
n
функций равно 22 .
Если булева функция задана таблицей истинности, то она может
быть представлена в аналитической форме с использованием опера-
ций конъюнкции, дизъюнкции и инверсии с помощью следующих пра-
вил:
6
– каждой единице в таблице истинности ставится в соответствие
конъюнкция ранга n, где n – число аргументов функции; рангом конъ-
юнкции называют число аргументов, входящих в конъюнкцию, причем
в этой конъюнкции аргумент входит без инверсии, если в соответству-
ющем наборе он принимает значение 1, и с инверсией, если принимает
значение 0;
– все полученные конъюнкции объединяются знаками дизъюнкции.
Например, для мажоритарной функции аналитическое выражение
будет иметь вид
F = x1 x2 x3 ? x1 x2 x3 ? x1x2 x3 ? x1 x2 x3. (1)
Аналитическое выражение функции вида (1) называют совершенной
дизъюнктивной нормальной формой (СДНФ), при этом под совершен-
ной формой понимают аналитическое выражение функции, когда во все
конъюнкции входят все аргументы, т. е. все конъюнкции имеют ранг n;
под нормальной формой понимают выражение, в котором инверсии при-
меняются только к отдельным аргументам.
Если в таблице истинности число нулей существенно меньше числа
единиц, используют аналитическую запись в виде совершенной конъ-
юнктивной нормальной формы (СКНФ). Она строится по следующим
правилам:
– каждому нулю в таблице истинности ставится в соответствие дизъ-
юнкция ранга n, где n – число аргументов функции; рангом дизъюнкции
называют число аргументов, входящих в дизъюнкцию, причем в этой
дизъюнкции аргумент входит без инверсии,
Таблица 4
если в соответствующем наборе он прини-
мает значение 0, и с инверсией, если прини-
x1 x2 x3 F F
мает значение 1;
– все полученные дизъюнкции объединя- 0 0 0 1 0
ются знаками конъюнкции.
0 0 1 0 1
Возьмем, например, функцию F, представ-
0 1 0 1 0
ленную следующей таблицей истинности
(табл. 4). 0 1 1 1 0
СДНФ этой функции представляет собой 1 0 0 0 1
шесть конъюнкций ранга 3, объединенные
1 0 1 1 0
знаками дизъюнкции, т. е. достаточно гро-
1 1 0 1 0
моздкое выражение. В то же время СКНФ
1 1 1 1 0
этой функции будет выглядеть так:
7
F = (x1 ? x2 ? x3 ) ( x1 ? x2 ? x3). (2)
В выражении (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 = x1 x2 x3 ? x1 x2 x3 ? x1 x2 x3 ? x1 x2 x3 ? x1 x2 x3 ? x1 x2 x3. (3)
Повторение конъюнкции x1x2x3 не меняет значение функции, так как
Y ? Y = Y, где Y – любое булево выражение. Тогда, склеивая 1-й и 4-й

стр. 1
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>