На  функции И и ИЛИ распространяются обычные алгебраические законы - переместительный, сочетательный и распределительный, которые легко доказываются методом перебора:

• x₁ op x₀ = x₀ op x₁ - переместительный,
• x₂ op x₁ op x₀ = (x₂ op x₁) op x₀ – сочетательный,
• x₂*(x₁+x₀) = (x₂*x₁) + (x₂*x₀) и x₂ + (x₁*x₀) = (x₂+x₁) * (x₂+x₀) - распределительный,

  где операция “op” может быть, либо И, либо ИЛИ. Наряду с тремя основными логическими функциями существуют и другие функции.

 

 3 ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ

 

  Для n - логических переменных (аргументов) существует 2ⁿ  (2**n) их комбинаций или двоичных наборов. На каждом таком наборе может быть определено значение функции 0 или 1. Если значения функции отличаются хотя бы на одном наборе, то функции - разные. Общее число переключательных функций (ПФ) от n аргументов равно N=2**(2**n). Для n=2, N=16. При n=3, N=256 и далее очень быстро растет. Практическое значение имеют 16 функций от 2-х переменных, так как любое сложное выражение можно рассматривать как композицию из простейших. В таблице 2 приведены переключательные функции для n = 2.

  Таблица 2

 

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

  У всех выше приведенных функций (читай  схем логических элементов), за исключением  инвертора, коэффициент объединения  равен двум. Промышленностью выпускаются  схемы с Коб = 2, 3, 4, 8. Для получения схем с другим числом входов основные элементы можно объединять. Например, если требуется пятивходовая схема И, то ее можно получить, используя сочетательный закон следующим способом: x₀ * x₁ * x₂ * x₃ * x₄ = (x₀*x₁) * (x₂*x₃*x₄) =  
(x₀*x₁) * x₂ * x₃ * x₄, то есть требуются две двухвходовые и одна трехвходовая схемы И, для первого варианта, либо одна двухвходовая и одна четырехвходовая - для второго (рисунок 1). 

Рисунок 1 

  Можно использовать также и восьмивходовую схему И, подав на незадействованные входы логические "1".

4 СПОСОБЫ ПРЕДСТАВЛЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ

 

  Целью проектирования цифрового устройства является получение его логической функции (ЛФ) и соответствующей ей схемной реализации. Логические функции  могут иметь различные формы представления:

• словесное,
• графическое,
• табличное,
• алгебраическое,
• на алгоритмическом языке,
• схемное.

  В качестве примера, рассмотрим функцию Y от двух переменных x₁ и x₀, заданную словесным описанием: Y = 1, если переменные не равны и Y = 0, если x₁  =  x₀.

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

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

• "дизъюнктивная" как сумма произведений;
• "совершенная", поскольку в каждое произведение входят все переменные;
• "нормальная", так как в любом произведении каждая переменная встречается лишь однажды.

4.1 Техническая интерпретация логических функций

    По логическим выражениям проектируются  схемы ЭВМ. При этом следует придерживаться следующей последовательности действий.

1. Словесное описание работы схемы.
2. Формализация словесного описания.
3. Запись функции в дизъюнктивной совершенной нормальной форме по таблицам истинности.
4. Минимизация логических зависимостей с целью их упрощения.
5. Представление полученных выражений в выбранном логически полном базисе элементарных функций.
6. Синтез схемы устройств.

5 ЛОГИЧЕСКИЙ БАЗИС

 

  Набор простейших логических функций, позволяющих  реализовать любую  другую функцию называется логическим базисом (ЛБ). Функции И, ИЛИ, НЕ не являются минимальным логическим базисом, так как сами могут быть представлены через другие функции, например через (ИЛИ -НЕ) или (И - НЕ) (смотри рисунок 2).  

Рисунок 2 

6 МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ

 

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

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

  Умение  создавать и минимизировать логические функции имеет огромное значение при проектировании устройств цифровой электроники.

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

   Основные критерии минимизации:

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

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

6.1 Аналитический способ

   Путем тождественных преобразований на основе законов алгебры логики. Речь идет о том, чтобы перейти от СДНФ к  ДНФ с минимумом слагаемых, при  этом количество множителей в каждом слагаемом должно быть также минимальным (избавиться от "совершенства"). Иными  словами - максимально уменьшить количество переменных и операций в СДНФ.

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

   Пример: логическая функция представлена в  виде СДНФ:

Y=A B^ C^+ A B^ C+ A B C+ A B C^

   Элементарные  конъюнкции называются соседними (логически смежными), если они отличаются только одной переменной, применение к ним операции «склеивания» понижает их ранг на единицу. Здесь соседние 1 и 2 конъюнкции, а также 3 и 4.

Y =  A B^ C^+ A B^ C+ A B C+ A B C^ = A B^ (C^ + C) + A B (C + C^) = 
A B^ + A B =  A ( B^ + B )  =  A

6.2 Табличный метод Квайна - МакКласки

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

   Любой аналитический (табличный) метод минимизации  состоит из следующих шагов.

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

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

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

   Задача  определении множества простых импликант является переборной и разумная организация вычислений может привести к значительному сокращению вычислений. Основной идеей метода Квайна-МакКласки является разбиение множества минимизируемых кубов на группы с равным количеством единиц в каждой. При выполнении склеивания сравниваются только кубы из соседних групп (различающихся на одну единицу). Это приводит к значительному сокращению числа переборов при выполнении склеиваний.

   Метод Квайна-МакКласки для кубического  представления булевых функций рассмотрим на примере минимизации функции четырех переменных.

6.2.1 Пример минимизации функции четырех переменных методом Куайна - Мак-Класки

    Минимизируем  логическую функцию S(a,b,c,d) методом Куайна - Мак-Класки.

   1. Пусть функция S(a,b,c,d) задана таблицей истинности (символ ' означает операцию отрицания):

2. Сгруппируем минтермы по количеству  в них единиц:

   3. Произведем первое объединение  строк каждых предыдущих и  последующих групп: 

   4. Объединим строки с совпадающими  позициями "крестиков":

   5. Из двух строк с идентичными  значениями минтермов оставляем  только одну:

   6. Обращаем внимание на то, что  третий минтерм избыточен (лишнее  ребро ac'd' на пространственной  диаграмме), т. к. 8-я строка уже  вошла в комбинацию с 10-й строкой (2-й минтерм), а 12-я - в комбинацию с 4-й, 5-й и 13-й строками (1-й минтерм). Поэтому удаляем третью строку таблицы и записываем минимальную СДНФ: