Булева функция

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

Булевы функции получили своё название по имени английского математика Дж. Буля (02.11.1815–08.12.1864). С давних времён эти функции играют важную роль в вопросах оснований математики и математической логике. С середины 20-го века булевы функции широко используются в различных теоретических и прикладных задачах дискретной математики и математической кибернетики.

↑Задание функций таблицами

Пусть E = {0, 1}, X— некоторое счётное множество переменных, Eⁿ— множество всех наборов (α₁, …,  α_n) из нулей и единиц, n ≥ 1. Пусть  f ⁽ⁿ⁾ — отображение множества Eⁿ в E, n ≥ 1, x₁, …, x_n — переменные из множества X, и пусть функция  f ⁽ⁿ⁾ (x₁, …, x_n) задаёт это отображение, где Eⁿ — область определения, E — область значений, x₁, …, x_n — переменные, от которых зависит f ⁽ⁿ⁾ (x₁, …, x_n). Функция f ⁽ⁿ⁾ (x₁, …, x_n) называется n-местной булевой функцией (или функцией алгебры логики), а f ⁽ⁿ⁾ — n-местным функциональным символом, соответствующим этой функции. Верхние индексы у функциональных символов, как правило, опускаются, однако при этом указывается число переменных, от которых зависят рассматриваемые функции.

Множество всех булевых функций обозначается через P₂. Так как число двоичных наборов длины n конечно (и равно 2ⁿ), то каждая функция f (x₁, …, x_n) из P₂ может быть полностью задана таблицей, в левой части которой выписаны все наборы значений переменных x₁, …, x_n, а в правой части — соответствующие им значения функции. На каждом из 2ⁿ наборов функция f (x₁, …, x_n) может принимать любое из двух значений. Отсюда следует, что число функций алгебры логики от переменных x₁, …, x_n равно 2^{2^n}. Таким образом, с одной стороны, число функций от фиксированного (конечного) множества переменных конечно, а с другой — это число очень быстро растёт с ростом числа переменных.

С теоретико-множественной точки зрения функция алгебры логики f (x₁, …, x_n) — это не просто отображение множества всех наборов длины n из нулей и единиц в множество {0, 1}, а совокупность такого отображения и упорядоченного набора x₁, …, x_n переменных. В этом смысле функции f (x₁, x₂, x₃) и f (x₂, x₁, x₃), вообще говоря, различны, хотя и определяются одним и тем же отображением {0, 1}³ → {0, 1}. В соответствии с этим возникает следующее понятие равенства функций: функции равны, если они зависят от одного и того же множества переменных и задают одно и то же отображение. А именно, булевы функции f ( x₁, …, x_n) и g (x₁, …, x_n) называются равными (обозначение f = g), если f (α₁, …, α_n) = g (α₁, …, α_n) для любого набора (α₁, …, α_n) из нулей и единиц.

Рассмотрим некоторые функции одного и двух аргументов, которые являются в определенном смысле аналогами « элементарных функций» в арифметике, алгебре и математическом анализе.

При n = 1 будет всего 4 функции, указанные в табл.1, где 0 — константа 0, x — тождественная функция, ¬ x — отрицание x, 1 — константа 1.

 

x	0	x	¬ x	1
0	0	0	1	1
0	0	1	0	1

Таблица 1

При n = 2 будет уже 16 функций. Некоторые из них указаны в табл. 2.

x1	x2	x1& x2	x1\/ x2	x1+ x2	x1→ x2	x1/ x2
0	0	0	0	0	1	1
0	1	0	1	1	1	1
1	0	0	1	1	0	1
1	1	1	1	0	1	0

Таблица 2

 

Функция x₁&x₂ называется конъюнкцией x₁ и x₂ или логическим умножением (И), она обозначается также x₁x₂. Функция x₁\/x₂ называется дизъюнкцией x₁ и x₂ или логическим сложением (ИЛИ); x₁+ x₂ называется суммой x₁ и x₂ по модулю 2; (исключающее ИЛИ); x₁→x₂ называется импликацией x₁ и x₂; x₁/ x₂ — это штрих Шеффера.

↑Существенные и несущественные переменные

Переменная x_i функции f (x₁, …, x_n) называется существенной, если существуют такие два набора из нулей и единиц, различающиеся только в i-й компоненте, что функция f на этих наборах принимает различные значения. В этом случае говорят, что функция f (x₁, …, x_n) существенно зависит от переменной x_i. Переменная x_i, не являющаяся существенной, называется несущественной или фиктивной переменной функции f (x₁, …, x_n); в этом случае говорят, что функция f (x₁, …, x_n) не зависит существенно от переменной x_i.

Например, функция f (x₁, x₂) = x₁ x₂ существенно зависит от переменной x₁, так как f (0, 1)  ≠ f (1, 1). Она также существенно зависит от переменной x₂, так как f (1, 0) ≠ f (1, 1). Аналогично показывается, что все функции, приведённые в табл. 2, существенно зависят от обеих переменных. Очевидно, что константы 0 и 1 не имеют существенных переменных.

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

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

↑Формулы. Реализация функций формулами

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

A = { f₁ (x₁, …, x_n1), f₂ (x₁, …, x_n2), … },

 

B — множество функциональных символов, соответствующих функциям из A. Понятие формулы над множеством A определяется индуктивно.

 

1. Выражение x (где x — переменная из множества X) является формулой над A; такие формулы называются тривиальными.
2. Если F₁, …, F_n — формулы над A, а f — функциональный символ из B, то выражение F вида f(F₁,  …, F_n) (то есть функциональный символ, левая скобка, формулы F₁, …, F_n в их порядке, правая скобка), является формулой над A; формулы F₁, …, F_n называются подформулами формулы F. Подформулами формулы F являются также сама формула F и все подформулы формул F₁, …,F_n.

 

Предполагается при этом, что никаких других формул над A не существует, то есть каждая формула над A может быть получена применением конечного числа правил 1 и 2.

Таким образом, формулы над A — это слова определённого вида (конечной длины) в алфавите X U B U V , где V — множество вспомогательных символов, состоящее из символов левой и правой скобок, а также запятой.

Через F(x₁, …, x_n) обозначается такая формула, в которую входят символы переменных x₁, …, x_n и только они.

Каждой формуле сопоставляется некоторая функция алгебры логики. Пусть дана формула F (x₁, …, x_n) над множеством функций A ({x₁, …, x_n} — множество всех переменных этой формулы), и пусть R = (α₁, …, α_n) — некоторый набор значений этих переменных. Значение формулы F (а также значение каждой её подформулы) на наборе переменных R (обозначение F|_R) определяется индуктивно. Если F — тривиальная формула вида x_i, то это значение равно α_i.  Пусть F имеет вид

 

f (F₁,  …, F_m),

 

где функция f(x₁, …, x_m) принадлежит множеству A, а F₁, …, F_m — формулы над A, для которых значения F₁|_R, …, F_m|_R уже определены и равны β₁, …,  β_m соответственно. Тогда  F|_R = f(β₁, …,  β_m).

Так как можно определить значение формулы F (x₁, …, x_n) на любом наборе значений переменных, то тем самым этой формуле сопоставляется некоторая функция f (x₁,  …, x_n) из P₂. Про функцию, сопоставленную указанным выше способом формуле, говорят, что она реализуется или выражается этой формулой. Таким образом, каждая формула выражает какую-то функцию алгебры логики.

Описанный выше способ порождения булевых функций называется операцией суперпозиции. Если функция f реализована некоторой нетривиальной формулой над A, то говорят также, что f получена операцией суперпозиции из функций системы A. Частными случаями операции суперпозиции являются следующие операции над булевыми функциями: перестановка переменных, переименование переменных, отождествление переменных, композиция функций (то есть подстановка функций на места переменных в другие функции). Отметим, что операция введения фиктивной переменной, вообще говоря, не является частным случаем операции суперпозиции.

↑Эквивалентность формул. Примеры эквивалентных формул

Формулы, реализующие равные функции, называются эквивалентными. Рассмотрим множество функций

A = { x₁ & x₂,  x₁ \/ x₂ , x₁ + x₂, ¬ x, 0, 1 },

Приведём несколько важных примеров эквивалентных формул над A. В этих примерах  для сокращения записи используются следующие соглашения: внешние скобки опускаются, а переменные и константы в скобки не заключаются.

1.Коммутативность операций &, \/, + :

 

x₁ & x₂ = x₂ & x₁,   x₁ \/ x₂ = x₂ \/ x₁,   x₁ + x₂ = x₂ + x₁.

 

2.Ассоциативность операций &, \/, + :

 

x₁ & ( x₂ & x₃ ) = ( x₁ & x₂) & x₃ ,

 

x₁ \/ ( x₂ \/ x₃ ) = ( x₁ \/ x₂ )  \/ x₃ ,

 

x₁ + ( x₂ + x₃ ) = ( x₁ + x₂ ) + x₃ .

 

3.Дистрибутивность:

( x₁ \/  x₂ ) & x₃  = ( x₁ &  x₃  ) \/ ( x₂ &  x₃  ),

 

( x₁ + x₂ ) & x₃  = ( x₁ & x₃  ) + ( x₂ & x₃  ),

 

( x₁ & x₂ ) \/ x₃  = ( x₁ \/  x₃  ) & ( x₂ \/ x₃  ).

 

4.Закон поглощения:

 

x₁ & ( x₁ \/ x₂ ) = x₁,     x₁ \/ ( x₁ & x₂ ) = x₁.

 

5.Идемпотентность конъюнкции и дизъюнкции:

 

x & x = x,    x \/ x = x.

 

6.Перенос отрицания через конъюнкцию и дизъюнкцию:

 

¬( x₁ & x₂ ) = ¬ x₁  \/ ¬ x₂,

 

¬( x₁ \/ x₂ ) = ¬ x₁  & ¬ x₂.

 

7.«Снятие» двойного отрицания:

 

¬ ¬ x = x.

 

8.Некоторые эквивалентности с использованием отрицания и суммы по модулю 2:

x & ¬ x = 0,   x \/ ¬ x = 1,

 

x + ¬ x = 1,    x + x = 0,

 

9.Операции с константами:

x & 1 = x,  x & 0 = 0,

 

x \/ 1 = 1,   x \/ 0 = x,

 

x + 1 = ¬ x,  x + 0 = x. 

Эти равенства проверяются путём вычисления значений функций в левой и правой части соотношений на каждом наборе значений переменных. Из этих правил выводятся некоторые производные правила. А именно, в дизъюнкции из нескольких членов можно произвольным образом их переставлять; аналогично для операций конъюнкции и суммы по модулю 2. Это позволяет ввести дальнейшие соглашения, упрощающие вид формул: в формулах, получающихся многократным применением одной из операций \/, &, + к более простым формулам, скобки опускаются..

↑Стандартные представления

Введём функцию x^δ следующим образом. Положим x^δ = x, если δ = 1, и x^δ = ¬ x, если δ = 0. Каждую булеву функцию f (x₁, …, x_n) можно представить в виде

f (x₁, …, x_m) = V x^β1₁ & … & x^βn_n,

где дизъюнкция берётся по всем наборам (β₁, …,  β_n) из нулей и единиц, таким, что выполняется равенство f (β₁, …, β_n) = 1. Это выражение является формулой над множеством {&,  \/ , ¬ }. Такое представление функции f называется совершенной дизъюнктивной нормальной формой (или СДНФ).

