Будем исходить из некоторого множества F функциональных символов. Каждому символу приписано натуральное число – местность (или арность) символа. Можно считать, что F представляет собой объединение F₁ÈF₂È… F_nÈ… , где F_n – множество символов n-местных функций. Кроме F, имеется множество переменных V, элементы которого будем обозначать буквами u,v,w,x,y,z с индексами и без них. Каждому n-местному функциональному символу поставлено в соответствие (всюду определенное) отображение

(При этом разным символам может соответствовать одно и то же отображение.) Это отображение будем обозначать той же буквой, что и символ.

Введем основное понятие.

Определение. Булевыми функциями называются выражения одного из следующих видов:

1)     f(v₁,…v_n), где fÎF_n, v₁,…,v_n – переменные,

2)     f(t₁,…t_n), где fÎF_n, t₁,…,t_n – булевы функции.

Для обозначения двухместных функций наряду с префиксным f(v₁,v₂) мы будем применять и инфиксное v₁fv₂, особенно, если речь идет об известных функциях, например, x₁+x₂, x₁×x₂. Условимся так же об обозначении некоторых часто встречающихся функций. Эти обозначения содержатся в таблицах 2.1 и 2.2.

Таблица 2.1

Таблица 2.2

(Заметим, что любую функцию f(x₁,…,x_n) можно задать аналогичной таблицей, содержащей 2ⁿ строк). Функции q(x) и i(x) будем называть константами, e(x) – тождественной функцией. Функцию n(x) будем иногда называть отрицанием. Для функций xÚy, x®y, x«y сохраним названия, идущие из логики высказываний: дизъюнкция, импликация и эквиваленция. Функции x×y и x+y, – естественно, умножение и сложение; умножение можно было бы назвать конъюнкцией. Функция x|y – штрих Шеффера, x¯y – стрелка Пирса (или стрелка Лукасевича).

В обозначениях функций будем допускать фиктивные переменные. Так, например, функцию x₁+x₂ можно обозначить через f(x₁,x₂,x₃).

Определение. Класс булевых функций K называется замкнутым относительно переименования аргументов, если из того, что n-местная функция f(x₁,…,x_n) принадлежит K, а y₁,…y_n – другие переменные (среди которых могут быть и совпавшие), то функция f(y₁,…y_n) также принадлежит K.

Например, если K содержит функцию x+y и замкнут относительно переименования аргументов, то K содержит также и функцию q(x).

Определение. Класс булевых функций K называется замкнутым относительно суперпозиции, если из того, что функции f(x₁,…x_k), g₁(x₁,…x_n),…, g_k(x₁,…,x_n) принадлежат K следует, что функция

f(g₁(x₁,…,x_n),…g_k(x₁,…x_n))

также принадлежит K.

Например, если K содержит функцию xÚy и n(x) и замкнут относительно суперпозиции (и переименования аргументов), то K содержит и x×y, поскольку x×y=n(n(x)Ú n(y)).

Определение. Класс булевых функций K называется замкнутым, если K

1)     содержит тождественную функцию;

2)     замкнут относительно переименования аргументов;

3)     замкнут относительно суперпозиции.

Приведем примеры. Функция f(x₁,…,x_n) называется сохраняющей

ноль, если f(0,…,0)=0. Функции x×y, xÚy, x+y сохраняют ноль, а x«y, x|y, x¯y не сохраняют. Через T₀ обозначим класс всех функций, сохраняющих 0, т.е.

T₀={f(x₁,…,x_n)| f(0,…,0)=0}.

Докажем, что класс T₀ замкнут. Функция e(x) сохраняет 0 и поэтому e(x)ÎT₀. Если f(x₁,…,x_n) сохраняет 0 и y₁,…y_n – новые переменные, то очевидно, что f(y₁,…,y_n) также сохраняет ноль. Это означает, что T₀ замкнут относительно переименования аргументов. Пусть f(x₁,…,x_k), g₁(x₁,…,x_n), …, g_k(x₁,…,x_n) сохраняют 0. Тогда

