Теорема Поста

В силу теоремы о представлении любой булевой функции дизъюнктивной или конъюнктивной нормальной формой стандартный базис {∨, ·,   } является полным множеством. Поскольку, согласно законам де Моргана, можно выразить конъюнкцию через дизъюнкцию и отрицание, равно как и дизъюнкцию можно выразить через конъюнкцию и отрицание, то при удалении из стандартного базиса одной функции, дизъюнкции или конъюнкции, при сохранении отрицания, получим снова полное множество.

Прежде чем рассматривать другие примеры полных множеств, установим один важный факт.

Теорема 6.3. Пусть F и G - некоторые множества булевых функций, причем F - полное множество. Тогда, если каждая функция из F может быть представлена некоторой формулой над множеством G, то G - полное множество.

◀ Из условия теоремы следует, что каждая функция f ∈ F может быть представлена некоторой формулой Ψ над G, т.е.

f(x₁,...,x₁) = Ψ(x₁,...,x_n).    (6.17)

Докажем, что всякая формула над F эквивалентна некоторой формуле над G, т.е. всякая функция φ, представляемая формулой над F, может быть представлена также и некоторой формулой над G. Доказательство проведем по такой схеме: сначала убедимся в справедливости утверждения для "базисных" формул, т.е. для переменных и констант из F, а затем в предположении, что оно уже доказано для формул Ф₁, ... , Ф_n, где n ≥ 1, докажем его для любой формулы вида f(Ф₁, ... , Ф_n), где f ∈ F. Такой метод доказательства называют доказательством индукцией по построению формулы.

Пусть φ - какая-то формула над F. Если φ = х, где х - булево переменное из множества Х, то, поскольку каждое переменное есть, по определению, и формула над G, функция φ представляется формулой над G.

Если φ есть константа из F, то представляющая φ формула над G существует ввиду (6.17).

Рассмотрим формулу над F вида f(Ф₁, ... , Ф_n), где n > 0, f ∈ F, а Ф₁, ... , Ф_n - формулы над F. Согласно предположению индукции, каждая формула Ф_i, i = 1,n, может быть заменена эквивалентной ей формулой Θ_i над G (т.е. имеет место тождество Ф_i = Θ_i над F ∪ G). Тогда, используя правила эквивалентных преобразований формул (см. теорему 6.1), получим тождество

f(Ф₁, ... , Ф_n) = f(Θ₁,...,Θ_n),

а в соответствии с (6. 17) будем иметь

f(Θ₁,...,Θ_n) = Ψ(Θ₁,...,Θ_n).     (6.18)

Правая часть тождества (6.18) и есть формула над G, эквивалентная исходной формуле над F.

Поскольку в силу полноты множества F любая булева функция может быть представлена некоторой формулой над F, а любая такая формула, как мы только что доказали, эквивалентна некоторой формуле над G, то любая булева функция может быть представлена некоторой формулой над G, что и доказывает полноту множества G. ▶

Пример 6.17. Рассмотрим базис Жегалкина {⊕, ·, 1}. Чтобы доказать полноту этого множества, заметим, что

x ∨ y = х · у ⊕ х ⊕ у, х = х ⊕ 1,

т.е. каждый элемент стандартного базиса может быть представлен формулой над базисом Жегалкина. Отсюда и следует (ввиду полноты стандартного базиса и теоремы 6.3) полнота базиса Жегалкина. #

Любую формулу над базисом Жегалкина называют полиномом Жегалпина. Полином Жегалкина от n переменных может быть записан в виде

где коэффициенты полинома a_i1i2...im ∈ {0, 1} индексированы всеми возможными подмножествами множества {1, 2, ... , n} (коэффициент а₀ соответствует пустому множеству). В частности, при n = 3 будем иметь:

a₁₂₃x₁x₂x₃ ⊕ a₁₂x₁x₂ ⊕ a₁₃x₁x₃

(общий вид полинома Жегалкина от трех переменных). Формула вида

называется полиномом Жегалпина первой степени от переменных. В таком полиноме отсутствуют "нелинейные" слагаемые, т.е. все коэффициенты, индексированные более чем одноэлементными подмножествами, равны 0 (и вместе с ними равны 0 все слагаемые, содержащие конъюнкции переменных).

Можно доказать следующее достаточно простое, но важное утверждение.