Таким образом, каждую булеву функцию можно выразить в виде формулы над множеством {&,  \/ , ¬ }. Функция, равная константе 0 (то есть принимающая значение 0 на любом наборе значений переменных), не имеет представления в виде СДНФ (можно также по определению считать, что эта функция представляется пустой СДНФ, не содержащей конъюнкций).

Аналогичным образом определяется совершенная конъюнктивная нормальная форма (СКНФ) — представление функции f (x₁, …, x_n) в виде

f (x₁, …, x_m) = & (x^β1₁ \/ … \/x^βn_n),

где конъюнкция берётся по всем наборам (¬ β₁, …,  ¬ β_n) из нулей и единиц, таким, что выполняется равенство f (β₁, …,  β_n) = 0.

 Каждую булеву функцию можно представить также в виде полинома. Рассматриваются конъюнкции вида x_i1,  …, x_is, где все i₁, …, i_s различны, s ≥ 1. При s = 1 получаются конъюнкции длины 1, то есть переменные. Константа 1 также называется конъюнкцией длины 0 (от пустого множества переменных). Полиномом Жегалкина называется сумма по модулю 2 попарно различных конъюнкций. Пустой полином (то есть не содержащий конъюнкций) по определению выражает константу 0. Таким образом, полином Жегалкина — это выражение вида

∑ x_i1 & … & x_is,

где суммирование происходит по различным подмножествам {i₁, …, i_s} множества {1, …, n}. Имеет место следующее утверждение: любая булева функция представима в виде полинома Жегалкина, причём это представление единственно с точностью до перестановки слагаемых и до перестановки множителей в слагаемых.

↑Примеры полных систем

Система функций A называется полной, если любая функция алгебры логики выражается формулой над A. Из приведённого выше представления в виде СДНФ следует, что система {&,  \/ , ¬ } является полной. Примеры других полных систем могут быть найдены с использованием следующего простого утверждения (которое называется достаточным условием полноты): если A и D — системы булевых функций, такие, что A является полной и любая функция из A выражается некоторой формулой над D, то D — полная система.

Используя это утверждение, можно показать, что системы {1,  \/ , + }, {1, &, + }, { \/ , ¬ }, {&,  ¬ }, {0, → }, { / } являются полными.

↑Замыкание множества функций. Замкнутые классы

Замыканием множества A (относительно операции суперпозиции) называется множество всех функций, которые могут быть получены из функций системы A применением операции суперпозиции (иными словами, могут быть реализованы нетривиальными формулами над A). Замыкание множества A обозначается через [A]. Из приведённого выше определения понятия равенства функций следует, что множеству [A] принадлежат также и все функции, которые отличаются от функций, реализуемых нетривиальными формулами над A, лишь фиктивными переменными. Таким образом, фактически замыкание систем функций рассматривается относительно двух операций: суперпозиции и введения фиктивной переменной.

Множество булевых функций A называется замкнутым (относительно операции суперпозиции), если A = [A]. Замкнутые множества функций называются также замкнутыми классами.

Операция замыкания обладает следующими свойствами. Пусть A и D — произвольные системы булевых функций. Тогда выполняются соотношения

1.  A содержится в [A].
2. Если A содержится в D, то [A] содержится в [D].
3. [[A]] = [A].
4. [A] ∩ [D] — замкнутое множество.
5. Если A — полная система, то выполняется равенство [A] = P₂.

↑Примеры замкнутых классов

Определяются следующие свойства функций алгебры логики. Говорят, что функция f (x₁, …, x_n) сохраняет константу 0 (соответственно 1), если выполняется равенство f (0, …, 0) = 0 (соответственно f (1, …, 1) = 1). Функция f (x₁, …, x_n) называется монотонной, если для любых двух наборов (α₁, …,  α_n) и (β₁, …,  β_n) из Eⁿ, таких, что α₁   ≤  β₁,  …,  α_n   ≤  β_n , выполняется неравенство

