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

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

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

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

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


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

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


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


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


Булева функция [math]f[/math] от [math]n[/math] аргументов [math]x_1,x_2,\ldots,x_n[/math] обозначается так: [math]f(x_1,x_2,\ldots,x_n)[/math].


Две булевы функции от [math]n[/math] аргументов [math]f(x_1,x_2,\ldots,x_n)[/math] и [math]g(x_1,x_2,\ldots,x_n)[/math] называются равными, если любым одинаковым наборам значений аргументов [math]x_1,x_2,\ldots,x_n[/math] обе эти функции сопоставляют одинаковые элементы из множества [math]\{0;1\}[/math], т.е. [math]f(a_1,a_2,\ldots,a_n)=g(a_1,a_2,\ldots,a_n)[/math] для любых элементов [math]a_1,a_2,\ldots,a_n\in\{0;1\}[/math].


Ранее уже встречались булевы функции от трех аргументов, например


[math]\begin{array}{ll}f_1(x_1,x_2,x_3)= (x_1\lor x_2)\lor x_3, &\quad f_2(x_1,x_2,x_3)= x_1\lor (x_2\lor x_3),\\[2pt] g_1(x_1,x_2,x_3)= x_1\lor (x_2\cdot x_3), &\quad g_2(x_1,x_2,x_3)= (x_1\lor x_2)\cdot (x_1\lor x_3).\end{array}[/math]

В частности, было показано, что [math]f_1(x_1,x_2,x_3)= f_2(x_1,x_2,x_3)[/math] и [math]g_1(x_1,x_2,x_3)= g_2(x_1,x_2,x_3)[/math]. Перечисленные функции построены с помощью суперпозиций (или последовательного применения) более простых функций.




Суперпозиция булевых функций


Определение 10.2. Суперпозицией булевых функций [math]g_1(y_1^1,y_1^2,\ldots,y_1^{m_1}),\ldots, g_n(y_n^1,y_n^2,\ldots,y_n^{m_n})[/math] в булеву функцию [math]f(x_1,x_2,\ldots,x_n)[/math] называется новая булева функция, получающаяся из функции [math]f(x_1,x_2,\ldots,x_n)[/math] подстановкой вместо (всех или некоторых) аргументов [math]x_1,x_2,\ldots,x_n[/math] функций [math]g_1,g_2,\ldots,g_n[/math] соответственно [math]f\bigl(g_1(y_1^1,\ldots,y_1^{m_1}),\ldots, g_n(y_n^1,\ldots,y_n^{m_n})\bigr)[/math]. Полученная функция [math]F\bigl(y_1^1,\ldots,y_1^{m_1},\ldots, y_n^1,\ldots,y_n^{m_n}\bigr)[/math] зависит от [math]m_1+m_2+\ldots+m_n[/math] аргументов.


Например, если [math]f(u,x_3)= u\lor x[/math] и [math]h_1(x_1,x_2)= x_1\lor x_2[/math], то


[math]F_1(x_1,x_2,x_3)= f\bigl(h_1(x_1,x_2),x_3\bigr)= (x_1\lor x_3)\lor x_3\,.[/math]

Или если [math]g(u,v)= u\cdot v,~ h_2(x_1,x_2)= x_1\lor x_2[/math] и [math]h_3(x_1,x_3)= x_1\lor x_3[/math], то имеем


[math]F_2(x_1,x_2,x_3)= g\bigl(h_2(x_1,x_2), h_3(x_1,x_3)\bigr)= (x_1\lor x_2)\cdot (x_1\lor x_3).[/math]

Опишем еще одну процедуру, которую можно проделывать с булевыми функциями. Зафиксировав один из аргументов булевой функции [math]f(x_1,x_2,\ldots,x_n)[/math] от [math]n[/math] аргументов, т.е. придав этому аргументу какое-нибудь конкретное постоянное значение (из двухэлементного множества [math]\{0;1\}[/math]), получим функцию от [math]n-1[/math] аргументов. Так, фиксируя в функции [math]f(x_1,x_2,\ldots,x_n)[/math] k-й аргумент [math](1 \leqslant k \leqslant n)[/math], можем получить две новые булевы функции от [math]n-1[/math] аргументов:


[math]f(x_1,\ldots,x_{k-1}, \,0,\, x_{k+1},\ldots,x_n)[/math] и [math]f(x_1,\ldots,x_{k-1},\, 1,\, x_{k+1},\ldots,x_n)[/math].

Например, из функции от трех аргументов [math]F_2(x_1,x_2,x_3)= (x_1\lor x_2)\cdot (x_1\lor x_3)[/math] фиксированием первого аргумента получаем следующие функции от двух аргументов:


[math]\begin{aligned}h'(x_2,x_3)&= F_2(0,x_2,x_3)= (0\lor x_2)\cdot (0\lor x_3)= x_2\cdot x_3\,;\\[2pt] h''(x_2,x_3)&= F_2(1,x_2,x_3)= (1\lor x_2)\cdot (1\lor x_3)= 1\cdot 1=1\,. \end{aligned}[/math]

Предлагаем посмотреть самостоятельно, какие получатся функции из функции [math]F_2(x_1,x_2,x_3)[/math] при последовательном фиксировании остальных ее аргументов [math]x_2,x_3[/math].




Число булевых функций


Перечислив ранее все булевы функции от одного аргумента и от двух аргументов, мы видели, что первых имеется всего четыре, а вторых — шестнадцать. Возникает вопрос, сколько будет разных булевых функций от трех аргументов, от четырех аргументов и т.д. Нельзя ли указать формулу, по которой вычислялось бы число булевых функций от [math]n[/math] аргументов? Ответ на поставленный вопрос дает следующая теорема.


Теорема 10.3 (о числе булевых функций от [math]n[/math] аргументов). Число различных булевых функций от [math]n[/math] аргументов равно [math]2^{2^n}[/math].


Доказательство. Чтобы задать булеву функцию [math]f(x_1,\ldots,x_n)[/math] от [math]n[/math] аргументов, нужно перечислить все наборы [math](a_1,\ldots,a_n)[/math] из нулей и единиц значений, которые могут принимать ее аргументы [math]x_1,\ldots,x_n[/math], и для каждого такого набора указать значение функции [math]f[/math], которое она принимает на этом наборе.


Выясним сначала, сколько существует различных наборов [math](a_1,\ldots,a_n)[/math], составленных из нулей и единиц, значений для [math]n[/math] аргументов [math]x_1,\ldots,x_n[/math]. Покажем, что это число равно [math]2^n[/math]. Доказательство будем вести методом математической индукции по числу [math]n[/math]. В самом деле, для [math]n=1[/math] имеется всего два набора значений переменного [math]x_1[/math]. Это 0 и 1. Так что для [math]n=1[/math] число наборов равно [math]2^1[/math]. Предположим, что для [math]k[/math] аргументов имеется точно [math]2^k[/math] различных наборов [math](a_1,\ldots,a_k)[/math], составленных из 0 и 1, значений для к аргументов. Тогда среди всевозможных различных наборов [math](a_1,\ldots, a_k,a_{k+1})[/math] значений для [math]k+1[/math] аргумента имеется, согласно предположению индукции, точно [math]2^k[/math] наборов вида [math](a_1,\ldots,a_k,0)[/math] и точно [math]2^k[/math] наборов вида [math](a_1,\ldots,a_k,1)[/math]. Следовательно, всего будет [math]2^k+2^k=2\cdot 2^k=2^{k+1}[/math] различных наборов. Тем самым доказано с помощью индукции утверждение о числе различных наборов.


Таким образом, для задания функции [math]f[/math] от [math]n[/math] аргументов нужно указать ее значение для каждого из [math]2^n[/math] различных наборов значений ее аргументов. Если каждое значение функции равно нулю, то такая функция постоянна. Она называется константа 0. Если каждое значение функции равно единице, то это вторая постоянная функция, называемая константа 1. Мы указали лишь две различные функции от [math]n[/math] аргументов. Сколько же их существует всего? Ровно столько, сколько имеется разных наборов длины [math]2^n[/math], составленных из нулей и единиц (см. таблицу).


