Понятие логического высказывания. Элементарное и сложное высказывание. Логические выражения (формулы) и логические операции. Диаграммы Венна.

Описание числовых множеств на плоскости.диаграммы Эйлера.

Диаграммы Эйлера – это графический способ представления операций над множествами, который появился раньше диаграмм Венна (Эйлер жил в XVIII веке, а математическая логика как наука сформировалась значительно позже).

Рассмотрим в качестве универсума множество всех точек плоскости. Введем декартову систему координат (X, Y).Если объект линейный, то множество описывается функцией y = f (x). Если объект площадной (полигон), то он описывается системой неравенств (предикатов) вида y>f(x), y³ f(x) (если граница включается) или y<f(x). Знак неравенства зависит от того, с какой стороны от ограничивающей функции лежат принадлежащие полигону точки. Например, множество точек, принадлежащих кругу A с центром в точке (a,b) и радиусом r, описывается неравенством (x-a)²+(y-b)²£r². Выполнение этого неравенства для некоторой точки (x, y) соответствует значению «true» предиката принадлежности «(x, y)ÎA».

AÈB AÇB

А/В АD В АDВ

Произвольное множество А отображается на плоскости фигурой, ограниченной замкнутой кривой f(x,y)=0. В случае круга – кривой (x-a)²+(y-b)²-r²=0. Эта часть плоскости – область значения true (1) для предиката «(x,y)ÎA». Часть плоскости за пределами круга соответствует, по определению, дополнению A до универсума. Если теперь изобразить таким же способом множества B,C,…, то, следуя предикатному определению операций над множествами, мы можем отобразить результаты различных операций, штрихуя или закрашивая области Q(A,B,C,…), в которых логическая функция от предикатных переменных принимает значение true (1). Штриховка или закрашивание применяется именно потому, что любая точка этой части плоскости принадлежит некоторому подмножеству Q(A,B,C,…), а таких точек бесконечно много.

Семейство подмножеств E={E_i},i=1,…,|E | называется покрытием множества M, если каждый элемент из M принадлежит хотя бы одному E_i. Семейство называется дизъюнктным или, иначе, разбиением M, если каждый элемент M принадлежит только одному E_i.

Пример 1. Описать заштрихованные части фигуры как операции над множествами точек плоскости.

Чтобы получить наиболее рациональное описание множеств, заметим, что ромб с вершинами в точках (3,0), (0,3), (-3,0), (0,-3) может быть аналитически описан уравнением | x| +| y |=3. Его внутренняя часть (с границей) определяется неравенством | x |+| y |£3. Соответственно, внутреннюю часть ромба с вершинами (1,0), (0,3), (-1,0), (0,-3) можно задать как |3 x |+| y |£3, а ромба с вершинами (3,0), (0,1), (-3,0), (0,-1) – как | x |+|3 y |£3. Три ромба, составляющие рассматриваемую фигуру, можно описать как множества:

