§1.3. Реализация булевых функций формулами
Функция 
называется суперпозицией булевых функций 
, если она получается некоторой подстановкой этих булевых функций друг в друга.
. Пусть 
и 
– две формулы. Говорят, что формулы 
и 
имеют одинаковое строение, если формула может быть получена из формулы заменой каждого функционального символа 
на символ 
.
Пусть 
. Формулой над 
является всякое (и только такое) выражение вида:
(1) 
– любая переменная из множества 
(2) 
где и 
ранее построенные формулы над .
Обычно принимаются следующие соглашения для сокращения записи формул над множеством связок :
а) внешние скобки у формул опускаются;
б) формула 
записывается в виде 
;
в) формула 
записывается в виде 
или 
;
г) считается, что связка 
сильнее любой двухместной связки из множества ;
д) связка & считается сильнее любой другой двухместной связки из множества .
На множестве переменных 
введем функцию
.
О формуле , задающей функцию , говорят также, что формула реализует функцию . Две формулы и эквивалентны (
), если реализуемые ими функции 
и 
равны.
В эквивалентности формул часто можно убедиться, построив таблицы соответствующих им функций.
Пример. Построив таблицы функций, выяснить эквивалентны ли формулы
и 
.
Решение. Построим векторы значений функций и .
Табл. 1.7
 |  |  |  |  |  | |  |  | |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
Из таблицы 1.7 видно, что 
. Следовательно, формулы и эквиваленты.