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; просмотров: 200; Мы поможем в написании вашей работы!






Мы поможем в написании ваших работ!