Игошин Математическая логика и теория алгоритмов (1019110), страница 24
Текст из файла (страница 24)
ез(х, у) = х, а вторая функция является отрицанием первой: еп(х, у) = х'. Во вторую пару входят функции яъ(х, у) и я1ь(х, у). Первая из них принимает всегда те же самые значения, что и ее второй аргумент, т.е. я,(х, у) = у, а вторая функция является отрицанием первой: я1ь(х, у) = у'. Теперь установим некоторые важнейшие свойства введенных функций. Две булевы функции Т(х„у) и я(х, у) называются равными, если каждому набору значений аргументов х, у обе функции сопоставляют один и тот же элемент из множества (О, Ц, т.е. г(а, Ь) = я(а, Ь) для любых а, Ь е (О, !). Например, х ч у = у ч х.
Из введенных простейших булевых функций можно строить с помощью суперпозиций более сложные булевы функции. Например, если в функцию х ч г вставить вместо аргумента г функцию у г, то получим следующую сложную функцию: х ч (у . г). Если в нее в свою очередь вставить вместо аргумента г функцию и -ь о, то получим сложную функцию х ч (у (и — > о)). И так далее. В результате получаются булевы функции от трех, четырех и большего числа аргументов. В следующих теоремах устанавливаются некоторые равенства одних булевых функций другим, выражающие свойства основных булевых функций. Свойства дизъюикции, конъюнкции и отрицания.
Теорема 9.3. Для булевых функций выполняются следующие равенства: а) х ч х=х, х х= х(идемпотентность дизъюнкции и конъюнкции); б) х ч у = у ч х, х . у = у . х (коммутативноеть дизъюнкции и коньюнкции); в) (х ч у) ч г = х ч (у ч г), (х . у) г = х . (у . г) (ассоциативность дизьюнкции и коньюнкции); г) хч1 = 1,х. 1=х; д)хчО=х,х 0=0; е) х ч (у г) = (х ч у) (х ч г), х . (у ч г) = (х . у) ч (х . г) (дистрибутивность дизъюнкции относительно коньюнкции и дистрибутивность конъюнкции относительно дизъюнкции); зк) х ч (у х) = х, х (у ч х) = х (законы +оглои1енил)' з) (х чу)'= х'.
у', (х у)'=х' чу'(законы де Моргана); и) х ч х' = 1, х . х' = 0; к) х" = х. Доказательство. а) Свойство идемпотентности дизъюнкции и конъюнкции означает, что применение как одной из них, так и другой к двум одинаковым элементам дает этот же самый элемент. Доказательства данных равенств вытекают непосредственно из таблиц, определяющих дизъюнкцию и конъюнкцию. В самом деле, для дизъюнкции 0 ч 0 = 0„1 ч 1 = 1 и для конъюнкции 0 0=0,1 1=1.
б) Коммугативность (перестановочность) дизъюнкции означает, что значение функции не зависит от порядка ее аргументов. Это действительно так, потому что, согласно определению дизъюнкции, она принимает значение 1 тогда и только тогда, когда хотя бы один из ее аргументов (не имеет значения, какой именно) принимает значение 1, и принимает значение 0 тогда и только тогда, когда оба аргумента равны О. Аналогична ситуация и с конъюнкцией. в) Вместо слова «ассоциативность» используется также термин «сочетательность». Докажем ассоциативность конъюнкции с помощью таблиц. Такой способ важен тем, что он может быть применен для доказательства (или опровержения) равенства между любыми двумя булевыми функциями.
Итак, составляем последовательно таблицы значений булевых функций, суперпозиция которых дает левую часть тождества ассоциативности, а затем булевых функций, суперпозиция которых дает его правую часть, придавая всевозможные значения аргументам х, у, г: Сравнивая пятый и седьмой столбцы таблицы, видим, что они одинаковы, т.е.
функции, стоящие в левой и правой частях доказываемого равенства, принимают одинаковые значения при 97 Игошнн одинаковых наборах значений аргументов. А это означает, что функции (х у) . г и х. (у. г) действительно равны. Составлением аналогичных таблиц может быть доказана и ассоциативность дизъюнкции. Ассоциативность означает, что при многократном применении дизъюнкции или конъюнкции результат не будет зависеть от последовательности их применения, и потому все скобки, обозначающие эту последовательность, могут быть опушены. Так, будем писать х у г вместо (х у) . г, а также вместо х (у г), или — хмумг вместо (хм у) жги вместо хм(уч г).
Точно так же будем писать х . у . г г вместо каждой из следующих равных между собой булевых функций: ((х. У) . г) . г = (х (у г)) =х. (у. (г г))=х. ((у г) г)=(х.у) (г г). Аналогичнымобразом будет использоваться запись х и у и г и г и т. д. г) Свойства сразу следуют из таблиц для дизъюнкции и коньюнкции. Первое свойство означает, что дизъюнкция любого элемента с элементом 1 дает снова элемент 1 (подобно тому как в арифметике умножение любого числа на нуль дает нуль). Второе свойство говорит о том, что относительно конъюнкции элемент 1 играет роль «нейтрального» элемента, т.е. такого элемента, коньюнкция которого с любым элементом не меняет его. д) Аналогично двум предыдущим свойствам, эти свойства также легко вытекают из таблиц для дизъюнкции и конъюнкции. Здесь первое свойство говорит о «нейтральности» элемента О относительно дизъюнкции. е) Для доказательства этих равенств можно воспользоваться рассмотренным выше методом таблиц, но можно использовать и ранее доказанные соотношения.
Проверим, например, первое равенство. При х = 1 его левая часть в силу свойств г) и б) равна 1 и (у . г) = 1, а правая, всилутехже свойств,равна(1му) (1мг) =1 1=1. Если же х = О, то левая часть доказываемого равенства становится, в силу свойств д) и б), равной О м (у г) = у . г; но тому же самому становится равной и правая часть: (О и у) . (О и г) = у . г. Следовательно, функции х и (у г) и (х м у) (х и г) при одинаковых значениях аргументов дают равные значения, т.е. они равны. Совершенно аналогичным путем можно доказать и второе тождество дистрибутивности. Вместо слова «дистрибутивность» иногда употребляется термин «распределительность». Отметим, что в обычной арифметике умножение дистрибутивно (распределительно) относительно сложения: х (у+ г) = х у+ х .
г, но сложение, конечно, не дистрибутивно относительно умножения: х+ (у . г) ~ ~ (х+ у) (х+ г). Для булевых операций (функций) не только коньюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции. ж) Снова при доказательстве можем пользоваться уже установленными свойствами. В самом деле, при у = О левая часть первого равенства превращается в х и (О х) = х и О = х, т.е. равна правой. 98 Если же у = 1, то левая часть рассматриваемого соотношения равна х~ (1 х) =х гх=х, т.е. снова равна его правой части. Следовательно, первое равенство доказано. Аналогично проверяется второе равенство. э) Для доказательства второго равенства положим сначала, что х = О.
Тогда его левая часть будет равна (О у)' = 0' = 1, а правая— 0' г у' = 1 ы у' = 1. Если же х = 1, то левая часть доказываемого тождества превратится в (1 у)' = у', а его правая часть — в 1' ы у' = = 0 г у' = у'. Следовательно, равенство выполняется. Аналогично проверяется первое равенство.
и) Если х = 1, то 1 ы !' = ! . Если х = О, то 0 г 0' = 0 ~ 1 = ! . Таким образом, первое равенство справедливо. Аналогично проверяется второе равенство. к) Если х = 1, то 1" = (1')' = 0' = 1. Если х = О, то 0" = (О')' = 1' = О. Следовательно, х" = х. Теорема полностью доказана. П Свойства эквивалентности, импликации и отрицания. Свойства эквивалентности и импликации только частично аналогичны свойствам дизъюнкции или конъюнкции. Теорема 9.4. гТлл булевых функций справедливы следующие равенства: а) х ь+ х = 1, х +-> х' = 0; б) х с-ь у = у +-> х (коммутативность эквивалентности); в) (х с-+ у) с-> г = х с-ь (у <-ь г) (ассоциативность эквивалентности); г) 1~-+х=х, 0<-ьх=х'; д) х' с-+ у' = х ~-» у; е) х'-ьу'=у — >х; эк) х — >х= 1; з) х -ь х' = х', и) х' -ь х = х; к) 1 -ь х = х; л) 0 -ь х = 1; м) х ь 1 = 1; н)хьО=х'.
Доказательство этих соотношений не представляет труда. Предлагается проделать их самостоятельно с помощью таблиц. П Заметим, что импликация не обладает ни свойством коммугативности, ни свойством ассоциативности. Предлагается самостоятельно исследовать вопрос о том, будут ли эквивалентность и импликация дистрибугивны (распределительны) одна относительно другой справа и слева. Некоторые дополнительные свойства булевых функций рассмотРены в Задачнике (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
