2.4. Нормальные формы функций алгебры логики

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

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

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

Дизъюнктивная совершенная нормальная форма (ДСНФ) БФ представляет собой дизъюнкцию специально вводимых вспомогательных функций – конституент единицы, которые равны 1 на тех же наборах, что и заданная функция. ДСНФ представляет собой алгебраическое выражение, которое принимает значение, равное 1 на тех наборах переменных, на которых значение заданной функции равно 1. Конституентой единицы называют функцию, которая принимает значение 1 на одном из всех возможных наборов переменных. Количество конституент единицы заданного числа переменных n, как следует из определения, совпадает с числом различных наборов k = 2ⁿ. Для составления алгебраического выражения, принимающего значение, равное 1, на всех наборах, на которых функция равна 1, следует взять дизъюнкцию конституент, соответствующих этим наборам.

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

Для функции f, заданной таблицей 2.1, ДСНФ имеет вид

.

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

Например, для функции f(х₁, ..., х₄) = {1, 3, 7} имеем

Расставляя отрицания над переменными, которые равны 0, и соединяя конституенты знаками дизъюнкции, получим ДСНФ

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

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

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

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

Конъюнкцию антиконституент, равных 0 на тех же наборах, что и заданная функция, называют конъюнктивной совершенной нормальной формой функции алгебры логики. КСНФ легко строится по таблице истинности. Следует записать столько конъюнктивных членов, представляющих собой дизъюнкции всех переменных, при скольких наборах значений переменных функция равна 0. Если в наборе значение переменной равно 1, в дизъюнкцию входит инверсия этой переменной. Например, для функции φ, заданной таблицей истинности (см. табл. 2.1), КСНФ имеет вид

.

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

.

Канонические формы функции, ДСНФ и КСНФ являются исходными при минимизации БФ.