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

41 Класс логических функций М Определение. Для двух наборов ) ,..., ~ ( n 1     и ) ,..., ( ~ n 1     выполнено отношение предшествования   ~ ~  , если n n 1 1 ,...,       . Например, ( 0,1,0,1) ( 1,1,0,1)  . Очевидно, что если   ~ ~  и   ~ ~  , то   ~ ~  . При этом не любые пары наборов находятся в отношении предшествования. Например, наборы (0,1) и (1,0) в таком отношении не находятся. Таким образом, множество всех двоичных наборов длины n по отношению к операции предшествования  является частично упорядоченным. Определение. Функция f(x 1 ,…,x n ) называется монотонной, если для любых двух наборов  ~ и  ~ , таких, что   ~ ~  имеет место ) ~ f ( ~ ) f (    . Заметим, что функция, равная монотонной функции, также является монотонной. Монотонными функциями являются 0, 1, x, x&y, x  y. Обозначим через M множество всех монотонных функций. Покажем, что класс M замкнут. Так как M содержит тождественную функцию, то достаточно показать, что функция  : ) ,..., ( 1 m f f f   является монотонной, если f, f 1 ,…,f m монотонны. Действительно, пусть ) ,..., ),..., ~ ( ,..., ), ~ ( ,..., ~ ( m 1 ml m1 m 1l 11 1 n 1 x x x x x x x x x    наборы переменных функций  , f 1 ,…,f m . Причем множество переменных функции  состоит из тех и только тех переменных, которые встречаются у функций f 1 ,…,f m .