8.8 Вопросы для самопроверки.

1. Что такое алгоритм?

2. Перечислите основные свойства алгоритмов.

3. Назовите универсальные алгоритмические модели.

4. Дайте определение примитивно-рекурсивных функций.

5. Дайте определение частично рекурсивных и общерекурсивных функций.

6. Дайте определение машины Тьюринга.

7. Дайте определение и приведите примеры полиномиальных алгоритмов.

8. В чем выражается вычислительная сложность алгоритмов?

9. Какая задача считается труднорешаемой?

10. Что означает термин NP- полная задача?

9. Задачи и упражнения.

1. Доказать, что числовых булевых функций от n аргументов равно .

2. Проверить справедливость равенства .

3. Доказать справедливость равенства .

4. Доказать справедливость равенства .

5. Установить, является ли самодвойственной функция эквивалентности.

6. Привести пример монотонной функции, которая бы была линейной.

7. Привести пример самодвойственной функции, которая бы одновременно была линейной.

8. Доказать, что функция Шеффера и Вебба не являются ни линейными, ни монотонными, ни самодвойственными.

9. Определить число самодвойственных функций, зависящих от n аргументов.

10. Доказать полноту системы булевых функций, состоящей из дизъюнкции, константы 0 и эквивалентности. Образует ли эта система базис.

11. Образует ли базис система булевых функций, состоящая из импликации и константы 0?

12. Установить является ли полной система, состоящая из дизъюнкции, импликации и конъюнкции.

13. Какая система из одной 2-местной функции является полной? Найти все такие системы.

14. Построить формулу от трех переменных, которая принимает такое же значение как большинство переменных.

15. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~

~.

16. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~

~

17. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~

~

18. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~

~

19. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~

~

20. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~.

~

21. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~

~

22. Доказать тавтологию и указать соответствующие законы алгебры логики:

23. На основании каких законов логики получены следующие соотношения. Докажите их:

=

24.Сформулируйте следующие законы логики и докажите их:

а) Закон тождества

б) Закон противоречия

в) Закон двойного отрицания

25. Сформулируйте следующие законы логики и докажите их:

а) Закон исключенного третьего

б) Закон двойного отрицания

в) Закон контрапозиции

26.Сформулируйте следующие законы логики и докажите их:

а) Закон противоречия

б) Законы де Моргана

в) Закон силлогизма

27.Сформулируйте следующие законы логики и докажите их:

а) Закон идемпотентности

б) Законы де Моргана

в) Закон противоположности

28.Сформулируйте следующие законы логики и докажите их:

а) Законы ассоциативности

б) Дистрибутивные законы

в) Законы тавтологии

29.Сформулируйте следующие законы логики и докажите их:

а) Закон нулевого множества

б) Закон поглощения

в) Закон Корецкого

30.Сформулируйте следующие законы логики и докажите их:

а) Закон тождества

б) Закон контрапозиции

в) Законы де Моргана