1. Булевый базисå0 = {х1 • х2, x1Ú х2,`х}.
Полнота булева базиса следует из того, что для любой логической функции можно построить СДНФ или СКНФ.
2. Конъюнктивный булевый базис å1 = {х1 • х2,`х}. Полнота этого базиса следует из п. 1 и представления дизъюнкции в виде:
x1 Ú х2 = `х1 •`х2.
3. Дизъюнктивный булевый базис å2 = {x1 Ú х2,`х }.
Полнота этого базиса следует из п. 1 и представления конъюнкции в виде:
х1 • х2 =`х1 Ú`х2.
4. Базис Жегалкина å3 = {х1 • х2, х1 Å х2, 1}.
Полнота этого базиса следует из п. 2 и представления отрицания в виде:`х = х Å 1.
Теорема 3. Любую логическую функцию f(x1,..., xn) можно представить в виде полинома Жегалкина:
f(x1,..., xn) = а0 Å а1 x1 Å а2 x2 Å … Å а 2n-1 x1 … xn, (6)
где аi Î {0,1}, i = 0, 1,..., 2n - 1.
Доказательство. Система функций å = {х1 • х2, х1 Å х2, 1, 0} полна. Из формулы СДНФ (3), пользуясь свойствами:
x Å x = 0, x • x = x, x Å 0 = x,
x • 0 = 0, x • 1 = x, x1 • x2 = x2 • x1,
x1 Å x2 = x2 Å x1, (x1 Å x2) • x3 = (x1 • x3) Å (x2 • x3),
получим представление функции в виде полинома (6).
Следствие. Для любой логической функции, наряду с СДНФ и СКНФ в случае булева базиса, существует единственный полином Жегалкина вида (6).
|
|
Далее в теореме 4 формулируется критерий полноты системы логических функций, на основе которого можно проверить полноту данной системы функций, а также построить другие базисы.
Теорема 4 (о полноте). Для того чтобы система функций {f1(xl1 ..., х1р1),..., fs (xs1,..., xsps),...} была полна, необходимо и достаточно, чтобы она содержала функцию, не сохраняющую 0; функцию, не сохраняющую 1; несамодвойственную функцию; немонотонную функцию; нелинейную функцию.