f(g₁(0,…,0),…,g_k(0,…,0))=f(0,…,0)=0.

Это означает, что T₀ замкнут относительно суперпозиции. Мы доказали, что T₀ – замкнутый класс.

Функция f(x₁,…,x_n) называется сохраняющей единицу, если f(1,…,1)=1. Функции x×y, xÚy, x®y сохраняют единицу, а функции x+y, x|y, x¯y не сохраняют. Через T₁ обозначим класс всех функций, сохраняющих 1, т.е.

T₁={f(x₁,…,x_n)| f(1,…,1)=1}.

Класс T₁ является замкнутым. Доказательство аналогично приведенному в предыдущем абзаце.

Теорема 2.1. Пересечение непустого семейства K={K_i | iÎI} замкнутых классов является замкнутым классом.

Доказательство. Пусть K=Ç{K_i½iÎI}. Класс K содержит тождественную функцию, так как все K_i ее содержат. Если f(x₁,…,x_n) принадлежит K, а y₁,…,y_n – новый набор переменных, то для любого i функция f(x₁,…,x_n)ÎK_i, поскольку K – пересечение этих классов, и f(y₁,…,y_n)ÎK_i, поскольку K_i замкнут относительно переименования аргументов. Если функция f(y₁,…,y_n) принадлежит всем классам K_i, то эта функция принадлежит и их пересечению, т.е. K. Следовательно, K замкнут относительно переименования аргументов.

Предположим, что функции f(x₁,…,x_k), g₁(x₁,…,x_n), …, g_k(x₁,…,x_n) принадлежат K. Тогда эти функции принадлежат всем классам K_i. Класс K_i замкнут относительно суперпозиции. Следовательно, для любого i класс K_i содержит функцию

f(g₁(x₁,…,x_n),…, g_k(x₁,…,x_n)).

Отсюда следует, что эта функция принадлежит пересечению этих классов – классу K. Мы доказали, что K замкнут относительно суперпозиции.

Теорема доказана.

Определение. Замыканием класса K называется пересечение всех замкнутых классов, содержащих K.

Замыкание класса K будем обозначать через [K]. Из теоремы 2.1 следует, что [K] – замкнутый класс.

Отметим ряд простых свойств замыкания.

Теорема 2.2. Пусть K – класс булевых функций. Тогда

1) KÍ[K],

2) если KÍL, то [K]Í[L],

3) класс K замкнут тогда и только тогда, когда K=[K].

Доказательство. Пусть K={K_i½iÎJ} – семейство (всех) замкнутых классов, содержащих K. Так как K содержится в K_i для любого i, то K содержится и в их пересечении, т.е. в [K].

Предположим, что Z={L_j½ÎJ}-семейство замкнутых классов, содержащих L, и что KÍL.Тогда KÍL_j для любого j и поэтому LÍK. Отсюда следует, что Ç{K_i½iÎI}ÍÇ{L_j½jÎJ}, т.е. что [K]Í[L].

Если K – замкнутый класс, то KÎK. Следовательно, K=Ç{K_i½iÎI}=[K]. Если же K=[K], то K совпадает с одним из классов K_i и поэтому замкнут.

Теорема доказана.

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

Пусть K={q(x), i(x), x+y, x×y}. Тогда класс [K] содержит многочлены (от любого числа переменных). Эти многочлены называются полиномами Жегалкина. Поскольку произведение элементов множества B удовлетворяет тождеству u²=u, то полином Жегалкина можно записать в виде Sa_i1,…,_ikx_i1…x_ik, где {i₁,…,i_k}Í{1,…,n}, a_i1,…,_ikÎB и суммирование ведется по всем подмножествам множества [1,…,n}. Например, 1×x₁x₂+0×x₁+1×x₂+1 – полином Жегалкина от двух переменных х₁ и х₂ и а₁₂=1, а₁=0, а₂=1, а₀==1. Этот полином можно, конечно, записать и так: х₁х₂+х₂+1.

