Предмет дискретной математики

ВВЕДЕНИЕ

Дискретная математика – самостоятельное направление современной математики. Она изучает математические модели объектов, процессов, зависимостей, существующих в реальном мире, с которыми имеют дело в технике, информатике и других областях знаний.

 

ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ

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

Дискретная и непрерывная математика взаимно дополняют друг друга. Понятия и методы одной часто используются в другой. Один и тот же объект может рассматриваться с двух точек зрения.

Дискретная математика предлагает:

· универсальные средства (языки) формализованного представления;

· способы корректной переработки информации;

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

Сегодня дискретная математика является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов – обязательное квалификационное требование к специалистам в области информатики.

 

Нормальные формы

Определение. Элементарной конъюнкцией называется конъюнкция, составленная из попарно различных переменных или отрицаний переменных.

Иногда будем допускать в элементарной конъюнкции наличие повторов элементов.

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

Иногда будем допускать в ДНФ наличие повторов элементов.

Пример 25.

Следующие формулы находятся в ДНФ: .

Определение. Элементарной дизъюнкцией называется дизъюнкция, составленная из попарно различных переменных или отрицаний переменных.

Иногда будем допускать в элементарной дизъюнкции наличие повторов элементов.

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

Иногда будем допускать в КНФ наличие повторов элементов.

Пример 26.

Следующие формулы находятся в КНФ:

Двойственные функции

Определение. Двойственной для функции f(x₁, x₂, …, x_n) называется функция

Пример 44.

Построить функцию, двойственную данной:

1. f = x Ú y;

2. f = x® y.

Решение.

1.

2.

Определение. Функция, совпадающая со своей двойственной, называется самодвойственной.

Утверждение. Если функция f(x₁, x₂, …, x_n) самодвойственна, то функция тоже самодвойственна.

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

Противоположными называются те наборы, которые в сумме дают двоичный код числа (2ⁿ-1).

Пример 45.

Выяснить являются ли функции самодвойственными:

1. ;

2. f = 01110010.

Решение.

1. Строим таблицу истинности для данной функции (табл. 55):

Таблица 55

№	x	y	z
0
1
2
3
4
5
6
7

Так как наборы (0, 0, 0) и (1, 1, 1) являются противоположными, а f(0, 0, 0) = f(1, 1, 1), то данная функция не является самодвойственной.

2. Строим таблицу значений для функции f = 01110001 (табл. 56).

Таблица 56

№	x	y	z	f(x, y, z)
0
1
2
3
4
5
6
7

Перечислим пары противоположных наборов: (0, 7), (1, 6), (2, 5), (3, 4). Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения. Следовательно, функция является самодвойственной.

 

Теорема. Класс S = {f | f = f*}самодвойственных функций замкнут относительно суперпозиций.

 

2.2.3.2. Линейные функции

Определение. Арифметические функции в алгебре логики это сложение по модулю два и умножение (конъюнкция).

Определение. Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: , причем на каждом наборе <i₁, …, i_k> все а_ij (j = 1, …, k) различны, a_j Î {0, 1}.

Теорема. Всякую булеву функцию можно представить единственным полиномом Жегалкина.

Многочлен Жегалкина можно получить различными способами. Остановимся на рассмотрении построения многочлена Жегалкина с помощью треугольника Паскаля. Рассмотрим алгоритм на примере.

Пример 46.

Построить многочлен Жегалкина для функции f=10011110.

Решение.

Алгоритм построения многочлена Жегалкина:

Шаг 1. Строим таблицу (табл. 57). Первый столбец содержит возможные слагаемые полинома Жегалкина. Нулевому набору всегда соответствует слагаемое 1. Остальным наборам соответствует слагаемое, представляющее собой конъюнкцию переменных, которые на данном наборе принимают значение 1. Следующие n столбцов – всевозможные наборы из 0 и 1, соответствующие переменным. Далее столбец значений функции f. Функция g является вспомогательной, поэтому изначально этот столбец не заполнен.

Таблица 57

Слагаемые полинома Жегалкина	x1	x2	x3	f	g	Треугольник Паскаля
1	0	0	0	1
x3	0	0	1	0
x2	0	1	0	0
x2x3	0	1	1	1
x1	1	0	0	1
x1 x3	1	0	1	1
x1 x2	1	1	0	1
x1 x2 x3	1	1	1	0

 

Шаг 2. Построение треугольника Паскаля. Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю два двух соседних элементов предыдущей строки. Левая сторона треугольника представляет собой значение вспомогательной функции g (табл. 58).

Таблица 58

Слагаемые полинома Жегалкина	x1	x2	x3	f	g	Треугольник Паскаля
1	0	0	0	1	1	f = 1 0 0 1 1 1 1 0
x3	0	0	1	0	1	1 0 1 0 0 0 1
x2	0	1	0	0	1	1 1 1 0 0 1
x2x3	0	1	1	1	0	0 0 1 0 1
x1	1	0	0	1	0	0 1 1 1
x1 x3	1	0	1	1	1	1 0 0
x1 x2	1	1	0	1	1	1 0
x1 x2 x3	1	1	1	0	1	1

Шаг 3. Построение полинома Жегалкина. В полином войдут только те слагаемые, которым соответствует единица во вспомогательной функции g.

Для данной функции многочлен Жегалкина имеет вид:

f = 1 + x₃ + x₂ + x₁ x₃ + x₁ x₂ + x₁ x₂ x₃.

 

Определение. Функция f(x₁, x₂, …, x_n) называется линейной, если многочлен Жегалкина для нее имеет следующий линейный относительно переменных вид:

f(x₁, x₂, …, x_n) = a₁x₁ + … + a_nx_n + a_n+1, где каждое a_i равно 0 или 1.

Булева функция из рассмотренного выше примера не является линейной.

Теорема. Класс L = {f | f = a₀+a₁x₁+…+a_nx_n, a_iÎ{0, 1}} линейных функций замкнут относительно суперпозиций.

Монотонные функции

Определение. Если a = (a₁, …, a_n) и b = (b₁, …, b_n) - наборы длины n из 0 и 1, то a £ b, если a₁ £ b₁, …, a_n £ b_n.

Пример 47.

Наборы (0, 1, 0) и (1, 1, 0) сравнимы, причем (0, 1, 0) £ (1, 1, 0).

Наборы (0, 1) и (1, 0) несравнимы. Также несравнимы наборы (0, 1) и (1, 1, 0).

Определение. Функция f(x₁, x₂, …, x_n) называется монотонной, если для всяких наборов a = (a₁, …, a_n) и b = (b₁, …, b_n) условие a £ b влечет f(a) £ f(b).

Утверждение. Функция монотонна тогда и только тогда, когда ее сокращенная ДНФ не содержит отрицаний.

Следствие. Функция монотонна тогда и только тогда, когда ее МДНФ не содержит отрицаний.

Пример 48.

Выяснить, являются ли функции монотонными:

1. f = 00100110;
2. f = 00110111.

Решение.

1. Сокращенная ДНФ для функции f = 00100110 имеет вид Поскольку сокращенная ДНФ содержит отрицания, то функция не является монотонной.

2. Сокращенная ДНФ для функции f = 00110111 имеет вид Поскольку сокращенная ДНФ не содержит отрицаний, то функция является монотонной.

Теорема. Класс M = {f | a£ b Þ f(a)£ f(b)} монотонных функций замкнут относительно суперпозиций.

2.2.3.4. Теорема Поста о функциональной полноте

Теорема Поста (признак полноты системы булевых функций). Для того чтобы система булевых функций {f₁, …, f_m} была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классов T₀, T₁, L, M, S нашлась хотя бы одна функция f_i из системы, не принадлежащая этому классу.

Пример.

Выяснить к каким функционально замкнутым классам принадлежит булева функция f=01001110, используя теорему Поста.

Решение.

Строим таблицу значений и треугольник Паскаля (табл. 59):

Таблица 59

Слагаемые полинома Жегалкина	x1	x2	x3	f	g	Треугольник Паскаля
1	0	0	0	0	0	f = 0 1 0 0 1 1 1 0
x3	0	0	1	1	1	1 1 0 1 0 0 1
x2	0	1	0	0	0	0 1 1 1 0 1
x2x3	0	1	1	0	1	1 0 0 1 1
x1	1	0	0	1	1	1 0 1 0
x1 x3	1	0	1	1	1	1 1 1
x1 x2	1	1	0	1	0	0 0
x1 x2 x3	1	1	1	0	0	0

Полином Жегалкина имеет вид: f = x₃ + x₂x₃ + x₁ + x₁ x₃.

1. f(0, 0, 0) = 0 Þ fÎT₀;
2. f(1, 1, 1) = 1 Þ fÏT₁;
3. f(0, 0, 0) = f(1, 1, 1), а наборы (0, 0, 0) и (1, 1, 1) являются противоположными, то f Ï S;
4. так как в полиноме Жегалкина присутствуют слагаемые, представляющие собой конъюнкцию нескольких переменных, то f Ï L;
5. сокращенная ДНФ функции имеет вид: , так как она содержит отрицания, то f Ï M.

Сведем полученные данные:

	T0	T1	S	L	M
f	+	-	-	-	-

 

Пример 49.

Доказать полноту системы {+, Ú, 1}.

Решение.

Введем обозначения: f₁ = x₁ + x₂, f₂ = x₁ Ú x₂, f₃ = 1. Построим единую таблицу для функций (табл. 60).

Таблица 60

Слагаемые	№	х1	х2	f1 = х1+х2	D Паскаля	f2 =х1Úх2	D Паскаля	f3 =1	D Паскаля
1	0	0	0	0	0 1 1 0	0	0 1 1 1	1	1 1 1 1
х2	1	0	1	1	1 0 1	1	1 0 0	1	0 0 0
х1	2	1	0	1	1 1	1	1 0	1	0 0
х1х2	3	1	1	0	0	1	1	1	0

Полином Жегалкина:

f	T0	T1	L	M	S
f1	+	-	+	-	-
f2	+	+	-	+	-
f3	-	+	+	+	-

Поскольку для каждого из пяти функционально замкнутых классов нашлась функция, не принадлежащая этому классу (в каждом столбце имеется хотя бы один минус), то система булевых функций {+, Ú, 1} является полной.

 

2.2.4. Существенные и несущественные переменные. Производная булевой функции первого порядка. Вес переменной

Определение. Булева функция fÎP_n существенно зависит от переменной x_i, если существует такой набор значений a₁, …, a_i-1, a_i+1, …, a_n, что

В этом случае x_i называют существенной переменной, в противном случае x_i называют несущественной переменной.

Определение. Производная первого порядка от булевой функции f по переменной x_i есть сумма по модулю 2 соответствующих остаточных функций:

где f(x₁, x₂, …, x_i-1, 1, x_i+1, …, x_n) – единичная остаточная функция; f(x₁, x₂, …, x_i-1, 0, x_i+1, …, x_n) – нулевая остаточная функция; Å - сумма по модулю 2.

Единичная остаточная функция получается в результате приравнивания переменной x_i единице, нулевая – приравниванием x_i нулю.

Определение. Весом производной от булевой функции называется число конституент этой производной.

Утверждение. Чем больше вес производной , тем больше функция f зависит от переменной x_i.

Пример 50.

Определить переменную x_i, по которой производная функции

имеет минимальный (максимальный) вес, т. е. функция f(x₁, x₂, x₃, x₄, x₅) зависит от нее менее (более) существенно.

Решение.

Определим вес каждой переменной, найдя сначала соответствующую производную.

Имеем

х2х3	х4х5
	0	0	1	1
	1	0	1	0
	0	0	0	0
	1	0	1	1

Таблица 61

Для вычисления веса производной зависящей от четырех переменных х₂, х₃, х₄, х₅, представим 4-мерное пространство с образующими {x₂, x₃, x₄, x₅} в виде декартова произведения двух двумерных пространств {x₂, x₃}´ {x₄, x₅} с образующими {x₂, x₃} и {x₄, x₅} соответственно. Тогда производную можно задать в виде двумерной таблицы (табл. 61). Вес производной равен числу единиц в этой таблице.

 

Итак,

Аналогично вычислим вес производных (i = 2, 3, 4, 5) (табл. 62, 63, 64, 65). Имеем:

х1х3	х4х5
	0	0	0	0
	0	1	0	1
	0	0	1	1
	0	1	0	0

 

 

 

х1х2	х4х5
	0	0	1	0
	0	1	1	1
	1	0	1	1
	0	1	0	0

 

 

 

Таблица 64

х1х2	х3х5
	1	0	0	0
	1	0	0	0
	0	1	0	0
	1	0	0	1

 

 

 

Таблица 65

х1х2	х3х4
	1	0	1	1
	1	0	0	0
	1	0	0	0
	1	0	1	0

 

 

 

Выяснили, что минимальное значение получено при дифференцировании функции f по переменным х₂ и х₄, максимальное значение получено при дифференцировании функции f по переменной х₃.

 

2.3. Исчисление высказываний

Таблицы истинности позволяют ответить на многие вопросы, касающиеся формул логики высказываний, например на вопрос о тождественной истинности формулы или на вопрос о равносильности двух формул. Однако более сложные вопросы логики высказываний уже не могут быть решены с помощью таблиц истинности.

Наряду с алфавитом и правилами построения сложных высказываний – логических формул, языки логики высказываний содержат правила преобразования логических формул. Правила преобразования реализуют общелогические законы и обеспечивают логически правильные рассуждения. Корректность допустимых в логике преобразований является фундаментальным свойством формальной (математической) логики.

Если описание системы (процесса, явления и т.п.) представлено совокупностью сложных высказываний – логических формул, истинных для данной системы (в данной интерпретации ее простых высказываний), то с помощью допустимых преобразований имеющихся логических представлений о системе может быть выполнен их анализ (синтез), могут быть получены новые представления, характеризующие указанную систему (истинные для данной системы) и т.п. Таким образом, с помощью допустимых в логике преобразований появляется возможность получения новых знаний из имеющихся.

Определение. Процесс получения новых знаний, выраженных высказываниями, из других знаний, также выраженных высказываниями, называется рассуждением (умозаключением). Исходные высказывания называются посылками (гипотезами, условиями), а получаемые высказывания – заключением (следствием).

Логика – это наука о способах доказательства.

В логике высказываний все доказательства строятся на отношении порядка, т.е. на отношении, которое существует между причиной и следствием. Отдельные звенья цепи связаны символом импликации «®» при логическом выводе мы будем заменять на символ «Þ», подобно тому, как используются два символа эквивалентности «»» и «=». Во избежании путаницы вместо конъюнкции «Ù» будем использовать символ запятой «,», а вместо дизъюнкции «Ú» - символ точка с запятой «;». Тогда утверждение, которое требуется доказать, в логике высказываний оформляется в виде следующего причинно-следственного отношения:

P₁, P₂, …, P_n-1, P_n Þ C,

где P_i – посылка, С – заключение. Условимся формальную запись такого рода называть клаузой. Смысловой текст, отвечающий некоторой конкретной клаузе, будем называть её легендой.

Пример 51.

Для данной легенды построить соответствующую клаузу:

«Если фирма приглашает на работу крупного специалиста в области новейшей технологии, то она считает ее привлекательной и разворачивает работы по изменению технологии производства своего традиционного продукта или начинает разработку нового продукта. Конкурирующая фирма пригласила на работу крупного специалиста в области новейшей технологии. Следовательно, она разворачивает работы по изменению технологии производства выпускаемого продукта или разработке нового продукта».

Решение.

Выделим простые высказывания и введем обозначения:

А – «фирма приглашает на работу крупного специалиста в области новейшей технологии»;

B – «фирма считает данную новейшую технологию привлекательной»;

С – «фирма разворачивает работу по изменению технологии производства своего традиционного продукта»;

D - «фирма начинает разработку нового продукта».

С учетом принятых обозначений умозаключение примет вид:

«Если А, то В и (С или D). А. Следовательно, С или D.»

Используя логические связки, получим окончательно:

((А®(ВÙ(СÚD)))ÙA)Þ(CÚD).

Используя равносильности логики высказываний получаем:

 

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

 

2.3.1. Основные схемы логически правильных рассуждений

Приведем примеры наиболее употребимых схем логически правильных рассуждений (некоторые их них приведем без пояснений) (табл. 62):

Таблица 62

№
1	Правило заключения – утверждающий модус (Modus Ponens)	Если из высказывания А следует высказывание В и справедливо (истинно) высказывание А, то справедливо В
2	Правило отрицания – отрицательный модус (Modus Tollens)	Если из А следует В, но высказывание В неверно, то неверно А
3	Правила утверждения-отрицания (Modus Ponendo-Tollens)	Если справедливо или высказывание А, или высказывание В (в разделительном смысле) и истинно одно из них, то другое ложно
4	Правила отрицания-утверждения (Modus Tollen-Ponens)	Если истинно или А, или В (в разделительном смысле) и неверно одно из них, то истинно другое
Если истинно А или В (в неразделительном смысле) и неверно одно из них, то истинно другое
5	Правило транзитивности	Если из А следует В, а из В следует С, то из А следует С
6	Закон противоречия	Если из А следует В и , то неверно А
7	Правило контрапозиции	Если из А следует В, то из того, что неверно В, следует, что неверно А
8	Правило сложной контрапозиции	Если из А и В следует С, то из А и следует
9	Правило сечения	Если из А следует В, а из В и С следует D, то из А и С следует D
10	Правило импортации (объединения посылок)
11	Правило экспортации (разъединения посылок)
12	Правила дилемм

Пример 52.

Следующие рассуждения не являются правильными:

.

2.3.2. Метод Вонга

Пусть дана клауза в своей наиболее общей форме:

В₁, В₂, …, В_n Þ А₁, А₂, …,A_n

Шаг 1. Снятие отрицаний с посылок и заключений. С этой целью нужно опустить знак отрицаний у A_i и B_j и перенести их в противоположные стороны относительно символа Þ.

Шаг 2. Если слева от символа Þ встречается конъюнкция, а справа дизъюнкция, то их следует заменить на запятые.

Шаг 3. Если после предыдущих шагов оказалось, что связкой, расположенной слева от Þ, является дизъюнкция, а справа – конъюнкция, то образуются две новые клаузы, каждая из которых содержит одну из двух подформул, заменяющих исходную клаузу.

Шаг 4. Если одна и та же буква находится с обеих сторон символа Þ, то такая строка считается доказанной. Исходная клауза является теоремой, если все ветви оканчиваются истинными клаузами. В противном случае переходим к шагу 3.

Пример 53.

Выяснить, является ли клауза теоремой:

.

Решение.

Шаг 1. .

Избавляемся от отрицаний. В результате получаем: .

Шаг 2. Поскольку слева от символа Þ не встречается конъюнкция, а справа не встречается дизъюнкция, то шаг 2 как таковой отсутствует.

Шаг 3. Построим дерево доказательств (рис. 11):

Так как есть не доказанные строки, то исходная клауза теоремой не является.

Пример 54.

Выяснить, является ли клауза теоремой:

.

Решение.

Представим ход доказательства в виде дерева (рис. 12). Поскольку все строки доказаны, то исходная клауза является теоремой.

 

2.3.3. Метод резолюций

Методику продемонстрируем на примере. Пусть требуется доказать:

.

Сначала поступают точно так же, как и по методике Вонга, только необходимо преобразовать клаузу таким образом, чтобы слева от символа Þ был ноль Æ:

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

Выпишем по порядку все посылки и далее начнем их «склеивать». Дизъюнкты можно перебирать автоматически в соответствии с возрастанием порядковых номеров. Такая стратегия поиска нуля очень непродуктивна. К решению данной задачи можно подойти творчески.

В итоге получим:

1. АÚ В	5. (1; 4)
2. СÚ А	6. (2; 4) С
3.	7. (3; 5)
4.	8. (6; 7) Æ

Иначе, произведенные раннее преобразования, можно представить в следующем виде:

 

 

2.4. Логика предикатов

2.4.1. Основные понятия, связанные с предикатами

В высказывании все четко: это конкретное утверждение о конкретных объектах – истинное или ложное. Предикат – предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить истинно оно или ложно.

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

Определение. N-местным предикатом, определенном на множествах М₁, М₂, …, М_n, называется предложение, содержащее n переменных х₁, х₂, …, х_n, превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств М₁, М₂, …, М_n соответственно.

Обозначение. Чаще всего предикаты обозначают большими латинскими буквами, а число переменных указывает на его размерность: P(x₁, x₂, …, x_n).

Предикат также называют функцией-высказыванием.

Пример 55.

Рассмотрим три высказывания:

А – «Рубль – валюта России»;

В – «Доллар – валюта России»;

С – «Доллар – валюта США».

Высказывания А и С – истинны, В – ложно. Если вместо конкретных наименований валюты в выражениях А, В подставить предметную переменную х и определить ее на множестве наименований денежных единиц М, то получим одноместный предикат

P(x): «х – валюта России», где х Î М.

Если же в высказывания подставить не только предметную переменную х, определенную на множестве М, но и вместо наименований стран ввести предметную переменную у, определенную на множестве названий стран У, то получим двуместный предикат:

Q(x, у): «х - валюта страны у», где х Î М, у Î У.

Чаще всего предикаты задают высказывательными формами, как показано выше. Однако предикат можно задать таблицей. Такой способ пригоден только для предикатов, область определения которых – конечное множество.

Пример 56.

Пусть задан одноместный предикат P(x), хÎМ, где М = {1, 2, 3, 4, 5}. Значение предиката можно задать таблицей (табл. 63):

Таблица 63

х	1	2	3	4	5
Р(х)	и	и	л	и	л

Пример 57.

Предикат задан высказывательной формой Р(х): «в слове х буква «а» встречается не более двух раз», хÎМ, где М = {конь, стол, карандаш, зал, чаша, барабан}.

Построим таблицу значений для данного предиката (табл. 64):

Таблица 64

х	конь	стол	карандаш	зал	чаша	барабан
Р(х)	и	и	л	и	и	л

 

Определение. Множеством истинности предиката Р(х₁, х₂, …, х_n), заданного на множествах М₁, М₂, …, М_n, называется совокупность всех упорядоченных n-систем (а₁, а₂, …, а_n), в которых таких, что данный предикат обращается в истинное высказывание при подстановке х₁=а₁, х₂=а₂, …, х_n=а_n.

Это множество будем обозначать Р⁺.

Пример 58.

Определить множество истинности предикатов, заданных на соответствующих множествах:

1. Р(х): «х кратно 3», хÎМ, где М = {1, 2, 3, 4, 5, 6, 7, 8, 9};

2. G(x, y): «