Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Пусть – некоторое подмножество множества булевых функций: .
Определение 1: Множество называется замыканием множества , если оно содержит все суперпозиции функций множества и не содержит никаких других функций.
Например, если , тогда, очевидно, .
Отметим очевидные свойства замыкания:
1) ;
2) ;
3) если , то .
Определение 2: Множество называется замкнутым классом, если выполняется условие: .
Например, пусть . Как следует из предыдущего примера, и поэтому не является замкнутым классом.
Если , то класс является замыканием класса . В силу свойства 2 операции замыкания является замкнутым классом.
Очевидно, что пересечение любого числа замкнутых классов есть замкнутый класс.
Легко заметить, что если функции содержатся в то для выяснения того, является ли замкнутым классом, достаточно ограничиться проверкой выполнения следующего условия: если функции ,..., , где , принадлежат множеству , то функция также принадлежит множеству .
Определение 3: Система функций из замкнутого класса называется полной в , если .
В случае если система полна в , то всякая функция из множества является суперпозицией функции из .
Для каждого замкнутого класса с конечным базисом введем понятие порядка замкнутого класса.
Пусть – конечный базис в . Обозначим через наибольший из порядков функций, принадлежащих множеству .
Определение 4: Порядком замкнутого класса с конечным базисом называется такое натуральное число , что (здесь минимум берется по всевозможным базисам класса ).
Теорема 1: Конъюнкция, дизъюнкция и отрицание образуют полную систему функций в .
Это утверждение вытекает из следствия 2 теоремы о разложении и соотношения: .
Из того, что и , а также из рассмотренной теоремы и неполноты каждой из систем , получаем следующие следствия.
Следствие 1: Системы функций и образуют базисы множества .
Далее, т.к. , то , .
Следствие 2: Функция образуем базис .
Следствие 3: Порядок класса равен 2.
Введём в рассмотрение принцип двойственности, имеющий в дискретной математике очень важное значение.
Определение 5: Функция называется двойственной к функции .
Из определения следует, что:
1) функция двойственна к функции ,
2) функция двойственна к функции ,
3) функция двойственна к функции ,
4) функция двойственна к функции ,
5) функция двойственна к функции ,
6) функция двойственна функции .
Заметим, что двойственная функция к двойственной функции есть исходная функция, т.е. .
Теорема 2: (принцип двойственности). Если данная функция имеет вид: , то двойственная ей функция: , где – это функции, двойственные к функциям соответственно.
Доказательство: Имеем
Что и требовалось доказать.
Пусть некоторое множество функций из . Обозначим через множество всех тех функций, которые являются двойственными к функциям из множества .
Определение 6: Назовем множество двойственным к . Множество называется самодвойственным, если .
Тогда в силу принципа двойственности имеют место следующие утверждения.
Следствие 1: Если – замкнутый класс, то также образует замкнутый класс.
Следствие 2: Если – замкнутый класс и система функций полна в , то система полна в , т.е. из следует, что .
В частности, если является базисом замкнутого класса , то является базисом .
Следствие 3: Если , то .
Определение 7: Функция называется самодвойственной, если , т. е. .
Из доказанной теоремы следует, что суперпозиция самодвойственных функций самодвойственна, т. е. множество самодвойственных функций образует замкнутый класс.
Замечание: Заметим, что константы являются несамодвойственными функциями.
Дата публикования: 2014-11-03; Прочитано: 476 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!