Изменения

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

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

Практически все булевы функции малых арностей (<tex>0, 1, 2 </tex> и <tex>3</tex>) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется ''фиктивной''(англ. ''dummy variable'').

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

Если выбрать некоторый набор [[Определение булевой функции|булевых функций]] <tex>A</tex>, то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется '''формулой'''(англ. ''formula'').}}

Две булевы функции '''тождественны''' (англ. ''identical'') друг другу, если на любых одинаковых наборах аргументов они принимают равные значения.}}

Функция <tex>g(x_1,x_2,\dots,x_n)</tex> называется '''двойственной''' (англ. ''duality'') функции <tex>f(x_1,x_2,\dots,x_n)</tex>, если <tex>f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}</tex>.}}Легко показать, что в этом равенстве <tex>f </tex> и <tex>g </tex> можно поменять местами, то есть функции <tex>f </tex> и <tex>g </tex> двойственны друг другу. Из простейших функций двойственны друг другу константы <tex>0 </tex> и <tex>1</tex>, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.

 == Литература См. также ==* [[Специальные формы КНФ]]* [[Сокращенная и минимальная ДНФ]]* [[Пороговая функция]]* [[Cумматор]]  == Источники информации ==