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

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

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

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

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


Таблицы булевых функций и булев оператор

Таблицы булевых функций и булев оператор


Булева функция от п переменных может быть задана таблицей, состоящей из двух столбцов и [math]2^n[/math] строк. В первом столбце перечисляются все наборы из [math]\mathbb{B}^n[/math] в лексикографическом порядке, а во втором — значения функции на наборах. Форма таблицы произвольной булевой функции приведена ниже (табл. 6.1).


[math]\begin{array}{|c|c|}\multicolumn{2}{r}{\mathit{Table~6.1}} \\\hline x_1\ldots x_n & f(x_1,\ldots, x_n) \\\hline 0\ldots0 & f(0,\ldots,0)\\ \ldots & \ldots\\ (\alpha_{k,1}\ldots \alpha_{k,n}) & f(\alpha_{k,1},\ldots, \alpha_{k,n})\\ \ldots & \ldots\\ 1\ldots1 & f(1,\ldots,1)\\\hline \end{array}[/math]

В (k+1)-й строке таблицы расположен набор [math]\widetilde{\alpha}_k=(\alpha_{k,1}\ldots \alpha_{k,n})[/math], являющийся двоичным кодом числа [math]k[/math] (при [math]0\leqslant k\leqslant 2^n-1[/math]).


Рассмотрим некоторые примеры булевых функций, которые будем задавать посредством таблиц.


При [math]n=1[/math] имеем четыре булевы функции (табл. 6.2).


[math]\begin{array}{|c||c|c|c|c|}\multicolumn{5}{r}{\mathit{Table~6.2}}\\\hline x& f_1(x)& f_2(x)& f_3(x)& f_4(x)\\\hline 0&0&0&1&1\\ 1&1&0&1&0\\\hline \end{array}[/math]

Функцию [math]f_1[/math] называют тождественной функцией, а функцию [math]f_4[/math] — отрицанием. Функции [math]f_2[/math] и [math]f_3[/math] являются функциями (от одного переменного), принимающими постоянное значение (0 и 1 соответственно). Их также зачастую называют константой 0 и константой 1. Постоянные функции, разумеется, могут быть определены и при любом (большем 1) числе переменных.


В табл. 6.3 указаны семь (из [math]2^{2^2}=16[/math]) наиболее важных для дальнейшего изложения булевых функций от двух переменных.


[math]\begin{array}{|c|c||c|c|c|c|c|c|c|}\multicolumn{9}{r}{\mathit{Table~6.3}}\\\hline x_1& x_2& f_1& f_2& f_3& f_4& f_5& f_6& f_7\\\hline 0&0&0&0&0&1&1&1&1\\ 0&1&1&0&1&1&0&1&0\\ 1&0&1&0&1&0&0&1&0\\ 1&1&1&1&0&1&1&0&0\\\hline \end{array}[/math]

Поскольку каждая булева функция от двух переменных есть одновременно и бинарная операция на множестве [math]\{0;1\}[/math], то естественно для таких функций использовать запись, принятую для бинарных операций: [math]x\,\omega\,y[/math] вместо [math]\omega(x,y)[/math].


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


[math]\begin{array}{ll}f_1(x_1,x_2)=x_1\lor x_2,&\qquad f_4(x_1,x_2)=x_1\to x_2,\\[2pt] f_2(x_1,x_2)=x_1\cdot x_2,&\qquad f_5(x_1,x_2)=x_1\sim x_2,\\[2pt] (f_2(x_1,x_2)=x_1\land x_2)&\qquad f_6(x_1,x_2)=x_1\mid x_2,\\[2pt]f_3(x_1,x_2)=x_1\oplus x_2,&\qquad f_7(x_1,x_2)=x_1\downarrow x_2. \end{array}[/math]

Функцию [math]f_1[/math] называют дизъюнкцией, [math]f_2[/math] — конъюнкцией, [math]f_3[/math] — сложением по модулю 2 [math](\operatorname{mod}2)[/math], [math]f_4[/math] — импликацией, [math]f_5[/math] — эквивалентностью, [math]f_6[/math] — штрихом Шеффера, [math]f_7[/math] — стрелкой Пирса.


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


Далее, можно заметить, что сложение по модулю 2 совпадает с операцией сложения кольца вычетов [math]\mathbb{Z}_2[/math] по модулю 2, штрих Шеффера есть отрицание конъюнкции, а стрелка Пирса — отрицание дизъюнкции, т.е.


[math]x_1\mid x_2=\overline{x_1\cdot x_2},\qquad x_1\downarrow x_2= \overline{x_1\lor x_2}.[/math]

Приведем для примера таблицу булевой функции от трех переменных (табл. 6.4).


[math]\begin{array}{|c||c|c|c||c|}\multicolumn{5}{r}{\mathit{Table~6.4}}\\\hline & x_1& x_2& x_3& f(x_1,x_2,x_3)\\\hline \scriptstyle{\mathsf{0}}& 0&0&0&0\\ \scriptstyle{\mathsf{1}}& 0&0&1&0\\ \scriptstyle{\mathsf{2}}& 0&1&0&0\\ \scriptstyle{\mathsf{3}}& 0&1&1&1\\ \scriptstyle{\mathsf{4}}& 1&0&0&0\\ \scriptstyle{\mathsf{5}}& 1&0&1&1\\ \scriptstyle{\mathsf{6}}& 1&1&0&1\\ \scriptstyle{\mathsf{7}}& 1&1&1&1\\\hline \end{array}[/math]

Эта функция называется мажоритарной функцией или функцией голосования. Заметим, что в первом столбце табл. 6.4 для каждого набора из [math]\{0;1\}^3[/math] указан его номер, т.е. число, двоичным кодом которого служит данный набор.


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


Кроме того, полезно иметь в виду, что, записывая таблицу булевой функции от п переменных, нет необходимости каждый раз перечислять все наборы длины [math]n[/math] — достаточно записать вектор значений булевой функции, понимая, что i-я компонента этого вектора есть значение функции на i-м наборе (двоичном коде числа [math]i[/math]).


Тогда мажоритарная функция [math]f[/math] может быть задана так: [math]f=(0,0,0,1,0,1,1,1)[/math].


Можно также перечислить номера тех наборов, на которых функция принимает значение 1: [math]f=\{3,5,6,7\}[/math].




Булев оператор


Обобщением понятия булевой функции служит понятие булева оператора. Булев оператор — это произвольное отображение вида


[math]f\colon\mathbb{B}^n\to\mathbb{B}^m[/math]
(6.3)

для произвольных [math]n,m\in\mathbb{N}\cup\{0\}[/math].


Булев оператор (6.3) может быть задан посредством семейства булевых функций в виде


[math]\left\{\!\begin{gathered}y_1=f_1(x_1,x_2,\ldots,x_n),\hfill\\ y_2= f_2(x_1,x_2, \ldots, x_n),\hfill\\[-7pt] \vdots \\[-5pt] y_m=f_m(x_1,x_2,\ldots,x_n).\hfill \end{gathered}\right.[/math]
(6.4)

Функции [math]f_i[/math] в (6.4) будем называть координатными функциями булева оператора (6.3). Бели ввести векторы переменных [math]\boldsymbol{y}=(y_1,y_2,\ldots,y_m)[/math] и [math]\boldsymbol{x}= (x_1,x_2,\ldots,x_n)[/math], то булев оператор (6.3), заданный семейством координатных функций (6.4), можно записать в таком виде:


[math]\boldsymbol{y}=f(\boldsymbol{x}).[/math]
(6.5)

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


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

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