2.8. Задачи и упражнения по функциям алгебры логики

, ;

,

, ;

, ;

, ;

, ;

, ;

, ;

, ;

, .

Ответы: 2), 6), 9), 10) – эквивалентны; 3), 7) – не эквивалентны.

2. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:

;

;

;

;

;

;

;

;

;

;

.

3. Используя приведенные выше основные эквивалентности и соотношения докажите эквивалентность формул V и U:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

Ответы:

4) ;

9)

4. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выясните, является ли функция G двойственной к функции F:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , ;

11) , ;

12) , .

Ответы: 4) , . Значит, G не двойственна к F. 6) – не является; 8),9),11) – является.

5. Используя принцип двойственности, постройте формулу, реализующую функцию, двойственную к функции F, и убедитесь в том, что полученная формула эквивалентна формуле V:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

Ответы:

1)

2) ; 5) ; 10) .

6. Указать все фиктивные переменные у функции F:

1)

2)

3)

4)

5)

6)

Ответы:1)две фиктивные переменные; 3)одна фиктивная переменная; 5)фиктивные переменные X1 и X3.

7. Показать, что X1 – фиктивная переменная у функции F (реализовав для этой цели функцию F формулой, не содержащей явно переменную X1):

1) ;

2) ;

3) ;

4) 5) 6) 7)

8) 9) 10)

Ответы: 4),8),10) 9)

8. Выяснить, можно ли из функции F , отождествляя и переименовывая в ней переменные, получить функцию G:

1) ,

2) ,

3) ,

4) ,

5) ,

6) ,

7) , ;

8) , ;

9) , ;

10) , .

Ответы: 1),2),5),7),8),9),10)можно. 3),4),6)нельзя.

9. Представить в СДНФ следующие функции:

1) ;

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 2) ; 4) , 7)

10. Представить в СКНФ следующие функции:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1) ; 2) ; 6) ; 8)

11. С помощью эквивалентных преобразований построить ДНФ функции

:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы:

4)

10)

12. Используя эквивалентные преобразования, построить КНФ функции

:

1)

2) ;

3)

4)

5)

6)

7)

Ответы:

1)

3)

6)

13. Применяя преобразования вида и построить из заданной ДНФ функции ее совершенную ДНФ:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:

2)

5)

14. С помощью преобразований вида и построить из данной КНФ функции ее совершенную КНФ:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:

1)

5)

15. Используя дистрибутивный закон и эквивалентности и перейти от заданной КНФ функции к ДНФ:

1)

2)

3)

4)

5)

6)

7)

Ответы:

3)

6)

16. Используя дистрибутивный закон и эквивалентности и перейти от заданной ДНФ функции к ее КНФ:

2)

3)

4)

5)

6)

7)

8)

Ответы:

2)

5)

17. Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы:

1) 3) 6)

10)

18. Методом треугольника Паскаля построить полином Жегалкина для этой функции, если:

1) 2)

3) 4)

5) 6)

7) 8)

9) 10)

Ответы:

1) 4) 7)

19. Представив функцию формулой над множеством связок {&, }, преобразуйте полученную формулу в полином Жегалкина функции (используя эквивалентности ):

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы:

1)

3)

9)

20. Построить множество всех функций, зависящих от переменных X1,X2 и принадлежащих замыканию множества А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1) 2) 3)

4) 5) 6)

21. Покажите, что , выразив формулой над множеством А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1) 2) 3) 4) 5) 6) 7)

22. Выписать все попарно неконгруэнтные функции , принадлежащие замыканию множества А:

1) 2) 3) 4)

5) 6) 7) 8) 9) 10)

Ответы: 1) 2) 3) 4) 5)

23. Из полной для класса [A] системы выделить базис:

1) 2) 3) 4)

5) 6)

7) 8) 9) 10)

Ответы: 1) 2) 3) 4) 5)

24. Сведением к заведомо полным системам в P2 показать, что множество А является полной системой в P2:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1)система является полной в P2, поскольку всякая может быть представлена в виде ДНФ или КНФ. С другой стороны,

