- •Лекция 1 Теория алгоритмов и математическая логика Функция
- •Словарные функции
- •Вычислимые функции и машина Тьюринга
- •Лекция 2 Словарное представление машины Тьюринга
- •Проблема остановки
- •Проблемы пустой ленты и метод сведения
- •Лекция 3 Проблема зацикливания
- •Введение в теорию np-полных задач Задачи, алгоритмы и сложности
- •Трудно решаемые задачи
- •Лекция 4 np – полные задачи
- •Задачи распознавания
- •Примеры массовых задач
- •Лекция 5 Детерминированные машины Тьюринга и класс p
- •Недетерминированное вычисление и класс np
- •Взаимоотношение между классами p и np
- •Лекция 6 Полиномиальная сводимость и np-полные задачи
- •Теорема Кука
- •Лекция 7 Шесть основных np-полных задач.
- •Некоторые методы доказательства np-полноты.
- •Сужение задачи.
- •Локальная замена.
- •Лекция 8
- •Лекция 9
- •Лекция 10 Доказательство результатов о сильной np-полноте
- •Лекция 11
- •Лекция 12 основы математической логики
- •Основные логические законы
- •Основные правила обращения с кванторами
- •Лекция 13
- •Минимизация булевых функций
- •Лекция 14 Стандартные формулы преобразования булевых функций
- •Геометрическая интерпретация
- •Построение простых импликантов
Основные правила обращения с кванторами
Имеется два квантора: квантор существования - , квантор общности -
Если Р(х) - некоторая высказывательная форма с единственной свободной переменной x, то возможно построение высказываний с ограниченными кванторами и неограниченными. Неограниченный квантор имеет вид:х Р(х),х Р(х). Ограниченные кванторы предполагают наличие ограничений на свободную переменную:хSР(х),хSР(х).
При работе с кванторами также выполняются законы Де моргана:
(x Р(х)) = x Р(х)
(x Р(х)) = x Р(х)
ПРИМЕР:
Записать не используя знаков отрицания, то что функция f(x) разрывна в точке Х0
( 0 0 хх-х0f(x)-f(x0))
применяется закон Де Моргана:
0 0 х(х-х0f(x)-f(x0))
(аb)=(аVb)=а(b)
0 0 хх-х0f(x)-f(x0)
Техника доказательств:
f:RRf(x)=2x
ПРИМЕР 1:
доказать, что х,уRf(x+y)=f(x)+f(y)
доказательство: возьмем любые два вещественных числа х и у, тогда
f(x+y)=f(x)+f(y)
ПРИМЕР 2:
доказать единственность нейтрального элемента в группе А по умножению (А*х). Предположим, что имеется два различных нейтральных элемента, левосторонний eи правостороннийe’, т.е. :
х ех=х (1)
х е’х=х (2)
Поскольку формула (1) справедлива для любого х, то возьмём в качестве х значение е’ (х=е’), получим ее’=е’. Поскольку формула (2) справедлива для любого х, то возьмём х равный е, получим ее’=е
теорема: существуют два иррациональных числа а и b, такие что аbявляется рациональным числом.
Доказательство: а=b=с=- может быть либо рациональным, либо иррациональным. Если с – рационально то теорема доказана. Если с – иррационально, о возьмём в качестве а=,b=, огда аb=. Теорема доказана.
АЛГЕБРА ЛОГИКИ. ЛОГИЧЕСКИЕ ОПЕРАЦИИ И ОПЕРАЦИИ НА МНОЖЕСТВАХ
Одноместным предикатом на множестве А называется функция, отображающая множество А{0,1}. ПустьX- некоторое подмножество А, определяемх: А{0,1}
х(а)=
хназывается характеристической функцией подмножестваX.
Операции над множествами и одноместными предикатами:
Пусть f,gотображают А{0,1}. Определим операции над функциямиfиg: А{0,1}.
(fvg)(a)=f(a)Vg(a). Аналогично fg и g
Две постоянные функции: 0: А{0,1}
1: А{0,1}
0(а)=0, 1(а)=1
Теорема: Пусть X,Y, тогда:
х V Y = xy
х Y = xy
x = x
0=Ø, 1=A
доказательство: пусть аА
(хVY)(a)= х(a)V Y(a)=
То есть первое тождество доказано, а второе аналогично. Теперь рассмотрим третье тождество:
(х)(a)=(х)(a)=
x (a)=
Четвёртое аналогично.
Следствие:Пусть имеется логическое тождество в которое входят только операции,V,. Тогда если вместо переменных подставить имена подмножеств множества А и заменить логические операции операциями над множеством:,,, а константы 0,1 на пустое множество и множество А, то получится верное тождество для множеств.
Лекция 13
Операции над подмножествами и одноместными предикатами
Пусть отображение fиg- одноместные предикаты; определим следующие операции над ними:
1.
2.
3. ;
4. - тождественно равно 0 на А;
5. - тождественно равно 1 на А;
Теорема:
Пусть X и Y – два произвольных подмножества множества А, тогда:
1. ;
2. ;
3. , где;
4. ;
5. ;
Доказательство:
Рассмотрим произвольное :
===
2. Рассмотрим произвольное :
===
3.
Следствие:
Пусть имеется булево тождество, в которое входят только связки ,,
, тогда, если вместо переменных подставить произвольные подмножества множества А и заменитьна, а 0 и 1 наи А, то получится верное равенство.
Операция - исключающее или.
Для множеств XиYопределяется операция “симметрическая разность”. На самом деле операциянад предикатами соответствует операциинад множествами.
Булевы функции
Определение:
БФ от nпеременных– это отображение.
Теорема:
Каждую БФ можно выразить через операцию ,,.
Доказательство:
Пусть f:{0,1}n {0,1} – БФ отnпеременных
1) Если (x1,x2,…,xn){0,1}n f(x1…xn)=0,тоf(x1…xn)=x1(x1)
2) Пусть функция fтождественно
Рассмотрим ,x{0,1}. Обозначимx=
Для любого набора (1,2,…,n), для которого функцияfпринимает значение 1, мы рассмотрим выражение вида:
x11x22…xnn
Дизъюнкция всех этих выражений даёт булеву функцию f
Докажем это: S={(1…n){0,1}n|f(1…n)=1 }
Тогда g(x1…xn) = (x11x22…xnn)
g(x1…xn)=f(x1…xn)
Определим, при каких значениях x1…xn функцияg=1(1…n)S,такой чтоX11Х22…Хnn=1
X11Х22…Хnn=1i Хi=i.
Т.е. g(x1…xn)=1 для тех наборов, которые входят в множестваS.
С другой стороны, f(x1…xn)=1 только для тех, которые входят в множествоS.
Т.е. функции fиgпринимают значения 1 и 0 на одних и тех же наборахf=g.
Следствие:
Каждую БФ можно выразить, используя только 2 операции: или
Замечание:
Представленная в теореме функция gназывается совершенной дизъюнктивной нормальной формой (СДНФ). Исходя из тождества=xстроится совершенная конъюнктивная нормальная форма. Возьмём СДНФ:
Тогда ¬=(¬)=
=
Пусть ρ(x1…xn)=f(x1…xn), тогда ρ(x1…xn)=
ρ(x1…xn)=
f=-(ρ(x1…xn))=()=