($ х)(А (х) & B) º ($ x) A (x) & B; (" x)(A (x) & B) º (" x) A (x) & B;
($ х)(А (х) Ú B) º ($ x) A (x) Ú B; (" x)(A (x) Ú B) º (" x) A (x) Ú B;
3) Перестановка одноименных кванторов.
(" y)(" x) A (x,y) º (" x)(" y) A (x,y); ($ y)($ x) A (x,y) º ($ x)($ y) A (x,y);
4) Переименование связанных переменных. Если заменить связанную переменную формулы А другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора получаем формулу, равносильную А.
Исчисление предикатов базируется на приведенных выше свойствах и правилах, называемых аксиомами.
Какими бы ни были формулы А и В для них справедливы следующие аксиомы:
1) A Þ (B Þ A);
2) (A Þ (B Þ C)) Þ ((A Þ B) Þ (A Þ C));
3) (ØB Þ ØA) Þ ((ØB Þ A) Þ B);
4) (" xi) A (xi) Þ A (xj), где формула А (хi) не содержит переменной xi.
5) A (xi) Þ ($ xj) A (xj), где формула А (хi) не содержит переменной xi.
Конечные графы и сети. Основные определения.
Определение. Если на плоскости задать конечное множество V точек и конечный набор линий Х, соединяющих некоторые пары из точек V, то полученная совокупность точек и линий будет называться графом.
При этом элементы множества V называются вершинами графа, а элементы множества Х – ребрами.
В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями. Одинаковые пары в множестве Х называются кратными (или параллельными) ребрами. Количество одинаковых пар
(v, w) в Х называется кратностью ребра (v, w).
Множество V и набор Х определяют граф с кратными ребрами – псевдограф.
G = (V, X)
Псевдограф без петель называется мультиграфом.
Если в наборе Х ни одна пара не встречается более одного раза, то мультиграф называется графом.
Если пары в наборе Х являются упорядоченными, то граф называется ориентированным или орграфом.
Графу соответствует геометрическая конфигурация. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины.
Определение. Если х = { v, w } – ребро графа, то вершины v, w называются концами ребра х.
Если х = (v, w) – дуга орграфа, то вершина v – начало, а вершина w – конец дуги х.
Определение. Вершины v, w графа G = (V, X) называются смежными, если { v,w }ÎX. Два ребра называются смежными, если они имеют общюю вершину.
Определение. Степенью вершины графа называется число ребер, которым эта вершина принадлежит. Вершина называется изолированной, если если ее степень равна единице и висячей, если ее степень равна нулю.
Определение. Графы G1(V1, X1) и G2(V2, X2) называются изоморфмными, если существует взаимно однозначное отображение j: V1 ® V2, сохраняющее смежность.
Определение. Маршрутом (путем) для графа G(V, X) называется последовательность v1x1v2x2v3…xkvk+1. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиной маршрута (пути).
Определение. Незамкнутый маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью.
Определение. Замкнутый маршрут (путь) называется циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.
Матрицы графов.
Пусть D = (V, X) – орграф, где V = {v1, …, vn}, X = {x1, …, xm}.
Определение. Матрицей смежности орграфа D называется квадратичная матрица A(D) = [aij] порядка п, у которой
Определение. Если вершина v является крнцом ребра х, то говорят, что v и х – инциндентны.
Определение. Матрицей инцидентности орграфа D называется матрица размерности п ´ т B(D) = [bij], у которой
Пример. Записать матрицы смежности и инцидентности для графа, изображенного на рисунке.
x1
v1 x4 v2
x2
x3
v3
Составим матрицу смежности:
| v1 | v2 | v3 | |
| v1 | |||
| v2 | |||
| v3 |
Т.е. 
- матрица смежности.
Матрица инцидентности:
| x1 | x2 | x3 | x4 | |
| v1 | -1 | |||
| v2 | -1 | -1 | ||
| v3 | -1 |
Т.е. 
Если граф имеет кратные дуги (ребра), то в матрице смежности принимается aij=k, где k – кратность дуги (ребра).
С помощью матриц смежности и инцидентности всегда можно полностью определить граф и все его компоненты. Такой метод задания графов очень удобен для обработки данных на ЭВМ.
Пример. Задана симметрическая матрица Q неотрицательных чисел. Нарисовать на плоскости граф G(V, X), имеющий заданную матицу Q своей матрицей смежности. Найти матрицу инцидентности R графа G. Нарисовать также орграф 
, имеющий матрицу смежности Q, определить его матрицу инцидентности С.
x4
x3
v2
x2 x5
x6
x1 v1 v3 x7 x8
x10
x11 x9
v4
Составим матрицу инцидентности:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | |
| v1 | |||||||||||
| v2 | |||||||||||
| v3 | |||||||||||
| v4 |
Итого: 
Построим теперь ориентированный граф с заданной матрицей смежности.
x4
x5
 |
v2
x2 x7
х3 x6
x1 v1 х8 v3 x10 x11
х9
х17 х15 x14
x16 х13 x12
v4
Составим матрицу инцидентности для ориентированного графа.
Элемент матрицы равен 1, если точка является концом дуги, -1 – если началом дуги, если дуга является петлей, элемент матрицы запишем как ±1.
Таким образом, операции с графами можно свести к операциям с их матрицами.