78
правок
Изменения
Нет описания правки
'''Бу́лева фу́нкция''' (или '''логи́ческая функция''', или '''функция а́лгебры ло́гики''') от <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>. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
|}
== Полные системы булевых функций = Представление функции формулой ===
=== Тождественность и двойственность ===
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
=== Суперпозиции ===
{{main|Суперпозиции}}
=== Полнота системы, критерий Поста ===
== Представление булевых функций ==
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <math>\Sigma = \{f_1,\ldots,f_n\}</math>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <math>\Sigma</math>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
