1 Дискретная математика Алгебра логики Институт проблем управления РАН, Лазарев Александр Алексеевич

2 План Функции алгебры логики Элементы комбинаторики Элементы теории графов Три контрольные работы (в редакторе ТеХ,

3 Рекомендуемая литература 1. Журавлёв Ю.И., Флёров Ю.А. Дискретный анализ. Часть I: Учебное пособие. – М.: МФТИ, Стэнли Р. Перечислительная комбинаторика. -М.: Мир, Липский В. Комбинаторика для программистов. - М.: Мир, Рыбников К.А. Введение в комбинаторный анализ. - М.: МГУ, Гаврилов Г.И., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. -М.: Наука, Риордан Дж. Введение в комбинаторный анализ. - М.: ИЛ, Холл М. Комбинаторика. - М.: Мир, Мендельсон Э. Введение в математическую логику.- М.: Наука, Дискретная математика и математические вопросы кибернетики/ Под ред. С.В.Яблонского, О.В.Лупанова, Т.1, -М.; Наука, Яблонский С.В. Введение в дискретную математику. -М.: Наука, Оре О. Теория графов. - М.: Наука, Кристофидис Н. Теория графов. Алгоритмический подход. -М.: Мир, Емеличев В.А., Мельников О.И. и др. Лекции по теории графов. М.: Наука, Уилсон Р.Дж. Введение в теорию графов. - М.: Мир, Харари Ф. Теория графов. - М.: Мир, Журавлёв Ю.И., Флёров А.А., Федько О.С., Дадашев Т.М. Сборник задач по дискретному анализу. – М.: МФТИ, Гжегорчик А. Популярная логика.- М.: Наука, Леонтьев В.К. Избранные задачи комбинаторного анализа. – М. Изд-во МГТУ им. Н.Э. Баумана, Лазарев А.А. Теория расписаний. Оценки абсолютной погрешности и схема приближённого решения задач теории расписаний: Учебное пособие. – М.: МФТИ, Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир. – Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М. – с.

4 Функции алгебры логики Джордж Буль ( ) Математический анализ логики, являющийся очерком, касающимся исчисления дедуктивных рассуждений, (1847 г.), Исследования законов мысли. на которых основываются математические теории логики и вероятностей, (1854 г.). Аугустус (Огастес, Август) де Морган ( ) Формальная логика или исчисление выводов, необходимых и возможных (1847 г.).

5 БУЛЬ, ДЖОРДЖ (Boole, George) ( ), английский математик. Родился 2 ноября 1815 в Линкольне. В возрасте 16 лет стал помощником учителя частной школы в Донкастере, в 1835 открыл собственную школу в Линкольне. В свободное время читал математические журналы, работы И.Ньютона, П.Лапласа и Ж.-Л.Лагранжа, начал вести самостоятельные алгебраические исследования. В 1839 написал первую научную работу Исследования по теории аналитических преобразований (Researches on the Theory of Analytical Transformations), которая была опубликована "Кембриджским математическим журналом" ("Cambridge Mathematical Journal"). В 1844 появилась его первая работа, где высказывалась идея объединения алгебры и логики, а в 1847 вышла в свет статья Математический анализ логики (The Mathematical Analysis of Logic), которая положила начало созданию "алгебры высказываний", получившей впоследствии название булевой алгебры. Благодаря этой публикации Буль в 1849 был назначен профессором математики Куинз-колледжа (Корк, Ирландия), где преподавал до конца жизни. В 1857 был избран членом Лондонского королевского общества. Основные идеи Буля суммированы в его работе Исследование законов мышления, на которых основаны математические теории логики и вероятностей (An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, 1854). Здесь впервые определено в явном виде исчисление классов (или множеств), введено обозначение для их пересечения, объединения и т.д., показано, что исчисление классов можно интерпретировать как исчисление высказываний. Булевы алгебры особые алгебраические системы, для которых определены две операции, нашли широкое применение в различных разделах математики: в теории вероятностей, топологии, функциональном анализе, а также в создании вычислительных машин. Умер Буль в Баллинтемпле (графство Корк, Ирландия) 8 декабря 1864.И.НьютонаП.ЛапласаЖ.-Л.Лагранжа

6 Огастес (Август) де Морган (англ. Augustus de Morgan, 27 июня 1806), Мадура, Индия 8 марта 1871, Лондон) шотландский математик и логик; профессор математики университетского колледжа в Лондоне ( , ); первый президент (1866) Лондонского математического общества.англ.27 июня1806МадураИндия8 марта 1871Лондонматематиклогикуниверситетского колледжа в Лондоне Лондонского математического общества Основные труды: по математической логике и теории рядов; к своим идеям в алгебре логики пришёл независимо от Дж. Буля; изложил (1847) элементы логики высказываний и логики классов, дал первую развитую систему алгебры отношений; с его именем связаны известные теоретико-множественные соотношения (законы де Моргана).математической логикетеории рядовДж. Буля1847 логики высказыванийлогики классовалгебры отношенийзаконы де Моргана

