Нормальная форма

В предыдущем разделе была составлена таблица истинности для выходов схемы семисегментного дешифратора. Данная таблица сама по себе не позволяет построить необходимую цифровую схему. Для того чтобы построить схему из логических примитивов необходимо записать соответствующую логическую функцию в виде последовательности операций «И», «ИЛИ» и «НЕ». Как это сделать?

Здесь приходят на помощь теоремы математической логики, в которых утверждается, что любую логическую функцию можно записать с использованием одних только операций «И», «ИЛИ» и «НЕ». Такая форма записи называется дизъюнктивной или конъюнктивной нормальной формой. Стоит пояснить, что дизъюнкцией в математической логике называется операция логического сложения — «ИЛИ». В свою очередь, конъюнкция — это операция логического умножения — «И».

Конъюнктивная нормальная форма это такая форма, в которой логические переменные объединяются в группы операцией логического сложения — «ИЛИ». А сами группы переменных соединяются с помощью логического умножения — операции «И», конъюнкции. Дизъюнктивная нормальная форма отличается тем, что операция «И» применяется непосредственно к переменным, а «ИЛИ» к их группам.

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

(I3 ИЛИ I2 ИЛИ I3) И (I3 ИЛИ (НЕ I2)) И (I3 ИЛИ I2 ИЛИ I1) И (I3 ИЛИ (НЕ I2)) И (I3 ИЛИ I3) — это конъюнктивная нормальная форма;

(I3 И I2 И I3) ИЛИ (I3 И (НЕ I2)) ИЛИ (I3 И I2 И I1) ИЛИ (I3 И (НЕ I2)) ИЛИ (I2 И I2) ИЛИ I1 — это дизъюнктивная нормальная форма.

Скобки здесь имеют тот же смысл что и в математике в целом — операция заключенная в скобки выполняется в первую очередь. Без скобок операция «И» имела бы приоритет на операцией «ИЛИ», что нормально для дизъюнктивной формы, но недопустимо для конъюнктивной нормальной формы.

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

Более строгой записью является совершенная конъюнктивная (дизъюнктивная) нормальная форма. Совершенные формы отличаются особыми требованиями к их записи:

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

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

(I0 ИЛИ I1 ИЛИ I2 ИЛИ I3) И (I0 ИЛИ (НЕ I1) ИЛИ I2 ИЛИ I3) И ((НЕ I0) ИЛИ I1 ИЛИ I2 ИЛИ I3) — совершенная конъюнктивная нормальная форма;

(I0 И I1 И I2 И I3) ИЛИ (I0 И (НЕ I1) И I2 И I3) ИЛИ ((НЕ I0) И I1 И I2 И I3) — совершенная дизъюнктивная нормальная форма.

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

Рассмотрим пример: получение функции для выхода DP управляющего десятичной точкой на индикаторе. Для этого потребуется таблица истинности выхода DP, она приводится ниже.

I3I2I1I0DP
00000
00010
00100
00110
01000
01010
01101
01110
10000
10011
10100
10110
11000
11010
11100
11110

Для получения логической функции в совершенной дизъюнктивной нормальной форме необходимо обратить внимание на те строки таблицы, в которых DP имеет значение единицы (ИСТИНА). Так DP равно истине в седьмой строке при следующих значениях на входах: I3=0, I2=1, I1=1, I0=0. Что позволяет записать конъюнкцию данных переменных в следующем виде: (НЕ I3) И I2 И I1 И (НЕ I0). Здесь, к тем переменным что имеют значение ноля (ЛОЖЬ) была применена функция отрицания (или инверсия), а переменные со значением ИСТИНА были взяты без изменений. Можно заметить, что полученное выражение имеет значение ИСТИНА для набора входных значений 0110 как и сам выход DP. В этом и состояла цель применения инверсии ко входам I3 и I0.

Аналогично, DP – ИСТИНА в десятой строке для входных значений: I3=1, I2=0, I1=0, I0=1. Конъюнкция для данного набора будет иметь вид: I3 И (НЕ I2) И (НЕ I1) И I0.

Теперь, с помощью дизъюнкции можно получить логическую функцию выхода DP в совершенной дизъюнктивной нормальной форме:
DP = ((НЕ I3) И I2 И I1 И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И I0).
Данная функция будет возвращать ИСТИНУ (единицу) только для входных значений 0110 и 1001. Во все остальных случая на выходе DP будет ЛОЖЬ, и десятичная точка на индикаторе гореть не будет.

Аналогичный подход используется для получения совершенной конъюнктивной нормальной формы для DP. Но в таблице выбираются строки, в которых DP принимает значение ноля (ЛОЖЬ). DP равно ЛОЖЬ в большинстве строк таблицы истинности. Во второй строке DP ЛОЖЬ при следующих значениях на входах: I3=0, I2=0, I1=0, I0=1. Дизъюнкция для данного набора имеет вид: I3 ИЛИ I2 ИЛИ I1 ИЛИ (НЕ I0). Здесь с отрицанием берутся уже те переменные что имеют значение ИСТИНА, то есть используется подход противоположный дизъюнктивной форме. Но цель та же: получить выражение, значение которого (ЛОЖЬ) для набора 0001 совпадает со значением выхода DP в данной строке таблицы истинности.

Таким же образом получаем выражения для оставшихся строк:

Первая строка 0000: I3 ИЛИ I2 ИЛИ I1 ИЛИ I0

Третья строка 0010: I3 ИЛИ I2 ИЛИ (НЕ I1) ИЛИ I0

Четвертая строка 0011: I3 ИЛИ I2 ИЛИ (НЕ I1) ИЛИ (НЕ I0)

Пятая строка 0100: I3 ИЛИ (НЕ I2) ИЛИ I1 ИЛИ I0

Шестая строка 0101: I3 ИЛИ (НЕ I2) ИЛИ I1 ИЛИ (НЕ I0)

Седьмая строка пропускается, так как в ней DP – ИСТИНА.

И так далее. Вплоть до шестнадцатой строки 1111: (НЕ I3) ИЛИ (НЕ I2) ИЛИ (НЕ I1) ИЛИ (НЕ I0)

Теперь, используя конъюнкцию можно записать булеву функцию выхода DP в совершенной конъюнктивной нормальной форме:

DP = (I3 ИЛИ I2 ИЛИ I1 ИЛИ I0) И (I3 ИЛИ I2 ИЛИ I1 ИЛИ (НЕ I0)) И (I3 ИЛИ I2 ИЛИ (НЕ I1) ИЛИ I0) И (I3 ИЛИ I2 ИЛИ (НЕ I1) ИЛИ (НЕ I0)) И (I3 ИЛИ (НЕ I2) ИЛИ I1 ИЛИ I0) И (I3 ИЛИ (НЕ I2) ИЛИ I1 ИЛИ (НЕ I0)) И (I3 ИЛИ (НЕ I2) ИЛИ (НЕ I1) ИЛИ (НЕ I0)) И ((НЕ I3) ИЛИ I2 ИЛИ I1 ИЛИ I0) И ((НЕ I3) ИЛИ I2 ИЛИ (НЕ I1) ИЛИ I0) И ((НЕ I3) ИЛИ I2 ИЛИ (НЕ I1) ИЛИ (НЕ I0)) И ((НЕ I3) ИЛИ (НЕ I2) ИЛИ I1 ИЛИ I0) И ((НЕ I3) ИЛИ (НЕ I2) ИЛИ I1 ИЛИ (НЕ I0)) И ((НЕ I3) ИЛИ (НЕ I2) ИЛИ (НЕ I1) ИЛИ I0) И ((НЕ I3) ИЛИ (НЕ I2) ИЛИ (НЕ I1) ИЛИ (НЕ I0))

Невооруженным глазом видно, что данное выражение получилось гораздо более громоздким по сравнению с совершенной конъюнктивной нормальной формой. При этом обе формы тождественны, то есть дают один и тот же результат: DP будет зажигаться только для входных значений 0110 и 1001.

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

