close

Вход

Забыли?

вход по аккаунту

?

Alasheeva Diskretnaya matematika utchebnoe posobie

код для вставкиСкачать
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ»
Кафедра высшей математики
Е.А. Алашеева
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие
Самара
2017
1
УДК 519.2
Рекомендовано к изданию методическим советом ПГУТИ,
протокол № 16, от 20.01.2017 г.
Рецензент:
Зав каф.ЭиА ПГУТИ ,
д.ф.-м.н, доцент, Клюев Д.С.
Алашеева, Е. А.
А
Математика: учебное пособие / Е. А. Алашеева. – Самара: ПГУТИ,
2017. –145 с.
Учебное пособие «Дискретная математика» содержит такие разделы,
теория множеств, отношения, булева алгебра, комбинаторика, математическая
логика и теория графов разработано в соответствии с ФГОС ВО по
направлению подготовки 09.03.02 «Информационные системы и технологии»
и предназначено для студентов 2 курса факультета ИСТ для самостоятельной
подготовки.
ISBN
©, Алашеева Е.А., 2017
2
Оглавление
Теория множеств .........................................................................................................................6
Элементы теории множеств ..................................................................... 6
Способы задания множества .................................................................... 9
Операции над множествами ................................................................... 10
Основные законы алгебры множеств .................................................... 12
Примеры решения задач ........................................................................ 12
Задачи для самостоятельного решения ................................................. 15
Контрольные вопросы ............................................................................ 17
Отношения на множестах ........................................................................................................18
Соответствия и отображения ................................................................. 18
Отношения на множествах ..................................................................... 19
Свойства бинарных отношений ............................................................. 20
Понятие функции и отображения .......................................................... 24
Примеры решения задач ........................................................................ 26
Задачи для самостоятельного решения ................................................. 29
Контрольные вопросы ............................................................................ 31
Булевы функции ........................................................................................................................32
Определение функций алгебры логики ................................................ 32
Табличный способ представления функций алгебры логики............. 33
Графическое представление функции алгебры логики 34
Булевы функции ...................................................................................... 35
Существенные и фиктивные переменные булевой функции. Эквивалентные
булевы функции ...................................................................................... 38
Суперпозиция и формулы алгебры логики .......................................... 41
Булева алгебра ......................................................................................... 42
Нормальные формы логических функций ............................................ 45
Методы минимизации булевых функций ............................................ 52
Алгебра Жегалкина ................................................................................. 57
Полнота и замкнутость ........................................................................... 62
3
Основные замкнутые классы логических функций ............................. 64
Примеры решения задач ......................................................................... 69
Задачи для самостоятельного решения ................................................. 70
Контрольные вопросы ............................................................................ 72
Комбинаторика .......................................................................................................................... 74
Основные элементы комбинаторики..................................................... 74
Правила суммы и произведения ............................................................ 75
Формула включения и исключения....................................................... 77
Соединения без повторений ................................................................... 78
Производящие функции ......................................................................... 81
Задача о беспорядке ................................................................................ 83
Соединения с повторениями .................................................................. 84
Число Стирлинга второго рода .............................................................. 87
Задачи для самостоятельного решения ................................................. 89
Контрольные вопросы ............................................................................ 90
Математическая логика ...........................................................................................................91
Основы математической логики ............................................................ 91
Логика высказываний ............................................................................. 91
Алгебра высказываний ........................................................................... 93
Правила записи сложных формул. ........................................................ 94
Задачи для самостоятельного решения ................................................. 98
Контрольные вопросы ............................................................................ 99
Теория графов .......................................................................................................................... 100
Основные определения теории графов ............................................... 100
Матрица смежности .............................................................................. 102
Матрица инцидентности ....................................................................... 103
Список дуг.............................................................................................. 104
Степень вершины .................................................................................. 105
Задача о Кенигсбергских мостах ......................................................... 107
Изоморфизм ........................................................................................... 108
4
Плоские графы ....................................................................................... 113
Пути. Цепи. Циклы. Расстояния .......................................................... 115
Подграфы. Связность ............................................................................ 119
Деревья ................................................................................................... 121
Задачи для самостоятельного решения ............................................... 122
Контрольные вопросы .......................................................................... 126
Глоссарий ..................................................................................................................................128
Литература ................................................................................................................................ 145
5
Теория множеств
Элементы теории множеств
Понятия множество и элемент являются неопределенными, т.к.
выбираются
в
качестве
исходных.
Множество
представляет
собой
объединение в одно целое различимых между собой элементов. Синонимами
слова "множество" являются слова "совокупность", "класс", "коллекция",
"собрание", "список" и т.д. Для обозначения множеств и их элементов будем
использовать латинские буквы: прописные буквы для обозначения множеств
и строчные буквы для обозначения элементов. В случае необходимости при
обозначении
будем
использовать
индексы.
Таким
образом,
будут
использоваться следующие обозначения
для множеств:
A, B, ...,X, Y, Z,A1 ,A2 ,... ,
и для элементов:
a, b, ..., x, y, z,a1 , a2 ,...
Общим обозначением множества служит пара фигурных скобок ”{”, “}”
между которыми перечисляют элементы множества.
Например, {1, 3, 5, 7} или {a, b, c, d}.
Определение 1.1
Утверждение " а является элементом множества А" записывается в
виде аА, а утверждение " а не является элементом множества А" - в виде
аА, (в случае аА говорят также, что а принадлежит А, а в случае аА, что а не принадлежит А).
Определение 1.2
Множества Х и Y называются равными (обозначается X=Y), если они
состоят из одних и тех же элементов.
6
Свойства операции:
- X=X для любого множества Х;
- Х=Y  Y=X для любых множеств Х и ;
- Х= и = Х= для любых множеств Х, , .
Определение 1.3
Запись Х означает, что множества  и  не равны, т.е. что
существует элемент, принадлежащий одному из этих множеств и не
принадлежащий другому.
Определение 1.4
Множество называется пустым, если оно не содержит ни одного
элемента. Все
пустые множества равны друг другу, в силу чего для
обозначения любого пустого множества используется один и тот же символ
 (т.е. вводится стандартное обозначение пустого множества).
Определение 1.5
Если каждый элемент множества Х является также элементом
множества , то говорят, что Х содержится или включается в . В этом
случае пишут .
Свойства операций
- Х  х   х  для всех х  .
- ХХ для любого множества Х;
- Х и   Х= для любых множеств Х, ;
- Х и    для любых множеств X, Y, Z;
Определение 1.6
Множество Х называется подмножеством множества , если .
7
Замечание 1.1
Для любого множества Х подмножествами являются пустое множество
 и само Х.
Замечание 1.2
Пустое множество является подмножеством любого множества.
Множество, содержащее все элементы всех подмножеств, принимающих
участие в решении каких-либо задач, называют универсальным множеством и
обозначают символом U.
Определение 1.7
В тех случаях, когда одновременно имеют место соотношения Х и
Х (причем последнее особенно хотят подчеркнуть в явном виде), говорят,
что  строго включается в , и используют запись Х.
Свойства операций
- Х   и .
- для любого множества Х не верно, что Х  Х;
-  для любого множества Х;
- Х и   для любых множеств   .
-   ;
- Х  ,
Определение 1.8
Множество, состоящее из конечного числа элементов, называется
конечным , а множество, состоящее из бесконечного числа элементов,—
бесконечным.
8
Пример 1.1
Пусть А=3,6, В=2,4,6,8, Х= х х 2, = уу 2 и у 3 и
 z  z  6 (где запись ab означает утверждение "число a делится на
число b"). Тогда А, , , , , .
Определение 1.9
Декартовым или прямым произведением множеств А и В называется
множество А В всех пар вида (а, b), где а А, b В.
Пример 1.2
Пусть А={1,2}, В={3,4}, тогда
А  В  1,3, 1,4, 2,3, 2,4
Определение 1.10
Мощностью
конечного множества называется количество его
элементов. Обозначается: P(A) –множество всех подмножеств.
A  n, P( A)  2 n  2 A
Пример 1.3
Пусть А={1,2,3}, тогда
P A  0, 
1 , 2, 3, 1,2, 2,3, 1,3, 1,2,3
P  A  8
Способы задания множества
1) Перечисление элементов. Данный способ задания множества
подходит для конечных множеств, которые содержат относительно небольшое
число элементов.
Например: А = {1,3,5,6,889,-10}
2) Задание определяющего (характеристического) свойства. Данный
способ задания множества для множеств, которые невозможно задать
перечислением элементов.
Например: X = { x | 1 > х > 5, x є Z }; А = {a2 | a - четное число}.
9
Пример 1.4
Задать различными способами множество А всех четных чисел 2, 4,
6,…., не превышающих 1000.
Решение:
1. Перечислением: А={2, 4, 6, 8, 10, …, 998, 1000};
2. Описанием: А={x|xN и х/2N, N1000};
(N – множество
натуральных чисел 1, 2, 3, ….)
3. Порождающей процедурой: а) 2А; б) если хА, то (х+2)А; в)
х1000.
Операции над множествами
Определение 1.11
Объединением множеств A и B (обозначается A  B) называется
множество, состоящее из всех элементов, принадлежащих хотя бы одному из
этих множеств, т.е A  B = а  а  A или а  B.
Определение 1.12
Пересечением
множеств A и B (обозначается AB) называется
множество, состоящее из всех элементов, принадлежащих каждому из этих
множеств, т.е.
А B = а а  А и а  B.
Определение 1.13
Разностью множеств А и B (обозначается А \ B) называется
множество, состоящее из всех элементов множества A , не принадлежащих
множеству B, т.е. А \ B =а а  А и а  B.
Определение 1.14
Дополнением
(обозначается
множества
А
в
универсальном
множестве
U
A , А) называется множество, состоящее из всех элементов
универсального множества U, не принадлежащих множеству А, т.е. А = U \
A.
10
Определение 1.15
Симметрической разностью множеств A и B (обозначается A  B)
называется множество, состоящее из всех элементов, принадлежащих в
точности одному из этих множеств, т.е. A  B  а либо а  A и а  B, либо
а  A и а  B. Операция симметрической разности может быть выражена
через операции объединения, пересечения и разности следующим образом A
 B = (A \ B)  (B \ A) = (A  B) \ (A  B).
Операции над множествами можно проиллюстрировать графически с
помощью кругов Эйлера (их также называют диаграммами Венна). В этом
случае исходные множества изображают кругами, а множество-результат
выделяют штриховкой.
U
A
B
A
A∪B
а)
B
A
A∩B
б)
A\B
в)
U
U
А
U
B
U
A
AB
д)
А
г)
Рисунок 1.1 Операции над множествами: а) объединение; б)
пересечение; в) разность; г) дополнение; д) симметрическая разность.
11
Основные законы алгебры множеств
Ассоциативные законы
Коммутативные законы
А  (В  С) = (А  В)  С
АВ=ВА
А  (В  С) = (А  В)  С
АВ=ВА
Дистрибутивные законы
АВ=ВА
А  (В  С) = (А  В)  (А  С)
А  (В  С) = (А  В)  (А  С)
Законы с  и U
А=А
АU=А
А A= U
А=
АU=U
А A= 
U =

=U
Законы де Моргана
Законы идемпотентности
AB = A
B
АА=А
AB = A
B
АА=А
Законы склеивания
A =А
(А  В)  ( A  В) = В
(А  В)  ( A  В) = В
Законы поглощения
А  (А  В) = А
А  ( A  В) = А  В
А  (А  В) = А
А  ( A  В) = А  В
Примеры решения задач
Задача 1.1
Верно ли, что: 1). {{1,2}, {2,3}}={1,2,3}? 2).{{1,2}}={1,2}?
Решение
1). Нет, так как элементами первого множества являются подмножества
{1,2} и {2,3}, а второго – элементы 1,2,3.
12
2). Нет, так как первое множество одноэлементное, состоящее из
одного элемента - подмножества, а второе имеет два элемента 1 и 2.
Задача 1.2
Перечислить элементы следующих множеств:
1). А={a|aB, B={1,2,3}};
2). A={a|aB, B={1,2,3}}.
Решение
1). Так как аВ, а В – трехэлементное множество, то имеется 23=8
подмножеств: А={{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, }.
2). Так как аВ, то А=В={1,2,3}.
Задача 1.3Доказать, используя тождества алгебры множеств, что
Решение
Используя тождества алгебры множеств, получаем
A  ( B \ A)  A  ( B  A )  ( A  B)  ( A  A ) 
 ( A  B)  I  A  B.
Задача 1.4 Упростить выражение
( A  B  C)  ( A  B  C)  B  C .
Решение
Используя законы и тождества алгебры множеств, получаем:
( A  B  C)  ( A  B  C)  B  C 
 [( A  A )  B  C ]  B  C 
I  B  C  B  C  (B  C)  (B  C)  I
13
Задача 1.5
Построить диаграммы Венна для множеств А, В, С, DI, если
АВСD, A  B   , A  D   .
Решение
Одно из возможных решение может быть представлено следующей
диаграммой:
Рисунок 1.2
Задача 1.6
Доказать аналитически:
( A  B)  C  ( A  C )  ( B  C ) .
Решение
Введем обозначения:
D  ( A  B)  C ; E  ( A  C )  ( B  C ) .
а). Пусть x  D , тогда имеет место либо x  A  B , либо x  C . Если
x  A  B , тогда x  A и x  B и в таком случае x  A  C и x  B  C или, что
тоже самое,
x  ( A  C )  ( B  C ) , т.е.
xE.
Если x  C , тогда можно
записать x  A  C и x  B  C одновременно. Откуда, очевидно, и в этом
случае
x  ( A  C )  ( B  C ) , т.е.
xE.
Итак, если x  D , то x  E . Следовательно, D  E.
б). Пусть x  E . Тогда x  A  C и x  B  C . Если x  A  C , то либо
x  A, либо x  C. Но если x  C , то (см. п.а) x  D . Если же x  C , тогда
x  B. Из последнего следует, что x  A и x  B, т.е. x  A  B , или, что тоже
самое,
x  ( A  B)  C , т.е.
xD.
Итак, если x  E то x  D . Следовательно, E  D .
14
Из пп. а и б следует, что D  E и E  D . Следовательно, D=E, т.е.
( A  B)  C  ( A  C )  ( B  C ) . Тождество доказано.
Задача 1.7
Из 100 студентов 28 изучают английский язык,
8
A
28
10
N
английский и немецкий язык, 10 – английский и
30
42
F
30 – немецкий язык, 42 – французский язык, 8 –
5
3
французский язык, 5 – немецкий и французский
язык и 3 студента – все 3 языка. Сколько человек
u
не изучают ни одного языка? Сколько изучают
только французский язык?
Пусть U – множество студентов. По условию мощность множества |U|=100
Пусть А – множество студентов, изучающих английский язык, N – множество
студентов, изучающих немецкий язык, F – множество студентов, изучающих
французский язык.
По условию |A| = 28, |N| = 30, |F| = 42, |A  N| = 8, |A  F| = 10, |N  F| = 5, |A 
N  F| = 3.
Необходимо найти множество студентов, не изучающих ни одного языка, т.е.
|U\(A  N  F)| = |U| - (|A| + |N| + |F|) + |A  N| + |A  F| + |N  F| - |A  N  F| =
20 и множество студентов, изучающих только французский язык |F\(A  N)| =
|F| - (|A  F| + |N  F|) + |A  N  F| = 30.
Задачи для самостоятельного решения
№ 1 Пусть А={{1,2,3}, {1,3}, 1, 2}. Верно ли, что {1,2}А? {1, 2}A?
№ 2 Перечислить элементы множества
A  {x | x 
n
, n=1, 2,…}.
n2  n  3
15
№ 3 Перечислить элементы следующих множеств:
A  {x | x  {{a, b}, {a, b, c}, {a, c, d}}};
B  {x | x  {a, b, c, d}};
C  {x | x  {a, b, c, d}}.
№ 4 Перечислите все элементы множества
P  A  {{1, 2}, {3}, 1}.
№ 5 Пусть А – произвольное множество. Что представляют собой
следующие множества:
A   ? A   ? A \  ? A \ A?
№6 Множество А состоит из натуральных чисел, делящихся на 4,
множество В – из натуральных чисел, делящихся на 10, множество С – из
натуральных чисел, делящихся на 75. Из каких чисел состоит множество
A  B C?
№ 7 Даны произвольные множества А, В, С такие, что:
1.
A  B и A  C;
2.
A  C и B  C.
Чему равно
A  B C? A  B  C?
№ 8 Даны произвольные множества А, В и С такие, что A  B, . Чему
равно
A  B  C ? A  B  C ? A \ C ? C \ A?
№ 9 На кафедре иностранных языков работают 18 преподавателей. Из
них 12 преподают английский язык, 11 – немецкий язык, 9 – французский
язык. 5 преподавателей преподают английский и немецкий языки, 4 –
английский и французский, 3 – немецкий и французский. Сколько
преподавателей преподают все три языка? Сколько преподавателей
преподают только два языка?
16
Контрольные вопросы
1.
Дать определение множества.
2.
Привести примеры конечных и бесконечных множеств.
3.
Указать существующие способы задания множеств.
4.
Дать определения пустого и универсального множеств.
5.
Какие множества называются равными?
6.
Что называют подмножеством множества?
7.
Ввести понятия операций над множествами.
8.
Что называется объединением множеств?
9.
Что называется пересечением множеств?
10.
Что называется разностью множеств?
11.
Что называется дополнением множеств?
12.
Что называется симметрической разностью множеств?
13.
Привести примеры операций над множествами с помощью кругов
Эйлера.
14.
Перечислить основные законы и теоремы алгебры множеств.
15.
Записать коммутативные законы.
16.
Записать дистрибутивные законы.
17.
Записать ассоциативные законы.
18.
Записать законы с пустым и универсальным множеством.
19.
Записать законы идемпотентности.
20.
Записать законы поглощения.
21.
Записать законы де Моргана.
22.
Записать законы склеивания.
23.
Что такое декартово произведение множеств?
24.
Что такое мощность множества?
17
Отношения на множестах
Соответствия и отображения
Определение 2.1
Если по какому-либо правилу для элементов множества A ставится в
соответствие один или несколько элементов множества B, то формируется
множество упорядоченных пар {(x, y)| xA, yB}. Тогда множество A
называют областью отправления, а множество B - областью прибытия.
A
B
x1 , x2 , x3
y1 , y2 , y3
Рисунок 2.1
На рисунке показаны области отправления A={x1, x2, x3} и прибытия –
B={y1, y2, y3} для пар {( xi , y j )| xi A, y j B}.
Определение 2.2
Проекция на первую компоненту пары 1{(x, y)} формирует область
определения A0={x1, x3}A, а на вторую компоненту 2{(x, y)} - область
значений B0={y2, y3}B. Элементы yjB0 называют образом элемента хiA0, а
элемент хiA0 - прообразом элемента yjB0.
Определение 2.3
Если для одного или нескольких элементов хiA0 существует
несколько образов, т.е. |{y}xi |>1, то такое множество упорядоченных пар
называют соответствием. (У x2 два образа y2 и y3 )
18
Определение 2.4
Если для каждого элемента хiA0 существует единственный образ, т.е.
|{y}xi |=1, то такое множество упорядоченных пар называют отображением.
Отношения на множествах
Определение 2.5
Отношением на множествах X и Y называется произвольное
подмножество прямого (декартова) произведения этих множеств
  Х × Y = {(x,y)| xX, yY}.
