§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 видно, что 
. Следовательно, формулы и эквиваленты.
Еще по теме §1.3. Реализация булевых функций формулами:
- 2.2.1. Представление булевой функции формулой логики высказываний
- Булевы функции.
- 2.2.3. Полные системы булевых функций
- Булевы переменные и функции
- 1.3.2. Булевы функции
- Арифметическое разложение булевых функций
- Элементарные булевы функции. Равносильности
- Полиномиальное разложение булевых функций
- Разложение булевых функций в канонический полином Жегалкина
- 2.2. Булевы функции
- 2. Булевы функции.
- 1.3. Булевы функции
- §1.4. Специальные представления булевых функций
- 2.2.4. Существенные и несущественные переменные. Производная булевой функции первого порядка. Вес переменной
- Формулы и функции
- Использование функций в формулах
- Представление некоторых элементарных функций по формуле Тейлора.