Может возникнуть вопрос: требуется ли каждый раз составлять две формы записи логической функции для определения наиболее выгодной? Нет. Это совсем не обязательно. Так как сложность функции зависит от числа строк таблицы истинности, в которых эта функция принимает значение ИСТИНА или ЛОЖЬ, то решить какая форма записи выгоднее можно просто посмотрев на таблицу истинности. Например, выход DP принимает значение ИСТИНА всего в двух строках из шестнадцати, а значит совершенная дизъюнктивная форма записи будет в семь раз короче совершенной конъюнктивной формы: две строки против четырнадцати. В свою очередь выход сегмента «C» — Sc принимает значение ИСТИНА в девяти строках, а значение ЛОЖЬ в семи строках, поэтому здесь более выгодной оказывается совершенная конъюнктивная форма записи.

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

I3I2I1I0SaSbScSdSeSfSgDP
000011111100
000101100000
001011011010
001111110010
010001100110
010110110110
011010111111
011111100000
100011111110
100111110111
101000000000
101100000000
110000000000
110100000000
111000000000
111100000000

Sa = ((НЕ I3) И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ ((НЕ I3) И (НЕ I2) И I1 И (НЕ I0)) ИЛИ ((НЕ I3) И (НЕ I2) И I1 И I0) ИЛИ ((НЕ I3) И I2 И (НЕ I1) И I0) ИЛИ ((НЕ I3) И I2 И I1 И (НЕ I0)) ИЛИ ((НЕ I3) И I2 И I1 И I0) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И I0)

Sb = ((НЕ I3) И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ ((НЕ I3) И (НЕ I2) И (НЕ I1) И I0) ИЛИ ((НЕ I3) И (НЕ I2) И I1 И (НЕ I0)) ИЛИ ((НЕ I3) И (НЕ I2) И I1 И I0) ИЛИ ((НЕ I3) И I2 И (НЕ I1) И (НЕ I0)) ИЛИ ((НЕ I3) И I2 И I1 И I0) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И I0)

Sc = (I3 ИЛИ I2 ИЛИ (НЕ I1) ИЛИ I0) И ((НЕ I3) ИЛИ I2 ИЛИ (НЕ I1) ИЛИ I0) И ((НЕ I3) ИЛИ I2 ИЛИ (НЕ I1) ИЛИ (НЕ I0)) И ((НЕ I3) ИЛИ (НЕ I2) ИЛИ I1 ИЛИ I0) И ((НЕ I3) ИЛИ (НЕ I2) ИЛИ I1 ИЛИ (НЕ I0)) И ((НЕ I3) ИЛИ (НЕ I2) ИЛИ (НЕ I1) ИЛИ I0) И ((НЕ I3) ИЛИ (НЕ I2) ИЛИ (НЕ I1) ИЛИ (НЕ I0))

Sd = ((НЕ I3) И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ ((НЕ I3) И (НЕ I2) И I1 И (НЕ I0)) ИЛИ ((НЕ I3) И (НЕ I2) И I1 И I0) ИЛИ ((НЕ I3) И I2 И (НЕ I1) И I0) ИЛИ ((НЕ I3) И I2 И I1 И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И I0)

Se = ((НЕ I3) И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ ((НЕ I3) И (НЕ I2) И I1 И (НЕ I0)) ИЛИ ((НЕ I3) И I2 И I1 И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И (НЕ I0))

Sf = ((НЕ I3) И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ ((НЕ I3) И I2 И (НЕ I1) И (НЕ I0)) ИЛИ ((НЕ I3) И I2 И (НЕ I1) И I0) ИЛИ ((НЕ I3) И I2 И I1 И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И I0)

Sg = ((НЕ I3) И (НЕ I2) И I1 И (НЕ I0)) ИЛИ ((НЕ I3) И (НЕ I2) И I1 И I0) ИЛИ ((НЕ I3) И I2 И (НЕ I1) И (НЕ I0)) ИЛИ ((НЕ I3) И I2 И (НЕ I1) И I0) ИЛИ ((НЕ I3) И I2 И I1 И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И I0)

DP = ((НЕ I3) И I2 И I1 И (НЕ I0)) ИЛИ (I3 И (НЕ I2) И (НЕ I1) И I0).

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

∧ — конъюнкция

v — дизъюнкция

¬ или ПЛИС Altera КС Рис 7 logical not x (читается как «не икс») — отрицание.

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

Получив описание функций выходов дешифратора в виде набора логических операций И, ИЛИ и НЕ можно переходить к реализации схемы в «железе».


Изменено:

Добавить комментарий

Ваш адрес email не будет опубликован.