Булевы функции от одного и двух аргументов

Булевы функции получили свое название по имени замечательного английского математика Джорджа Буля (1815—1864), который первым начал применять математические методы в логике.

Происхождение булевых функций

В конце первой лекции отмечалось, что каждое из определений операций над высказываниями: отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности, — можно рассматривать как определение некоторого действия над символами 0 и 1, т. е. как определение некоторой функции, заданной на двухэлементном множестве $\{0;1\}$ и принимающей значения в том же множестве. Символом 0 обозначалось любое ложное высказывание, а символом 1 — любое истинное. Например, отрицание представляет собой в этом смысле функцию одного аргумента $f_2(x)$ , которая принимает следующие значения: $f_2(0)=1,~ f_2(1)=0$ ; конъюнкция представляет собой функцию двух аргументов $g_1(x,y)$ , принимающую следующие значения:

$g_1(0;0)=0,~~ g_1(0;1)=0,~~ g_1(1;0)=0,~~ g_1(1;1)=1$ и т.д.

Во второй лекции эта мысль была развита дальше: отмечено, что каждая формула алгебры высказываний $F(X_1,X_2,\ldots,X_n)$ от $n$ пропозициональных переменных $X_1,X_2,\ldots,X_n$ определяет по существу некоторую функцию от $n$ аргументов, сопоставляющую любому набору длины $n$ , составленному из элементов двухэлементного множества $\{0;1\}$ , единственный элемент того же множества. Этот элемент является логическим значением того составного высказывания, в которое превращается данная формула, если вместо всех ее пропозициональных переменных подставить конкретные высказывания, имеющие соответствующие значения истинности. Легко понять, что высказывания (точнее, их содержание) здесь ни при чем. Функция, о которой идет речь, определяется структурой формулы $А$ и определениями отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности, которые понимаются как определения действий над символами 0, 1 — элементами двухэлементного множества $\{0;1\}$ .

В связи с этим естественно рассмотреть функции, заданные на двухэлементном множестве $\{0;1\}$ и принимающие значения в нем же безотносительно к формулам алгебры высказываний, т.е. сами по себе. Тогда функции, определяемые таблицами в определениях отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности, а также функции, определяемые формулами алгебры высказываний, будут служить примерами таких функций. Такие функции, заданные и принимающие значения в двухэлементном множестве, появляющиеся в алгебре высказываний, носят название функций алгебры логики или булевых функций.

Введя понятие булевой функции, мы окончательно отрываемся от того содержательного смысла, который имели в виду в алгебре высказываний: пропозициональные переменные служили там обозначениями для высказываний языка. Теперь же остались только два символа 0 и 1 и понятие булевой функции. Чтобы еще более оттенить это обстоятельство, обозначим переменные, пробегающие множество $\{0;1\}$ , малыми буквами латинского алфавита $x,y,z,u,v,\ldots, x_1,x_2, \ldots, x_n,\ldots$ и будем называть их булевыми.

В этой лекции изучим некоторые свойства булевых функций и посмотрим, как эти функции могут применяться в алгебре высказываний и в теории релейно-контактных схем.

Булевы функции от одного аргумента

Определение 9.1. Булевой функцией от одного аргумента называется функция $f$ , заданная на множестве из двух элементов и принимающая значения в том же двухэлементном множестве.

Элементы двухэлементного множества будем обозначать 0 и 1. Таким образом, $f\colon \{0;1\}\to\{0;1\}$ . Нетрудно перечислить все булевы функции от одного аргумента:

$\begin{array}{|c||c|c|c|c|}\hline x& f_0(x)& f_1(x)& f_2(x)& f_3(x)\\\hline 0&0&0&1&1\\ 1&0&1&0&1\\\hline \end{array}$

Составленная таблица означает, что, например, булева функция $f_2$ на аргументах 0 и 1 действует следующим образом: $f_2(0)=1$ и $f_2(1)=0$ . Всего имеется четыре различных булевых функций от одного аргумента:

$f_0(x)=0$ — функция, тождественно равная 0 (тождественный нуль);
$f_1(x)=x$ — тождественная функция;
$f_2(x)=x'$ — функция, называемая отрицанием;
$f_3(x)=1$ — функция, тождественно равная 1 (тождественная единица).

Булевы функции от двух аргументов

Определение 9.2. Булевой функцией от двух аргументов называется функция $g$ , заданная на множестве $\{0;1\}\times\{0;1\}$ и принимающая значения в двухэлементном множестве $\{0;1\}$ . Другими словами, булева функция от двух аргументов сопоставляет любой упорядоченной паре, составленной из элементов 0 и 1 (а таких упорядоченных пар будет четыре), либо 0, либо 1.

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

