IV.Специальные бинарные отношения
1. Доказать, что если отношения r1 и r2 рефлексивны, то рефлексивны и отношения: r1Èr2, r1Çr2, r1-1, r1·r2.
2. Доказать, что если отношения r1 и r2 иррефлексивны, то иррефлексивны и отношения: r1Èr2, r1Çr2, r1-1. Показать, что композиция r1·r2 иррефлексивных отношений может не быть иррефлексивной.
3. Доказать, что если отношения r1 и r2 симметричны, то симметричны и отношения: r1Èr2, r1Çr2, r1-1, r1·r1-1.
4. Доказать, что композиция симметричных отношений r1 и r2 симметрична тогда и только тогда, когда r1 · r2 = r2 · r1.
5. Доказать, что если отношения r1 и r2 антисимметричны, то антисимметричны и отношения: r1Çr2 и r1-1, а объединение r1Èr2 антисимметричных отношений на А антисимметрично тогда и только тогда, когда r1Çr2-1 Í IА.
6. Построить бинарное отношение, симметричное и транзитивное, но не рефлексивное. Доказать, что если r есть транзитивное и симметричное отношение на множестве А и domr È rngr = A, то r есть эквивалентность на А.
7. Доказать: что любое бинарное отношение, являющееся одновременно симметричным и антисимметричным, транзитивно.
8. Доказать что бинарное отношение r на множестве А является одновременно эквивалентностью и частичным порядком тогда и только тогда: когда r= IА.
9. Пусть А - множество всех прямых на плоскости. Являются ли эквивалентностями следующие отношения:
9.1. параллельности прямых,
9.2. перпендикулярности прямых?
10. Доказать, что отношение равномощности множеств есть эквивалентность. Что является классами эквивалентности в этом случае?
|
|
11. Пусть £ и < на множестве N= {1,2,3,...} определены обычным образом. Доказать, что
11.1. <·<¹<;
11.2. £·<=< ;
11.3. £·³=N2.
12. Доказать, что если r1Ír2 , то
12.1. q·r1 Í q·r2 ;
12.2. r1·qÍr2·q;
12.3. r1-1 Í .r2-1.
13. Пусть I-универсум. Доказать, что Р(I) частично упорядочено отношением включения Í.
14. Пусть аrbÛа, bÎN и а делитель b. Доказать, что r - частичный порядок на N.
V. Функции алгебры логики
1. Построить таблицу истинности для формулы и, используя правила равносильных преобразований формул, привести ее к ДНФ и к КНФ, построить полином Жегалкина. Проверить правильность выполненных преобразований с использованием диаграмм Вейча. Найти существенные переменные функции, заданной формулой
1.1.
1.2.
1.3. (x®y)¯(y«z);
1.4. (x|(x&y)) ®`z;
1.5. (x®y) Å (x|z);
1.6. (x¯z) ® ( `yÅz);
1.7. (`x«(yÚz)) Å (x&`z);
1.8. ( xz Ú(y¯x)) | (x®y);
1.9. (x |`y) ® (z Å`x);
1.10. (`xÅ(y®z)) « yz;
1.11. (x &`y) ®(y¯z);
1.12. (x«(y¯z))®z;
1.13. (z|y)«(xÅyz);
1.14. (x|z)®(y Å`x);
1.15. (x«(z|y))Åxz;
1.16. (yÅxz)«(y |`z);
1.17. (x |`z)®(x«y);
1.18. (`z®(x &`y) | (`x & z);
1.19. (`xÅ(z &`y))®(x ¯`y);
1.20. (x®`y¯z) Å `x;
1.21. `xÅ((x ®`z)|y);
1.22. (y®(`x¯z))«xz;
1.23. (`z|y)®(x «`y);
1.24. (x ¯`y)«(z &`x).
|
|
2. Определить СДНФ, СКНФ, СПНФ для функции, заданной вектором:
2.1. a f= ( 1001 0110 1011 0011);
2.2. a f =(0001 0101 0110 1001);
2.3. a f =(1000 1101 0101 0110);
2.4. a f =(0010 0111 1100 0111);
2.5. a f =(1100 1001 0011 0110);
2.6. a f =(0001 1000 0101 1011);
2.7. a f =(1100 1001 1011 1110);
2.8. a f =(0101 0010 1011 0110);
2.9. a f =(0111 0100 1011 0010);
2.10. a f =(1100 0101 1011 0011);
2.11. a f =(0100 1111 1011 1010);
2.12. a f =(0001 0110 1001 1110);
2.13. a f =(1100 0111 1011 0001);
2.14. a f =(0110 0110 0001 0111);
2.15. a f =(0000 1000 0110 1111);
2.16. a f =(1111 0100 1101 0001);
2.17. a f =(0000 0111 1101 0001);
2.18. a f =(0101 0010 1001 1101);
2.19. a f =(1011 1100 0000 0100);
2.20. a f =(0010 1001 0100 1000);
3. Реализовать формулы системы D формулами над множеством связок S
3.1. D = { &,®,Å }, S = {` ,Ú };
3.2. D = {&,®,Å}, S = {|};
3.3. D = {&,®,Å}, S = {¯};
3.4. D = {&,®}, S = {Å, 1, &};
3.5. D= {Ú,®,Å}, S = {|};
3.6. D = {Å,Ú,«}, S = {| };
3.7. D = {1,&,Å}, S = {`x,®};
3.8. D= {«,Æ,&}, S = {`x,®};
3.9. D = {`x,1}, S = {Æ,®};
3.10.D = {`x,&}, S = {1,Å,Ú};
3.11.D= {Ú}, S = {®};
3.12.D = {`x,&,®}, S = {|};
3.13.D = {`x,&,Ú} , S = {¯};
3.14.D = {|}, S = {¯};
3.15.D = {¯}, S = {Æ,®}.
4. Определить все функции, являющиеся суперпозициями функций из D:
4.1. D = {Å,1};
4.2. D ={xyÅ(xÚy)}.
5. Доказать, что функция штрих Шеффера коммутативна, но не ассоциативна.
6. Доказать, что функция стрелка Пирса коммутативна, но не ассоциативна.
7. Доказать справедливость тождеств:
|
|
7.1.
7.2.
7.3.
7.4.
8. Найти вектор функции f, являющейся суперпозицией функций f1, f2, f3, если функциональным символам f1, f2, f3 сопоставлены булевы функции, определяемые соответственно векторами (10), (1011) и (1000):
8.1. f = f2 ( f1 (f3 (x, f1(y)), y);
8.2. f = f3 (f1 (f2 (x, y)), f3(x, f1( y)));
8.3. f = f1 (f2 (x, f3 (f2 (x, y), f1 (y)))).
9. Найти число булевых функций , для которых СКНФ является одновременно ДНФ.
10. Найти длину СДНФ функции :
10.1.
10.2. = (x1Úx2Ú ... Úxn) (`x1Ú`x2Ú ... Ú`xn);
10.3. = (x1Úx2Úx3)(`x1Ú`x2 Ú`x3)Å x4Å x5 Å ... Å xn.
11. Построить СКНФ булевой функции трех переменных, которая истинна тогда, когда ровно две переменные ложны.
12. Доказать, что если f1,f2 ÎP2 и f1&f2=0 то f1Úf2=f1Åf2.
13. Указать булеву функцию, для которой длина полинома Жегалкина в 2n превышает длину ее СДНФ.
14. Доказать теорему Шеннона о разложении булевой функции по переменным. Следствия о разложении булевой функции по одной и по всем переменным.
15. Доказать теорему о возможности представления булевой функции в СКНФ.
Дата добавления: 2019-03-09; просмотров: 291; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!