"Задание функций непосредственно таблицей удобно лишь при небольшом числе переменных. Другим средством представления функций является суперпозиция, символическим (аналитическим) выражением которой служат формулы. Применение формул связано с использованием функциональных знаков - символов булевых функций. Некоторые из них уже встречались. Применение формул позволяет представить функции большого числа переменных суперпозициями
функций меньшего числа переменных, прежде всего через функции 1 и 2 переменных.
Формулы алгебры логики (пропозициональные формулы)
- формулы, построенные из знаков переменных и знаков функциональных операций с соблюдением определенных правил построения формул.
Поскольку мы будем рассматривать формулы, использующие исключительно одноместные и двуместные операции, приведем соответствующее индуктивное определение:
1) булевы константы 0, 1 - формулы;
2) переменные X,Y,Z и т.д. - формулы;
3) если F и G - формулы, то 
- формулы, где 
знак унарной операции (функции) отрицания, а 
знак некоторой
бинарной функциональной операции; F и G называются подформулами.
Согласно этому определению 
формулы: переменные, связанные знаками функциональных операций
- также формулы, поскольку 
- формулы, и
суть функциональные знаки. Однако для сокращения формул принято использовать следующую иерархию (частичный порядок) функциональных символов. 'Знак 
связывает теснее знака 
, знак 
- теснее знаков 
, а последние - теснее знака равенства
=, связывающего равные формулы. Символически:
Кроме того, знак конъюнкции можно опускать подобно знаку умножения в алгебре; знак отрицания 
, отнесенный к отдельной
переменной удобнее записывать как надстрочное отрицание 
. Это соглашение, а также ассоциативность операций 
позволяют
устранять излишние скобки, в том числе, внешние. Например, выражение
может быть записано короче: 
Формулам естественным образом соответствуют функции: знакам переменных - булевы переменные, а подформулам, соединенным функциональными знаками - булевы функции. При этом каждая формула
задает единственную функцию, но обратное не верно: для любой функции существует много различных представляющих ее формул. Например,
приведенное выше равенство 
, предлагает две разные
записи одной и той же функции. Другие примеры встречались при
определении функции 
. Мы приходим к следующему понятию.
, Эквивалентные (равносильные) формулы -формулы, представляющие одну и ту же функцию.
Проверить равенство 
двух булевых функций,
представленных разными формулами, можно с помощью вычисления их значений на всех наборах значений переменных. Однако это трудоемкая процедура, и удобнее избрать другой путь: эквивалентные преобразования.
Прежде всего приведем равенства для формул, содержащих
операции конъюнкции, дизъюнкции и отрицания (X, Y,Z - логические переменные^.
! Конъюнкцию, дизъюнкцию и отрицание можно рассматривать как алгебраические операции над булевыми функциями. Свойства 1-2 выражают коммутативность, свойства 3-4 - ассоциативность^операций
; свойства 5-6 - взаимную дистрибутивность этих операций, что дает возможность раскрывать скобки в формулах. Свойства 7-8 -устранение кратности; свойства 9-10 называют правилами поглощения! они являются следствиями остальных свойств, что показано нижед Свойства 11-12 - законы де Моргана. Свойство 13
называют законом исключенного третьего; свойство 14 - законом противоречия. Свойства 15-20 характеризуют основные операции над переменной и константами 0 и 1. Свойство 21 - снятие двойного отрицания.|
Совокупность всех булевых функций 
с тремя данными
операциями есть алгебра 
. Она называется алгеброй
булевых функций, алгеброй логики, а также булевой алгеброй. Сравнивая свойства 1-21 для булевых функций со свойствами 1-21 §1 главы 1 для алгебры множеств, приходим к следующему результату.
Соотношение между булевой алгеброй и алгеброй Кантора есть изоморфизм, порождаемый соответствием между подмножествами
конечного п -элементного множества М и п -мерными булевыми векторами вместе с соответствием между операциями объединения, пересечения, дополнения для множеств и операциями дизъюнкции, конъюнкции и отрицания для векторов. При этом соответствии сохраняются все свойства операций, их определяющие.
Вследствие описанного изоморфизма всякую алгебру, которая обладает свойствами 1-21, называют булевой алгеброй. Кроме алгебры Кантора и алгебры логических функций, булевой алгеброй является, например, алгебра случайных событий в теории вероятностей.
Упражнение. Разберите самостоятельно, что соответствует в алгебре Кантора и в алгебре случайных событий булевым функциям
, константам 0 и 1. Некоторые рассмотренные выше функции выражаются через
и эти выражения тоже представляют эквивалентности:
Для функций 
справедливы также
соотношения:
Важнейшее свойство равенства булевых функций состоит в том,
что если в суперпозиции 
заменить какую-либо
функцию 
на равную ей, то это не повлияет на результат Указанная
процедура представляет правило замены подформул.
С другой стороны, если в формуле 
, выражающей равенство
(эквивалентность формул) двух булевых функций заменить какую-либо переменную X на произвольную формулу 
, то полученные формулы
представляют уже две другие функции 
, но
равенство между ними сохраняется: 
. Подчеркнем, что должны
одновременно заменяться все вхождения переменной X, Так, из равенства (13) получается равенство 
, верное для любой
формулы F. Однако частичная замена 
уже не дает верного
равенства.
Правильная подстановка и замена подформул приводит к новым эквивалентным соотношениям.
Несколько следствий основных равенств:
1) поглощение: а) свойство 9: 
; (*) Доказательство: 
= [в силу свойства 18]= 
=
[выносим X за скобки] = 
= [в силу свойств 17,18] = 
б) свойство 10: 
;
Доказательство: 
[раскрываем скобки]
2) склеивание: 
;
Доказательство 
; [выносим X за скобки]
Доказательство' 
[заменяем X на левую часть
равенства (*)] = 
= [выносим Y за скобки из двух
последних слагаемых] = 
= [в силу свойства 13]
Обратите 
внимание, что равенства 7-10, 13-18 и указанные следствия содержат в правой части меньше символов (более короткие
формулы), чем в левой Поэтому применение этих эквивалентностей позволяет осуществлять преобразования, в частности, упрощения формул, выражать одни из функций через другие; некоторые примеры такого рода уже встречались.
Возникают естественные вопросы
(1) можно ли суперпозициями функций одной-двух переменных выразить любую функцию большего числа переменных;
(2) как это сделать, если это возможно. Ответ на эти вопросы - в следующем разделе.