$\begin{array}{|c|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline \phantom{y} \begin{matrix}{}\\[-9pt]{} \end{matrix} & {} & 0 & \cdot & \to' & x & \leftarrow' & y & + & \lor & \downarrow & \leftrightarrow & y' & \leftarrow & x' & \to& \vert & 1\\\hline \begin{matrix}{} \\[-10pt] {} \end{matrix} x& y& g_{{}_0}& g_{{}_1}& g_{{}_2}& g_{{}_3}& g_{{}_4}& g_{{}_5}& g_{{}_6}& g_{{}_7}& g_{{}_8}& g_{{}_9}& g_{{}_{10}}& g_{{}_{11}}& g_{{}_{12}}& g_{{}_{13}}& g_{{}_{14}}& g_{{}_{15}}\\\hline \begin{matrix}{} \\[-6pt] {} \end{matrix} 0&0& 0&0&0&0&0&0&0&0 &1&1&1&1&1&1&1&1\\[-3pt] 0&1& 0&0&0&0& 1&1&1&1& 0&0&0&0& 1&1&1&1\\[1pt] 1&0& 0&0& 1&1& 0&0& 1&1& 0&0& 1&1& 0&0& 1&1\\[1pt] 1&1& 0&1& 0&1& 0&1& 0&1& 0&1& 0&1& 0&1& 0&1\\\hline \end{array}$

Заметим: функции пронумерованы так, что номер функции, записанный в двоичной системе счисления, дает последовательность значений соответствующей функции. Например, двоичная запись числа 13 имеет вид: 1101. Соответствующая функция $g_{{}_{13}}(x,y)$ принимает следующие значения:

$g_{13}(0;0)=1,\qquad g_{13}(0;1)=1,\qquad g_{13}(1,0)=0,\qquad g_{13}(1,1)=1.$

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

Первые две функции, которые рассматриваются, $g_0(x,y)=0$ и $g_{{}_{15}}(x,y)=1$ — тождественный ноль и тождественная единица.

Далее, функция $g_{1}(x,y)$ называется конъюнкцией и обозначается $x\cdot y$ (или $xy$ ). Таким образом, $g_{1}(x,y)=x\cdot y$ . Конъюнкция принимает значение 1 в том и только в том случае, когда оба ее аргумента принимают значение 1. Отрицание конъюнкции, функция $g_{14}(x,y)$ , называется штрихом Шеффера и обозначается $x\mid y$ . Таким образом, $g_{14}(x,y)=(x\cdot y)'=x\mid y$ . Эта функция принимает значение 0 в том и только в том случае, когда функция $g_{1}(x,y)$ принимает значение 1, т.е. в случае, когда оба ее аргумента принимают значение 1.

Функция $g_{7}(x,y)$ называется дизъюнкцией и обозначается $x\lor y$ . Таким образом, $g_{7}(x,y)= x\lor y$ . Функция $g_{8}(x,y)$ , являющаяся отрицанием функции $g_{7}(x,y)$ , носит название стрелка Пирса (или функция Вебба) и обозначается $x\downarrow y$ . Итак, $g_{8}(x,y)=(x\lor y)'=x\downarrow y$ .

Функция $g_{13}(x,y)$ называется импликацией и обозначается $x\to y$ , т.е $g_{13}(x,y)=x\to y$ . Аргумент $x$ в этой функции называется посылкой импликации, а аргумент $y$ — ее следствием. Отрицанием импликации является функция $g_{2}(x,y)=(x\to y)'$ . Специального названия она не имеет.

Функция $g_{11}(x,y)$ называется антиимпликацией или обратной импликацией, потому что представляет собой импликацию с посылкой $y$ и следствием $x$ . Таким образом, $g_{11}(x,y)=y\to x$ . Ее отрицанием является функция $g_{4}(x,y)=(y\yo x)'$ , не имеющая названия.

Функция $g_{9}(x,y)$ называется эквивалентностью и обозначается $x\leftrightarrow y$ , так что $g_{9}(x,y)=x\leftrightarrow y$ . Она принимает значение 1 тогда и только тогда, когда оба ее аргумента принимают одинаковые значения. Функция $g_{6}(x,y)$ , являющаяся отрицанием функции $g_{9}(x,y)$ , называется сложением по модулю два, или суммой Жегалкина, и обозначается $x+y$ .

Наконец остаются еще две пары функций. В первую пару входят функции $g_{3}(x,y)$ и $g_{12}(x,y)$ . Первая из них принимает всегда те же самые значения, что и ее первый аргумент, т.е. $g_{3}(x,y)=x$ , а вторая функция является отрицанием первой: $g_{12}(x,y)=x'$ . Во вторую пару входят функции $g_{5}(x,y)$ и $g_{10}(x,y)$ . Первая из них принимает всегда те же самые значения, что и ее второй аргумент, т.е. $g_{5}(x,y)=y$ , а вторая функция является отрицанием первой: $g_{10}(x,y)=y'$ .

Теперь установим некоторые важнейшие свойства введенных функций. Две булевы функции $f(x,y)$ и $g(x,y)$ называются равными, если каждому набору значений аргументов $x,y$ обе функции сопоставляют один и тот же элемент из множества $\{0;1\}$ , т.е. $f(a,b)=g(a,b)$ для любых $a,b\in\{0;1\}$ . Например, $x\lor y=y\lor x$ .

Из введенных простейших булевых функций можно строить с помощью суперпозиций более сложные булевы функции. Например, если в функцию $x\lor t$ вставить вместо аргумента $t$ функцию $y\cdot z$ , то получим следующую сложную функцию: $x\lor(y\cdot z)$ . Если в нее в свою очередь вставить вместо аргумента $z$ функцию $u\to v$ , то получим сложную функцию $x\lor (y\cdot (u\to v))$ . И так далее. В результате получаются булевы функции от трех, четырех и большего числа аргументов.