Презентация на тему Функции алгебры логики

(в редакторе ТеХ, http://miktex.org/2.8/setup)

Часть I: Учебное пособие. – М.: МФТИ, 1999.
2. Стэнли

Р. Перечислительная комбинаторика. -М.: Мир, 1990.
3. Липский В. Комбинаторика для программистов. - М.: Мир, 1988.
4. Рыбников К.А. Введение в комбинаторный анализ. - М.: МГУ,1985.
5. Гаврилов Г.И., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. -М.: Наука, 1992.
6. Риордан Дж. Введение в комбинаторный анализ. - М.: ИЛ, 1963.
7. Холл М. Комбинаторика. - М.: Мир, 1970.
8. Мендельсон Э. Введение в математическую логику.- М.: Наука, 1976.
9. Дискретная математика и математические вопросы кибернетики/
Под ред. С.В.Яблонского, О.В.Лупанова, Т.1, -М.; Наука, 1974.
10. Яблонский С.В. Введение в дискретную математику. -М.: Наука, 1986.
11. Оре О. Теория графов. - М.: Наука, 1968.
12. Кристофидис Н. Теория графов. Алгоритмический подход. -М.: Мир, 1987.
13. Емеличев В.А., Мельников О.И. и др. Лекции по теории графов. М.: Наука, 1990.
14. Уилсон Р.Дж. Введение в теорию графов. - М.: Мир, 1977.
15. Харари Ф. Теория графов. - М.: Мир,1973.
16. Журавлёв Ю.И., Флёров А.А., Федько О.С., Дадашев Т.М. Сборник задач по дискретному анализу. – М.: МФТИ, 2000.
17. Гжегорчик А. Популярная логика.- М.: Наука, 1979.
18. Леонтьев В.К. Избранные задачи комбинаторного анализа. – М. Изд-во МГТУ им. Н.Э. Баумана, 2001.
19. Лазарев А.А. Теория расписаний. Оценки абсолютной погрешности и схема приближённого решения задач теории расписаний: Учебное пособие. – М.: МФТИ, 2008.
20. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир. – 1982.
21. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М. – 2005. 1293 с.

очерком, касающимся исчисления дедуктивных рассуждений”, (1847 г.),
“Исследования законов мысли.

на которых основываются математические теории логики и вероятностей”, (1854 г.).
Аугустус (Огастес, Август) де Морган (1806-1871)
“Формальная логика или исчисление выводов, необходимых и возможных” (1847 г.).

2 ноября 1815 в Линкольне. В возрасте 16 лет стал помощником учителя частной школы

в Донкастере, в 1835 открыл собственную школу в Линкольне. В свободное время читал математические журналы, работы И.Ньютона (1815-1864), английский математик. Родился 2 ноября 1815 в Линкольне. В возрасте 16 лет стал помощником учителя частной школы в Донкастере, в 1835 открыл собственную школу в Линкольне. В свободное время читал математические журналы, работы И.Ньютона, П.Лапласа (1815-1864), английский математик. Родился 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.

27 июня, 27 июня 1806, 27 июня 1806), Мадура,

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

функции, их свойства, таблица операций, коммутативность, ассоциативность, дистрибутивность элементарных

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

0 и 1
Область значений функций также 0 и 1
Функция

от одной переменной f(x)
x f(x)
0 0 0 1 1
1 0 1 0 1
0 x ⎤ x 1

y x ∧y x ∨ y x→y x≡y

x+y x|y x↓y
0 0 0 0 1 1 0 1 1
0 1 0 1 1 0 1 1 0
0 0 1 0 0 1 1 0
1 1 1 1 1 1 0 0 0

2n конъюнкция ∧ & и min(x,y) дизъюнкция ∨ max (x,y) импликация → ⊃ эквивалентность ≡ ~ ↔ сумма по модулю 2 + ⊕
штрих (Шеффера) | “не x или не y” стрелка (Пирса) ↓ “не x и не y”.

множество формул алгебры логики над U определяется следующим образом:
1.

