БУЛЕВЫ ФУНКЦИИ

Основные определения и понятия темы

Булева функция одной переменной, виды булевых функций одной переменной (отрицание, тождественный 0, тождественная 1, тождественная функция), булева функция двух переменных, виды булевых функций двух переменных (конъюнкция, дизъюнкция, импликация, эквиваленция, сумма Жегалкина, стрелка Пирса, штрих Шеффера), булева функция n переменных, равносильные булевы функции, суперпозиция булевых функций, совершенная конъюнктивная форма булевой функции, совершенная дизъюнктивная форма булевой функции, булева функция, сохраняющая 1, булева функция, сохраняющая 0, двойственная булева функция, самодвойственная булева функция, полином Жегалкина, линейная булева функция, монотонная булева функция, полная система булевых функций.

Основные теоремы и утверждения темы

Теорема о числе булевых функций n переменных, основные равносильности булевых функций, теорема о разложении любой булевой функции в суперпозицию конъюнкции, дизъюнкции и отрицания, отнесенного к атому, алгоритмы построения СДНФ и СКНФ с помощью таблицы истинности, алгоритм построения полинома Жегалкина методом неопределенных коэффициентов, критерий полноты системы булевых функций.

Рекомендуемая литература

1.Конспект лекций О.Б. Лупанова по курсу «Введение в математическую логику». – М.: Изд-во ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. – 2007.

2.Игошин В.И. Задачник-практикум по математической логике. М.: Просвещение, 1986.

3.С.В. Судоплатов, Е.В. Овчинникова. Элементы дискретной математики. – Москва – Новосибирск, 2002.

Задание 6.1.Проверить эквивалентность булевых функций двумя способами:

· с помощью таблицы истинности;

· с помощью равносильных преобразований.

1. и ;

2. и ;

3. и ;

4. и ;

5. и ;

6. и ;

7. и ;

8. и ;

9. и ;

10. и ;

11. и ;

12. и ;

13. и ;

14. и ;

15. и ;

16. и ;

17. и ;

18. и ;

19. и ;

20. и .

Задание 6.2.Найти СДНФ и СКНФ булевой функции двумя способами:

· с помощью таблицы истинности;

· с помощью равносильных преобразований.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 6.3.Построить полином Жегалкина для булевой функции методом неопределенных коэффициентов. Является ли данная функция линейной?

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 6.4.Построить функцию, двойственную к булевой функции . Проверить, эквивалентна ли полученная формула функции .

1. ;

2. ;

3. ;

4. ;

5. ;

6. , ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 6.5.Выяснить, является ли булева функция монотонной.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

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

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 6.7.Упростить релейно-контактную схему. Найти ее функцию проводимости.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.