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

39 Далее, функции 0, x, x&y, x  y, x  y принадлежат классу T 0 , а функции 1, x не входят в Т 0 . Поскольку таблица для функций f из класса T 0 в первой строке содержит значение 0 , то в Т 0 содержится ровно n 2 2 2 1 ( ) булевых функций, зависящих от переменных х 1 ,…,х n . Покажем, что T 0 –замкнутый класс. Так как T 0 содержит тождественную функцию (в противном случае необходимо было бы показать, что x i =f(f 1 ,…,f n ) ), то для обоснования замкнутости достаточно показать, что функция  :  =f(f 1 ,…,f n ) принадлежит T 0 , если f,f 1 ,…,f n принадлежат T 0 . Это следует из цепочки равенств  (0,…,0)=f(f 1 (0,…,0),…,f n (0,…,0))=f(0,…,0)=0. Класс логических функций Т 1 Обозначим через T 1 класс всех логических функций f(x 1 ,…,x n ) , сохраняющих константу 1, т.е. функций, для которых выполнено равенство f(1,…,1) =1 . Очевидно, что класс Т 1 вместе с любой функцией содержит и любую равную ей функцию. Легко видеть, что функции 1, x, x&y, x  y принадлежат классу T 1 , а функции 0 и x не входят в T 1 . Аналогично предыдущему показывается, что T 1 содержит n 2 2 2 1 ( ) , функций, зависящих от n переменных, и является замкнутым классом. Замечание. Класс T 1 состоит из функций, двойственных функциям из класса T 0 . Класс логических функций S Обозначим через S класс всех самодвойственных функций f из P 2 , т.е. таких, что f * =f .