![]() |
Задание функций непосредственно таблицей удобно лишь при небольшом числе переменных. Другим средством представления функций является суперпозиция, символическим (аналитическим) выражением которой служат формулы. Применение формул связано с использованием функциональных знаков - символов булевых функций. Некоторые из них уже встречались. Применение формул позволяет представить функции большого числа переменных суперпозициями функций меньшего числа переменных, прежде всего через функции 1 и 2 переменных.
Формулы алгебры логики (пропозициональные формулы) - формулы, построенные из знаков переменных и знаков функциональных операций с соблюдением определенных правил построения формул. Поскольку мы будем рассматривать формулы, использующие исключительно одноместные и двуместные операции, приведем соответствующее индуктивное определение:
Согласно этому определению (XY), (X
Z), (Y
Y) -формулы: переменные, связанные знаками функциональных операций
,
,
(X
(┐Y
Z)), ((X | Y)
(X
Z)) - также формулы, поскольку (X | Y), (X
Z), (X
Z), ┐Y, (┐Y
Z) - формулы, и
,
,
, суть функциональные знаки. Однако для сокращения формул принято использовать следующую иерархию (частичный порядок) функциональных символов. Знак ┐ связывает теснее знака
, знак
- теснее знаков
,  
,
,
, а последние - теснее знака равенства =, связывающего равные формулы. Символически:
"┐" >"">("
" , "
" , "
" , "
")>" = ".
Кроме того, знак конъюнкции можно опускать подобно знаку умножения в алгебре; знак отрицания ┐Х, отнесенный к отдельной переменной удобнее записывать как надстрочное отрицание. Это соглашение, а также ассоциативность операций и
позволяют устранять излишние скобки, в том числе, внешние. Например, выражение
((┐A (В
C))
(А
(В
С))) = (((┐A
┐В)
(┐В
┐С))
(B
С))
может быть записано короче: А(В C)
А(В
С) = ┐А┐В
┐B┐C
BC
Формулам естественным образом соответствуют функции: знакам переменных - булевы переменные, а подформулам, соединенным функциональными знаками - булевы функции. При этом каждая формула задает единственную функцию, но обратное не верно: для любой функции существует много различных представляющих ее формул. Например,
приведенное выше равенство ┐(Х
У) =
┐Х
┐Y, предлагает две разные записи одной и той же функции. Другие примеры встречались при определении функции Х | Y. Мы приходим к следующему понятию.
Эквивалентные (равносильные) формулы - формулы, представляющие одну и ту же функцию.
Проверить равенство F1 = F2 двух булевых функций, представленных разными формулами, можно с помощью вычисления их значений на всех наборах значений переменных. Однако это трудоемкая процедура, и удобнее избрать другой путь: эквивалентные преобразования. Прежде всего приведем равенства для формул, содержащих операции конъюнкции, дизъюнкции и отрицания (X,Y,Z - логические переменные).
Конъюнкцию, дизъюнкцию и отрицание можно рассматривать как алгебраические операции над булевыми функциями. Свойства 1-2 выражают коммутативность, свойства 3-4 - ассоциативность операций Ъ и ; свойства 5-6 - взаимную дистрибутивность этих операций, что дает возможность раскрывать скобки в формулах. Свойства 7-8 -устранение кратности ; свойства 9-10 называют правилами поглощения; они являются следствиями остальных свойств, что показано ниже. Свойства 11-12 - законы де Моргана. Свойство 13
называют законом исключенного третьего; свойство 14 - законом противоречия. Свойства 15-20 характеризуют основные операции над переменной и константами 0 и 1. Свойство 21 - снятие двойного отрицания.
Совокупность всех булевых функций Р2 с тремя данными операциями
есть алгебра (P2;,
,┐). Она называется алгеброй булевых функций, алгеброй логики,
а также булевой алгеброй. Сравнивая свойства 1-21 для булевых функций со свойствами 1-21 пункт 1 главы 1 для алгебры множеств, приходим к следующему результату.
Соотношение между булевой алгеброй и алгеброй Кантора есть изоморфизм, порождаемый соответствием между подмножествами конечного n -элементного множества М и n -мерными булевыми векторами вместе с соответствием между операциями объединения, пересечения, дополнения для множеств и операциями дизъюнкции, конъюнкции и отрицания для векторов. При этом соответствии сохраняются все свойства операций, их определяющие.
Вследствие описанного изоморфизма всякую алгебру, которая обладает свойствами 1 -21, называют булевой алгеброй. Кроме алгебры Кантора и алгебры логических функций, булевой алгеброй является, например, алгебра случайных событий в теории вероятностей.
Некоторые рассмотренные выше функции выражаются через
,
,┐, и эти выражения тоже представляют эквивалентности:
X Y =
┐X∙Y
X∙┐Y;
X→Y = ┐X Y;
X | Y = ┐X ┐Y;
X Y = ┐X
∙
┐Y
X ∙ Y.
Для функций XY, X
Y, X→Y справедливы также соотношения:
Важнейшее свойство равенства булевых функций состоит в том, что если в суперпозиции
ƒ(g1(x),g2(x),...,gn(x)) заменить какую-либо функцию gi(x) на равную ей, то это не повлияет на результат. Указанная процедура представляет правило замены подформул.
С другой стороны, если в формуле F1 = F2, выражающей равенство (эквивалентность формул) двух булевых функций заменить какую-либо переменную Х на произвольную формулу ƒ, то полученные формулы
F1' и F2' представляют уже две другие функции (F1'≠ F1, F2'≠ F2), но равенство между ними сохраняется: F1'= F2'. Подчеркнем, что должны одновременно заменяться все вхождения переменной Х . Так, из равенства (13) получается равенство F ┐F = l, верное для любой формулы F. Однако частичная замена F
┐X = 1 уже не дает верного равенства.
Правильная подстановка и замена подформул приводит к новым эквивалентным соотношениям. Несколько следствий основных равенств:
1) поглощение:
а) свойство 9: Х Х
∙ Y = Х ;
Доказательство: Х Х
∙ Y = [в силу свойства 18] = Х
∙ 1
X
∙ Y =
= [выносим Х за скобки] = Х
∙ (1
Y) = [в силу свойств 17, 18] = X
∙ 1 = Х
б) свойство 10: Х
∙ (X Y) = X;
Доказательство: X
∙ (X Y) = [раскрываем скобки] = Х
∙ Х
Х
∙ Y = [в силу свойств 8,9]=X
X
∙ Y = X.
2)склеивание:
а) Х
∙ Y Х
∙ ┐Y = Х
Доказательство: Х ∙ Y Х
∙ ┐У = [выносим Х за скобки] =X
∙ (Y
┐Y) = [в силу свойств 13, 18] =Х
∙ 1= Х;
б) ┐X
┐X
∙
┐Y = X
Y
Доказательство: X X
∙ Y = [заменяем Х на левую часть
равенства (*)] = X
X
∙ Y
X
∙ Y =
[выносим Y за скобки из двух последних слагаемых] = X
Y
∙ (X
┐X) = [в силу свойства 13] X
Y
∙ 1 = X
Y.
Обратите внимание, что равенства 7-10, 13-18 и указанные следствия содержат в правой части меньше символов (более короткие формулы), чем в левой. Поэтому применение этих эквивалентностей позволяет осуществлять преобразования, в частности, упрощения формул, выражать одни из функций через другие; некоторые примеры такого рода уже встречались.
Возникают естественные вопросы:
(1) можно ли суперпозициями функций одной-двух переменных выразить любую функцию большего числа переменных;
(2) как это сделать, если это возможно.
Ответ на эти вопросы - в следующем разделе.
![]() |
Практические задания |
![]() |
Tест для самоконтроля |