§ 5. Полнота. Примеры полных систем

Выше было показано, что всякая функция алгебры логики может быть выражена в виде формулы через элементарные функции , x₁x₂, x₁x₂. Оказывается, что таким свойством обладают и некоторые другие системы элементарных функций.

Система функций {f₁, f₂,..., f_k} называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Примеры. Системы P₂  множество всех булевых функций и ₂={, x₁x₂, x₁x₂}.

Теорема 1.3. Пусть даны две системы функций из P₂: F={f₁, f₂,...} и G={g₁,g₂,...}, относительно которых известно, что система F полна и каждая ее функция выражается в виде формулы через функции системы G. Тогда система G также является полной.

 Пусть h  произвольная функция из P₂. Т.к. система F  полная, можно выразить h формулой над F, то есть h=c(f₁, f₂,...). По условию f₁=c₁(g₁,g₂,...), f₂=c₂(g₁,g₂,...), ... Поэтому в формуле c(f₁, f₂,...) можно исключить вхождения функций f₁, f₂,..., заменив их функциями из G:

h=c(f₁, f₂,...)=c(c₁(g₁,g₂,...), c₂(g₁,g₂,...), ...)= c’(g₁,g₂,...).

Таким образом, произвольную формулу h удалось выразить через функции системы G, что доказывает полноту этой системы. 

Опираясь на теорему 1.3, можно установить полноту еще ряда систем.

3. Система ₃={,x₁x₂} является полной. В качестве полной системы выберем ₂={,x₁x₂,x₁x₂} (см. п. 2). В соответствии с законом де Моргана, x₁x₂=.

4. Система ₄={,x₁x₂} является полной. Аналогично п. 3 с помощью закона де Моргана выражаем конъюнкцию через дизъюнкцию и отрицание: x₁x₂=.

5. Система ₅={x₁x₂}, состоящая из одной функции  стрелки Пирса, является полной. В качестве полной выберем систему ₃={,x₁x₂}. Затем, =xx и x₁x₂=(x₁x₁)(x₂x₂).

6. Система ₆={x₁|x₂}, состоящая только из одной функции  штриха Шеффера, является полной. За полную возьмем систему ₄={,x₁x₂}. Затем, =x|x и x₁x₂=(x₁|x₁)|(x₂|x₂).

7. Система ₇={1,x₁x₂,x₁x₂} является полной. За полную возьмем систему ₃={,x₁x₂}. Отрицание выразим через константу 1 и сложение по модулю 2: =x1.

Формула, построенная из констант 0 и 1 и функций x₁x₂ и x₁x₂ после раскрытия скобок и несложных алгебраических преобразований переходит в полином по модулю 2, который называют полиномом И.И.Жегалкина.

Пример. Общий вид полинома Жегалкина для функции трех переменных следующий:

f(x₁,x₂, x₃)=a₁₂₃x₁x₂x₃  a₁₂x₁x₂  a₁₃x₁x₃  a₂₃x₂x₃  a₁x₁  a₂x₂  a₃x₃  a₀ ,

где a₁₂₃, a₁₂, ..., a₀  коэффициенты полинома, каждый из которых может принимать одно из двух значений  0 или 1.

Теорема 1.4 (Жегалкина). Каждая функция из P₂ может быть выражена при помощи полинома по модулю 2.

 Подсчитаем общее число различных полиномов Жегалкина от n переменных. Число m различных конъюнкций равно количеству подмножеств (i₁,i₂,...,i_k) множества {1,2...,n}, то есть m=2ⁿ ( соответствует a₀). Каждая конъюнкция имеет коэффициент a_..., который можно выбрать двумя способами (0 либо 1). В соответствии с правилом произведения число различных полиномов от n переменных, которые можно образовать из этих конъюнкций, равно 2^m=(пустому подмножеству конъюнкций соответствует полином 0).

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

Пример. Выразить x₁|x₂ в виде полинома Жегалкина. Ответ. x₁|x₂ = x₁x₂1.