Если (x,y), то (x,y) находятся в отношении  или связаны
отношением  или х  y или y = (х).
Между математическими объектами такими отношениями могут быть
{=, , , , <, }, а между “нематематическими” объектами {“x принадлежит
y”, “x часть y”, “x смежный y”, “x родственник y”, “x родитель y”, “x находится
рядом с y”,..}.
Определение 2.6
Область определения D бинарного отношения - множество первых
D = {x | (x,y)  }.
элементов каждой упорядоченной пары
Определение 2.7
Область значений Е бинарного отношения - множество вторых
элементов каждой упорядоченной пар
Е  = {y | (x, y)  }.
Способы задания отношений
Список пар
Характеристическая функция
Пример:  = {(1,5), (2,4), (3,6), (6,2)}
Пример:  = {(n,m)| n = 2*m
на   Х2, Х = {1,2,3,4,5,6}
19
Матрица отношения
Матрица
отношения
строится
следующим образом: если xy (х
Графическое изображение
находится в отношении с у), то в
Пример:  ={(1,5), (2,4), (3,6), (6,2)} клетку ставим 1 (  x, y   1 ).
на   Х2, Х = {1,2,3,4,5,6}
Пример:  ={(1,5), (2,4), (3,6), (6,2)}
1
4
2
5
3
на   Х2, Х = {1,2,3,4,5,6}
6
1
2
3
4
5
6
1
0
0
0
0
1
0
2
0
0
0
1
0
0
3
0
0
0
0
0
1
4
0
0
0
0
0
0
5
0
0
0
0
0
0
6
0
1
0
0
0
0
Определение 2.8
Каждое отношение ρ=(xi, xj) или ρ=(x1, x2,..,xn) есть кортеж, а их
множество есть подмножество X2 или Xn, т.е. R={(xi, xj)| xi, xjX}X2 или
R={(x1, x2,..,xn)| xiX}Xn.
Определение 2.9
Если n=1, то отношение называют унарным или одноместным.
Если n=2, то отношение называют бинарным или двухместным.
Если n=n, то отношение называют n- арным или n-местным.
Свойства бинарных отношений
Определение 2.10
Бинарное отношение рефлексивно, если для каждого хiХ имеем ρ(xi;
xi)=1. Такими отношениями являются “..=..”, “..быть похожим..”, “..быть
20
изоморфным..”, “..быть эквивалентным..” и т.п. При матричном описании
такого отношения на главной диагонали матрицы будут только “1”, т.е. ρ(xi,
xi)=1.
Определение 2.11
Бинарное отношение антирефлексивно, если для каждого хiХ имеем
ρ(xi, xi)=0. Такими отношениями являются “.... ”, “..<..”, “быть родителем” и
т.п.. При матричном описании такого отношения на главной диагонали
матрицы будут только “0”, т.е. ρ(xi, xi)=0.
Определение 2.12
Бинарное отношение симметрично, если для любой пары (xi, xj)R
имеем ρ(xi, xi)=ρ(xj, xi)=1. Такими отношениями являются “....”, “..быть
похожим..”, “..быть эквивалентным..”, “..быть родственником..” и т.п.. При
матричном задании такого отношения будет симметричное расположение “1”
относительно главной диагонали, т.е. ρ(xi, xi)=ρ-1(xj, xi).
Определение 2.13
Бинарное отношение асимметрично, если для любой пары (xi, xj) при
ij имеем ρ(xi, xi)ρ(xj, xi), а при i=j имеем ρ(xi, xi)=0. Такими отношениями
являются “....”, “..<..”, “быть родителем” и т.п. При матричном задании такого
отношения это означает несимметричное расположение “1” относительно
главной диагонали и наличие “0” на главной диагонали.
Определение 2.14
Бинарное отношение транзитивно, если для любых элементов xi, xj,
xkХ выполняется: при ρ(xi, xj)=1 и ρ(xj, xk)=1 следует ,что ρ(xi, xk)=1. Такими
отношениями
являются
“....”,
“..<..”,
родственником” и т.п.
21
“быть
родителем”,
“быть
Определение 2.15
Бинарное отношение, удовлетворяющее условиям рефлексивности,
симметричности и транзитивности называют отношением эквивалентности.
Такими
отношениями
являются
“..=..”,
“..быть
похожим..”,
“..быть
родственником..”. Отношение эквивалентности обозначают ρ~(xi, xi) или ~(xi,
xi). Отношение ρ~ позволяет формировать классы эквивалентности по образцу
х, в виде подмножества множества X, т.е. K ={x| ρ~(x, x)=1, x, xX}X.
Попарно различимые классы эквивалентности K1, K2,...Kn позволяет
выполнять разбиение множества Х на подмножества, т.е. Х={Х1, Х2,..,Хn}.
Определение 2.16
Бинарные отношения, удовлетворяющие условиям рефлексивности,
антисимметричности и транзитивности называют отношением частичного
порядка. Такими отношениями являются “....”, “....”, “..быть не старше..” и
т.п.. Отношение порядка обозначают для элементов множества: ρ  (xi, xi) или
 ( xi, xi), а для подмножеств множества: ρ(Xi, Xj) или (Xi, Xj). Задание
отношения  (xi, xj) позволяет формировать частичный порядок элементов
множества X, а задание отношения (Xi, Xj) – частичный порядок на
подмножествах множества X.
Определение 2.17
Композиция отношений  и  - отношение, состоящее из пар  ○  =
={(x, z)| х  у, y  z }
Пример 2.1
Отношения  и  заданы на множестве Х = {1, 2, 3, 4, 5, 6,}.
 = {(1,4), (2,5), (3,6), (4,1), (6,3)},
 = {(1,1), (2,3), (3,4), (4,5), (5,6), (6,6)}.
Область определения D = {1, 2, 3, 4, 6}.
Область значений E  = {1, 3, 4, 5, 6}.
22
Обратное отношение -1 = {(4,1), (5,2), (6,3), (1,4), (3,6)}.
Отношение  - антирефлексивно, не симметрично, не транзитивно.
Область определения D = {1, 2, 3, 4, 5, 6}.
Область значений E  = {1, 3, 4, 5, 6}.
Отношение  - не рефлексивно, антисимметрично, не транзитивно.
Композиция  ○  = {(1,5), (2,6), (3,6), (4,1), (6,4)}.
Пример 2.2
Отношение = { (x, y) | сравнение по модулю m, x,y  N }.
Отношение сравнения по модулю m на множестве натуральных чисел:
x = y mod m, что означает x и y имеют одинаковый остаток при делении на m
(классы вычетов по модулю m).
Отрезок натурального ряда N4={1,2,3,4}.
Отношение сравнения по модулю 2 на N4 :
 = { (1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2) ,(4,4)}.
Область определения D = {1, 2, 3, 4}.
Область значений
E = {1, 2, 3, 4}.
Отношение  - рефлексивно, симметрично, транзитивно.
Отношение  - отношение эквивалентности.
Классы эквивалентности: [ 1 ]={ 1,3 }=[ 3 ]
[ 2 ]={ 2,4 }=[ 4 ].
Пример 2.3
Отношения  и  заданы на множестве N4 .
 ={ (1,2), (2,3), (1,3), (3,4), (2,4), (1,4) }
={ (1,1),(2,2),(3,3),(4,4) }.
Область определения D = { 1, 2, 3 }.
Область значений
E = { 2, 3, 4 }.
Отношение  - антирефлексивно, антисимметрично, транзитивно.
23
Отношение  - отношение строгого порядка.
Область определения D = { 1, 2, 3 ,4 }.
Область значений
Отношение 
E  = { 1, 2, 3, 4 }.
- рефлексивно, симметрично,
антисимметрично,
транзитивно.
Отношение  - отношение нестрогого частичного порядка.
Отношение  - отношение эквивалентности.
Классы эквивалентности: [ 1 ]={ 1 }
[ 2 ]={ 2 }
[ 3 ]={ 3 }
[ 4 ]={ 4 }.
Понятие функции и отображения
Определение 2.18
Бинарное отношение f между множествами A и B (f  (AB) называется
функцией, если для элемента xA найдется не более одного элемента yB вида
(x,y)f. При этом, если для каждого элемента x из А имеется один элемент y вида
(x,y)f, то функция f называется всюду (полностью) определенной, в противном
случае частично определенной (недоопределенной).
Определение 2.19
Множество A образует область определения D(f) функции f, множество
B – область значений E(f). Понятия D(f) и E(f) являются содержательными. В
общем случае D(f)  A и E(f)  B.
Замечание 2.1
Для всюду определенной функции: D(f) = A, для частично
определенной: D(f)  A. Всюду определенную функцию называют еще
отображением.
24
Если f – функция между множествами A и B, то этот факт может быть
записан как f: AB (читается: функция f из A в B). Если (x,y)f, то пишут: y=f(x)
(y значение функции f при значении аргумента x ) или f : xy (функция f
ставит в соответствие элементу x элемент y). Последние обозначения часто
используют для того, чтобы описать правило, определяющее функцию.
Пример 2.4
Функция f: AA, где A = {-1,0,1} может быть определена следующим
отношением f: xx3.
Определение 2.19
Функция f: AB называется функцией A на B или сюръективной
функцией (сюръекцией), если область значения E(f) = B. Это означает, что
HA
 B. В общем
bB имеем f -1  . Если f сюръекция, то будем писатьf:A 
случае, когда E(F)  B, говорят, что f есть функция из A в B.
Определение 2.20
1
Функция f: AB является инъективной (инъекция), если отношение f
является частичной функцией, т. е. для любых элементов х1, х2 D(f), если х1 
х2  f(х1)  f(х2).
Замечание 2.2
Если f: AB и f сюръективна, то bB имеем
f-1(A)\. Это может
быть проинтерпретировано следующим образом: каждая точка из B является
«острым концом», по крайней мере, одной f – стрелы, выходящей из A
Определение 2.21
Функция f называется взаимнооднозначным соответствием между
множествами A и B или биективной функцией (биекцией), если f одновременно
является сюръекцией и инъекцией (обозначается f: AB).
25
Пример 2.5
Пусть  = { (x, y)  R2 | y2 + x2 = 1, y > 0 }.
у
y2 + x2 = 1, y > 0
х
Отношение  функционально, не всюду определено ("есть одинокие х
"), не инъективно (есть разные х, которым соответствуют одинаковые у), не
сюръективно ("есть одинокие у "), не биекция.
Примеры решения задач
Задача 2.1
Проверить, является ли D отношением эквивалентности на R, если
D={(x;y)| sin x = sin y}.
Решение
1.
D – рефлексивно, так как для любого
a R ( a, a )D, т.е. для
любого xR имеем sin x = sin x.
2.
D – симметрично, так как для любой пары ( a, b ) D имеем ( a, b )
D, т.е. для любых (x,y)R из (x,y)D следует, что sin x = sin y, тогда и sin
y = sin x, следовательно, (y,x)D.
3. D – транзитивно, так как для любых а,b,c R из того что ( a, b )
D и ( b, c )D следует, что ( a, c ) D, т. е. если (x,y)D, то sinx=siny, если (y,z)
D, то sin y = sin z, тогда sin x=sin z, следовательно, (x,z) D.
Задача 2.3
Задано бинарное отношение R на множестве М={1, 2, 3, 4}. Является
ли оно рефлексивным, симметричным, антисимметричным, транзитивным?
26
Найти область определения R, область значений R, обратное отношение R-1,
пересечение и объединение отношений R и R-1
R={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2), (4,3), (4,4).
Решение
Отношение R, заданное на множестве М, называется рефлексивным,
если для всякого х из этого множества хRх истинно. Заданное отношение не
является рефлексивным, так как нет пар (2,2) и (3,3).
Отношение R, заданное на множестве M называется симметричным,
если на этом множестве из xRy следует yRx. Заданное отношение не является
симметричным, т.к., например, пара (1,2)  R, а (2,1) R.
Отношение
R,
заданное
на
множестве
M
называется
антисимметричным, если на этом множестве из xRy и yRx следует x=y.
Заданное отношение не является антисимметричным, так как ему принадлежат
пары (1,4) и (4,1), но 14.
Отношение
R,
заданное
на
множестве
M
называется
антирефлексивным, если для любого x  M xRx ложно. Заданное отношение
антирефлексивно, так как (уже было показано) нет пар (2,2) и (3,3).
Отношение R, заданное на множестве M называется транзитивным,
если на этом множестве из xRy и yRz следует xRz. Заданное отношение
является транзитивным, так как для любых двух пар (a,b) и (b,c) следует, что
(a,c) R, где а, b, с  М.
Областью определения отношения R называется множество R ={x| (у)
xRy}. Следовательно, областью определения R является двухэлементное
множество {1, 4}.
27
Областью значений отношения R называется множество R={y|(x)
xRy}. Следовательно, областью значений является все множество М={1, 2, 3,
4}.
Обратным отношением для R называется отношение R-1={(y,x)|(x,y)
R}.
Обратное отношение R-1={(1,1), (2,1), (3,1), (4,1), (1,4), (2,4), (3,4),
(4,4)}.
Пересечение R и R-1 равно R  R-1={(1,1), (4,1), (1,4), (4,4)}.
Объединение R и R-1 равно R  R-1={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2),
(4,3), (4,4), (2,1), (3,1)}.
Задача 2.3
График функции f(x) представляет собой ломанную, звенья которой
параллельны координатной оси, либо биссектрисам координатных углов.
Координаты каждой вершины ломанной являются целыми числами. Функция
f(x) определяет отношение Rf на множестве Х=[0, 5]: xRfy  f(x)=f(y), т.е. х
находится в отношении Rf с у тогда и только тогда, когда f(x)=f(y).
Доказать, что Rf – эквивалентность на Х. Перечислить все классы
эквивалентности.
Рисунок 2.2
Решение
Рефлексивное, симметричное и транзитивное отношение  на
множестве Х называется отношением эквивалентности на множестве Х.
28
Классом
эквивалентности,
порожденным
элементом
х,
называется
подмножество множества Х, состоящее из тех элементов у Х, для которых ху
и обозначается [x]. [x]={y| у Х и ху}.
Сначала докажем, что отношение Rf есть отношение эквивалентности.
Действительно,
рефлексивность
хRfy,
очевидна,
так
как
f(x)=f(y).
Симметричность: пусть хRfy т.е. f(x)=f(y), но тогда f(y)=f(x) и, следовательно,
yRfx. Транзитивность: если f(x)=f(y), а f(y)=f(z), то f(x)=f(z) и, следовательно,
хRfy и уRfz влечет xRfz.
Классы эквивалентности: {, 2-, 2+}, [4, 5], {0,2}, {1,3}, {3+}, где
  (0,1).
Задачи для самостоятельного решения
№ 1 Является ли множество {(1, 2), (3, 4), (5, 6), (7, 8)} бинарным
отношением. Почему?
№ 2 Выписать элементы множества {0, 1, 2}{a,b}. Найти область
определения и область значений этого отношения, построить его график.
№ 3 Задано бинарное отношение на множестве М={1,2,3,4}. Является
ли оно рефлексивным, симметричным, антисимметричным, транзитивным?
Почему?
Найдите область определения R, область значений R, обратное
отношение R-1.
а) R={(1,1), (1,2), (1,3), (2,3), (3,3), (4,1), (4,4)};
б) R={(1,1), (1,2), (2,1), (2,3), (3,2), (3,3), (4,4)};
в) R={(1,1), (1,4), (2,3), (3,2), (4,1)};
г) R={(1,1), (1,2), (1,4), (2,2), (2,3), (3,3), (4,4)};
д) R={(1,1), (1,3), (2,2), (3,3), (4,1), (4,4)};
е) R={(1,1), (1,2), (3,1), (3,2), (3,3), (4,4)};
ж) R={(1,1), (1,2), (2,2), (2,3), (3,4), (4,4)};
29
з) R={(1,2), (1,3), (2,2), (2,3), (3,3), (4,3)};
и) R={(1,4), (2,3), (3,2), (3,4), (4,1), (4,3)};
к) R={(2,1), (3,1), (3,2), (3,3), (3,4), (4,1)}.
№ 4 Найти область определения, область значений, построить график
каждого из следующих отношений:
2
2
а) {( x, y)  R  R | x  y };
б) {( x, y)  R  R || x | 2 |
y | 1};
2
2
в) {( x, y)  R  R | x  y  1и
г) {( x, y)  R  R |
x  0};
y  0, y  x, x  y  1};
2
2
д) {( x, y)  R  R | x  ( y  1)  1};
2
2
е) {( x, y)  R  R | x  y  1}.
№ 5 Пусть f: R  R задано формулой:
1)f ={ (x, y) R2 | y = e| x | }
2)f={ (x, y)  R2 | y = cos(3x) - 2 }
3)f={ (x, y)  R2 | y = 3x2 - 2 }
4)f={ (x, y)  R2 | y = 1 / (x + 2) }
5)f={ (x, y)  R2 | y = ln(2x) - 2 }
6)f={ (x, y)  R2 | y = | 4x -1| + 2 }
7)f={ (x, y)  R2 | y = 1 / (x2+2x-5)}
Определить, является ли отображение f инъективным, сюръективным,
биективным
№ 6 Заданы множества N1 и N2. Вычислить множества:
(N1 х N2)  (N2 х N1);
(N1 х N2)  (N2 х N1);
(N1  N2) x (N1  N2);
30
(N1  N2) x (N1  N2),
где N1 = {цифры номера зачетной книжки};
N2 = {цифры даты и номера месяца рождения}.
Определить отношения на множестве N1 N2.
№ 7 Отношения  и  заданы на множестве N6={1,2,3,4,5,6}.
Описать отношения , ,  -1,  ○ , -1 ○  списком пар.
Найти матрицы отношений  и .
1) = { (m, n) | m > n }

= { (m, n) | сравнение по модулю 2}
2) = { (m, n) | (m - n) делится на 2}

= { (m, n) | m делитель n }
3) = { (m, n) | m < n }

= { (m, n) | сравнение по модулю 3}
Контрольные вопросы
1. Что такое соответствие?
2. Определение бинарного отношения.
3 .Способы описания бинарных отношений.
4. Область определения и область значений.
5. Свойства бинарных отношений.
6.Отношение эквивалентности и классы эквивалентности.
7. Отношения порядка: строгого и нестрого, полного и частичного.
8. Что такое отображение?
9. Функциональные отношения.
10. Инъекция, сюръекция, биекция.
31
Булевы функции
Определение функций алгебры логики
Определение 3.1
Функцией алгебры логики (булевой функцией) называется функция,
аргументы
которой
и
ее
значения
могут
принимать
значения
из
двухэлементного множества. (обычно из Е2 = { 0,1 } ).
Любая логическая функция n переменных, как правило, задается
таблицей, в левой части которой перечислены
2n
наборов значений
переменных; в правой части - значения функции на этих наборах. Наборы
переменных – это двоичные числа, расположенные в возрастающем порядке.
Число различных функций n переменных, обозначается Р2(n). Оно
n
равно Р2(n)= 22 – числу различных двоичных векторов длины 2 n .
Пусть (х1, х2, …, хn) – логический набор, тогда х12n-1+х22n-2+…+xn20 –
номер набора.
Пример 3.1
(0,1,1) = 022 + 121+120 = 3
(0,0,1,1) = 023+022 +121+120 = 3
Определение 3.2
Логическая переменная – это переменная, которая может принимать
только два значения: истина или ложь.
Определение 3.3
Функция алгебры логики – f(x1,x2, …,xn) – это функция, у которой все
аргументы есть логические переменные, и сама функция принимает только
логические значения.
Пример 3.2 Построим всевозможные двоичные наборы длиной n = 3.
По теореме, приведенной выше, их количество равно 2n = 23 = 8.
32
Набор
Номер
двоичного
х1
х2
х3
0
0
0
0
1
0
0
1
2
0
1
0
3
0
1
1
4
1
0
0
5
1
0
1
6
1
1
0
7
1
1
1
набора
Табличный способ представления функций алгебры логики
Любую булеву функцию можно представить таблицей, имеющей 2n
строк. Такая таблица называется таблицей истинности. В левой части
таблицы перечисляются всевозможные двоичные наборы значений
аргументов, а в правой части – значения некоторой булевой функции.
№
X1
х2
…
хn f (х1, х2,…,хn)
0
0
0
…
0
1
1
0
0
…
1
2
…
… …
…
…
…
1
…
1
2 n
2n-1
1
33
Графическое представление функции алгебры логики
Булеву функцию можно представить в виде n-мерного единичного куба:
если наборам значений аргументов сопоставить точки n-мерного
пространства, то множество 2n наборов определяет множество вершин nмерного куба.
Одномерный куб (n = 1)
Двумерный куб (n = 2)
Трехмерный куб (n = 3)
Четырехмерный куб (n = 4)
34
Булевы функции
Для функции одной переменной ( n=1 ). число различных наборов
равно 2 – 0 и 1. Число различных функций равно Р2(1) = 22 = 4, а различные
векторы длины 2 имеют вид
(0,0), (0,1), (1,0), (1,1).
х
f0
f1
f2
f3
0
0
0
1
1
1
0
1
0
1
f0(x) = 0 - константа ноль,
f1(x) = x – тождественная функция,
f2(x) = x –отрицание x (читается “ не х“),
f3(x) = 1 – константа единица.
Для функции двух переменных ( n=2 ) число различных наборов переменных
будет 22 = 4, а разных функций Р2(2) = 24 = 16.
x1
0
0
1
1
x2
0
1
0
1
f0
0
0
0
0
тождественный 0, const 0.
f1
0
0
0
1
х1 и х2, х1х2, х1&х2, х1х2 – конъюнкция,
логическое «и»
f2
0
0
1
0
запрет х2, x1  x 2 ; х1, но не х2
f3
0
0
1
1
х1 повторение первого аргумента
f4
0
1
0
0
запрет х1; не х1, но х2
35
f5
0
1
0
1
х2 повторение второго аргумента
f6
0
1
1
0
x1  x 2 , x1  x 2 -
сложение по модулю 2,
неравнозначность
f7
0
1
1
1
х1х2 – дизъюнкция, сумма, логическое
«или»
f8
1
0
0
0
х1х2 – стрелка Пирса, функция Вебба,
;
f9
1
0
0
1
логическое “или-не”
х1х2 эквивалентность,
равнозначность,
тождество
f10
1
0
1
0
x2
-
отрицание,
инверсия
второго
аргумента
f11
1
0
1
1
х2х1 – обратная импликация
f 12
1
1
0
0
x1 - отрицание первого аргумента
f13
1
1
0
1
х1х2 – импликация
f14
1
1
1
0
х1 | х2 – штрих Шеффера, логическое «ине »,
f15
1
1
1
1
&
f  1 – тождественная 1, константа 1
Условные приоритеты булевых функций
1. ( )
2. отрицание ( x )
3. & 
4.    ≡
36
Пример 3.3
Дана функция
F ( x, y , z )  x  y  z  y & ( z  x ) .
Составить таблицу истинности функции 3-х переменных: F (x, y, z).
Изобразить функцию графически.
Решение
Расставим порядок выполнения действий, соблюдая приоритеты.
2
F ( x, y , z )  x  y  z  y & ( z  x )
5
3
6
4
1
Выполним операции согласно порядку от 1 до 6
x
y
z
1
2
3
4
5
F(x,y,z
)
0
0
0
1
0
1
0
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
1
0
1
1
0
1
0
0
1
0
1
0
1
1
1
0
1
1
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
Таблица истинности функции F(x, y, z)
37
Изобразим функцию на кубе:
Существенные и фиктивные переменные булевой функции.
Эквивалентные булевы функции
Определение 3.3
Переменная xi функции алгебры логики называется существенной,
если имеет место неравенство:
f1(x1, x2, … , xi-1, 0, xi+1, … , xn)  f2(x1, x2, … , xi-1, 1, xi+1, …, xn).
В противном случае говорят, что функция несущественно зависит от xi,
и xi является ее фиктивной переменной.
Определение 3.4
Эквивалентными
(равносильными)
функциями алгебры логики
называются функции, имеющие одинаковые таблицы задания функции. Будем
обозначать эквивалентные функции так: f1 ~ f2.
Пример 3.4 Из таблицы для булевых функций двух переменных (см.
лекцию 3): f11 ~ f 4 , f2 ~ f13
Пример 3.5 Покажем, что в функциях f3, f5, f10, f12 из таблицы для
булевых функций двух переменных одна из переменных является фиктивной.
Из таблицы видно, что f3( 0, 0 ) = f3( 0, 1 ) = 0, f3( 1, 0 ) = f3( 1, 1 ) = 1,
т.е. изменение значения переменной х2, при одинаковых значениях х1, не
приводит к изменению значения функции. Следовательно х2 – фиктивная
38
переменная, а значит функция f3( x1, x2 ) является функцией только одной
переменной х1.
Исключая х2 , получим – таблицу задания функции f3. Из этой таблицы
следует, что f3( x1, x2 ) ~ x1, т.е. функция эквивалентна переменной х1.
х1
f3
0
0
1
1
Аналогичные рассуждения приводят к следующим соотношениям для
остальных функции: f5( x1, x2 ) ~ x2, f10( x1, x2 ) ~ x 2 , f12( x1, x2 ) ~ x1 .
Таким образом, из 16 функций 6
функций имеют фиктивные
переменные.
Алгоритм нахождения фиктивных аргументов
Для нахождения фиктивных аргументов необходимо задать ФАЛ
(функцию алгебры логики) таблично:
1)
Разбить множество наборов аргументов ФАЛ на 2 подмножества:
1-е подмножество, на котором функция принимает значение 0, и 2-е
подмножество, где функция принимает значение 1, соответственно множества
Т0 и Т1.
2)
Для проверки фиктивности аргумента xi вычеркиваем столбец,
который ему соответствует, и проверяем, не появились ли в двух
подмножествах одинаковые наборы. Если такие наборы не появились, то x i
является фиктивным.
39
Пример 3.6
Имеет ли функция
F ( x, y , z )  x  y  z  y & ( z  x )
фиктивные аргументы?
Решение:
Зададим функцию таблично:
x
y
z
F(x,y,z)
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
Множество Т0
x
y
z
F(x,y,z)
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
0
1
1
1
0
40
Множество Т1
x
y
z
F(x,y,z)
0
0
1
1
0
1
0
1
1
0
0
1
Если вычеркнуть x во множестве Т0 и Т1, то появятся одинаковые
наборы. Следовательно, х не является фиктивным аргументом функции
F(x,y,z). Аналогично для аргументов y и z. В результате, функция F(x,y,z) не
имеет фиктивных аргументов.
Суперпозиция и формулы алгебры логики
Определение 3.5
Суперпозицией функций
f1, … , fm
называется функция
f,
полученная с помощью подстановок этих функций друг в друга и
переименования переменных.
Пример 3.7 Пусть даны функции
f1( x1, x2 ) = ( 0, 1, 1, 0 ) и f2( x1, x2 ) = (1, 0, 1, 0).
Тогда функция f( x2, x3, x4 ) = f1[ x2, f2(x3, x4) ] будет суперпозицией
функций f1 и f2.
Определение 3.5
Формулой алгебры логики называется выражение, описывающее
суперпозицию логических функций.
Пример 3.8
Дана формула F = f3{ f1( x3,x1 ), f2[ x1, f3( x1,x2 ) ] }, описывающая
суперпозицию функций f1, f2 и f3. Пусть f1 –дизъюнкция, f2 – конъюнкция, а f3
41
– сложение по mod 2. Тогда формула в инфиксной записи будет иметь вид: F
= ( x3  x1 )  ( x1 & ( x1  x2 ) ).
Определение 3.6
Эквивалентными
(равносильными)
называются
формулы,
представляющие одну и ту же функцию.
Пример 3.9 Функцию Шеффера, функцию стрелка Пирса и можно
представить следующими эквивалентными формулами:
x1 | x2 ~ x1  x2 ~ x1  x2
x1  x2 ~ x1  x2 ~ x1  x2
Булева алгебра
Определение 3.7
Алгеброй называется множество с определёнными на нем операциями.
Обозначается алгебра обычно парой: ( Μ, Ω ), где Μ – множество
элементов алгебры, а Ω – множество операций алгебры над её элементами
(называется сигнатурой). Результаты операций всегда принадлежат Μ.
Определение 3.8
Алгеброй логики называется алгебра у которой множество
М-
логические переменные и логические функции, а сигнатура – логические
операции, т.е.: Ω = { − ,  , & , → , ↓ , ~ , / ,  }.
Определение 3.9
Булева алгебра – алгебра с произвольным множеством элементов M,
сигнатура которой содержит две бинарные операции < & >, <

>, одну
унарную операцию < – > и две нульарных операции – константы 0 и 1 и
для любых x, y, z  M в ней справедливы следующие законы (аксиомы):
42
Законы булевой алгебры
Коммутативность
Ассоциативность
x1  x2  x2  x1
x1 & ( x2 & x3 )  ( x1 & x2 ) & x3
x1 & x2  x2 & x1
x1  ( x2  x3 )  ( x1  x2 )  x3
Дистрибутивность
Идемпотентность
x1 & ( x2  x3 )  x1 & x2  x1 & x3
x x  x
x1  ( x2 & x3 )  ( x1  x2 ) & ( x1  x3 )
x&x  x
Закон отрицания отрицания
Свойства констант
xx
x 11
x0x
x &1 x
x&00
Закон исключающего третьего
x  x 1
Закон противоречия
x&x0
Законы де Моргана
Законы поглощения
x1 & x2  x1  x2
x1  x1 x2  x1
x1  x2  x1 & x2
x1 ( x1  x2 )  x1
Обобщенное склеивание
Правила склеивания
x1 x3  x2 x3  x1 x2  x1 x3  x2 x3
x1 x2  x1 x2  x1
Правило вычеркивания
( x1  x2 ) & ( x1  x2 )  x1
x1  x1 x2  x1  x2
43
Свойства ,,
Свойства импликации
Сложения по модулю два
x  x 1
x1  x2  x2  x1
x1  x2  x2  x1
xxx
x 1 1
x1  x2  x1  x1
x1  ( x2  x3 )  ( x1  x2 )  x3
x1  x2  x1  x2
x 1  x
x1 & x2  x1  x2
x  x 1
x0 x
0  x 1
x1  x2  x1  x2  x1 x2
1 x  x
x1  x2  x2  x1
x1  ( x2  x3 )  ( x1  x2 )  x3
xx 0
xx 0
x0  x
x0  x
Свойства функций Шеффера и стрелки Пирса
x1 | x2  x2 | x1
x| x  x
xx x
x1  x2  x2  x1
x |1  x
x0 x
x | x 1
xx0
x | 0 1
x 1 0
( x1 | x2 ) | x3  x1 | ( x2 | x3 )
( x1  x2 )  x3  x1  ( x2  x3 )
Функции  и  связаны соотношениями аналогичными формулам де
Моргана
x1 | x2  x1  x2
x1  x2  x1 | x2
Выражение одних элементарных функций через другие
x1  x2  x1  x2
x1  x2  x1  x2  x1  x2  x1  x2  ( x1  x2 )  ( x1  x2 )
x1  x2  x1  x2  x1  x2  x1  x2  ( x1  x2 )  ( x1  x2 )
x1  x2  x1  x2
x1  x2  x1  x2

x1 | x2  x1  x2  x1  x2
x1  x2  x1  x2  x1  x2
44
С помощью данных формул можно упрощать выражения путем
эквивалентных преобразований.
Пример 3.10
(x

y) ( x
x z 
 y z.

z) = xx
yz = x(1


y)
yx


xz
xz


yz
 x y  x z  y z = x ·1  x y
= x  x z  y z = x ( 1  z ) y z = x
yz = x
Нормальные формы логических функций
Определение 3.10
Полной конъюнкцией
n
переменных называется конъюнкция
состоящая из n переменных или их отрицаний, в которой каждая переменная
встречается только один раз.
Пример 3.11 xyz и xyz - полные конъюнкции трех переменных.
Определение 3.11
Совершенной дизъюнктивной нормальной формой (СДНФ) логической
функции называется формула, представляющая данную функцию, и имеющая
вид дизъюнкции полных конъюнкций, которые формируются для наборов
переменных при которых функция равна 1:
f( x1,x2,…,xn ) =
 x1 x 2 … x n ,
f ( s1,..., sn ) 1
s1
s2
sn
s i – равно значению переменной x i в любом наборе значений
переменных, для которого значения функций равно 1, причем x i1  x i , x i 0  x i .
Алгоритм перехода от табличного задания функции к СДНФ
1. Выбрать в таблице все наборы аргументов, на которых функция
обращается в единицу.
2. Выписать конъюнкции, соответствующие этим наборам аргументов. При
этом, если аргумент xi входит в данный набор как 1, он вписывается без
45
изменения в конъюнкцию, соответствующую данному набору. Если xi входит
в данный набор как 0, то в конъюнкцию вписывается его отрицание.
Определение 3.12
Полной дизъюнкцией
n
переменных называется дизъюнкция
состоящая из n переменных или их отрицаний, в которой каждая переменная
встречается только один раз.
Пример 3.12
x y z
и x  y  z - полные дизъюнкции трех
переменных.
Определение 3.13
Совершенной конъюнктивной нормальной формой (СКНФ) логической
функции называется формула, представляющая данную функцию, и имеющая
вид конъюнкции полных дизъюнкций, которые формируются для наборов
переменных при которых функция равна нулю:
f( x1, x2, …, xn )
= & ( x1s1  x2 s2  ....  xn sn ),
где s i – равно противоположному значению переменной xi , в любом
наборе переменных, для которого значение функции равно нулю.
Алгоритм построения совершенной конъюнктивной нормальной
формы
1.
Выбрать в таблице все наборы аргументов, на которых функция
обращается в 0.
2.
Выписать дизъюнкции, соответствующие этим наборам аргументов. При
этом, если аргумент xi входит в данный набор как 0, он вписывается без
изменения в дизъюнкцию, соответствующую данному набору. Если xi
входит в данный набор как 1, то в дизъюнкцию вписывается его
отрицание.
46
Пример 3.13 Построить СДНФ и СКНФ для функции F(x,y,z).
F ( x, y , z )  x  y  z  y & ( z  x )
Решение Таблица истинности для данной функции построена выше.
Имеем:
x
y
z
F(x,y,z)
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
Для нахождения ДСНФ выбираем из таблицы только те строки, в
которых стоят наборы значений аргументов, обращающие функцию в
единицу. Это вторая, третья и пятая строки. Выпишем конъюнкции,
соответствующие выбранным строкам: x y z, x y z , x y z .
Соединяя
эти
конъюнкции
знаками
дизъюнкции,
получаем:
F ( x, y, z)  x y z  x y z  x y z .
Для нахождения СКНФ выбираем из таблицы только те строки, в
которых стоят наборы значений аргументов, обращающие функцию в ноль.
Выпишем соответствующие дизъюнкции и соединим их знаками конъюнкции.
Получим:
F ( x, y, z)  ( x  y  z)( x  y  z )( x  y  z )( x  y  z)( x  y  z ) .
47
Алгоритм перехода от СДНФ к СКНФ
1. Образовать логическую сумму дизъюнктивных членов, не
входящих в СДНФ функции
2. В полученном выражении заменить символы дизъюнкций на
символы конъюнкций и наоборот, аргументы xi на их отрицания
x i на
xi , а
xi .
Пример 3.14 Для данной функции f( x1,x2,x3 ) = x 1 x2 x 3

x1 x 2 x3

x1 x2 x 3, представленной в форме СДНФ, составить СКНФ.
Решение:
Обозначим через Кi полную конъюнкцию трех переменных для i-ой
строки таблицы задания функции. Так, для второй строки К2 = x1º x2º x3¹ =
x1 x 2 x 3 .
Запишем заданную функцию в следующем виде: f( x1, x2, x3 ) = x1º x2¹
x3º  x11 xº2 x13

x11 x12 xº3 = K3

K6

K7.
Образуем логическую сумму дизъюнктивных членов, не входящих в
СДНФ функции: K1  K2
 x11 xº2
 K4  K5  K8
xº3  x11 x12 x13 = x x x 
1
2
3
 xº1 xº2 x13  xº1 x12 x13
x3  x x2 x3  x1 x 2 x 3  x1
= x1º xº2 xº3
x1 x 2
1
x2 x3.
Меняя в данном выражении символы

на & и наоборот, а аргументы
на их отрицания и наоборот, получим искомую СКНФ для заданной функции:
f( x1,x2,x3 ) = ( x1  x2  x3 )
(x1  x2  x 3 )( x1  x 2  x 3 )( x1  x2  x3 )(
x1
x x
2
3
).
Алгоритм перехода от СКНФ к СДНФ
1. Образовать логическое произведение конъюнктивных членов, не
входящих в СКНФ функции.
48
2. В полученном выражении нужно заменить символы & на
, 
на
&, аргументы xi на x i , x i на xi.
Пример 3.15
Для функции предыдущего примера составить СДНФ по найденной
СКНФ.
Решение:
Обозначим через Di полную дизъюнкцию для i-ой строки таблицы
задания данной функции. Так, для третьей строки таблицы значения
переменных ( 0,1,0 ). Следовательно, s 1 = 1, s 2 = 0, s 3 = 1.Полная дизъюнкция
для третьей строки:
D3 =
s
1
0
s
s
1
x1 1  x 2 2  x 3 3 = x1  x 2  x 3 = x1

x2

x3.
Запишем найденную в предыдущем примере СКНФ в следующем виде:
f(x1,x2,x3) = (x1¹  x2¹  x3¹)( x1¹  x2¹  x3º )
( x1¹  x2º  x3º )( x1º  x2¹  x3¹ )( x1º  x2º  x3º) = D1∙D2 D4 D5 D8.
В СКНФ не входят полные дизъюнкции 3, 6 и 7 строк.
Образуем логическое произведение из этих дизъюнкций: D3∙D6 D7 =
= ( x1¹


x2º

x3¹ )( x1º
X 2  x 3 )( x1

x2¹

x3º )( x1º

x2º

x3¹ ) = ( x1 
x2

x3 )(
x1
 x 2  x3).
 ,  на & а аргументы на их отрицания
и наоборот, получим СДНФ для заданной функции: f( x1, x2,x3 ) = x x2 x 3 
x1 x 2 x3  x1 x2 x 3.
Меняя в этом выражении & на
1
Определение 3.14
Дизъюнктивной нормальной формой (ДНФ) логической функции
называется дизъюнкция разных конъюнкций, которые не все являются
полными.
49
Пример 3.16
Привести к СДНФ следующую ДНФ функции: x y

x y z.
Решение:
В данной ДНФ конъюнкция xy не является полной, т.к. не содержит
переменной z . Учитывая, что z
образом: xy(z

z)

xyz
=

z =1
xyz

преобразуем ДНФ следующим
xy z
 x y z. Полученная форма и
есть искомая СДНФ.
Алгоритм приведения логической формулы к ДНФ
1. С помощью равенства
x=
x и законов де Морга на все отрицания
“спускаются” до переменных.
2. Раскрываются скобки в полученном выражении.
x
3. С помощью выражений:x ·x = x ,x
= x, x· x = 0, x
 x
= 1.
Пример 3.16
Привести к ДНФ следующую формулу: xy  x (y

x z ) ( x(y z) yz) .
Решение:
Преобразуем по закону де Моргана выражение во вторых скобках:
( x(y z) yz) = x
  y  z &
yz =
x

yz &  y  z  .
Раскрывая скобки в этом выражении получим:
x  yz y  yz z = x  0  yz = x  yz.
Подставляя это выражение в исходную формулу и раскрывая скобки
получим: x y
 x
(y

x z )( x

yz) = y
 xyz.
Полученное выражение и есть ДНФ данной формулы.
Определение 3.15
Конъюнктивной нормальной формой (КНФ) логической функции
называется конъюнкция разных дизъюнкций, которые не все являются
полными.
50
Алгоритм приведения ДНФ функции к КНФ
Пусть ДНФ функции имеет следующий вид:
K1

K2

…

Kn,
где Ki – некоторые конъюнкции, не обязательно полные. Обозначим через Di
– дизъюнкции, не обязательно полные. Тогда, используя закон де Моргана
получим:
K1  K 2  … K n = D1  D 2  … D n .
Раскрывая скобки в выражении
D1∙ D2 … ·Dn
и удаляя лишние
конъюнкции и повторения переменных в полученных конъюнкциях,
получим:
D1  D 2  … D n = K1  K2  …  Km .
Полученное выражение с помощью закона де Моргана преобразуем к виду:
D*1  D*2  … ·D*m .
Это и будет КНФ функции для исходной ДНФ.
Пример 3.17
Привести к КНФ функцию, заданную в ДНФ:
f( x,y,z) = x y

xy

xz.
Решение:
Используя закон де Моргана, раскрывая затем скобки и удаляя лишние
конъюнкции, получим:
f(x, y, z) = xy  xy  xz =  x  y  x  y  x  z    xx  x y  yx  yy  x  z  
 x y  yx  x  z   x y x  x y z  yxx  yxz  x y  x y z  yxz.
Применяя к этому выражению закон де Моргана получим:
x y  x y z  yxz   x  y  x  y  z  x  y  z  .
51
Это и есть искомая КНФ для заданной функции.
Приведение КНФ функции к ДНФ
Приведение КНФ к ДНФ осуществляется путем раскрытия скобок и удаления
полученных лишних конъюнкций и повторных переменных.
Пример 3.18 Привести к ДНФ следующую функцию, заданную в КНФ
Решение: f( x, y, z ) = ( x

y
x

1) =

 z  y )= x x  x z  x y 
x  yz  y= xz  y(x  x)  y(z
y )(
x
 yy = xz  xy  y
x z  y∙1  y ·1 = x z  y.
yz
Методы минимизации булевых функций
Определение 3.16
ДНФ булевой функции называется минимальной, если она реализует
эту функцию и имеет наименьшее суммарное число сомножителей в своих
слагаемых по сравнению с другими эквивалентными ей ДНФ.
Определение 3.17
Нахождение минимальной ДНФ функции называется минимизацией.
Методы минимизации
1. Метод неопределенных коэффициентов
Пусть дана функция трех переменных. Составим
для нее
дизъюнктивную форму, включающую всевозможные конъюнкции, первого,
второго и третьего рангов:
 a3z  a4 x  a5 y  a6 z  b1xy  b2xz  b3yz
 b4 x y  b5 x z  b6 y x  b7 y z  b8 z x  b9 z y  b10 x y  b11 z x 
f(x,y,z) = a1x
b12 y

z

a2 y
 c1xyz  c2 x yz  c3 y xz  c4 z xy  c5 x y z  c6 x z y  c7 x y z
c8 x y z .
52
Найдем значения правых частей данной дизъюнктивной формы при
разных наборах переменных. Например, при x = y = z = 0 получим систему
уравнений:
a4
a4


a5

a5

a6

a6

b10
 b12 
c8 = f( 0,0,0 )
b10  b11  b12  c8 = f( 1,1,0 ),
a3

a4

a5

b5  b7 + b12  c5 = f( 0,0,1 ),
a2

a4

a6

b4  b9  b11  c6 = f( 0,1,0 ),
a2

a3

a4

b3  b4  b5  c2 = f( 0,1,1 ),
a1

a5

a6

b3  b6  b8  c7 = f( 1,1,0 ),
a1

a3

a5

b2  b6  b7  c3 = f( 1,0,1 ),
a1

a2

a6

b1  b8  b9  c4 = f( 1,1,0 ),
a1

a2

a3

b1  b2  b3  c1 = f( 1,1,1 ).
Подставляя в правые части уравнений системы значения f(x,y,z ),
взятые из таблицы задания функции, получим более простую систему
уравнений. Решая эту систему, найдем значения коэффициентов ai, bi, и ci.
Пример 3.18
Найти минимальную форму для функции, заданной следующей
таблицей:
x
y
z
f
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
53
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
Подставляя значение f( 0, 0, 0 ) = 0
в первое уравнение исходной
системы, получим: a4 = a5 = a6 = b10 = b11 = b12 = c8 = 0.
Аналогично получим, что все коэффициенты в третьем, четвертом,
пятом и шестом уравнениях также равны нулю. В системе уравнений
останутся только второе, седьмое и восьмое уравнения, которые будут иметь
вид: c5 = 1; b1

c4 = 1; b1

c1 = 1
Так как мы ищем минимальную формулу, то во втором уравнении надо
положить, что c4 = 0. Тогда получим, что b1 = 1. Аналогично в третьем
уравнении. Полагаем, что c1 =0. Окончательно имеем: b1 = 1, c5 = 1, а остальные
коэффициенты равны нулю. Подставляя найденные коэффициенты в исходное
уравнение получим минимальную дизъюнктивную форму данной функции в
виде: f ( x,y,z ) = x y
 x
y z.
Если найти СДНФ этой функции и попытаться ее упростить, то
результат упрощения может быть не однозначным, т.к. одна и та же функция
может иметь несколько минимальных форм.
Пример 3.19
Для функции f( x,y,z ) = x y z
 x
yz
 xyz 
xyz

xy z
xyz существуют две эквивалентные минимальные дизъюнктивные формы:
x
y

xz
 yz
и
54
x z

xy

y z.

Данный метод минимизации удобен для функции с числом
переменных ≤ 5.
2. Графический метод минимизации с помощью карты Карно
Карты Карно – графический метод отображения булевых функций.
Это специальные таблицы, задающие булеву функцию. Они формируются
так, чтобы облегчить процесс склеивания. Карты Карно используются при
n=2,3,4,5,6, при n>6 они практически непригодны.
Принципы построения карт Карно:
- склеивающиеся между собой конституанты единицы или нуля
расположены в соседних клетках: по горизонтали и по вертикали клетки
таблицы отличаются лишь значением одной переменной;
- клетки, расположенные по краям таблицы считаем соседними и
обладают этим же свойством.
Ниже представлены способы задания данных таблиц (n – число
переменных).
n=2
n=3
n=4
При n≥5 используют две карты Карно.
55
Пример 3.20
Минимизировать на картах Карно функцию f(x1,x2,x3,x4), которая равна
единице на наборах с номерами – 0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 15 .
Решение:
Построим двоичные наборы, на которых задана функция.
№
Наборы f (x 1, x 2, x 3, x4)
набора
0
0000
1
1
0001
1
2
0010
1
3
0011
1
4
0100
1
6
0110
1
7
0111
1
8
1000
1
9
1001
1
11
1011
1
15
1111
1
Построим Карты Карно для заданной функции.
56
x1 x 4
00
01
11
10
00
1
1
1
1
01
1
1
1
11
10
1
1
1
1
x3 x 4
x2 x3
Таким образом,
f min  x 2 x 3  x1 x 4  x3 x4 .
Алгебра Жегалкина
Определение 3.18
Алгеброй Жегалкина называется алгебра над множеством логических
функций и переменных, сигнатура которой содержит две бинарные операции
& и  , и две нульарные операции – константы 0 и 1.
Справедливы соотношения:
1. x ⊕ y = y ⊕ x;
2. x ( y ⊕ z ) = x y ⊕ x z;
3. x ⊕ x = 0;
4. x ⊕ x = 1;
57
5. x ⊕ 0 = x.
Выражения для основных элементарных функций алгебры логики в
алгебре Жегалкина
1.
x = x⊕1
Доказательство: Это соотношение проверяется непосредственной
подстановкой 0 и 1 в обе части равенства.
2.
x

y = x y ⊕ x ⊕ y.
Доказательство:
x

y = xy = x
y
⊕ 1 = ( x ⊕ 1 )( y ⊕ 1 ) ⊕1 =
= x y ⊕ x ⊕ y ⊕1 ⊕ 1 = x y⊕ x ⊕ y.
3.
x → y = x y ⊕ x ⊕ 1.
Доказательство:
x→y = x

y = x y⊕ x ⊕y =
( x ⊕1 ) y ⊕ ( x ⊕ 1 ) ⊕y = x y⊕ y ⊕ x ⊕ 1 ⊕ y=
x y ⊕ x ⊕ 1.
4.
x / y = xy⊕1
Доказательство:
x / y = x y = xy ⊕ 1.
5.
x↓y = xy⊕x⊕y⊕1
Доказательство:
x↓y = x
y
= ( x⊕1 )( y ⊕ 1) =
x y ⊕x ⊕ y ⊕ 1.
6.
x ~ y = 1⊕x⊕y
Доказательство:
x ~ y = x y
x ~ y = xy
xy


x y;
( x ⊕ 1 )( y ⊕ 1 ) =
x y ⊕ x ⊕ y ⊕ 1 = 1 ⊕ x ⊕ y.
58
Определение 3.19
Полиномом Жегалкина для n логических переменных называется
полином, являющийся суммой константы и различных одночленов, в
которые все переменные входят не выше, чем в первой степени:
a ⊕ ∑ x i1 x i 2 … x ik , ( 1 ≤ k ≤ n )
причем в каждом наборе ( i 1 , , i k ) все i j различны, а
суммирование по mod 2 ведется по некоторому множеству таких не
совпадающих наборов.
Пример 3.21
1 ⊕ x1 ⊕ x1 x2 , x 2 ⊕ x1 x 3 ⊕ x1 x 2 x3 .
При нахождении полинома Жегалкина для некоторой формулы
алгебры логики можно использовать следующее соотношение, вытекающее из
представления дизъюнкции в алгебре Жегалкина:
f1  f2 = f1 ⊕f2,
справедливое при f1f2 = 0.
Пример 3.22 Найти полином Жегалкина для функции:
f( x, y ) = x y
xy
Решение:
f( x,y ) = x y

x y = xy⊕x y =
x y ⊕( x ⊕ 1 )( y ⊕ 1 ) = x y ⊕ x y ⊕ x ⊕ y ⊕ 1 =
1 ⊕ x ⊕ y - полиномом Жегалкина.
Пример 3.23 Найти полином Жегалкина для функции:
f( x, y ) = x y

x z.
Решение:
f( x,y ) = x y

x z = xy⊕ x z =
59
x( y ⊕ 1 )⊕ ( x ⊕ 1 ) z = x y ⊕ x ⊕ x z ⊕ z =
x ⊕ z ⊕ x y ⊕ x z - полиномом Жегалкина.
Теорема 3.1
Для любой логической функции существует полином Жегалкина и
притом единственный.
Доказательство: Существование полинома доказано
вышеприведенным алгоритмом получения полинома из логической
формулы. Для доказательства единственности надо показать, что между
множеством всех логических функций от n переменных и множеством всех
полиномов Жегалкина от n переменных существует взаимно однозначное
соответствие.
Полином Жегалкина можно найти методом неопределенных
коэффициентов.
Пример 3.24 Найти полином Жегалкина для функции заданной
векторно: f( x,y ) = ( 0, 1, 1, 0 ).
Решение:
x
y
f
0
0
0
0
1
1
1
0
1
1
1
0
Полином Жегалкина для функции двух переменных ищем в
следующем виде: f( x, y ) = a0 ⊕ a1·x ⊕ a2·y ⊕a3·xy
Для определения коэффициентов полинома нужно подставить
значения неизвестных и соответствующее значение функции.
Подставляя набор переменных(0,0) получим:
60
0 = a 0  a1  0  a 2  0  a 3  0  0 . 
a 0 = 0.
Аналогично для набора (0,1) получим:
1 =0  a1  0  a 2 1  a 3  0  0 .  a 2 = 1.
Для набора (1,0) получим:
1 =0  a1 1 1 0  a 3 1 0  a 1 = 1.
Для набора (1,1) получим:
0 =0 11 11  a 3 11 или 1  1  a 3  0  a 3 = 0.
Итак, искомый полином для данной функции:
f( x, y ) = x ⊕ y.
Алгоритм построения полинома Жегалкина методом
неопределенных коэффициентов:
1. Привести в таблицу истинности булеву функцию.
2. Записать ⊕ элементарных конъюнкций, соответствующих
наборам, где функция равна 1 в таблице истинности.
3. Под каждой булевой функцией написать соответствующий булев
набор, проставить инверсии в соответствии с 0.
4. Сделать замену по формуле: x  x  1 .
5. Привести подобные слагаемые, используя формулу:
 0, n  2k
x  x  x  
 x, n  2 k  1
Пример 3.25
Построить полином Жегалкина для функции f(x,y,z)=01000011.
61
Решение:
x
y
z
f(x,y,z)
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
f ( x, y, z )  x yz  xyz  xyz  ( x  1)( y  1) z  xy( z  1) 
( 0 , 0 ,1)
(1,1, 0 )
(1,1,1)
xyz  xyz  xz  yz  z  xyz  xy  xyz  xyz  xz 
yz  z  xy
Полнота и замкнутость
Определение 3.20
Система функций F = {f1, … , fn} называется функционально полной,
если любая логическая функция может быть представлена суперпозицией
функций этой системы.
Пример 3.26
Система функций { x , x1 & x2, x1  x2} является полной, т.к. любая
логическая функция может быть представлена в СДНФ, т.е. формулой в
62
которую входят только функции данной системы. Это и означает, что данная
система будет полной.
Пример 3.27
Система функций {1,0,⊕,∧} является полной, т.к. из данных
операторов состоит полином Жегалкина.
Теорема 3.2
Пусть система функций F1 = {f1, … ,fn} полная, а каждая ее функция
выражается в виде формулы через функции системы F2 = { h1, … , hm }. Тогда
система F2 так же полная.
Пример 3.28
Доказать, что система функций { x , x1 & x2} будет полной.
Решение:
Согласно закону де Моргана имеем: x1

 x2 = x
1
 x2 , т.е. функция x1
x2 выражается через функции данной системы. Следовательно, каждая
функция системы предыдущего примера выражается через функции данной
системы. Поэтому по представленной теореме эта система тоже будет полной.
Определение 3.21
Минимальная полная система функций (т.е. такая полная система
функций, удаление из которой любой функции делает систему не полной)
называется базисом.
Базисами будут следующие полные системы функций:
{ xy, x  y, 1 }, { x ↓ y }, { x ∕ y }, { x
{ x  y  z , xy, 0, 1 },

y , x  y , 1 },
{ x → y, x }, { x → y, 0 }.
Определение 3.22
Множество логических функций называется замкнутым классом, если
любая суперпозиция функций из этого множества снова принадлежит ему.
63
Основные замкнутые классы логических функций
Определение 3.23
Тo – класс всех логических функций f( x1,…, xn ), сохраняющих ноль, для
которых выполняется равенство:
f( 0, …, 0 ) = 0.
Функции 0, x, x & y, x
y, x ⊕ y принадлежат классу To, а функции

1, x не принадлежат ему.
Определение 3.24
T1 – класс всех логических функций f ( x1, …, xn ), сохраняющих единицу,
т.е.для которых выполняется равенство:
f( 1, …, 1 ) = 1.
Функции 1, x, x & y, x

y принадлежат данному классу, а функции 0,
x не принадлежат ему.
Определение 3.25
Функция f*( x1, … , xn ) называется двойственной функцией к функции
f( x1, … , xn ), если она определяется равенством: f*( x1, … , xn ) = f
 x ,..., x
1
n
.
Определение 3.26
Функция f(x1, …, xn ) называется самодвойственной, если она
равносильна своей двойственной, т.е. выполняется следующее условие: f( x1,
… , xn ) = f*( x1, … , xn ) или f( x1, … , xn ) = f ( x1 , …, x n ).
Пример 3.29
f = (0, 1, 1, 0, 1, 0, 0, 1)
заданную функцию получим
будет самодвойственной, т.к. инвертируя
f 1 = (1, 0, 0, 1, 0, 1, 1, 0 ). Переворачивая
значения функции f1, получим двойственную функцию к f , f* = (0, 1, 1, 0,
1, 0, 0, 1). Сравнивая значения функций
64
f и f* видим, что
f = f*.
Определение 3.27
S – класс всех самодвойственных функций. Для данного класса
функции справедливо: на наборах значений переменных (a1, … , an) и ( a 1, …
, a n), которые мы будем называть противоположными, самодвойственная
функция принимает противоположные значения.
Определение 3.28
Для двух наборов значений переменных a = (a1, … , an) и b = (b1, … ,
bn) выполнено отношение предшествования
a ≤ b, если a1 ≤ b1, … , an ≤ bn,
где ai, bi {0,1}.
Пример 3.30
Для a = ( 0,1,0,1 ) и b = ( 1,1,0,1 ) выполнено отношение a ≤ b.
Определение 3.29
Функция
f( x1, …, xn ) называется монотонной, если для любых двух
наборов значений переменных a и b таких, что a ≤ b, имеет место неравенство:
f( a ) ≤ f( b ).
Монотонными функциями будут следующие функции: 0, 1, x, x & y, x

y. Функция x не является монотонной.
Пример 3.31
Проверить на монотонность функции f1 и f2, заданные следующей
таблицей:
x
y
z
f1
f2
0
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
1
1
1
1
65
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
Для проверки монотонности нужно сравнивать наборы значений
переменных двух строк, причем в верхней строке значение функции должно
быть равно 1, а в нижней 0.
Для функции f1 вторую строку ( f1 = 1 ) можно сравнивать с третьей,
шестой и седьмой строками, где f1 = 0. Набор значений переменных второй
строки не находится в отношении предшествования с набором третьей строки,
а с набором шестой строки находится в отношении предшествования, т.е. ( 0,
0, 1 ) ≤ ( 1, 0, 1 ). Сравнивая значения функции f1 для этих строк, получим: f1(
0, 0, 1 ) > f1( 1, 0, 1 ). Следовательно, функция
f1 не является монотонной.
Для функции f2 наборы значений переменных третьей и четвертой
строк, где f2 = 1, можно сравнивать с наборами пятой строки, для которой f2 =
0. Наборы значений переменных этих строк не находятся в отношении
предшествования с набором пятой строки, поэтому эти строки не следует
сравнивать. Другие строки так же не следует сравнивать, т.к. значение
функции в предшествующей строке не больше значения функции в
последующей строке. Следовательно функция монотонная.
M - класс всех монотонных логических функций
Определение 3.30
Логическая функция
n
переменных называется линейной, если
полином Жегалкина, представляющий данную функцию, содержит только
линейные слагаемые, т.е.
f( x1, …, xn ) = a0  a1 x1  a2 x  …  an xn , где ai  {0,1}.
66
x, x , x  y
Константы 0, 1 и функции
функциями. Функция
x

являются линейными
y не является линейной, т.к. она представляется
следующим полиномом Жегалкина:
x

y = 1⊕x⊕xy.
L – класс всех линейных логических функций.
Определение 3.31
Функционально замкнутый класс называется предполным, если он не
содержится ни в каком функционально замкнутом классе, отличном от самого
себя и от класса всех функций алгебры логики.
Предполными классами будут классы Т 0 , T 1 , S, M и L. Других
предполных классов нет.
Теорема 3.3 Теорема Поста
Для того чтобы система функций была полной, необходимо и
достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых
классов
To, T1, S, M и L.
Следующие системы не являются полными:
{ x ,1 }, { xy, x

y }, { x  y, x }, { xy

yz

xz, x }, { xy

yz

xz, 0, 1
}, { 0, xy, x  y  z },{ 1, xy, x  y  z }, { 0, 1, x  y }, { 0, 1, xy }.
Для проверки систем на полноту удобно пользоваться следующей
таблицей Поста
T0
T1
S
L
M
x
-
-
+
+
-
xy
+
+
-
-
+
x y
+
+
-
-
+
f
67
1
-
+
-
+
+
0
+
-
-
+
+
x y
+
-
-
+
-
x↓y
-
-
-
-
-
x ∕y
-
-
-
-
-
x y z
+
+
+
+
-
x→y
-
+
-
-
-
Определение 3.32
Замыканием множества К называется множество всех логических
функций, представимых в виде формул через функции множества К.
Замыкание множества К обозначается [K].
Примеры 3.32
1) Пусть К = Р2. Тогда очевидно, что
2) Пусть K = { x , x

[K] = P2.
y, x & y }. Тогда [K] = P2.
3) Пусть K = { 1, x  y }. Замыканием этого множества будет класс L.
4) Пусть K = { 0, 1, x
 y, x & y }. Замыканием данного множества будет
класс М, т.к. любая монотонная функция может быть представлена в виде
формул через функции множества К.
Пример 3.33
Множество
K = { 1, x  y } не является замкнутым классом, т.к. [K]
= L, а константа 1 не является линейной функцией.
68
Примеры решения задач
Задача 3.1
Доказать полноту систем F1 = {x1 / x2} и F2 = {x1↓ x2}.
Решение:
Данные системы будут полные, т.к. отрицание, дизъюнкция и
конъюнкция выражаются через функции этих систем следующим образом:
x = x / x = x ↓ x,
x1

x2 = x1  x2 = ( x1 ↓ x2 ) ↓ ( x1 ↓ x2 ),
x1 & x2 = x1 / x2 = ( x1 / x2 ) / ( x1 / x2 ).
Задача 3.2
Доказать полноту системы{ x & y, x⊕y, 1 }.
Решение: Так как x = x⊕1 получим, что функции полной системы { x ,
x & y } выражаются через функции данной системы. Следовательно, эта
система так же полная.
Задача 3.3 Проверить на полноту следующую систему функций: {x →
y, x & y).
Решение:
f
To
→
–
&
+
S
M
L
+
–
–
–
+
–
+
–
T1
Из таблицы видно, что все функции данной системы принадлежат
классу Т1. Следовательно, по теореме о полноте данная система функций не
является полной.
69
Задачи для самостоятельного решения
№ 1 Доказать полноту системы { x , x1

x2 }.
Примечание: учесть x1 & x2 = x1  x2 .
№ 2 Проверить на монотонность следующие функции:
x

y, x & y, x & ( y

z ).
Ответ: монотонные.
№ 3 Проверить на полноту следующую систему функций: { x , x
Ответ: не является полной.
№ 4 Проверить на полноту следующую систему функций:
{xy, x

y, x⊕y⊕z}.
Ответ: не является полной.
№ 5 Проверить на монотонность функции:
а) 00010011
б) 01010011
в) 01110011
Ответ: а),б) – монотонная ,в) - не монотонная.
№ 6 Проверить на самодвойственность
f(x,y,z)=00111000.
Ответ: не является самодвойственной.
№ 7 Доопределить функции, являющиеся самодвойственными:
1) (11-0--1-)
2) (----1010)
70

y }.
№ 8 Доопределить функции, являющиеся монотонными:
1) (1-0-11-1)
2) (--1100--)
№ 9 Построить полином Жегалкина для x1  x2
Ответ: 1  x1  x2
№10 Построить полином Жегалкина для функции f(x,y,z)=00010101.
Ответ: xyz  xz  yz
№11 Составить таблицу истинности функции 3-х переменных: F (x, y,
z).
Изобразить функцию графически.
1.
F ( x, y , z )  z x  y z  y | z  x z .
Ответ: 01110010
2.




F ( x, y , z )   x  y   y  z | x | y  z  y .
Ответ: 01110110
3.
F ( x, y , z )  x z  z  y  z  x .
Ответ: 11111111
4.
F ( x, y, z )  x y  z | x  x  zx  z .
Ответ: 01011111
№ 12 Записать СДНФ и СКНФ булевой функции f(x1, x2, x3),
принимающую значения 1 на наборах с номерами 3, 4, 7.
№ 13 Записать СДНФ и СКНФ булевой функции f(x1, x2, x3, x3 x4),
принимающую значения 0 на наборах с номерами 2, 6, 7, 8, 11, 12.
№ 14 Привести к СКНФ, а потом к КНФ:
1. (00100000)
2.(00110101)
3.(10100000)
71
4.(11100011)
№ 15 Минимизировать функции, заданные наборами логических
переменных двумя способами:
1) (0000111101010000)
2) (11001010)
3) (010101111110011)
№ 16 Построить минимальные КНФ функций с помощью карт Карно
1) (00001111)
2) (0101)
№ 17 Построить минимальные ДНФ функций с помощью карт Карно
1)(00101010)
2)(1110)
Контрольные вопросы
1.
Дать определение двоичного набора.
2.
Дать определение булевой функции или функции алгебры логики.
3.
Дать определения области определения и области значений функции
алгебры логики.
4.
Дать определение алгебры.
5.
Перечислите функции алгебры логики от одной переменной.
6.
Перечислите элементарные функции алгебры логики от двух
переменных.
7.
Перечислите элементарные функции алгебры логики от одной
переменных.
8.
Дать определение алгебры Жегалкина.
9.
Привести основные соотношения алгебры Жегалкина.
10.
Что такое полином Жегалкина?
72
11.
В чем состоит метод неопределенных коэффициентов для построения
полинома Жегалкина?
12.
Привести алгоритм построения полинома Жегалкина.
13.
Дайте определение полной конъюнкции.
14.
Дайте определение полной дизъюнкции.
15.
Дайте определение СКНФ.
16.
Дайте определение СДНФ.
17.
Приведите алгоритм нахождения СКНФ.
18.
Приведите алгоритм нахождения СДНФ.
19.
Приведите алгоритм перехода функции к ДНФ.
20.
Приведите алгоритм перехода от ДНФ к КНФ.
21.
В чем заключается процесс минимизации?
22.
В чем состоит метод неопределенных коэффициентов?
23.
В чем состоит метод карт Карно?
24.
Как выглядит карта Карно для функции двух переменных?
25.
Как выглядит карта Карно для функции трех переменных?
26.
Как выглядит карта Карно для функции четырех переменных?
27.
Какая система называется функционально полной?
28.
Что такое класс замкнутых функций?
29.
Перечислить основные классы замкнутых функций.
30.
Дать определение двойственности.
31.
Что такое самодвойственная функция?
32.
Что такое монотонная функция?
33.
Что такое линейная функция?
34.
Сформулировать теорему Поста.
35.
Что такое замыкание?
73
Комбинаторика
Основные элементы комбинаторики
При решении многих экономических, физических
и других задач
возникает необходимость знать количество возможных наборов объектов из
заданного множества, удовлетворяющих определенным условиям. Такие
задачи называют комбинаторными, а раздел математики, изучающий методы
решения данных проблем – комбинаторикой.
Комбинаторные задачи обычно оцениваются с точки зрения общего
количества вариантов, среди которых нужно найти решение, а алгоритмы - с
точки зрения сложности. При этом различают сложность по времени, т. е.
количества необходимых шагов алгоритма, и по памяти, т. е. по
необходимому объему памяти для работы алгоритма.
Определение 4.1
В
комбинаторике
возможные
комбинации
объектов называют
выборками.
Каждую выборку называют комбинаторным объектом, а их
количество - комбинаторным числом.
Пример 4.1 Дано множество Х={a, b, c, d}. Сформируем для него
следующие множества трехэлементных комбинаторных объектов:
1){(a, b, c); (b, a, c); (b, c, a); (c, b, a);...(d, c, b)};
2){{a, b, c}; {a, c, d}; {b, c, d}};
3){(a, a, a); (a, a, b); (a, b, a); (b, a, a);...; (d, d, d)};
В первом случае важным является порядок следования элементов
внутри выборки, во втором случае - не порядок элементов внутри выборки, а
только их, в третьем случае главным является повторяемость использования
одного элемента.
74
Правила суммы и произведения
При решении многих комбинаторных задач, в основном, кроме
комбинаторных формул, с которыми познакомимся ниже, используют
правило суммы и произведения.
Правило суммы
- Теоретико – множественная формулировка
Пусть A – множество из m элементов; B – множество из n элементов.
AB=. Тогда, объединение множеств: AB содержит m+n элементов.
В общем случае: пусть |M1|=m1, |M2|=m2, …, |Mk| = mk и Mi  Mj=
i,j=1.. k, ij. Тогда, |M| = |M1 M2…Mk| = m1+ m2+…+ mk.
- Комбинаторная формулировка
Если объект a может быть выбран m способами, а объект b – n другими
способами, то выбор "a или b" может быть осуществлен m+n способами.
В общем случае: если объект a1 может быть выбран m1 способами; … ak
– mk способами. Выбор "a1 или a2…или ak " может быть осуществлен m1 +m2
+…+mk способами.
Пример 4.2 Из Самары в Волгоград в течении суток отправляется 3
поезда, 1 самолет и 2 автобуса. Сколько существует способов выехать из
Самары в Волгоград?
Решение: По правилу суммы имеем N= 3+1+2 = 6 способов.
Правило произведения
- Теоретико – множественная формулировка.
Если A и B – конечные множества и |A|=m, |B|=n, то мощность
множества AB равна mn.
В общем случае: если |M1|=m1, |M2|=m2, …, |Mk|=mk, то |M1M2…Mk|=
=m1m2…mk.
75
- Комбинаторная формулировка
Если объект a может быть выбран m способами, и после этого объект b
может быть выбран n способами, то выбор пары (a,b) может осуществляться
mn способами (выбор a и b независимы).
В общем случае: пусть объект a1 может быть выбран m1 способом;
объект a2 – m2 способами; … ak – mk способами, причем выбор a1 не влияет на
число способов выбора a2 …ak, выбор a2 на число способов выбора a3 …ak, …
Тогда, выбор упорядоченного множества объектов (a1, a2 …ak) – в указанном
порядке можно осуществить m1 m2… mk способами.
Пример 4.4 Сколько различных танцующих пар можно составить из 3х девушек и 2-х юношей?
Решение: По правилу произведения имеем N= 32=6 пар.
Сложный выбор объектов
Часто в комбинаторных задачах выбор объектов происходит в
несколько ступеней, на некоторых работает правило суммы, на других –
правило произведения. При сложном выборе объектов важно обеспечить
полный перебор всех возможных случаев.
Пример 4.5 Имеется три различных флага. На флагштоке поднимается
сигнал, состоящий не менее, чем из 2-х флагов. Сколько различных сигналов
можно поднять на флагштоке, если порядок сигналов учитывается?
Решение: Сигнал может состоять либо из 2-х сигналов, либо из 3-х.
Одновременное выполнение 2-х действий невозможно.
N=N2+N3 (правило суммы)
N2=32=6 (правило произведения)
N3=321=6 (правило произведения)
N=12
76
Формула включения и исключения
Пусть N – число предметов, которые обладают или не обладают
некоторыми свойствами 1 , 2 ,..., n .
N ( i ) - число предметов, которые обладают свойством  i .
N ( i) - число предметов, которые не обладают свойством  i .
Запишем формулу, по которой можно вычислить число предметов, не
обладающих ни одним из свойств 1 , 2 ,..., n . Это формула включения и
исключения:
N 1,  2 ,..., 3   N  N 1   N  2   ...  N  n  
 N 1 ,  2   N  2 ,  3   ...  N  n1 ,  n  
 N 1 ,  2 ,  3   ...  N  n2 ,  n1 ,  n   ...
  1n N 1 ,  2 ,..., n 
Пример 4.6 При
обследовании читательских вкусов студентов
выяснилось , что 60% - читают журнал А, 50% - читают журнал В, 50% читают журнал С, 30% - читают журналы А и В, 20% - читают журналы В и С,
40% - читают журналы А и С, 10% - А,В и С. Сколько студентов не читают ни
одного журнала
Решение:
N(A',B',C')=N-N(A)-N(B)-N(C)+N(AB)+N(AC)+N(BC)-N(ABC)=100-6050-50+30+20+40-10=20%
Пример 4.7
Даны множества A, B и C, элементы которых могут принадлежать
одному, двум или трем множествам, т. е. xA, xB, xC, x(AB), x(AC),
x(BC), x(ABC). Определить общее число элементов множеств A, B и
C.
77
Решение:
Поиск объединения множеств A, B, C
Согласно правилу включения-исключения имеем:
=|ABC|-|A|-|B|-C|+|(AB)|+|(AC)|+|(BC)|-|(ABC)|.
Откуда:
ABC|=|A|+|B|+|C|-|(AB)|-|(AC)|-|(BC)|+|(ABC)|.
Пусть даны 4 буквы латиницы:
A={A, B, C, D}, 4 буквы
кириллицы: B={А, Б, В, Г} и 4
буквы греческого алфавита:
C={Α, Β, Γ, Δ}.
Тогда:
(AB)={A, B}, (AC)={A, B}, (BC)={A, В, Г}, (ABC)={A, B}.
|ABC|=|A|+|B|+|C|-|(AB)|-|(AC)|-|(BC)|+|(ABC)|=4+4+4-2-2-3+2=7,
т. е.
(ABC)={A, B, C, D, Б, Г, Δ}.
Соединения без повторений
Соединения – простые комбинаторные объекты, к которым относятся
перестановки, сочетания и размещения.
Перестановки
Определение 4.2
Перестановка из n элементов – упорядоченная последовательность
элементов n- элементного множества (кортеж). Различные перестановки –
отличаются порядком элементов в них.
Пример 4.8 Пусть A={1,2,3}
Перестановки: 123, 132, 213, 231, 312, 321.
Число перестановок из n различных объектов равно:
78
Pn=n!
Определим n!=1*2*3*…*n, 0!=1, n!=(n-1)!*n
Пример 4.9 Число способов стать в очередь за стипендией из 17
человек?
P17=17!
Размещения
Определение 4.3
Размещения – упорядоченная последовательность из m элементов
множества, содержащего всего n элементов. Различные размещения –
отличаются совокупностью элементов и (или) порядком их следования.
Пример 4.9 Пусть A={1,2,3}
Размещения из 3 по 2: 12, 21, 13, 31, 23, 32.
Число размещений из n по m равно: Amn 
n!
( n  m )!
Пример 4.10 Сколькими способами можно расставить на полке 5 книг
из 7?
A 57 
7!
( 7  5)!
m
Замечание: Формула An верна для всех mn.
n
n!
При m=n An = =Pn.
0!
Сочетания
Определение 4.4
Сочетания из k по m – набор из m элементов, без учета порядка
элементов в наборе. Сочетание – произвольное неупорядоченное mподмножество из n элементов. Различные сочетания – отличаются набором
элементов, но не их порядком.
79
Пример 4.11 A={1,2,3}
Сочетания из 3 по 2: 12, 31, 32.
Число сочетаний из n различных объектов по m равно:
Сm 
n
n !
, m<n.
m !  (n  m)!
m
n!
Anm=Cnmm!  Cnm= An =
m! m !  (n  m)!
Свойства сочетаний
n
1
0
k
1. C n  1; C n  n; C n  1; C n  0 , при k0 и k n
m
nm
2. Симметричность числа сочетаний: C n  Cn
3. Правило Паскаля: для числа сочетаний из n по m справедливо
k
k 1
k
следующее рекуррентное соотношение: C n  Cn1  Cn1
4. Треугольник Паскаля
Числа Cnk , 0  k  n выпишем в виде треугольника:
C00
n=0
1
C10 1
2
1
3
1
5
1
Cn0
5
C21
1
3
4
C11
1
2
1
4
1
3
6
10 10
C31  C32
1
4
1
5
1
n
Cn
0
1
n
n
5. Cn  Cn  ...  Cn  2 - из бинома Ньютона
80
Cnk , k  0,1,...n - биноминальные коэффициенты в выражении, которое
известно, как бином Ньютона.
( a  x )  a  Cn  a
n
n
1
n 1
 x  Cn  a
1
2
n2
 x  ...  Cn  x 
2
n
n
n
  Cnk  a nk  x k .
k 0
Пример 4.12
Сколько способов существует выбрать два предмета из четырёх?
Решение: С 4 2 
4!
6
2!( 4  2)!
Производящие функции
Метод производящих функций обычно используется для перечисления
комбинаторных чисел и установления комбинаторных тождеств.
Пусть задана последовательность комбинаторных чисел { ai } и последовательность функций {
 i (x) } ( i = 0, 1, … }.
Определение 4.5
Производящей функцией называется следующая функция

F(x) =  ai i ( x)
i 0
Пример 4.13
i
i
Пусть ai  Cn , ( i = 0, 1, …, n ), i ( x)  x .
В этом случае в качестве производящей функции будет бином
n
Ньютона, т.е. F(x) = ( 1 + x ) n =  Cni x i
i 0
С
помощью
этой
производящей
функции
справедливость следующего равенства:
n
С 2nn   (C nk ) 2
k 0
81
можно
установить
Для этого запишем тождество: ( 1 + x ) 2 n = ( 1 + x ) n ( 1 + x ) n . Оно будет
эквивалентно следующему тождеству:
2n
n
n
i 0
k 0
m 0
i
i
k k
m m
 C 2 n x  (  C n x )(  C n x ) .
Приравнивая коэффициенты при x n в обеих частях этого равенства,
получим
n
n
k 0
k 0
С 2nn   C nk C nn k   (C nk ) 2 .
Иногда удается использовать свойства последовательности { ai } для
нахождения уравнения в которое входит производящая функция F(x). Если
удается решить это уравнение, то можно получить выражения для { ai }.
В качестве примера рассмотрим такой случай с числами Фибоначчи,
которые определяются следующими рекуррентными соотношениями:
а0 = а1 = 1,
а n = а n1 + а n2 , n > 1.
Запишем производящую функцию для этой последовательности при
n ( x)  x n . Получим: F(x) =  an x n .
n 0

Это выражение запишем в следующем виде
F(x) =
а0 + а1 x +

а0 + а1 x +
n
 an x =
n 2


n2
n2
n
n
 a n 1 x +  an 2 x
=
= а0 +
а1 x +

 an x
n 1
n 1

+  an x n 2 .
n 0
Легко видеть, что первая сумма в этом выражении равна x ( F(x) ), а вторая x 2 F(x). Тогда F(x) можно записать так
F(x) =
Учитывая, что
а 0 + а x + x F(x) + x ( F(x) – а 0 ).
2
1
а 0 = а = 1, получим
1
F(x) = 1 + x + x 2 F(x) + x (F(x) – 1 )
82
а0
1
.
1 x  x2
Откуда получим: F(x) =
Эту функцию можно разложить в степенной ряд. Для этого
знаменатель функции представим в виде: 1 – x - x 2 = ( 1 -
а = 1
5
2
Тогда: F(x) =
, b=
а x)( 1 – bx) , где
1 5
.
2
А
B
a
b
, где А =
, B=
.

1  ax 1  bx
a b
a b
Учитывая, что при малых x справедливо:

1
  c n x n , получим :
1  сx n 0
a n1  b n1 n
x
n 0
ab

F(x) = 
Получим следующие выражения для членов последовательности
аnв
виде
аn =
1  1  5 


5  2 
n 1
n 1
1 5  
 .
 

2

 
Можно проверить непосредственно, что это выражение удовлетворяет
рекуррентным соотношениям для чисел Фибоначчи.
Задача о беспорядке
Определение 4.6
Беспорядком называется такая перестановка из N элементов, при
которой ни один из элементов не останется на своем месте.
Dn - число беспорядков.
1
1
n 1 
1
Dn  n!


 ...   1

n! 
 2! 3! 4!
D0  1
Число перестановок из n – элементов, при которых r – элементов
остается на своих местах равно:
83
Dn ,r  C nr Dn  r
Пример 4.14
При отправлении писем обнаружилось, что некоторые письма пришли
не по своим местам. Пришлось обрабатывать 5 писем.
а) Найти число случаев, при которых ни один адресат не получил
письма.
б) Найти число случаев, при которых один адресат получит письмо.
в) Найти число случаев, при которых два адресата получат письма.
Решение:
а) D5  5! 1  1  1  1   44 ;
 2! 3!
4! 5! 
б) D5,1  C 51 D4  5  4! 1  1  1   45
 2!
3!
4! 
в) D4 , 2  C 42 D3  6  3! 1  1   12
 2!
3! 
Соединения с повторениями
До сих пор рассматривали соединения из множеств, состоящих из
различных элементов. Часто на практике имеют место случаи, когда среди
рассматриваемых элементов есть одинаковые.
Перестановки с повторениями
Определение 4.7
Пусть дано множество из n элементов, в котором - n1 элементов
принадлежит к 1 типу; n2 элементов принадлежит к 2 типу элементов, nk - kтому типу. Элементы одного и того же типа неразличимы между собой.
Тогда, общее число перестановок данного множества n элементов равно:
k
!
n  n.
P( n , n ..., n )  n !n n!...

,
где
nk !
1 2
k
1 2
i1 i
84
Следствие:
P(m, n  m) 
m
n!

Cn ;
m!(nm)!
P ( n1 ,..., nk )  C n1  C n 2n1 ...C nkk .
n
n
n
Пример 4.15
Сколько различных чисел можно получить, переставляя цифры числа
12341234?
Решение: P(2,2,2,2)  (28!!)4
Размещения с повторениями
Определение 4.8
Размещения с повторениями (m перестановки с неограниченными
повторениями). Пусть имеется множество A  a1 , a2 ..., an , A  n . Рассмотрим
следующую схему выбора упорядоченной последовательности из m
элементов: выбираем элемент на 1-е место, имеется n вариантов выбора. После
этого элемент возвращается обратно и может быть выбран еще, т.е. на 2-е
место имеется n претендентов и т.д.
Число различных размещений с повторениями из n по m равно:
~
Anm  n m
Пример 4.16
Сколько различных сигналов может дать 4 семафора одновременно?
~
Решение N  3  3  3  3  A34  3 4 .
85
Сочетания с повторениями
Определение 4.9
Пусть A  a1 , a2 ..., an , где a1 , a2 ..., an
- представители 1-го, 2-го,…
n-го типа элементов. Объектов каждого типа имеется в неограниченном
количестве.
Сочетания с повторениями отличаются составом элементов, входящих
в выбираемое множество. Порядок элементов не имеет значения. Имеет
значение, сколько элементов каждого типа вошло в сочетание.
Рассмотрим сочетание: r1 объектов 1-го типа,
r2 объектов 2-го типа,
. . . . . . . . .
rn объектов n-го типа;
n
 ri  m
i 1
Некоторые ri могут быть равны 0. Сочетанию можно поставить в
соответствие следующую схему:
00
...
...0 ... 00
..0


0 0
r2
r1
rn
Вертикальные черточки отделяют элементы одного вида от элементов
другого вида. Если элементов какого-либо вида нет, две черты будут рядом.
Количество черточек равно (n-1). Каждому сочетанию с повторениями
соответствует схема и наоборот, каждая подобная схема соответствует
некоторому сочетанию с повторениями.
Количество сочетаний с повторениями из n по m равно числу таких
схем.
Всего в схеме (n-1)+m объектов, (n-1) – черточек и m – нулей. Нужно
выбрать места для (n-1) черточек. Число схем равно числу различных
86
перестановок из (n+m-1) – элементов, среди которых (n-1) – одинаковых “ |
” и m – одинаковых “ 0 ”.
P(n  m - 1; n - 1, m) 
(n  m - 1)!
 C nm m 1  C mn 1n 1
m!(n - 1)!
Число различных сочетаний с повторениями из n по m равно:
~
C nm  C nnm1 1  C nm m 1  P(n  m  1; n  1, m) .
Пример 4.17 В кондитерской продают 4 вида пирожных. Сколькими
способами один человек может купить 8 пирожных?
Решение:
~
C 48  C 44118  C113 .
Число Стирлинга второго рода
Если Y представить набором подмножеств Y={Y1;Y2;...;Yt},
то
отображение множества Х={x1;x2;...;xn} на Y определит разбиение множества
X на подмножества Х1;Х2;...;Хt, при выполнении следующих условий:
|Y1|+|Y2|+...+|Yt|=|X|=n; i=1tXi=X;
XiXj=0, для ij; 1i, jt;
Xi, для 1it;
Каждое подмножество Хi называют блоком разбиения множества Х, а само
разбиение обозначают символом Bt(Х), т.е. Bt(Х)={Х1;Х2;...;Хt}.
Число возможных разбиений множества Х определяется числом Стирлинга
второго рода:
S(n;t)=|Bt(Х)|,
где n - мощность множества X, а t - число подмножеств, по системе
рекуррентных соотношений:
87
S(n;0)=0 для n>0;
S(n;n)=1 для n0;
S(n;t)=S(n-1;t-1)+tS(n-1;t) для 0<tn.
Пример 4.18
Пусть дано множество Х={a, b, c, d}. Необходимо выполнить разбиение
на два одноэлементных подмножества и одно двухэлементное, т.е. Y={Y1, Y2,
Y3}, где |Y1|=1, |Y2|=1, |Y3|=2.
Решение:
Число таких разбиений по формуле Стирлинга определяется так:
S(4, 3)=S(3, 2)+3S(3, 3)=S(3, 2)+3,
S(3, 2)=S(2, 1)+2S(2, 2)=S(2, 1)+2;
S(2, 1)=S(1, 0)+1S(1, 1)=0+1;
S(4, 3)=3+2+1=6.
Множество подмножеств разбиения есть: B3(4)={{{a}, {b}, {c, d}}; {{a}, {c},
{b, d}}; {{a}, {d}, {b, c}}; {{b}, {c}, {a, d}}; {{b}, {d}, {a, c}}; {{c}, {d}, {a,
b}}}.
Замечание 4.1
Множество подмножеств универсального множества U, включающее в
себя пустое подмножество - , одноэлементные подмножества - {(|U|)1},
двухэлементные - {(|U|)2}, трёхэлементные {(|U|)3}, и т. д. до n-элементного {(|U|)|U|}, называют семейством подмножеств универсального множества U
или его булеаном B(U).
Каждое подмножество есть сочетание без повторения элементов
универсально
множества
|U|=n
по
подмножества i.
88
числу
элементов
формируемого
Пример 4.19
Пусть U={a, b, c, d}. Семейство подмножеств данного множества есть:
B(U)={; {a}; {b}; {c}; {d}; {a, b}; {a, c}; {a, d}; {b, c}; {b, d}; {c, d};
{a, b, c}; {a, b, d}; {b, c, d}; {a, c, d}; {a, b, c, d}}.
Задачи для самостоятельного решения
№ 1 Сколько различных перестановок можно образовать из всех букв
слова Миссисипи?
Ответ:
9! .
1!3!4!1!
№ 2 В кондитерской продают 4 вида пирожных. Сколькими
способами 8 различных человек могут купить по 1 пирожному?
~
Ответ: A48  4 8
№ 3 Сколько различных трехзначных чисел можно составить из цифр
1,2,…9 так, чтобы ни одна цифра не повторялась?
~
Ответ: A93  9 3
№ 4 Сколькими способами можно выбрать из колоды в 52 карты по 1
карте каждой масти?
~
Ответ: C 131 C131  C131 C 131  13 4  A134
№ 5 Пусть Х={a, b, c, d} и Y={y1, y2, y3}. Необходимо выполнить
сочетание из четырех элементов по три с повторением.
Ответ: 20
№ 6 Из m букв и n цифр следует сформировать k элементные
множества, содержащие s букв и (k-s) цифр при условии sm, (k-s)n.
№ 7 В цехе имеется 9 свободных рабочих мест, из которых на двух
могут работать только женщины, на трех - только мужчины. Сколькими
89
способами можно распределить трех женщин и четырех мужчин на эти
рабочие места?
Ответ: 6 способов
№ 8 Сколькими способами можно расставить на полке 5 книг?
Ответ: P5=5!
№ 9 Сколько различных слов можно образовать, переставляя буквы в
слове "ковш"?
Ответ: P4=4!
№ 10 Сколько различных 4х символьных идентификаторов можно
получить в алфавите {A,B,C,D,E}.
Ответ: 120.
Контрольные вопросы
1.
Дайте определение беспорядка.
2.
Приведите формулу перестановки с повторениями.
3.
Приведите формулу сочетаний с повторениями.
4.
Приведите формулу размещений с повторениями.
5.
Дайте определение числа Стирлинга второго рода.
6.
Что есть с точки зрения комбинаторики подмножество множества?
7.
Дайте определение комбинаторики?
8.
Дайте определение выборки?
9.
Приведите формулу включений – исключений.
10.
Дайте определение размещения без повторений?
11.
Дайте определение сочетаний без повторений?
12.
Дайте определение перестановки?
13.
Приведите свойства числа сочетаний.
14.
Дайте определение числам Фибоначи.
90
Математическая логика
Основы математической логики
Математическая логика - это формальная система, носителем которой
являются символы и последовательности символов формального языка, а
множество операций используется для формирования и вывода новых
суждений формального языка. Между символами нет иных связей и
отношений, кроме тех, которые описаны средствами самой формальной
системы.
Выделяют несколько типов формальных систем: логика высказываний
и логика предикатов, логика отношений и нечеткая логика и др.
Логика высказываний (prepositional calculus) есть модель формальной
системы, предметом которой являются повествовательные предложения,
взятые целиком без учета их внутренней структуры.
Логика предикатов (predicate calculus)
есть формальная система,
предметом которой являются предложения с учетом их внутренних состава и
структуры.
Логика отношений (relation calculus) есть формальная система,
предметом которой являются отношения в виде множества однородных
предложений, существенно расширяющие логику предикатов. Чаще эту
логику называют реляционной.
Логика нечеткая (fuzzi calculus) есть формальная система, предметом
которой являются предложения при нечетком задании характерных признаков
отдельных составляющих элементов или отношений между ними.
Логика высказываний
Исходным понятием математической логики является
“высказывание”.
91
Определение 15.1
Любое повествовательное предложение, которое может быть
признано истинным или ложным, называют высказыванием.
Пример 5.1
Предложение "З есть простое число" является истинным, а “3.14… рациональное число" - ложным, "Колумб открыл Америку" - истинным, а
"Киев - столица Узбекистана" – ложным, “число 6 делится на 2 и на 3” –
истинным, а “сумма чисел 2 и 3 равна 6” – ложным и т.п.
Такие высказывания называют простыми или элементарными. Их
обозначают прописными буквами латинского алфавита “A”, “B”, “C”,…
Истинность или ложность высказывания будем отмечать символами “и” –
истина или “л” – ложь.
Определение 5.2
Высказывания, которые получаются из простых предложений с
помощью грамматических связок “не”, “и”, “или”, “если…, то…”, “… тогда и
только тогда, когда…” и т.п., называют сложными.
Для обозначения грамматических связок в формальном языке вводят
дополнительные символы, которые называют логическими связками.
Например, :=”или”, &:=“и”, :=”не”, :=“если…, то…”, :=“…тогда и
только тогда, когда …”.
Для построения сложных высказываний используют также
вспомогательные символы “(“, “)” - скобки.
Пример 5.2
Если высказывание: “3 – вещественное или целое число”, то формула
(A1A2) = и; если высказывание: ”3,14… - рациональное число”, то формулы
B1=л или B1 = и;
92
Логические связки позволяют сохранять или изменять логическое
значение сложного высказывания, относительно простых высказываний его
формирующих. Поэтому они обозначают логические операции над
высказываниями. Правила исполнения логических операций над
высказываниями формирует алгебру высказываний.
Алгебра высказываний
Определение 5.3
Множество T={A, B, C,…} с заданными над ним логическими
операциями F={; ; ; ;  } формируют модель алгебры высказываний
Aв=<T; F>.
Символы логических операций заданы логическими связками:  отрицание,  - конъюнкция,  - дизъюнкция,  - импликация,  эквиваленция.
Определение 5.4
Сложное
высказывание,
которое
может
быть
получено
из
элементарных высказываний посредством применения логических связок,
называют формулой алгебры логики.
Определение 5.5
Любую пропозициональную переменную называют элементарной
формулой.
Пример 11 3
Ai =Fi.
Если F1 и F2 –формулы, то F1; F2; F1F2; F1F2; F1F2 и F1F2 также
формулы.
Логические операции бывают унарные (или одноместные) и бинарные
(или двухместные). Это определяется наличием одного или двух операндов у
операции.
93
Различные значения логической формулы в зависимости от значений
входящих в нее элементарных высказываний, могут быть полностью описаны
с помощью таблицы истинности.
Правила записи сложных формул.
Для определения истинности суждения необходимо анализировать
значение истинности каждого элементарного высказывания и формировать
последовательно значение истинности каждой подформулы, входящей в
формулу сложного суждения.
Логические
значения
формулы
удобно
описывать
таблицами
истинности.
Пример 5.4
Суждение "если инвестиции на текущий год не изменятся (A), то
возрастет расходная часть бюджета (B) или возникнет безработица (C), а если
возрастет расходная часть бюджета, то налоги не будут снижены (D) и,
наконец, если налоги не будут снижены и инвестиции не изменятся, то
безработица не возникнет".
В этом суждении есть четыре повествовательных предложения. Тогда
формула сложного суждения имеет вид:
F =(A(BC))&(BD)&((D&A) C).
Ниже представлена таблица истинности для этого суждения. Для
удобства
записи
любой
подформулы
и
формулы
каждый
столбец
пронумерован и логические операции выполняются с индексами столбцов.
94
B
C
D
C
4&1
23
17
24
65
8&9
11&10
1
2
3
4
5
6
7
8
9
10
11
12
Л
Л
Л
Л
И
Л
Л
И
И
И
И
И
Л
Л
Л
И
И
Л
Л
И
И
И
И
И
Л
Л
И
Л
Л
Л
И
И
И
И
И
И
Л
Л
И
И
Л
Л
И
И
И
И
И
И
Л
И
Л
Л
И
Л
И
И
Л
И
Л
Л
Л
И
Л
И
И
Л
И
И
И
И
И
И
И
И
Л
Л
Л
И
И
Л
И
Л
Л
Л
И
И
И
Л
Л
И
И
И
И
И
И
И
Л
Л
Л
И
Л
Л
Л
И
И
Л
Л
И
Л
Л
И
И
И
Л
Л
И
И
Л
Л
И
Л
И
Л
Л
Л
И
И
И
И
И
И
И
Л
И
И
Л
И
И
И
И
Л
И
Л
И
И
Л
Л
И
Л
И
И
Л
И
Л
Л
И
И
Л
И
И
И
И
И
И
И
И
И
И
И
И
Л
Л
Л
И
И
Л
И
Л
Л
И
И
И
И
Л
И
И
И
И
Л
И
Л
A
Л
Анализ таблицы показывает: чтобы не возникла безработица нужно не
снижать налоги (D=и) при любых тенденциях инвестиций (А=и или А=л) и
расходной части бюджета (В=и или В=л).
Правила записи сложных суждений
-
каждое
вхождение
логической
связки
“”
относится
к
пропозициональной переменной или формуле, следующей непосредственно за
логической связкой справа;
- каждое вхождение логической связки “” после расстановки скобок
связывает пропозициональные переменные или формулы, непосредственно
окружающие логическую связку;
- каждое вхождение логической связки “” после расстановки скобок
связывает пропозициональные переменные или формулы, непосредственно
окружающие эту связку и т.д.;
- в формулах нет двух рядом стоящих логичеcких связок - они должны
быть разъединены формулами;
- в формулах нет двух рядом стоящих формул - они должны быть
разъединены логической связкой.
95
- логические связки по силе и значимости упорядочены так: , , , ,
, т.е. самой сильной связкой является отрицание, затем коньюнкция,
дизьюнкция, импликация и, наконец, эквиваленция; знания о силе логических
связок позволяют опускать скобки, без которых ясен порядок исполнения
логических операций.
Законы алгебры логики
Наименование
закона
Коммутативности
Ассоциативности
Равносильные формулы Fi=Fj
(F1F2)=(F2F1); (F1F2)=(F2F1)
F1(F2F3)=(F1F2)F3; F1(F2F3) =
= (F1F2) F3
Дистрибутивности
F1(F2F3)=(F1F2)(F1F3);
F1(F2F3)=F1F2F1F3
Идемпотентности
FF = F; FF = F
Исключенного
третьего
FF = и;
Противоречия
FF = л
Де Моргана
(F1F2) = F1F2; (F1F2) = F1F2.
Поглощения
F1(F1F2) = F1; F1(F1F2) = F1
Дополнения
(F) = F
Свойства констант
Fл = F; Fи = и; Fл= л; Fи = F
96
Определение 5.6
Две формулы Fi и Fj называются равносильными, если они имеют
одинаковое значение “и” или “л” при одинаковых наборах
пропозициональных переменных, т.е. F1 = F2 .
Определение 5.7
Если две формулы равносильны, то они эквивалентны (FiFi).
Определение 5.8
Если формула F содержит подформулу Fi, которая, в свою очередь,
имеет эквивалентную формулу Fj, т.е. FiFj, то возможна подстановка в
формулу F всюду вместо формулы Fi формулу Fj без нарушения истинности
формулы F.
Знание
законов
алгебры
высказываний
позволяет
выполнять
эквивалентные преобразования любых логических формул, сохраняя их
значения для любых наборов пропозициональных переменных. Ниже на
примерах рассмотрены эквивалентные преобразования основных логических
операций.
Пример 5.5
Дано суждение "или верно, что Петр поступил в университет (А), и при
этом неверно, что Петр не поступил и Андрей не поступил, или Петр поступил
и Семен поступил (С), или даже Петр поступил и Семен поступил, и Андрей
поступил (В)"[2].
Формула сложного высказывания имеет вид:
А(AВ)АСАВС;
преобразовать, используя закон де Моргана:
А (АВ)АСАВС;
применить закон идемпотентности:
97
А (АВ)AАСАВС;
применить закон дистрибутивности по переменной А:
А((АВ) АСВС);
применить закон дистрибутивности по переменной С:
А((АВ) С(АВ));
ввести константу "и":
А((АВ)”и” С(АВ));
применить закон дистрибутивности для подформулы (АВ):
А(АВ)(“и”С);
удалить (“и”С):
А(АВ);
применить закон поглощения:
А.
Следовательно, в данном высказывании утверждается только то, что
Петр поступил в университет, а об Андрее и Семене никакой информации нет.
Задачи для самостоятельного решения
№ 1 Напишите формулы следующих суждений:
а) “подготовка специалистов высокой квалификации возможна лишь
на базе всемерного развития вузовской науки, усиления связи вузовской,
академической и отраслевой науки, обеспечения единства научной и учебной
работы, широкого привлечения студентов к научным исследованиям";
b) "хлеба уцелеют в различных климатических и погодных условиях
тогда и только тогда, когда будут выполнены все мелиоративные работы; если
хлеба не уцелеют, то фермеры обанкротятся и оставят фермы; следовательно,
98
необходимо выполнить все мелиоративные работы";
c) “если я поеду автобусом и автобус опоздает, то я опоздаю на работу;
если я опоздаю на работу и стану огорчаться, то я не попадусь на глаза моему
начальнику; если я не сделаю в срок важную работу, то я начну огорчаться и
попадусь на глаза моему начальнику. Следовательно, если я поеду автобусом,
а автобус опоздает, то я сделаю в срок важную работу”.
№ 2 Докажите эквивалентность следующих формул:
а) (AB)(AB)=A;
b) (AB)(BC)(CA)=(AB)(BC)(CA);
c) (AB)(AC)(BD)(CD)=((AD)(BC)).
Контрольные вопросы
1.
Дайте определение логики предикатов.
2.
Дайте определение логики отношений.
3.
Дайте определение нечёткой логики.
4.
Дайте определение логики высказываний.
5.
Дайте определение высказывания.
6.
Какое высказывание является простым?
7.
Какое высказывание является сложным?
8.
Дайте определение формулы.
9.
Приведите правила записи сложных высказываний.
10.
Приведите законы алгебры логики.
11.
Какие формулы являются равносильными?
99
Теория графов
Основные определения теории графов
Определение 6.1
Графы принято изображать в виде точек, называемыми вершинами, и
линий, называемыми дугами (ребрами), соединяющими две вершины графа.
Форма дуг несущественна, важен только сам факт соединения вершин.
Дуги могут пересекаться, но точки пересечения не являются вершинами графа.
Вершины графа будем обозначать v i , а дуги x i .
V2
x2
V4
x3
x4
x1
V1
V3
x5
V5
Рисунок 6.1 Граф
На рисунке: x1,x2,x3,x4 - дуги графа; v1,v2,v3,v4,v5 – вершины графа.
Определение 6.2
Если дуги имеют направление (ориентацию), отмеченное стрелкой, то
такие графы называются ориентированными или орграфами. Дуги графа часто
называют ребрами.
V2
x2
x3
x1
V1
x5
V3
x6
Рисунок 6.2 Орграф
100
x4
Определение 6.3
Дуга в орграфе, имеющая направление от вершины v i к вершине vј ,
называется выходящей из вершины vi и заходящей в вершину vj. При этом
вершина vi называется началом дуги, а
vj – ее концом.
Определение 6.4
Дуги, соединяющие две одинаковые вершины не ориентированного
графа, называются кратными.
На рисунке 6.1 дуги x1 и x2 являются кратными.
Определение 6.5
Дуга, выходящая из вершины и входящая в нее, называется петлёй.
На рисунке 6.2 дуга x4 является петлёй.
Определение 6.6
Дуги орграфа называются параллельными, если они соединяют две
одинаковые вершины орграфа и имеют одно направление.
На рисунке 6.2 дуги x 5 и x 6 являются параллельными.
Определение 6.7
Дуги орграфа называются противоположными, если они соединяют
две одинаковые вершины орграфа и противоположно направлены.
На рисунке 6.2 дуги x1 и x2 являются противоположными.
Определение 6.8
Две вершины графа называются смежными, если они соединены
дугой, иначе они называются несмежными.
Определение 6.9
Вершина графа (орграфа) называется изолированной, если она не
соединяется дугой с другими вершинами графа.
101
На рисунке 6.1 вершина v 5 является изолированной.
Определение 6.10
Граф с кратными дугами и петлями называется псевдографом. Орграф
называется псевдографом, если имеет параллельные дуги и петли.
Орграф на рисунке 6.2 является ориентированным псевдографом.
Определение 6.11
Граф с кратными дугами и без петель называется мультиграфом.
Орграф называется мультиграфом, если имеет параллельные дуги, но не
имеет петель.
Граф на рисунке 6.1 является мультиграфом.
Матрица смежности
Определение 6.12
Матрицей смежности графа, имеющего n вершин, называется
квадратная матрица A nn у которой элемент aij = k, если вершина i и j
соединены k дугами, иначе aij = 0.
V1 V2 V3 V4 V5
V1
0
2
1
0
0
V2
2
0
1
0
0
V3
1
1
0
1
0
V4
0
0
1
0
0
V5
0
0
0
0
0
Матрица смежности для графа рисунка 6.1.
102
V1
V2
V3
V1
0
1
0
V2
1
0
0
V3
2
1
1
Матрица смежности для орграфа рисунка 6.2.
Замечание 6.1
Для графа матрица смежности симметрична.
Замечание 6.2
Если в графе (орграфе) нет петель, то в матрице смежности по главной
диагонали стоят нулевые элементы.
Матрица инцидентности
Определение 6.13
Матрицей инцидентности графа, имеющего n вершин и m
дуг,
называется матрица B nm у которой элемент bij = 1, если вершина vi инцидентна
дуге xj, т.е. соединена дугой xj с другой вершиной графа. Иначе bij = 0.
Замечание 6.3
Для орграфа элемент матрицы инцидентности
bij = - 1, если из
вершины vi выходит дуга xj, и bij = 1, если в вершину vi заходит дуга xj.
Элемент bij = 0, если вершина vi не инцидентна дуге xj. Элемент bij = α, где α число петель в вершине vj.
103
x1
x2
x3
x4
x5
V1
1
1
0
0
1
V2
1
1
1
0
0
V3
0
0
1
1
1
V4
0
0
0
1
0
V5
0
0
0
0
0
Матрица инцидентности для графа рисунка 6.1
x1
x2
x3
x4
x5
x6
V1 1
1
0
0
1
1
V2 1
1
1
0
0
0
V3 0
0
1
1
1
1
Матрица инцидентности для орграфа рисунка 6.2
Список дуг
Определение 6.14
Список дуг графа – таблица, в каждой строке которой записывается
дуга и две вершины инцидентные этой дуге.
Замечание 6.4
В орграфе дуга будет инцидентна вершине, если данная вершина
является началом или концом этой дуги. Для неориентированных графов
порядок перечисления вершин произволен. Для орграфа вначале записывается
вершина являющаяся началом дуги.
104
Дуги
Вершины
x1
v1, v2
x2
v2, v1
x3
v3, v2
x4
v3, v3
x5
v3, v1
x6
v3, v1
Список дуг орграфа рисунка 6.2
Замечание 6.5
Граф часто обозначают так: G(X,V) , где X- множество дуг графа, а
V – множество его вершин, т.к. граф однозначно определяется через
множество своих вершин и множество дуг.
Определение 6.15
Граф называется конечным, если X и V- конечные множества.
Степень вершины
Определение 6.16
Степенью или валентностью вершины v графа (орграфа) называется
число дуг, инцидентных ей при этом каждая петля вносит вклад равный 2.
Замечание 6.6
Степень вершины v обозначается как deg v. Степень изолированной
вершины равна 0. Вершина, степень которой равна 1, называется висящей или
концевой.
105
Определение 6.17
Полустепенью захода в вершину
орграфа, называется число
v
заходящих в v дуг и обозначается deg  v.
Определение 6.18
Полустепенью исхода из вершины
v
орграфа называется число
выходящих из v дуг и обозначается deg  v.
Пример 6.1
Для вершины v1 орграфа рисунка 6.2 deg  v1 = 3, deg  v1 = 1, deg v1 = 4.
Утверждение 6.1
Для любого конечного графа (орграфа) сумма степеней всех вершин
n
графа равна удвоенному числу его дуг, т.е.  deg vi  2m , где m- число дуг
i 1
графа, n- число его вершин.
Утверждение 6.2
Сумма элементов i - ой строки или i -ого столбца матрицы смежности
n
n
j 1
j 1
графа равна степени i -ой вершины: deg v i =  aij =  a ji .
Утверждение 6.3
Сумма элементов i - ой строки матрицы инцидентности графа равна
m
степени i - ой вершины deg v i =  bij .
j 1
Утверждение 6.4
Для
n
n
i 1
i 1
любого
орграфа
выполняется


 deg vi   deg vi  m.
106
следующее
равенство:
Утверждение 6.5
Сумма элементов i - ой строки матрицы смежности ориентированного
мультиграфа равна полустепени исхода вершины v i , а сумма элементов i –
n
m
j 1
j 1
го столбца – полустепени захода вершины v i deg  v i =  aij ,deg  v i =  a ji .
Утверждение 6.6 (Теорема Эйлера о рукопожатиях)
В любом конечном графе число вершин нечетной степени четно или
равно нулю.
Задача о Кенигсбергских мостах
Задача, положившая начало теории графов - задача о Кенигсбергских
мостах.
Семь мостов города Кенигсберга расположены на реке Прегель так, как
изображено на рисунке 6.3, соединяя его части A,B,C,D. Нужно найти такую
точку города, выйдя из которой можно пройти по всем мостам города по
одному разу и вернуться в нее обратно.
Рисунок 6.3 Кенигсбергские мосты
107
Эйлер показал, что эта задача не имеет решения. Каждый мост он
заменил линией, соединяющей точки, соответствующие берегам. В
результате получился граф, изображенный на рисунке 12.4
А
С
D
B
Рисунок 6.4
Изоморфизм
Определение 6.19
Изоморфные графы (орграфы) имеют одинаковое число вершин и дуг
и отличаются лишь их обозначением, т.е. если можно переименовать вершины
и дуги графа (орграфа) G так, чтобы получился граф G1, то графы G и G1
будут изоморфными.
Алгоритм определения изоморфизма
Шаг 1. Если число вершин и число дуг, соответственно, совпадают для
орграфов, то переходим к шагу 2. Иначе орграфы не изоморфны.
Шаг 2. Для каждой вершины орграфов определяем пары чисел, равные
полустепеням захода и исхода. Если каждой такой паре орграфа G 1 найдется
аналогичная пара орграфа G 2 , то переходим к шагу 3. Иначе орграфы не
изоморфны.
108
Шаг 3. Если каждой рассмотренной паре чисел для орграфа G 1
соответствует единственная аналогичная пара орграфа G 2 , то есть
единственное соответствие между вершинами орграфов из которого можно
легко установить соответствие между дугами орграфов, т.е. они будут
изоморфными.
Пример 6.2
Проверим по алгоритму изоморфность графов:
x3
1
x2
2
2
3
x6
x1
x2
x5
x4
x5
4
x1
x3
3
4
1
x4
x6
G1
G2
Рисунок 6.5
Решение:
Шаг 1. У каждого из рассматриваемых орграфов по 4 вершины и по
6 дуг. Переходим к шагу 2.
Шаг 2. Для каждой вершины орграфов определяем пары чисел –
полустепени захода и исхода ( deg  v i ,deg  v i ). Эти пары представлены в
следующей таблице:
109
орграф
v1
v2
v3
v4
G2
(1,2) (2,1) (1,2) (2,1)
G1
(1,2) (2,1) (2,1) (1,2)
Из этой таблицы видно, что каждой паре орграфа G 2 можно найти
аналогичную пару орграфа G 1 . Переходим к шагу 3.
Шаг 3. Вершине v 1 орграфа G 2 соответствует пара (1,2). У орграфа
G 1 таких пар две. Следовательно, этой вершине можно сопоставить вершины
v 1 и v 4 орграфа G 1
Вначале поставим этой вершине в соответствие вершину v 1 орграфа
G 1 . Тогда по инцидентным этим вершинам дугам составим следующие
подстановки
 x1, x3, x6 
 и п2 =
п1 = 
 x5, x3, x1
 x1, x3, x6 

 .
 x5, x1, x3 
В этих и в последующих подстановках дуги в верхней строке относятся
к орграфу G 2 , а дуги нижней строки относятся к орграфу G 1 .
Далее вершине v 1 орграфа G 2 поставим в соответствие вершину v 4
орграфа G 1 . Тогда получим следующие подстановки для дуг
 x1, x3, x6 

п3 = 
x
1
,
x
4
,
x
6


 x1, x3, x6 
 .
и п4 = 
x
1
,
x
6
,
x
4


Из таблицы видно, что вершине v 2 орграфа G 2 можно сопоставить
вершины v 2 и v 3 . Из сопоставления v 2 → v 2 получим подстановки:
110
 x 2, x3, x5 
 и п6 =
п5 = 
x
2
,
x
3
,
x
6


 x 2, x3, x5 

 .
x
2
,
x
6
,
x
3


Из сопоставления v 2 → v 3 получим подстановки:
 x 2, x3, x5 
 и п8 =
п7 = 
x
5
,
x
2
,
x
4


 x 2, x3, x5 

 .
x
5
,
x
4
,
x
2


Вершине v 3 орграфа G 2 можно сопоставить вершины v 1 и v 4
орграфа G 1 .
Из сопоставления v 3 → v 1 получим подстановки:
 x 2, x1, x 4 

п9 = 
x
5
,
x
1
,
x
3


 x 2, x1, x 4 
 .
и п10 = 
x
5
,
x
3
,
x
1


Из сопоставления v 3 → v 4 получим подстановки:
 x 2, x1, x 4 
 и п12 =
п11 = 
 x1, x 4, x6 
 x 2, x1, x 4 

 .
 x1, x6, x 4 
Вершине v 4 орграфа G 2 можно сопоставить вершины v 2 и v 3
орграфа G 1 .
Из сопоставления v 4 → v 2 получим подстановки:
 x5, x 4, x6 
 и п14 =
п13 = 
x
2
,
x
3
,
x
6


 x5, x 4, x6 

 .
x
2
,
x
6
,
x
3


Из сопоставления v 4 → v 3 получим подстановки:
 x5, x 4, x6 

п15 = 
x
5
,
x
2
,
x
4


и
111
 x5, x 4, x6 
 .
п16 = 
x
5
,
x
4
,
x
2


При изоморфизме орграфов, если вершина
vi
орграфа
G2
соответствует вершине v j орграфа G 1 , то подстановка дуг, полученная из
этого соответствия, не должна противоречить
(n-1)
подстановкам,
полученных из-за соответствия для остальных (n-1) вершин орграфа G 2 .
Рассмотрим подстановки п1 и п2. Каждая из них не противоречит
только одной из приведенных выше, соответственно подстановкам п5 и п14.
Следовательно, вершина v 1 орграфа G 2
не соответствует вершине v 1
орграфа G 1 .
Следующая подстановка п3 не противоречит трем подстановкам п 8,
п9 и п13. Из этого следует подстановка для вершин:
 v1, v 2, v3, v 4 
 ,
Пв = 
 v 4, v3, v1, v 2 
где первая строка это вершины орграфа G 2 , а вторая строка вершины
орграфа G 1 .
Объединяя указанные подстановки получим полную подстановку для
дуг орграфов:
 x1, x 2, x3, x 4, x5, x6 
 .
Пд = 
x
1
,
x
5
,
x
4
,
x
3
,
x
2
,
x
6


Из полученных подстановок Пв и Пд следует, что орграфы
изоморфны.
Представленное ранее переименование вершин и дуг орграфа G 2
полностью соответствует этим подстановкам.
112
Плоские графы
Определение 6.20
Подразбиением (измельчением) дуги vi в неориентированном графе
или в орграфе называется замена ее на две новые и добавление одной новой
вершины.
v1
v2
v12
v2
v11
Подразбиение дуги v1 на дуги v11 и v12.
Определение 6.21
Подразбиение графа – граф, полученный путем последовательного
подразбиения его дуг.
Определение 6.22
Гомеоморфными графами (орграфами) называются графы (орграфы)
для которых существует их подразбиения, являющиеся изоморфными
графами.
v2
v2
v12
v3
v1
v31
v11
v32
G1
G2
Рисунок 6.6
113
Если в графе G1 выполнить подразбиение дуги v3 , а в графе G2
выполнить подразбиение дуги v1, то полученные графы будут изоморфны,
графы G1 и G2 гомеоморфны.
Определение 6.23
Геометрическим графом называется граф у которого множество
вершин – множество отмеченных точек в R2 или в R3, множество дуг –
множество параметризованных отрезков непрерывных кривых в R2 или в R3,
концами которых являются соответствующие им вершины.
Теорема 6.1
Для любого графа существует изоморфный ему геометрический граф
(в R2 или в R3) называемый геометрической реализацией.
Определение 6.24
Геометрический граф называется правильно реализованным (или
правильным), если его дуги не имеют общих точек, отличных от вершин
графа.
Графы на рисунке 6.6 правильные.
Определение 6.25
Граф называется плоским (планарным), если у него существует
правильная реализация в R2.
А
В
Рисунок 6.7
Граф А является планарным, т. к. его можно изобразить в виде В
114
Определение 6.26
Граф называют планарным, если он может быть изображён на
плоскости так, что рёбра или дуги графа не пересекаются.
Определение 6.27
Полным графом называется граф с n вершинами без петель, кратных и
противоположных дуг (ориентация безразлична), у которого любые две
вершины соединены дугой.
Графы А и В – полные.
Пути. Цепи. Циклы. Расстояния
Определение 6.28
Путем в графе (орграфе) называется последовательность в которой
чередуются вершины и дуги графа. Начинается последовательность с
вершины которая называется началом пути и заканчивается вершиной,
называемой концом пути.
V3
V1
x2
x1
V2
x4
x6
x3
x5
V4
V5
Рисунок 6.8
Для графа изображенного на рисунке, путем будет следующая
последовательность: v1 x1 v2 x3 v4 x4 v3, где v1- начало, а v3- конец пути.
115
Определение 6.29
Длиной пути называется число дуг, входящих в данный путь.
Длина приведенного выше пути – 3.
Определение 6.30
Путь называется замкнутым, если начало пути совпадает с концом
этого пути.
Определение 6.31
Цепью называется путь в котором все дуги различны.
Определение 6.32
Простая цепь – цепь в которой все вершины различны.
Определение 6.33
Циклом (контуром) в графе (в орграфе) называется замкнутая цепь.
Определение 6.34
Простой цикл (контур) – цикл (контур) в котором все вершины
различны.
Для графа приведённого на рисунке 7 путь v2 x3 v4 x4 v3 x2 v2 x1 v1
является цепью длиной 4, путь v1 x1 v2 x3 v4 x 4 v 3 – простая цепь длиной 3, путь
v1 x1 v2 x3 v4 x4 v3 x2 v2 x 5 v 5 x 6 v 1 – цикл (не является простым), путь v2 x2 v3 x4
v4 x3 v2 – простой цикл.
Теорема 6.2
Элемент
a ij k
матрицы
А k равен числу всех путей длиной k
из
вершины v i в вершину v j , где А k - k-я степень матрицы смежности графа
(орграфа).
Пример 6.3
Построить матрицу смежности и выяснить, сколько путей длины три
существует в графе G.
116
Х2
Х4
V1
V2
X1
V3
X3
Рисунок 6.8
Решение:
0

0
A
0

0
1 0 0
0 0


0 1 0  2 0 0
A 
0 0 1
0 0


0 0 0
0 0
Элемент
1 0
0 0


0 1  3 0 0
A 
0 0
0 0


0 0
0 0
0 1
0 0


0 0 4 0 0
A 
0 0
0 0


0 0
0 0
0 0

0 0
0 0

0 0 
a14( 3)  1 , следовательно, в данном графе существует
единственный путь длиной три. Это путь из вершины Х1 в вершину Х4:
V3
V1
V2
X 1 
X 2 
X 3 
X4.
Все элементы матрицы А4 равны нулю, следовательно, в графе
отсутствуют пути длиной четыре.
Определение 6.35
Путь (цепь) называют эйлеровым, если он замкнут и проходит через
каждое ребро графа только по одному разу.
Определение 6.36
Путь (цепь) называют гамильтоновым, если он замкнут и проходит
через каждую вершину графа только по одному разу.
Рисунок 6.9
117
Путь 00=(r04, r45, r53, r31, r10)}, показанный на рисунке а) – эйлеров.
Путь 00=(r04, r41, r15, r53, r31, r10)}, показанный на рисунке б) –
гамильтонов.
Определение 6.37
Расстоянием в графе между вершинами vi и vj называется длина
минимального пути из вершины v i в вершину v j и обозначается через d(v
i
, v j ).
Замечание 6.6
Принимается, что d(vi,vi) = 0 для любой вершины графа, и d(vi,vj) = ∞,
если из вершины vi нет пути в вершину vj.
Замечание 6.7
Расстояние в графе удовлетворяет аксиомам метрики:
1.d(vi, vj) ≥ 0, причем d(vi, vj) = 0 тогда и только тогда, когда vi = vj;
2.d(vi, vj) = d(vj, vi);
3.d(vi, vj) ≤ d(vi, vk) + d(vk, vj), где vi, vj, vk – произвольные вершины
графа.
Определение 6.38
Диаметром d(G) графа G(V,X) называется максимальное расстояние,
которое будет между некоторыми вершинами графа, т.е.:
d(G) = max d(vi, vj), vi, vj V
Определение 6.39
Эксцентриситетом
r(vi)
(максимальным удалением) вершины vi
называется максимальное расстояние от этой вершины до некоторой другой
вершины графа, т.е:
r(vi) = max d(vi, vj), vj V
118
Определение 6.40
Радиусом r(G) графа называется минимальный эксцентриситет в
данном графе, т.е.:
r(G) = min r(v), v V
Определение 6.41
Центром графа называется любая его вершина v эксцентриситет
которой равен радиусу графа, т.е.:
r(v) = r(G).
Пример 6.3
V3
V1
V4
V5
V2
Рисунок 6.9
d(G) = 3, r(v1) = 3, r(v2) = 2, r(v3) = 2, r(v4) = 2, r(v5) = 3, r(G)
= 2, v2, v3, v4 – центры графа.
Подграфы. Связность
Рисунок 6.10
119
Определение 6.42
Подграфом графа G называется граф, все вершины и дуги которого
содержатся среди вершин и дуг графа G.
На рисунке 6.10 граф с) является подграфом графа а)
Определение 6.43
Граф (орграф) называется связным (сильно связным), если для любых
двух его вершин vi и vj существует путь из вершины vi в вершину vj.
Определение 6.44
Вершина vj называется достижимой из вершины vi, если vi = vj, или
существует путь из вершины vi в вершину vj.
Определение 6.45
Орграф называется односторонне связным, если для любых двух его
вершин по крайней мере одна достижима из другой.
Определение 6.46
Псевдографом, ассоциированным с ориентированным псевдографом,
называется псевдограф, получающийся из ориентированного псевдографа,
путем замены направленных дуг на дуги без стрелок.
Определение 6.47
Орграф, не являющийся сильно связным, называется слабо связным,
если связным является ассоциированный с ним граф.
а
)
б
)
Рисунок 6.11
На
рисунке
6.11
представлены
ассоциированный псевдограф.
120
слабо
связанный
орграф
и
Определение 6.48
Компонентой
связности
(сильной
связности)
графа
(орграфа)
называется связный (сильно связный) подграф, не являющийся собственным
подграфом никакого другого связного (сильно связного) подграфа графа
(орграфа).
Пусть граф G с n вершинами и m ребрами содержит k компонент
связности.
Определение 6.49
Ранг графа определяется как:  (G) = n – k
Определение 6.50
Цикломатическое число графа определяется как:
 (G) = m – n + k.
При этом  (G) +  (G) = m.
Деревья
Определение 6.51
Граф называется деревом, если он является связным и не имеет
циклов.
G1
G2
G3
Рисунок 6.12
Графы G1 и G2 на рисунке 6.12 являются деревьями, а граф G3 – не
дерево.
121
Задачи для самостоятельного решения
№ 1 Построить графы, матрицы смежности которых указаны:
0

 0 1 1


1
M 1  1 0 1 ; M 2  
1
1 1 0 



1
1 1 1
0 1


0 1 1
1 0
;
M

3
1 0
1 0 1


1 1 0 
1 1
1 1

 0 1  1


1 1
;
M


1
0
1


4
0 1
 11 0 



1 0
Подсказка: воспользуйтесь определением матрицы смежности
(расставьте вершины и соедините их ребрами в соответствии с таблицей и
определением).
№ 2 Построить графы, матрицы инцидентности которых указаны:
0
 1 0 1 1



1
1
0
0





1

1
0
0
0
1 1 0 




0 1 1 0 


M 1  1 0 1 ; M 2  
; M3 
0
0
0 1
0 ;



0
0 1 1
 0 1 1


0
1

1
0

1




 1
0
0  1

 0
0
0
0
1

Подсказка: воспользуйтесь определением матрицы инцидентности
(расставьте вершины и соедините их ребрами в соответствии с таблицей и
определением).
№ 3 Для полученных в задачах 2 и 3 орграфах найдите списки дуг.
№ 4 Наидите таблицы степеней вершин у тех же Графов.
№ 5 Дан ориентировнный граф. Построить его матрицы смежности и
инцидентности.
1)
2)
3)
122
№ 6 Проверить изоморфность графов:
Ответ: изоморфные.
№ 7 Проверить изоморфность графов:
Ответ: неизоморфные.
№ 8 Какой из двух графов является планарным, а какой нет?
Ответ: а) – планарный, б) – нет.
№ 9 Среди графов, указанных на рисунке, выделить полные графы:
а)
б)
в)
123
г)
Ответ: а) и г) – полные, б) и в) – нет.
№ 10 Изоморфны ли графы, изображенные на ниже представленных
рисунках?
Ответ: нет
№ 11 Изоморфны ли графы, изображенные на ниже представленных
рисунках?
Ответ: да
№ 12 Дан граф и его матрица смежности. Сколько путей длины три
существует в графе?
124
0

1
A
0

1
1 0 0

1 1 1
1 0 1

