![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
6.1. Сколько существует различных булевых функций от одной переменной? Составьте таблицы значений всех булевых функций от одной переменной. Выразите эти функции через отрицание и основные булевы функции от двух переменных.
6.2. Сколько существует различных булевых функций от двух переменных? Составьте таблицы значений каждой из них. Выразите эти функции через отрицание и основные булевы функции от двух переменных.
6.3. Постройте таблицы значений для следующих булевых функций:
а) f(x,y)=((x®y)Ùùy)®ùx;
б) f(x,y,z)=(((x®(yÚz))Ùù(yÙz))®x;
в) f(x,y,z)=ùx®(z«(y+(xÙz)));
г) f(x,y,z)=(((x/y)¯z)/y)¯z;
д) f(x,y,z)=((xÚùy)®z)Ù((x/y)«ùz).
6.4. Построив таблицы значений, выясните, равны ли следующие булевы функции:
a) f(x,y,z)=((xÚy)Úz)®((xÚy)Ù(xÚz)),
g(x,y,z)=x«z;
б) f(x,y,z)=(ùxÚy)Ù(yÚz),
g(x,y,z)=(xÚyÚz)Ù(ùxÚyÚz)Ù(ùxÚyÚùz);
в) f(x,y,z)=(x®y)®z,
g(x,y,z)=x®(y®z);
г) f(x,y)=((x+y)®(xÚy))Ù((ùx®y)®(x+y)),
g(x,y)=x/y;
6.5. Покажите, что:
а) xÙy=ù(ùxÚùy);
б) x®y=ùxÚy;
в) x«y=(x®y)Ù(y®x)=(ùxÚy)Ù(xÚùy);
г) x+y=ù(ùxÚy)Úù(xÚùy);
д) x¯y=ù(xÚy);
е) x/y=ùxÚùy.
6.6. С помощью таблиц значений проверьте справедливость следующих формул:
а) ùx=x+1;
б) x+y=y+x;
в) (x+y)+z=x+(y+z);
г) xÙ(y+z)=xÙy+xÙz;
д) x+x=0;
е) 0+0=0;
ж) x+0=x;
з) 1+1=0.
6.7. Выразите с помощью суперпозиций функции Ú,®,«,+,/,¯ через функции Ù и ù.
6.8. Выразите с помощью суперпозиций функции Ú,Ù,«,+,/,¯ через функции ® и ù.
6.9. Выразите с помощью суперпозиций булевы функции ù,Ù,Ú,®«,¯,+ через штрих Шеффера /.
6.10. Выразите с помощью суперпозиций булевы функции ù,Ù,Ú,®,«,/,+ через стрелку Пирса ¯.
6.11. Докажите полноту следующих систем булевых функций:
а) {Ù,Ú,ù};
б) {Ú,ù};
в) {Ù,ù};
г) {®,ù};
д) {/};
е) {¯}.
6.12. Докажите, что нельзя с помощью суперпозиций выразить:
а) ù через Ù, Ú, ® и «;
б) Ù через Ú, ®;
в) ® через Ù, Ú;
г) Ù через ù, «;
д) «через Ù, Ú.
Решение: В каждом случае нужно обнаружить такое свойство выражающих функций, которое сохраняется при суперпозиции функций (и следовательно, которое будет присуще всякой функции, получающейся из данных функций в результате их суперпозиций), но которым не обладает выражаемая функция.
Например, в задача n.в каждая из функций Ù и Ú сохраняет 0, т.е. 0Ù0=0 и 0Ú0=0. Следовательно, всякая суперпозиция функций Ù и Ú будет функцией, сохраняющей 0. Но функция ® не сохраняет 0, т.к. 0®0=1.
6.13. Докажите неполноту следующих систем функций, т.е. в каждом случае укажите функцию, которая не выразима с помощью суперпозиций через функции данной системы:
а) {Ù,Ú,®};
б) {Ù}.
6.14. Докажите полноту системы {+, Ù, 1}.
6.15. Докажите, что любую булеву функцию можно представить в виде полинома Жегалкина (причем это представление единственно).
6.16. Постройте многочлен Жегалкина для функций:
а) x®y;
б) (x®y)Ù(y¯z);
в) (x/y)¯z;
г) ((x®y)Úz)/x;
д) (x«y)Ùz.
6.17. Для каждой булевой функции от двух переменных найдите двойственную ей булеву функцию.
6.18. Является ли функция g двойственной к функции f, если:
а) f=x+y g=x«y;
б) f=x®y g=y®x;
в) f=(xÙy)Ú(xÙz)Ú(yÙz) g=(xÙy)+(xÙz)+(yÙz);
г) f=x+y+z g=x+y+z;
д)f=(ùxÙùy)Ú(xÙ(y«z)) g(x,y,z)=(01101101)
6.19. Раскладывая функцию f в полином Жегалкина, выясните является ли она линейной:
а) f(x1,x2,x3)=((x1Ùx2)Ú(ùx1Ùùx2))+x3;
б) f(x1,x2)=x1Ùx2Ù(x1+x2);
в) f(x1,x2,x3)= ((x1®x2)Ù(x2®x1))«x3;
г) f(x1,x2,x3,x4)= (ùx1Ùx2)Ú(ùx2Ùx3)Ú (ùx3Ùx4)Ú(ùx4Ùx1);
6.20. Среди булевых функций от одного и двух аргументов найдите все функции, принадлежащие классам Т0, Т1, L, M, S.
6.21. Какие из перечисленных функций являются монотонными:
а) x®(x®y);
б) x®(y®x);
в) xÙyÙ(x+y);
г) (xÙy)+(yÙz)+(zÙx)+z;
д) f(x1,x2,x3)=(00110111);
е) f(x1,x2,x3)=(01100111).
6.22. Используя теорему Поста, выясните, полна ли система:
а) {+,Ú,1};
б) {x®y, x®ùyÙz};
в) {xÙùy, ùx«yÙz};
г) {(01101001),(10001101),(00011100)}.
Решение: а) Составим таблицу Поста.
В клетках таблицы будем писать знак «+» или «-» в зависимости от того, принадлежит рассматриваемая функция данному функционально замкнутому классу или нет.
f | T0 | T1 | S | L | M |
X+y | + | - | - | + | - |
XÚy | + | + | - | - | + |
- | + | - | + | + |
В силу теоремы Поста для полноты системы необходимо, чтобы в каждом столбце был хотя бы один минус.
Принадлежность функции x+y класса T0, L и непринадлежность классу Т1 очевидна. Эта функция не самодвойственная, т.к. (x+y)*=ù(ùx+ùy)=((x+1)+(y+1))+1=x+y+1. Функция x+y немонотонная, т.к. (1,0)£(1,1), а 1+0=1 и 1+1=0.
Функция xÚy, очевидно, принадлежит классам Т0 и Т1. Она несамодвойственная, т.к. двойственная ей функция есть хÙу. Она нелинейная, т.к. многочлен Жегалкина этой функции имеет вид xÚy=ху+х+у. Монотонность функции легко проверяется по ее таблице истинности.
Для функции, тождественно равной 1, таблица Поста заполняется тривиально.
Т.к. каждый столбец таблицы Поста содержит по меньшей мере один знак “-“, то система {+, Ú, 1} – полная.
Дата публикования: 2015-03-26; Прочитано: 832 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!