Читайте также:
|
|
1. Проверить принадлежность каждому из классов P 0, P 1, S, L, M функций Ú иÅ.
Решение. Выпишем соответствующие таблицы истинности:
xy | Ú Å
0 0 | 0 0
0 1 | 1 1
1 0 | 1 1
1 1 | 1 0
P 0: Из первой строки видно, что дизъюнкция и сложение Å сохраняют 0. Следовательно, Ú,ÅÎ P 0;
P 1: Из последней строки видно, что дизъюнкция сохраняет 1, а сложение Å – нет. Следовательно, ÚÎ P 1, а ÅÏ P 1.
S: Для проверки принадлежности к классу S необходимо сравнить прямую и двойственную функции.
Способ I. Для дизъюнкции имеем f *=(x Ú y)*= xy. Но
x Ú y ¹ xy, следовательно ÚÏ S.
Способ II. Для сложения Å воспользуемся таблицей:
x y | Å Å*
0 0 | 0 1
0 1 | 1 0
1 0 | 1 0
1 1 | 0 1
Последний столбец для двойственной функции был получен по следующему правилу: столбец функции инвертируется (замены 0«1), полученные значения записываются в инвертированные строки. Например, строка 0 1 ú 1 для Å превращается в строку 1 0ú 0 для Å*.
Из полученной таблицы следует, что ŹÅ*, т.е. ÅÏ S.
L: Представим исследуемые функции через 1, Ø и Å.
Для дизъюнкции имеем:
x Ú y =(x ’ y ’)’=((1Å x)(1Å y))’=1Å((1Å x)(1Å y))=
=1Å(1Å x Å y Å xy)= x Å y Å xy.
Здесь мы воспользовались законом де Моргана, тождеством x ’=1Å x, дистрибутивностью сложения Å относительно Ù и ассоциативностью Å (’’привычные’’ правила раскрытия скобок).
Полученное выражение содержит нелинейное слагаемое xy. Отсюда следует, что ÚÏ L.
Для сложения по модулю два имеем: f = x Å y – линейная функция. Значит, ÅÎ L.
M: Вернемся к таблицам истинности обеих функций (см. пункт P 0). Необходимо сравнить значения функции для каждой сравнимой пары аргументов. Мы видим, что дизъюнкция монотонна, а Å — не монотонна. Следовательно, ÚÎ M, ÅÏ M.
2. Найти линейную булеву функцию f (x, y, z), удовлетворяющую условиям: f (1,0,0)=1, f (0,1,0)=1, f (1,1,1)=0 и f (1,1,0)=0.
Решение. Будем искать линейную функцию в виде
f (x, y, z)=a0Åa1 x Åa2 y Åa3 z.
Указанные условия приводят к системе линейных булевых уравнений
Воспользуемся методом Гаусса, учитывая, что 1Å1=0:
.
Следовательно, a0=0, a1=1, a2=1 и a3=0, т.е. f (x, y, z)= x Å y.
Вопросы и упражнения для самостоятельной работы
7. Проверить принадлежность каждому из классов P 0, P 1, S, L, M следующих функций: a) Ù, б) ¯, в) Ø.
8. Найти все булевы функции двух переменных, принадлежащие а) классу M, б) классу S.
9. Принадлежит ли классу L функция а) xy, б) x ½ y, в) x «y.
10. Построить булеву функцию, не принадлежащую ни одному из классов P 0, P 1, S, L, M.
11. Монотонны ли следующие функции:
а) x Ú yz, б) x ¯(y Ú z), в) x ’ y Ú(xy ’Å z).
12. Найти линейную булеву функцию f (x, y), удовлетворяющую условиям:
а) f (0,1)=1, f (1,0)=0 и f (1,1)=0;
б) f (1,0)=0, f (0,1)=1 и f (1,1)=1.
13. Найти линейную булеву функцию f (x, y, z), удовлетворяющую условиям:
а) f (0,1,0)=1, f (0,0,1)=0, f (1,1,1)=1 и f (1,0,1)=1;
б) f (0,0,1)=0, f (0,1,0)=1, f (1,1,1)=1 и f (1,1,0)=1.
Дата добавления: 2015-04-11; просмотров: 24 | Поможем написать вашу работу | Нарушение авторских прав |