f (α₁, …,  α_n) ≤ f (β₁, …, β_n);

функция f (x₁, …, x_n) называется самодвойственной, если для любого набора (α₁, …, α_n) из Eⁿ выполняется равенство

¬ f (¬ α₁, …, ¬  α_n) = f (α₁, …,  α_n);

функция f (x₁, …, x_n) называется линейной, если имеет место представление

f (x₁, …, x_n) = c₀  + c₁ x₁ + … +  c_n x_n,

где c₀ , c_{1 ,} …, c_n  принадлежат множеству  {0, 1} (то есть если в представлении этой функции в виде полинома Жегалкина содержатся только линейные члены).

Выделяются следующие множества булевых функций: T₀ — множество всех функций, сохраняющих константу 0, T₁ — множество всех функций, сохраняющих константу 1, M — множество всех монотонных функций, S — множество всех самодвойственных функций, L — множество всех линейных функций.

Из определения следует, что множества T₀, T₁, M, S и L являются замкнутыми классами, причём ни один из этих классов не содержится в другом.

↑Критерий полноты. Предполные классы

Имеет место следующий критерий функциональной полноты систем булевых функций: система A функций алгебры логики полна тогда и только тогда, когда она целиком не содержится ни в одном из классов T₀ , T₁, M, S и L.

Из этого критерия следует, что из любой полной системы можно выделить полную подсистему, состоящую не более чем из пяти функций; кроме того, следует, что каждый замкнутый класс F булевых функций, такой, что F ≠  P₂, содержится в одном из пяти классов T₀ , T₁, M, S и L.

Пусть F и G — замкнутые классы булевых функций, такие, что F содержится в G. Класс F называется предполным в G, если F ≠ G и для любой функции f из множества G \ F система G U {f} является полной в G. В P₂ существует только пять предполных классов: T₀, T₁, M, S и L.

↑Формулировка основных теорем Э. Поста

Замкнутые классы булевых функций были описаны американским математиком Э. Л.  Постом в 1920 году. Он изучил ряд важных свойств этих классов. Основные результаты Поста формулируются следующим образом.

Пусть F — произвольный замкнутый класс булевых функций, а A — некоторая система функций, содержащихся в F. Говорят, что система A порождает замкнутый класс F, если [A] = F. В этом случае говорят также, что система A является полной в F. Базисом класса F называется такая порождающая F система A, любая собственная подсистема которой не порождает F. Справедливы следующие два принадлежащих Э. Посту утверждения: множество всех замкнутых классов функций алгебры логики имеет счётную мощность; каждый замкнутый класс булевых функций имеет конечный базис.

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

↑Рекомендуемая литература

1. Конспект лекций О.Б. Лупанова по курсу «Введение в математическую логику» / Отв. ред. А. Б. Угольников. — М.: Изд-во ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова, 2007. — 192 c.

2. Яблонский С. В. Введение в дискретную математику. — М.: Высшая школа, 2008. — 384 с.

3. Post E.L. Introduction to a general theory of elementary propositions (Doctoral dissertation, Columbia University, 1920)// Amer. J. Math. — 1921. — 43, № 3, July. — P. 163–85. [Reprinted in: Solvability, provability, definability: the collected works of Emil L. Post // Martin Davis editor. Boston, Basel, Berlin: Birkhauser, 1994. — P. 21–43.].

4. Post E. L. Two-valued iterative systems of mathematical logic // Ann. Math. Stud. Princeton; London: Princeton Univ. Press, 1941. — № 5. — 122 р. [Reprinted in: ibid. — P. — 249–374.].

5. Яблонский С. В., Гаврилов Г . П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966. — 120 с.

6. Угольников А. Б. Классы Поста. — М.: Изд-во ЦПИ при механико-математическом факультете МГУ им. М. В. Ломоносова, 2008. — 64 с.