Построение СНДФ, СНКФ и СНПФ. Минимизация

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

Пример:

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

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

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

– конституэнты объединяются операциями дизъюнкции.

В данном примере

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

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

.

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

.

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

.

Под представлением булевых функций в виде совершенной нормальной полиномиальной формы (СНПФ) подразумевается представление функции в базисе (1, Ø, +, ):

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

Пример. .

Рассмотрим набор аргументов :

.

Далее

;

;

;

;

;

;

.

Это и есть СНПФ для заданной функции.

Можно также воспользоваться соотношениями

.

Они позволяют перейти от базиса (, , ) к базису (1, Ø, +, ).

Дата добавления: 2015-06-04