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

38 б) система {  ,  } является полной, что может быть доказано либо аналогично предыдущему, либо через принцип двойственности. Определение. Пусть F – некоторое подмножество функций из P 2 . Замыканием F называется множество всех логических функций, представляемых в виде формул через функции из F . Замыкание множества F обозначается через [F] . Примеры замыканий: а) [P 2 ]=P 2 ; б) замыканием множества { , }  1 будет класс L всех линейных функций, т.е. функций, имеющих вид , ... ) ,..., ( n n 1 1 0 n 1 x x f x x        где  i ={0,1}, i= 0 n , . Определение. Класс F называется функционально замкнутым, если [F]=F . Примеры функционально замкнутых классов: а) P 2 ; б) класс L замкнут, т.к. линейная комбинация линейных выражений является линейным выражением. Определение (полноты в терминах замыкания и замкнутых классов). F – полная систем, если [F]=P 2 . Основные замкнутые классы Класс логических функций Т 0 Обозначим через T 0 класс всех логических функций f(x 1 ,…,x n ) , сохраняющих константу 0 , т.е. функций таких, для которых выполняется равенство f(0,…,0)=0. Заметим, что если f  T 0 , a f  – функция, равная f (т.е. отличающаяся некоторым множеством фиктивных переменных), то и f  T 0 .