Всякая переменная - формула.
2. Константы 0 и 1 - формулы.
3. Если А - формула, то ⎤ А (или в другой записи ) - формула.
4. Если А и В - формулы, то (А∧В), (А∨В), (А→В), (А+В), (А≡В), (А⎪В), (А↓В) - формулы.
5. Формулами являются те и только те выражения, которые могут быть получены из констант, переменных и логических связок за конечное число шагов 1- 4.

принимающая значения из множества {0, 1}, называется функцией алгебры

логики или булевой функцией.

F(x1 ,x2 ,x3,…, xn),

x1 x2 ... xn-1 xn f(x1, x2, ...

xn-1, xn)
0 0 ... 0 0 f(0, 0, ... , 0, 0)
0 0 ... 0 1 f(0, 0, ... , 0, 1)
0 0 ... 1 0 f(0, 0, ... , 1, 0)

......................
1 1 ... 1 1 f(1, 1, ... , 1, 1)
2n

* означает, что

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

.Свойство

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

∙ означает, что

.
Дистрибутивность конъюнкции:

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

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

и дизъюнкцией:


закон

(правила) де Моргана.

Указанные соотношения отражают отношение двойственности между дизъюнкцией и конъюнкцией.

отрицания” на элементарные логические функции:

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

значений функций.

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

булевых функций размерности n.
Теорема. Число p2(n) всех функций из

P2(n), зависящих от переменных x1, x2, ... , xn , равно .

x2, ... ,xi-1, xi , xi+1, ... , xn

) из P2(n)называется существенной, если можно указать такие наборы
и


значений переменных, что


В противном случае переменную xi называют несущественной или фиктивной переменной функции f.
Две функции f(x1, x2, ... ,xi-1, xi , xi+1, ... , xn ) и
g(x1, x2, ... ,xi-1, xi , xi+1, ... , xn )
называются равными, если множества их существенных переменных совпадают и на любых двух наборах
(x1, x2, ... ,xi-1, xi , xi+1, ... , xn ) и
(y1, y2, ... ,yi-1, yi , yi+1, ... , yn ),
различающихся быть может только значениями несущественных переменных, значения функций одинаковы: f(x)=g(y).
Если f(x) и g(y) - равные функции, то одну из них можно получить из другой путем добавления и/или изъятия несущественных переменных.

единообразно записывать переменные с отрицанием и без отрицания введем

следующее обозначение:

только тогда, когда x = σ, то есть значение

“основания” равно значению “показателя”.

f(x1 , ... , xn) - произвольная функция алгебры

логики, тогда справедливо следующее представление f в форме разложения по переменной x1 :

(2.1)

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

функции 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). €

тогда и только

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

f(x1 , ... , xn) - произвольная функция алгебры

логики. Тогда ее можно представить в следующей форме:

(2.2)

, αn) и покажем, что левая и правая части

соотношения (2.2) принимают на нем одно и то же значение. Левая часть дает
f(α1 ,..., αk ,α k+1 ,..., αn).
Правая часть дает

k переменным.
Пример. Для k = 2 разложение в

дизъюнктивную форму имеет вид:

по переменным x2 и x3:

Оно может быть преобразовано при f(x1, ... , xn)

≠ 0 следующим образом:

называется совершенной дизъюнктивной нормальной формой (совершенная ДНФ.). Оно определено

для любой функции f, не равной константе 0.

формулой при помощи операций ∧, ∨, ⎤, причем операция

⎤ применяется только к переменным

Тогда, очевидно,
f(x1, ... , xn) = x1 ∧ ⎤

x1 .
2. Пусть f(x1, ... , xn) ≠ 0. Представим ее в форме совершенной ДНФ:


Таким образом, в обоих случаях функция f выражается в виде формулы через конъюнкцию, дизъюнкцию и отрицание, причем отрицание применяется только к символам переменных. €

операций
{∧, ∨, ⎤ }, состоящим из

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

а затем соединяем все полученные конъюнкции знаком дизъюнкции.

задача распознавания — задача распознавания, важная для теории вычислительной

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

алфавите, с помощью которого задаются экземпляры языка. Этот алфавит

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



примет вид

1971-м году в статье Стивена Кука был впервые введен

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

что всякая функция алгебры логики может быть выражена в

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

- заданная функция алгебры логики. Будем говорить, что функция

ϕ(y1, y2, ... , yn) получена операцией замены переменных из функции f(x1, x2, ... , xn), если осуществлена подстановка переменных

из функции
можно получить функцию
.

f(x1, x2, ... , xn) и функции

,
тогда функцию

будем называть суперпозицией функции f(x1, x2, ... , xn) и функций .
Другими словами: пусть F = { fj } - набор функций алгебры логики, не обязательно конечный. Функция f называется суперпозицией функций из множества F или функцией над F, если она получена из функции

путем замены одной или нескольких ее переменных функциями из множества F.

{f1(x1), f2 (x1 ,x2 ,x3 ), f3(x1 ,x2 )}.
Тогда

суперпозициями функций из F будут, например, функции:
φ1(x2, x3) = f3( f1(x2), f1(x3));
φ2(x1, x2) = f2 (x1 , f1(x1 ), f3(x1 ,x2 )).
Cовершенная ДНФ - суперпозиция функций из множества
. €

суперпозиции и замены переменных из функций этой системы может

быть получена любая функция алгебры логики. €

1}.
Как определить условия, при которых система полна?

замкнутым классом, если оно содержит все функции, получающиеся из

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

одной переменной - замкнутый класс.

- замкнутый класс.
Класс {1, x+y} не является замкнутым классом.

0.
Обозначим через Т0 класс всех функций алгебры логики f(x1,

x2, ... , xn), сохраняющих константу 0, то есть функций, для которых f(0, ... , 0) = 0.

0, x, xy, x∨y, x+y ∈ T0;
1, ∉ T0. Из того, что ∉ T0 следует, например, что нельзя выразить через дизъюнкцию и конъюнкцию.

в первой строке содержит фиксированное значение 0, то для

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

, 1) = 1

1, x, xy, x∨y, x≡y

∈ T1;

0,

, x+y ∉ T1

Из того, что x + y ∉ T1 следует, например, что x + y нельзя выразить
через дизъюнкцию и конъюнкцию.

x+y, x1 ≡ x2 = 1+ x1 + x2,

= x+1 ∈ L;

xy, x∨y ∉ L .

искать выражение для x∨y в виде линейной функции с

неопределенными коэффициентами:

При x = y = 0 имеем α=0,
при x = 1, y = 0 имеем β = 1,
при x = 0, y = 1 имеем γ = 1,
но тогда при x = 1, y = 1 имеем 1∨ 1 ≠ 1 + 1, что доказывает нелинейность функции дизъюнкция x∨y.
Доказательство замкнутости класса линейных функций очевидно.

коэффициента α0, ... , αn , число линейных функций

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

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

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

x2)* = x1 ∧ x2,
(x1 ∧ x2)* = x1

∨ x2.

(f*)* = f

функция f является двойственной к f*.

f, f1, f2, ... , fm, то функция, двойственная

к суперпозиции, есть суперпозиция двойственных функций.

=

P2:
S = {f | f* = f }
x,

∈ S;
0, 1, xy, x∨y ∉ S .

Для самодвойственной функции имеет место тождество

и

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

x∈S , то для обоснования замкнутости достаточно показать замкнутость

относительно операции суперпозиции, поскольку операция замены переменных есть частный случай суперпозиции с функцией x.

.

Тогда достаточно показать, что



Последнее устанавливается непосредственно:

предшествует набору,


если αi ≤ βi для всех i = 1, ... , n.




Наборы α и β называются сравнимыми, если либо α≤β либо β≤α.В случае, когда ни одно из этих оотношений не выполняется, то наборы называются несравнимыми.

двух наборов и , таких, что ,

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

x≡y ∉ M .
Покажем, что класс монотонных функций

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