 |
|
ЭЛЕМЕНТАРНЫЕ БУЛЕВСКИЕ ФУНКЦИИ
Табличное задание булевских функций не всегда удобно, поскольку уже для небольшого числа переменных размер таблицы произвольной функции таких переменных оказывается слишком большим.
Например, для функций 32переменных, соответствующих 32 разрядным операциям процессора, такая таблица является практически необозримой. Поэтому целесообразно нахождение других форм представления б.ф., имеющих меньшие размеры.
Рассмотрим способ представления б.ф., в котором одни функции выражаются через другие. При этом некоторые б.ф., называемые элементарными функциями, выбираются в качестве базовых. Они получают собственные обозначения, а остальные функции выражаются через элементарные функции с помощью специальных операций.
Элементарными являются следующие булевские функции.
Функции одной переменной:
1. Тождественный ноль (эта функция обозначается как O(x) или0).
2. Тождественная единица (обозначается как 1(x) или1).
3. Отрицание, записываемое как 
.
4. Тождественная функция (обозначается как I(x) или x).
Табличные задания данных функций имеют следующий вид:
| x | 0(x) | 1(x) |
| I(x) |
Функции двух переменных:
1) " (x1, x2) - дизъюнкция;
2) &( x1, x2) - конъюнкция;
3) ®(x1, x2) - импликация;
4) + (x1, x2) - сумма по модулю два;
5) ~ (x1, x2) - эквивалентность;
6) ê (x1, x2) - функция Шеффера.
На практике для представления этих функций используется инфиксная запись, в которой символическое имя функции записывается между левой и правой компонентой аргумента, т.е. например, вместо &(x1, x2) используется запись:(x1 & x2).
Табличные задания этих функций приведены в следующей таблице:
| x1 x2 | x1  x2
| x1& x2 | x1® x2 | x1+x2 | x1~x2 | x1 | x2 |
| 0 0 | ||||||
| 0 1 | ||||||
| 1 0 | ||||||
| 1 1 |
Заметим, что отнесение приведенных функций к элементарным достаточно условно. Например, нетрудно проверить, что 
совпадает с отрицанием конъюнкции, т.е. одни элементарные функции могут быть выражены через другие такие функции.
ФОРМУЛЫ
С помощью символических обозначений переменных и функций можно строить записи, представляющие другие булевские функции. Такие записи называются формулами.
Пусть B - произвольное множество булевских функций. Определим понятие формулы над B.
ОПРЕДЕЛЕНИЕ
1. Если f(x1, . . . , xn) 
B, то запись f(x1, . . . ,xn) является формулой над B.
2. Пусть f ( x1 , . . . , xn ) B и A 1 ,. . ., A n - это либо формулы над B, либо обозначения переменных. Тогда запись
f(A1,. . . , An) - формула над B.
3. Никакие другие записи не являются формулами над B.
Примером формулы над множеством элементарных функций является следующая запись:
.
Пары ограничивающих скобок в формулах необходимы для определения порядка вложенности одних формул в другие. При этом всякая формула, вложенная или содержащаяся в другой формуле, называется подформулой такой формулы.
Важной характеристикой подформул является глубина их вхождения в формулы:
1. Вхождения переменных во всякую формулу имеют глубину 0.
2. Если f (x1, . . . , xn) B, то формула U = f (x1, . . . , xn) имеет глубину d(U)=1
2. Если U = f (U 1,. . . , Un), то глубина U определяется соотношением: d(U)= 1+ max(d(U1), . . . , d(Un)).
Для обозначения формул используются прописные символы латинского алфавита (возможно с индексами). Если в записи формулы Uсодержатся символы переменных x1, . . . , xn, то допускается запись этой формулы в виде U(x1, . . . , xn). Если U содержит подформулы U1, . . . , Uk, то для указания на это свойство формулы U используется запись U(U1,. . .,Uk).
Записи формул над множеством элементарных функций можно упростить за счет опускания части скобок. Для этого достаточно ввести понятие приоритета или старшинства функций из этого множества.
Приоритеты или старшинство элементарных функций устанавливаются следующей схемой убывания приоритетов:
1) 0,1,I;
2) ;
3) &, ç;
4) +,~, ®,Ú.
Приоритеты означают, что при отсутствии скобок более сильная операция соответствует подформуле большей вложенности, или применяется раньше. Тогда с учетом приоритетов приведенный ранее пример формулы можно переписать в виде: 
.
Всякая формула U(х1, . . . , хn) представляет однозначно определяемую булевскую функцию f U(x1 ,. . ., xn). Напомним, что x1, . . . , xn - это все переменные, входящие вU.
Для определения значения fU на конкретном наборе значений переменных x1 , . . ., xn можно воспользоваться следующими правилами:
1) подставим в U вместо переменных x1,. . ., xn принимаемые ими значения;
2) вычислим значение произвольной наиболее вложенной функции, все переменные которой принимают конкретные значения, и заменим вхождение этой функции в формулу на полученное значение;
3) если полученная в результате запись не является двоичным значением, то повторим действие 2.
Понятие формулы над множеством функцийB и понятие функции, представляемой формулой, не являются эквивалентными и не равносильны поскольку всякая формула - это запись, представляющая некоторую булевскую функцию f, но сама такая функция может представляться различными формулами.
Например, нетрудно убедиться, что следующие две формулы над множеством элементарных функций представляют одну и ту же функцию: U1 = 
и 
.
ОПРЕДЕЛЕНИЕ
Формулы U1 и U2 называются эквивалентными, если представляемые ими функции равны.
Эквивалентность формул U1 и U 2 представляется записью U1 º U2. Такие записи называются тождествами.