Читайте также:
|
|
x ’ = x ®0 = x | x = x ¯ x = 1Å x; (1)
xy = (x ’Ú y ’)’ = x ’¯ y ’ = (x ¯ x)¯(y ¯ y); (2)
x Ú y = (x ’ y ’)’ = x ’® y = =(x ® y)® y = x ’| y ’ = (x | x)|(y | y); (3)
x ® y = x ’Ú y; (4)
x «y = (x ® y) (y ® x) = xy Ú x ’ y ’; (5)
x Å y = xy ’Ú x ’ y. (6)
Примеры
1. Доказать, что:
а) (x Ú y) ’ = x’y’ (закон де Моргана); б) x ’¯ y ’ = xy.
Решение. Построим таблицы значений:
xyx ’ y ’ x Ú y а) ( x Ú y )’ x ’ y ’ б) xyx ’¯ y ’
0 0 1 1 0 1 1 0 0
0 1 1 0 1 0 0 0 0
1 0 0 1 1 0 0 0 0
1 1 0 0 1 0 0 1 1
Равенства последних столбцов (правая и левая части соответствующих уравнений) и доказывают истинность.
2. Доказать, что (xy’)¯(y Å x’) = x’y.
Решение. Способ I. Строим таблицы значений:
xyx ’ y ’ xy ’ y Å x ’ ( xy ’)¯( y Å x ’) x ’ y
0 0 1 1 0 1 0 0
0 1 1 0 0 0 1 1
1 0 0 1 1 0 0 0
1 1 0 0 0 1 0 0
Способ II. Упростим левую часть, используя свойства функций: (xy’)¯(y Å x’) =|избавимся от ¯, используя x ¯ y = x’y’ согласно (2)| = (xy’) ’ (y Å x’) ’ =|применим закон де Моргана для первого сомножителя и тождество (6) для второго| = (x’ Ú y)(yx’’ Ú y’x’) ’ =|несколько раз применим з-н де Моргана для второго сомножителя, предварительно заменив x’’ = x | =(x’ Ú y)((yx) ’ (y’x’) ’)=(x’ Ú y)(y ’Ú x ’)(y Ú x)=| перемножим две последние скобки|=(x’ Ú y)(yy’ Ú yx’ Ú xy’ Ú xx’)=|учитывая, что yy’ = xx’ =0, опустим данные слагаемые и раскроем оставшиеся скобки|=(x’ Ú y)(yx’ Ú xy’)= yx’x’ Ú yyx’ Ú xx’y Ú yxy’ = yx’ Ú yx’ Ú0Ú0= yx’.
3. Установить, дистрибутивно ли сложение Å относительно умножения Ù.
Решение. Закон дистрибутивности означает, что справедливо тождество: (x Å y) z = xz Å yz (по умолчанию умножение выполняется первым). Упростим левую и правую части уравнения:
1) (x Å y) z =(x’y Ú xy’) z = x’yz Ú xy’z;
2) xz Å yz =((xz) ’yz)Ú(xz (yz) ’)=((x’ Ú z’) yz)Ú(xz (y’ Ú z’))=
= x’yz Ú z’yz Ú xzy’ Ú xzz’ = x’yz Ú xzy’.
Сравнивая результаты упрощений, приходим к выводу о выполнении дистрибутивного свойства.
4. Установить, ассоциативна ли стрелка Пирса.
Решение. Ассоциативность стрелки Пирса означала бы справедливость равенства (x ¯ y)¯ z = x ¯(y ¯ z). Проверим тождественную истинность табличным способом:
x y z x ¯ y y ¯ z (x ¯ y )¯ z x ¯(y ¯ z )
0 0 0 1 1 0 0
0 0 1 1 0 0 1
0 1 0 0 0 1
0 1 1 0 0 0
1 0 0 0 1 1
1 0 1 0 0 0
1 1 0 0 0 1
1 1 1 0 0 0
Далее продолжать подсчет последнего столбца не требуется. Стрелка Пирса не ассоциативна.
Вопросы и упражнения для самостоятельной работы
1. Доказать тождества (1)–(6).
2. Для приведенных ниже функций установить, выполняются ли законы коммутативности и ассоциативности:
а) x | y; б) x ¯ y; в) x → y; г) x «y; д) x Å y.
3. Проверить свойство дистрибутивности:
а) (x Å y)Ú z =(x Ú z)Å(y Ú z); б) (x → y)Ú z =(x Ú z)→(y Ú z);
в) (x ¯ y)Ú z =(x Ú z) ¯ (y Ú z); г) (x | y) z =(xz)|(yz).
Дата добавления: 2015-04-11; просмотров: 33 | Поможем написать вашу работу | Нарушение авторских прав |