Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

17 Из определения двойственности следует, что * * * 1 1 1 ( ) ( ( , , )) ( , , ) ( , , ) n n n f f x x f x x f x x    , т.е. исходная функция f является двойственной к f* . Пусть функция  (x 1 ,…,x n ) реализуется формулой F . Спрашивается, какой вид имеет формула F* , реализующая функцию  *(x 1 ,…,x n ) . Обозначим через x 1 ,…,x n все различные символы переменных, встречающиеся в множествах ) ,..., ),...,( ,..., ( m 1 mn m1 1n 11 x x x x . Теорема 4.1. Если )) ,..., ( ),..., ,..., ) ( ( ,..., ( m 1 mn m m1 1n 1 11 n 1 f x x f f x x x x   , то )) ,..., ( ),..., ,..., ( ( ) ,..., ( * * * * m 1 mn m m1 1n 1 11 n 1 f x x f f x x x x   . Доказательство. 1 1 1 1 * 1 1 1 11 1 1 1 11 1 1 * * 1 11 1 1 * * * 1 11 1 1 ( , , ) ( , , ) ( ( , , ), , ( , , )) ( ( , , ),..., ( , , )) ( ( ,..., ),..., ( ,..., )) ( ( ,..., ),..., ( ,..., ))). . . . m m m m n n n m m mn n m m mn n m m mn n m m mn x x x x f f x x f x x f f x x f x x f f x x f x x f f x x f x x ч т д          Из теоремы вытекает следующий принцип. Принцип двойственности. Если формула F=F(f 1 ,…,f m ) реализует функцию  (x 1 ,…,x n ) , то формула F*=F(f 1 *,…,f m *) полученная из F заменой функций f 1 ,…,f m на f 1 *,…,f m * , реализует функцию  *(x 1 ,…,x n ) . Формулу F* будем называть формулой, двойственной к F . Для формул над ( 0,1,  ,&, ) принцип двойственности может быть сформулирован так: для получения формулы F* ,