Для описания алгоритмов работы цифровых устройств необходим соответствующий математический аппарат. Такой аппарат для решения задач формальной логики в середине прошлого века разработал ирландский математик Джордж Буль (1815 — 1864). Этот математический аппарат получил название булевой алгебры.
Понятие булевой функции
Дискретная математика изучает функции, область определения которых — дискретное множество (в отличии от математического анализа, где область определения функций — непрерывное множество).
Примером дискретного множества является множество из двух элементов.
Булевой функцией от n аргументов называется функция f из n-ой степени множества { 0, 1 } в множество { 0, 1 }.
Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }. Множество { 0, 1 } мы будем в дальнейшем обозначать через B.
Булеву функцию от n аргументов можно рассматривать как n-местную алгебраическую операцию на множестве B. При этом алгебра <B;W>, где W – множество всевозможных булевых функций, называется алгеброй логики.
В математике булевой функцией называют функцию типа , где — булево множество, а — неотрицательное целое число, которое называют арностью. Элементы 1 (единица) и 0 (ноль) стандартно интерпретируют как истину и ложь, хотя в общем случае их смысл может быть любым. Элементы называют булевыми векторами. В случае булева функция превращается в булеву константу.
, где 
— булево множество, а 
— неотрицательное целое число, которое называют арностью. Элементы 1 (
называют булевыми векторами. В случае 
булева функция превращается в булеву константу.Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2n наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:
| x1 | x2 | … | xn-1 | xn | f |
|---|---|---|---|---|---|
| 0 | 0 | … | 0 | 0 | f(0,0,…,0,0) |
| 0 | 0 | … | 0 | 1 | f(0,0,…,0,1) |
| 0 | 0 | … | 1 | 0 | f(0,0,…,1,0) |
| 0 | 0 | … | 1 | 1 | f(0,0,…,1,1) |
| … | … | … | … | … | … |
| 1 | 1 | … | 0 | 0 | f(1,1,…,0,0) |
| 1 | 1 | … | 0 | 1 | f(1,1,…,0,1) |
| 1 | 1 | … | 1 | 0 | f(1,1,…,1,0) |
| 1 | 1 | … | 1 | 1 | f(1,1,…,1,1) |
Раз у нас есть стандартный порядок записывания наборов, то для того, чтобы задать функцию, нам достаточно выписать значения f(0,0,…,0,0), f(0,0,…,0,1), f(0,0,…,1,0), f(0,0,…,1,1),…, f(1,1,…,0,0), f(1,1,…,0,1), f(1,1,…,1,0), f(1,1,…,1,1). Этот набор называют вектором значений функции.
Таким образом, различных функций n переменных столько, сколько различных двоичных наборов длины 2n*. А их 2 в степени 2n.
Множество B содержит два элемента – их можно рассматривать как булевы функции от нуля (пустого множества) переменных – константу 0 и константу 1.
Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция, т.е. функция, значение которой совпадает с аргументом и так называемая функция «отрицание». Отрицание будем обозначать символом ¬ как унарную операцию. Приведём таблицы этих четырёх функций:
| x | 0 | x | ¬ x | 1 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
Как видим, функции от некоторого числа переменных можно рассматривать как функции от большего числа переменных. При этом значения функции не меняется при изменении этих «добавочных» переменных. Такие переменные называются фиктивными, в отличие от остальных – существенных.
Фиктивные и существенные переменные. Переменная xi называется фиктивной (несущественной) переменной функции f(x1,···,xn), если
Функций от двух аргументов шестнадцать. Наиболее употребимые из этих функций (только те, которые существенно зависят от обеих переменных) мы приводим в следующей таблице:
| x1 | x2 | x1 & x2 | x1 Ъ x2 | x1 Йx2 | x1 Е x2 | x1 є x2 | x1 | x2 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
Эти функции записываются как бинарные операции в инфиксной нотации. x1 & x2 называется конъюнкцией, x1 Ъ x2 – дизъюнкцией, x1 Й x2 – импликацией, x1 є x2 – эквивалентностью, x1 Е x2 – суммой по модулю 2, x1 | x2 – штрихом Шеффера.
Значения 0 и 1 часто интерпретируют как «ложь» и «истину». Тогда понятным становится название функции «отрицание» – она меняет «ложь» на «истину», а «истину» на «ложь». Отрицание читается как «не». Конъюнкция читается обычно как «и» – действительно, конъюнкция равна 1 тогда и только тогда, когда равны 1 и первая и вторая переменная.* Кроме x1& x2 часто используют обозначение x1 Щ x2 или x1 · x2 или x1x2 или min(x1,x2). Дизъюнкция читается «или» – дизъюнкция равна 1 тогда и только тогда, когда равны 1 первая или вторая переменная.* Импликация выражает факт, что из x1 следует x2.* Импликацию часто также обозначают x1 ® x2.