22. Примеры задач np-класса.

Задача о выполнимости.

Пусть х1, х2, …, хn – множество логических переменных; x , x ,..., xn 1 2 – их

отрицания или дополнения.

if xi = true then i x = false

- И; - ИЛИ.

Дизъюнкция: х1 х5 x2 …

Конъюнкция: х4 х3 x2 …

Конъюнктивная нормальная форма:

E*(x1, …, xn) = (x1 x2 x3) (x1 x2 x4 ) ( 3 x x4) ( x1 ) (*)

Задача о выполнимости заключается в определении, является ли

булевская функция, записанная в КНФ, выполнимой.

Любая булевская функция может быть представлена в КНФ по правилу

Де Моргана:









A B A B

A B A B

А(ВС)=( АВ)(АС)

Говорят, что булевская функция выполнима, если существует некоторое

присваивание переменным true или false, при этом функция должна быть

равна true.

Для функции (*) она будет выполнима, если ввести следующие

присваивания:

(*)







x true

x x x false

3

1 2 4

Например:

Функция

f2(xi)=(x1 x2)( x1 )( x2 )

не является выполнимой, т. к. при любых xi f2(xi)=false.

Теорема:

Задача о выполнимости является NP-полной.

for i=1 to N do

xi выбор (true, false)

if E(x1, x2, …, xN) then успех

else неудача

Используя преобразование задачи Р1 в Р2, можно показать, что даже

ограниченный случай задачи о выполнимости является NP-полным.

К-выполнимость.

К-выполнимость означает, что любой дизъюнкт, входящий в КНФ,

содержит не более К логических переменных.

36

Минимальный случай К=3. Для булевской функции, представленной в

КНФ, за полиномиальное время можно найти функцию Е*(х2), содержащую не

более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если

выполнима Е*.

E*(x1, x2,…, xn)E*(xi)

Для этого используется метод уменьшения порядка дизъюнкта

(1 2 …k)=(1 2 z) (3 4 …k z )

Применяя итерационный процесс разложения, можно получить Е*.

Найти алгоритм решения Е* проще, чем функции Е. Но при этом доказав

выполнимость Е*, докажем выполнимость исходной функции Е.

Частный случай: при К=2 функция Е входит в Р.

Примерами задач NP-класса могут послужить также задачи на графах:

1) Определение максимума клик неориентированного графа (NP-

трудная задача).

2) Задача определения полного подграфа (NP-полная задача).

3) Определение вершинного покрытия мощности L для

неориентированного графа (NP-полная задача).

4) Определение максимума вершинных покрытий

неориентированного графа (NP-трудная задача).

5) Задача определения существования Гамильтонова цикла для

графа (NP-полная задача).

6) Задача коммивояжера: определение оптимального движения по

графу с единым вхождением в каждую вершину (NP-трудная задача).

Задача составления расписания (NP-полная задача).

37

24. Дедуктивные теории

Дедукция (от латинского deductic - выведение) - форма мышления, когда

заключение выводится чисто логическим путем (т.е. по правилам логики) из

некоторых данных посылок.

Индукция (от латинского inductio - наведение) - форма мышления, посред-

ством которой от некоторых фактов или истинных высказываний переходят к

некоторой гипотезе (общему утверждению).

Примеры дедуктивных рассуждений.

1. Все люди смертны. Сократ – человек. Следовательно, Сократ смертен.

2. 5> 3, 3 >1, следовательно, 5 >1.

Примеры индуктивных рассуждений.

1. График функции y=2x+3 прямая, график функции y=3x+1 прямая, сле-

довательно, функции вида y=kx+b имеют графиком прямую. Полученная

здесь гипотеза оказывается истинной.

2. Рассмотрим предположение Ферма, что число р= +1 является про-стым для

всех n. При n=0,1,2,3,4 получим, что р равно 3, 5, 17, 257, 65537 и все они

простые числа. Но Эйлер показал, что для n=5 р= 4 294 967 297 и это число

является составным (делится на 641). Следовательно, это предположение

Ферма не верно. n22

2. Возьмем формулу Эйлера N=x2+x+41. При каждом x=1,2,3,...,39 число N

является простым, следовательно, числа N, указанного вида, являются

просты-ми. Сформулированная здесь гипотеза неверна, например, при х=40

число N=412, следовательно, оно не является простым.

Таким образом, заключение, полученное дедуктивным способом, уже не

нуждается в доказательстве. Заключение, полученное индуктивным

способом, требует доказательства его истинности. Будем рассматривать

дедуктивные ме-тоды. Введем понятие дедуктивной теории.

Дедуктивная теория считается заданной, если задан язык этой теории и из

множества правильно построенных выражений (предложений, называемых

формулами) языка выделено дедуктивным образом множество теорем. Под-

робнее, дедуктивная теория считается заданной, если:

1). Задан алфавит и правила образования выражений (слов) в этом алфа-

вите.

2). Заданы правила образования формул (правильно построенных выра-

жений) языка.

3). Из множества всех формул языка выделено некоторым дедуктивным

способом (который будет описан ниже) подмножество Т, элементы которого

будем называть теоремами. В зависимости от того, как задано это подмноже-

ство Т, будем различать получающиеся при этом дедуктивные теории.

Подмножество Т может задаваться одним из следующих способов.

I. Задаются аксиомы и конечное число правил выводов, т.е.

а) из множества формул (правильно построенных выражений) выделяется

подмножество А, элементы которого называются аксиомами (аксиом может

быть как конечное число, так и бесконечное),

б) задается конечное число правил выводов, используя которые, и только их,

из аксиом можно некоторым образом получать теоремы (подробнее этот

вопрос будет изучаться в следующих параграфах).

38

Если теоремы заданы указанным образом, т.е. заданием аксиом и конеч-ного

числа правил вывода, то эта дедуктивная теория называется формальной

аксиоматической теорией или формальным (логическим) исчислением.

Особо отметим, что аксиомы лишь задаются, поэтому их часто называют

скрытыми определениями. Бытующее мнение, согласно которому аксиомы

принимаются без доказательств, не совсем точно передает суть дела.

Аксиомы не доказываются не потому, что могут не доказываться, а

потому, что не могут быть доказаны.

II. Задаются только аксиомы, а правила вывода считаются известными, т.е.:

а) из множества формул (правильно построенных выражений) выделяется

подмножество А, элементы которого называются аксиомами (аксиом может

быть как конечное число, так и бесконечное),

б) правила вывода (методы доказательства) теорем считаются известными из

опыта изучения математики.

При таком задании теорем дедуктивной теории, говорим, что задана по-

луформальная аксиоматическая теория.

III. Аксиом нет, а задается только конечное число правил выводов, с по-

мощью которых и получают теоремы. Такую дедуктивную теорию называют

теорией естественного вывода.

Случай, когда нет аксиом и нет правил вывода, не рассматривается в ло-гике.

Применяя один из указанных выше способов задания теорем, будем полу-

чать множества теорем Т1, Т2 и Т3 соответственно. Сразу возникают вопросы:

когда эти множества Т1, Т2, и Т3 совпадают? Когда некоторые из Т1, или Т2, или

Т3 дедуктивной теории B совпадают или покрывают класс "истинных" формул

теории B1, при условии совпадения для B и B1, алфавитов и формул. Эти во-

просы оказываются не всегда простыми и в рамках этого курса затрагиваются

незначительно .

39