A ={(x, y)| | x |+| y |£3}, B ={(x, y)| |3 x |+| y |£3, C ={(x, y)| | x |+|3 y |£3}.

При таком задании множеств-операндов незаштрихованную часть фигуры можно описать как (B È C)\(B Ç C), то есть как симметрическую разность B D C. Следовательно, заштрихованную часть Q данной фигуры наиболее коротким способом можно представить как Q = A \(B D C).

Ответ: Q = A \(B D C), где A ={(x, y)| | x |+| y |£3}, B ={(x, y)| |3 x |+| y |£3, C ={(x, y)| | x |+|3 y |£3}.

 

 

Подграфы и части. Операции над графами.

Подграфы. Основные определения.

Граф G ’ называется подграфом графа G, если V ’Ì V и E ’Ì E. Если в графе G ’ нет изолированных вершин, можно ограничиться только условием E ’Ì E.

G1

G2

G=G1ÈG2

G=G1+G2

G1

G2

Рис.3.5. Объединение и соединение графов.

Граф G ’ называется остовным подграфом графа G, если V ’= V. Ясно, Нуль-граф { V ’= V, E ’=0} тоже является остовным подграфом G.

Граф G ’ называется индуцированным подграфом на графе G, если " v _iÎ V ’, v _jÎ V ’ (v _i, v _j)Î E Þ(v _i, v _j)Î E ’.

Ясно, что если остовный подграф одновременно является индуцированным, то он совпадает с самим графом G.

G

G 1

G 2

Рис.3.4. Подграфы полного графа G на 6 вершинах: G1 – остовный подграф, G2 – индуцированный подграф на 4 вершинах.

Операции над графами.

Поскольку граф - это однородное бинарное отношение на V², то, казалось бы, операции над графами будут те же самые, что и для отношений. Давайте посмотрим, что происходит на самом деле. Во-первых, чтобы выполнять некоторые операции, нам нужно ввести понятие «универсума». Если мы примем за универсум полный неориентированный граф на p вершинах, то относительно операций над ребрами, то есть на множестве E, мы можем построить булеву алгебру (вспомним представление графов матрицей смежности). Минимальным элементом у нас тогда будет нуль-граф, максимальным – полный неориентированный граф, и можете сами проверить, что все законы логики (то есть соответствующие им свойства операций над множествами ребер) будут выполняться. Но поскольку граф, по определению, - конструкция из двух множеств, операции над графами рассматриваются не только как операции на множестве ребер, но и как операции на множестве вершин.

Начнем с операций добавления и удаления элементов графа.

Удаление ребра e приводит к образованию графа G ’, где V ’= V & E ’= E \{ e }. Ясно, что добавление ребра образует граф G ’, где V ’= V & E ’= E È{ e }. То есть множество–носитель отношения не меняется. А что же происходит при операциях с вершинами?

Удаление вершины v приводит к образованию графа G ’, где V ’= V \{ v } & E ’= E \{ e _i | e _i=(v _i, v) Ú e _i=(v, v _i)}. Но здесь заметим, что для полных графов K ₃\{ v }= K ₂, K ₄\{ v }= K ₃,…, K _n\{ v }= K _n-1, n =| V | (попробуйте сами объяснить, почему).

Посмотрим теперь, как добавлять элементы графа. Здесь тоже есть нюанс.

Просто добавление вершины v – это расширение множества V: V ’= V È{ v }. Но есть еще операция стягивания графа G к вершине v. В результате этой операции образуется граф G ’, где V ’= V È{ v } & E ’= E È{ e =(v, v _i), i=1,…,| V |}.

Таким образом, для полного графа операция стягивания является обратной к операции удаления вершины. Но только для полного графа.

Теперь перейдем от операций с элементами графа к операциям над графами в целом.

Просто под дополнением графа G подразумевается дополнение его до полного графа K_p, где p =|V|. Употребляется также дополнение графа G ’ до графа G. Его обозначают G - G ’. Точно так же, как мы определяли дополнение бинарного отношения. А вот с другими операциями дело обстоит иначе.

Объединением графов G ₁È G ₂ при V ₁Ç V ₂=Æ называется граф G ’, где V ’= V ₁È V ₂ & E ’= E ₁È E ₂. В случае V ₁Ç V ₂=Æ операцию объединения графов называют прямой суммой.

В принципе, операцию объединения нетрудно распространить и на случай V ₁Ç V ₂¹Æ, обозначив V ₃= V ₁Ç V ₂. Тогда мы получаем, что V ’= V ₃È(V ₁- V ₃)È(V ₂- V ₃), где (V ₁- V ₃)Ç(V ₂- V ₃)=Æ. На V ₃ мы выполняем объединение как операцию над бинарными отношениями, а на (V ₁- V ₃)Ç(V ₂- V ₃) - по правилу объединения графов.

Заметим, что в данном случае мы рассматривали графы с фиксированной нумерацией вершин, то есть без учета изоморфизма. Но свойства графов, в том числе и свойства операций, мы обязаны рассматривать для всего класса изоморфных графов и тогда должны предполагать, что V ₁Ç V ₂=Æ.

Соединением графов G ₁+ G ₂ при V ₁Ç V ₂=Æ называется граф G ’, где V ’= V ₁È V ₂ & E ’= E ₁È E ₂.{ e _ij=(v _i, v _j), i=1,…, p ₁, j=1,…, p ₂}.

 

Заметим, что в результате соединения полных графов мы опять получаем полный граф. А вот в результате соединения двух нуль-графов мы получаем очень интересную конструкцию, которая называется двудольным графом. Причем не просто двудольным, а так называемым полным двудольным графом. Такие графы обозначают K_m,n, где m = p ₁, n = p ₂.

 

 

14. Маршруты, цепи, циклы. Понятие связности и достижимости. Взаимосвязь числа компонент связности с основными инвариантами графа. Графы и бинарные отношения. Транзитивное замыкание.

Маршрутом в графе называется любая последовательность попарно смежных (в орграфе – непосредственно достижимых) вершин { v ₀, v ₁,…, v _k}. В маршруте как вершины, так и ребра могут повторяться. Если v ₀ = v _k, то маршрут называется замкнутым, в противном случае – открытым.

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

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

Чтобы решать любые задачи обхода графа, необходимо ввести понятие связности.

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

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

Для ориентированных графов понятие цепи, следовательно, и понятие связности можно ввести только при снятии ориентации ребер. Если же учитывать ориентацию, то мы обязаны будем ввести какие-то дополнительные понятия. В этом случае нам придется рассматривать не цепи, а пути.

Путем в орграфе называется последовательность вершин, непосредственно достижимых одна из другой. Замкнутый путь называется контуром.

Покажем, что связность есть отношение эквивалентности. Связность рассматривается как достижимость одной вершины из другой при отсутствии ориентации ребер, то есть (u, v)=(v, u) " u, v Î V.

Топологическим минором графа G называется граф G ’, который получается в результате склеивания некоторых смежных вершин из G. Операция склеивания вершин v_i и v_j называется еще стягиванием ребра e =(v_i, v_j). При стягивании ребра (v_i, v_j) все отношения смежности, которые были у вершин v_i и v_j, переходят к новой вершине v (рис.3.6). Но при этом если для какой-то вершины v _k существовала пара ребер (v_i, v_k) и (v_j, v_k), то эта пара превращается в одно ребро (v, v_k).

Рис.3.6. Стягивание ребра (v i, v j). Результат стягивания показан справа.

Ясно, что если мы стягиваем неориентированное ребро, то мы не теряем никакой информации о связности вершин графа, поскольку можем пройти по ребру в любом направлении. А вот если мы стянем ориентированное ребро, то здесь мы можем либо потерять некоторые пути, либо получить лишние. Поэтому говорить про достижимость вершины самой из себя на орграфе некорректно. Под рефлексивностью тогда следует понимать возможность опять вернуться в эту вершину после выхода из нее. Т.е. в графе должен существовать замкнутый контур, включающий эту вершину. Кстати, в этом случае мы, возможно, кое-что сможем и склеить без потери информации.

Свойства отношения «связность».

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

Симметричность. Если из v_i можно попасть в v_j, то по любой из цепей, соединяющих v_i и v_j, можно попасть обратно.

Транзитивность. Если из v_i можно пройти в v_j, а из v_j в v_k, то через v_j можно пройти из v_i в v_k.

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

Орграф G_d называется связным, если связен граф, который получается из G_d при снятии с ребер ориентации. То есть если между каждой парой вершин существует либо путь S (v _i, v _j), либо путь S (v _j, v _i).

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

Матрица достижимости и транзитивное замыкание.

Матрицей достижимости называется матрица M размерности p ´ p, где m_ij =1, если v_i достижима из v_j, и m_ij =0 в противном случае.

Для связного неориентированного графа такая матрица будет состоять из одних единиц. Причем по диагонали тоже будут стоять единицы, потому что, походив-походив по графу, мы всегда можем вернуться назад, хотя бы тем же самым путем (не так, как в задаче о 7 мостах). А вот для ориентированного графа матрица M будет другой. И по ее виду мы можем понять, какой тип отношения порядка задает граф G_d. Если по диагонали будут одни нули, значит, это отношение строгого частичного порядка, поскольку имеет место антирефлексивность. В противном случае мы имеем отношение нестрогого частичного порядка.

Определяя транзитивность, мы писали такое выражение R o R Ì R. То есть отношение транзитивно, если оно замкнуто относительно операции композиции. R образует полугруппу относительно операции композиции. Если отношение задано бинарной матрицей A размерности n ´ n, то операция композиции есть логическое произведение A × A.

A × A для матриц непосредственной достижимости- это матрица путей, состоящих из двух ребер, то есть матрица достижимости одной вершины из другой за два шага. Тогда A × A × A есть матрица достижимости одной вершины из другой за три шага, и так далее. Ясно, что таких шагов t будет не более чем p -1, причем t = p -1, только если диаметр графа есть p -1. Значит, в общем случае, чтобы получить полную матрицу достижимости, мы должны объединить все пути длиной от 1 до p -1 ребра. Итак, имеем: .

Вспомним что такое замыкание отношения относительно некоторого свойства (Пусть R и R’ – однородные отношения на множестве A. Отношение R’ называется замыканием отношения R относительно свойства C, если 1) R’ обладает свойством C; 2) R является подмножеством R’: RÌR’; 3) R является наименьшим среди всех R’’, таких что имеет место C(R’’) и RÌ R’’.)

