4. Булевы функции

4.1. Основные понятия

Функцию , принимающую одно из двух значений 0 или 1, от п переменных, каждая из которых принимает одно из двух значений 0 или 1, будем называть булевой функцией от п переменных, называемых пропозиционными.

Булева функция от п переменных сопоставляет каждому упорядоченному набору (кортежу), составленному из п элементов, 0 и 1, либо 1, либо 0.

Две булевы функции называются равными, если для любых одинаковых наборов значений переменных обе функции принимают одинаковые значения. Булевых функций одной переменной четыре, а двух переменных — шестнадцать и т. д. Число булевых функций от п переменных равно .

Рассмотрим функции одной и двух переменных, которые называются «элементарными» функциями и с помощью которых можно определить функции большего количества переменных.

Рассмотрим таблицы истинности таких функций. В таблице, задающей булевы функции, наборы значений переменных пишут в лексикографическом порядке, который совпадает с порядком возрастания наборов, рассматриваемых как числа в двоичной системе счисления.

Таблица истинности булевой функции одной переменной:

Таблица 22.

x
0	0	0	1	1
1	0	1	0	1

Функции и называются константами — соответственно 0 и 1.

Функция совпадает с переменной х и называется тождественной .

Функция принимает значения, противоположные значениям аргумента х, и называется отрицанием х, обозначается :

Таблица истинности булевой функции двух переменных:

Таблица 23.

x1	x2	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15	f16
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	l	l	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	l	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Следует отметить, что здесь к функциям двух переменных относятся и такие, которые в действительности зависят от одной переменной.

1. Функции и представляют собой константы 0 и 1.

2. Функции , существенно зависят только от одной переменной: .

3. Остальные функции существенно зависят от двух переменных, и для них есть названия и обозначения:

а) функция и называется конъюнкцией,

б) функция и называется дизъюнкцией,

в) функция и называется эквивалентностью,

г) функция и называется суммой по модулю два, или суммой Жегалкина,

д) функция и называется конверсией,

е) функция и называется импликацией,

ж) функция и называется штрих Шеффера,

з) функция и называется стрелкой Пирса,

и) функции и логически несовместимы с импликацией и конверсией и называются функциями запрета.