Задача о суммах элементов подмножеств

Пусть у нас есть множество объектов различных размеров и некоторая положительная верхняя граница L. В задаче оптимиза­ции нам необходимо найти набор объектов, сумма размеров которых наиболее близка к L и не превышает этой верхней границы. В задаче принятия решения нужно установить, существует ли набор объектов с суммой размеров L. Это упрощенная версия задачи об упаковке рюк­зака.

Задача об истинности КНФ-выражения

Конъюнктивная нормальная форма (КНФ) представляет собой по­следовательность булевских выражений, связанных между собой опера­торами AND (обозначаемыми ), причем каждое выражение является мономом от булевских переменных или их отрицаний, связанных опе­раторами OR (которые обозначаются через ). Вот пример булевского выражения в конъюнктивной нормальной форме (отрицание обознача­ется чертой над именем переменной):

.

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

Задача планирования работ

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

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

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.Сформулируйте следующие законы логики и докажите их:

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

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

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