14. Эквивалентность формул.

Формулы φ(x₁,…,x_n) и ψ(x₁,…,x_n) называются эквивалентными (φ≈ψ), если совпадают их таблицы истинности, т.е. совпадают представляемые этими формулами функции.

Основные эквивалентности:

1. ассоциативность

2. Коммутативность:

3. Идемпотентность:

4. Дистрибутивность: ,

5. Поглощение:

6. Законы де Моргана:

7. Двойное отрицание:

8. 

9. 

10. 

11. 

Формула φ(x₁,…,x_n) называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значения 1 (соответственно 0).

Формула φ(x₁,…,x_n) называется тождественно истинной, или тавтологией (тождественно ложной, или противоречием), если эта формула принимает значение 1 (соотв-нно 0) при всех наборах значений переменных.

Утверждение: Если формула φ₁ тождественно истинна, φ₀ – тождественно ложна, то справедливы следующие эквивалентности:

1) , 2) ,

3) , 4) ,

5) , 6) ,

7) ,8) , 9) .

36. Планарные графы.

Критерий планарности: Граф G планарен тогда и только тогда, когда G не содержит подграфа, гомеоморфного K₅ или K_3,3 (или подграфов, стягиваемых к K₅ или K_3,3, т.е. получаемых последовательным отождествлением связанных друг с другом вершин).

Теорема: Любой конечный граф может быть расположен в трехмерном пространстве без пересечения ребер.

Толщина графа – минимальное количество плоскостей, в которых можно осуществить раскладку графа без пересечений.

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

27. Определение графа. Виды и способы задания графов.

Графом называется алгебраическая система G=<M,R>, R – двухместный предикатный символ. М называются вершинами графа G, а элементы бинарного отношения - дугами, являются пары вершин . дуга (a,b) называется исходящей из вершины a и заходящей в вершину b.

Мультиграфом G называется тройка <M,U,P>, в которой M – множество вершин, U – множество дуг, а - трехместный предикат, представляемый образом: , когда дуга u исходит из вершины a и заходит в вершину b.

Граф G=<M,R> называется ориентированным (орграфом), если найдется дуга такая, что .

Граф G называется неориентированным (неорграфом), если отношение R симметрично, т.е. из следует .

Если одновременно пары (a,b) и (b,a) принадлежат R, то эти дуги можно представить множеством [a,b]={(a,b),(b,a)}, называемым ребром, соединяющим вершины a и b.

Пусть G=<M,R> - граф, Матрицей смежности A_G=(A_ij) графа G называется матрица , определенная следующим образом: . Если G -мультиграф, то в матрице смежности элемент A_ij равен числу дуг, исходящих из вершины a_i и заходящих в вершину a_j.

Петлей в графе G называется дуга, соединяющая вершину саму с собой.

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

Матрицей инцидентности B_G=(B_ij) мультиграфа G называется матрица размера m на n (где m – количество дуг в графе), определяемая по правилу: Теорема: Мультиграфы G и G’ изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга некоторыми перестановками строк и столбцов.

Информацию о весах дуг во взвешенном графе можно представить в виде матрицы весов W=(w_ij), где w_ij – вес дуги (a_i,a_j), если эта дуга существует и ∞ в противном случае.