Теорема 6.4. Полином Жегалкина для любой булевой функции определен однозначно.

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

Пример 6.18. Пусть вектор значений булевой функции а равен 11001011. Найдем полином Жегалкина, представляющий а. Поскольку размерность вектора значений а равна 2³ = 8, то f задана как функция от трех переменных. Тогда она представляется некоторым полиномом Жегалкина третьей степени, общий вид которого дает формула (6.19). Наша задача - найти такие значения коэффициентов этого полинома, при которых он представляет функцию f. Ясно, что значение функции f на наборе 000 равно коэффициенту а₀ в формуле (6.19). Но, согласно заданному вектору значений, оно равно 1. Следовательно, а₀ = 1. Далее,

f(0,0,1) = a₃ ⊕ 2₀ = a³ ⊕ 1 = 1,

откуда, решая уравнение относительно 2³ в поле ℤ₂, получим 2³ = 0;

f(0,1,0) = а₂ ⊕ 1 = 0,

т.е. а₂ = 1;

f(1,0,0) = а₁ ⊕ 1 = 1,

и а₁ = 0. Чтобы найти коэффициенты а₁₂, а₁₃ и а₂₃, нужно рассмотреть значения функции на наборах 110, 101 и 011 соответственно. Так, для первого набора получим

f(1,1,0) = а₁₂х₁х₂ ⊕ а₁х₁ ⊕ а₂х₂ ⊕ а₀ = а₁₂ ⊕ а₂ ⊕ а₀ = а₁₂ ⊕ 1 ⊕ 1 = а₁₂

(сумма по модулю 2 любого четного числа равных слагаемых равна 0). Поскольку в то же время f(1,1,0) = 1, то а₁₂ = 1.

Аналогично

f(1,0,1) = а₁₃ ⊕ а₀ = 0,

откуда а₁₃ = 1;

f(0,1,1) = а₂₃ ⊕ а₂ ⊕ а₀ = 0,

и, так как а₂ = а₀ = 1, а₂₃ = 0. Наконец,

f(1,1,1) = a₁₂₃ ⊕ a₁₂ ⊕ a₁₃ ⊕ a₂ ⊕ a₀ = a₁₂₃ = 1

Итак,

f = x₁x₂x₃ ⊕ x₁x₂ ⊕ x₁x₃ ⊕ x₂ ⊕ 1. #

Как видно из примера 6.18, суть метода неопределенных коэффициентов состоит в следующем. Записывая полином Жегалкина сначала в общем виде, с неопределенными коэффициентами, мы выражаем значение полинома на фиксированных наборах через коэффициенты и приравниваем его заданному значению функции. Начинаем с нулевого набора и находим коэффициент ао, равный значению заданной функции на нулевом наборе. Зная его, из рассмотрения значений фукнции на наборах , содержащих в точности одну единицу, находим коэффициенты a_i при "одиночных" переменных (коэффициенты "линейной части" полинома). Зная их, из рассмотрения значений функции на наборах, содержащих в точности две единицы, находим коэффициенты при конъюнкциях двух переменных и т.д. При этом выполняются вычисления и решаются простейшие линейные уравнения в поле вычетов по модулю 2.

Пример 6.19. а. Рассмотрим множество {|}, состоящее из единственной функции (штриха Шеффера). Полнота этого множества следует из легко проверяемых тождеств

х·у= (x|y)|(x|y), х = (x|x).

б. Полнота множества {↓}, единственным элементом которого является стрелка Пирса, проверяется аналогично. #

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

Определение 6.8. Функцию f называют функцией, сохраняющей константу 0 (соответственно константу 1), если а(0˜ )= 0 (соответственно: а(1˜ ) = 1), где 0˜ - нулевой, а 1˜ - единичный наборы значений переменных функции f.

Например, мажоритарная функция является функцией, сохраняющей и константу 0, и константу 1. Отрицание не сохраняет ни 0, ни 1, а эквивалентность сохраняет 1, но не сохраняет 0. Множество всех функций, сохраняющих константу 0 (константу 1), обозначается Т₀ (соответственно Т₁),