Обозначим через BF класс всех булевых функций.

Определение. Класс функций K полным, если [K]=BF.

Другими словами, класс K полон, если любую булеву функцию можно получить из K ( и тождественной функции) с помощью суперпозиции и переименования аргументов.

Теорема 2.3. Следующие классы функций являются полными

1)     K₁={x×y, xÚy, n(x)}

2)     K₂={x×y, n(x)}

3)     K₃={xÚy, n(x)}

4)     K₄={x×y, x+y, q(x), ((x)}

Доказательство. Докажем, что любая функция может быть получена из функций класса K₁ с помощью суперпозиции и переименования аргументов. Доказательство проведем на примере функции f(x₁,x₂,x₃), заданной таблицей 2.3.

Таблица 2.3

Выделим те строки таблицы, где в последнем столбце стоит 1. Это вторая, шестая, и седьмая строки. Каждой строке поставим в соответствие произведение переменных или их отрицаний следующим образом. Второй строке поставим в соответствие произведение n(x₁)×n(x₂)×x₃, шестой – x₁×n(x₂)×x₃, седьмой – x₁×x₂×n(x₃), т.е. если переменная x принимает значение 1, то пишем x, если принимает значение 0, то пишем n(x). Легко видеть, что функция

g(x₁,x₂,x₃) =[n(x₁)×n(x₂)×x₃]Ú[x₁×n(x₂)×n₃]Ú[ x₁×x₂×n(x₃)]

задается той же таблицей 2.3. Это означает, что f(x₁,x₂,x₃) равна g(x₁,x₂,x₃). Но в записи функции g(x₁,x₂,x₃) использованы только функции из класса K₁. Следовательно, f(x₁,x₂,x₃) может быть получена из функций класса K₁ суперпозицией и переименованием аргументов, т.е. f(x₁,x₂,x₃)Î[K]. (Естественно, есть прямая аналогия между построением функции g(x₁,x₂,x₃) и приведением к СДНФ, изложенном в конце §5 темы 1.) На основании этого заключаем, что любая булева функция принадлежит замыканию [K₁]. Следовательно, K₁ – полный класс.

Полнота классов K₂ и K₃ получается из полноты класса K₁ с помощью следующего утверждения. Если K – полный класс и любая функция класса K выражается (с помощью суперпозиции и переименования аргументов) через функции класса L, то L – полный класс. Действительно, если любая булева функция выражается через функции класса K, то она будет выражаться и через функции класса L. Мы уже отмечали, что x×y=n(n(x)Ún(y)). Это равенство доказывает полноту класса K₃. Далее справедливо равенство xÚy=n(n(x)×n(y)), из которого следует полнота класса K₂. Полнота класса K₄ следует из полноты класса K₂ и равенства n(x)= x+i(x). Полнота класса K₄ означает, в частности, что каждая булева функция может быть задана полиномом Жегалкина. Например, x₁®x₂=x₁×x₂+х₁+1, х₁Úх₂=х₁×х₂+х₁+х₂.

Теорема доказана.

Связь излагаемого материала с логикой высказываний достаточно очевидна. Тем не менее, отметим следующее. Пусть F(X₁,…,X_n) и G(X₁,…,X_n) – формулы логики высказываний. Заменим ØX на n(X), X&Y на X×Y, большие буквы X_i на маленькие x_i(1£i£n). Получим функции f(x₁,…,x_n) и g(x₁,…,x_n). Тогда формулы F(X₁,...,X_n) и G(X₁,...,X_n) равносильны в том и только в том случае, когда функции f(x₁,…,x_n) и g(x₁,…,x_n) равны. Это замечание позволит нам при доказательстве равенства функций ссылаться на законы логики высказываний.