2001-0084-0-01 (Лабы)

ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈÑàíêò-Ïåòåðáóðãñêèéãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿИ. Л. ЕрошДИСКРЕТНАЯ МАТЕМАТИКАБУЛЕВА АЛГЕБРА, КОМБИНАЦИОННЫЕ СХЕМЫ,ПРЕОБРАЗОВАНИЯ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙУчебное пособиеÑàíêò-Ïåòåðáóðã2001УДК 519.6(075)ББК 22.19E78Ерош И. Л.Е78 Дискретная математика. Булева алгебра, комбинационные схемы, преобразования двоичных последовательностей: Учеб.

пособие/СПбГУАП.СПб., 2001. 30 c.Приводятся методы анализа и синтеза булевых выражений, примерыреализации комбинационных схем, построенных по словесному описанию алгоритма функционирования. Рассмотрены булевы преобразования двоичных последовательностей и показана возможность использования этих преобразований при решении некоторых задач криптографии.Пособие ориентировано на студентов технических университетов, аспирантов и преподавателей дисциплины “Дискретная математика“ технических вузов.Рецензенты:кафедра радиосистем Санкт-Петербургского электротехнического университета;канд. техн.

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

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

БУЛЕВЫ ФУНКЦИИ И КОМБИНАЦИОННЫЕ СХЕМЫ1.1. Понятие о булевых функциях.Булевы функции одного и двух аргументовБулевыми функциями (функциями алгебры логики) называют функции, аргументы которых, так же как и сама функция, принимаюттолько два значения – 0 или 1. Алгебра логики является разделомматематической логики, в которой изучаются методы доказательства истинности (1) или ложности (0) сложных логических конструкций, составленных из простых высказываний, на основе истинностиили ложности последних.Алгебра Буля оказалась очень удобным и эффективным математическим аппаратом для анализа и синтеза комбинационных схем.Булевы функции определяют логику работы комбинационных схемследующего вида:x1x2x3xn...КомбинационнаясхемаF(x1, x2, ..., xn)где x1– xn , F ∈ { 0, 1}. Рассмотрим частные случаи.Пусть n = 1, тогда входной сигнал x может принимать только двазначения – 0 и 1, а выходной сигнал F(x) может обеспечивать четыреразличных реакции на выходе. Таблица, в которой каждому набору входных сигналов сопоставляется значение выходного сигнала, называетсятаблицей истинности функции.Для комбинационных схем с одним входом таблицы истинностивсех булевых функций, описывающих логику работы схемы, примутвид (табл.

1).4Таблица 1F1 = const 0, F2 = x, функция повторения x,F4 = const 1, F3 – инверсия аргуменмента x,обозначаемая  x или x и называемая иногда “не x”, “отрицание x”.При n = 2 получаем таблицу истинности16 различных функций двух аргументов(табл. 2).xF1F2F3F40001110101Таблица 2x 1 x 2 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15000000000011111111010000111100001111100011001100110011110101010101010101Среди функций двух аргументов имеются уже известные функции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. Булевы функции трех аргументовТаблица 3x1x2x3F00000010010001111000101111011111Функции трех аргументов задаются на восьми наборах.

Количество функций трех аргументов равно 28 = 256.Одной из функций трех аргументов являетсямажоритарная функция. Таблица истинности этойфункции имеет следующий вид (табл. 3).Функция равна 1, если во входном наборе дваили три аргумента принимают значение 1, и равна 0 в остальных случаях. Эта функция обладаеткорректирующей способностью, поэтому на зареразвития вычислительной техники были работы,в которых рекомендовалось все комбинационныесхемы строить на мажоритарных элементах.1.3.

Булевы функции n аргументов.СДНФ и СКНФБулева функция n аргументов задается на 2n наборах. Число такихnфункций равно 22 .Если булева функция задана таблицей истинности, то она можетбыть представлена в аналитической форме с использованием операций конъюнкции, дизъюнкции и инверсии с помощью следующих правил:6– каждой единице в таблице истинности ставится в соответствиеконъюнкция ранга n, где n – число аргументов функции; рангом конъюнкции называют число аргументов, входящих в конъюнкцию, причемв этой конъюнкции аргумент входит без инверсии, если в соответствующем наборе он принимает значение 1, и с инверсией, если принимаетзначение 0;– все полученные конъюнкции объединяются знаками дизъюнкции.Например, для мажоритарной функции аналитическое выражениебудет иметь вид(1)F = x1 x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1 x2 x3.Аналитическое выражение функции вида (1) называют совершеннойдизъюнктивной нормальной формой (СДНФ), при этом под совершенной формой понимают аналитическое выражение функции, когда во всеконъюнкции входят все аргументы, т.

е. все конъюнкции имеют ранг n;под нормальной формой понимают выражение, в котором инверсии применяются только к отдельным аргументам.Если в таблице истинности число нулей существенно меньше числаединиц, используют аналитическую запись в виде совершенной конъюнктивной нормальной формы (СКНФ). Она строится по следующимправилам:– каждому нулю в таблице истинности ставится в соответствие дизъюнкция ранга n, где n – число аргументов функции; рангом дизъюнкцииназывают число аргументов, входящих в дизъюнкцию, причем в этойдизъюнкции аргумент входит без инверсии,Таблица 4если в соответствующем наборе он принимает значение 0, и с инверсией, если приниx2 x3FFx1мает значение 1;– все полученные дизъюнкции объединя00010ются знаками конъюнкции.00101Возьмем, например, функцию F, представ01010ленную следующей таблицей истинности(табл.