и обратим внимание, что здесь мы как раз и имеем случай такого замыкания. Матрица M объединяет все варианты путей - отношений достижимости между парами вершин, то есть является надмножеством над всеми возможными путями - отношениями. При этом она не включает ничего лишнего, только простые цепи. То есть это минимальное надмножество, обладающее свойством транзитивности. Поэтому матрицу M называют иначе транзитивным замыканием отношения достижимости.

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

Рис.3.7. Граф, состоящий из трех компонент связности.

К аждый граф единственным способом представим в виде прямой суммы своих связных компонент.

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

Число компонент связности k является инвариантом графа, так же, как число вершин p и число ребер q. Если k =1, то мы имеем просто связный граф.

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

Теорема. Пусть p – число вершин, q – число ребер, k - число компонент связности графа. Тогда

Докажем левую часть отношения. Для того чтобы соединить p точек, нужно, по меньшей мере, p -1 ребро, то есть q ³ p-1. Если в графе k компонент связности, каждая из которых содержит p _i вершин (i=1,…, k), то, просуммировав неравенства для ребер по всем k компонентам, получаем искомую нижнюю оценку.

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

Теперь осталось выяснить, при каком числе k общее число ребер будет максимально. В результате операции соединения двух полных графов у нас опять получается полный граф. Такое соединение добавляет D q = p ₁× p ₂/2 ребер. Общее число ребер в двух соединяемых связных графах равно q =1/2[(p ₁+ p ₂)(p ₁+ p ₂-1)- p ₁× p ₂], следовательно, q будет тем больше, чем меньше величина D q = p ₁× p ₂/2 - число добавляемых ребер. Минимальное же количество ребер добавляется при добавлении одной вершины: p ₂=1, D q=p ₁ - 1. То есть максимальное количество ребер в графе из k компонент будет тогда, когда одна компонента – полный граф, а остальные – изолированные вершины. Число ребер в таком графе q =(p - k)(p - k +1)/2. Отсюда имеем искомое неравенство.