2) имеем Система полна, поскольку

3) имеем ;

4) имеем ;

5) имеем ;

25. Выяснить, является ли функция F самодвойственной:

1)

3)

5)

7)

2)

4)

6)

8)

9)

11)

13)

15)

10)

12) 14)

Ответы: 1),3),4),8),10) – является; 2),5),6),7),9) – не является.

26. Выяснить, является ли самодвойственной функция F, заданная векторно:

1)

3)

5)

7)

9)

11)

13)

15)

2)

4)

6)

8)

10)

12)

14)

Ответы: 1),3),5),6),7),8) – является; 2),4),9),10) – не является.

27. Выяснить, является ли множество А самодвойственным:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1),3),5-7),10) – является; 2),4),8),9) – не является.

28. Представив функцию F полиномом, выяснить, является ли она линейной:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 2),3),5),6),8),9)–является. 1),4),7),10)–не является.

29. Выяснить, является ли линейной функция F, заданная векторно:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1),3),4),5),7),8),9),10) – является; 2),6) – не является.

30. Доказать, что система А полна в L. Выяснить, является ли система A базисом в L:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1)с помощью суперпозиции из функции можно получить любую функцию вида , путем подстановки 1-любую функцию вида Система А является базисом;

2),3),4),5),7),8),9) – является; 6),10) – не является.

31. Выяснить, принадлежит ли функция F множеству T1\T0:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1),3),4),6),8),9) – является; 2),5),7),10) – не является.

32. Подсчитать число функций, зависящих от переменных X1,…,Xn и принадлежащих множеству А:

1) ;

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

16)

17)

18)

19)

20)

21)

22)

23)

24)

25)

26)

27)

28)

29)

30)

31)

32)

33)

34)

35)

36)

37)

38)

39)

40)

41)

42)

43)

44)

45)

Ответы: 1) ; 2) ; 3)22N; 4) ; 5) 6)2N; 7) ; 8) ; 9) ; 10) ; 15) 0.

33. Доказать, что:

Указание: если то если то

34. Выяснить, является ли множество А базисом в классе К:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

Ответы: 1)да. Имеем ;

2) А не является базисом в T1,так как ;

А не является базисом в T1,так как ;

А не является базисом в T1,так как ;

А не является базисом в T1,так как ;

А – базис в .

35. По вектору значений выяснить, является ли функция F монотонной:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 2),3),5),8) – является; 1),4),6),7) – не является.

36. Проверить, является ли функция F монотонной:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 1),2),4),6),7) – является; 3),5),8) – не является.

37. Выяснить, полна ли система функций:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 2),4),6) – полна; 1)нет, 3)нет, 5)нет,

38. Выяснить, полна ли система А функций, заданых векторами своих значений:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 3),5) – полна; 1)нет, 2)нет, 4)нет, 6)нет,

39. Выяснить, полна ли система А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Ответы: 1),4),6) – полна; 2)нет, 3)нет, 5)нет,

40. Проверить, является ли система функций А базисом в Р2:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы:1) нет, так как подсистема полна; 2) является; 3) не является, 4)нет, можно удалить

41. Из полной в Р2 системы А выделить всевозможные базисы:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 1) где

2)

42. Используя теоретико - множественные операции, выразить через известные замкнутые классы T0, T1, L, S, M и P2 замыкания множества А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

Ответы: 1)P2; 2) 3) 4) 5) 6)

43. Выяснить, можно ли расширить до базиса в Р2 множество А:

1)

2)

3)

4)

5)

6)

7)

8)

Ответы: 1) можно, – базис; 2) нельзя, функция x входит во все предполные классы; 3) можно, – базис; 4) нет, функции и принадлежат одним и тем же предполным классам.

44. Выяснить, полна ли система функций

1)

2)

3)

4)

Ответы: 1)вообще говоря, нет. Рассмотреть

2)да, имеем

3) вообще говоря, нет. Рассмотреть

4) вообще говоря, нет. Рассмотреть