0 0 0
Ответ: 5 путей.
№ 13 Являются ли примером эйлерова графа так называемые сабли
Магомета? Почему?
Ответ: Да.
№ 14 Дан граф:
С
В
М
А
Д
Найти все пути из А в В.
Ответ: АСВ, АСМВ, АСМДВ, АДВ, АДМВ, АДМСВ, АМВ, АМСВ,
АМДВ.
125
№ 15 Какие из графов, изображенных на рисунке являются частями графа G и
какие – подграфами.
G
А)
Б)
В)
Ответ А и Б – части графа, В – подграф.
Контрольные вопросы
1. Дайте определение графа.
2. Дайте определения смежных вершин, кратных дуг, петли, параллельных
дуг.
3. Дайте определение орграфа.
4. Дайте определение псевдографа.
5. Дайте определение мультиграфа.
6. Дать определение матрице смежности.
7. Дать определение матрице инцидентпости.
126
8. Дайте определение списка дуг.
9. Дайте определение степени вершины.
10. Рассказать о задаче Кенигсбергских мостов.
11. Дайте определение изоморфизма.
12. Какие графы называются гомеоморфными?
13. Какая реализация является правильной?
14. Какие графы называются планарными?
15. Какие графы называются полными?
16. Привести алгоритм проверки на изоморфизм.
17. Дайте определения пути и цикла.
18. По какой формуле вычисляется расстояние?
20. Дайте определения связанного графа.
21. Дайте определения подграфа.
22. Дайте определения компоненты связности.
23. Дайте определения дерева.
24. Дайте определения эйлерова цикла.
25. Дайте определения гамильтонова цикла.
127
Глоссарий
- равные множества – множества, состоящие из одних и тех же
элементов
- пустое множество – множество, не содержащее ни одного элемента
- Х содержится или включается в , если каждый элемент множества
Х является также элементом множества 
- конечное множество – множество, состоящее из конечного числа
элементов
- бесконечное множество – множество, состоящее из бесконечного
числа элементов
- объединением множеств A и B (обозначается A  B) называется
множество, состоящее из всех элементов, принадлежащих хотя бы одному из
этих множеств
- пересечением
множеств A и B (обозначается AB) называется
множество, состоящее из всех элементов, принадлежащих каждому из этих
множеств
- разностью множеств А и B (обозначается А \ B) называется
множество, состоящее из всех элементов множества A , не принадлежащих
множеству B
- дополнением множества А в универсальном множестве U
(обозначается
A,
А) называется множество, состоящее из всех элементов
универсального множества U, не принадлежащих множеству А
128
- симметрической разностью множеств A и B (обозначается A  B)
называется множество, состоящее из всех элементов, принадлежащих в
точности одному из этих множеств
- декартовым или прямым произведением множеств А и В называется
множество А В всех пар вида (а, b), где а А, b В.
- мощностью
конечного множества называется количество его
элементов.
- соответствием называют такое множество упорядоченных пар, если
для одного или нескольких элементов хiA0 существует несколько образов,
т.е. |{y}xi |>1.
- отображением называют такое множество упорядоченных пар, если
для каждого элемента хiA0 существует единственный образ, т.е. |{y}xi |=1.
- отношением на множествах X и Y называется произвольное
подмножество прямого (декартова) произведения этих множеств.
- область определения D бинарного отношения - множество первых
элементов каждой упорядоченной пары.
- область значений Е бинарного отношения - множество вторых
элементов каждой упорядоченной пар.
- рефликсивное бинарное отношение – отношение, если для каждого
хiХ имеем ρ(xi; xi)=1.
- антирефлексивное бинарное отношение – отношение, если для
каждого хiХ имеем ρ(xi, xi)=0.
- симметричное бинарное отношение – отношение, если для любой
пары (xi, xj)R имеем ρ(xi, xi)=ρ(xj, xi)=1.
129
- асимметричное бинарное отношение – отношение, если для любой
пары (xi, xj) при ij имеем ρ(xi, xi)ρ(xj, xi), а при i=j имеем ρ(xi, xi)=0.
- транзитивное бинарное отношение – отношение, если для любых
элементов xi, xj, xkХ существует ρ(xi, xi)=1 тогда и только тогда, когда
существует ρ(xi, xk)=1 и ρ(xk, xi)=1.
- отношением эквивалентности называется бинарное отношение,
удовлетворяющее
условиям
рефлексивности,
симметричности
и
транзитивности.
- отношением частичного порядка называют бинарные отношения,
удовлетворяющие
условиям
рефлексивности,
антисимметричности
и
транзитивности.
- композиция отношений  и  - отношение, состоящее из пар  ○  =
={(x, z)| х  у, y  z }.
- функцией называется бинарное отношение f между множествами A и B (f
 (AB), если для элемента xA найдется не более одного элемента yB вида
(x,y)f.
- сюръективной функцией (сюръекцией) называется функция f: AB ,
если область значения E(f) = B.
- инъективной (инъекция) является функция f: AB, если отношение f
1
является частичной функцией, т. е. для любых элементов х1, х2 D(f), если
х1  х2  f(х1)  f(х2).
- биективной функцией (биекцией), если f одновременно является
сюръекцией и инъекцией (обозначается f: AB).
130
- функцией алгебры логики называется функция, аргументы которой и
ее значения могут принимать значения из двухэлементного множества.
- логическая переменная – это переменная, которая может принимать
только два значения: истина или ложь.
- существенной переменной xi функции алгебры логики называется
переменная, если имеет место неравенство:f1(x1, x2, … , xi-1, 0, xi+1, … , xn)f2(x1,
x2, … , xi-1, 1, xi+1, …, xn).
- фиктивной переменной xi функции алгебры логики называется
переменная, если имеет место равенство: f1(x1, x2, … , xi-1, 0, xi+1, … , xn)=f2(x1,
x2, … , xi-1, 1, xi+1, …, xn).
- эквивалентными функциями алгебры логики называются функции,
имеющие одинаковые таблицы задания функции.
- суперпозицией функций f1, … , fm называется функция f, полученная
с помощью подстановок этих функций друг в друга и переименования
переменных.
- формулой алгебры логики называется выражение, описывающее
суперпозицию логических функций.
- эквивалентными называются формулы, представляющие одну и ту же
функцию.
- булева алгебра – алгебра с произвольным множеством элементов M,
сигнатура которой содержит две бинарные операции < & >, <

>, одну
унарную операцию < – > и две нульарных операции – константы 0 и 1 и
для любых x, y, z  M
-
алгеброй называется множество с определёнными на нем
операциями.
131
- алгеброй логики называется алгебра у которой множество
М-
логические переменные и логические функции, а сигнатура – логические
операции, т.е.
Ω = { − ,  , & , → , ↓ , ~ , / ,  }.
- полной конъюнкцией
n
переменных называется конъюнкция
состоящая из n переменных или их отрицаний, в которой каждая переменная
встречается только один раз.
-
совершенной
дизъюнктивной
нормальной
формой
(СДНФ)
логической функции называется формула, представляющая данную функцию,
и имеющая вид дизъюнкции полных конъюнкций, которые формируются для
наборов переменных при которых функция равна 1.
- полной дизъюнкцией
n
переменных называется дизъюнкция
состоящая из n переменных или их отрицаний, в которой каждая переменная
встречается только один раз.
-
совершенной
конъюнктивной
нормальной
формой
(СКНФ)
логической функции называется формула, представляющая данную функцию,
и имеющая вид конъюнкции полных дизъюнкций, которые формируются для
наборов переменных при которых функция равна нулю.
- дизъюнктивной нормальной формой (ДНФ) логической функции
называется дизъюнкция разных конъюнкций, которые не все являются
полными.
- конъюнктивной нормальной формой (КНФ) логической функции
называется конъюнкция разных дизъюнкций, которые не все являются
полными.
- минимальной называется ДНФ булевой функции, если она реализует
эту функцию и имеет наименьшее суммарное число сомножителей в своих
слагаемых по сравнению с другими эквивалентными ей ДНФ.
132
- минимизацией называется нахождение минимальной ДНФ функции.
- карты Карно – графический метод отображения булевых функций,
специальные таблицы, задающие булеву функцию.
- алгеброй Жегалкина называется алгебра над множеством логических
функций и переменных, сигнатура которой содержит две бинарные операции
& и  , и две нульарные операции – константы 0 и 1.
- полиномом Жегалкина для n логических переменных называется
полином, являющийся суммой константы и различных одночленов, в которые
все переменные входят не выше, чем в первой степени:
a  ∑ x i1 x i 2 … x ik , ( 1 ≤ k ≤ n )
- функционально полной называется система функций F = {f1, … , fn},
если любая логическая функция может быть представлена суперпозицией
функций этой системы.
- базисом называется минимальная полная система функций (т.е. такая
полная система функций, удаление из которой любой функции делает систему
не полной).
- замкнутым классом называется множество логических функций, если
любая суперпозиция функций из этого множества снова принадлежит ему.
- Тo – класс всех логических функций f( x1,…, xn ), сохраняющих ноль,
для которых выполняется равенство: f( 0, …, 0 )=0.
- T1 – класс всех логических функций f ( x1, …, xn ), сохраняющих
единицу, т.е.для которых выполняется равенство: f(1, …, 1) = 1.
- двойственной функцией называется функция
f*(x1, … , xn) к
функции f(x1, … , xn), если она определяется равенством:f*(x1, … , xn)= f ( x 1,
…,
xn
).
133
- самодвойственной называется функция f(x1, …, xn), если она
равносильна своей двойственной, т.е. выполняется следующее условие:f( x1,
… , xn ) = f(x1, … ,xn) или f(x1, … , xn)= f ( x1 , …, xn ).
- S – класс всех самодвойственных функций. Для данного класса
функции справедливо: на наборах значений переменных ( a1, … , an ) и ( a 1, …
, a n ), которые мы будем называть противоположными, самодвойственная
функция принимает противоположные значения.
- отношение предшествования a ≤ b для двух наборов
значений
переменных a = (a1, … , an) и b = (b1, … , bn) выполнено, если a1 ≤ b1, … , an ≤
bn, где ai, bi  {0,1}.
- монотонной называется функция f( x1, …, xn ), если для любых двух
наборов значений переменных a и b таких, что a ≤ b, имеет место неравенство:
f( a ) ≤ f( b ).
- M - класс всех монотонных логических функций
- линейной называется логическая функция
n
переменных, если
полином Жегалкина, представляющий данную функцию, содержит только
линейные слагаемые, т.е.
f(x1, …, x ) = a0  a1 x1  a2 x  …  an xn , где ai  {0,1}.
- L – класс всех линейных логических функций.
- предполным называется функционально замкнутый класс, если он не
содержится ни в каком функционально замкнутом классе, отличном от самого
себя и от класса всех функций алгебры логики.
- Теорема Поста. Для того чтобы система функций была полной,
необходимо и достаточно, чтобы она целиком не содержалась ни в одном из
пяти замкнутых классов To, T1, S, M и L.
134
- замыканием множества К называется множество всех логических
функций, представимых в виде формул через функции множества К.
Замыкание множества К обозначается [K].
- комбинаторикой называется раздел математики, изучающий методы
решения задач, определяющих количество возможных наборов объектов из
заданного множества, удовлетворяющих определенным условиям.
- выборками в комбинаторике называется возможные комбинации
объектов.
- комбинаторным объектом называется каждую выборку.
- комбинаторным числом называется количество выборок.
- Правило суммы: пусть A – множество из m элементов; B – множество
из n элементов. AB=. Тогда, объединение множеств: AB содержит m+n
элементов.
- Правило произведения: Если A и B – конечные множества и |A|=m,
|B|=n, то мощность множества AB равна mn.
- формула включения и исключения:
N 1,  2 ,..., 3   N  N 1   N  2   ...  N  n  
 N 1 ,  2   N  2 ,  3   ...  N  n 1 ,  n  
 N 1 ,  2 ,  3   ...  N  n 2 ,  n 1 ,  n   ...
  1n N 1 ,  2 ,..., n 
- перестановка из n элементов – упорядоченная последовательность
элементов n- элементного множества: Pn=n!
- размещения – упорядоченная последовательность из m элементов
множества, содержащего всего n элементов:
135
m
An 
n!
( n  m )!
- Сочетания из k по m – набор из m элементов, без учета порядка
элементов в наборе: Cnm 
n!
m !  ( n  m )!
, m<n.
- беспорядком называется такая перестановка из N элементов, при
которой ни один из элементов не останется на своем месте.
Dn - число беспорядков.
1
1 1
n 1 
Dn  n!     ...   1

n! 
 2! 3! 4!
D0  1
Число перестановок из n – элементов, при которых r – элементов
остается на своих местах равно:
Dn ,r  Cnr Dnr
число перестановок с повторениями множества
-
n элементов
равно:
k
n!
P(n1, n2 ..., n ) 
n n.
,
где

k n1!n2!...nk !
i 1 i
~
- число размещений с повторениями из n по m равно: Anm  nm
-
число
сочетаний
с
повторениями
из
n
по
m
равно:
~
Cnm  Cnnm1 1  Cnmm1  P(n  m  1; n  1, m) .
- математическая логика - это формальная система, носителем
которой являются символы и последовательности символов формального
языка, а множество операций используется для формирования и вывода новых
суждений формального языка. Между символами нет иных связей и
отношений, кроме тех, которые описаны средствами самой формальной
системы.
136
Выделяют несколько типов формальных систем: логика высказываний
и логика предикатов, логика отношений и нечеткая логика и др.
- логика высказываний (prepositional calculus) есть модель формальной
системы, предметом которой являются повествовательные предложения,
взятые целиком без учета их внутренней структуры.
- логика предикатов (predicate calculus)
есть формальная система,
предметом которой являются предложения с учетом их внутренних состава и
структуры.
- логика отношений (relation calculus) есть формальная система,
предметом которой являются отношения в виде множества однородных
предложений, существенно расширяющие логику предикатов. Чаще эту
логику называют реляционной.
- логика нечеткая (fuzzi calculus) есть формальная система, предметом
которой являются предложения при нечетком задании характерных признаков
отдельных составляющих элементов или отношений между ними.
- любое повествовательное предложение, которое может быть
признано истинным или ложным, называют высказыванием.
- высказывания называют простыми или элементарными. Их
обозначают прописными буквами латинского алфавита “A”, “B”, “C”,…
Истинность или ложность высказывания будем отмечать символами “и” –
истина или “л” – ложь.
- высказывания, которые получаются из простых предложений с
помощью грамматических связок “не”, “и”, “или”, “если…, то…”, “… тогда и
только тогда, когда…” и т.п., называют сложными.
- для обозначения грамматических связок в формальном языке вводят
дополнительные символы, которые называют логическими связками.
137
Например, :=”или”, &:=“и”, :=”не”, :=“если…, то…”, :=“…тогда и
только тогда, когда …”.
- для построения сложных высказываний используют также
вспомогательные символы “(“, “)” - скобки.
- множество T={A, B, C,…} с заданными над ним логическими
операциями F={; ; ; ;  } формируют модель алгебры высказываний
Aв=<T; F>.
- символы логических операций заданы логическими связками:  отрицание,  - конъюнкция,  - дизъюнкция,  - импликация,  эквиваленция.
-
сложное
высказывание,
которое может
быть получено
из
элементарных высказываний посредством применения логических связок,
называют формулой алгебры логики.
- любую пропозициональную переменную называют элементарной
формулой.
- логические операции бывают унарные (или одноместные) и бинарные
(или двухместные). Это определяется наличием одного или двух операндов у
операции.
- различные значения логической формулы в зависимости от значений
входящих в нее элементарных высказываний, могут быть полностью описаны
с помощью таблицы истинности.
- для определения истинности суждения необходимо анализировать
значение истинности каждого элементарного высказывания и формировать
последовательно значение истинности каждой подформулы, входящей в
формулу сложного суждения.
138
- логические значения формулы удобно описывать таблицами
истинности.
- графы принято изображать в виде точек, называемыми вершинами, и
линий, называемыми дугами (ребрами), соединяющими две вершины графа.
- ориентированными или орграфами называются такие графы, если
дуги имеют направление (ориентацию), отмеченное стрелкой.
- кратными называются дуги, соединяющие две одинаковые вершины
не ориентированного графа.
- петлей называется дуга, выходящая из вершины и входящая в нее.
- параллельными называются дуги орграфа, если они соединяют две
одинаковые вершины графа и имеют одно направление.
- противоположными называются дуги орграфа, если они соединяют
две одинаковые вершины графа и противоположно направлены.
- смежными называются две вершины графа, если они соединены
дугой, иначе они называются несмежными.
- изолированной называется вершина графа (орграфа), если она не
соединяется дугой с другими вершинами графа.
- псевдографом называется граф с кратными дугами и петлями.
- мультиграфом называется граф с кратными дугами и без петель.
- матрицей смежности графа, имеющего n вершин, называется
квадратная матрица A nn у которой элемент aij=k, если вершина i и j соединены
k дугами, иначе aij=0.
139
- матрицей инцидентности графа, имеющего n вершин и m дуг,
называется матрица B nm у которой элемент bij = 1, если вершина vi инцидентна
дуге xj, т.е. соединена дугой xj с другой вершиной графа. Иначе bij=0.
- список дуг графа – таблица, в каждой строке которой записывается
дуга и две вершины инцидентные этой дуге.
- степенью или валентностью вершины v графа (орграфа) называется
число дуг, инцидентных ей при этом каждая петля вносит вклад равный 2.
- степень изолированной вершины равна 0.
- степень висящей или концевой вершины равна 1.
- полустепенью захода в вершину
v
орграфа, называется число
заходящих в v дуг и обозначается deg  v.
- полустепенью исхода из вершины v орграфа называется число
выходящих из v дуг и обозначается deg  v.
- изоморфные графы (орграфы) имеют одинаковое число вершин и дуг
и отличаются лишь их обозначением.
- подразбиением (измельчением) дуги vi в неориентированном графе
или в орграфе называется замена ее на две новые и добавление одной новой
вершины.
- подразбиение графа – граф, полученный путем последовательного
подразбиения его дуг.
- гомеоморфными графами (орграфами) называются графы (орграфы)
для которых существует их подразбиения, являющиеся изоморфными
графами.
140
- геометрическим графом называется граф у которого множество
вершин – множество отмеченных точек в R2 или в R3, множество дуг –
множество параметризованных отрезков непрерывных кривых в R2 или в R3,
концами которых являются соответствующие им вершины.
- правильно реализованным называется геометрический граф, если его
дуги не имеют общих точек, отличных от вершин графа.
- плоским (планарным) называется граф, если у него существует
правильная реализация в R2.
- полным графом называется граф с n вершинами без петель, кратных и
противоположных дуг (ориентация безразлична), у которого любые две
вершины соединены дугой.
- путем в графе (орграфе) называется последовательность в которой
чередуются вершины и дуги графа. Начинается последовательность с
вершины которая называется началом пути и заканчивается вершиной,
называемой концом пути.
- длиной пути называется число дуг, входящих в данный путь.
- замкнутым называется путь, если начало пути совпадает с концом
этого пути.
- цепью называется путь в котором все дуги различны.
- простая цепь – цепь в которой все вершины различны.
- циклом ( контуром ) в графе (в орграфе) называется замкнутая цепь.
- простой цикл (контур) – цикл (контур) в котором все вершины
различны.
141
- эйлеровым называют путь (цепь), если он замкнут и проходит через
каждое ребро графа только по одному разу.
- гамильтоновым называют путь (цепь), если он замкнут и проходит
через каждую вершину графа только по одному разу.
- расстоянием в графе между вершинами vi и vj называется длина
минимального пути из вершины v i в вершину v j и обозначается через d( v i ,
v j ).
- аксиомы метрики:
1. d(vi, vj) ≥ 0, причем d(vi, vj) = 0 тогда и только тогда, когда vi = vj;
2. d(vi, vj) = d(vj, vi);
3. d(vi, vj) ≤ d(vi, vk) + d(vk, vj), где vi, vj, vk – произвольные вершины
графа.
- диаметром d(G) графа G(V,X) называется максимальное расстояние,
которое будет между некоторыми вершинами графа, т.е.d(G) = max d(vi, vj).
vi , vj  V
- эксцентриситетом r(vi) (максимальным удалением) вершины vi
называется максимальное расстояние от этой вершины до некоторой другой
вершины графа, т.е.
r(vi) = max d(vi, vj).
vj  V
- радиусом r(G) графа называется минимальный эксцентриситет в
данном графе, т.е
r(G) = min r(v).
142
v V
- центром графа называется любая его вершина v
эксцентриситет
которой равен радиусу графа, т.е. r(v) = r(G).
- подграфом графа G называется граф, все вершины и дуги которого
содержатся среди вершин и дуг графа G.
- связным (сильно связным) называется граф (орграф), если для любых
двух его вершин vi и vj существует путь из вершины vi в вершину vj.
- достижимой называется вершина vj из вершины vi, если vi = vj, или
существует путь из вершины vi в вершину vj.
- односторонне связным называется орграф, если для любых двух его
вершин по крайней мере одна достижима из другой.
- псевдографом, ассоциированным с ориентированным псевдографом,
называется псевдограф, получающийся из ориентированного псевдографа,
путем замены направленных дуг на дуги без стрелок.
- слабо связным называется орграф, не являющийся сильно связным,
если связным является ассоциированный с ним граф.
- компонентой связности (сильной связности) графа (орграфа)
называется связный (сильно связный) подграф, не являющийся собственным
подграфом никакого другого связного (сильно связного) подграфа графа
(орграфа).
- граф G с n вершинами и m ребрами содержит k компонент связности.
- ранг графа определяется как:  (G) = n – k
- цикломатическое число графа определяется как:  (G) = m – n + k.
При этом  (G) +  (G) = m.
143
- деревом называется граф, если он является связным и не имеет
циклов.
144
Литература
1.
Новиков, Ф. А. Дискретная математика для бакалавров и магистров:
учебник / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2013. - 400 с.
2.
Алашеева, Е. А. Дискретная математика [Текст] : конспект лекций / Е.
А. Алашеева ; ПГУТИ. - Самара : ИУНЛ ПГУТИ, 2013. - 143 с.
3.
Блатов, И. А. Дискретная математика [Текст] : учебное пособие для
студентов заочного факультета / И. А. Блатов, И. М. Сергиевская ; ПГУТИ. Самара : ИУНЛ ПГУТИ, 2011. - 67 с.
4.
Шевелев, Ю. П. Дискретная математика [Text] : учеб. пособие для вузов
/ Шевелев, Ю. П. - СПб. : Лань, 2008. - 592 с.
5.
Тишин, В. В. Дискретная математика в примерах и задачах [Текст] :
учеб. пособие для вузов / В. В. Тишин. - СПб. : БХВ-Петербург, 2008. - 337 с.
145
Документ
Категория
Без категории
Просмотров
10
Размер файла
2 373 Кб
Теги
posobie, matematiki, utchebnoe, diskretnaya, alasheeva
1/--страниц
Пожаловаться на содержимое документа