Учебное пособие 1518
.pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Воронежский государственный технический университет
В.А. Шаруда
ДИСКРЕТНАЯ МАТЕМАТИКА
Курс лекций
Воронеж 2003
УДК 510.6 + 519.17 + 519.713 + 512.0
Шаруда В.А. Дискретная математика: Курс лекций. Воронеж: Воронеж. гос. техн. ун-т, 2003. 74 с.
Курс лекций охватывает такие разделы дискретной математики как математическая логики, теория графов, теория конечных автоматов и сетей, теория алгоритмов. Содержание соответствует рабочей программе дисциплины “Дискретная математика”.
Курс лекций предназначен для студентов третьего курса специальности 652000 “Мехатроника и робототехника” дневной формы обучения
Курс лекций подготовлен в электронном виде в текстовом редакторе MS WORD 97, содержатся в файле diskrmat.doc.
Табл.: 20. Ил.: 17. Библиогр.: 4 назв.
Научный редактор д-р физ.-мат. наук В.Д. Репников
Рецензенты: кафедра дифференциальных уравнений Воронежского государственного университета (зав. кафедрой д-р физ.-мат. наук А.И. Шашкин); д-р тех. наук М.Г. Матвеев
Издается по решению редакционно-издательского совета Воронежского государственного технического университета
©Шаруда В.А., 2003
©Воронежский государственный технический университет, 2003
2
ВВЕДЕНИЕ
Предлагаемый курс лекций ставит своей целью знакомство читателя с современными средствами математического моделирования – универсальными моделями и методами формализованного описания систем, процессов, явлений, такими, как теоретикомножественные, графические, логические. При огромном разнообразии таких методов, общим в них является дискретность описания объектов анализа.
Методы дискретной математики широко используются в практике моделирования в управлении, в случае когда появляется необходимость в систематизации сведений о системе, ее структуризации, представлении информации о системе в виде, удобном для ее анализа как «вручную», так и с использованием вычислительной техники. Методы дискретной математики оказываются пригодными для описания и анализа многих проблем, которые не поддаются, ввиду их сложности, описанию традиционными средствами классической математики.
Важность освоения методов дискретной математики заключается еще и в том, что современная информационно-компьютерная техника базируется на дискретных представлениях.
3
1.АЛГЕБРА ЛОГИКИ
1.1.Функции алгебры логики
Будем рассматривать функции f(ui1, ui2, …, uin) (uik≠uim при k≠m), аргументы которых определены на множестве E2={0; 1} и такие, что f(α1, α2, …, αn)εE2, если αiεE2. Эти функции называются
функциями алгебры логики или булевыми функциями.
Чтобы избежать двойной индексации, будем употреблять символы x, y, z, … с индексами или без них, т.е. f(x1, x 2, …, x n). Из определения функции f(x1, …, x n) следует, что для ее задания достаточно указать, какое значение функции соответствует каждому из наборов значений аргументов, т.е. выписать таблицу.
Таблица 1
x1 |
… |
xn-1 |
xn |
f(x1, x 2, …, x n-1, x n) |
0 |
… |
0 |
0 |
f(0, …, 0, 0) |
0 |
… |
0 |
1 |
f(0, …, 0, 1) |
0 |
… |
1 |
0 |
f(0, …, 1, 0) |
… |
… |
… |
… |
… |
1 |
… |
1 |
1 |
f(1, …, 1, 1) |
Нетрудно видеть, что n переменных принимают 2n значений. Для удобства употребляется стандартное расположение наборов: если набор рассматривается как запись числа в двоичной системе исчисления, то расположение наборов соответствует порядку следования чисел 0, 1, …, 2n-1.
Обозначим через Р2 систему всех функций алгебры логики над алфавитом U={ u1, u2, …, um, …}, содержащую также константы
0 и 1.
Если фиксировать n переменных x1, x 2, …, x n, то различные таблицы будут различаться только значениями правого столбца.
Имеет место следующая теорема.
Теорема. Число p2(n) всех функций из P2 , зависящих от n пе-
ременных x1, x 2, …, x n, равно 22n .
Замечание I. Число функций алгебры логики, зависящих от n аргументов конечно, поэтому изучить их в принципе можно перебо-
4
ром, однако p2(1)=4; p2(2)=16; p2(3)=256; p2(4)=65536; …, следова-
тельно при больших n (n≥6) перебор становится практически невозможным даже с использованием вычислительной техники.
Замечание II. С ростом n таблица, задающая функцию, сильно усложняется, так при n=10 в ней уже 1024 стоки, а при n=20 она практически необозрима.
Введенное выше определение функции имеет существенный недостаток: оно не позволяет рассматривать функции от меньшего числа аргументов. Для устранения этого недостатка введем следующее определение.
Определение. Функция f(x1, …, x i-1, x i, x i+1, …, x n) из P2 зависит существенным образом от аргумента xi, если найдутся такие значе-
ния α1, …, α i-1, α i, α i+1, …, α n переменных x1, …, x i-1, x i, x i+1, …, x n,
что f(α1, …, α i-1, 0, α i+1, …, α n)≠ f(α1, …, α i-1, 1, α i+1, …, α n).
В этом случае переменная xi называется существенной. Если переменная xi не является существенной, то она называется несуще-
ственной или фиктивной.
Пусть xi является фиктивной переменной. Возьмем таблицу для функции f(x1, …, x n) и по ней построим новую таблицу, вычер-
кивая все строки вида α1, …, α i-1, 1, α i+1, …, α n и столбец xi. Полученная таблица будет определять некоторую функцию g(x1, …, x i-1,
xi+1, …, x n).
Будем говорить, что g(x1, …, x i-1, x i+1, …, x n) получена из f(x1, …, x n) путем удаления фиктивной переменной xi, а f получена из g
путем введения фиктивной переменной xi.
Определение. Функции f1 и f2 будем называть равными, если функцию f2 можно получить из f1 путем изъятия или добавления фиктивных аргументов.
Существуют 2 типа функций, не имеющих существенных переменных. Это 0 и 1. Ввиду этого целесообразно включить в рассмотрение константы 0 и 1, рассматривая их как функции от пустого множества переменных.
Рассмотрим примеры «элементарных» функций алгебры логи-
ки:
1)f1(x)=0 – константа 0;
2)f2(x)=1 – константа 1;
3)f3(x)=x – тождественная функция;
4)f4(x)= x – отрицание х (читается «не х»);
5
5)f5(x1, x2)= (x1Λx2) – конъюнкция x1 и x2 (читается «х1 и x2»). Вместо знака Λ употребляется знак “·”. Эту операцию называ-
ют логическим умножением.
6)f6(x1, x2)= (x1Vx2) – дизъюнкция x1 и x2 (читается «х1 или x2»). Эту операцию называют логическим сложением.
7)f7(x1, x2)= (x1→x2) – импликация x1 и x2 (читается «из х1 следует x2»). Эту операцию называют логическим следованием.
8)f8(x1, x2)= (x1+x2) – сложение х1 и x2 по mod2.
9)f9(x1, x2)= (x1/x2) – функция Шеффера (понимается как отрицание конъюнкции).
Функции f1- f4 – монарные функции, f5- f9 – бинарные функ-
ции.
Выпишем таблицы значений этих функций.
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 2 |
|||
|
х |
0 |
|
|
1 |
|
|
х |
|
|
|
x |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
0 |
|
0 |
|
|
1 |
|
|
0 |
|
1 |
||||
|
1 |
|
0 |
|
|
1 |
|
|
1 |
|
0 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 3 |
|||
x1 |
|
x2 |
|
(x1Λx2) |
(x1Vx2) |
|
(x1→x2) |
(x1+x2) |
|
(x1/x2) |
|||||
0 |
|
0 |
|
0 |
0 |
|
1 |
0 |
|
|
1 |
||||
0 |
|
1 |
|
0 |
1 |
|
1 |
1 |
|
|
1 |
||||
1 |
|
0 |
|
0 |
1 |
|
0 |
1 |
|
|
1 |
||||
1 |
|
1 |
|
1 |
1 |
|
1 |
0 |
|
|
0 |
Заметим, что
(x1Λx2)= (x1·x2)= min(x1, x2); (x1Vx2)= max(x1, x2).
1.2. Формулы. Реализация функций формулами
Как и в элементарной алгебре, исходя из «элементарных» функций, можно строить формулы.
Приведем индуктивное определение формул. Определение.
Пусть В – некоторое подмножество функций из Р2.
6
Базис индукции. Каждая функция f(x1, …, xm) из В называется формулой над В.
Индуктивный переход. Пусть f(x1, …, xm) – функция из В и А1,
…, Аm – выражения, являющиеся либо формулами над В, либо символами переменных из U. Тогда выражение f(А1, …, Аm) называется формулой над В.
Пример 1.1: Пусть В – множество «элементарных» функций. Следующие выражения являются формулами над В:
1) |
(((x1Λx2)+ x1)+x2); |
|
|
|
|||
|
|
|
|
|
|
|
|
2) |
( x1 Λ (x1+x2)); |
|
|
|
|||
|
|
|
|
|
|
|
|
3) |
( x1 |
x2 |
x3 |
x3 |
x2 ). |
Пусть M[f1, …, fn] – произвольная формула над В, тогда формулы, используемые для ее построения будем называть подформу-
лами М.
Пусть формула М= M[f1, …, fs] – формула над множеством
В={ f1(x1, …, xn), …, fs(x1, …, xn) }.
Возьмем множество функций
G={g1(x1, …, xn), …, gs(x1, …, xn)},
где gi имеют те же переменные, что и fi (i=1…s).
Определение. Рассмотрим формулу N[g1, …, gs], которая получается из М путем замены (f1, …, fs) на (g1, …, gs). Говорят, что формула N имеет то же строение, что и формула М.
Пример 1.2.
|
|
|
|
|
; M x1 |
x2 |
x3 |
|
||
1) |
B x1; x1 |
x2 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
2) |
G x1; x1 |
x2 |
; N x1 |
|
x2 |
|
x3 . |
Очевидно, что М и N имеют одинаковое строение. Функцию f, соответствующую формуле М, будем называть суперпозицией функций из В, а процесс получения функции f из В будем называть опе-
рацией суперпозиции.
Пример 1.3. Пусть функции f1(x1, x2, x3), f2(x1, x2, x3), f3(x1, x2, x3)
–функции, соответствующие формулам из примера 1.1.
1)Формула (((x1Λx2)+x1)+x2) строится за три шага: (x1Λx2); ((x1Λx2)+x1); ((x1Λx2)+x1)+x2. Составим таблицу этой функции.
7
|
|
|
|
|
|
|
|
|
|
Таблица 4 |
|
x1 |
x2 |
|
|
|
(x1Λx2) |
(x1Vx2)+x1 |
((x1Λx2)+x1)+x2 |
||
|
0 |
0 |
|
|
|
|
0 |
0 |
0 |
|
|
0 |
1 |
|
|
|
|
0 |
0 |
1 |
|
|
1 |
0 |
|
|
|
|
0 |
1 |
1 |
|
|
1 |
1 |
|
|
|
|
1 |
0 |
1 |
|
|
Последний столбец определяет функцию f1(x1, x2). Нетрудно |
|||||||||
видеть, что f1(x1, x2)=max (x1, x2)= x1Vx2. |
|
|||||||||
|
2) Функцию f2(x1, x2, x3) будем строить сразу: |
|
||||||||
|
|
|
|
|
|
|
|
|||
|
f2(x1, x2, x3)= x Λ (x1+x2). |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
Таблица 5 |
|
x1 |
|
|
|
x2 |
|
x3 |
f2(x1, x2, x3) |
||
|
0 |
|
0 |
|
0 |
|
0 |
|||
|
0 |
|
0 |
|
1 |
|
1 |
|||
|
0 |
|
1 |
|
0 |
|
1 |
|||
|
0 |
|
1 |
|
1 |
|
0 |
|||
|
1 |
|
0 |
|
0 |
|
0 |
|||
|
1 |
|
0 |
|
1 |
|
0 |
|||
|
1 |
|
1 |
|
0 |
|
0 |
|||
|
1 |
|
1 |
|
1 |
|
0 |
|
3) Для нахождения функции f3(x1, x2, x3) будем искать те набо- |
|||||||||
|
|
|
|
|
|
|
||||
ры, на которых формула: { x1 |
x2 |
x3 |
x3 |
x2 } обращается |
||||||
в |
1. |
Очевидно, |
что |
это происходит тогда, когда |
||||||
x1 |
x2 |
x3 |
x3 |
x2 |
обращается в 0. Последнее имеет ме- |
|||||
сто при x1=0 и при x2 |
x3 |
x3 |
x2 |
0 . Это же выполняется |
тогда, когда, по крайней мере одна из формул (x2→x3) или (x3→x2) обращается в 0, что имеет место при x2=1, x3=0 или при x2=0, x3=1. Таким образом f3(x1, x2, x3) равна 1 на наборах (0, 0, 1) и (0, 1, 0).
8
Таблица 6
x1 |
x2 |
x3 |
f3(x1, x2, x3) |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Отметим, что f2(x1, x2, x3)= f3(x1, x2, x3).
Введенный таким образом язык формул удобен для записи функций алгебры логики, описывающих различные условия или высказывания.
Рассмотрим два примера. В них используются высказывания вида «имеет место х» или просто «х», а это означает, что при данных условиях х истинно, или равно 1.
Пример 1.4. Сложение n-разрядных чисел.
Исходим из обычного алгоритма сложения столбиком
xn … x2 x1
+
yn … y2 y1
____________
zn+1zn … z2 z1
Требуется выразить значения разрядов суммы через значения разрядов слагаемых. Для решения этого вопроса рассмотрим вспомогательные величины wn, wn-1, …, w1, где wi означает результат переноса из i-го разряда в (i+1) разряд.
Ясно, что
zi=((xi+yi)+wi-1)
(w0=0, xn+1= yn+1=0, i=1, …, n+1).
Величина wi определяется уровнем переноса из i-го разряда в (i+1)-й: «перенос в (i+1)-й разряд имеет место тогда и только тогда, когда по крайней мере две из трех величин xi, yi, wi-1 равны 1». Это высказывание можно cформулировать так: «xi и yi» или «xi и wi-1» или «yi и wi-1» или формально
wi=(((xiΛyi)V(xiΛwi-1))V(yiΛwi-1)) i=1, …, n.
9
Пример 1.5. Задача о вызове свободного лифта.
В подъезде имеется три лифта, обслуживающих n этажей. На каждом этаже имеется устройство, позволяющее при нажатии кнопки вызвать ближайший свободный лифт. Вопрос: как можно на логическом языке записать условие вызова i-го лифта (i=1, 2, 3)?
Рассмотрим задачу для случая вызова лифта на первом этаже. Для описания исходной информации введем 3n аргументов
x1, y1, z1, x2, y2, z2, …, xn, yn, zn,
где xi=1, тогда и только тогда, когда 1-й лифт находится на i-м этаже и свободен. yi и zi – аналогично для второго и третьего лифтов.
Обозначим через
fI(x1, y1, z1, …, xn, yn, zn); fII(x1, …, zn); fIII(x1, …, zn)
функции равные 1 тогда и только тогда, когда вызывается лифт с номерами 1, 2,3 соответственно.
Условие вызова 1 лифта, или функция fI, характеризуется тем, что «1 лифт свободен или нет свободных лифтов, расположенных на более низком этаже, чем 1-й лифт. Это высказывание более подробно можно выразить следующим образом:
«1-й лифт вызывается тогда и только тогда, когда 1-й лифт находится на 1-м этаже и свободен, или на 1-м этаже нет свободных лифтов с номерами 2 и 3, и в этом случае 1-й лифт находится на 2-м этаже и свободен, или на 2-м этаже нет свободных лифтов с номерами 2 и 3 и лифт №1 находится на 3-м этаже и свободен и т.д….».
Запишем это высказывание через высказывания
x1, y1, z1, x2, y2, z2, …, xn, yn, zn:
«1-й лифт вызывается тогда и только тогда, когда x1 или «не y1», «не z1», и в том случае x2 или «не y2 и не z2» и в этом случае …».
Таким образом
fI(x1, y1, z1, …, xn, yn, zn)=(x1V(( y1 Λ z1 ) Λ(x2V(( y2 Λ z2 ) Λ(…))..).
Аналогично
fII(x1, …, zn)=(y1V(( x1 Λ z1 ) Λ(y2V(( x2 Λ z2 ) Λ(…))..).
fIII(x1, …, zn)=(z1V(( x1 Λ y1 ) Λ(z2V(( x2 Λ y2 ) Λ(…))..).
10