Таблиці булевих функцій та булев оператор - MathHelpPlanet
Обговорення та вирішення завдань з математики, фізики, хімії, економіки
Часовий пояс: UTC + 3 години [ Літній час ]
Введення в аналіз
Теорія черг (СМО)
Таблиці булевих функцій та булев оператор
Булева функція від п змінних може бути задана таблицею, що складається з двох стовпців і [math]2^n[/math] рядків. У першому стовпці перераховуються всі набори [math]\mathbb^n[/math] у лексикографічному порядку, а в другому — значення функції на наборах. Форма таблиці довільної булевої функції наведена нижче (табл. 6.1).
6.1>> \\hline x_1\ldots x_n & f(x_1,\ldots, x_n) \\hline 0\ldots0 & f(0,\ldots,0)\\ldots & \ldots\\ (\alpha_\ldots \alpha_) & f(\alpha_,\ldots, \alpha_)\\ldots & \ldots\\ 1\ldots1 & f(1,\ldots,1)\\hline \end[/math]
У (k+1)-му рядку таблиці розташований набір [math]\widetilde_k=(\alpha_\ldots \alpha_)[/math] , що є двійковим кодом числа [math]k[/math] (при [math]0\ leqslant k\leqslant 2^n-1[/math] ).
Розглянемо деякі приклади булевих функцій, які задаватимемо за допомогою таблиць.
При [math]n=1[/math] маємо чотири булеві функції (табл. 6.2).
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[/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^=16[/math] ) найбільш важливих для подальшого викладу булевих функцій від двох змінних.
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&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[/math]
Оскільки кожна булева функція від двох змінних є одночасно і бінарна операція на множині [math]\[/math] , то природно для таких функцій використовувати запис, прийнятий для бінарних операцій: [math]x\,\omega\,y[/math ] замість [math]\omega(x,y)[/math] .
Для функцій, записаних у табл. 6.3 приймаються такі позначення:
Функцію [math]f_1[/math] називають диз'юнкцією, [math]f_2[/math] - кон'юнкцією, [math]f_3[/math] - додаванням по модулю 2 [math](\operatorname2)[/math] , [math ]f_4[/math] - імплікацією, [math]f_5[/math] - еквівалентністю, [math]f_6[/math] - штрихом Шеффера, [math]f_7[/math] - стрілкою Пірса.
Диз'юнкція і кон'юнкція, як видно, - це операції двоелементної булевої алгебри - об'єднання і перетин відповідно (тоді як функція заперечення є не що інше, як доповнення в цій булевій алгебрі). У той же час, диз'юнкція і кон'юнкція — це не що інше, як однойменні логічні операції. Очевидним чином з логічними зв'язками, крім заперечення, співвідносяться імплікація та еквівалентність (хоча їх позначення як булеві функції дещо відрізняються від позначень у математичній логіці). Таблиці для введених булевих функцій є тоді нічим іншим, як формою уявлення таблиць істинності.
Далі можна помітити, що додаванняпо модулю 2 збігається з операцією складання кільця відрахувань [math]\mathbb_2[/math] по модулю 2, штрих Шеффера є заперечення кон'юнкції, а стрілка Пірса - заперечення диз'юнкції, тобто.
Наведемо приклад таблицю булевої функції від трьох змінних (табл. 6.4).
6.4>>\\hline & x_1& x_2& x_3& f(x_1,x_2,x_3)\\\hline \scriptstyle>& 0&0&0&0\\ \scriptstyle>& 0&0&1&0\\ \scriptstyle>& 0&1&0&0\\ \scriptstyle>& 0&1&1&1\\ \scriptstyle>& 1&0&0&0\\ \scriptstyle>& 1&0&1&1\\ \scriptstyle>& 1&1&0&1\\ \scriptstyle>& 1&1&1&1\\hline \end[/math]
Ця функція називається мажоритарною функцією чи функцією голосування. Зауважимо, що у першому стовпці табл. 6.4 кожному за набору з [math]\^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=\[/math] .
Бульов оператор
Узагальненням поняття булевої функції є поняття булева оператора. Бульов оператор - це довільне відображення виду
для довільних [math]n, m\in\mathbb\cup\[/math] .
Булев оператор (6.3) може бути заданий за допомогою сімейства булевих функцій у вигляді
Функції [math]f_i[/math] в (6.4) називатимемо координатними функціями булева оператора (6.3). Біли ввести вектори змінних [math]\boldsymbol=(y_1,y_2,\ldots,y_m)[/math] і [math]\boldsymbol= (x_1,x_2,\ldots,x_n)[/math] , то булев оператор ( 6.3), заданий сімейством координатних функцій (6.4), можна записати у такому вигляді: