ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9594
Скачиваний: 93
71
2)
внести все отрицания внутрь формулы, “приклеив” их к предикат-
ным символам;
3)
вынести все кванторы в начало формулы.
Пример. Записать в ПНФ формулу логики предикатов
)))
(
)
(
(
(
y
yQ
x
P
x
F
∀
→
∃
¬
=
.
В преобразованиях будем использовать законы логики высказываний
(табл. 2.5) и логики предикатов (табл. 2.13).
≡
∀
∨
¬
¬
∀
≡
∀
→
∃
¬
≡
)))
(
)
(
(
(
)))
(
)
(
(
(
y
yQ
x
P
x
y
yQ
x
P
x
F
)))
(
(
&
)
(
(
)))
(
(
&
)
(
(
y
Q
y
x
P
x
y
yQ
x
P
x
¬
∃
∀
≡
∀
¬
∀
≡
≡
)).
(
&
)
(
(
y
Q
x
P
y
x
¬
∃
∀
≡
2.3.6. Решение задачи контрольной работы №2
Задача. Используя два предиката, записать предложение в виде формулы
логики предикатов: “Все кошки знают румынский язык”. Записать отрицание
этой формулы и привести ее к предваренной нормальной форме.
Решение. Будем использовать предикат
)
(x
K
– “
x
является кошкой”,
)
(x
R
– “
x
знает
румынский язык”. Тогда данное предложение можно записать
в виде формулы:
)).
(
)
(
(
))
(
)
(
(
x
R
x
K
x
x
R
x
K
x
F
∨
¬
∀
≡
→
∀
=
Отрицание данного предложения сформулируем, начиная со слова “не-
верно”. “Неверно, что все кошки знают румынский язык”.
)).
(
&
)
(
(
)
(
)
(
(
(
))
(
)
(
(
(
)))
(
)
(
(
(
x
R
x
K
x
x
R
x
K
x
x
R
x
K
x
x
R
x
K
x
F
¬
∃
≡
∨
¬
¬
∃
≡
∨
¬
∀
¬
≡
→
∀
¬
=
¬
2.3.7. Контрольные вопросы и упражнения
1.
Приведите примеры одноместных предикатов.
2.
Дайте определение
n-
местного предиката.
3.
Что такое предметные переменные?
4.
Что такое порядок (местность) предиката?
5.
Что такое множество истинности предиката?
6.
Какие переменные являются связанными, а какие свободными:
))
(
(
))
(
)
(
(
z
zQ
y
Q
x
xP
F
¬
∨
→
∀
=
?
7.
Запишите в виде формулы логики предикатов:
а) если мороз больше 40
0
, то некоторые школьники не идут на заня-
тия;
б) если мороз больше 50
0
, то все школьники не идут на занятия.
8.
Что такое общезначимая формула?
9.
Запишите основные равносильности логики предикатов.
10.
Как привести формулу логики предикатов к предваренной нормаль-
ной форме?
72
3. ОСНОВЫ ТЕОРИИ ГРАФОВ
3.1. Ориентированные графы
3.1.1. Основные понятия
С ориентированными графами мы уже встречались при изучении бинар-
ных отношений.
Определение. Ориентированным графом (орграфом) называется упоря-
доченная пара
)
,
(
Γ
X
, где
X
– множество произвольной природы, а
X
X
×
⊆
Γ
.
Элементы множества X называются вершинами, а элементы
)
,
(
y
x
мно-
жества
Γ
- дугами орграфа
)
,
(
0
Γ
= X
G
. Обычно вершины орграфа изобра-
жаются точками плоскости, а каждая дуга
)
,
(
y
x
– стрелкой от вершины
x
к
вершине
y
(
x
- начало,
y
– конец дуги).
Говорят, что вершина х смежна вершине у, если х является началом, а у –
концом одной и той же дуги. Две дуги смежны, если у них есть общая верши-
на. Говорят, что вершина
x
и дуга
g
инцидентны, если вершина
x
является
началом или концом дуги
g
. Дуга
)
,
(
y
x
g
=
называется петлей, если
y
x
=
.
Обозначим
}
)
,
(
{
)
(
Γ
∈
=
Γ
y
x
y
x
;
}
)
,
(
{
)
(
1
Γ
∈
=
Γ
−
x
z
z
x
;
))
(
(
)
(
1
x
x
n
n
−
Γ
Γ
=
Γ
;
))
(
(
)
(
)
1
(
1
x
x
n
n
−
−
−
−
Γ
Γ
=
Γ
.
Множеством достижимости вершины
X
x
∈
называется множество
вершин
X
:
.
...
)
(
)
(
}
{
)
(
2
∪
Γ
∪
Γ
∪
=
x
x
x
x
D
Множеством контрдостижимости вершины
X
x
∈
называется мно-
жество вершин
X
:
.
...
)
(
)
(
}
{
)
(
2
1
∪
Γ
∪
Γ
∪
=
−
−
x
x
x
x
K
3.1.2. Орграфы и бинарные отношения
Мы рассматриваем орграфы, в которых каждая пара вершин может со-
единяться не более, чем двумя дугами; причем если дуги две, то они идут в
противоположных направлениях. Это графы Бержа – графы представления
бинарных отношений. Рассмотрим, как связаны свойства бинарного отноше-
ния (см. 1.2.4) с изображением орграфа на плоскости.
73
Рефлексивное бинарное отношение
X
X
R
×
⊆
представляется оргра-
фом
)
,
(
0
R
X
G
=
, имеющим петли при каждой вершине, т.к. по определению
R
x
x
X
x
∈
⇒
∈
∀
)
,
(
(рис. 3.1, а).
Антирефлексивному отношению
R
соответствует орграф, не имеющий
ни одной петли (рис. 3.1, б)
Свойство симметричности отношения
R
означает, что любые две вер-
шины соединены парой противоположно направленных дуг (рис. 3.1, в). В
орграфе, представляющем несимметричное отношение, нет петель, и любая
пара вершин может быть соединена только одной дугой (рис. 3.1, г). Анти-
симметричность означает, что любая пара вершин орграфа может быть со-
единена только одной дугой, но могут быть и петли (рис. 3.1, д). Согласно
определению транзитивности, для любой пары дуг таких, что конец первой
совпадает с началом второй, существует третья дуга, имеющая общее начало с
первой и общий конец со второй. Этому условию отвечают орграфы, изобра-
женные на рис. 3.1, б, г.
3.1.3. Матрицы орграфа
При решении на ЭВМ задач, связанных с орграфами, удобно представ-
лять орграфы в виде матриц. Дадим определения матриц для орграфа
)
,
(
0
Γ
= X
G
, где
}
,
,
,
{
2
1
n
x
x
x
X
…
=
,
}
,
,
,
{
2
1
m
g
g
g
…
=
Γ
.
Матрицей смежности орграфа
0
G
называется матрица
A
, имеющая
n
строк и
n
столбцов, элемент которой, стоящий на пересечении
i
-ой строки и
j
-го столбца, равен
74
⎩
⎨
⎧
Γ
∉
Γ
∈
=
,
)
,
(
,
0
,
)
,
(
,
1
j
i
j
i
j
i
x
x
если
x
x
если
a
.
,
1
,
n
j
i
=
Матрица смежности не сохраняет информацию о нумерации дуг орграфа.
Матрицей инцидентности орграфа
0
G
называется матрица
B
, имею-
щая n строк и m столбцов, элемент которой, стоящий на пересечении
i
-ой
строки и
j
-го столбца, равен
1,
,
1,
,
2,
,
0,
,
i
j
i
j
i j
i
j
i
j
если вершина x
начало дуги g
если вершина x
конец дуги g
b
если при вершине x есть петля g
если вершина x и дуга g неинцидентны
−
−
⎧
⎪
−
⎪
= ⎨
⎪
⎪⎩
.
,
1
,
,
1
m
j
n
i
=
=
3.1.4. Решение задачи 5 контрольной работы № 2
Задача. Дан ориентированный граф
)
,
(
0
R
X
G
=
(рис. 3.2, а). Найти
множество достижимости и множество контрдостижимости вершины
2
x
.
Выяснить, какими свойствами обладает бинарное отношение
R
. Построить
матрицу смежности и матрицу инцидентности орграфа
0
G
.
Решение. Будем строить множество достижимости поэтапно, включая в
него вершины, в которые можно попасть из вершины
2
x
, пройдя по одной,
двум, трем и так далее дугам орграфа, до тех пор, пока множество не переста-
нет меняться.
Шаг 0.
}
{
:
2
0
x
D
=
.
Шаг 1.
}.
,
,
{
)
(
},
,
{
)
(
3
2
1
2
0
1
3
1
2
x
x
x
x
R
D
D
x
x
x
R
=
∪
=
=
Шаг 2.
∪
=
∪
=
=
}
,
{
)
(
)
(
))
(
(
)
(
4
1
3
1
2
2
2
x
x
x
R
x
R
x
R
R
x
R
∅
}
,
{
4
1
x
x
=
.
}.
,
,
,
{
}
,
{
}
,
,
{
)
(
4
3
2
1
4
1
3
2
1
2
2
1
2
x
x
x
x
x
x
x
x
x
x
R
D
D
=
∪
=
∪
=
75
Множество
2
D
содержит все вершины орграфа, поэтому процесс по-
строения множества достижимости окончен:
}.
,
,
,
{
)
(
4
3
2
1
2
x
x
x
x
x
D
=
Аналогично строится множество контрдостижимости, но теперь мы
ищем вершины, из которых можно попасть в вершину
2
x
.
Шаг 0.
}
{
:
2
0
x
K
=
.
Шаг 1.
=
−
)
(
2
1
x
R
∅,
∪
=
0
1
K
K
∅
0
K
=
.
Дальнейшее изменение множества невозможно, поэтому
}.
{
)
(
2
2
x
x
K
=
Выясним, какими свойствами обладает отношение
R
. Отношение не яв-
ляется рефлексивным (не при всех вершинах есть петли) и не является анти-
рефлексивным (есть петля при вершине
2
x
). Отношение не является симмет-
ричным (пара вершин
)
,
(
3
2
x
x
соединена только одной дугой), не является
несимметричным (вершины
1
x
и
4
x
соединены парой дуг), не является анти-
симметричным (
R
x
x
∈
)
,
(
4
2
и
R
x
x
∈
)
,
(
2
4
, но
4
2
x
x
≠
). Отношение не яв-
ляется транзитивным (
R
x
x
∈
)
,
(
1
2
и
R
x
x
∈
)
,
(
4
1
, но
R
x
x
∉
)
,
(
4
2
).
Матрица смежности орграфа
0
G
имеет вид:
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
1
4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
A
.
Для построения матрицы инцидентности занумеруем дуги орграфа
0
G
(рис. 3.1, б). В этих обозначениях матрица инцидентности имеет вид (
i
-ый
столбец матрицы соответствует дуге
5
,
,
2
,
1
,
…
=
i
g
i
):
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
−
−
−
−
=
0
0
1
1
0
1
0
0
0
0
1
1
0
0
0
0
1
1
1
2
4
3
2
1
5
4
3
2
1
x
x
x
x
g
g
g
g
g
B
.
3.1.5. Контрольные вопросы и упражнения
1.
Какие вершины орграфа называются смежными?
2.
Когда говорят, что вершина x инцидентна дуге
g
?