.01 Булевы функции. Замкнутые и полные классы.

Возьмём, например, в качестве множества множество из одной булевой функции , в качестве множества тоже множество из одной функции .

Тогда, как мы знаем, система - полна, то есть .

Однако, понятно, что будет состоять только из конъюнкций, сколь угодно длинных, то есть конъюнкций вида , однако ничего другого кроме таких длинных конъюнкций композициями одной только конъюнкции мы получить не сможем.

Точно так же будет представлять из себя только многократно навешиваемые отрицания на одну переменную, поэтому состоит всего из двух функций - отрицания переменной и самой переменной, которая получится если дважды взять отрицание. То есть фактически (более чем двукратные отрицания будут сокращаться друг с дружкой, поскольку ).

Значит, в объединении будут лежать только сколь угодно длинные конъюнкции, переменная и её отрицание:

А это явно не все возможные булевы функции. В то время как если разрешить композиции между функциями из и из , то есть рассмотреть , то получается, что - это мы уже доказывали ранее.

Этот пример показывает, что бывают ситуации, когда включение строгое, то есть равенство там стоять не обязано.