78
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Булева функция ''' от <tex>n</tex> переменных — отображение <tex>B_n</tex> → <tex>B</tex>, где <tex>B = \{0, 1\}</tex> — булево множество.}} Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла.Элементы декартова произведения ''B''<sup>''n''</sup> называют ''булевыми векторами''. Множество всех булевых функций от любого числа переменных часто обозначается ''P''<sub>2</sub>, а от ''n'' переменных — ''P''<sub>2</sub>(''n''). Булевы функции названы так по фамилии математика Джорджа Буля.
== Основные сведения ==
Каждая булева функция арности ''n'' полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины ''n''. Число таких векторов равно 2<sup>''n''</sup>. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех ''n''-арных булевых функций равно 2<sup>2<sup>''n''</sup></sup>. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
{| class="standard" border=1
|-
!class="dark" style="font-weight:normal" bgcolor=#FFF8DC| ''<tex>x''</tex> !class="dark" style="font-weight:normal" bgcolor=#FFF8DC| ''<tex>y''</tex> !class="dark" style="font-weight:normal" bgcolor=#FFF8DC| ''<tex>z''</tex> !style="font-weight:normal" bgcolor=#FFF8DC| ''<tex>x''↓''\downarrow y''↓''\downarrow z''</tex> !style="font-weight:normal" bgcolor=#FFF8DC| <mathtex>\neg</math>(≥2\geq 2(x,y,z))</tex> !style="font-weight:normal" bgcolor| <tex>x \not = y \not =#FFF8DC| x≠y≠zz</tex> !style="font-weight:normal" bgcolor=#FFF8DC| x<nowiki>|</nowikitex>x \mid y<nowiki>|\mid z</nowikitex>z !style="font-weight:normal" bgcolor=#FFF8DC| <tex>min(x,y,z)</tex> !style="font-weight:normal" bgcolor=#FFF8DC| <tex>x=y=z</tex> !style="font-weight:normal" bgcolor=#FFF8DC| ''<tex>x''⊕''\oplus y''⊕''\oplus z''</tex> !style="font-weight:normal" bgcolor=#FFF8DC| ≥2<tex>\geq 2(x,y,z)</tex> !style="font-weight:normal" bgcolor=#FFF8DC| ''f<subtex>1f_1</subtex>'' !style="font-weight:normal" bgcolor=#FFF8DC| ''f<subtex>2f_2</subtex>'' !style="font-weight:normal" bgcolor=#FFF8DC| <tex>max(x,y,z)</tex>
|- align="center"
!class="shadow" style="font-weight:normal" | 0
|-
!<tex>x \not = y \not = z</tex>
|align = center|<tex>[\not =(x,y,z)] = NE(x,y,z,v)</tex>
|Неравенство
|-
=== Тождественность и двойственность ===
{{Определение|definition=Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. }}Тождественность функций f и g можно записать, например, так:<br />
<math>f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)</math>
<math>x\lor yz=(x\lor y)(x\lor z)</math> (дистрибутивность конъюнкции и дизъюнкции)
{{Определение|definition=Функция <math>g(x_1,x_2,\dots,x_n)</math> называется двойственной функции <math>f(x_1,x_2,\dots,x_n)</math>, если <math>f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}</math>. }}Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
== Представление булевых функций ==
{{main|Представление функции формулой, полные системы функций}}
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <math>\Sigma = \{f_1,\ldots,f_n\}</math>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <math>\Sigma</math>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
* Как построить по данной функции представляющую её формулу?
* http://psi-logic.narod.ru/bool/bool.htm
* [http://mathcyb.cs.msu.su/books.html Учебные пособия кафедры математической кибернетики ВМиК МГУ]
* [http://ru.wikipedia.org/wiki/Заглавная_страница Булева_функция Булева функция — Википедия — свободная энциклопедия]
[[Категория: Булевы функции ]]
