Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
X = X, (Хя & Жа) = (Х1 V (,Х1 V Ха.) (л? 1 & Хг) .
5. Выполняются следующие свойства конъюнкции и дизъюнкции:
(х & х) = х, (х V х) = X,
(х&х)=0, (хУх)=1,
(х & 0)= 0, (х V 0) = х,
(х & 1) = х, (хУ1)=1.
Тождества легко могут быть проверены путем сопоставления функций, соответствующих правой и левой частям тождеств.
Замечания. 1. С целью упрощения записи формул мы условимся, что операция & сильнее операции V, т. е. если нет скобок, то сначала выполняется операция &, а потом V. Например, запись (х1 & х2 V х8) означает ( {^1 ^2) V Ж3) ?
2. В силу закона ассоциативности для (х, • х2) можно вместо формул ((х, ° х2)° х3), (х! ° (ха о ) пользоваться выражением (х, 15 х2 ° х3), которое не является формулой, но может быть превращено в нее путем расстановки скобок, причем функциональные свойства не меняются, как бы мы ни расставляли скобки.
3. В формулах, у которых внешняя функция является либо конъюнкцией, либо дизъюнкцией, либо сложе-
22 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
нием по то<1 2, либо импликацией, либо функцией Шеффера, внешние скобки опускаются, например, пишем Хх -*? х2 вместо (ж, -> хг); опускаются также скобки у выражения, над которым стоит знак например, пишем XI -* х2 вместо {х1-> х2).
В дальнейшем будем употреблять следующие обозначения:
ё
& Щ & ^2 & . . • & Хп
1 = 1
в
\/ Х( ” х^ \/ Х% \/ I . . \/ Ха .
Эти записи имеют смысл также и при в = 1.
Удобно сформулировать ряд правил,, вытекающих из пунктов 2 и 5 списка тождеств элементарных функций.
Если е логическом произведении один из множителей равен 0, то и логическое произведение равно 0.
Если в логическом произведении, содержащем не менее двух множителей, имеется множитель, равный 1, то этот множитель можно зачеркнуть.
Если в логической сумме, содержащей не менее двух слагаемых, имеется слагаемое, равное 0, то это слагаемое можно зачеркнуть.
Если в логической сумме одно из слагаемых равно 1, то и логическая сумма равна 1.
В дальнейшем, используя замечания 1, 2 и 3, мы будем употреблять не формулы, а выражения, отличающиеся от формул тем, что в них кое-где опущены скобки. Эти выражения мы также иногда будем называть формулами.
Очевидно, что если 2Г — подформула формулы И и если заменить любое из ее вхождений на эквивалентную формулу Э', то формула 9С перейдет в формулу §3, которая будет эквивалентна 5М.
Этот принцип вместе с тождествами для элементарных функций, к которым присоединяются все тождества, получаемые подстановкой вместо переменных х, хи х2, х& любых формул, позволяет осуществлять эквивалентные преобразования и, тем самым, получать новые тождества. Пример 7.
XI V х%х2 = ж, * 1 V хххг (хг V х2) V х{х2 ~
= Х-1Хг У ХгХ2 V Х1Хг = Х\Х2 V Х1Х2 V х,х2 =
= х^2 V Х\Х2 =? х± {хг V х2) =* хх - 1 = хи
ГЛ. 1. АЛГЕБРА ЛОГИКИ
23
Таким образом, ачV х1х2 = хи т. е. получаем правило поглощения произведения х^хг множителем хх.
Существует еще один способ для получения тождеств. Он основан на использовании так называемого принципа двойственности.
Определение. Функция [/ (хц ..хп) ]*, равная / , называется двойственной функцией к
функции 1{хи ..хп).
Очевидно, что таблица для двойственной функции (при выбранном порядке наборов) получается из таблицы для функции /(я,, ..ж„) инвертированием (т. е. заменой 0 на 1 и 1 на 0) столбца функции и его переворачиванием (см. табл. 6).
Таблица 6
?Ч яа *3 Дя,, яг, Яз)
0 0 0 1 0
0 0 1 1 1
0 1 0 0 0
0 1 1 0 1
1 0 0 0 1
1 0 1 1 1
1 1 0 0 0
1 1 1 1 0
Поскольку [/(жц, .=*}(xh, . - то
функция [f(xiv определяет то же ото-
бражение, что и [/(ач, ..., яч)]*. Обозначим это отображение через /*. Тогда
[}{хи . . Жп)]* = }*{xif ..жп).
Легко видеть, что среди функций 0, 1, X, X, ЯЧ&Жг,
х{ V х2
функция 0 двойственна 1, функция 1 двойственна О, функция х двойственна х, функция х двойственна ж, функция Xi & Хг двойственна Xi V х2, функция Xi V х2 двойственна ач & х2.
Из определения двойственности вытекает, что
/**=(/*).*=/,
24 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
т. е. функция / является двойственной к /* (свойство взаимности).
Пусть /{#,, ..#„) выражена формулой й. Спрашивается, какой вид имеет формула. 53, реализующая
/*(*1, • ? *«)?
Обозначим через хи ..хп все различные символы переменных, встречающиеся в множествах
(#ц, . . •( « • * л (^т11 * • ч Я'Зпрт')'
Теорема 2. Если
Ф (#1, . » ч #п) ==
= /(/1(^111 ? • •> *С1Р1)» • • *> 1т[х7П1, . • ^трт))>
ТО
Ф* (#1, . . ., Хп) =
“ /* (/I (^111 • ? • > *114)1 • ’ ч %П (*»Ш * * ? 1 Хтрт))* Доказательство.
Ф*{#! , ..., хп) = Ф (#1, ... 1 ж«) =
““ / (/1 (*111 * * *1 ^1?!)) ? • м (*«»11 ? • • 1 хтр„У) =
-7(л(^11, * ? " .*» (*«41 ' * Ч *тРга))
= / (/1 (^ь * ? *1 ?Г1Р1)>. • • ч }т (*«»11 * ? *1 *тРтп))
= /* (/1 (*Ш • ? *1 *1р,)» '* ч fm (*«»11 * * м ХтРтУ)'
Из теоремы вытекает
Принцип двойственности. Если формула
г-С[/, /Л реализует функцию }{хи ..., #л), го
$о/щг/ла ?[/*, т. е. ^орл1ула, полученная из 9Е
заменой функций /„ ../« соответственно на Д 2 ,д реализует функцию /*(#1, ..., #„).
Эту формулу мы будем называть формулой, двойственной к §1, б обозначать через $1*, Таким образом,
