Единое окно доступа к образовательным ресурсам

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

Голосов: 2

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
       ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ
                    Ñàíêò-Ïåòåðáóðãñêèé
ãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ




                        И. Л. Ерош




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

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




                     Ñàíêò-Ïåòåðáóðã
                          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


   F1 = const 0, F2 = x, функция повторения x,                                 Таблица 1
F4 = const 1, F3 – инверсия аргуменмента x,
                                                      x       F1       F2       F3   F4
обозначаемая  x или x и называемая иног-
да “не x”, “отрицание x”.                             0       0        0        1    1
   При n = 2 получаем таблицу истинности              1       0        1        0    1
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, и рав-
    1   0     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, и с инверсией, если прини-
мает значение 1;                                  x1       x2 x3  F    F
   – все полученные дизъюнкции объединя-            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-й
члены, 2-й и 5-й, 3-й и 6-й, получаем эквивалентное выражение
                     F = x2 x3 ∨ x1 x3 ∨ x1 x2.                (4)
Выражение (4) будет дизъюнктивной, нормальной формой функции, так
как в каждую из конъюнкций входят не все аргументы функции.
   Преобразование булевых выражений с помощью приведенных пра-
вил поглощения, склеивания и обобщенного склеивания применяется
достаточно редко, так как имеется более эффективный способ миними-
зации булевых функций, число аргументов которых не превышает 11.
Кроме того, так же просто обосновывается преобразование, называе-
мое правилом де Моргана:
                          а) x1 x2 = x1 ∨ x2 ;
                        б) x1 ∨ x2 = x1 x2 .                       (5)
   Покажем, как применить правило де Моргана для вывода формулы
СКНФ. В табл. 4 имеется значение функции, инверсной к F, т. е. F . Эта
функция имеет только две единицы, поэтому СДНФ ее будет представлять
собой две конъюнкции, каждая ранга 3, объединенные знаком дизъюнкции:

8


                    F = x1 x2 x3 ∨ x1 x2 x3 .                 (6)
   Проинвертируем левую и правую части выражения (6) и применим к
правой части правило де Моргана, тогда получим
                F = (x1∨ x2 ∨ x3 ) ( x1 ∨ x2 ∨ x3) .
  В результате получена формула СКНФ функции F.
        1.5. Минимизация булевых функций с помощью
                 диаграмм Вейча (карт Карно)
   Диаграммы Вейча представляет собой ту же таблицу истинности
булевой функции, только в более компактной форме. Так, для функции
трех аргументов, которая задается на восьми наборах, таблица истин-
ности будет содержать восемь клеток, причем каждая клетка в диаг-
рамме Вейча соответствует некоторому набору в таблице истинности.
   Области в диаграмме Вейча обозначим следующим образом: под-
черкнутые столбцы или строки будут соответствовать истинному зна-
чению аргумента, а не подчеркнутые – ложному. Тогда диаграмма Вей-
ча мажоритарной функции примет вид
                                   x2
                                            x1
                     1        1         1
              x3              1

  Из полученной диаграммы Вейча легко выписывается минимальное
выражение для мажоритарной функции
                    F = x2 x3 ∨ x1 x3 ∨ x1 x2.
  Возьмем некоторую функцию F четырех аргументов, диаграмма
Вейча которой имеет вид
                                      B
                                               A

                     1        1                  1


          D

              C      1                           1

                                                                  9


   Эта функция принимает значение 1 на пяти наборах, отмеченных на
диаграмме единицами. На остальных наборах функция принимает зна-
чение 0. СДНФ этой функции содержала бы пять конъюнкций каждая
ранга 4, объединенные знаками дизъюнкций. Однако из диаграммы Вейча
легко выписывается минимальное выражение функции в дизъюнктив-
ной нормальной форме
                       F = AC ∨ B C D .
   Области в диаграмме Вейча обозначаются так, чтобы две соседние
клетки соответствовали бы “склеивающимся” конъюнкциям (т. е. конъ-
юнкциям, отличающимся значением только одного аргумента). Так,
например:
                     A B C D ∨ A B C D = AC D .
     Это обеспечивает наглядность минимизации.
     В общем случае области в диаграммах Вейча для функций большо-
                      го числа аргументов обозначаются кодом Грэя.
          Таблица 5
                      Особенностью этого кода является то, что две
     0000    0000     соседние комбинации отличаются значением толь-
     0001    0001     ко одного аргумента. Обычный двоичный код это-
                      му условию не удовлетворяет.
     0010    0011
                         Код Грэя используется в цифровых кодовых дат-
     0011    0010     чиках, что позволяет сделать ошибку равномер-
     0100    0110     ной при смещениях токосъемников, при этом ошиб-
     0101    0111
                      ка равна 2-m где m – число двоичных разрядов ко-
                      дового датчика. Это свойство кода Грэя исполь-
     0110    0101     зуется для обозначения областей в диаграммах
     0111    0100     Вейча.
     1000    1100        В табл. 5 приведен код Грэя для четырех аргу-
                      ментов (разрядов). Если требуется построить код
     1001    1101
                      Грэя на меньшее число разрядов, то его легко по-
     1010    1111     лучить из имеющейся таблицы путем “выреза-
     1011    1110     ния” соответствующей части. Так, в приведенной
     1100    1010
                      таблице показано, как получить двухразрядный код
                      Грэя. Если требуется построить код Грэя на пять
     1101    1011     разрядов, то код в таблице следует зеркально от-
     1110    1001     разить вниз и добавить еще один разряд, причем в
     1111    1000     первой половине в этом разряде будут стоять нули,

10



    
Яндекс цитирования Яндекс.Метрика