7 Функции алгебры логики. Табличное задание функций. Элементарные функции, их свойства, таблица операций, коммутативность, ассоциативность, дистрибутивность элементарных функций. Формулы и функции алгебры логики. Теоремы о разложении функций по одной и нескольким переменным. Совершенная дизъюнктивная нормальная форма. Задача о ВЫПОЛНИМОСТИ. Определение понятия NP-трудности задач. Функциональная полнота систем функций алгебры логики. Замкнутые классы. Пять предполных замкнутых классов T 0, T 1, L, S, M. Пересечение данных классов. Теорема о функции двойственной к суперпозиции. Критерий функциональной полноты систем функций алгебры логики (теорема Поста). Примеры полных систем функций алгебры логики. Основная лемма. Лемма о несамодвойственной функции. Лемма о немонотонной функции. Лемма о нелинейной функции. Следствия из критерия полноты.

8 Функции алгебры логики. Область определения логических или булевых переменных 0 и 1 Область значений функций также 0 и 1 Функция от одной переменной f(x) x f(x) x x 1

9 Операции над двумя переменными (двухместные, бинарные операции) x y x y x y x y x y x+y x|y x y n конъюнкция & и min(x,y) дизъюнкция max (x,y) импликация эквивалентность сумма по модулю 2 + штрих (Шеффера) | не x или не y стрелка (Пирса) не x и не y.

10 Индуктивное определение формулы: Пусть U - множество переменных. Тогда множество формул алгебры логики над U определяется следующим образом: 1. Всякая переменная - формула. 2. Константы 0 и 1 - формулы. 3. Если А - формула, то А (или в другой записи ) - формула. 4. Если А и В - формулы, то (А В), (А В), (А В), (А+В), (А В), (А В), (А В) - формулы. 5. Формулами являются те и только те выражения, которые могут быть получены из констант, переменных и логических связок за конечное число шагов 1- 4.

11 Определение. Функция от n переменных определенная на множестве и принимающая значения из множества {0, 1}, называется функцией алгебры логики или булевой функцией. F(x 1,x 2,x 3,…, x n ),

12 «Табличное» задание функции x 1 x 2... x n-1 x n f(x 1, x 2,... x n-1, x n ) f(0, 0,..., 0, 0) f(0, 0,..., 0, 1) f(0, 0,..., 1, 0) f(1, 1,..., 1, 1) 2 n

13 Алгебраические свойства элементарных операций 1. Коммутативность (или перестановочность) операции означает, что. Логическая операция коммутативна, если связка принадлежит следующему множеству связок (существенно только, чтобы символ в равенстве всюду имел один и тот же смысл):

14 2. Ассоциативность операции означает, что.Свойство ассоциативности позволяет записывать формулы, содержащие одинаковые ассоциативные связки, без скобок, например,. Логическая операция ассоциативна, если связка принадлежит следующему множеству связок (существенно только, чтобы символ в равенстве всюду имел один и тот же смысл):.

