Упражнения.

1. Проиллюстрировать на примере предиката порядка {Q:N² B; Q(a₁, a₂)=1 тогда и только тогда, когда a₁ a₂}, понятия истинного, логичного и переменного высказываний.

2. Пусть предикт P(x, y) задан на множестве M = {a; b;c} таблицей 14. Определить истинность следующих формул:

а) xP(x, a), xP(x, a), y P(a, y), yP(a,y) ;

б) xP(x, b), xP(x, b), y P(b, y), yP(b,y) ;

в) x y P(x, y), x y P(x, y), y x P(x, y), y xP(x,y) ;

г) y xP(x, y), x y P(x, y), x y P(x, y), x y P(x,y) ;

Таблица 14

x y	P(x,y)
a a a b a c b a b b b c c a c b c c	0 1 1 0 1 1 0 1 1

3. Определить истинность, логичность либо выполнимость следующих формул:

а) xP(x, y, z);

б) xP(x, y) xP(x, y);

в) x(P(x) (x));

г) x(P(x) & P(x));

д) xP(x) x P(x);

4. Получить ПНФ следующих предикатных формул:

а) x yP₁(x, y) x yP₂(x, y);

б) ( x zP₁(x, z) x yP₂(x, y)) z P₃(z);

в) ( yP₁( y) x y P₂(x, y)) z P₃(z);

г) ( x y P₁(x, y) x yP₂(x, y)).

4. Теория графов

4.1.Основные понятия

Так называемые графы являются наиболее исследованным классом объектов, относящихся к графическим представлениям. Графические представления в узком смысле это описание исследуемой системы, процесса, явления средствами теории графов в виде совокупности двух классов объектов: вершин и соединяющих их ребер. Графы и их составляющие характеризуются определенными свойствами и набором допустимых операций над ними.

Определение. Графом G называется совокупность двух множеств: вершин V и ребер Е, между элементами которых определено отношение инцидентности – каждое ребро еεЕ инцидентно ровно двум вершинам v' и v''εV, которые они соединяют. При этом вершина v' (и v'') и ребро е называют инцидентными друг другу, а вершины v' и v'', являющиеся для ребра е концевыми точками, называют смежными. Часто вместо vεV и еεЕ пишут vεG и еεG.

Ребро, соединяющее две вершины, может иметь направление от одной вершины к другой. В этом случае оно называется направленным или ориентированным или дугой и изображается стрелкой, направленной от вершины, называемой началом к вершине, называемой концом.

Граф, содержащий направленные ребра называется ориентированным или орграфом, а ненаправленные – неориентированным или н-графом.

Ребра, инцидентные одной и той же паре вершин, называется параллельными или кратными. Граф, содержащий кратные ребра называется мультиграфом. Ребро, концевые вершины которого совпадают, называется петлей.

Граф называется конечным, если множество его элементов (вершин и ребер) конечно и пустым, если множество его вершин (а следовательно и ребер) пусто. Граф без петель и кратных ребер называется полным, если каждая пара вершин соединена ребром.

Дополнением графа G называется граф , имеющий те же вершины, что и G и содержащий только те ребра, которые нужно добавить к графу G, чтобы получить полный граф.

Каждому н-графу канонически соответствует орграф с тем же множеством вершин, в котором каждое ребро заменено двумя ориентированными ребрами, инцидентными тем же вершинам и имеющим противоположные направления.

Локальной степенью (или просто степенью) вершины vεV

н-графа G называют количество ребер ρ(V), инцидентных вершине v. В н-графе сумма степеней всех вершин равна удвоенному числу ребер m графа, т.е. четна (полагается, что в графе с петлями петля дает вклад 2 в степень вершины).

.

Следовательно, в н-графе число вершин нечетной степени четно.

Для вершин орграфа определяются две локальные степени:

1. ρ₁(v) – число ребер, выходящих из v.

2. ρ₂(v) – число ребер, входящих из v.

Петля дает вклад 1 в обе эти степени.

В орграфе суммы степеней всех вершин ρ₁(v) и ρ₂(v) равны количеству ребер m этого графа.

.

Графы G₁ и G₂ равны, т.е. G₁=G₂, если их множества вершин и ребер (выраженных через пары инцидентных им вершин) совпадают: V₁=V₂ и Е₁=Е₂.

Граф G считается полностью заданным в строгом смысле, если нумерации его вершин и ребер зафиксированы. Графы, отли­чающиеся только нумерацией вершин и ребер, называются изоморф­ными.

П ример 1.