[math]\begin{array}{|c||c|c|c|c|c|c|} \hline \begin{matrix}\\[-12pt] \text{Arguments} \\[-2pt] \bigl(x_{{}_1},\ldots,x_{{}_{n-1}},x_{{}_n}\bigr)\\[-12pt] \end{matrix} & \multicolumn{6}{|c|}{\text{Boolean functions}} \\ \cline{2-7} & f_{{}_0}& f_{{}_1}& f_{{}_2}& \cdots & f_{{}_{m-2}}& f_{{}_{m-1}} \\\hline (0,\ldots,0,0)& 0& 0& 0& \cdots & 1& 1\\ (0,\ldots,0,1)& 0& 0& 0& \cdots & 1& 1\\ (0,\ldots,1,0)& 0& 0& 0& \cdots & 1& 1\\ (0,\ldots,1,1)& 0& 0& 0& \cdots & 1& 1\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ (1,\ldots,1,0)& 0& 0& 1& \cdots & 1& 1\\ (1,\ldots,1,1)& 0& 1& 0& \cdots & 0& 1\\\hline \end{array}[/math]

Разных наборов длины [math]2^n[/math], составленных из нулей и единиц, как показано в начале доказательства теоремы, имеется [math]2^{\ell}[/math], где [math]\ell=2^n[/math] — длина набора. Таким образом, число [math]m[/math] разных булевых функций от [math]n[/math] аргументов равно точно [math]2^{\ell}=2^{2^n}[/math]. Теорема доказана.




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


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


Лемма 10.4 (о разложении функции по переменной). Для произвольной булевой функции [math]f(x_1,x_2,\ldots,x_n)[/math] справедливы следующие формулы, называемые формулами разложения этой функции по переменной [math]x_1:[/math]


[math]\begin{aligned} f(x_1,x_2,\ldots,x_n)&= \bigl(x_1\cdot f(1,x_2,\ldots,x_n)\bigr) \lor \bigl(x'_1\cdot f(0,x_2,\ldots,x_n)\bigr)\bigr);\\[2pt] f(x_1,x_2,\ldots,x_n)&= \bigl(x_1\lor f(0,x_2,\ldots,x_n)\bigr)\bigr) \cdot \bigl(x'_1\lor f(1,x_2,\ldots,x_n)\bigr)\bigr). \end{aligned}[/math]

Доказательство. Докажем справедливость первой формулы. Нужно проверить, что функции, стоящие в обеих частях равенства, при одинаковых значениях их аргументов принимают равные значения. Рассмотрим сначала всевозможные наборы значений аргументов следующего вида [math](0,a_2,\ldots,a_n)[/math], т.е. будем придавать аргументам [math]x_1,x_2,\ldots,x_n[/math] значения: [math]x_1=0,x_2=a_2,\ldots,x_n=a_n[/math]. При этом безразлично, каковы именно значения [math]a_2,\ldots,a_n[/math]. Вычислив, какое значение принимает на наборах такого вида функция, стоящая в правой части доказываемого равенства, убедимся, что оно совпадает со значением, принимаемым функцией, стоящей в левой части этого равенства, на том же наборе значений аргументов. В самом деле,


[math]\begin{aligned}\bigl(0 \cdot f(1,a_2,\ldots,a_n)\bigr) \lor \bigl(0' \cdot f(0,a_2,\ldots,a_n)\bigr)&= 0\lor \bigl(1 \cdot f(0,a_2,\ldots,a_n)\bigr)=\\ &=0\lor f(0,a_2,\ldots,a_n)=\\ &=f(0,a_2,\ldots,a_n).\end{aligned}[/math]

Теперь рассмотрим всевозможные наборы значений аргументов вида [math](1,a_2,\ldots,a_n)[/math], т.е. будем придавать аргументам [math]x_1,x_2,\ldots,x_n[/math] значения: [math]x_1=1,x_2=a_2,\ldots,x_n=a_n[/math]. Аналогично вычисляем значение, принимаемое функцией, стоящей в правой части доказываемого равенства, на наборах такого вида:


[math]\begin{aligned}\bigl(1 \cdot f(1,a_2,\ldots,a_n)\bigr) \lor \bigl(1' \cdot f(0,a_2,\ldots,a_n)\bigr)&= f(1,a_2,\ldots,a_n) \lor \bigl(0 \cdot f(0,a_2,\ldots,a_n)\bigr)=\\ &= f(1,a_2,\ldots,a_n) \lor 0=\\ &=f(1,a_2,\ldots,a_n).\end{aligned}[/math]

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


Совершенно аналогично доказывается вторая формула.


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




Представление булевых функций через конъюнкцию, дизъюнкцию и отрицание


Теорема 10.5 (о представлении булевых функций через конъюнкцию, дизъюнкцию и отрицание). Всякая булева функция [math]f(x_1,x_2,\ldots,x_n)[/math] может быть представлена в виде суперпозиции конъюнкции, дизъюнкции и отрицания; причем знак отрицания стоит только непосредственно около переменной и не стоит ни перед одной из внутренних скобок.


Доказательство будем вести методом математической индукции по числу [math]n[/math] аргументов функции [math]f[/math].


В предыдущем параграфе перечислены все булевы функции от одного аргумента. Их всего четыре. Напомним их (используя равенства теоремы 9.3, пункт и):


[math]f_0(x)=0=x\cdot x',\quad f_1(x)=x,\quad f_2(x)=x',\quad f_3(x)=1=x\lor x'.[/math]

Отсюда видно, что все функции от одного аргумента выражаются через конъюнкцию, дизъюнкцию и отрицание; причем знак отрицания стоит только непосредственно около переменных. Это означает, что утверждение теоремы справедливо при [math]n=1[/math].


Предположим, что теорема верна для всех функций от [math]k[/math] аргументов. Докажем ее для функций от [math]k+1[/math] аргумента. Пусть [math]f(x_1,\ldots,x_k,x_{k+1})[/math] — произвольная булева функция от [math]k+1[/math] аргумента. На основании предыдущей леммы запишем разложение данной функции по последней переменной:


[math]f(x_1,\ldots,x_k,x_{k+1})= \bigl(x_{k+1}\cdot f(x_1,\ldots, x_k,1)\bigr)\lor \bigl(x'_{k+1}\cdot f(x_1,\ldots,x_k,0)\bigr).[/math]

Как отмечалось в начале настоящего параграфа, фиксирование в булевой функции одного аргумента приводит к булевой функции с числом аргументов на единицу меньшим, нежели число аргументов исходной функции. Так что каждая из функций [math]f(x_1,\ldots, x_k,1)[/math] и [math]f(x_1,\ldots,x_k,0)[/math] есть булева функция от [math]k[/math] аргументов. Но согласно предположению индукции, все такие функции выражаются через конъюнкцию, дизъюнкцию и отрицание, причем знак отрицания стоит только непосредственно около переменных и не стоит ни перед одной из внутренних скобок. Принимая это во внимание, видим, что правая часть последнего равенства представляет собой суперпозицию лишь трех функций — конъюнкции, дизъюнкции и отрицания. Причем отрицание стоит около переменной [math]x_{k+1}[/math]. Это и доказывает окончательно теорему.




Булевы функции и формулы алгебры высказываний


Установим сначала соответствие между формулами алгебры высказываний и булевыми функциями. Это делается следующим образом. Во-первых, определяется взаимно-однозначное соответствие между пропозициональными переменными и булевыми переменными, при котором прописная буква, обозначающая пропозициональную переменную, соответствует той же самой строчной букве, обозначающей булеву переменную:


[math]\begin{gathered}P,~ Q,~ R,~ X,~ Y,~ Z,~ X_1,~ X_2,~ \ldots,~ Y_1,~ Y_2,~ \ldots\\ p,~ q,~ r,~ x,~ y,~ z,~ x_1,~ x_2,~ \ldots,~ y_1,~ y_2,~ \ldots \end{gathered}[/math]

Во-вторых, устанавливается соответствие между знаками логических связок и одноименных булевых функций:


[math]\begin{array}{|c||c|c|c|c|c|}\hline \text{Logic connectives} & \lnot & \land & \lor & \to & \leftrightarrow \\\hline \text{Boolean functions} & ' & \cdot & \lor & \to & \leftrightarrow \\\hline \end{array}[/math]

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


Например, формуле [math](P \leftrightarrow \lnot Q)\to \bigl((\lnot X_1\lor X_2)\land\lnot Z\bigr)[/math] соответствует булева функция [math](p \leftrightarrow q')\to \bigl((x'_1\lor x_2)\cdot z'\bigr)[/math].


Если булева функция задана с помощью формулы, то для того чтобы найти соответствующую этой функции формулу алгебры высказываний, нужно в выражении для булевой функции заменить строчные буквы такими же прописными буквами, а каждый символ булевой функции [math]',\cdot,\lor,\to,\leftrightarrow[/math] заменить соответственно символом одноименной логической операции [math]\lnot,\land,\lor,\to,\leftrightarrow[/math]. Здесь возникает неоднозначность такого обратного соответствия, поскольку булева функция может иметь множество различных формульных выражений. Например, функция, рассмотренная в предыдущем абзаце, имеет также следующие формульные выражения:


[math]\begin{aligned}& (p \leftrightarrow q') \to (x'_1\cdot z'\lor x_2\cdot z');\\[2pt] & \bigl((p\to q')\cdot (q'\to p)\bigr)\to \bigl((x'_1\lor x_2)\cdot z'\bigr);\\ & \bigl((p'\lor q')\cdot (p\lor q)\bigr)\to (x'_1\cdot z'\lor x_2\cdot z')~~ \text{etc.} \end{aligned}[/math]

Этим выражениям сопоставляются соответственно следующие формулы алгебры высказываний:


[math]\begin{aligned}& (P \leftrightarrow\lnot Q) \to \bigl((\lnot X_1\land\lnot Z)\lor (X_2\land\lnot Z)\bigr);\\ & \bigl((P\to\lnot Q) \land (\lnot Q\to P)\bigr)\to \bigl((\lnot X_1\lor X_2)\land\lnot Z\bigr);\\ & \bigl((\lnot P\lor\lnot Q)\land (P\lor Q)\bigr) \to \bigl((\lnot X_1\land\lnot Z)\lor (X_2\land\lnot Z)\bigr)~~ \text{etc.} \end{aligned}[/math]

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


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


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




Нормальные формы булевых функций


На основе теоремы 10.5 всякая булева функция может быть представлена некоторой формулой алгебры высказываний. Нетрудно понять, что всякая формула алгебры высказываний, равносильная формуле, представляющей некоторую булеву функцию [math]f[/math]; будет представлять функцию, равную [math]f[/math]. В частности, одной из таких представляющих формул будет совершенная дизъюнктивная нормальная форма (если данная булева функция не равна тождественно 0, т.е. представляющая формула не тождественно ложна) или совершенная конъюнктивная нормальная форма (если данная булева функция не равна тождественно 1, т.е. представляющая формула не является тавтологией). Отыскав совершенную нормальную форму для формулы алгебры высказываний, представляющей данную булеву функцию (применяя правила, полученные в теоремах 5.2 и 5.4), можно перейти от этой формы к формульному выражению для данной булевой функции. Его будем называть совершенной (дизъюнктивной или конъюнктивной) нормальной формой булевой функции, сокращенно СДН-формой или соответственно СКН-формой. Каждая из них для данной булевой функции, если она существует, единственна.


Приобретя опыт работы с булевыми функциями, можно отыскивать их нормальные формы, не переходя к символике алгебры высказываний. При этом, если функция задана каким-то формульным выражением, то для его тождественного преобразования следует пользоваться свойствами булевых функций, установленными в теоремах 9.3–9.5, а если функция задана своими значениями на всех наборах значений аргументов (т.е. если она задана таблично), то следует применять правила, полученные в теоремах 5.2 и 5.4, переведя их предварительно на язык булевых функций.


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


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

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