15 3. Дистрибутивность (распределительный закон) операции относительно операции означает, что. Дистрибутивность конъюнкции: - дистрибутивность конъюнкции относительно дизъюнкции; - дистрибутивность конъюнкции относительно суммы по модулю 2. Дистрибутивность дизъюнкции: - дистрибутивность дизъюнкции относительно конъюнкции; - дистрибутивность дизъюнкции относительно импликации; - дистрибутивность дизъюнкции относительно эквивалентности.

16 Дистрибутивность импликации: - дистрибутивность импликации относительно конъюнкции; - дистрибутивность импликации относительно дизъюнкции; - дистрибутивность импликации относительно импликации.

17 4. Имеет место следующее соотношение для двойного отрицания:

18 5. Имеют место следующие соотношения между отрицанием, конъюнкцией и дизъюнкцией: закон (правила) де Моргана. Указанные соотношения отражают отношение двойственности между дизъюнкцией и конъюнкцией.

19 6. Имеют место следующие соотношения, связанные с навешиванием отрицания на элементарные логические функции:

20 7.Константы могут быть выражены следующим образом:

21 8. Правила поглощения:

22 9. Выполняются следующие свойства конъюнкции и дизъюнкции:

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

24 Определение. Через P 2 (n) будем обозначать множество всех разных булевых функций размерности n. Теорема. Число p 2 (n) всех функций из P 2 (n), зависящих от переменных x 1, x 2,..., x n, равно.

25 Переменная x i (1 i n) функции f(x 1, x 2,...,x i-1, x i, x i+1,..., x n ) из P 2 (n)называется существенной, если можно указать такие наборы и значений переменных, что В противном случае переменную x i называют несущественной или фиктивной переменной функции f. Две функции f(x 1, x 2,...,x i-1, x i, x i+1,..., x n ) и g(x 1, x 2,...,x i-1, x i, x i+1,..., x n ) называются равными, если множества их существенных переменных совпадают и на любых двух наборах (x 1, x 2,...,x i-1, x i, x i+1,..., x n ) и (y 1, y 2,...,y i-1, y i, y i+1,..., y n ), различающихся быть может только значениями несущественных переменных, значения функций одинаковы: f(x)=g(y). Если f(x) и g(y) - равные функции, то одну из них можно получить из другой путем добавления и/или изъятия несущественных переменных.

26 8. Правила поглощения:

27 Разложение функций алгебры логики по переменным Чтобы иметь возможность единообразно записывать переменные с отрицанием и без отрицания введем следующее обозначение:

28 Легко видеть, что x = 1 тогда и только тогда, когда x =, то есть значение основания равно значению показателя.

29 Лемма. (О разложении функции по одной переменной). Пусть f(x 1,..., x n ) - произвольная функция алгебры логики, тогда справедливо следующее представление f в форме разложения по переменной x 1 : (2.1)

30 Доказательство. Отметим прежде всего, что представление (2.1), естественно, справедливо для произвольной переменной x i из множества переменных функции f. Для доказательства рассмотрим произвольный набор значений переменных ( 1,..., n ) и покажем, что левая и правая части соотношения (2.1) принимают на нем одно и то же значение. Рассмотрим набор значений переменных (1, 2,..., n ). Левая часть (2.1) принимает на этом наборе значение f(1, 2,..., n ), а правая часть - значение 1 f(1, 2,..., n ) 0 f(0, 2,..., n ) = f (1, 2,..., n ). Таким образом, на наборах (1, 2,..., n ) левая и правая части (2.1) принимают одинаковые значения. Рассмотрим набор значений переменных (0, 2,..., n ). Левая часть (2.1) принимает на этом наборе значение f(0, 2,..., n ), а правая часть - значение 0 f(1, 2,..., n ) 1 f (0, 2,..., n ) = f (0, 2,..., n ). Таким образом, на наборах (0, 2,..., n ) левая и правая части (2.1) принимают одинаковые значения. Тем самым мы доказали, что левая и правая части соотношения (2.1) принимают одинаковые значения на всех наборах ( 1,..., n ).

31 Лемма 2.3. Конъюнкция (произведение) тогда и только тогда, когда. Доказательство. Произведение (конъюнкция) равно 1 тогда и только тогда, когда каждый сомножитель равен 1, но x = 1 тогда и только тогда, когда x =.

32 В дальнейшем будем употреблять следующие обозначения:

33 Теорема 2.4. (О разложении функции по нескольким переменным). Пусть f(x 1,..., x n ) - произвольная функция алгебры логики. Тогда ее можно представить в следующей форме: (2.2)

34 Доказательство. Рассмотрим произвольный набор значений переменных ( 1,..., n ) и покажем, что левая и правая части соотношения (2.2) принимают на нем одно и то же значение. Левая часть дает f( 1,..., k, k+1,..., n ). Правая часть дает

35 Представление (2.2) называется дизъюнктивным разложением функции по k переменным. Пример. Для k = 2 разложение в дизъюнктивную форму имеет вид:

36 Выпишем такое разложение для конкретной функции трех переменных по переменным x 2 и x 3 :

37 Если k = n, то получаем разложение Оно может быть преобразовано при f(x 1,..., x n ) 0 следующим образом:

38 Итак, в этом случае разложение имеет вид: Это разложение называется совершенной дизъюнктивной нормальной формой (совершенная ДНФ.). Оно определено для любой функции f, не равной константе 0.

39 Теорема 2.5. Произвольную функцию алгебры логики можно выразить формулой при помощи операций,,, причем операция применяется только к переменным

40 Доказательство. 1. Пусть f(x 1,..., x n ) = 0. Тогда, очевидно, f(x1,..., xn) = x 1 x Пусть f(x 1,..., x n ) 0. Представим ее в форме совершенной ДНФ: Таким образом, в обоих случаях функция f выражается в виде формулы через конъюнкцию, дизъюнкцию и отрицание, причем отрицание применяется только к символам переменных.

41 Любую булеву функцию можно выразить формулой над множеством операций {,, }, состоящим из трех функций: отрицания, конъюнкции и дизъюнкции. Данная теорема носит конструктивный характер, так как она позволяет для каждой функции построить реализующую ее формулу (совершенную ДНФ). А именно, берем таблицу для функции f(x 1,..., x n ) (f 0) и отмечаем в ней все строки ( 1,..., n ), в которых f( 1,..., n ) =1, для каждой такой строки образуем логическое произведение а затем соединяем все полученные конъюнкции знаком дизъюнкции.

42 Пример. Построить совершенную ДНФ для функции, заданной таблицей: x 1 x 2 x 3 f(x 1, x 2, x 3 )x 1 x 2 x 3 f(x 1, x 2, x 3 ) Имеем:

43 Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности.задача распознавания теории вычислительной сложности Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ЛОЖЬ и ИСТИНА так, чтобы формула стала истинной.булева формула Согласно теореме Кука, доказанной Стивеном Куком в 1971-м году, задача SAT NP-полна.теореме КукаСтивеном КукомNP-полна

44 Чтобы четко сформулировать задачу распознавания, необходимо условиться об алфавите, с помощью которого задаются экземпляры языка. Этот алфавит должен быть фиксирован и конечен. Обычно используют следующий алфавит:задачу распознавания {,,, (, ), x, 0, 1}. При использовании такого алфавита скобки и операторы записываются естественным образом, а переменные получают следующие имена: x1, x10, x11, x100 и т. д., согласно их номерам, записанным в двоичной системе счисления.двоичной системе счисления Пусть некоторая булева формула, записанная в обычной математической нотации, имела длину N символов. В ней каждое вхождение каждой переменной было описано хотя бы одним символом, следовательно, всего в данной формуле не более N переменных. Значит, в предложенной выше нотации каждая переменная будет записана с помощью символов. В таком случае, вся формула в новой нотации будет иметь длину символов, то есть длина строки возрастет в полиномиальное число раз.булева формулаполиномиальное Например, формула примет вид

45 Вычислительная сложность В 1971-м году в статье Стивена Кука был впервые введен термин «NP-полная задача», и задача SAT была первой задачей, для которой доказывалось это свойство.Стивена КукаNP-полная задача В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. После появления результатов Кука была доказана NP- полнота для множества других задач. При этом чаще всего для доказательства NP-полноты некоторой задачи приводится полиномиальное сведение задачи SAT к данной задаче, возможно в несколько шагов, то есть с использованием нескольких промежуточных задач.теоремы Кука класса NPполиномиальное сведение

46 Две задачи

47

48

49

50

51 Функциональная полнота систем функций алгебры логики Выше мы видели, что всякая функция алгебры логики может быть выражена в виде формулы через элементарные функции, x y, x y. В связи с этим возникает вопрос, какими свойствами должна обладать система функций, чтобы через функции этой системы можно было выразить произвольную функцию алгебры логики? Новые функции получаются из имеющихся в заданной системе функций с помощью операций замены переменных и суперпозиции. Опишем эти две операции.

52 1. Замена переменных. Пусть f(x 1, x 2,..., x n ) - заданная функция алгебры логики. Будем говорить, что функция (y 1, y 2,..., y n ) получена операцией замены переменных из функции f(x 1, x 2,..., x n ), если осуществлена подстановка переменных

53 Пример. Пусть имеется функция Тогда при замене переменных из функции можно получить функцию.

54 2. Суперпозиция функций алгебры логики. Пусть имеется функция f(x 1, x 2,..., x n ) и функции, тогда функцию будем называть суперпозицией функции f(x 1, x 2,..., x n ) и функций. Другими словами: пусть F = { f j } - набор функций алгебры логики, не обязательно конечный. Функция f называется суперпозицией функций из множества F или функцией над F, если она получена из функции путем замены одной или нескольких ее переменных функциями из множества F.

55 Пример. Пусть задано множество функций F = {f 1 (x 1 ), f 2 (x 1,x 2,x 3 ), f 3 (x 1,x 2 )}. Тогда суперпозициями функций из F будут, например, функции: φ 1 (x 2, x 3 ) = f 3 ( f 1 (x 2 ), f 1 (x 3 )); φ 2 (x 1, x 2 ) = f 2 (x 1, f 1 (x 1 ), f 3 (x 1,x 2 )). Cовершенная ДНФ - суперпозиция функций из множества.

56 Система функций называется полной, если при помощи операций суперпозиции и замены переменных из функций этой системы может быть получена любая функция алгебры логики.

57 Мы уже имеем некоторый набор полных систем: {x+y, xy, 1}. Как определить условия, при которых система полна?

58 Замкнутые классы. Множество (класс) K функций алгебры логики называется замкнутым классом, если оно содержит все функции, получающиеся из K операциями суперпозиции и замены переменных, и не содержит никаких других функций. Пусть K - некоторое подмножество функций из P 2 (n). Замыканием K называется множество всех булевых функций, представимых с помощью операций суперпозиции и замены переменных функций из множества K. Замыкание множества K обозначается через [K]. В терминах замыкания можно дать другие определения замкнутости и полноты (эквивалентные исходным): K- замкнутый класс, если K = [K]; K - полная система, если [K] = P 2 (n).

59 Примеры. {0}, {1} - замкнутые классы. Множество функции одной переменной - замкнутый класс. - замкнутый класс. Класс {1, x+y} не является замкнутым классом.

60 Замкнутые классы. 1. Т 0 - класс функций, сохраняющих 0. Обозначим через Т 0 класс всех функций алгебры логики f(x 1, x 2,..., x n ), сохраняющих константу 0, то есть функций, для которых f(0,..., 0) = 0. 0, x, xy, x y, x+y T 0 ; 1, T 0. Из того, что T 0 следует, например, что нельзя выразить через дизъюнкцию и конъюнкцию.

61 Поскольку таблица для функции f из класса Т 0 в первой строке содержит фиксированное значение 0, то для функций из Т 0 можно задавать произвольные значения только на 2 n - 1 наборе значений переменных, то есть, где - множество функций, сохраняющих 0 и зависящих от n переменных. Покажем, что Т 0 - замкнутый класс. Так как x T 0, то для обоснования замкнутости достаточно показать замкнутость относительно операции суперпозиции, поскольку операция замены переменных есть частный случай суперпозиции с функцией x.

62

63 2. T 1 - класс функций, сохраняющих 1. f(1,..., 1) = 1 1, x, xy, x y, x y T 1 ; 0,0,, x+y T 1 Из того, что x + y T 1 следует, например, что x + y нельзя выразить через дизъюнкцию и конъюнкцию.

64 Т 1 - замкнутый класс

65 3. L - класс линейных функций. 0, 1, x, x+y, x 1 x 2 = 1+ x 1 + x 2, = x+1 L; xy, x y L.

66 Докажем, что x y L. Предположим противное. Будем искать выражение для x y в виде линейной функции с неопределенными коэффициентами: При x = y = 0 имеем =0, при x = 1, y = 0 имеем = 1, при x = 0, y = 1 имеем = 1, но тогда при x = 1, y = 1 имеем , что доказывает нелинейность функции дизъюнкция x y. Доказательство замкнутости класса линейных функций очевидно.

67 Поскольку линейная функция однозначно определяется заданием значений n+1 коэффициента 0,..., n, число линейных функций в классе L(n) функций, зависящих от n переменных равно 2n+1.

68 4. S - класс самодвойственных функций. Функция, определяемая равенством называется двойственной к функции Таблица для двойственной функции (при стандартной упорядоченности наборов значений переменных) получается из таблицы для исходной функции инвертированием (то есть заменой 0 на 1 и 1 на 0) столбца значений функции и его переворачиванием.

69 0* = 1, 1* = 0, x* = x, (x 1 x 2 )* = x 1 x 2, (x 1 x 2 )* = x 1 x 2. (f*)* = f функция f является двойственной к f*.

70 Теорема. Если функция получена как суперпозиция функций f, f 1, f 2,..., f m, то функция, двойственная к суперпозиции, есть суперпозиция двойственных функций.

71 Доказательство. φ*(x 1,..., x n ) = f( x 1,..., x n ) =

72 Обозначим через S класс всех самодвойственных функций из P 2 : S = {f | f* = f } x, S; 0, 1, xy, x y S. Для самодвойственной функции имеет место тождество

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

74 Докажем теперь, что класс S замкнут. Так как x S, то для обоснования замкнутости достаточно показать замкнутость относительно операции суперпозиции, поскольку операция замены переменных есть частный случай суперпозиции с функцией x.

75 Пусть. Тогда достаточно показать, что Последнее устанавливается непосредственно:

76 5. М - класс монотонных функций. Набор предшествует набору, если i i для всех i = 1,..., n. Наборы α и β называются сравнимыми, если либо αβ либо βα.В случае, когда ни одно из этих оотношений не выполняется, то наборы называются несравнимыми.

77

78 Функция алгебры логики называется монотонной, если для любых двух наборов и, таких, что, имеет место неравенство. Множество всех монотонных функций алгебры логики обозначаетcя через М, а множество всех монотонных функций, зависящих от n переменных - через М(n).

79 0, 1, x, xy, x y M; x+y, x y, x y M. Покажем, что класс монотонных функций М - замкнутый класс. Так как x М, то для обоснования замкнутости достаточно показать замкнутость относительно операции суперпозиции, поскольку операция замены переменных есть частный случай суперпозиции с функцией x.

80 наборы переменных, соответственно, функций, f 1,..., f m, причем множество переменных функции состоит из тех и только тех переменных, которые встречаются у функций f 1,..., f m.