1. Математический аппарат цифровых систем

1.1 Основы булевой алгебры

1.1.1 Основные положения и законы булевой алгебры

Основным математическим аппаратом, используемым при анализе и синтезе дискретных элементов и устройств, является булева алгебра (алгебра логики, алгебра Буля). В булевой алгебре широко используется понятие “высказывание”. Высказыванием будем называть простое повествовательное положение, о котором можно сказать, что оно ложно или истинно, но не то и другое одновременно. Любое высказывание можно обозначить символом X и считать, что X=1, если высказывание истинно, а X=0, если высказывание ложно. Логическая (булева) переменная – такая переменная X, которая может принимать только два значения: X={0,1}. Из двух простых высказываний X1 и X2 можно образовать более сложные высказывания, используя операции “И”, “ИЛИ”, “НЕ”. Сложные высказывания также принимают значения “истинно” или “ложно”, т.е. 1 или 0. Смысл логических операций над простыми высказываниями X1 и X2 и значениями сложных высказываний можно представить в виде таблиц истинности: “ИЛИ”, “И”, “НЕ” соответственно

Таким образом, простые высказывания являются переменными, а более сложные высказывания – функциями. Причем как переменные, так и функции могут принимать только значения 0 или 1. Булева алгебра может быть определена как алгебра, содержащая 3 операции “И” (конъюнкция), “ИЛИ” (дизъюнкция), “НЕ” (отрицание) над множеством элементов, каждый из которых принимает два значения 0 или 1. Результаты выполнения операций над множеством элементов также принимают два значения 0 или 1.

     Таблица 1.1

Рекомендуемые материалы

Определение логических операций

Таблица 1.2

Основные аксиомы и теоремы булевой алгебры

Примеры алгебраического метода доказательства теорем:

15. а+вс = а1 + вс = а(1 + в + с) + вс = а1 + ав + ас + вс = аа + ав + ас +вс =   = а(а + в) + с(а + в) = (а + в)(а+с)

20.

Табличный метод доказательства теоремы де-Моргана

1.1.2 Формы представления функций булевой алгебры

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

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

Пусть имеется функция , которая представляет собой набор переменных, связанных через одну из логических операций (ИЛИ, И). Функция называется термом, который имеет две разновидности: дизъюнктивный терм и конъюнктивный терм. Дизъюнктивный терм – набор переменных в прямой или инверсной форме, связанных между собой через операцию “ИЛИ”.

Аналитическое обозначение дизъюнктивного терма выглядит следующим образом:

Конъюнктивный терм – набор переменных в прямой или инверсной форме, связанных между собой через операцию “И”. Конъюнктивный терм обозначается следующим образом:

Ранг терма r определяется количеством переменных, входящих в данный терм. Например: , r=5, а для , r=3.

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

Теорема 1. Любая таблично заданная функция булевой алгебры может быть представлена в виде дизъюнкции конъюнктивных термов

где i – номер наборов, при которых функция равна 1.

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

,

где k – количество наборов переменных, для которых Ф=0.

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

Таким образом, функции булевой алгебры могут существовать в дизъюнктивной нормальной форме (ДНФ) и в совершенной дизъюнктивной нормальной форме (СДНФ), а также в конъюнктивной нормальной форме (КНФ) и конъюнктивной совершенной нормальной форме (СКНФ).

Булевы функции от двух переменных. Полнота и базис булевых функций.

Общее число булевых функций от n переменных определяется соотношением .

Построим все возможные булевы функции от двух переменных. Общее количество функций будет равно 16, их значения представлены в виде таблицы.

                                                                                                       Таблица 1.3

Функций двух переменных.

Представленные 16 функций называются элементарными. Функции  и  являются константами соответственно 0 и 1.

- есть конъюнкция (логическое умножение)

 альтернатива (сложение по модулю 2)  

дизъюнкция

    функция Вебба (ИЛИ-НЕ)

   эквивалентность (равнозначность)

  функция Шеффера (И-НЕ)  

Из булевых функций можно строить новые булевы функции путем подстановки вместо аргументов других функций.

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

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

С понятием полнота имеет тесную связь понятие базиса. Система является базисом, если теряется полнота при удалении хотя бы одной функции. В качестве базиса можно указать функции  и . Например, любая булева функция может быть выражена в базисе И-НЕ  ():

1.2  Логические функции

Логическая переменная F называется логической функцией переменных а,в,с и т.д., если каждому набору значений переменных а,в,с и т.д. поставлено в соответствие одно из значений переменной f

F = f (а,в,с...).

Функции считаются различными, если значение F отличается хотя бы для одного из наборов.

Если имеется n переменных, тогда число наборов, которые можно построить равно

К_n =

 

       

Число функций будет равно N_n=

                   n=1          N₁=4

                   n=2          N₂=16

                   n=3          N₃=256

Формы представления логических функции

     1. Словесно.

     2. Таблица истинности – таблица, содержащая все возможные комбинации всех входных переменных вместе с соответствующими значениями выходных переменных, т.е. значениями функциями.

     3. Алгебраическая  форма записи.

     4. Графический способ записи с помощью карт Карно.

Переход от табличной формы к алгебраической форме записи функции

Чтобы перейти к алгебраической форме в таблице истинности каждому набору в соответствие ставится минтерм и суммируется.

Минтерм – это конъюнкция (логическое произведение), в которое входят все аргументы в прямой или инверсной форме.

Каждый минтерм соответствует одному из значений в таблице истинности. Если переменная в наборе 0, то в минтерм она включается в инверсной форме, если 1, то в прямой.

Пример:

                                           

Такая форма  представления называется совершенной дизъюнктивной нормальной формой (СДНФ).

1.3 Минимизация логических функций

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

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

        F =     =     =

                                            Σ_кв=6           Σ_кв=2        Σ_кв=2

Минимизация может быть выполнена различными методами. Алгебраический метод. Алгебраический метод основан на применении законов булевой алгебры к заданной булевой функции. Причем функция может быть задана в произвольной форме.

1.3.1. Минимизация логических функций с помощью карт Карно

Для минимизации функций относительно небольшого числа переменных (k<6) наиболее простым и наглядным является графический метод, использующий карты Карно. При использовании этого метода исходная функция представляется на карте Карно. Минтермы, соответствующие двум соседним (в столбце или ряду) клеткам карты Карно, отличаются значениями только одной переменной. Поэтому дизъюнкция этих минтермов дает одну импликанту, в которой исключена переменная, имеющая взаимоинверсные значения.

Пример карт Карно для числа переменных 2 и 3:

                            n=2                                                     n=3

                                                 

Чтобы выделить на карте Карно клетки, представляющие одну импликанту, их графически объединяют (обводят тонкой линией). Импликанта представляется на картах Карно двумя, четырьмя, восьмью объеди­ненными клетками. Такое объединение клеток на картах Карно эквивалентно выполнению операции склеивания минтермов и поз­воляет получать более простое выражение логической функции. Поэтому для минимизации логических выражений вместо их алге­браических преобразований можно выполнять соответствующее объединение клеток на картах Карно. Объединенные клетки будут соответствовать импликантам, дизъюнкция которых даст сокра­щенную ДНФ или МДНФ заданной функции. Чем больше клеток входит в объединение, тем меньше переменных входит в соответ­ствующую импликанту, т. е. проще получаемая ДНФ.

Таким образом, минимизацию логических выражений можно выполнять графическим объединением на карте Карно клеток, занятых 1, и последующим получением алгебраического выражения функции в виде сокращенной ДНФ, каждая импликанта которой соответствует объединению нескольких клеток (минтермов) или одной необъединенной клетке. Процесс получения алгебраического выражения функции, представленной на карте Карно, т. е. пере­ход от графического представления к алгебраическому, называется считыванием. При этом каждое объединение клеток считывается в виде импликанты, в которую входят переменные или их инверсии, общие для всех минтермов, соответствующих этим клеткам. Необъединенные клетки считываются в виде соответствующих минтер­мов.

Полученные на основании законов булевой алгебры правила минимизации путем объединения на картах Карно клеток, заня­тых 1, формулируются для функций 4 переменных следующим образом.

1. Объединяются две соседние клетки в столбце или ряду, четыре соседние клетки, составляю­щие квадраты.

2. Объединяются клетки или па­ры клеток, крайние в столбцах или рядах.

3. Объединяются полные столбцы или ряды, пары рядом расположенных столбцов или рядов, а также крайние столбцы или ряды на карте.

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

4. Объединяются клетки, пары соседних клеток, квадраты, столбцы, ряды, пары соседних столбцов и рядов, расположенные симметрично относительно вертикальной или горизонтальной оси карты Карно.

Количество импликант в получаемой сокращенной ДНФ равно сумме числа объединений и необъединенных клеток. Для получения МДНФ следует включать в каждое объединение максимально возможное число клеток и выбирать такой вариант объединения клеток, чтобы общее число объединений и оставшихся необъедененых клеток было минимально. При этом одна и та же клетка может входить в несколько объединений

Используя различные варианты объединений для некоторых функций, можно получать несколько различных МДНФ, одно из которых выбирается для реализации в цифровом устройстве.

Если для заданной функции имеются безразличные наборы входных переменных, которые обозначаются знаком Х в соответ­ствующих клетках карты Карно, то можно доопределить функцию, чтобы получить более простую МДНФ. В этом случае при минимизации функции с помощью карт Карно в объединения включаются те клетки, отмеченные знаком X, кото­рые дают расширение объединений и уменьшение их количества.

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

        

           

           

Примеры минимизации с помощью карт Карно:

Рекомендуем посмотреть лекцию "24. Элизабет Гаскелл".