- •4.13. Специальные классы булевских функций определение
- •4.13.1. Функции, сохраняющие ноль
- •4.13.2. Функции, сохраняющие единицу
- •4.13.3. Самодвойственные функции
- •Определение
- •Определение
- •4.13.4. Монотонные функции
- •Определение
- •4.13.5. Линейные функции
- •4.14. Критерий функциональной полноты
- •4.14.1. Построение функций-констант
- •4.14.3. Построение конъюнкции
- •4.15. Предполные классы булевских функций определение
4.15. Предполные классы булевских функций определение
Класс B называется предполным классом, если [B] P2 и для любой функции множество является полной системой.
Предполные классы булевских функций обладают несколькими специальными свойствами.
Если B предполный класс, то [B] = B, т.е. всякий предполный класс является замкнутым классом.
Действительно, если предполный класс B незамкнут и , то справедливо соотношение . (Иллюстрация рассуждений приведена на рис. 4.7), Т.е. это неполная система. Последнее свойство противоречит предположению о том, что B является предполным классом.
B
[B]
f
P2
Рис. 4.7
ТЕОРЕМА 4.10
Классы Т0, Т1, S, L и M являются предполными.
Доказательство
Проведем доказательство теоремы только для класса Т0. Для остальных классов такое доказательство может быть выполнено аналогично.
1. Уже известно, что Т0 неполный класс.
2. Покажем, что в Т0 содержатся функции, не принадлежащие каждому из остальных классов.
Действительно, f(x1, x2) = x1 + x2 Т0, но f Т1, f S, f M. Кроме того, h(x1, x2) = x1&x2 Т0, но h L. Поэтому, по критерию полноты в P2, добавление к Т0 любой функции g Т0 преобразует Т0 в полную систему, т.е. Т0 является предполным классом.
Доказательство окончено.
ТЕОРЕМА 4.11
В P2 существует ровно 5 предполных классов.
Доказательство
Поскольку Т0, Т1, S, L и M являются предполными, то остается доказать, что всякий предполный класс в P2 совпадает с одним из этих классов.
Пусть B произвольный предполный класс в P2.
Возможен один из следующих двух случаев:
B не содержится ни в одном из классов Т0, Т1, S, L или M;
B целиком содержится в одном из классов Т 0, Т 1, S, L или M.
Первый случай оказывается невозможным, поскольку по критерию полноты система B оказывается полной системой.
Во втором случае B либо совпадает с одним из пяти классов Т0, Т1, S, L и M, либо строго содержится в одном из таких классов.
Вторая из последних ситуаций невозможна. Действительно, пусть B D, где D один из классов Т0, Т1, S, L или M, и функция f входит в D, но не принадлежит в B.
Так как D является замкнутым классом, то [B {f}] D.
Последнее противоречит тому, что B является предполным классом.
Следовательно, система B должна совпадать с одним из пяти предполных классов Т0, Т1, S, L и M.
Доказательство окончено.