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

При оперировании с функциями алгебры логики бывают полезны следующие эквивалентности (большинство из них называют обычно основными эквивалентностями алгебры логики). Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:

1. – коммутативность связки *, где символ * является общим обозначением для связок &, Ú, Å, ~, |, ¯.

2. – ассоциативность связки *, где *– общее обозначение для связок &, Ú, Å, ~.

3. Дистрибутивность

а) – дистрибутивность конъюнкции относительно дизъюнкции;

б) – дистрибутивность дизъюнкции относительно конъюнкции;

в) – дистрибутивность конъюнкции относительно сложения по mod 2.

4. а) ; б) суть правила де Моргана;

5. а) ; б) суть правила поглощения;

6. а) ; б) ;

7. а) ; б) ;

в) ; г) ; д) ;

8. а) ;

б) ; в) ;

9. а) ; б) .

 

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

1) , ;

2) ,

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

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

 

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

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) ;

11) .

 

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)фиктивные переменные x ₁ и x ₃.

 

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

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. Используя дистрибутивный закон и эквивалентности и перейти от заданной ДНФ функции к ее КНФ:

1)

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. Построить множество всех функций, зависящих от переменных x ₁, x ₂ и принадлежащих замыканию множества А:

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. Сведением к заведомо полным системам в P ₂ показать, что множество А является полной системой в P ₂:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

 

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

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 множеству T ₁\ T ₀:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

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

 

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

1) ;

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

16)

17)

18)

19)