Полные системы логических функций

Система функций å ={f₁(x₁₁,..., x_1p1), ..., f_s(x_s1, ..., x_sps),…} на­зывается полной, если любую логическую функцию f(x₁, ..., x_n) мож­но представить в виде супер­позиции функций {f₁, ..., f_s, ...} и переменных х₁, ..., х_n.

Функции, входящие в полную систему, называются базисными, а сама полная система функций å – базисом.

Примеры полных систем функций (базисов)

1. Булевый базисå₀ = {х₁ • х₂, x₁Ú х₂,`х}.

Полнота булева базиса следует из того, что для любой логической функ­ции можно построить СДНФ или СКНФ.

2. Конъюнктивный булевый базис å₁ = {х₁ • х₂,`х}. Полнота этого базиса следует из п. 1 и представления дизъюнкции в виде:

x₁ Ú х₂ = `х<sub>1</sub> •`х_2.

3. Дизъюнктивный булевый базис å₂ = {x₁ Ú х₂,`х }.

Полнота этого базиса следует из п. 1 и представления конъюнкции в виде:

х₁ • х₂ =`х<sub>1</sub> Ú`х₂.

4. Базис Жегалкина å₃ = {х₁ • х₂, х₁ Å х₂, 1}.

Полнота этого базиса следует из п. 2 и представления отрицания в виде:`х = х Å 1.

Теорема 3. Любую логическую функцию f(x₁, ..., x_n) можно предста­вить в виде полинома Жегалкина:

f(x₁, ..., x_n) = а₀ Å а₁ x₁ Å а₂ x₂ Å … Å а ₂ⁿ_-1 x₁ … x_n, (6)

где а_i Î {0,1}, i = 0, 1, ..., 2ⁿ - 1.

Доказательство. Система функций å = {х₁ • х₂, х₁ Å х₂, 1, 0} полна. Из формулы СДНФ (3), пользуясь свойствами:

x Å x = 0, x • x = x, x Å 0 = x,

x • 0 = 0, x • 1 = x, x₁ • x₂ = x₂ • x₁,

x₁ Å x₂ = x₂ Å x₁, (x₁ Å x₂) • x₃ = (x₁ • x₃) Å (x₂ • x₃),

получим представление функции в виде полинома (6).

Следствие.Для любой логической функции, наряду с СДНФ и СКНФ в случае булева базиса, существует единственный полином Жегалкина вида (6).

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

Теорема 4 (о полноте).Для того чтобы система функ­ций {f₁(x_l1 ..., х_1р1), ..., f_s (x_s1, ..., x_sps), ...} была полна, необ­хо­димо и достаточно, чтобы она содер­жала функцию, не сохраняющую 0; функцию, не сохраняющую 1; несамо­двой­ственную функцию; немо­нотонную функцию; нелинейную функцию.