Наборы из булева куба Bⁿ = {0,1}ⁿ (для произвольного фиксированного n) будем называть взаимно противоположными, говоря при этом так же, что набор есть инверсия (или отрицание) набора α˜ (в силу единственности дополнения любого элемента булевой алгебры набор α˜ будет, очевидно, инверсией набора .

Определение 6.9. Функцию g ∈ P_2,n называют двойственной к функции f ∈ P_2,n, если для всякого α˜ ∈ {0,1}ⁿ (n > 0) имеет место

Полагаем также, что константа 0 является двойственной к константе 1 и наоборот.

Пример 6.20. а. Стрелка Пирса есть функция, двойственная к штриху Шеффера, так как

б. Сумма по модулю 2 двойственна к эквивалентности, так как

Эти две функции являются и отрицанием друг друга, но неверно в общем случае, что функция g, будучи отрицанием функции f, двойственна к f: штрих Шеффера не есть функция, двойственная к конъюнкции, а стрелка Пирса не естъ функция, двойственная к дизъюнкции, но конъюнкция двойственна к дизъюнкции и наоборот, а стрелка Пирса двойственна к штриху Шеффера и наоборот. #

В общем случае в силу уже упомянутого свойства единственности дополнения в булевой алгебре функция h, двойственная к функции g, которая двойственна к f, равна f.

Определение 6.10. Функцию f ∈ P_2,n называют самодвойственной, если она двойственна к себе самой, т.е.

Таким образом, функция само двойственна тогда и только тогда, когда на взаимно противоположных наборах она принимает взаимно противоположные значения. Следовательно, для того чтобы убедиться в несамодвойственности заданной функции f, достаточно найти хотя бы одну пару взаимно противоположных наборов , таких, что значения функции на них совпадают, т.е. f(а)= f(). Так, мажоритарная функция является само двойственной, а эквивалентность - нет, поскольку при α˜ = {0, 0) 0 ~ 0 = 1 и 1 ~ 1 = 1.

Множество всех самодвойственных функций (при всех n ≥ 1) обозначим S.

Определение 6.11. Функцию f ∈ P_2,n называют монотонной, если для любых наборов α˜, β˜ ∈ Bⁿ, таких, что α˜ ≤ β˜, имеет место f(α˜) ≤ f(β˜).

Другими словами, функция монотонна тог да и только тогда, когда для любого набора α˜ имеет место следующее свойство: если значение функции на наборе α˜ равно 1, то оно равно 1 и на всех наборах, строго больших (по отношению булева порядка на Bⁿ) набора α˜. Любой минимальный (относительно того же порядка) набор α˜, для которого значение f(α˜) монотонной функции f равно 1, называют нижней единицей фунпции f. Очевидно, что вектор значений монотонной булевой функции полностью определяется множеством ее нижних единиц*. Мажоритарная функция монотонна, и множество ее нижних единиц есть {011, 101, 110}. Штрих Шеффера - немонотонная функция, так как 00 < 11, но 0|0 = 1, а 1|1 = 0. Множество всех монотонных функций принято обозначать через М.

* нетрудно понять, что множество нижних единиц монотонной функции f есть множество всех минимальных элементов множества С^1f -конституент единицы функции f.

Определение 6.12. Функцию f ∈ P_2,n называют линейной, если она может быть представлена полиномом Жегалкина первой степени от n переменных, т.е. формулой вида (6.20).

Множество всех линейных функций принято обозначать через L.

Любая булева константа и любая проектирующая функция х являются линейными функциями. Такова, разумеется, сумма по модулю 2. Отрицание также линейно, ибо x = х ⊕ 1. Конъюнкция и дизъюнкция не являются линейными функциями, так как не могут быть представлены полиномом Жегалкина первой степени (см. теорему 6.4).

Определение 6.13. Множества функций Т₀, Т₁, S, М, L называются классами Поста.

Замечание 6.9. Каждый класс Поста состоит из функций с соответствующим свойством для любого числа переменных. Можно доказать также, что если функция f принадлежит какому-то классу Поста С, то и любая функция, равная функции f, принадлежит этому же классу. Другими словами, добавление или удаление фиктивных переменных не выводит за пределы любого из классов Поста.

Полезно еще заметить, что любая проектирующая функция х принадлежит одновременно всем пяти классам Поста. Действительно, если f(x)= х, то f(0)= 0 и f(1)= 1, т.е. f ∈ Т₀ ∩ T₁. Отсюда же вытекает и самодвойствеииость функции х. Монотонность следует из того, что 0 < 1 и f(0)= 0 < f(1) = 1. Линейность очевидна.

В то же время существуют функции, не принадлежащие ни одному из классов Поста. Таков, например, штрих Шеффера. Все свойства, кроме нелинейности, следуют прямо из таблицы этой функции. Нелинейность же доказывается выводом полинома Жегалкина для штриха Шеффера:

x|y = x·у = х·у ⊕ 1,

что не есть полином Жегалкина первой степени. #

Фундаментальным свойством каждого класса Поста является его замкнутость (в смысле определения 6.3). Это означает для любого из классов Поста С, что всякая суперпозиция над С снова есть элемент С.

Теорема 6.5. Каждый класс Поста замкнут.

◀ Нужно для каждого класса Поста С ∈ {Т₀, Т₁, S, М, L} доказать, что замыкание [С] множества булевых функций С совпадает с С. Пусть f (g₁, ..., g_n) - какая-то суперпозиция над С. Обозначим ее через φ. Без ограничения общности можно считать, что все функции f, g₁, ..., g_n ∈ P_2,n (для некоторого n).

Рассуждаем, используя индукцию по определению суперпозиции. Если для каждого i = 1,n функция g_i = x_i, где x_i - переменное, то φ = f(x₁, ..., x_n) ∈ С. Предположим, что в суперпозиции φ все функции g_i есть элементы класса Поста С (в частности, это может быть и соответствующая проектирующая функция, которая ввиду замечания 6.9 принадлежит всем классам Поста). Докажем, что и φ = f(g₁, ..., g_n) ∈ С.

1. Если С = Т₀, то φ(0˜) =f(g₁(0˜), ..., g_n(0˜)) = f(0, ...,0) = 0, так как f, g₁, ..., g_n ∈ Т₀. Следовательно, φ ∈ Т₀.
2. При С = Т₁ рассуждаем точно так же.
3. Пусть С = S. Фиксируем произвольно набор α˜ ∈ {0, 1}ⁿ.
   Вычислим (используя самодвойственность всех функций):
   
   Следовательно, φ ∈ S.
4. С = М. Берем произвольно наборы α˜ и β˜ так, что α˜ ≤ β˜. Докажем, что φ ∈ М. Имеем
   φ(α˜) = f(g₁(α˜),..., g_n(α˜)) ≤ f(g₁(β˜),..., g_n(β˜)) = φβ˜,
   так как все функции g_i, i = 1,n, монотонны и тем самым вектор (g₁(α˜), ...,g_n(α˜)) не больше вектора (g₁(β˜), ...,g_n(β˜)), а функция f также монотонна. Тог да ясно, что φ ∈ М.
5. Если же С = L, то очевидно, что при подстановке в линейную функцию (полином Жегалкина первой степени) вместо ее переменных произвольных линейных функций получится снова линейная функция. Итак, мы доказали замкнутость каждого класса Поста. ▶

Докажем теперь теорему, характеризующую одно важное свойство немонотонных функций.

Теорема 6.6. Если функция f не является монотонной, т.е. f ∉ М, то найдутся два таких набора α˜, β˜, что

α˜ = (α₁, .. , , α_i-1, 0, α_i+1,..., α_n),

β˜ = (α₁, .. , , α_i-1, 1, α_i+1,..., α_n),

и f(α˜) = 1, f(β˜) = 0, т.е. эти два набора различаются значениями в точности одной компоненты, а значение функции равно 0 на большем наборе и равно 1 на меньшем.

◀ Так как функция f не является монотонной, то найдутся такие два набора γ˜ и δ˜, что γ˜ < δ˜, но f(γ˜)= 1, f(δ˜) = 0. Строгое неравенство γ˜ < δ˜ означает, что найдутся такие номера (не меньше одного) 1 ≤ i₁ < i₂ <...< i_k ≤ n, что

γ˜ = (γ₁,...,γ_i1-1, 0, γ_i1+1,...,γ_i2-1,0,...,γ_i2+1,...,γ_ik-1,0,γ_ik+1,...,γ_n),

а

δ˜ = (γ₁,...,γ_i1-1, 1, γ_i1+1,...,γ_i2-1,1,...,γ_i2+1,...,γ_ik-1,1,γ_ik+1,...,γ_n),

т.е. все компоненты наборов, кроме выделенных, с номерами i₁, i₂, ... , i_л соответственно совпадают, а все компоненты с выделенными номерами у меньшего набора равны 0, а у большего равны 1. Построим монотонно возрастающую последовательность наборов γ˜ = γ˜ ₀ < γ˜ ₁ < γ˜ ₂ < ... < γ˜ _k = δ˜ так, что для каждого s ∈ {1, 2, ..., k} набор γ˜_s получается из набора γ˜_s-1 заменой нулевого значения компоненты с номером i_s единичным. Поскольку f(γ˜) = 1, а f(δ˜) = 0, то обязательно найдется такое s ∈ {1, 2, ..., k}, что f(γ˜_s-1) = 1, а f(γ˜_s) = 0 (на наборе γ˜_s-1 значение функции еще равно 1, а на наборе γ˜_s оно уже равно 0). Полагая α˜ = γ˜_s-1 и β˜ = γ˜_s, получим доказываемое. ▶

Теорема 6.7 (критерий Поста). Множество F булевых функций полно тогда и только тогда, когда оно не содержится целиком ни в одном из классов Поста.

◀ Необходимость условия теоремы доказывается просто: если бы для некоторого класса Поста С выполнялось F ⊆ С, то всякая суперпозиция над F, согласно теореме 6.5, снова лежала бы в С. Между тем существуют функции, не содержащиеся ни в одном из классов Поста, например штрих Шеффера (см. пример 6.9). Таким образом, нашлась бы функция, которую нельзя представить в виде суперпозиции над F, что противоречит предположению о полноте F.

Переходим к доказательству достаточности условия теоремы. Для доказательства полноты множества F, удовлетворяющего условию теоремы, построим формулы над F для функций отрицания и конъюнкции, поскольку, как было замечено выше, множество, образованное этими функциями, полно. Тогда в силу теоремы 6.3 будет полным и множество F.

Для немонотонной функции f_M ∈ F\М, согласно теореме 6.6, найдутся два таких набора α˜ и β˜, что

α˜ = α₁,...,α_i-1, 0, α_i+1,...,α_n,

β˜ = α₁,...,α_i-1, 1, α_i+1,...,α_n,

f_M(α˜) = 1, а f_M(β˜) = 0.

Тогда x = f_M(α₁, ... ,α_i-1,х,α_i+1, ... ,α_n), т.е. отрицание может быть получено из немонотонной функции подстановкой вместо некоторого ее переменного x₁ переменного х, а вместо остальных переменных констант α₁, ... ,α_i-1,α_i+1, ... ,α_n, определяемых выбранными выше наборами α˜ и β˜. Но, вообще говоря, система F может и не содержать констант. Поэтому константы 0 и 1 необходимо представить некоторыми формулами над F.

Рассмотрим два случая.

П е р в ы й с л у ч а й. В F существует функция f₀, не сохраняющая константу 0, которая сохраняет константу 1; или существует функция f₀, не сохраняющая константу 1, но сохраняющая константу 0.

Если существует функция f₀ ∉ Т₀ и f₀ ∈ Т₁, то константа 1 представляется формулой

1 = f₀(х, ... ,х),

так как f₀(0, ... ,0) = 1 и f₀(1, ..., 1) = 1. Чтобы выразить константу 0, используем любую функцию g ∈ F, не сохраняющую константу 1:

0 = g(1, ... , 1) = g(f₀(х, ... ,х), ..., f₀(х, ... ,х)).

Если же указанная функция f₀ не существует, но найдется функция f₁ ∈ Т₀\Т₁, то константы представляем формулами над F аналогично (двойственным образом).

В т о р о й с л у ч а й. Любая функция из F, не сохраняющая константу 0, не сохраняет и константу 1, и, наоборот, любая функция из F, не сохраняющая константу 1, не сохраняет и константу 0.

Пусть f₀(0, ... ,0)= 1, а f₀(1, ... ,1) = 0. Тогда мы получаем возможность представить отрицание следующей формулой:

x = f₀(х, ... ,х).

Переходим к построению формул для констант, так как они потребуются нам далее при построении формулы для конъюнкции. Чтобы представить константы формулами над F, воспользуемся несамодвойственной функцией f_S из F. Для этой функции найдется такой набор α˜, что f_S() = f_S(α˜). Введем функцию от одного переменного h(x) = f_S(x^α₁,...,x^α_n)( в предположении, что α˜ = (α₁, ..., α_n)). Легко видеть, что h(O) = = f_S() = f_S(α˜) = h(1), так как для любого σ ∈ {0, 1}

Итак, значение h{x) есть константа. Если она равна 0, то константу 1 представляем через функцию, не сохраняющую константу 0; если же h(x) = 1, то константу 0 представляем через функцию, не сохраняющую константу 1.

Опишем построение формулы для конъюнкции. Берем нелинейную функцию f_L из F. В полиноме Жегалкина для этой функции выберем произвольное нелинейное слагаемое, содержащее наименьшее число переменных; пусть это будет слагаемое x_i1,..., x_ik при 2 ≤ k ≤ n. Вместо каждого переменного x_m функции f_L, где m ∉ {i₁, ..., i_k}, подставим константу 0, т.е. заменим нулем все переменные, которые не вошли в выбранную ранее конъюнкцию. Получим "редуцированную" функцию

f'_L = x_i1,..., x_ik ⊕ a_i1x_i1 ⊕ ... ⊕ a_ikx_ik ⊕ a₀ = f_L(0,...,0,)x_i1,0,...,0,x_ik,0,...,0).

Заметим, что коль скоро мы уже представили константы формулами над F, то функция f'_L, тоже представлена формулой над F. Разобьем теперь множество переменных {x_i1,...,x_ik} произвольно на две части: {x_i1,...,x_im} и {x_im+1,...,x_ik}, где 1 ≤ m ≤ k - 1, и заменим все переменные первой части переменным х, а переменные второй части - переменным у. В результате получим функцию от двух переменных

где а = a_i1 ⊕ ... ⊕ a_i1, b = a_im+1⊕ ... ⊕ a_ik, c = а₀,

Ясно также, что функция х может быть представлена такой формулой над F:

т.е. функциях получена из нелинейной функции f_L ∈ F путем подстановки на место ее переменных с номерами i₁, ... , i_m переменного х, на место переменных с номерами i_m+1, ... , i_k - переменного у, а на место всех остальных переменных - константы 0, уже представленной формулой над F (см. выше).

Определим функцию

ψ(х, у) = (х ⊕ b, у ⊕ а) ⊕ аb ⊕ с.

Выразив эту функцию из полинома Жегалкина для , получим

ψ(х, у) = (х ⊕ b, у ⊕ а) ⊕ аb ⊕ с = (x ⊕ b)(y ⊕ a) ⊕ a(x ⊕ b) ⊕ b(y ⊕ a) ⊕ c ⊕ ab ⊕ c = xy ⊕ ax ⊕ by ⊕ ab ⊕ ax ⊕ ab ⊕ by ⊕ ab ⊕ c ⊕ ab ⊕ c = xy,

поскольку сумма по модулю 2 любого четного числа равных слагаемых равна 0. Итак, функция ψ есть конъюнкция. Так как прибавление к любой функции константы по модулю 2 есть либо сама исходная функция, либо ее отрицание, а отрицание уже представлено формулой над базисом F, то тем самым и конъюнкция представлена такой формулой. ▶

Чтобы исследовать полноту конкретного множества функций F = {f₁, f₂, ... , f_n}, нужно построить так называемую критериальную таблицу (табл. 6.6).

Строки таблицы соответствуют функциям исследуемого множества, а столбцы - классам Поста. В результате анализа функций множества F клетки таблицы заполняются: если функция fi принадлежит некоторому классу Поста С, то в соответствующей клетке критериальной таблицы ставится знак "+" (плюс), а если нет, то - знак "-" (минус). Множество F тогда полно, если и только если в каждом столбце таблицы стоит хотя бы один знак "-".

Пример 6.21. а. Пусть F = {~, ∨, 0}. Ниже приведены результаты исследования элементов этого множества на принадлежность к классам Поста, а также заполненная критериальная таблица (табл. 6.7).

При этом 1 = х ~ х, так как функция ~ (эквивалентность) не сохраняет константу 0, но сохраняет константу 1 (т.е. имеет место первый случай из доказательства достаточности условия теоремы Поста). Константа 0 принадлежит самому множеству F. Поскольку x = х ~ 0, то ввиду полноты множества {∨,   } будет полным и рассматривамое множество. Конъюнкцию можно представить формулой над F, следуя доказательтву теоремы Поста. Берем единственную нелинейную функцию данного множества, дизъюнкцию, и записываем для нее полином Жегалкина:

x₁ ∨ x₂ = x₁ ⋅ x₂ ⊕ x₁ ⊕ x₂.

Видно, что этот полином есть не что иное, как функция (х₁,х₂) при а = b = 1 и с = 0. Следовательно,

х₁ · х₂ = (х₁ ⊕ 1, х₂ ⊕ 1) ⊕ 1.

Но так как x = х ~ 0, то х₁ · х₂ = ((х₁ ~ 0) ∨ (х₂ ~ 0)) ~ 0. Этот же результат (в данном конкретном случае) можно получить и гораздо проще:

Итак, исходное множество является полным.

Заметим, что это полное множество двойственно к базису Жегалкина в том смысле, что каждая из его функций двойственна к соответствующей функции базиса Жегалкина: эквивалентность двойственна к сумме по модулю 2, дизъюнкция - к конъюнкции, константа О - к константе 1. Полезно заметить также, что никакое собственное подмножество заданного множества не будет полным.

б. Функция f₁ задана картой Карно (рис. 6.21), а вектор значений функции f₂ есть (0,1,0,0).

Для функции f₂ очень просто находятся ДНФ и полином Жегалкина:

f₂ = x₁x₂ = (x₁ ⊕ 1)x₂ = x₁x₂ ⊕ x₂,

откуда следует нелинейность функции f₂. Легко показать также, что эта функция принадлежит лишь классу Т₀,

Так как f₁(0,0,0,0) = 1, а f₁(1,1,1,1) = 0, то функция f₁ не сохраняет ни константу 0, ни константу 1. Далее, эта функция несамодвойственна, поскольку f₁(0,1,1,1) = f₁(1,0,0,0) = 1; немонотонность ее следует из того, что, например, f₁(0,0,0,0)= 1, но f₁(0,1,0,0) = 0. Вопрос о нелинейности функции f₁ оставим пока открытым, так как даже из частично заполненной критериальной таблицы (табл. 6.8) вытекает, что множество {f₁, f₂} полно.

Формулы для отрицания и констант находятся легко:

x = f₁(x,x,x,x),

0 = f₂(x,x),

1 = f₁(f₂(x,x),f₂(x,x),f₂(x,x),f₂(x,x)).

Формулу для конъюнкции проще всего построить прямо по ДНФ для функции f₂:

x₁ ⋅ x₂ = f₂(x₁,x₂) = f₂(f₂(x₁,x₁,x₁,x₁,),x₂).

Вернемся теперь к отложенному вопросу о нелинейности функции f_i. По приведенной на рис. 6.21 карте Карно можно построить одну из минимальных ДНФ, представляющих эту функцию в виде

f₁ = x₁x₂x₄ v x₁x₃x₄ v x₁x₂x₃ v x₁x₂x₄.

Подставляя в последнюю формулу 0 вместо х₁, х вместо x₂, 1 вместо х₃ и у вместо х₁, получаем

х ⋅ у = f₁(0,x,1,у),

что доказывает нелинейность функции f₁ и одновременно полноту множества {f₁}.

Константы же можно представить формулами над базисом {f₁}, используя несамодвойственность функции f₁ (см. разбор второго случая в доказательстве достаточности условия теоремы Поста): мы уже видели, что f₁(0,1,1,1) = f₁(1,0,0,0) = 1, т.е. набор α˜ из упомянутого места в доказательстве теоремы Поста есть 0111, и тогда функция h, фигурирующая в том же месте доказательства и равная в данном случае константе 1, будет иметь вид

h(x) = f₁(x ,х,х,х).

Но так как x = f₁(x,x,x,x), то получаем

1 = f₁(f₁(x,x,x,x),х,х,х),

0 = f₁(f₁(f₁(x,x,x,x),x,x,x), f₁(f₁(x,x,x,x),x,x,x),

f₁(f₁(х,х,х,х),х,х,х), f₁(f₁(х,х,х,х),х,х,х)).

Подставив эти формулы в написанную выше формулу для конъюнкции, получим окончательно формулу над базисом {f₁} для конъюнкции. Мы не выписываем эту формулу ввиду ее громоздкости.