Следствие. Если q >(p -1)(p -2)/2, то граф связен.

 

 

Теорема Менгера.

рассмотрим задачу. Менеджер фирмы, находящейся в городе A, собирается лететь на деловые переговоры в город F, с которым нет прямого воздушного сообщения. Учитывая плохие погодные условия, менеджер выписал для себя все возможные варианты перелетов с пересадками в городах В, С, D, E, G, H, K, L, M, в результате чего получился граф, представленный следующими списками смежности.

А: B,C,G,K,M; B: C,H; C: E,G,M; D: F,H,M; E: C,F,L; F: D,E,H,L,M; G: A,C,L; H: B,D,F,K; K: A,H,L; L: E,F,G,K; M: A,D,F.

Попадет ли менеджер на переговоры, если перед его вылетом в трех городах из списка все рейсы были отменены по погодным условиям?

Поставленное условие означает, что закрытые аэропорты – это вершины, удаление которых разбивает граф на две компоненты связности, причем пункты вылета и назначения находятся в разных компонентах.

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

Определение. Пусть u,v – две несмежные вершины связного графа G (V, E). Две цепи S ₁(u, v), S ₂(u, v) называются вершинно непересекающимися, если они у них нет общих вершин, кроме u и v. Соответственно, цепи S ₁(u,v), S ₂(u,v) называются реберно непересекающимися, если у них нет общих ребер.

