Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


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


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


[math]g_1(0;0)=0,~~ g_1(0;1)=0,~~ g_1(1;0)=0,~~ g_1(1;1)=1[/math] и т.д.

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


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


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


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




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


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


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


[math]\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}[/math]

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


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



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


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


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


[math]\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}[/math]

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


[math]g_{13}(0;0)=1,\qquad g_{13}(0;1)=1,\qquad g_{13}(1,0)=0,\qquad g_{13}(1,1)=1.[/math]

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


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


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


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


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


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


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


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


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


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


В следующих теоремах устанавливаются некоторые равенства одних булевых функций другим, выражающие свойства основных булевых функций.




Свойства дизъюнкции, конъюнкции и отрицания


Теорема 9.3. Для булевых функций выполняются следующие равенства:


а) [math]x\lor x=x,~ x\cdot x=x[/math] (идемпотентность дизъюнкции и конъюнкции);
б) [math]x\lor y=y\lor x,~ x\cdot y=y\cdot x[/math] (коммутативность дизъюнкции и конъюнкции);
в) [math](x\lor y)\lor z=x\lor (y\lor z),~ (x\cdot y)\cdot z=x\cdot (y\cdot z)[/math] (ассоциативность дизъюнкции и конъюнкции);
г) [math]x\lor1=1,~ x\cdot1=x[/math];
д) [math]x\lor 0=x,~ x\cdot 0=0[/math];
е) [math]x\lor (y\cdot z)= (x\lor y)\cdot (x\lor z),~ x\cdot (y\lor z)= (x\cdot y)\lor (x\cdot z)[/math] (дистрибутивность дизъюнкции относительно конъюнкции и дистрибутивность конъюнкции относительно дизъюнкции);
ж) [math]x\lor (y\cdot x)=x,~ x\cdot (y\lor x)=x[/math] (законы поглощения);
з) [math](x\lor y)'= x'\cdot y',~ (x\cdot y)'=x'\lor y'[/math] (законы де Моргана);
и) [math]x\lor x'=1,~ x\cdot x'=0[/math];
к) [math]x''=x[/math].

Доказательство. а) Свойство идемпотентности дизъюнкции и конъюнкции означает, что применение как одной из них, так и другой к двум одинаковым элементам дает этот же самый элемент. Доказательства данных равенств вытекают непосредственно из таблиц, определяющих дизъюнкцию и конъюнкцию. В самом деле, для дизъюнкции [math]0\lor 0=0,~ 1\lor 1=1[/math] и для конъюнкции [math]0\cdot 0=0,~ 1\cdot 1=1[/math].


б) Коммутативность (перестановочность) дизъюнкции означает, что значение функции не зависит от порядка ее аргументов. Это действительно так, потому что, согласно определению дизъюнкции, она принимает значение 1 тогда и только тогда, когда хотя бы один из ее аргументов (не имеет значения, какой именно) принимает значение 1, и принимает значение 0 тогда и только тогда, когда оба аргумента равны 0. Аналогична ситуация и с конъюнкцией.


в) Вместо слова "ассоциативность" используется также термин "сочетательность". Докажем ассоциативность конъюнкции с помощью таблиц. Такой способ важен тем, что он может быть применен для доказательства (или опровержения) равенства между любыми двумя булевыми функциями. Итак, составляем последовательно таблицы значений булевых функций, суперпозиция которых дает левую часть тождества ассоциативности, а затем булевых функций, суперпозиция которых дает его правую часть, придавая всевозможные значения аргументам, [math]x,y,z:[/math]


[math]\begin{array}{|c|c|c||c|c|c|c|}\hline x& y& z& x\cdot y& (x\cdot y)\cdot z& y\cdot z& x\cdot (y\cdot z)\\\hline 0&0&0&0&0&0&0\\ 0&0&1&0&0&0&0\\ 0&1&0&0&0&0&0\\ 0&1&1&0&0&1&0\\ 1&0&0&0&0&0&0\\ 1&0&1&0&0&0&0\\ 1&1&0&1&0&0&0\\ 1&1&1&1&1&1&1\\\hline \end{array}[/math]

Сравнивая пятый и седьмой столбцы таблицы, видим, что они одинаковы, т.е. функции, стоящие в левой и правой частях Доказываемого равенства, принимают одинаковые значения при одинаковых наборах значений аргументов. А это означает, что функции [math](x\cdot y)\cdot z[/math] и [math]x\cdot (y\cdot z)[/math] действительно равны.


Составлением аналогичных таблиц может быть доказана и ассоциативность дизъюнкции. [math]A[/math]ссоциативность означает, что при многократном применении дизъюнкции или конъюнкции результат не будет зависеть от последовательности их применения, и потому все скобки, обозначающие эту последовательность, могут быть опущены. Так, будем писать [math]x\cdot y\cdot z[/math] вместо [math](x\cdot y)\cdot z[/math], а также вместо [math]x\cdot (y\cdot z)[/math], или — [math]x\lor y\lor z[/math] вместо [math](x\lor y)\lor z[/math] и вместо [math]x\lor (y\lor z)[/math]. Точно так же будем писать [math]x\cdot y\cdot z\cdot t[/math] вместо каждой из следующих равных между собой булевых функций:


[math]\bigl((x\cdot y)\cdot z\bigr)\cdot t= \bigl(x\cdot (y\cdot z)\bigr)\cdot t= x\cdot \bigl(y\cdot (z\cdot t)\bigr)= x\cdot \bigl((y\cdot z)\cdot t\bigr)= (x\cdot y)\cdot (z\cdot t).[/math]

Аналогичным образом будет использоваться запись [math]x\lor y\lor z\lor t[/math] и т.д.


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


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


е) Для доказательства этих равенств можно воспользоваться рассмотренным выше методом таблиц, но можно использовать и ранее доказанные соотношения. Проверим, например, первое равенство. При [math]x=1[/math] его левая часть в силу свойств г) и б) равна [math]1\lor (y\cdot z)=1[/math], а правая, в силу тех же свойств, равна [math](1\lor y)\cdot (1\lor z)=1\cdot1=1[/math]. Если же [math]x=0[/math], то левая часть доказываемого равенства становится, в силу свойств д) и б), равной [math]0\lor (y\cdot z)=y\cdot z[/math]; но тому же самому становится равной и правая часть: [math](0\lor y)\cdot (0\lor z)=y\cdot z[/math]. Следовательно, функции [math]x\lor (y\cdot z)[/math] и [math](x\lor y)\cdot (x\lor z)[/math] при одинаковых значениях аргументов дают равные значения, т. е. они равны.


Совершенно аналогичным путем можно доказать и второе тождество дистрибутивности. [math]B[/math]место слова "дистрибутивность" иногда употребляется термин "распределительность". Отметим, что в обычной арифметике умножение дистрибутивно (распределительно) относительно сложения: [math]x\cdot (y+z)= x\cdot y+x\cdot z[/math], но сложение, конечно, не дистрибутивно относительно умножения: [math]x+(y\cdot z)\ne (x+y)\cdot (x+z)[/math]. Для булевых операций (функций) не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.


ж) Снова при доказательстве можем пользоваться уже установленными свойствами. В самом деле, при [math]y=0[/math] левая часть первого равенства превращается в [math]x\lor (0\cdot x)= x\lor 0=x[/math], т. е. равна правой.


Если же [math]y=1[/math], то левая часть рассматриваемого соотношения равна [math]x\lor (1\cdot x)= x\lor x=x[/math], т. е. снова равна его правой части. Следовательно, первое равенство доказано. Аналогично проверяется второе равенство.


з) Для доказательства второго равенства положим сначала, что [math]x=0[/math]. Тогда его левая часть будет равна [math](0\cdot y)'=0'=1[/math], а правая — [math]0'\lor y'=1\lor y'=1[/math]. Если же [math]x=1[/math], то левая часть доказываемого тождества превратится в [math](1\cdot y)'=y'[/math], а его правая часть — в [math]1'\lor y'=0\lor y'=y'[/math]. Следовательно, равенство выполняется. Аналогично проверяется первое равенство.


и) Если [math]x=1[/math], то [math]1\lor1'=1[/math]. Если [math]x=0[/math], то [math]0\lor0'=0\lor1=1[/math]. Таким образом, первое равенство справедливо. Аналогично проверяется второе равенство.


к) Если [math]x=1[/math], то [math]1''=(1')'=0'=1[/math]. Если [math]x=0[/math], то [math]0''=(0')'=1'=0[/math]. Следовательно, [math]x''=x[/math].


Теорема полностью доказана.




Свойства эквивалентности, импликации и отрицания


Свойства эквивалентности и импликации только частично аналогичны свойствам дизъюнкции или конъюнкции.


Теорема 9.4. Для булевых функций справедливы следующие равенства:


а) [math]x \leftrightarrow x=1,~ x \leftrightarrow x'=0[/math];
б) [math]x \leftrightarrow y= y \leftrightarrow x[/math] (коммутативность эквивалентности);
в) [math](x\leftrightarrow y) \leftrightarrow z = x \leftrightarrow (y \leftrightarrow z)[/math] (ассоциативность эквивалентности);
г) [math]1 \leftrightarrow x,~ 0 \leftrightarrow x=x'[/math];
д) [math]x' \leftrightarrow y'= x \leftrightarrow y[/math];
е) [math]x'\to y'=y\to x[/math];
ж) [math]x\to x=1[/math];
з) [math]x\to x'=x'[/math];
и) [math]x'\to x=x[/math];
к) [math]1\to x=x[/math];
л) [math]0\to x=1[/math];
м) [math]x\to 1=1[/math];
н) [math]x\to 0=x'[/math].

Доказательство этих соотношений не представляет труда. Предлагается проделать их самостоятельно с помощью таблиц.


Заметим, что импликация не обладает ни свойством коммутативности, ни свойством ассоциативности. Предлагается самостоятельно исследовать вопрос о том, будут ли эквивалентность и импликация дистрибутивны (распределительны) одна относительно другой справа и слева.




Выражение одних булевых функций через другие


О взаимозависимостях булевых функций возникает много вопросов. Как выражаются одни булевы функции в виде суперпозиций других булевых функций? Можно ли все булевы функции выразить через какие-то одни и те же функции? Существует ли такая булева функция, через которую выражаются все остальные? И так далее. В следующей теореме приводятся основные выражения одних булевых функций через другие, которые можно использовать при получении новых зависимостей между булевыми функциями.


Теорема 9.5. Справедливы следующие равенства, выражающие одни булевы функции через другие:


а) [math]x\cdot y=(x'\lor y')[/math];
в) [math]x\lor y=(x'\cdot y')[/math];
г) [math]x\lor y=(x\to y)\to y[/math];
д) [math]x\lor y=x'\to y[/math];
е) [math]x\to y=x'\lor y[/math];
ж) [math]x'=x\mid x[/math];
з) [math]x\mid y=(x\cdot y)'[/math];
и) [math]x\lor y=x'\mid y'=(x\mid x)\mid (y\mid y)[/math];
к) [math]x'=x\downarrow x[/math];
л) [math]x\downarrow y=(x\lor y)'[/math];
м) [math]x\cdot y=x'\downarrow y'= (x\downarrow x)\downarrow (y\downarrow y)[/math].

Доказательство. Для а) и б) доказательства равенств легко следуют из законов де Моргана (теорема 9.3, пункт з), если на обе части каждого из них "навесить" знак отрицания, а затем к левым частям полученных равенств применить равенство из теоремы 9.3, пункт к.


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


[math]\begin{aligned}(x\to y)\to y &= (x'\lor y)\to y= (x'\lor y)'\lor y= (x''\cdot y')\lor y= (x\cdot y')\lor y=\\ &= (x\lor y)\cdot (y'\lor y)= (x\lor y)\cdot 1= x\lor y.\end{aligned}[/math]

При доказательстве были использованы, кроме того, соотношения теоремы 9.3, з, к, е, и, г.


д) Равенство легко проверяется с помощью таблиц.
ё) Докажите, построив таблицы.
ж) и к) Соотношения непосредственно видны из таблиц, определяющих функции штрих Шеффера и стрелку Пирса.
з) и л) Равенства уже отмечались при определении функций штрих Шеффера и стрелка Пирса.
и) Можно составить таблицы, а можно рассуждать следующим образом: [math]x'\mid y'=(x'\cdot y')'=x\lor y[/math]. [math]B[/math] первом равенстве использовано предыдущее соотношение з).
м) Докажите равенство подобно тому как было доказано равенство и), используя при этом соотношение л).

Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved