Изменения

'''Бу́лева фу́нкция''' (или '''логи́ческая функция''', или '''функция а́лгебры ло́гики''') от <tex>n</tex> переменных — отображение <tex>B_nB^n</tex> → <tex>B</tex>, где <tex>B = \{0, 1\}</tex> — булево множество.}} Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения ''B''<suptex>''B^n''</suptex> называют ''булевыми векторами''. Множество всех булевых функций от любого числа переменных часто обозначается ''P''<subtex>2P_2</subtex>, а от ''n'' переменных — ''P''<subtex>2P_2(n)</subtex>(''n''). Булевы функции названы так по фамилии математика Джорджа Буля.

Каждая булева функция арности ''n'' полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины ''n''. Число таких векторов равно 2<suptex>''2^n''</suptex>. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех ''n''-арных булевых функций равно 2<suptex>{2^2^{''}^n''}</suptex>. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:

{| class="wikitable" align="center" style="width:10cm" border=1

|-align="center" bgcolor=#EEEEFF! x<subtex>1x_1</subtex> || x<subtex>2x_2</subtex> || … || x<subtex>n...</subtex> || f(x<subtex>1x_n</subtex>,x|| <sub>2</subtex>f(x_1,x_2,…...,x<sub>nx_n)</subtex>)|-align="center" bgcolor=#F0F0F0| <tex>0 </tex> || <tex>0 </tex> || … <tex>...</tex> || <tex>0 </tex> || bgcolor=white | <tex>f(0,0,…...,0)</tex>|-align="center" bgcolor=#F0F0F0| <tex>1 </tex> || <tex>0 </tex> || … <tex>...</tex> || <tex>0 </tex> || bgcolor=white | <tex>f(1,0,…...,0)</tex>|-align="center" bgcolor=#F0F0F0| <tex>0 </tex> || <tex>1 </tex> || … <tex>...</tex> || <tex>0 </tex> || bgcolor=white | <tex>f(0,1,…...,0)</tex>|-align="center" bgcolor=#F0F0F0| <tex>1 </tex> || <tex>1 </tex> || … <tex>...</tex> || <tex>0 </tex> || bgcolor=white | <tex>f(1,1,…...,0)</tex>|-align="center" style="height:10.2cm9cm" bgcolor=#F0F0F0| <mathtex>\vdots</mathtex> || <mathtex>\vdots</mathtex> || <mathtex>\vdots</mathtex> || <mathtex>\vdots</mathtex> || bgcolor=white | <mathtex>\vdots</mathtex>|-align="center" bgcolor=#F0F0F0| <tex>0 </tex> || <tex>1 </tex> || … <tex>...</tex> || <tex>1 </tex> || bgcolor=white | <tex>f(0,1,…...,1)</tex>|-align="center" bgcolor=#F0F0F0| <tex>1 </tex> || <tex>1 </tex> || … <tex>...</tex> || <tex>1 </tex> || bgcolor=white | <tex>f(1,1,…...,1)</tex>

При ''<tex>n'' = 0 </tex> количество булевых функций равно 2<suptex>{2^{^2}^0}</sup> = 2<sup>^1= 2</suptex> = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.

При ''<tex>n'' = 1 </tex> число булевых функций равно 2<suptex>{2^{^2}^1}</sup> = 2<sup>^2= 4</suptex> = 4.

|-align="center" bgcolor=#FFF8DC

|! width="12%" | <tex>0</tex>|! width="12%" | <tex>x</tex>|! width="12%" | &not;<tex>\neg x</tex>|! width="12%" | <tex>1</tex>

При ''<tex>n'' = 2 </tex> число булевых функций равно 2<suptex>{2^{^2}^2}</sup> = 2<sup>^4= 16</suptex> = 16.

|-align="center" bgcolor=#FFF8DC

|! width="5%" | <tex>0</tex>|! width="5%" | &and;<tex>x \land y</tex>|! width="5%" | <tex>x \nrightarrowy</tex>|! width="5%" | <tex>x</tex>|! width="5%" | <tex>x \nleftarrowy</tex>|! width="5%" | <tex>y</tex>|! width="5%" | &<tex>x \oplus;y</tex>|! width="5%" | &or;<tex>x \vee y</tex>|! width="5%" | &darr;<tex>x \downarrow y</tex>|! width="5%" | &harr;<tex>x = y</tex>|! width="5%" | &not;<tex>\neg y</tex>|! width="5%" | &larr;<tex>x \leftarrow y</tex>|! width="5%" | &not;<tex>\neg x</tex>|! width="5%" | &rarr;<tex>x \rightarrow y</tex>|! width="5%" | &nabla;<tex>x \triangledown y</tex>|! width="5%" | <tex>1</tex>

!<tex>\bar{neg y}</tex> |align = center|<tex>NOT2(x, y),\ y',\ \neg bar{y},</tex> ''НЕ2(x, y)''

!<tex>\bar{neg x}</tex> |align = center|<tex>NOT1(x,y),\ x',\ \neg bar{x},</tex> ''НЕ1(x, y)''

При ''<tex>n'' = 3 </tex> число булевых функций равно 2<sup>2³</suptex> {2^2}^3 = 2<sup>^8= 256</suptex> = 256. Некоторые из них определены в следующей таблице:

<mathtex>f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)</mathtex>

| <mathtex>\overline{0}=1</mathtex> || <mathtex>\overline{1}=0</mathtex> || <mathtex>\overline{\overline{x}}=x</mathtex>|| <mathtex>xy=yx\!</mathtex> || <mathtex>x\lor y=y \lor x</mathtex>

|| <mathtex>0x=0\!</mathtex> || <mathtex>1x=x\!</mathtex> || <mathtex>0\lor x=x</mathtex> || <mathtex>1\lor x=1</mathtex> || <mathtex>xx=x\lor x=x</mathtex>

| <mathtex>x\overline{x}=0</mathtex> || <mathtex>x\lor\overline{x}=1</mathtex>

| <mathtex>\overline{x\cdot y}=\overline{x}\lor\overline{y}</mathtex>|| <mathtex>\overline{x}\cdot\overline{y}=\overline{x\lor y}</mathtex> || (законы де Моргана)

<mathtex>x(y\lor z)=xy\lor xz</mathtex><br /><mathtex>x\lor yz=(x\lor y)(x\lor z)</mathtex> (дистрибутивность конъюнкции и дизъюнкции)

Функция <mathtex>g(x_1,x_2,\dots,x_n)</mathtex> называется двойственной функции <mathtex>f(x_1,x_2,\dots,x_n)</mathtex>, если <mathtex>f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}</mathtex>.}}

Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <mathtex>\Sigma = \{f_1,\ldots,f_n\}</mathtex>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <mathtex>\Sigma</mathtex>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы: