Дискретная математика
Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Дискретная математика
(конспект лекций)
для студентов направления 09.03.03 «Прикладная информатика»
2
Теория множеств.
Множеством S называется объединение в одно целое объектов, хорошо
различимых нашей мыслью или интуицией. Эти объекты называется
элементами множества S. Такое интуитивное определение дал немецкий
математик Г. Кантор. В данном определении важны следующие два момента:
1. Множество- это нечто, состоящее из хорошо различимых объектов.
2. Это нечто мыслится как единое целое.
Множества бывают конечными и бесконечными, Количество элементов в
конечном множестве называется мощностью множества. Множество, не
содержащее ни одного элемента, называется
пустым множеством и
обозначается . Множество, включающее в себя в се рассматриваемые
множества, называется универсальным множеством или универсумом и
обозначается U. Символом обозначается отношение принадлежности. Запись
x означает , что элемент х принадлежит множеству Х. Если элемент х не
принадлежит множеству Х, то пишут хХ.
Множества могут быть заданы следующими способами:
1. перечислением (списком своих элементов);
2. описанием свойств, которыми должны обладать его элементы;
3. порождающей процедурой.
ПРИМЕР
Множество экзаменационных оценок может быть задано:
1. перечислением А={2; 3; 4; 5}
2. описанием свойств: А={a a- экзаменационная оценка
3. порождающей процедурой: А=а а=2+i, i= 0,3
Подмножеством множества А называется множество В, если любой
элемент множества В принадлежит множеству А:
A B | a Aи a B
(1)
Символом обозначается отношение включения. Запись АВ означает
множество А является подмножеством множества В.
Не следует смешивать отношение принадлежности и отношение
включения .
Отношение принадлежности применяется к элементам
множества, а отношение включения к множествам. Хотя 1}, не
верно, что 1, так как единственным элементом множества 1 является
1.
Если А и , то , то есть множество А строго включено в
множество В. Символ называется строгим включением.
Свойства подмножеств.
1. Рефлексивность. Множество А является подмножеством множества А:
A A.
(2)
3
2. Транзитивность. Если множество А является подмножеством
множества В , а множество В является подмножеством множества С, то
множество А является подмножеством множества С:
A B, B C A C
(3)
3. Принцип объемности. Если множество А является подмножеством
множества В, а множество В является подмножеством множество А, то
множество А равно множеству В:
A B, B A A B
(4)
Операции над множествами.
1. Объединением множеств А и В называется множество, состоящее из
всех тех и только тех элементов, которые принадлежат хотя бы одному из
множеств А или В:
A B {x | x A или x B}
(5)
2. Пересечением множеств А и В называется множество, состоящее из тех
и только тех элементов, которые принадлежат множеству А и множеству В:
A B {x | x A и x B}
(6)
3. Разностью множества А и В называется множество всех тех элементов,
которые принадлежат множеству А и не принадлежат множеству В:
A \ B {x | x A и x B}
(7)
4. Симметричной разностью множеств А и В называется множество ,
состоящее из элементов множества А , не принадлежащих множеству В, и
элементов множества В, не принадлежащих множеству А:
AB {x | ( x A и x B) и ( x B и x A)}
(8)
5. Дополнением множества А называется множество всех тех элементов,
которые не принадлежат множеству А:
A {x | x A }
(9)
Для наглядного представления операций над множествами используют
диаграммы Эйлера- Венна.
U
A
B
3
1
2
4
Рис 1. Диаграмма Эйлера-Венна
где A B - это области 1,2,3
A B - это область 3;
А \ B - это область 1;
A - это область 1,3
- это области 2,4.
4
Алгебра теории множеств.
Для любых множеств А, В и С выполнимы следующие тождества:
1. Коммутативный закон
A B B A
A B B A
(9)
A ( B C ) ( A B) C
(10)
2. Ассоциативный закон
A ( B C ) ( A B) C
3. Дистрибутивный закон
A ( B C ) ( A B) ( A C )
A ( B C ) ( A B) ( A C ) (11)
4. Закон поглощения
A ( A B) A
A ( A B) A
(12)
A A A
(13)
5. Закон идемпотентности
A A A
6. Закон де Моргана
A B A B
A B A B
(14)
7. Закон исключенного третьего
A A U
(15)
8. Закон противоречия
A A
(16)
9. Операции с универсумом:
A U U
A U A
(17)
A
(18)
10. Операции с пустым множеством:
A A
U
11.
12. Закон двойного дополнения
U
A A
13.
A\ B A B
AB ( A \ B) ( B \ A) ( A B) ( B A)
(19)
(20)
(21)
14.
(22)
При преобразованиях выражений над множествами по законам алгебры
логики существуют следующие приоритеты: самой приоритетной операцией
является дополнение, затем пересечение и в последнюю очередь объединение.
Решение уравнений алгебры множеств.
Пусть дано уравнение вида:
A( X ) B( X )
(23)
где X - неизвестное множество. Необходимо определить это неизвестное
множество.
Алгоритм решения уравнений алгебры множеств имеет следующий
алгоритм:
1. Представляем данное уравнение в следующем виде:
A( X )B( X )
(24)
2. Используя алгебру множеств, преобразуем данное уравнение к виду:
5
C X D X
(25)
где C и D - некоторые множества, не содержащие множество X и его
дополнение.
3. Решением уравнения является следующее выражение:
(26)
D X C
C
x
D
Рис 2. Диаграмма Эйлера-Венна для решения уравнения алгебры множеств.
ПРИМЕР.
Необходимо решить уравнение:
X A B
1. Преобразуем данное уравнение:
( X A)B
2. С помощью алгебры множеств преобразуем данное выражение
следующим образом:
( X A) B ( X A) B X B A B X A B
В данном выражении присутствует множество A I B , в котором не
содержится ни множество X , ни его дополнение, поэтому к этому множеству
применяем следующие преобразования:
A B A B U A B (X X ) A B X A B X
C учетом данных преобразований имеем:
X B A B X A B X X A B
X ( B A B) X ( A B A B)
X B X ( AB).
Таким образом, имеем множества C и D в следующем виде:
CB
D AB .
Решением уравнения будет множество:
AB X B .
Решение уравнения (один из вариантов) может быть представлено на
диаграмме Эйлера-Венна
6
U
B
A
Рис 3 Диаграмма Эйлера-Венна для решения уравнения алгебры множеств.
При изображении решения уравнения алгебры множеств следует иметь в
виду, что два множества могут иметь следующие диаграммы Эйлера-Венна
U
U
U
A
A
B
A
B
B
U
U
B
A
A=В
Рис 4 Диаграмма Эйлера-Венна для решения уравнения алгебры множеств.
Кортеж.
Кортеж - это упорядоченный набор элементов. Кортеж характеризуется
элементами и их порядком расположения. Элементы кортежа называются
компонентами. Компоненты нумеруют слева направо. Число компонент
определяет длину кортежа. Кортеж обозначается а1, а2, ..., аn .
Кортеж длиной в две компоненты называется парой, кортеж длиной в три
компоненты - тройка, длиной в n - n-ка.
Проекцией кортежа на i-тую ось называется его i-тая компонента.
Проекцией кортежа на оси i1, i2, ..., iq оси называется кортеж, состоящий
из i1, i2, ... , iq компонент, где 2 q n .
Проекцией кортежа на пустое множество осей является пустой кортеж.
ПРИМЕР
Пусть дан кортеж А=< ,,,>. Найти проекции на 1 ось, 3 ось, 5 ось, 1 и 4
оси, 4 и 2 оси.
Пр А1=<>
Пр А3=<>
Пр А5 не определена
Пр А1,4=<>
Пр А4,2 не определена.
7
Проекция множества.
Проекция множества определена только для множеств, элементами
которого являются кортежи одинаковой длины.
Проекцией множества называется множество проекций соответствующих
кортежей.
Пример.
А=1,2,3;4,5,6;3,3,3
Пр А1=
Пр А1,3=,3,6,3
Пр А3,1 не определена.
График и свойства графика
Графиком называется множество пар. Графики могут задаваться :
1. перечислением: P { x1 , y1 ; x2 , y2 ; xn , y n }
2. описанием свойств: P { x, y | x y}
Пара называется инверсией пары , если a=d, b=c.
График P-1 называется инверсией графика P, если он состоит из инверсий
пар графика P.
ПРИМЕР.
P={<1,2>;<2,3>;<3,4>,<4,5>}.
P-1={<2,1>;<3,2>;<4,3>;<5,4>}.
График называется симметричным, если вместе с каждой парой он
содержит её инверсию.
(27)
Q P P 1
Диагональным называется график вида:
M { x, x ; y, y ;} ,
(28)
для всех x,y M.
Композицией графиков R P Q называется график R, такой что для
любой пары R есть такой элемент z, что P, а Q.
R P Q { x, z | x, y P, y; z Q} ,
(29)
ПРИМЕР.
1. Пусть заданы графики P={; ; } и Q={; ;
; }. Найти композицию графиков P и Q.
P o Q={;;;;}.
2. Пусть заданы графики P и Q:
8
z
y
P
R
1
-1
1
x
z
P◦Q
2
-1
1
2
-1
y
1
x
Рис 5. Композиция графиков.
Свойства графиков.
Функциональным графиком называется график, который не содержит
пары с одинаковыми первыми и различными вторыми компонентами.
Инъективным графиком называется график, который не содержит пары с
одинаковыми вторыми и различными первыми компонентами.
y
y
P1
y
P2
x
P3
x
x
Рис 6. Примеры графиков.
P1График функциональный, но не инъективный.
P2График инъективный, но не функциональный.
P3 График функциональный и инъективный.
Возможно другое изображение графиков.. Пусть X {a; b; c; d } , а Y {1;2;3;4}
Р1
Р2
Р3
Рис 7 . Примеры графиков.
P1График функциональный, но не инъективный.
P2График инъективный, но не функциональный.
P3 График функциональный и инъективный.
Прямое (декартовое) произведение множество.
Прямым (декартовым) произведением
B называется множество пар таких, что:
множества A и множества
9
A B { x, y | x A, y B} ,
(29)
ПРИМЕР.
Пусть заданы X и Y : X {x | x 2} , Y { y | y 2} . Тогда прямое (декартовое)
произведение этих множеств может быть представлено графически:X={x | x2}
2
XY
2
Рис. 8 График прямого произведения множеств X
иY:
Пусть заданы X и Y : X {a; b; c; d ; e; f ; g ; h} , Y {1;2;3;4;5;6;7;8} . Тогда прямое
(декартовое) произведение этих множеств представляет шахматную доску.
Соответствия.
Соответствием называется тройка вида P, X , Y . При этом X - область
отправления (определения), Y - область прибытия (значений), P X Y график соответствия.
ПРИМЕР.
Дано соответствие такое, что:
X={x x ;
Y=y y ;
P={ y=x2}.
y
5
х
2
Рис. 9 График соответствия.
Если P = X Y , то данное соответствие называется полным.
Если P = , то данное соответствие называется пустым.
10
Свойства соответствий.
1. Соответствие называется функциональным, если его график
функционален.
2. Соответствие называется инъективным, если его график инъективен.
3. Соответствие называется всюду определенным, если проекция его
графика на первую ось совпадает с областью отправления. Пр P1=X.
4. Соответствие называется сюръективным, если проекция его графика на
вторую ось совпадает с областью прибытия. Пр P2=Y.
5. Соответствие называется биективным (взаимнооднозначным), если оно
функционально, инъективно, всюду определенно, сюръективно.
ПРИМЕР.
Дано соответствие , где X - множество конфет, Y - множество
фантиков, P - ”быть упакованным в фантик”. Какими свойствами обладает
данное соответствие?
Данное соответствие
1. функциональное, так как две и более конфет не может быть упаковано в
один фантик;
2. инъективное, так как одна конфета не может быть завернута в два антика
одновременно (брак упаковочной техники не рассматривается);
3. не всюду определенное, так как существуют сорта конфет, которые
продаются без фантиков (зефир, мармелад);
4. сюръективное, так как фантики без конфет - это мусор;
5. не биективное, так как является несюръективным соответствием.
Отношения.
Отношением называется пара вида , M такая, что Ф2
(M2=M M),где Ф - график отношения, М - это множество, между элементами
которого существует данное отношение.
ПРИМЕР.
Пусть дано , M , где M {x | x N } , а график отношения
определяется как { x, y | x y} . Это отношение ”X больше Y” на
множестве натуральных чисел. Данное отношение задано описанием свойств.
Перечислением данное отношение может быть задано следующим образом:
,
где >
Отношение называется полным, если 2.
Отношение
называется
отношением
равенства,
если
{. Над
отношениями могут быть выполнены следующие операции:
1. объединение U r=< U R,M>.
2. пересечение r=<Ф R,M>.
3. дополнение {M 2 \ M }
4. разность \r=<Ф\R,M>.
5. композиция o r=<Ф o R,M>.
6. инверсия -1=<Ф-1,M>.
данными
Основные свойства отношений.
1. Рефлексивность.
Отношение называется рефлексивным, если для всех x выполняется
условие: xx или .
2. Антирефлексивность.
Отношение называется антирефлексивным, если для всех x выполняется
условие: xx (символ ““ означает “не выполняется”) или M .
3. Симметричность.
Отношение называется симметричным , если для всех x выполняется
условие: xy yx или Ф=Ф-1.
4. Антисимметричность.
Отношение называется антисимметричным, если для всех x выполняется
условие: xy и xy yx или 1 .
5. Асимметричность.
Отношение называется асимметричным, если для всех x выполняется
условие: xy yx или 1 =.
6. Связность (полнота).
Отношение называется связным (полным), если для всех x выполняется
условие: xy xy или yx или М2\ 1 .
7. Транзитивность.
Отношение называется транзитивным, если для всех x выполняется
условие: xy и yz xz или Ф o ФФ.
ПРИМЕР
Какими свойствами обладает отношение =<Ф,X>, где X={1; 2; а},
Ф={<1,1>;;;<2,2>}.
Определим Ф-1, X:
Ф-1={<1,1>;;<2,a>;<2,2>}
X={<1,1>;<2,2>;}.
12
Отношение является:
- рефлексивным, так как XФ;
- антисимметричным, так как I 1 X;
- транзитивным, так как Ф o Ф={<1,1>;;;<2,2>}Ф;
- несвязное, так как X2\X={<1,2>;<1,a>;<2,1>;<2,a>;;} Ф U Ф1
={<1,1>;;;<2,2>;<2,a>}.
Отношение называется отношением эквивалентности, если оно
рефлексивное, симметричное и транзитивное.
Отношение называется отношением нестрогого (частичного) порядка
( p ) , если оно рефлексивное, антисимметричное и транзитивное.
Отношение называется совершенно нестрого порядка ( ), если оно
рефлексивное, антисимметричное, транзитивное и связное.
Отношение называется строго порядка ( ), если оно антирефлексивное,
антисимметричное и транзитивное .
Отношение называется совершенно строго порядка ( ), если оно
антирефлексивное, транзитивное и связное.
Решетки.
Диаграммы Хассе.
Рассмотрим отношение частичного порядка: “быть подмножеством“ на
множестве-степени М={1,2}.
, где
Ф={<{},{}>;<{},{1}>;<{},{2}>;<{},{1,2}>;<{1},{1}>;<{1},{1,2}>;
<{2},{2}>;<{2},{1,2}>};<{1,2},{1,2}>}.
Графически данное отношение можно изобразить следующим образом:
{Ø}
{1}
{2}
{ 1, 2 }
РИС 10 Графическое изображения отношения
Отношение является рефлексивным (графически это отображается
петлями), антисимметричным ( графически - однонаправленные стрелки),
транзитивным ( графически - транзитивными замыканиями вида:
Для отношений частичного порядка применимы диаграммы Хассе, которые
строятся на основе обыкновенной диаграммы следующим образом:
1. рефлексивные петли и транзитивные связи не изображаются;
2. большие элементы ( элементы, в которые входят стрелки) располагают
выше.
13
Таким образом, диаграмма Хассе для вышеприведенного примера будет
выглядеть следующим образом:
{ 1, 2 }
{2}
{1}
{Ø}
РИС 11 Диаграмма Хассе
Для частично упорядоченного множества справедливо следующее:
1. Элемент аА называется наибольшим (наименьшим) , если для всех х
А выполняется x p a ( a p x). Если наибольший (наименьший) элемент
существует, то он единственный.
2. Элемент аА называется максимальным (минимальным) , если нет а
множестве А элементов, больших (меньших), чем а. Максимальных
(минимальных) элементов может быть несколько.
3. Пусть ВА. Элемент аА называется можарантой (минорантой) ,
если для всех х В этот элемент является наибольшим (наименьшим).
4. Множество мажорант В образует верхнюю границу множества В.
Множество минорант В образует нижнюю границу множества В.
5. Наименьший элемент верхней границы называется точной верхней
границей , или supremum ( sup ) B. Наибольший элемент нижней границы
называется точной нижней границей, или infimum (inf) B.
6. Частично упорядоченное множество, у которого для любой пары
элементов определен и существует sup и inf , называется решеткой.
ПРИМЕР
Пусть дано отношение, представленное на диаграмме Хассе
8
7
6
5
В
А
3
4
2
1
РИС 12 Диаграмма Хассе
Отношение А не является решеткой, т.к. элементы 7 и 8 не имеют sup.
Отношение В является решеткой, т.к. любая пара имеет sup и inf.
14
Алгебраическое представление решеток.
Введем обозначения: sup(a,b)=a U b, inf(a,b)=a I b. Для решетки справедливы
следующие свойства:
1. Коммутативный:
a U b=b U a
a I b=b I a
2. Ассоциативный:
а (в U с)=(а U в) U с
а I (в I с)=(а I в) I с
3. Идемпотентности:
а U а=а
а I а=а
4. Поглощения:
а U (а в)=а
а I (а U в)=а
Решетки , для которой выполняется дистрибутивный закон:
а U (в с)=(а U в) (а U с)
а I (в U с)=(а в) U (а с)
называется дистрибутивной решеткой.
Решетка называется ограниченной, если он имеет максимальный и
минимальный элемент.
ПРИМЕР
Пусть дана решетка (рис. 13). Определить
является ли решетка
5
дистрибутивной.
4
3
2
1
РИС 13 Диаграмма Хассе решетки
Решетка не является дистрибутивной, т.к. для элементов {2;3;4} не
выполняется дистрибутивный закон:
2 (3 4) 2 1 2
(2 3) (2 4) 5 4 4
2 (3 4) (2 3) (2 4)
Дана решетка ,
где М={xx1, Ф={xy. Эта решетка не является , так как не
определен максимальный элемент (0.9999999999 ....) и минимальный элемент
(0.0000000...1).
Обозначим в ограниченной решетке максимальный элемент 1, а
минимальный элемент 0. Элемент a называется дополнением элемента а в
15
данной решетке, если a U a 1 и a I a 0 . Решетка называется с дополнением,
если каждый элемент имеет хотя бы одно дополнение.
ПРИМЕР
Рассмотрим решетку, представленную на рис. 13. Найдем дополнения для
каждого элемента решетки
1 5
23
32
43
5 1
Данная решетка является решеткой с дополнением.
Ограниченная дистрибутивная решетка с дополнением называется булевой
решеткой.
На рис . 14 представлены дистрибутивные решетки
РИС. 14. Примеры булевых решеток
16
Математическая логика
Высказывания и операции над высказываниями.
Высказыванием называется повествовательное предложение, о котором
можно сказать истинно оно или ложно.
1. Москва - столица России.
2. Если студент учится на отлично, то он получит красный диплом.
3. Осадки - это снег или дождь.
4. Курица – не птица.
5. Пейте томатный сок.
6. Я лгу.
7. 23<5
Высказываниями являются 1, 2, 3,4 и 7 предложения. Предложение 5 не
является высказыванием, так как про него нельзя сказать истинно оно или
ложно. Предложение 6 является логическим парадоксом.
Элементарным высказыванием называется высказывание, которое
содержит одно утверждение (предложения 1,7).
Сложное (составное) высказывание состоит из элементарных
высказываний связанных с помощью следующих предлогов и частиц: И, НЕ,
ИЛИ, ЕСЛИ - ТО, ТОГДА И ТОЛЬКО ТОГДА и другие. Предложения 2,3,4
являются сложными высказываниями.
Операции над высказываниями.
Отрицанием высказывания х называется новое высказывание, которое
истинно, если высказывание ложное и наоборот. Таблица истинности операции
отрицания имеет вид:
x
x
1
1
Дизъюнкцией двух высказываний x и y (логическое «или»)называется
новое высказывание, которое будет истинным тогда когда, когда хотя бы одно из
высказываний будет истинным.
x
y
x y
1
1
1
1
1
1
1
Конъюнкцией двух высказываний x и y (логическое «и»)называется новое
высказывание, которое будет истинным тогда когда, когда оба высказывания
истины. Обозначение операции конъюнкция - &( )
17
x
y
x y
1
1
1
1
1
Импликацией двух высказываний x и y («если – то») называется новое
высказывание, которое ложно тогда, когда х (предпосылка) истинно, а у
(следствие) ложно.
x
y
x y
1
1
1
1
1
1
1
Эквивалентностью двух высказываний x и y («тогда и только тогда»)
называется новое высказывание, которое будет истинно , если высказывания х и
у будут одновременно истинны или ложны.
x
y
x y
1
1
1
1
1
1
Неодназночностью (суммой по модулю два) двух высказываний x и y
(«тогда и только тогда») называется новое высказывание, которое будет
истинно тогда когда одно из высказываний х или у истинно, а другое ложно.
x
y
x y
1
1
1
1
1
1
Штрих Шеффера (логическое «и - не») высказываний x и y - это новое
высказывание, которое будет ложно
тогда и только тогда когда оба
высказывания истинны.
x
y
xy
1
1
1
1
1
1
1
18
Стрелка Пирса (логическое «или - не») высказываний x и y - это новое
высказывание, которое будет истинно
тогда и только тогда когда оба
высказывания ложны.
x
y
xy
1
1
1
1
1
Для операций справедливы следующие приоритеты: , &, , , .
Формулы математической логики.
Формулой математической логики называется сложное высказывание,
которое получено из элементарных высказываний с использованием логических
операций.
Две формулы равносильны, если они принимают одинаковые логические
значения на любом наборе значений входящих в формулу элементарных
высказываний. Равносильность формул обозначается A B.
Формулы равносильности.
1) Коммутативность
АVВ ВVА
А&В В&А
2) Ассоциативность
АV(ВVС) (АVВ)VС
А&(В&С) (А&В) &С
3) Дистрибутивность
АV(В&С) (АVВ)&(АVС)
А&(ВVС) (А&В)V(А&С)
4) Идемпотентность
АVА А
А&А А
5) Поглощение
АV(А&В) А
А&(АVВ) А
6)
Закон де Моргана
АVВ А & В
А& В АVВ
7) Закон исключающий третьего
АV1 1
А&1 A
8) Закон противоречия
AV A
A&
19
9)
Закон двойного отрицания
A A
10)
11)
12)
13)
0 1, 1 0
AB A VB
AB (AB)&(BA)
AB A& B V A &B
14) A | B A & B A V B
15) AB AVB A & B
ПРИМЕР
Доказать: ( x y) ( x y) x
( x y) ( x y) xx x y yx y y x x y xy 0 x x y xy x xy x
Представление произвольной функции алгебры логики в виде
формулы алгебры логики
Пусть
F ( x , x , , x ) 1 2
n
произвольная
функция
алгебры
логики
n
переменных.
Рассмотрим формулу
F (1,1, 1,1) x x x
x F (1,1, 1,01) x x x
x
1 2
n 1 n
1 2
n 1 n
F (1,1, 0,1) x x x
x F (0,0, 0,0) x x x
x
1 2
n 1 n
1 2
n 1 n
(2.1)
которая составлена следующим образом: каждое слагаемое этой логической
суммы представляет собой конъюнкцию, в которой первый член является
значением функции F при некоторых определенных значениях переменных
x , x , x , остальные же члены конъюнкции представляют собой переменные
1 2
n
или их отрицания. При этом под знаком отрицания находятся те и только те
переменные, которые в первом члене конъюнкции имеют значение 0..
Вместе с тем формула (2.1) содержит в виде логических слагаемых
всевозможные конъюнкции указанного вида.
Ясно, что формула (2.1)полностью определяет функцию F ( x , x , x ) .
1 2
n
Иначе говоря, значения функции F и формулы (2.1) совпадают на всех наборах
значений переменных x , x , x . То есть функция
1 2
n
Составление формул по таблице истинности. F ( x , x , x ) может быть
1 2
n
представлена в виде:
F ( x , x , x ) F (1,1, 1,1) x x x
x F (1,1, 1,01) x x x
x
1 2
n
1 2
n 1 n
1 2
n 1 n
(2.2)
F (1,1, 0,1) x x x
x F (0,0, 0,0) x x x
x
1 2
n 1 n
1 2
n 1 n
20
ПРИМЕР
Пусть
функция
F (x , x , x )
1 2 3
имеет
следующую
таблицу
истинности:
x
1
x
1
1
1
1
1
1
1
1
1
x
1
F (x , x , x )
1 2
3
0 1
1 0
0 0
1 1
0 0
1 1
0 1
1 0
Тогда функция F ( x , x , x ) может быть определена в следующем виде:
1 2 3
F (x , x , x ) 1 x x x 0 x x x 0 x x x
1 2 3
1 2 3
1 2 3
1 2 3
1 x x x 0 x x x 1 x x x 1 x x x
1 2 3
1 2 3
1 2 3
1 2 3
0 x x x 1 x x x 1 x x x 1 x x x 1 x x x
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
x x x x x x x x x x x x
1 2 3 1 2 3 1 2 3 1 2 3
Нетрудно заметить, что для определении функции берутся только те наборы
переменных x , x , x , при которых функция принимает значения 1, что
1 2 3
значительно упрощает процедуру определения функции F .
Формула (2.1) обладает свойствами:
1. Каждое логическое слагаемое формулы содержит все переменные ,
входящие в функцию F ( x , x ,, x ) .
1 2
n
2. Все логические слагаемые формулы различны.
3. Ни одно логическое слагаемое формулы не содержит одновременно
переменную и ее отрицание.
4. Ни одно логическое слагаемое формулы не содержит одну и ту же
переменную дважды.
5. Перечисленные свойства называются свойствами совершенства.
Различные формы представления высказываний
Литерой называется элемент высказывания x или её отрицание.
Элементарной дизъюнкцией называется выражение следующего вида:
L L L ,
(2.2)
1
2
n
где L литера.
1
Элементарной конъюнкцией называется выражение следующего вида:
21
L L L ,
1 2
n
(2.3)
Дизъюнктивной нормальной формой (ДНФ) формулы A называется
выражение вида:
КНФ А K K K ,
(2.4)
1
2
n
где K элементарная конъюнкция.
1
Конъюнктивной нормальной формой (КНФ) формулы A называется
выражение вида:
ДНФ А D D D ,
(2.5)
1
2
n
где D элементарная дизъюнкция.
1
Любую формулу можно представить в виде ДНФ или КНФ.
ПРИМЕР
Пусть дана формула
A x y x y
Требуется получить ДНФ и КНФ данной формулы.
Применяя формулы равносильности, получаем КНФ A :
A x y xy ( x y ) x y ( x y ) x y ( x y ) ( x y ) x y x y
( x y) ( x y)
Применяя формулы равносильности, получаем ДНФ A :
A x y xy ( x y ) x y ( x y ) x y ( x y ) ( x y ) x y x y
( x y) ( x y) x x x y x y y y x y x y
Совершенной дизъюнктивной нормальной формой (СДНФ) формулы A
называется такая ДНФ, для которой выполняются следующие условия:
1. Все элементарные конъюнкции, входящие в ДНФ A , различны.
2. Все элементарные конъюнкции, входящие в ДНФ A , содержат
литеры, соответствующие всем переменным.
3. Каждая элементарная конъюнкция, входящая в ДНФ A , не содержит
двух одинаковых литер.
4. Каждая элементарная конъюнкция, входящая в ДНФ A , не содержит
переменную и ее отрицание.
СДНФ A можно получить двумя способами:
1. по таблице истинности;
2. с помощью равносильных преобразований.
Первый способ получения СДНФ A рассмотрен выше. Рассмотрим второй
способ, который состоит в следующем:
С помощью равносильных преобразований формулы A получают ДНФ A .
При этом в полученной ДНФ возможны следующие ситуации:
1. Элементарная конъюнкция B ДНФ A не содержит переменную x ,
i
тогда используются следующие равносильные преобразования:
22
B B1 B( x x ) Bx B x
i
i
i
i
2. Если в ДНФ A входят две одинаковые элементарные конъюнкции, то
используя следующее равносильное преобразование:
BB B,
одну элементарную конъюнкцию можно отбросить.
3. Если элементарная конъюнкция B ДНФ A содержит одновременно
переменную x и ее отрицание, то используя следующие
i
равносильные преобразования:
Bx x B0 0 ,
i i
эту элементарную конъюнкцию можно отбросить
4. Если элементарная конъюнкция B ДНФ A содержит дважды
x ,
переменную
то используя следующее равносильное
i
преобразование:
Bx x Bx ,
i i
i
одну переменную x можно отбросить
i
СДНФ формулы A существует в единственном виде.
ПРИМЕР
Получить СДНФ формулы A x y z
С помощью равносильных преобразований получаем СДНФ A :
A x y z x y z x( y y)( z z ) y z ( x x) x yz x y z x yz x y z xy z
x y z x yz x y z x yz x y z xy z
С помощью таблицы истинности получаем СДНФ A :
y
z
z
yz
A x yz
0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
x
СДНФ A x y z x yz x y z x yz xy z
Очевидно, что в результат двух способов совпадает.
Совершенной конъюнктивной нормальной формой (СКНФ) формулы A
называется такая КНФ, для которой выполняются следующие условия:
1. Все элементарные дизъюнкции, входящие в КНФ A , различны.
2. Все элементарные дизъюнкции, входящие в КНФ A , содержат
литеры, соответствующие всем переменным.
23
3. Каждая элементарная дизъюнкция, входящая в КНФ A , не содержит
двух одинаковых литер.
4. Каждая элементарная дизъюнкция, входящая в КНФ A , не содержит
переменную и ее отрицание.
СКНФ A можно получить двумя способами:
1. по таблице истинности;
2. с помощью равносильных преобразований.
По первому способу по таблице истинности получаем СДНФ A , а СКНФ A
можно получить, следуя следующему правилу
СКНФ А СДНФ А
С помощью равносильных преобразований формулы A получают КНФ A .
При этом в полученной КНФ возможны следующие ситуации:
1. Элементарная дизъюнкция B КНФ A не содержит переменную x ,
i
тогда используются следующие равносильные преобразования:
B B 0 B x x ( B x )( B x )
i i
i
i
2. Если в КНФ A входят две одинаковые элементарные дизъюнкции,
то используя следующее равносильное преобразование:
BB B ,
одну элементарную дизъюнкцию можно отбросить.
3. Если элементарная дизъюнкция B КНФ A содержит одновременно
переменную x и ее отрицание, то используя следующие
i
равносильные преобразования:
B x x B 1 1,
i
i
эту элементарную дизъюнкцию можно отбросить.
4. Если элементарная дизъюнкция B КНФ A содержит дважды
x ,
переменную
то используя следующее равносильное
i
преобразование:
B x x B x ,
i
i
i
одну переменную x можно отбросить.
i
СКНФ формулы A существует в единственном виде.
ПРИМЕР
Получить СКНФ формулы A x y z
С помощью равносильных преобразований получаем СКНФ A :
A x y z x y z ( x y )( x z ) ( x y z )( x y z )( x z y)( x z y)
( x y z )( x y z )( x y z )
24
С помощью таблицы истинности получаем СДНФ A :
y
z
z
yz
A x yz
A
0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
x
СДНФ A x y z x yz xyz
СКНФ А СДНФ A x y z x yz xyz ( x y z)( x y z)( x y z)
Очевидно, что в результат двух способов совпадает.
СДНФ формулы A можно получить из СКНФ A , используя следующее
правило:
СДНФ А СКНФ А
Выполнимость формулы алгебры логики
Все формулы алгебры логики делятся на три класс:
1. тождественно истинные или тавтологии:
2. тождественно ложные или противоречия;
3. выполнимые.
Формулу называют тождественно истинной (тавтологией), если она
принимает значение истинно при любых значениях входящих в нее переменных.
Формула называется тождественно ложной (противоречие), если она
принимает значение ложно при любых значениях переменных входящих в нее.
Формула A называется выполнимой, если она принимает значение истинно
хотя бы один раз на любом наборе значений входящих в нее переменных и не
является тождественно истинной..
Тождественно истинная формула не имеет СКНФ, а ложная СДНФ.
ПРИМЕР
Формула A x x является тождественно ложной:
x
x
A xx
1
1
Формула A x x является тождественно истинной:
x
x
A x x
1
1
1
1
25
Формула A x y является выполнимой:
x
y
A x y
0 0
0 1
1
1 0
1
1 1
1
Очевидно, что тождественно ложная формула не имеет СДНФ, а
тождественно истинная – СКНФ. Выполнимая формула алгебры логики имеет
СДНФ и СКНФ,
Применение математической логики.
С помощью алгебры логики можно:
решать логические задачи;
реализация технических устройств.
С помощью алгебры логики можно решать логические задачи. Суть
применения методов алгебры логики к решению логических задач состоит в том,
что, имея конкретные условия логической задачи, необходимо записать их в
виде формулы логики. В дальнейшем путем равносильных преобразований
упрощают полученную формулу. Простейший вид формулы, как правило,
приводит к ответу на все вопросы задачи.
ПРИМЕР
Определить, Был ли Смит убийцей, если известно следующее:
Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей,
либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой
ночью, и убийство имело место после полуночи. Если убийство было совершено
после полуночи, то либо Смит был убийцей, либо Джонс лжет.
Составим элементарные высказывания:
А – Джонс не встречал Смит этой ночью.
В – Смит был убийца.
С – Джонс лжет.
D – убийство было совершено после полуночи.
Тогда сложные высказывания можно записать на языке алгебры логики в
следующем виде:
Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей,
либо Джонс лжет. - A ( B C )
.Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и
убийство имело место после полуночи. - B AD
Если убийство было совершено после полуночи, то либо Смит был
убийцей, либо Джонс лжет. - D ( B C )
Вся картина преступления может быть представлена в виде формулы:
( A ( B C )) ( B AD) ( D ( B C ))
Упростим полученную формулу с помощью равносильных преобразований:
26
( A ( B C )) ( B AD ) ( D ( B C )) ( A B C )( B AD )( D B C )
( A B C )( B AD )( B C D) ( AB B ABD BC ACD )( B C D)
( B ACD )( B C D) B BC B D ABCD ACD B ACD
Ответ B ACD трактуется так: Либо Смит был убийцей, либо убийство
совершено после полуночи Джонс лжет, что видел Смита этой ночью. Последнее
сложное высказывание ( ACD ) по сути также определяет вину Смита, как и
прямое утверждение, что Смит был убийцей ( B ). Таким образом приговор
Смиту вынесен.
В техническом аспекте математическая логика применяется в технических
средствах автоматизации в виде релейно-контактных схем (РКС) и логических
элементов «и-не», «или-не».
РКС представляют собой переключатели, которые могут находиться либо
замкнутом состоянии (1) , либо в разомкнутом состоянии (0).
Логические элементы «и-не» осуществляют логическую функцию:
y x x x
1 2
n
Логические элементы «или-не» осуществляют логическую функцию:
y x x x
1
2
n
Нетрудно заметить, что суть и РКС, и логических элементов – это формулы
математической логики. Суть применения методов алгебры логики к
конструированию технических средств автоматизации на базе РКС технического
устройства, необходимо записать принцип его работы в виде формулы логики. В
дальнейшем путем равносильных преобразований упрощают полученную
формулу. Далее полученную формулу реализуют на базе РКС или логических
элементов.
Важным требованием при конструировании технических средств
автоматизации является минимальное количество базовых элементов(РКС,
логических элементов). Поэтому задача минимизации сложных высказываний
является особо актуальной.
Минимизация сложных высказываний.
Существует несколько способов минимизации сложных высказываний.
Рассмотрим самые распространенные:
метод Квайна;
карты Вейча;
минимизирующие карты.
Метод Квайна.
Алгоритм метода Квайна включает в себя следующие этапы:
1. Любая формула A приводится к СДНФ.
2. СДНФ приводится к сокращенной ДНФ (СкДНФ). При получении
СкДНФ используются следующие формулы равносильности:
27
а) Формула склеивания
AB A B A
б) Формула неполного склеивания
AB AB A AB AB
в) Формула поглощения
A AB A
Применяя все возможные процедуры склеивания, СДНФ приводится к
СкДНФ.
3. Минимальная форма формулы A (МДНФ A ) получается на основе
импликантной матрицы путем нахождения минимального покрытия этой
матрицы. Импликанта – это элементарная конъюнкция СкДНФ.
Конституента единицы – это
элементарная конъюнкция СДНФ.
Импликантная матрица – это матрица импликант и констиуент единиц.
(столбцы - конституенты единицы, строки – импликанты). МДНФ может быть
несколько.
ПРИМЕР.
Необходимо найти МДНФ формулы:
X Y Z X Y Z X YZ X Y Z XY Z XYZ
1
2
3
4
Осуществляем всевозможные склеивания
1-2 X Y Z X Y Z X Y
1-4 Y Z
2-3 X Z
3-6 YZ
4-5 X Z
5-6 XY
СкДНФ имеет вид:
5
6
X Y Y Z X Z YZ X Z XY
Составляем импликантную матрицу
XY Z
X YZ
XY
+
+
YZ
XZ
YZ
XZ
XY
+
X YZ
XY Z
XY Z
XYZ
+
+
+
+
+
+
+
+
+
По данной импликантной матрице можно выбрать следующие МДНФ
X Y YZ X Z
Y Z X Z XY
28
Метод минимизирующих карт.
Алгоритм метода минимизирующих карт включает в себя следующие этапы:
1. Любая формула приводится к СДНФ.
2. Составляется таблица всевозможных сочетаний переменных.
3. Из таблицы вычеркиваются те строки, которые не содержат конституенты
СДНФ. Конъюнкции этих строк вычеркиваются в других строках.
4. В каждой строке оставляются конъюнкции с минимальным количеством
переменных.
5. Из каждой строки выбирается олна конъюнкция и составляется ДНФ.
6. Из построенных ДНФ выбирается минимальная.
ПРИМЕР
Дана СДНФ
X Y Z X Y Z XYZ X Y Z XY Z XYZ
X
X
X
X
X
X
X
X
Y
Y
Y
Y
Y
Y
Y
Y
Z
Z
Z
Z
Z
Z
Z
Z
XY
XY
XY
XY
XY
XY
XY
XY
XZ
XZ
XZ
XZ
XZ
XZ
XZ
XZ
YZ
YZ
YZ
YZ
YZ
YZ
YZ
YZ
XYZ
XY Z
X YZ
XY Z
X YZ
XY Z
X YZ
XY Z
*
*
* - помечены строки, не содержащие конституенты СДНФ.
После соответствующих преобразований получаем следующую таблицу
XY
XY
YZ
XZ
*
XZ
XZ
YZ
YZ
*
XY
XY
XZ
YZ
После всевозможного перебора остаются следующие МДНФ:
X Y YZ X Z
Y Z X Z XY
Метод минимизации с помощью карт Вейча.
Алгоритм метода карт Вейча включает в себя следующие этапы:
29
1. Любая формула приводится к СДНФ.
2. Составляется карта Вейча. Карта Вейча – это таблица всех возможных
комбинаций значений переменных. В соответствующие ячейки заносятся
единицы, соответствующие конституентам СДНФ.
3. Единицы, стоящие по вертикали и горизонтали, объединяются (по 2 , по 4
. по 8 и т.д.). Объединение единиц соответствует операциям склеивания и
поглощения. Иначе говоря, формируются максимальные подкубы.
4. Для каждого объединения выписываются конъюнкции из элементов,
общих для каждой единицы, входящих в объединение..
5. Выше полученные конъюнкции составляют МДНФ.
Карты Вейча удобны при поиске МДНФ функций двух, трех и четырех
переменных.
n=2
СДНФ= XY X Y X Y
X
X
1
1
Y
Y
1
МДНФ= X Y
n=3
СДНФ= XYZ XY Z X Y Z X Y Z
X
1
X
1
1
Z
Y
Y
1
Z
Z
МДНФ= XY Y Z
n=4
СДНФ= XYZT XY ZT X Y ZT X YZT X Y Z T X Y ZT X Y ZT XY ZT
X
X
1
T
1
1
1
Y
1
1
T
1
Y
1
T
Z
Z
Z
30
МДНФ= YT X T XY Z X Y Z T
Булевые функции и их свойства.
Булевой функцией называется функция n переменных, которая принимает
значение 1 или 0, а так же ее аргументы тоже принимают значение 1 или 0.
Булевая функция имеет следующие свойства:
1. Свойство сохранения нуля T . Булевая функция сохраняет нуль, если
функция при нулевых значениях аргумента принимает значение нуль.
2. Свойство сохранения единицы T . Булевая функция сохраняет единицу,
1
если функция при единичных значениях аргумента принимает значение
единица.
ПРИМЕР
Логическая операция – дизъюнкция F x y обладает и свойством
сохранения нуля ( F (0,0) x y 0 ), и свойством сохранения единицы
( F (1,1) x y 1 )
3. Линейность L . Функция является линейной, если её можно представить
в виде:
F ( x , x , , x ) a a x a x
1 2
n
11
n n
где a - булевая переменная
i
ПРИМЕР
Эквивалентность является линейной функцией:
x y 1 1 x 1 y 1 x y
4. Монотонность M . Функция является монотонной, если для любых
произвольных наборов и выполняются следующие неравенства:
F ( ) F ( )
5. Самодвойственность S . Функция называется самодвойственной, если
она равна двойственной ей функции.
Двойственной функцией называется функция:
F * ( x , x ,, x ) F ( x , x ,, x )
1 2
2
1 2
2
Тогда свойство самодвойственности может представлено:
F ( x , x ,, x ) F * ( x , x ,, x )
1 2
2
1 2
2
ПРИМЕР
Отрицание является самодвойственной функцией:
F ( x) F * ( x) x x x
31
Функциональная полнота. Теорема Поста.
Функциональный набор логических функций это такой набор функций,
который позволяет любую функцию математической логики описать с помощью
функций данного набора.
Теорема Поста. Для того чтобы набор функций {f1,f2,……fn} был
функционально полный необходимо и достаточно, чтобы для всего набора
функций в целом не выполнялись свойства сохранения нуля, сохранения
единицы, линейности, монотонности и самодвойственности.
Полноту набора удобно определять по таблице Поста, в клетках которой
ставится знак «+» или «-» в зависимости от того, обладает функция из этого
набора тем или иным свойством. В силу теоремы Поста для полноты системы
необходимо и достаточно, чтобы в каждом столбце был хотя бы один минус.
{ }
F1
F2
T0
+
T1
+
L
+
M
+
S
+
ПРИМЕР
Доказать, что набор функций6 дизъюнкция и отрицание является
функционально полным.
V
T0
+
T1
+
L
+
M
+
S
+
Логика предикат.
Предикат это сложное высказывание, в котором аргументы ( x , x ,, x )
1 2
n
принимают значение из некоторой вещественной области D , а значение самого
высказывания принимает значение истинно или ложно.
P( x , x ,, x )
1 2
n
xi D
P ( x , x , , x ) {0,1}
1 2
n
ПРИМЕР
Предикатом является высказывание – быть четным числом на множестве
натуральных чисел:
P (x ) - быть четным числом;
32
x N {1,2,3}
P( x) {0,1)
P(5) 0
p(10 ) 1
Предикаты
могут
быть
одноместные
и
P ( x, y ) ( x D , y D )
1
2
P ( x , x , , x ) ( x D , x D , , x D )
1 2
n
1
1 2
2
n
n
P (x ) , двухместные
многоместные
-
Логические операции над предикатами.
Для предикатов выполнимы следующие операции:
Конъюнкция P( x) Q( x) - это новый предикат, который принимает значение
истинно при тех и только тех значениях x из вещественной области D , при
которых оба предиката P (x) и Q(x) истинны одновременно, и ложно во всех
других случаях.
Дизъюнкция P( x) Q( x) - это новый предикат, который принимает
значение ложно при тех и только тех значениях x из вещественной области D ,
при которых оба предиката P (x) и Q(x) ложны одновременно, и истинно во всех
других случаях.
Отрицание предиката P(x) - это новый предикат, который принимает
значение истинно при всех x из вещественной области D , при которых
предикат P (x) принимает значение ложно и наоборот.
Квантовые операции.
Для предикатов кроме логических операций применимы кванторные
операции: всеобщности и существования.
Пусть P (x) - предикат, определенный на множестве D . Тогда xP(x) означает «для всякого (любого) x истинно P (x) ». Символ называется
квантором всеобщности.
Переменную x в предикате P (x) называют свободной ( ей можно
придавать различные значения из М), в высказывании xP(x) переменную
x называют связанной квантором всеобщности.
Пусть P (x) - предикат, определенный на множестве D . Тогда xP(x) означает «существует x , для которого истинно P (x) ». Символ называется
квантором существования.
ПРИМЕР
Пусть на множестве натуральных чисел задан предикат P (x) -«число x
кратно 3». Используя кванторы, из данного предиката можно получить
высказывания:
xP(x) - «все натуральные числа кратны 3»;
33
xP(x) - «существуют натуральные числа, кратные 3».
Очевидно, что первое из данных высказываний ложно, а второе – истинно.
Кванторные операции применяются и к многоместным предикатам. Пусть
на множестве D задан двухместный предикат P( x, y ) . К данному предикату
могут применяться кванторные операции как по одной, так и по двум
переменным.
ПРИМЕР
Пусть предикат P( x, y ) означает x делится на y без остатка., причем обе
переменные определены на множестве натуральных чисел. Тогда применение
кванторных операций приводит к следующим высказываниям:
1. xyP( x, y ) - «для любого x и для любого y справедливо, что x
делится на y без остатка.
2. xyP( x, y ) - «для любого x существует y , который является
делителем x без остатка.
Нетрудно заметить, что первое высказывание является ложным, а второе –
истинным.
Для многоместных предикатов, связанных по одной переменной
справедливы следующие формулы:
x P( x , x ,, x ) P( , x ,, x ) P( , x ,, x ) P( , x ,, x ) ,
1
1 2
n
1 2
n
2 2
n
m 2
n
где x { , , }
1
1 2
m
x P( x , x ,, x ) P( , x ,, x ) P( , x ,, x ) P( , x ,, x ) ,
1 1 2
n
1 2
n
2 2
n
m 2
n
где x { , , }
1
1 2
m
Равносильные формулы логики предикатов.
Две формулы логики предикатов A и B называются равносильными на
области D , если они принимают одинаковые логические значения при всех
значениях входящих в них переменных, отнесенных к области D .
Две формулы логики предикатов A и B называются равносильными, если
они равносильны во всякой области.
Очевидно, что все формулы равносильности алгебры высказываний будут
верны, если в них вместо переменных подставить формулы логики предикатов.
Но , кроме того, имеют место равносильности самой логики предикатов:
Закон де Моргана:
1. xA( x) x A( x)
2. xA( x) x A( x)
Закон двойного отрицания:
3. xA( x) x A( x)
4. xA( x) x A( x)
5. xA( x) xB( x) x[ A( x) B( x)]
34
6. xA( x) xB( x) x[ A( x) B( x)]
7. xA( x) yB( y ) xy[ A( x) B( x)]
Для произвольного высказывания C (предиката, не связанного по
переменной x ) справедливы следующие формулы равносильности:
8. C xA( x) x[C A( x)]
9. C xA( x) x[C A( x)]
10. C xA( x) x[C A( x)]
11. C xA( x) x[C A( x)]
12. xC C
13. xC C
Формулы замены переменных (где x и y из одной предметной области):
xA( x) yA( y )
14.
15. xA( x) yA( y )
Предваренная нормальная форма предиката
Формула предиката имеет нормальную форму, если она содержит только
операции конъюнкции, дизъюнкции, и кванторные операции, а операция
отрицания отнесена к элементарному предикату.
ПРИМЕР
Пусть дан предикат (xP( x) yQ( y )) R( z ) . Привести данный предикат к
нормальной форме
(xP( x) yQ( y )) R ( z ) (xP( x) yQ( y )) R ( z )
(xP( x) yQ( y )) R ( z ) xP( x) yQ( y ) R ( z )
xP( x) yQ ( y ) R ( z )
Предварённой нормальной формой предиката называется такая
нормальная форма предиката, в которой кванторные операторы либо
отсутствуют, либо используются после операций алгебры логики.
ПРИМЕР
Привести предикат из предыдущего примера к предваренной нормальной
форме предиката
xP( x) yQ( y) R( z ) xy( P( x) yQ( y)) R( z )
xy( P( x) Q( y) R( z ))
35
ТЕОРИЯ ГРАФОВ
Начало теории графов как математической дисциплине было положено
Леонардом Эйлером в его знаменитом решении задачи о Кенигсбергских мостах
в 1736 году. План города Кенигсберга представлен на рис. 3.1. Задача о
Кенигсбергских мостах сводилась к тому, чтобы построить маршрут своей
воскресной прогулки так, чтобы, начиная в любой точке суши (A, B, C или D)
пройти по всем мостам строго по одному разу и вернуться в исходную точку
(начало маршрута).
A
С
D
B
Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах.
Такую задачу не предоставляется возможным решить классическими
методами математики. Для решения такой задачи был предложен качественно
новый аппарат – аппарат теории графов.
Основные понятия теории графов
Графом называется пара следующего вида:
G Г , X ,
(3.1)
где Г - график Г X X ;
X - множество вершин.
Иными словами, граф представляет совокупность множества вершин и дуг.
1
x1
7
x6
2
6
x5
3
x2
x3
5Рис. 3.2. αГраф
4
x4
36
Граф, представленный на рис. 3. 2, состоит из множества вершин
X {x , x , x , x , x , x } и множество дуг { , , , , , , }
1 2 3 4 5 6
1
2
3
4
5
6
7
Графическое изображение графа является самым наглядным, но не
единственным способом задания графа. Кроме того граф может быть задан:
1.
перечислением:
{ x , x , x , x , x , x , x , x , x , x , x , x , x , x }
1 1
1 2
1 6
3 1
3 4
4 5
5 1
множеством образов:
2.
{x , x , x }
x
1 2 6
1
Г
x
2
Г
{x , x }
x
1 4
3
,
Г
{x }
x
5
4
Г
{x }
x
1
5
Г
x
6
где Г - образ вершины x - множество вершин, в которые исходят дуги из
x
i
i
Г
данной вершины.
3.
матрицей инцидентности
Матрица инцидентности - это матрица вершин и инцидентных им дуг.
Дуга инцидентна вершине, если эта дуга исходит или заходит в данную
вершину.
Вершина инцидентна дуге, если в эту вершину заходит или исходит
данная дуга.
В матрице инцидентности в первом столбце расположены вершины, в
первой строке – дуги. Остальные ячейки матрицы инцидентности заполняются
по следующему правилу:
1 , если из i-той вершины исходит j-тая дуга:
ij
ij
ij
ij
1 , если в i-той вершину заходит j-тая дуга;
0 , если i-тая вершина не инцидента j-той дуге;
2 , если из i-той вершины исходит j-тая дуга и в нее же заходит, т.е.
в i-той вершине j-тая дуга образует петлю.
Для графа, представленного на рис. 3.2 матрица инцидентности имеет вид:
37
x
1
x
2
x
3
x
4
x
5
x
6
1
2
3
4
5
6
7
2
-1
+1
+1
-1
+1
-1
-1
+1
-1
+1
-1
+1
На практике в матрице инцидентности иногда нули не проставляются для
наглядности.
x
1
x
2
x
3
x
4
x
5
x
6
1
2
2
-1
3
4
5
+1
6
+1
7
-1
+1
-1
-1
+1
-1
+1
-1
+1
Свойство матрицы инцидентности – сумма элементов по столбцам равна 0
или 2.
4.
матрицей смежности
Смежные дуги – это дуги инцидентные одной вершине.
Смежные вершины – вершины, инцидентные одной дуге.
Матрица смежности - это матрица смежных вершин.
Матрица смежности заполняется по следующему правилу: 1 , если из iij
той вершины исходит дуга в j – тую вершину; во всех остальных случаях
ij
0
(для удобства и наглядности на практике в матрице смежности нули не
проставляются).
Для графа, представленного на рис. 3.2 матрица смежности имеет вид:
38
x
1
x
1
1
x
1
x
2
x
3
x
4
x
5
x
6
2
1
x
3
x
4
x
5
x
6
1
1
1
1
Полустепенью захода ( x ) i–той вершины называется число дуг,
заходящих в данную вершину.
i
Полустепенью исхода ( x ) i-той вершины называется число дуг,
i
исходящих из данной вершины.
Степенью i-той вершины исхода ( x ) называется сумма полустепеней
i
захода и исхода:
(x ) (x ) (x )
i
i
i
(3.2)
Свойства матрицы смежности:
1. Сумма единиц по строке определяет полустепень исхода;
2. Сумма единиц по столбцу определяет полустепень захода;
3. Сумма единиц по строкам и по столбцам определяет степень вершин.
Основное свойство графа:
В любых графах число вершин с нечетной степенью четно.
Путем в графе называется последовательность дуг такая, что каждая
следующая дуга исходит из вершины, в которую заходит предыдущая дуга.
Длиной пути называется количество пройденных дуг.
Простой путь – это такой путь, в котором дуга встречается не более
одного раза.
Элементарный путь – это путь, в котором вершина встречается не более
одного раза.
Контур – путь, начинающийся и заканчивающийся в одной точке.
Петля – контур длиной в одну единицу.
Графы бывают двух видов:
ориентированный граф (орграф) - это граф, состоящий из вершин и дуг.
неориентированный граф – это граф, состоящий из вершин и ребер.
Ребро – это дуга, не имеющая направление.
39
2
II
I
1
III
VI
V
5
VII
3
IV
4
Рис. 3.3. Неориентированный граф
В неориентированном графе путь называется цепью; контур – циклом.
Неориентированный граф также может быть задан с помощью матриц
инцидентности и смежности.
Матрица инцидентности для неориентированного графа составляется по
правилу:
1 , если i-тая вершина инцидентна j-тому ребру;
ij
ij
ij
0 , если i-тая вершина не инцидента j-тому ребру;
2 , если. в i-той вершине j-тое ребро образует петлю.
Для графа, представленного на рис. 3.3, матрица инцидентности имеет вид:
I II III IV V VI VII
1
1 1
1 1
2 1 1
3 1
1 1
4
1 1
1
5
1
1
Матрица смежности для неориентированного графа составляется по
правилу: 1 , если из i-тая и j – тая вершины смежные.
ij
Для графа, представленного на рис. 3.3, матрица смежности имеет вид:
1 2 3 4 5
1 1 1 1 1 1
2 1 1
3 1 1
1
4 1
1
1
5 1
1
Матрица смежности для неориентированного графа симметрична
относительно главной диагонали. Степень i- той вершины равна сумме
элементов по строке или по столбцу матрицы смежности.
Если в графе присутствуют как ребра, так и дуги, то он называется
смешанным.
40
Если между двумя вершинами существует более чем 1 дуга или ребро, то
такой граф называется мультиграфом.
Рис. 3.4. Смешанный мультиграф.
Граф называется связным, если между любыми двумя вершинами которого
существует путь (цепь).
Эйлеров граф.
Эйлеровой цепью называется цепь, проходящая по всем ребрам графа.
Эйлеровым циклом называется эйлеровая цепь, начинающаяся
заканчивающаяся в одной вершине.
Эйлеровым графом называется граф, содержащий Эйлеров цикл.
и
ТЕОРЕМА: Для того чтобы связанный граф был Эйлеровым, необходимо
и достаточно, чтобы степени всех вершин были четны
Данная теорема позволяет решить задачу о Кенигсбергских мостах. Граф,
соответствующий данной задаче, имеет вид
А
С
D
B
Рис. 3.5 Граф «Кенигсбергские мосты»
Вершины графа (A, B, C, D) имеют степени:
3
A
B
C
D
3
5
3
(3.3)
41
Тогда в соответствии с теоремой Эйлера данный граф не является
Эйлеровым. А это означает, что нельзя обойти все мосты г. Кенигсберга строго
по одному разу, начав и закончив путь в одной точке суши.
Следствие из ТЕОРЕМЫ: Для того чтобы граф содержал Эйлеровую
цепь, необходимо и достаточно, чтобы две вершины имели нечетную степень.
При этом в одной из вершин цепь будет начинаться, в другой – заканчиваться.
Множество внутренней устойчивости графа
Множество внутренней устойчивости графа – это множество
несмежных вершин.
Пусть дан граф G Г , X . Тогда для множества
внутренней
устойчивости X ' справедливо следующее:
X ' X
X ' Г
X'
(3.4)
Максимальным множеством внутренней устойчивости называется
внутренне устойчивое множество, добавление любой вершины к которому,
делает это множество неустойчивым.
ПРИМЕР
Дан граф
B
A
C
D
E
Рис. 3.6 Граф
Данный граф имеет следующие множества внутренней устойчивости.
{ A, E}, {B, D}, {B, E}, {C , D}, {C , E}
Рассмотрим множество { A, E} . Добавляя к нему любую вершину, получаем
множества внутренне неустойчивые: { A, E , B}, { A, E , C}, { A, E , D} . Следовательно,
множество { A, E} является максимальным множеством внутренней устойчивости.
Числом внутренней устойчивости (α) называется число, равное
наибольшей мощности максимального внутренне устойчивого множества.
Очевидно, что поиск максимальных внутренне устойчивых множеств путем
простого перебора является неэффективной процедурой, поэтому для поиска
максимальных внутренне устойчивых множеств существует специальный
алгоритм – алгоритм Магу.
42
Алгоритм Магу для определения множества внутренней устойчивости
графа
Пусть дан граф G Г , X . Для данного графа существует множество
внутренней устойчивости X ' .
Введем булевую переменную x , которая определяется следующим
i
образом:
x 1 , если вершина x принадлежит множеству внутренней устойчивости
i
i
x X ';
i
x 0 , если вершина x
не принадлежит множеству внутренней
i
i
устойчивости x X ' ;
i
Введем булевую переменную :
ij
1 , если между i-той и j-той вершиной есть дуга;
ij
0 , если между i-той и j-той вершиной нет дуги.
ij
Тогда определение внутренней
представлено в следующем виде:
устойчивости
(3.4)
i, j ( x X ' , x G( x )) x X '
i
j
i
j
может
(3.5)
Или используя булевую алгебру:
i, j ( ( x & ) x ) 1
i
ij
j
(3.6)
Применяя формулы равносильности, преобразуем:
n n
i, j ( ( x & ) x ) & & ( ( x & ) x )
i
ij
j
ij
j
i 1 j 1 i
n n
n n
& & ( (x & ) x ) & & (x x ) 1
ij
j
ij
j
i 1 j 1 i
i 1 j 1 i
(3.7)
Рассмотрим выражение:
n n
& & (x x ) 1
ij
j
i 1 j 1 i
Если 0 , то данное равенство является тавтологией.
ij
Если 1 , то равенство имеет вид:
ij
& (x x ) 1
j
ij
1 i
Данное уравнение лежит в основе алгоритма Магу
Алгоритм Магу состоит из следующих этапов:
(3.8)
(3.9)
быть
43
1.
2.
3.
4.
Для графа составляется матрица смежности.
По таблице смежности выписываются все парные дизъюнкции.
Выражение приводится к ДНФ.
Для любой элементарной конъюнкции выписываются недостающие
элементы, которые и образуют множество внутренней устойчивости.
ПРИМЕР
Дан граф
X1
X2
X4
Рис. 3.7 Граф
X3
Матрица смежности имеет вид:
x
1
x
1
x
2
x
3
x
4
x
2
1
x
1
3
x
4
1
1
1
1
Для всех единиц выписываются парные дизъюнкции:
( x x )( x x )( x x )( x x )( x x )( x x )
1
2 1
3 1
4 2
1 3
1 4
3
(3.10)
Приведем выражение к ДНФ:
( x x )( x x )( x x )( x x )( x x )( x x )
1
2 1
3 1
4 2
1 3 1 4
3
( x x )( x x )( x x )( x x )
1
2 1
3 1
4 4
3
( x x x )( x x x )
1
2 3 4
1 3
x x x x x x x x x x
1 4
1 3
2 3 4
1 2 3
x x x x x x x
1 4
1 3
2 3 4
Множества внутренней устойчивости:
{x , x }, {x , x }, {x }
2 3
2 4
1
Числом внутренней устойчивости = 2.
(3.11)
44
Множество внешней устойчивости графа
Множество внешней устойчивости – множество вершин, для которых
выполняется одно из следующих правил:
1). Любая вершина входит в это множество
2) Либо вершина не входит в это множество, но из этой вершины есть дуга
в данное множество.
Пусть дан граф G Г , X . Тогда для множества внешней устойчивости
X ' справедливо следующее:
x X "
i
X " Г
X"
(3.12)
Число внешней устойчивости (β) – это наименьшая мощность из всех
множеств внешней устойчивости.
Алгоритм Магу для определения множества внешней устойчивости.
Пусть дан граф G Г , X . Для данного графа существует множество
внешней устойчивости X " .
Вводятся булевые переменные x и по тому же правилу, что и для
i
ij
алгоритма Магу для определения множества внутренней устойчивости.
Тогда определение множества внешней устойчивости (3.12) запишется
следующим образом:
n
n
& (x & x ) 1
i j 1 ij
j
i 1
Для 1 справедливо следующее
ij
n
& (x x ) 1
i 1 j
ij
i 1
(3.13)
(3.14)
Данное уравнение лежит в основе алгоритма Магу
Алгоритм Магу состоит из следующих этапов:
1. Для графа составляется матрица смежности
2. Матрица смежности дополняется единицами (1) по главной диагонали.
3. Для каждой строки выписываются дизъюнкции.
4. Выражение приводится к ДНФ.
5. Все вершины, входящие в элементарную конъюнкцию, образуют
множество внешней устойчивости
ПРИМЕР
Определить множество внешней устойчивости для графа, представленного
на рис. 3.7.
Матрица смежности имеет вид:
45
x
1
x
1
x
2
x
3
x
4
x
2
1
x
3
1
x
4
1
1
1
1
Дополним матрицу смежности единицами по главной диагонали
x
1
x
2
x
3
x
4
x
1
x
1
1
1
1
2
1
x
1
3
x
4
1
1
1
1
Для каждой строки выписываются дизъюнкции:
( x x x x )( x x )( x x )( x x )
1
2
3
4 1
2 1
3 3
4
(3.15)
Приведем выражение к ДНФ:
( x x x x )( x x )( x x )( x x )
1
2
3
4 1
2 1
3 3
4
( x x )( x x )( x x ) ( x x x )( x x )
1
2 1
3 3
4
1
2 3 3
4
x x x x x x x x x x x x x x x
1 3
1 4
2 3
2 3 4
1 3 1 4
2 3
(3.16)
Множества внутренней устойчивости:
{x , x }, {x , x }, {x , x }
1 3
1 4
2 3
Числом внешней устойчивости = 2.
Ядром графа
называется подмножество
одновременно внутренней и внешней устойчивостью.
вершин,
являющихся
Граф, представленный на рис. 3.7. имеет ядро {x , x }
2 3
Множество путей в графе
По матрице смежности можно определить, сколько различных путей
существует между i-той и j- той вершинами длиной в к единиц. Для этого
необходимо определить матрицу M k , где M - матрица смежности.
Если элемент a матрицы M k :
ij
46
a 0 - между i-той и j- той вершины не существует пути длиной в к
ij
единиц;
a n - между i-той и j- той вершины существуют n различных путей
ij
длиной в к единиц;
Если M k - нулевая матрица, это означает, что графе нет путей в к единиц,
а максимальный путь – это путь длиной в (к -1) единиц.
Алгоритм фронта волны. Поиск минимального пути в графе.
Одной из самых распространенных задач в теории графов является задача
поиска минимального пути в графе.
Рассмотрим некоторые свойства минимальных путей
1. Любой минимальный путь является простым путем.
x x x
2. Если путь
- минимальный, то любые пути
1 2
k
xx
x (1 i j k ) внутри
i i 1
j
минимального
пути
также
будут
минимальны.
Пусть Г-1х – прообраз вершины xi – это множество вершин, из которых
исходят дуги в вершину xi.
Одним из алгоритмов поиска минимального пути в графе является алгоритм
фронта волны (FW –Front Wave)
Алгоритм фронта волны.
Пусть необходимо найти минимальный путь из вершины x в вершину x .
i
1. Выписываются все вершины с 1 по n. Вершина
j
помечается индексом
x
i
0.
2. Находится первый фронт волны FW ( x ) как множество вершин образа
1 i
вершины x .
i
FW ( x ) Г
1 i
x
i
(3.17)
3. Все вершины, принадлежащие первому фронту волны, помечаются
индексом 1.
4. Вводится счетчик шагов (фронтов волны) k 1 .
5. Если FW ( x ) или k n 1 , то вершина x недостижима из
k
i
j
вершины, и работа алгоритма на этом заканчивается. В противном смысле
переходим к пункту 6.
6. Если x FW ( x ) , то переходим к пункту 8. В противном случае
j
k
i
существует путь из вершины x в вершину x длиной в k единиц, и этот путь
i
минимальный:
j
47
x z z z
x
i 1 2
k 1 j
7. Находятся промежуточные вершины z , z ,, z
z по правилу:
1 2
k 1
z
FW
(x ) Г 1
k 1
k 1 i
x
j
z
FW
(x ) Г 1
k 2
k 2 i
z
(3.18)
k 1 ,
z FW ( x ) Г 1
1
1 i
z
2
1
где Г - прообраз вершины x - множество вершин, из которых заходят
x
дуги в вершину x
8. Определяется k 1 фронт волны как все непомеченные вершины,
принадлежащие образу вершин k - го фронта волны. Помечаются индексом k 1
вершины k 1 фронта волны. Далее осуществляется переход к пункту 5.
ПРИМЕР
Пусть задан граф матрицей смежности:
x
1
x
1
x
2
x
3
x
4
x
5
x
6
x
2
x
3
1
1
1
x
4
x
5
x
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Необходимо найти минимальный путь из вершины x в вершину x
1
алгоритму «фронта волны»).
1. Выпишем все вершины. Вершина x помечается индексом «0»
1
x x x x x x
1 2 3 4 5 6
2. Находится первый фронт волны:
FW ( x ) Г {x , x }
1 1
x
4 5
1
6
(по
48
3. Все вершины, принадлежащие первому фронту волны, помечаются
индексом «1».
1
1
x x x x x x
1 2 3 4 5 6
4. Так как FW ( x ) , k 1 n 1 6 1 5 и x FW ( x ) , то определяем
1 1
6
1 1
второй фронт волны:
FW ( x ) ( Г
Г ) \ {x , x , x }
2 1
x
x
1 4 5
4
5
({x , x , x } {x , x , x , x }) \ {x , x , x } {x , x }
4 3 5
1 2 3 4
1 4 5
2 3
5. Все вершины, принадлежащие второму фронту волны, помечаются
индексом «2».
2
2
1
1
x x x x x x
1 2 3 4 5 6
6. Так как FW ( x ) , k 2 n 1 6 1 5 и x FW ( x ) , то определяем
2 1
6
2 1
третий фронт волны:
FW ( x ) ( Г
Г ) \ {x , x , x , x , x }
3 1
x
x
1 2 3 4 5
2
3
({x , x , x , x } {x , x , x , x , x }) \ {x , x , x , x , x }
1 4 5 6
1 2 4 5 6
1 2 3 4 5
{x }
6
7. Так как x FW ( x ) , то существует путь из вершины x в вершину x
6
3 1
6
1
длиной 3 единицы:
x z z x
11 2 6
8. Находятся промежуточные вершины z , z :
1 2
z FW ( x ) Г 1 {x , x } {x , x } {x , x }
2
2 1
x
2 3
2 3
2 3
6
Выберем z x
2
3
z FW ( x ) Г 1 {x , x } {x , x , x } {x , x }
1
1 1
x
4 5
4 5 6
4 5
3
Выберем z x
1
5
Таким образом, минимальный путь из вершины x в вершину x имеет
6
1
вид:
x x x x
1 3 5 6
Ярусно-параллельная форма графов
Граф, не имеющий контуров, может быть представлен в яруснопараллельной форме. Ярусно-параллельная форма – это такой вид графа, у
которого в верхний нулевой ярус помещены вершины, имеющие только
49
исходящие дуги; в нижний ярус помещены вершины, имеющие только входящие
дуги. На k-том ярусе помещены вершины, которые имеют входящие дуги из
предыдущих ярусов, среди которых хотя бы одна дуга из (k-1)-того яруса.
Количество вершин в ярусе определяет ширину яруса. Наибольшая ширина
яруса определяет ширину графа в ярусно-параллельной форме. Количество
ярусов определяет высоту графа в ярусно-параллельной форме.
Алгоритм приведения графа к ярусно-параллельной форме.
1. Составляется матрица смежности графа.
2. Матрица смежности просматривается в поисках нулевых столбцов.
Вершины, которым соответствуют нулевые столбцы, помещаются в
нулевой ярус.
3. Из матрицы смежности столбцы и строки, соответствующие вершинам
нулевого яруса.
4. Повторяется п.2 данного алгоритма до тех пор, пока не будут охвачены
все вершины.
5. По исходной матрице смежности восстанавливаются дуги между
вершинами.
ПРИМЕР
Привести граф к ярусно-параллельной форме.
1
3
2
4
5
6
7
8
Рис. 3.8 Граф
1. Матрица смежности имеет вид:
1
1
2
3
4
5
6
7
8
2
1
3
4
5
1
1
6
1
7
1
1
1
1
1
8
50
2. В нулевой ярус помещаются вершины 3 и 8.
3. Из матрицы смежности вычеркиваются
соответствующие вершинам 3 и 8:
1
1
2
4
5
6
7
2
1
4
5
6
1
строки
и
столбцы,
строки
и
столбцы,
строка
и
столбец,
7
1
1
1
4. В первый ярус помещаются вершины 4 и 5.
5. Из матрицы смежности вычеркиваются
соответствующие вершинам 4 и 5:
1
2
1
1
2
6
7
6
1
7
1
6. Во второй ярус помещается вершина 1.
7. Из матрицы смежности вычеркиваются
соответствующие вершине 1:
2
6
7
2
6
7
8. В третий (последний) ярус помещаются вершины 2,6 и 7.
Таким образом, граф может быть представлен в ярусно-параллельной
форме:
8
3
4
5
1
2
6
7
Рис. 3.9 Граф
Высота графа - 4 яруса; ширина -3.
51
Деревья и леса
Отделенными называются вершины, для которых не существует
соединяющего эти вершины пути.
Неотделенными называются вершины, между которыми существует путь.
Подграфом графа G Г , X называется граф вида:
Г , A
A
A
A X Г Г
A
G
(3.19)
Компонентой связности называется подграф, порождаемый множество
неотделенных вершин.
ПРИМЕР
На рис. 3.10 представлен граф, имеющий две компоненты связности
{1,2,3,4} и {5.6}
1
2
5
3
4
6
Рис. 3.10 Граф
Связанным графом называется граф, имеющий одну компоненту
связности.
Дерево – связный неориентированный граф, в котором отсутствует цикл.
На рис. 3.11 представлены графы- деревья.
Рис. 3.11 Граф
Лесом называется граф, имеющий несколько компонентов связности,
причем каждая из компонент является деревом.
Цикломатическим числом () графа называется минимальное количество
ребер, которое необходимо изъять из графа, чтобы он стал деревом.
Цикломатическое число определяется по формуле:
N (k 1) ,
(3.20)
где N – количество ребер,
k – количество вершин.
52
Алгоритм получения дерева из графа
1. Выбирается любая вершина. Счетчик i принимаем равным 1 (i=1).
2. Если i = k, то дерево построено.
3. Если i k, то выбирается любая незадействованная вершина и ребро,
соединяющее данную вершину с любой из выбранных.
4. Счетчик увеличивается на единицу.(i= i+1).
5. Переход на пункт 2.
ПРИМЕР
Преобразовать граф, представленный на рис. 3.12 в дерево:
3
2
5
4
1
Рис. 3.12
1. Найдем цикломатическое число N (k 1) 8 (5 1) 4 ,
необходимо изъять 4 ребра.
2. Выбираем вершину 5. i 1
3. Присоединяем вершину 3.
4. i i 1 2
5. Присоединяем вершину 4.
6. i i 1 3
7. Присоединяем вершину 1.
8. i i 1 4
9. Присоединяем вершину 2.
10. i i 1 5
11. Все вершины охвачены. Дерево построено
5
3
4
1
2
Рис. 3.13
т.е.
53
ТЕОРИЯ АЛГОРИТМОВ
Алгоритм – это точное, понятное предписание о том, какие действия и в
каком порядке должны быть выполнены, чтобы решить любую задачу из класса
однотипных задач.
Алгоритм обладает следующими характеристиками:
1. Дискретность. Алгоритм – это процесс последовательного построения
величин таким образом, что в начальный момент задается исходная конечная
система величин, а в каждый следующий момент система величин получается по
определенному закону из системы, имевшихся в предыдущий момент времени.
2. Детерминированность. Система величин, получаемых в какой-то не
начальный момент, однозначно определяется системой величин, полученных в
предшествующие моменты времени.
3. Элементарность шагов алгоритмов. Закон получения последующей
системы величин из предшествующих должен быть простым.
4. Массовость алгоритма. Начальная система величин может выбираться
из некоторых потенциально бесконечного множества. Иначе говоря, алгоритм
должен обеспечивать решение некоторому множеству (классу) задач с
различными параметрами (коэффициентами).
5. Результативность алгоритма. Последовательный процесс построения
величин должен быть конечным и давать результат, того есть решение задачи.
Основная задача теории алгоритмов – это решение проблемы
алгоритмической разрешимости, а не поиск правила (способа/метода) ее
решения. Теория алгоритмов дает ответ на вопрос «Данная задача имеет
решение?», и не отвечает на вопрос «Как решается данная задача?»
В рамках такого подхода к определению понятия алгоритма можно
определить три основных направления:
1. Первое направление связано
с уточнением понятия эффективно
вычисляемой функции. В результате был выделен класс так называемых
рекурсивных функций.
2. Второе направление связано с машинной математикой. Здесь сущность
понятия
алгоритма
раскрывается
путем
рассмотрения
процессов,
осуществляемых в машине. Впервые это было сделано Тьюрингом, который
предложил общую и вместе с тем самую простую концепцию вычислительной
машины. Ее описание было дано Тьюрингом в 1937 г. А это направление в
теории алгоритмов получило название - машина Тьюринга.
3. Третье направление связано с понятием нормальных алгоритмов,
введенным и разработанным российским математиком А. А. Марковым. х
Нормальные алгоритмы Маркова. Это направление получило название
нормальные алгоритмы Маркова.
Рекурсивная функция
Основные понятия: элементарные функции, правила образования новых
функций.
54
Простейшие функции:
1. Функция сохранения нуля (нуль-функция)
x N
Z ( x) 0
(4.1)
2. Функция сдвига
x N
S ( x) x 1
(4.2)
3. Функция-проекция
x N
I n ( x , x ,, x , x ) x
k 1 2
k
n
k
(4.3)
Правила преобразования функций
1. Правило подстановки (суперпозиции)
Пусть даны функции:
g ( y , y ,, y ); h ( x , x ,, x ); h ( x , x ,, x ); h ( x , x ,, x )
1 2
n
1 1 2
m
2 1 2
m
n 1 2
m
Тогда
f ( x ,, x ) g (h ( x ,, x ),, h ( x ,, x ))
1
n
1 1
m
n 1
m
(4.4)
где g и h являются или простейшими, или выведенными из простейших.
Правило вывода (4.4) означает, что функция f получена из функций
g , h ,, h правилом суперпозиции
1
n
ПРИМЕР
Функция f ( x) k может быть получена путем применения k раз правила
суперпозиции на основе функций Z ( x), S ( x)
f ( x) S ( S ( Z ( x))) k ,
(4.5)
k
2. Правило примитивной рекурсии
Основывается на простейших или выведенных из простейших функциях g и
h:
Пусть
g ( x , x ,, x ); h( x , x ,, x , x
,x
)
1 2
n
1 2
n n 1 n 2
Тогда новая функция f ( y, x ,, x ) может быть выведена по правилу:
1
n
f ( x , , x ,0) g ( x , , x )
1
n
1
n
(4.6)
f ( x , , x , y 1) h(( x , , x ), f ( x , , x ), y )
1
n
1
n
1
n
Следует отметить, что функция g зависит от n аргументов, функция f зависит
от n 1 аргументов, функция h зависит от n 2 аргументов. Иначе говоря,
правило примитивной рекурсии позволяет получить n + 1-местную функцию из
n-местной и n + 2 - местной функций.
ПРИМЕР
Пусть некоторая функция f ( x, y ) задана правилом рекурсии
55
f ( x,0) I 2 ( x, y ) x
1
f ( x, y 1) S ( f ( x, y )) f ( x, y ) 1
Нетрудно заметить, что функция g ( x) I 2 ( x, y) x , функция
1
h( x, f ( x, y ), y ) S ( f ( x, y )) f ( x, y ) 1
Вычислим значение функции f ( x, y ) при x 2,
f (2,0) 2
y 5.
f (2,1) f ( x,0) 1 2 1 3
f (2,2) f ( x,1) 1 3 1 4
f (2,3) f ( x,2) 1 4 1 5
f (2,4) f ( x,3) 1 5 1 6
f (2,5) f ( x,4) 1 5 1 7
Нетрудно заметить, что функция f ( x, y ) выполняет сложение двух чисел x
и y.
3. - оператор (оператор нахождения наименьшего корня у)
Оператор y ( f ( x, y )) определяет наименьшее значение у, при котором
f ( x, y ) 0 при фиксированном значении. Принято обозначение
( x) y[ f ( x, y ) 0]
(4.7)
f ( x, y ) 0 »). Аналогично
(Читается: «наименьшее y такое, что
определяется функция многих переменных :
( x , x ,, x ) y[ f ( x , x ,, x , y ) 0]
(4.8)
1 2
n
1 2
n
Для вычисления функции существует следующий алгоритм:
1. Вычисляется f ( x , x ,, x ,0) . Если это значение функции f равно
1 2
n
( x , x ,, x ) 0 .
f ( x , x ,, x ,0) 0 ,
нулю,
то
Если
то
1 2
n
1 2
n
осуществляется переход к следующему шагу.
2. Вычисляется f ( x , x ,, x ,1) . Если это значение функции f равно
1 2
n
нулю, то ( x , x ,, x ) 1 . Если f ( x , x ,, x ,1) 0 , то осуществляется
1 2
n
1 2
n
переход к следующему шагу. И т. д.
Если окажется, что для всех y функция f ( x , x ,, x , y ) 0 , то функция
( x , x ,, x ) считается неопределенной.
1 2
1 2
n
n
ПРИМЕР
f ( x, y ) x y 2 .
Дана
функция
( x) y[ f ( x, y ) 0] при x 7
Необходимо
определить
56
y 0 702 5 0
y 1
y2
y3
y4
y5
7 1 2 4 0
722 3 0
7 3 2 2 0
7 4 2 1 0
752 5 0
Таким образом, ( x 7) 5
Функция
f ( x , x , , x ) называется частично рекурсивной, если она
1 2
n
получена из простейших функций за конечное число шагов на основе правил
подстановки, примитивной рекурсии или - оператора.
Функция f ( x , x ,, x ) называется примитивно рекурсивной, если она
1 2
n
может быть получена из простейших функций за конечное число шагов на
основе правил подстановки, примитивной рекурсии.
Функция называется общерекурсивной, если она частично рекурсивная и
всюдуопределенная.
Тезис А. Черча. Если функция является общерекурсивной, то она
выполнима, т.е. имеет алгоритм решения.
Машина Тьюринга
Если для решения некоторой массовой проблемы известен алгоритм, то для
его реализации необходимо лишь четкое выполнение предписаний этого
алгоритма. Автоматизм, необходимый при реализации алгоритма, приводит к
мысли о передаче функции человека, реализующий алгоритм, машине. Идею
такой машины предложил в 1937 году английский математик А. Тьюринг.
Машина Тьюринга включает в себя:
1. Внешний
алфавит
конечное
множество
символов
A {a , a , a ,, a } . В этом алфавите в виде слова кодируется та
0 1 2
n
информация, которая подается в машину. Машина перерабатывает
информацию, поданную в виде слова, в новое слово. Обычно символ
Внешний алфавит - конечное множество символов a обозначает
пробел.
2. Внутренний
алфавит
Q {q , q , q ,, q } .
Для
0 1 2
m
- конечное множество
любой машины число
символов
состояний
фиксировано. Два состояния имеют особое назначение q - начальное
1
состояние машины, q - заключительное состояние (стоп-состояние).
3. Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига
«влево», «вправо» и «на месте».
57
4. Бесконечная лента Бесконечная лента характеризует память машины.
Она разбита на клеточки. В каждую клеточку может быть записан
только один символ из внешнего алфавита.
5. Управляющая головка. Управляющая головка (УГ) передвигается вдоль
ленты и может останавливаться напротив какой-либо клетки, т. е.
считывать символ
6. Управляющая головка. Управляющая головка (УГ) передвигается вдоль
ленты и может останавливаться напротив какой-либо клетки, т. е.
считывать символ.
УГ
Рис. 4.1. Функциональная схема машины Тьюринга.
7. Программа машины Тьюринга (Р) - совокупность всех команд,
Программа представляется в виде таблицы и называется Тьюринговой
функциональной схемой.
a0
а0Пq1
а1Пq2
q1
q2
a1
a1Пq1
a2Нq0
a2
a2Лq2
a0Нq0
Таким образом, машина Тьюринга может быть представлена в виде
четверки:
MT A, Q, T , P
(4.9)
Работа машины Тьюринга:
Информация, хранящаяся на ленте, является набором символов из внешнего
алфавита. Начальное состояние управляющей головки характеризуется
символом внутреннего алфавита q . Работа машины складывается из тактов. В
1
течение любого такта машина Тьюринга осуществляет следующие действия:
машина Тьюринга находится во внутреннем состоянии q , считывает входной
i
символ a
j
и по таблице работы совершает операцию сдвига t , переходя в
l
состояние q , при этом входное слово a заменяется на a :
k
j
a q a t q
j i
ml k
m
Если в результате операции машина перейдет в состояние q , то работа
машины останавливается. Если состояние q
недостижимо, то значит по
данному входному слову машина Тьюринга не достигает конечного состояния и
алгоритма для данного входного слова не существует.
58
ПРИМЕР
Построить машину Тьюринга, которая будет стирать последнюю единицу в
последовательности единиц.
Внешний алфавит - A {a ,1} . Внутренний алфавит - Q {q , q , q } , при
0 1 2
этом состояние q .сохраняется до тех пор, пока не будет найден конец
1
последовательности единиц, состояние q
- стирание последней единицы. При
2
этом следует заметить, что ситуация a q
0 2
в работе машины Тьюринга
невозможна, поэтому соответствующая клеточка доопределена произвольно,
например a П q . Начальное состояние q на начале последовательности
2
1
единиц. Рабочая программа машины Тьюринга имеет вид:
q
1
q
2
1
a
1Пq
1
a Нq
a Лq
2
a Пq
2
Проверим работоспособность машины Тьюринга:
a 11
q
1
a 11
2. 0
q
1
a 11
a
1.
3.
a
a
q
1
a 11 a
4. 0
q
2
a 10 a
5. 0
q
Тезис А. Черча. Если функция выполнима, то она всегда может быть
представлена в виде машины Тьюринга.
Нормальные алгоритмы Маркова
Нормальный алгоритм Маркова представляет собой систему подстановок
P () Q ,
(4.10)
где P, Q - слова из символов входного алфавита A
() - оператор подстановки, при этом :
-простая подстановка
59
- заключительная подстановка.
Слово z считается включенным в слово у, если у может быть представлено
как:
x zx ,
1 2
где x , x - любые символы входного алфавита. A
1 2
(4.11)
Работа нормального алгоритма Маркова:
Исходное слово просматривается слева направо с целью выявления
вхождения первого правила подстановки. Как только находится первое
вхождение первого правила подстановки, оно заменяется по этому правилу и
исходное слово снова просматривается с первого символа по первому правилу
подстановки.
После того, как первое правило больше не встречается в данном слове,
аналогично применяется второе правило подстановки.
Работа алгоритма заканчивается тогда, когда ни одна из подстановок не
применима, либо.использована заключительная подстановка.
ПРИМЕР
Построить нормальный алгоритм Маркова, стирающий последовательность
единиц.
Нормальный алгоритм Маркова для данной задачи представляет собой две
подстановки :
1. 11 1
2. 1a a a
0 0
Первая подстановка стирает все единицы до последней. Вторая
(заключительная) подстановка заменяет последнюю единицу пробелом a .
Тезис А. Черча. Если функция выполнима, то она может быть представлена
в виде нормального алгоритма Маркова.
Заключительный тезис А. Черча. Если функция выполнима, то она может
быть представлена в виде либо общерекурсивной функции, либо. машины
Тьюринга, либо в виде нормального алгоритма Маркова.
60
ТЕОРИЯ АВТОМАТОВ
Автомат – дискретный преобразователь информации, который на основе
входных сигналов, поступающих в дискретные моменты времени, и с учетом
своего состояния вырабатывает выходные сигналы и изменяет свое состояние.
В данном разделе рассматриваются абстрактные автоматы, т.е. некоторая
математическая модель. Вопросы практической реализации не рассматриваются.
В связи с этим при построении автоматов будем иметь в виду, что:
1. Автомат функционирует в абстрактном времени.
2. Все переходы происходят мгновенно.
Автомат представляет собой кортеж 6 –го порядка:
(5.1)
X , Y , A, f (t ), (t ), a ,
где X – множество входных сигналов (входной алфавит),
Y – множество выходных сигналов (выходной алфавит),
A – множество внутренних состояний,
f (t ) – функция перехода,
(t ) – функция выхода,
a A - начальное состояние автомата.
Законы функционирования автоматов.
В зависимости от законов функционирования различают 3 вида автоматов:
1. Автоматы первого рода, или автоматы Мили:
a(t ) f (a(t 1), x(t ))
(5.2)
y (t ) (a(t 1), x(t ))
2. Автоматы второго рода
a(t ) f (a(t 1), x(t ))
(5.3)
y (t ) (a(t ), x(t ))
3. Правильные автоматы второго рода, или автоматы Мура:
a(t ) f (a(t 1), x(t ))
(5.4)
y (t ) (a(t ))
На практике наибольшее распространение получили автоматы Мили и
автоматы Мура.
Задание автоматов
Автоматы могут быть заданы следующими способами:
1. В виде графа
a0
x2/y1
a1
x1/y2
x2/y1
x2/y3
x1/y3
a2
x1/y3
РИС. 5.1. Автомат Мили
61
y1
x2
x1
a0
x2
a1
y2
x2
x1
a2
x1
y3
РИС. 5.2. Автомат Мура.
При построении автомата Мили каждая дуга, соединяющая вершины a и
i
a , имеет обозначение x / y . Это означает следующее: находясь, в состоянии
k m
j
a автомат, отрабатывая входной сигнал x , выдает выходной сигнал y
и
k
m
i
переходит в состояние a .
j
Так как в автомате Мура выходной сигнал y зависит только от текущего
m
состояния a , то каждая дуга, соединяющая вершины a и a , имеет
i
j
j
обозначение x .
k
2. В виде таблиц перехода и выхода (автомат Мили); отмеченной таблицы
перехода (автомат Мура).
Автомат Мили описывается с помощью двух таблиц: таблицы перехода и
таблицы выхода:
Таблица переходов (ТП)
a
x
1
x
2
a
1
a
2
a
1
a
2
a
Таблица выходов (ТВ)
a
a
a
a
2
x
1
x
2
2
y
y
2
3
a
1
y
3
y
1
a
2
y
3
y
1
Автомат Мура описывается с помощью отмеченной таблицы перехода:
Таблица переходов (ТП)
x
1
x
2
y
1
a
a
1
a
2
y
2
a
1
a
2
a
y
a
a
a
3
2
2
ПРИМЕР.
Синтезировать автомат, на вход которого подаются монеты номинальной
стоимостью 1, 2 и 3 копейки, а на выходе автомат выдает билет, если сумма
набранных монет составляет 3 копейки, если сумма меньше 3 копеек, то автомат
ничего не выдает, если сумма больше 3 копеек, то автомат возвращает деньги.
62
Определим входной, выходной алфавиты и множество внутренних
состояний:
входной алфавит X {1,2,3} - монеты номинальной стоимостью 1, 2 и 3
копейки
выходной алфавит Y {Н , Б , В} - на выходе возможны выходные
символы: Н - ничего; Б - билет; В - возврат.
множество внутренних состояний A {a , a , a , a } ,
0 1 2 3
где a - начальное состояние автомата « в автомате ничего нет»;
a - «в автомате 1 копейка»;
1
a - «в автомате 1 копейка»;
1
a - «в автомате 2 копейки»;
2
a - «в автомате 3 копейки».
3
Граф автомата имеет вид:
3/B
а0
1/Н
1/Н
2/н
3/Б
2/н
а1
1/Н
1/Н
2/В, 3/В
а3
1/Б
а2
3/Б
2/Н
РИС. 5.3. Автомат Мили
Таблицы перехода и выхода представлены в виде:
Таблица переходов (ТП)
Таблица выходов (ТВ)
a
1
2
3
a
1
a
2
a
3
a
1
a
2
a
3
a
a
2
a
3
a
a
a
3
a
1
a
2
a
3
a
a
1
a
1
Н
Н
Б
Н
2
Н
Б
В
Н
3
Б
В
В
Б
2
a
3
Неопределенным состоянием называется несуществующее состояние.
Частичным автоматом называется автомат, в котором некоторые
состояния в таблице перехода не определены. Для дальнейшего исследования
неопределенное состояние некоторым образом доопределяют.
63
Минимизация автоматов
Входным словом называется совокупность сигналов, поступающих на вход.
Выходным словом называются совокупность сигналов на выходе.
Два автомата называются эквивалентными, если они имеют одинаковый
входной и выходной алфавит, и на одинаковые входные слова выдают
одинаковые выходные слова.
Два состояния одноэквивалентными , если на одинаковое входное слово
выдается одинаковый выходной сигнал.
Два состояния k-эквивалентными, если на одинаковое входное слово
длиной в k-единиц выдается одинаковый выходной сигнал длиной в k-единиц.
Эквивалентными состояниями называются k-эквивалентные состояния для
любых k.
Эквивалентные состояния объединяются в класс эквивалентности.
Минимальный автомат – это автомат, состоящий из наименьшего числа
состояний, каждое из которых является классом эквивалентности исходного
автомата.
Алгоритм минимизации автомата Мили
1. По таблице выхода находятся состояния с одинаковыми выходными
сигналами. Данные состояния объединяются в класс одноэквивалентных
состояний. Проводится перекодировка.
2. По таблице перехода определяются классы двухэквивалентных
состояний: для любого класса выделяется состояние, которое на одинаковый
входной сигнал переходит в одинаковое состояние. Объединяем
двухэквивалентные состояния в классы двухэквивалентных состояний.
Проводится перекодировка.
3. Алгоритм выполняется, пока в классах k-эквивалентных состояний не
находятся одинаковые состояния.
4. Вводятся новые состояния, соответствующие классам эквивалентных
состояний.
5. С учетом новых состояний переписываются таблицы перехода и выхода.
ПРИМЕР
Пусть задан автомат Мили
x
1
x
2
x
3
1
1
2
3
1
4
5
1
6
Таблица выходов
7
8
9
1
1
1
1
1
1
1
1
1
1
64
Таблица переходов
x
1
x
2
x
3
1
2
2
1
3
2
4
3
5
6
6
8
7
6
8
4
9
7
2
4
2
2
4
9
2
4
9
5
4
5
2
3
6
8
7
7
Определяем класс одноэквивалентных состояний по таблице выхода
Таблица выходов
1
2
3
4
5
6
7
8
9
1
1
1
1
1
x
1
x
2
x
3
1
1
1
1
1
1
1
1
а
в
а
в
а
в
а
в
Выделяются два класса одноэквивалентных состояний a={1,3,5,7,8} и
b={2,4,6,9}. Перегруппируем таблицу перехода по классам одноэквивалентных
состояний
Таблица переходов
а
в
1
3
5
7
8
2
4
6
9
2
2
6
6
4
1
3
8
7
x
1
x
2
x
3
2
2
4
2
4
4
2
9
9
5
5
3
8
7
4
2
6
7
Перекодируем состояния по полученным классам
x
1
x
2
x
3
1
2/в
3
2/в
а
5
6/в
7
6/в
8
4/в
2
1/а
Таблица переходов
в
4
6
9
3/а
8/а
7/а
2/в
2/в
4/в
2/в
4/в
4/в
2/в
9/в
9/в
5/а
5/а
3/а
8/а
7/а
4/в
2/в
6/в
7/а
Выделяем внутри каждого из классов одинаковые состояния, тем самым
определяя классы двухэквивалентных состояний
65
x
1
x
2
x
3
7
6/в
8
4/в
2
1/а
Таблица переходов
в
4
6
9
3/а
8/а
7/а
1
2/в
3
2/в
а
5
6/в
2/в
2/в
4/в
2/в
4/в
4/в
2/в
9/в
9/в
5/а
5/а
3/а
8/а
7/а
4/в
2/в
6/в
7/а
а
в
с
Определим новые классы двухэквивалентных состояний a={1,3,5,7,8},
b={2,4,6}, c={9}, перекодируем по новым состояниям и выделим классы
трехэквивалентных состояний
Таблица переходов
а
в
с
1
3
5
7
8
2
4
6
9
2/в
2/в
6/в
6/в
4/в
1/а
3/а
8/а
7/а
x
1
x
2
x
3
2/в
2/в
4/в
2/в
4/в
4/в
2/в
9/с
9/с
5/а
5/а
3/а
8/а
7/а
4/в
2/в
6/в
7/а
а
в
с
d
Классы трехэквивалентных состояний a={1,3,5,7,8}, b={2,4}, c={6}, d={9}
перекодируем по новым состояниям и выделим классы четырехэквивалентных
состояний
Таблица переходов
а
в
с
d
1
3
5
7
8
2
4
6
9
2/в
2/в
6/с
6/с
4/в
1/а
3/а
8/а
7/а
x
1
x
2
x
3
2/в
2/в
4/в
2/в
4/в
4/в
2/в
9/d
9/d
5/а
5/а
3/а
8/а
7/а
4/в
2/в
6/с
7/а
а
в
а
c
d
e
Перегруппируем таблицу перехода по новым классам a={1,3,8}, b={5,7},
c={2,4}, d={6}, е={9}, перекодируем по новым состояниям.
Таблица переходов
а
в
c
d
e
1
3
8
5
7
2
4
6
9
2/с
2/с
4/с
6/d
6/ d
1/a
3/a
8/a
7/b
x
1
x
2
x
3
2/с
2/с
4/с
4/c
2/c
4/c
2/c
9/e
9/e
5/в
5/в
7/в
3/a
8/a
4/c
2/c
6/d
7/b
а
в
c
d
e
Так как внутри из каждого класса дальнейшее разбиение на классы не
осуществляется, это означает, что найдены классы эквивалентных состояний:.
a={1,3,8}, b={5,7}, c={2,4}, d={6}, е={9}.
66
Минимизированный автомат Мили в новых состояниях имеет вид
Таблица переходов
x
1
x
2
x
3
a
с
b
d
c
a
d
a
e
b
с
c
c
e
e
в
c
c
d
b
Таблица выходов
x
1
x
2
x
3
a
1
b
1
c
d
e
1
1
1
1
Особенности минимизации автомата Мура.
:
Автомат Мура минимизируется аналогично минимизации автомата Мили за
исключением первого шага. Выделение класса одноэквивалентных состояний
осуществляется по строке выходов отмеченной таблицы переходов автомата
Мура.
Минимизация частичных автоматов.
Для того, чтобы провести минимизацию частичных автоматов
неопределенное состояние доопределяется самостоятельно. Далее минимизация
автоматов осуществляется по вышеизложенному алгоритму.
Переход от автомата Мили к автомату Мура
Автоматы Мили и автоматы Мура отличаются функцией выхода.
Автомат Мили:
y (t ) (a(t 1), x(t ))
(5.5)
Автомат Мура:
y (t ) (a (t ))
(5.6)
То есть произвольному состоянию автомата Мили a и входному сигналу
i
x соответствует состояние b автомата Мура:
j
ij
a x b
i j
ij
При этом начальные состояния автоматов Мили и Мура совпадают:
(5.7)
67
a b
(5.8)
Учитывая вышеизложенное, можно перекодировать таблицу перехода
автомата Мили и составить отмеченную таблицу переходов автомата Мура.
ПРИМЕР
Пусть задан автомат Мили
Таблица переходов (ТП)
a
x
1
x
2
a
1
a
2
a
1
a
2
a
a
a
a
Таблица выходов (ТВ)
a
2
x
1
x
2
2
a
1
y
3
y
1
y
y
2
3
a
2
y
3
y
1
Перекодируем матрицу перехода автомата Мили:
a b
a /b
1 01
a /b
2 02
x
1
x
2
a
1
a /b
2 11
a /b
0 12
a
2
a /b
2 21
a /b
0 22
Составляем таблицу перехода автомата Мура.
b
b
01
b
02
x
1
x
2
b
01
b
11
b
12
b
02
b
21
b
22
b
11
b
21
b
22
b
12
b
01
b
02
b
21
b
21
b
22
b
22
b
01
b
02
При составлении таблицы перехода автомата Мили рассуждаем следующим
образом: состояние автомата Мура b соответствует состоянию автомата Мили
01
a , следовательно, столбец состояния b автомата Мура совпадает со столбцом
01
1
состояния a автомата Мили.
1
Так как в автомате Мура произвольному состоянию b соответствует
ij
некоторый выходной сигнал, то строка выхода отмеченной таблицы перехода
автомата Мура однозначно определяется таблицей выхода автомата Мили
(состоянию b соответствует выходной сигнал y ; b - y )
01
2
y
x
1
x
2
b
b
01
b
02
2
b
01
b
11
b
12
y
3
b
02
b
21
b
22
y
3
b
11
b
21
b
22
y
1
b
12
b
01
b
02
3
02
y
3
b
21
b
21
b
22
y
1
b
22
b
01
b
02
68
Выходной
сигнал,
соответствующий
состоянию
b ,
выбирается
произвольно.
y
x
1
x
2
y
2
b
b
01
b
02
2
b
01
b
11
b
12
y
y
3
b
02
b
21
b
22
3
b
11
b
21
b
22
y
1
b
12
b
01
b
02
y
3
b
21
b
21
b
22
y
1
b
22
b
01
b
02
Если автомат Мили содержит m-состояний и n входных символов, то
количество состояний автомата Мура определяется по формуле:
(5.9)
k m n 1
Переход от автомата Мура к автомату Мили
Переход от автомата Мура к автомату Мили заключается в построении
таблицы выходов. Построение состоит в подстановке выходных сигналов,
отмечающих состояния в отмеченной таблице переходов, вместо состояний, в
которые автомат переходит. Тем самым, если говорить в терминах графов,
выходные сигналы от состояний переносятся на дуги, которые в эти состояния
заходят.
А таблица переходов автомата Мили получается из отмеченной таблицы
переходов автомата Мура отбрасыванием строки выходов.
ПРИМЕР
Пусть задан автомат Мура в виде отмеченной таблицы перехода
x
1
x
2
x
3
y
1
y
A
A
B
B
C
A
B
B
C
C
A
C
3
y
2
Данный автомат может быть представлен в виде графа:
69
y1
х1
x2
A
x3 x3
x1
B
x
y3
x2
C
y2
x1
x2
x1 3
РИС. 5.4. Автомат Мура
Автомат Мили будет иметь вид:
в виде таблиц перехода и выхода
Таблица переходов
x
1
x
2
x
3
y
1
y
y
A
A
B
B
C
A
B
B
C
C
A
C
3
Таблица выходов
2
x
1
x
2
x
3
в виде графа
x1/y1
А
x2/y3
x3/y1
x3/y2
B
x1/y1
x1,x2/y3
C
x2,x3/y
2
РИС. 5.5. Автомат Мили
A
B
C
y
1
y
3
y
2
y
y
1
y
2
y
2
y
3
3
y
1
