Материал: 5540
дизъюнкции, поменяем в каком-либо предикате, например во втором, переменную х на новую переменную z:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
( x)( y) F1(x, y) |
( x)( y) F2 (x, y) ( x)( y) F1(x, y) ( z)( y) F2 (z, y). |
|||||||||||||||||||||||||||||||||||||
Окончательно получим префиксную нормальную форму для |
||||||||||||||||||||||||||||||||||||||
исходной предикатной формулы: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
( x)( y) F1(x, y) |
( z)( y) F2 (x, y) ( x)( z)(( y) F1(x, y) |
( y) F2 (z, y)) |
||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
( x)( z)( y) (F1 (x, y) |
|
F2 (z, y)). |
|
|
|
|
|
|
|
|
|
||||||||||||||||||
Правило перемещения символа отрицания слева направо для |
||||||||||||||||||||||||||||||||||||||
многоместных предикатов, например, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
P |
|
|
|
|
P |
P |
P |
|
|
|
|
|
P |
|
P. |
|||||||||||||||||||
Таким образом, чтобы произвести полное отрицание многоместного |
||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
предиката с кванторами, необходимо прибегнуть к замене: |
|
|
|
|
, P P . |
|||||||||||||||||||||||||||||||||
Пример 4.10. Получить ПНФ предикатной формулы: |
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
( x)( y)(( z)(F1(x, z) |
F2 ( y, z)) |
|
|
|
( u) F3(x, y, u)). |
||||||||||||||||||||||||||||||
Решение. ( x)( y)(( z)(F1 (x, z) |
|
F2 ( y, z)) |
|
|
( u) F3 (x, y, u)) |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
( x)( y) (( z) (F1(x, z) |
|
F2 ( y, z)) |
|
( u) F3 (x, y, u)) |
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
( x)( y) (( |
z) F1(x, z) |
F2 ( y, z) |
( u) F3 (x, |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
( x)( y) (( z) F1(x, z) |
F2 ( y, z)) |
( u) F3 (x, |
||||||||||
|
|
|
|
|
|
|
|
|
|
|||
( x)( y) ( z)( F1(x, z) |
F2 ( y, z) |
( u) F3 (x, |
||||||||||
|
|
|
|
|
|
|||||||
( x)( y)( |
z)( u)( F1(x, z) F2 ( y, z) F3 (x, |
|||||||||||
y,u)) 
y,u)) 
y,u)) 
y,u)).
Пример 4.11. Получить ПНФ предикатной формулы
(( u) F1(u) ( y)( u) F2 ( y, u)) ( x) F3 (x).
Решение. Для получения ПНФ осуществим эквивалентные преобразования:
|
|
|
|
|
|
|
|
|
|
|
|
(( u) F1(u) |
( y)( u) F2 ( y, u)) |
( x) F3 (x) |
|||||||||
|
|
|
|
|
|
|
|
|
|||
|
(( u) F1 (u) ( y)( u) F2 ( y, u)) |
( x) F3 (x) |
|||||||||
|
|
|
|
|
|
||||||
|
(( u) F1(u) |
( y)( u) F2 ( y, u)) |
( x) F3 (x) |
||||||||
( u) F1(u) ( y)( u) F2 ( y, u) ( x) F3(x) 
( u) F1 (u) ( y)( u) F2 ( y, u) ( x) F3 (x) 
( u) F1(u) ( y)( u) F2 ( y, u) ( x) F3 (x) 
96
|
|
|
|
|
|
( u) F1(u) |
( y)( u) F2 ( y, u) ( x) F3 (x) |
||||
|
|
|
|
||
( u) (F1(u) |
( y) F2 ( y, u)) ( x) F3 (x) |
||||
( u)( y) (F1 (u) F2 ( y, u)) ( x) F3 (x) ( u)( y)( x) (F1(u) F2 ( y, u) F3 (x)) 
( x)( y)( u) (F1(u) F2 ( y, u) F3 (x)).
Задача 4.14. Получить ПНФ следующих предикатных формул:
1) ( x)( y) F1(x, y) |
( x)( y) F2 (x, y); |
|
|
|
|
|
||||||
2) (( x)( y) F2 (x, y) ( x) F2 (x)) ( y)( z) F3( y, z); |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
3) ( x)( y) F1(x, y) |
( y)( z) F2 ( y, z) |
( y)( z) F3 ( y, z); |
||||||||||
4) (( x)( y) F1(x, z) |
|
|
|
|
|
|
|
|
|
|||
( x)( y) F2 (x, y)) |
( z) F3 (z); |
|||||||||||
|
|
|
|
|
|
|||||||
5) (( x)( y)( z) F1(x, y, z) ( y) F2 ( y)) |
( x)( z) F3 (x, z). |
|||||||||||
Глава 5. ТЕОРИЯ ГРАФОВ
Теория графов находит самое широкое применение в моделировании информационных процессов, в программировании и в решении экономических задач. Она позволяет просто описывать сложные явления и даёт им графическую интерпретацию.
Первая работа по теории графов была опубликована математиком Л. Эйлером в 1736 г. в Трудах Академии наук Санкт-Петербурга в виде задачи о Кёнигсбергских мостах (рисунок 5.1). Суть задачи сводилась к следующему: мог ли житель Кенигсберга, выйдя из дома, находящегося на части суши A, B, С или D, пройти по семи мостам через реку Прегель в точности по одному разу и вернуться домой? Ответ на этот вопрос был отрицательным.
97
Рисунок 5.1 – Кёнигсбергские мосты и их модель
Для пояснения задачи представлена модель (рисунок 5.1), где каждый участок суши замещён точкой на плоскости, а мосты – линиями, связывающими участки суши.
5.1 Основные понятия теории графов. Способы задания графов
Графические представления в узком смысле – это описание исследуемой системы, процесса, явления средствами теории графов в виде совокупности двух классов объектов: вершин и соединяющих их линий –
рёбер или дуг.
Графом G называется совокупность двух множеств: |
вершин V и |
рёбер E, между элементами которых определено |
отношение |
инцидентности – каждое ребро е E инцидентно ровно двум вершинам vi, vj V, которые оно соединяет. При этом вершина vi (vj) и ребро е называются инцидентными друг другу, а вершины vi и vj, являющиеся для ребра е концевыми точками, называются смежными. Часто вместо v V и е Е пишут соответственно v G, е G.
Ребро, соединяющее две вершины, может иметь направление от одной вершины к другой; в этом случае оно называется направленным, или ориентированным, или дугой и изображается стрелкой, направленной от вершины, называемой началом, к вершине, именуемой концом.
Граф, соединяющий направленные рёбра (дуги) с началом vi и концом vj, называется ориентированным (орграфом), а ненаправленные –
неориентированным (н-графом) (рисунок 5.2).
98
а) |
|
|
б) |
|
|
v1 |
е3 |
v3 |
v1 |
е3 |
v3 |
|
|
|
|
||
е1 |
е5 |
е6 |
е1 |
е5 |
е6 |
е4 |
|
е4 |
|
||
|
v5 |
|
|
||
v0 |
|
v0 |
|
|
|
е2 |
|
е8 |
е2 |
|
е8 |
|
|
|
|
||
v2 |
v4 |
|
v2 |
v4 |
|
|
|
|
|
Рисунок 5.2 – н-граф (а) и орграф (б)
Рёбра, инцидентные одной и той же паре вершин, называются параллельными, или кратными. Граф, содержащий кратные рёбра, именуется мультиграфом. Ребро, концевые вершины которого совпадают, называется петлёй.
Граф называется конечным, если множество его элементов (вершин и рёбер) конечно, и пустым, если его множество вершин V (а значит и рёбер E) пусто. Граф без петель и кратных рёбер именуется полным, если каждая пара вершин соединена ребром.
Дополнением графа G называется граф G , имеющий те же вершины, что и граф G, и содержащий только те рёбра, которые нужно добавить к графу G, чтобы получить полный граф.
Локальной степенью (или просто степенью) вершины v V н-графа
G называется количество рёбер ρ(v), инцидентных вершине v. В н-графе сумма степеней всех вершин равна удвоенному числу рёбер m графа, т.е. чётна (предполагается, что в графе с петлями петля даёт вклад 2 в степень вершины):
(v) 2m ,
v G
отсюда следует, что в н-графе число вершин нечётной степени чётно.
Для вершины орграфа определяются две локальные степени:
99
ρ1(v) – число рёбер с началом в вершине v, или количество выходящих из v рёбер;
ρ2(v) – количество входящих в v рёбер, для которых эта вершина является концом.
Петля даёт вклад 1 в обе эти степени.
В орграфе суммы степеней всех вершин ρ1(v) и ρ2(v) равны количеству рёбер m этого графа, а значит, и равны между собой:
1(v) |
2 (v) m . |
v G |
v G |
Графы G1 и G2 равны, т.е. G1 = G2, если их множества вершин и рёбер (выраженных через пары инцидентных им вершин) совпадают:
V1 = V2 и Е1 = Е2.
Граф G считается полностью заданным в строгом смысле, если нумерация его вершин и рёбер зафиксирована. Графы, отличающиеся только нумерацией вершин и рёбер, называются изоморфными.
Пример 5.1. Задать граф G (рисунок 5.3) через множество вершин и рёбер.
v2 |
v1 |
е1 |
|
е4 |
|
е2 |
v3 |
v4 |
е3 |
|
|
v5 |
|
Рисунок 5.3 – Граф G
Решение. Граф G может быть полностью определён:
– двумя множествами поименованных вершин V1 = {v1, v2, v3, v4, v5} и поименованных рёбер Е1 = {e1, e2, e3, e4} (в строгом смысле требуется установление отношения инцидентности рёбер соответствующим вершинам);
100