Говорят, что множество G ’(u,v)Ì G разделяет две вершины u,v, если эти вершины принадлежат разным компонентам связности G ₁Ì G, G ₂Ì G, где G ₁È G ₂È G ’= G.

Здесь, как и раньше, следует выделить два вида разделяющих множеств.

Определение. Разделяющим множеством вершин для пары u, v называется множество R (u,v)Ì V, такое, что u Î G ₁, vÎ G ₂, V ₁È V ₂È R = V, E ₁È E ₂È E ’= E, где E ’= E \(E ₁È E ₂). Соответственно, разделяющим множеством ребер называется P (u, v), такое, что u Î G ₁, v Î G ₂, V ₁È V ₂= V, E ₁È E ₂È E ’= E, где E ’= E \(E ₁È E ₂). Разделяющее множество ребер обычно называют разрезом.

Теорему Менгера сформулируем без доказательства, его можно посмотреть, например, в [1]. Эта теорема может быть сформулирована как в вершинной, так и в реберной форме.

Теорема Менгера в вершинной форме. Мощность наименьшего разделяющего множества вершин R (u, v) для пары вершин u и v равна максимальному количеству вершинно непересекающихся простых цепей S (u,v): min| R (u,v)|=max | S _v(u,v)|.

Теорема Менгера в реберной форме. Мощность наименьшего разреза P (u,v) для пары вершин u и v равна максимальному количеству реберно непересекающихся простых цепей S (u,v): min| P (u,v)|=max | S _e(u,v)|.

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

Итак, для решения задачи про аэропорты нам не нужно перебирать все возможные варианты перелета. Достаточно найти максимальное количество вершинно непересекающихся простых цепей между пунктами A и F. Давайте попробуем это сделать.

Во-первых, заметим, что количество таких цепей не может быть больше, чем число вершин, смежных с вершиной A, и не может быть больше, чем число вершин, смежных с вершиной F. В противном случае цепи неизбежно будут пересекаться по вершинам. Итак, | S |<min(r(A),r(F))=5, и в данном случае обе эти вершины имеют максимальную степень. Для дальнейшего анализа можно воспользоваться схемой поиска в ширину, начиная с концевой вершины маршрута, имеющей минимальную степень. Для нашего случая схема поиска в ширину будет иметь следующий вид (рис.3.11).

В этой схеме уже имеется одна простая цепь (A,M,F). Еще три цепи получаем непосредственным переходом в F из смежных с ней вершин H,E,L. Из вершины К мы не можем непосредственно попасть в F, а все остальные вершины уже задействованы в цепях. Таким образом, в рассматриваемом графе существует 4 вершинно непересекающихся простых цепи. И этого достаточно, чтобы менеджер смог добраться на переговоры, так как при любых трех закрытых аэропортах у него всегда останется один запасной вариант.

 

26. Независимые и покрывающие множества вершин и ребер. Теорема Галаи.

Мы уже рассматривали некоторые задачи о покрытиях. Например, говорили о том, как покрыть граф минимальным числом простых цепей, и это была задача на построение эйлерова цикла в дополненном фиктивными ребрами графе. Теперь мы рассмотрим задачу, как описать граф минимальным количеством вершин, чтобы сохранились все связи. Это может быть, например, задача оптимизации сетевой базы данных. Другим примером практической задачи может быть задача о расположении ретрансляторов в телекоммуникационных сетях. Задачи такого типа часто иллюстрируют головоломкой о том, как расставить на шахматной доске заданное количество фигур, чтобы они били все клетки.

Мы знаем, что при удалении вершины из графа вместе с ней уходят и все инцидентные ей ребра. Будем поэтому говорить, что вершина покрывает эти ребра. И, соответственно, будем говорить, что ребро ( i,j ) покрывает вершины i,j, если эти вершины являются его концами.

Определение. Множество вершин, покрывающее все ребра графа G, называется вершинным покрытием графа G. Аналогично, множество ребер, покрывающих все вершины графа G, называется реберным покрытием G.

Рис. 3.29. Графы с различными покрывающими множествами вершин и ребер.

Нетрудно заметить, что мощность вершинного покрытия в связном графе будет меньше числа вершин. Чтобы покрыть все ребра, нам понадобится тем больше вершин, чем меньше ребер покрывает каждая вершина. Больше всего вершин потребуется для покрытия простой цепи, где q = p- 1. А вот мощность реберного покрытия не всегда меньше числа ребер. На рис.3.29 показаны два графа с различными вершинными и реберными покрытиями. В цикле слева вершинное покрытие состоит из трех вершин (через одну), и реберное покрытие также состоит из трех ребер (через одно). В звезде справа вершинное покрытие состоит всего из одной центральной вершины, а реберное покрытие включает все ребра графа.

 

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

Введем обозначения: a₀ – мощность минимального вершинного покрытия (число вершинного покрытия), a₁ – мощность минимального реберного покрытия (число реберного покрытия).

Теперь вернемся к примеру со звездой (рис. 3.29), как к критическому случаю. Обратите внимание, что здесь покрывающее множество состоит из одной вершины именно потому, что между другими вершинами нет ребер. Если бы было хотя бы одно такое ребро, было бы другое минимальное покрывающее множество. Чтобы сделать какие-то выводы относительно такой ситуации, введем еще одно понятие.

Множество вершин называется независимым, если никакие две вершины в нем не смежны. Соответственно, множество ребер называется независимым, если в нем никакие два ребра не имеют общего конца. Мощность максимального независимого множества вершин в графе называется вершинным числом независимости и обозначается b₀. Мощность максимального независимого множества ребер называется реберным числом независимости и обозначается b₁.

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

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

Теорема Галаи. Для любого нетривиального связного графа справедливо следующее соотношение

a₀+b₀=a₁+b₁=p.

Понятие логического высказывания. Элементарное и сложное высказывание. Логические выражения (формулы) и логические операции. Диаграммы Венна.

Высказывание- повествовательное предложение (утверждение), которое может быть либо истинным, либо ложным, но не то и другое вместе. Заключение, которое мы делаем относительно того, истинно или ложно высказывание, называется его истинностным значением.

Для истинностных значений высказываний используются обозначения И (истина), Л (ложь); в компьютерных приложениях и языках программирования используются обозначения true, false или, соответственно, «1», «0».

Элементарное (простое) -высказывание, которое нельзя разбить на более простые без потери смысла, следовательно, истинностного значения. Если же высказывание расчленяется на составляющие, которые также имеют смысл и, следовательно, истинностное значение, оно называется сложным. Такое высказывание будет истинным или ложным в зависимости от значений входящих в него элементарных высказываний.

В математической логике элементарные высказывания называют логическими переменными. Логические переменные обычно обозначают прописными латинскими буквами: a,b,c,… Связки, образующие сложное высказывание, называются позиционными связками или логическими операциями.

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

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

Табличную форму представления называют таблицами истинности. Каждая строка таблицы содержит упорядоченный набор значений всех переменных и соответствующее ему значение функции.

x 1	x 2	…	x n	f (x 1, x 2,…, x n)
		…		f (0,0,…,0)
		…		f (0,0,…,1)
…	…	…	…	…
		…		f (1,1,…,1)

 

С помощью n двоичных разрядов можно представить 2ⁿ различных чисел. Следовательно, для n логических переменных таких наборов будет 2ⁿ.

Графическим способом представления сложных высказываний через элементарные являются диаграммы Венна.

В диаграмме Венна каждому элементарному высказыванию сопоставляется замкнутый контур (рис.1.1). Внутри этого контура высказывание считается истинным, за пределами контура – ложным. Контуры для n элементарных высказываний, входящих в сложное, изображаются так, чтобы все их возможные перекрытия давали полный набор всех возможных комбинаций значений элементарных высказываний, то есть 2ⁿ. На плоскости таким способом можно наглядно отобразить значения логических формул только от трех переменных. (Для четырех простых контуров мы уже никак не получим ровно 2⁴ областей)

Рис.1.1. Диаграмма Венна.

Область пересечения контуров, в которой сложное высказывание, состоящее из обозначенных контурами элементарных высказываний истинно, в диаграмме Венна обозначается точкой. На рис. 1.1 показана диаграмма Венна для сложного высказывания, включающего только две логические переменные – a,b. Здесь сложное высказывание истинно, только когда истинны обе переменные: a=1,b=1.

Если сложное высказывание истинно при нулевых значениях всех переменных, точка ставится за пределами всех контуров.

Логические операции.

Самой простой логической операцией является отрицание того утверждения, которому соответствует элементарное высказывание. Отрицание обозначается символами

Поскольку операция отрицания применяется только к одной переменной, она называется одноместной или унарной. Если a= 1, то Ø a= 0 и, наоборот, если a= 0, то Ø a= 1.

Простейшие из сложных высказываний, соответствующие привычным для нас конструкциям речи, описываются операциями с двумя переменными. Они называются двухместными или бинарными.

Основными бинарными операциями принято считать следующие.

1. Конъюнкция (логическое умножение). Соответствует речевой связке «и». В математической логике связка «и» означает только одновременное выполнение каких-либо условий или одновременное осуществление каких-либо событий. Конъюнкция обозначается a×b, a & b, a Ù b.

Таблица истинности для конъюнкции.Диаграмма Венна

a	b

a

b

×

для конъюнкции.

Поскольку конъюнкция принимает значение 1 только при a = b =1, в двоичной системе счисления эту операцию можно рассматривать как min(a,b).

2. Дизъюнкция (логическое сложение). Соответствует связке «или» и обозначает объединение каких-либо условий или событий. Т.е. сложное высказывание является истинным, когда истинно хотя бы одно из элементарных высказываний. Дизъюнкция обозначается a Ú b.

Таблица истинности для дизъюнкции. Диаграмма Венна

a	b

для дизъюнкции.

 

a.

b.

..

 

Поскольку дизъюнкция принимает значение 0 только при a = b =0, в двоичной системе счисления эту операцию можно рассматривать как max(a,b).

3. Импликация (следование, достаточное условие в доказательствах теорем). Соответствует связке «если …, то …». Обозначается a ® b.

Определение значений импликации в зависимости от значений a и b основывается на следующем соображении. Из ложной посылки может следовать как истина, так и ложь. Но из истины всегда следует только истина. Поэтому импликация принимает значе