Могут ли равносильные высказывания быть записаны в виде некоторой релейно-контактной схемы?

а) да;

б) нет;

в) могут, но не всегда.

Если исчисление противоречиво, имеет ли оно некоторую содержательную интерпретацию?

а) имеет;

б) не имеет;

в) имеет, но не всегда.

Если исчисление является полным, можно ли какую-либо невыводимую в этом исчислении формулу добавить к аксиомам так, чтобы исчисление осталось непротиворечивым?

а) можно;

б) нельзя;

в) можно, но не всегда.

Если система аксиом некоторого исчисления независима, можно ли какие-либо аксиомы вывести из других?

а) можно;

б) нельзя;

в) можно, но не всегда.

Тема 3.

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

Графы

Бинарное отношение на конечном множестве X есть ориентированный конечный граф (орграф) RÍX². Таким образом, всякий орграф определяется множествами:

X={x₁,x₂,…,x_n} – множеством вершин графа и множеством упорядоченных пар (кортежей);

R={<x_i,x_j>|x_iRx_j} – множеством дуг графа.

Общепринято обозначать орграфы в виде

G(X,U),

где X – множество вершин орграфа;

U – множество дуг орграфа, или в виде

G(x, гx),

где ГX = {Гx₁,Гx₂,…,Гx_n} – множество образов элементов множества X, т.е. отображение X в X, понимая термин отображение как точечно-множественное отображение.

Наряду с орграфами в приложениях рассматриваются неориентированные графы. Неориентированный граф является частным случаем орграфа, в котором для каждой дуги <x_i,x_j> существует ей параллельная и противоположно направленная дуга <x_j,x_i>, т.е. бинарное отношение R обладает свойством симметрии. Если, кроме того, бинарное отношение R обладает свойством рефлексивности, то соответствующий ему ориентированный граф есть орграф-толерантность, содержащий дуги типа петля <x_i,x_i> для всех вершин графа.

При геометрической реализации неориентированного графа вместо двух дуг <x_i,x_j> и <x_j,x_i>, соединяющих вершины x_i и x_j, употребляется одно ребро (x_i,x_j), не имеющее ориентации. На рис. 3.1.1 приведены геометрические реализации орграфов (слева) и их неориентированных аналогов – неориентированных графов (справа). G' (Х', U') есть подграф графа G(X, U), если X'ÍX; U'ÍU, т.е. подграф G' получим из графа G, если уберем какое-либо число вершин или ребер (дуг).

Две вершины графа называются смежными, если они соединены друг с другом.

Дуги называются смежными, если конец одной из них совпадает с началом другой.

Некоторая последовательности смежных дуг называется путем, а последовательность смежных ребер называется цепью.

Замкнутый путь называется контуром, а замкнутая цепь – циклом.

Сформулированные определения удобно представить в виде следующей таблицы:

Ориентированный граф	Неориентированный граф
Дуга	Ребро
Путь	Цепь
Контур	Цикл

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

Путь (цепь) называется простым, если он проходит через дуги графа по одному разу. В противном случае путь (цепь) называется составным. Аналогично определяются и простые контуры и циклы.

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

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

Аналогично определяются гамильтоновы и эйлеровы пути и контуры.

Симметричный граф Неориентированный граф

Граф-толерантность Неориентированный граф

Граф-толерантность Неориентированный граф

Граф-декартово произведение Неориентированный

(с полным насыщением) полный граф

Рис. 3.1.1