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

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

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

Таким образом, булева функция аргументов может бдаь написана в виде

Так как каждая булева переменная принимает лишь два значения (0 и 1), область определения всякой булевой функции конечна. Если приписать фиксированные значения аргументам получим конечную упорядоченную последовательность (называемую кортежем или набором), составленную из нулей и единиц.

Каждый такой набор можно рассматривать как запись некоторого -разрядного двоичного числа. Наибольшее двоичное число получим, составив набор из одних единиц, а наименьшее — из нулей. Следовательно, наибольшему числу соответствует десятиричное число наименьшему — нуль. Всем остальным возможным наборам будут соответствовать двоичные числа, заключенные между нулем и числом Таким образом, получим всего различных наборов значений аргументов.

Это соответствие способствует упорядочению наборов аргументов булевой функций. Первым будем считать набор, соответствующий нулю, вторым — соответствующий единице, и т. д., последним — соответствующий числу

Таблица 1 (см. скан)

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

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

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