Таблици с булеви функции и булев оператор - MathHelpPlanet
Обсъждане и решаване на задачи по математика, физика, химия, икономика
Часова зона: UTC + 3 часа [DST]
Въведение в анализа
Теория на опашката (QS)
Булеви функционални таблици и булев оператор
Булевата функция на n променливи може да бъде дадена от таблица, състояща се от две колони и [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>>\\\hlinex& 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&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] е посочен неговия номер, т.е. числото, чийто двоичен код е даденото множество.
Теоретично всяка булева функция може да бъде дефинирана с таблица, но при голям брой променливи този метод практически не е приложим. След това ще разгледаме метод за специфициране на булеви функции под формата на формули, подобно на аналитичната спецификация на елементарни функции в анализа. От гледна точка на логическата интерпретация на булева функция, нейната таблица е таблицата на истинността на някакво сложно твърдение. Променливите на функцията са прости изрази, включени в комплексен оператор.
Освен това е полезно да имате предвид, че когато пишете таблица на булева функция от n променливи, няма нужда да изброявате всички набори с дължина [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), може да се запише по следния начин: