Нормальные формы двоичных функций

Всюду в этом параграфе рассматриваются формулы над классом . Обозначим через функцию

Очевидно, что тогда и только тогда, когда , .

Определение 2.1. Элементарной конъюнкцией называется формула вида , где все переменные различны. Рангом элементарной конъюнкции называется число входящих в неё переменных.

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

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

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

Теорема 2.3 (о разложении функции). Пусть k такое, что . Тогда двоичную функцию можно представить в виде:

. (2.1)

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

=

= .

Теорема доказана.

Дата добавления: 2014-12-29