Дефинираме двоична функция f (x, ) = x по следния начин:
x = x, ако = 1 и x = , ако = 0.
Лема: 0 = , 1 = .
Формули от вида , където при j s, j { 0, 1}, наричаме елементарни конюнкции.
Теорема (Бул): Множеството { x y, xy, } е пълно.
Доказателство: Ако f =, можем да представим f = x и тогава
f [{ x y, xy, } ].
Нека f . Тогава f (x1, x2, …, xn) = , което е формула над { x y, xy, }.
В означенията на доказателството, когато f , формулата се нарича съвършена дизюнктивна нормална форма на f.
Теорема: Нека F F2 е пълно множество, G F2 и за всяка функция f F имаме f [G]. Тогава G е пълно множество.
Следствие: { xy, } е пълно, { x y, } е пълно,
{ , , xy, x y } е пълно.
Доказателство: От теоремата на Бул и законите на Де Морган , и от = x .
Да се спрем на последното пълно множество от следствието.
Нека f F2. Тогава f има формула над { , , xy, x y }. Разкриваме скобите във формулата, като прилагаме дистрибутивния закон на конюнкцията спрямо събирането по модул 2, използваме идемпотентността на умножението (xx = x) и факта, че f f = . Накрая получаваме многократна сума по
модул 2 от елементарни конюнкции без отрицания, като една елементарна конюнкция участва най-много веднъж. При това, от аналогията на конюнкцията с умножението по модул 2, получената формула може да разглеждаме като полином над полето GF (2) (полето с два елемента). Наричаме я полином на Жегалкин.
Теорема: Всяка булева функция има и то единствен полином на Жегалкин.
Доказателство: Всяка функция има полином, различните функции имат различни полиноми и броят на полиномите е = |F2n|.
Казваме, че множеството F F2 е затворено, ако [F] = F.
Например F2 е затворено, тъй като [F2] = F2.
Множествата {}, {}, { x, } също са затворени.
Теорема (критерий за затвореност): Нека F F2 е такова, че
1. f (x) = x F;
2. за всяка функция f (x1, …, xn) F и g1, …, gn F имаме
h = f (g1, …, gn) F.
Тогава F е затворено множество.
Kазваме, че функцията f (x1, …, xn) F2 запазва нулата, ако
f (0, …, 0) = 0. Kазваме, че функцията f (x1, …, xn) F2 запазва единицата, ако f (1, …, 1) = 1.
Oзначаваме с T0 множеството от всички булеви функции, които запазват нулата. Tези от тях които са на n променливи
означаваме с T0n. Oзначаваме с T1 множеството от всички булеви функции, които запазват единицата и с T1n тези от тях, които са на n променливи.
Например xy T0, x y T0, xy T1, x y T1, x T0, x T1,
T0, T1, x y T0, x y T1.
Така T0 F2 и T1 F2.
Очевидно, |T0n| = = |T1n|, тъй като всяка функция запазваща коя да е от константите се дефинира по произволен начин върху всички вектори освен един.
Теорема: Множествата T0 и T1 са затворени множества от булеви функции.
Доказателство: Директно от критерия за затвореност.
Редактор: Снежина Стоянова
