Текст книги "Математический аппарат инженера"

Автор книги: Виталий Сигорский

сообщить о нарушении

Текущая страница: 4 (всего у книги 8 страниц)

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

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

6. Инцидентность. Если вершина v_i, является концом ребра e_k то говорят, что они инцидентны: вершина v_i инцидентна ребру e_k и ребро e_k, инцидентно вершине v_i. В то время как смежность представляет собой отношение между однородными объектами (вершинами), инцидентность – это отношение между разнородными объектами (вершинами и ребрами). При рассмотрении орграфов различают положительную инцидентность (дуга исходит из вершины) и отрицательную инцидентность (дуга заходит в вершину).

Рассматривая инцидентность вершин и ребер (p и q) – графа, можно представить его матрицей инцидентности размера p × q, строки которой соответствуют вершинам, а столбы – ребрам. Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-элемент равен 1, если вершина v_i, инцидентна ребру e_i, и равен нулю, если v_i, и e_i, не инцидентны.

– 50 -

В случае орграфа ненулевой ij-элемент равен 1, если v_i начальная вершина дуги e_i, и равен – 1, если v_i – конечная вершина дуги e_i.

Например, матрица инцидентности графа, приведенного на Рис. 9, а, имеет вид:

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

Рис. 10. Изоморфные графы

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

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

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

– 51 -

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

8. Маршруты. Нередко задачи на графах требуют выделения различных маршрутов, обладающих определенными свойствами и характеристиками. Маршрут длины m определяется как последовательность т ребер графа (не обязательно различных) таких, что граничные вершины двух соседних ребер совпадают. Маршрут проходит и через все вершины, инцидентные входящим в него ребрам. Примерами маршрутов на графе Рис. 9, а могут служить последовательности ( e₁, e₃, e₂, e₃, e₅ ), ( e₅, e₆, e₄, e₄). Первый маршрут проходит через последовательность вершин ( v₁, v₂, v₃, v₂, v₃, v₅ ) и соединяет вершины v₁ и v₅ a второй – через последовательность вершин ( v₃, v₅, v₅, v₂, v₅ ) и соединяет вершины v₃ и v₅. Замкнутый маршрут приводит в ту же вершину, из которой он начался.

Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью. Замкнутая цепь называется циклом, а простая цепь – простым циклом. Так, на графе Рис. 9, а ( e₂, e₅, e₆ ) – цепь, ( e₁, e₂, e₅ ) -простая цепь, ( e₂, e₃, e₄, e₅ ) – цикл, ( e₂, e₄, e₅ ) – простой цикл.

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

Ориентированные маршруты на орграфе определяются аналогично с той разницей, что начальная вершина каждой последующей дуги маршрута должна совпадать с конечной вершиной предыдущей дуги. Иначе говоря, движение по маршруту допускается только в направлениях, указанных стрелками. Маршрут, не содержащий повторяющихся дуг, называется путем, а не содержащий повторяющихся вершин – простым путем. Замкнутый путь называется контуром, а простой замкнутый путь – простым контуром. Граф (орграф) называется циклическим (контурным), если он содержит хотя бы один цикл (контур), в противном случае он называется ациклическим (бесконтурным).

– 52 -

Понятия цепи и цикла применимы и к ориентированным графам. При этом направления дуг не учитываются, т. е. по существу вместо орграфа рассматривают неориентированный соотнесенный ему граф.

9. Части графа. Граф G' = (V', Е') является частью графа G = (V, Е), если V' ⊂ V и Е' ⊂ Е, т. е. граф содержит все вершины и ребра любой его части. Часть, которая, наряду с некоторым подмножеством ребер графа, содержит и все инцидентные им вершины, называется подграфом. Часть, которая наряду с некоторым подмножеством ребер графа, содержит все вершины графа (V’=V, Е' ⊂ Е), называется суграфом. Рассмотренные графы показаны на Рис. 11.

Рис. 11. Граф и его части:

а – граф; б – часть графа; в – подграф; г – суграф.

Исходный граф по отношению к его подграфу называют надграфом, а по отношению к суграфу – сверхграфом. Совокупность всех ребер графа, не принадлежащих его подграфу (вместе с инцидентными вершинами), образует дополнение подграфа. Говорят, что подграфы G' = (V', Е') и G" = (V", Е") разделены ребрами, если они не имеют общих ребер (Е' ∩ Е" =∅) и разделены вершинами, если у них нет общих вершин (V' ∩ V" =∅).

10. Связность. Две вершины графа называют связанными, если существует маршрут, соединяющий эти вершины. Граф, любая пара вершин которого связана, называют связным графом. Очевидно, в связном графе между любыми двумя вершинами существует простая цепь, так как из связывающего их маршрута всегда можно удалить циклический участок, проходящий через некоторую вершину более одного раза (Рис. 12, где маршрут между вершинами v_i и v_j, изображен жирными линиями).

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

– 53 -

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

Часто отношение связности усложняется дополнительными условиями. Граф называют циклически связным, если любые две различные вершины содержатся в цикле (например, граф на Рис. 11, а циклически связный, а граф на Рис. 12 – нет, так как вершина и, не содержится ни в каком цикле с другими вершинами). Граф называют R – связным, если любая пара различных вершин связана, по крайней мере R цепями, которые не имеют общих вершин (кроме начальной и конечной). Так, граф на Рис. 11, а двусвязный, а на Рис. 12 – односвязный.

Рис. 12. Связный граф.

Рис. 13. Несвязный граф, состоящий из трех компонент (G₁, G₂, G₃

Связность ориентированных графов определяется так же, как и для неориентированных (без учета направлений дуг). Специфичным для орграфа (или смешанного графа) является понятие сильной связности. Орграф называют сильно связным, если для любой пары его вершин v_i и v_j существует путь из v_i в v_j и из v_j в v_i , (например, граф на Рис. 8, а сильно связный). Граф, представляющий план города с односторонним движением по некоторым улицам, должен быть сильно связным, так как в противном случае нашлись бы вершины (площади и перекрестки), между которыми нельзя было бы проехать по городу без нарушения правил движения.

11. Разделимость. Связный граф может быть разделен на несвязные подграфы удалением из него некоторых вершин и ребер (при удалении вершин исключаются и все инцидентные им ребра, а при удалении ребер вершины сохраняются). Если существует такая вершина, удаление которой превращает связный граф (или компоненту несвязного графа) в несвязный, то она называется точкой сочленения (Рис. 14, а). Ребро с такими же свойствами называется мостом (Рис. 14, б). Ясно, что при наличии моста в графе имеется, по крайней мере, две точки сочленения.

– 54 -

Граф называется неразделимым, если он связный и не имеет точек сочленения (например, граф на Рис. 11, а неразделим). Граф, имеющий хотя бы одну точку сочленения, является разделимым и называется сепарабельным. Он разбивается на блоки, каждый из котооых представляет собой максимальный неразделимый подграф (на Рис. 14, в показаны блоки B₁,B₂,B₃ графа Рис. 14, б).

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

Рис. 14. Разделимые графы:

а – с точкой сочленения; б – с мостом; в – блоки B₁ – B₃ графа с мостом

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

12. Деревья и лес.Особый интерес представляют связные ациклические графы, называемые деревьями. Дерево на множестве р вершин всегда содержит q = р – 1 ребер, т. е. минимальное количество ребер, необходимое для того, чтобы граф был связным. Действительно, две вершины связываются одним ребром, и для связи каждой последующей вершины с предыдущими требуется ребро, следовательно, для связи р вершин необходимо и достаточно р – 1 ребер.

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

– 55 -

деревьями, называется лесом (лес из к деревьев, содержащий р вершин, имеет в точностир – к ребер). Сказанное иллюстрируется на примере дерева (Рис. 15, а), которое превращается в циклический граф добавлением ребра (Рис. 15, б) и распадается на лес из двух деревьев T₁ и T₂ при удалении ребра е (Рис. 15, в).

Рис. 15. Дерево (а), образование цикла при введении дополнительного ребра (б) и лес, который образуется после удаления ребра е (в).

Обычно деревья считаются существенно различными, если они не изоморфны. На Рис. 16 показаны все возможные различные деревья с шестью вершинами. С увеличением числа вершин количество различных деревьев резко возрастает (например, при р = 20 их насчитывается около миллиона). Среди различных деревьев выделяются два важных частных случая: последовательное дерево, представляющее собой простую цепь, и звездное дерево, в котором одна из вершин (центр) смежна со всеми остальными вершинами.

Рис. 16. Существенно различные деревья с шестью вершинами.

Рис. 17. Прадерево с корнем v₀.

Рассматриваются также деревья с ориентированными ребрами (дугами). Ориентированное дерево называется прадеревом с корнем v₀ , если существует путь между вершиной v₀ любой другой его вершиной (Рис. 17). Ясно, что прадерево имеет единственный корень.

До сих пор рассматривались деревья как минимальные связные графы на множестве р вершин. Важное значение имеет и другая точка зрения, когда деревья или лес являются частями некоторого графа, т. е. образуются из его ребер. Любая связная совокупность ребер, не содержащая контуров, вместе с инцидентными им вершинами образует дерево графа (Рис. 18, а). Если такое дерево является суграфом (содержит все вершины графа), то оно называется покрывающим деревом или остовом (Рис. 18, б). Так как петля

– 56 -

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

Ребра графа, которые принадлежат его дереву, называют ветвями. Если дерево покрывает граф, то множество ребер графа разбивается на два подмножества: подмножество ветвей и подмножество ребер дополнения дерева, называемых хордами. При этом связный (р, q) – граф содержит v = р – 1 ветвей и σ = q – р + 1 хорд. Если граф несвязный, то совокупность, остовов R его компонент образует покрывающий лес. В этом случае ν = р – R и σ = q – р + R.

Рис. 18. Дерево как часть графа (выделено жирными линиями):

а – дерево; б – остов (покрывающее дерево).

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

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

На Рис. 19 показаны два неплоских графа, играющие фундаментальную роль в теории планарности и называемые графами Понтрягина – Куратовского. Полный пятиугольник (Рис. 19,а) представляет собой простой неплоский графе минимальным числом вершин (полный графе четырьмя вершинами – плоский, а удаление из пятиугольника хотя бы одного ребра также превращает его в плоский граф). Двудольный граф (Рис. 19, б) является моделью известной задачи о трех домах и трех колодцах: можно ли проложить от домов к каждому колодцу дороги так, чтобы они не пересекались (враждующие соседи должны иметь возможность пользоваться всеми колодцами, но не хотят встречаться на дорогах).

– 57 -

Рис. 19. Графы Понтрягина – Куратовского:

а – полный пятиугольник; б – двудольный граф.

Свойства планарности не нарушаются, если некоторое ребро разбить на два введением новой вершины второй степени или заменить два ребра, инцидентные вершине второй степени, одним ребром, удалив эту вершину. Два графа называют гомеоморфными (изоморфными с точностью до вершин второй степени), если после удаления из них вершин второй степени и объединения инцидентных этим вершинам ребер, они оказываются изоморфными (Рис. 20). Очевидно, граф, гомеоморфный плоскому графу, также плоский.

Строго доказывается, что граф является плоским тогда и только тогда, когда он не содержит подграфа, гомеоморфного одному из графов Понтрягина – Куратовского.

Рис. 20. Гомеоморфные графы.

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

14. Графы и отношения.Пусть на множестве Х задано бинарное отношение А. Ему соответствует ориентированный граф, вершины которого отображают элементы из X, а дуга (х_i, x_j), где (х_i, x_j ∈ X), существует тогда и только тогда, когда(х_iАx_j). Обратно, множество ориентированных дуг графа (без строго параллельных дуг), заданных упорядоченными парами (х_i, x_j), можно рассматривать как бинарное отношение на множестве X.

Если бинарное отношение хАy устанавливает связь между элементами х из множества Х и элементами у из множества Y (х ∈ X, у ∈ У), то граф такого отношения будет ориентированным биграфом.

Следует заметить, что в общем случае орграф представляет нечто большее, чем бинарное отношение. Любое бинарное отношение, определенное на некотором множестве, можно представить соответствующим орграфом, вершины которого соответствуют элементам этого множества. Однако орграф с параллельными дугами позволяет отражать более общие связи между объектами, чем бинарные отношения.

– 58 -

Задачи и упражнения

1. Какие части города (см. рис. 7) нужно соединить мостами, чтобы задача о кенигсбергских мостах имела положительное решение? Достаточно ли для этого одного дополнительного моста?

2. Постройте граф отношений между сотрудниками Вашего подразделения: а) x_i связан по работе с x_j; б) x_i подчинен x_j ( x_j, x_j ∈ X, где X – множество сотрудников подразделения). Охарактеризуйте полученные графы: что в них общего и чем они различаются? В каких случаях может получиться несвязный граф?

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

4. На графе, построенном в задаче 3, укажите (хотя бы приблизительно) расстояния между смежными вершинами. Найдите кратчайшие маршруты, соединяющие интересующие Вас вершины.

5. Существует ли эйлеров цикл для графа, построенного в задаче 3, и что он означает? Попытайтесь найти для этого графа гамильтонов цикл (если он существует).

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

а) Запишите все ребра как неупорядоченные пары вершин и отметьте кратные ребра и петли.

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

в) Является ли граф однородным (если нет, то добавлением ребер преобразуйте его в однородный)?

г) К какому типу относится рассматриваемый граф (простой, мультиграф, псевдограф)?

д) Запишите матрицу смежности графа.

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

а) Запишите все ребра как неупорядоченные пары вершин и отметьте параллельные ребра.

б) Определите положительные и отрицательные степени всех вершин и соответственно их суммы (что можно сказать об этих суммах?).

в) Запишите матрицу инцидентности графа.

8. Докажите, что кубический граф имеет четное число вершин. Обобщается ли свойство четности вершин на однородные графы высших степеней?

9. Постройте графы, соответствующие следующим матрицам смежности:

– 59 -

Охарактеризуйте полученные графы и запишите для них матрицы инцидентности.

10. Расположите на плоскости четыре вершины, как в графе на рис. 11, а, но обозначения вершин v₂ и v₃ взаимно переставьте. На множестве обозначенных таким образом вершин постройте граф, изоморфный исходному.

11. Выполните следующие упражнения с графом (см. рис. 11, а):

а) Найдите все ориентированные маршруты от вершины а к вершине е.

б) Найдите все пути и простые пути от вершины а к вершине е.

в) Определите все простые контуры графа.

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

14. Для графа (см. рис. 12) простойте:

а) часть, состоящую из четырех вершин и пяти ребер;

б) суграф с четырьмя, пятью и шестью ребрами.

15. Два графа G' = (V', E') и G" = (V", E") называются непересекающимися, если V' ∩ V" = ∅ и E' ∩ E" = ∅. Постройте непересекающиеся подграфы графа рис. 12, содержащие по три вершины.

16. Постройте блоки, на которые разбивается сепарабельный граф (см. рис. 14, а).

17. Постройте все различные деревья с восьмью вершинами (их должно быть 23).

18. Постройте все покрывающие деверья и их дополнения для графа (см. рис. 11, а). Сколько имеется существенно различных деревьев?

19. Постройте покрывающий лес несвязанного графа (см. рис. 13).

20. Постройте все прадеревья оргарфа (см. рис. 8, а) с корнем в вершине d.

21. Рассматривая компоненты несвязанного графа (см. рис. 13) как блоки, постройте соответствующий сепарабельный граф. Сколько возможно различных вариантов (без учета изолированной вершины G₂)?

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

23. Покажите, что графы на рис. 21, а и в гомеоморфные.

– 60 -

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

25. Докажите, что (p, p – k) – граф при k ≥ 2 всегда является несвязным и состоит не менее, чем из k компонент.

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

27. Покажите, что число ребер полного графа равно 1/2 p(p – 1), где p – число его вершин.

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

29. Покажите, что любое дерево можно представить как двухдольный граф. Какие деревья являются полными двудольными графами?

Рис. 21. Неплоские графы.

30. Докажите: а) кубический граф имеет точку сочленения тогда и только тогда, когда он содержит мост; б) наименьшее число вершин в кубическом графе, имеющем мост, равно 10.

31. Постройте граф, изоморфный графу Понтрягина-Куратовского (см. рис. 19, б), в котором внешние ребра образуют шестиугольник. Рассматривая его как подграф полного шестиугольника, нарисуйте дополнение этого подграфа. Укажите характерные свойства полученного дополнения.

32. Покажите, что следующие свойства дерева Т равносильны:

а) Т связно и не содержит циклов;

б) Т не содержит циклов и имеет p – 1 ребер, где p – число вершин;

в) Т связно и имеет p – 1 ребер;

г) Т не содержит циклов, но добавление ребра между любыми двумя несмежными вершинами приводит к появлению цикла;

д) Т связно, но утрачивает это свойство при удалении любого ребра;

е) всякая пара вершин в Т соединена цепью и притом только одной.

5. Логика

1. Чем занимается математическая логика? Логика как искусство рассуждении зародилась в глубокой древности. Начало науки о законах и формах мышления связывают с именем Аристотеля. Прошло два тысячелетия, прежде чем Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею последовательно реализовал в прошлом столетии Джордж Буль и тем самым заложил основы математической (символической) логики.

– 61 -

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

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

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

Столь энергичный выход математической логики за пределы математики объясняется тем, что ее аппарат легко распространяется на объекты самой общей природы, лишь бы только они характеризовались конечным числом состояний.

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

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

2. Булевы функции. Объекты с двумя возможными состояниями характеризуются булевыми переменными, которые способны принимать лишь два различных значения. Для обозначения этих двух значений обычно используются цифры 0 и 1 или буквы Л (ложно) и И (истинно).

– 62 -

Отношения между булевыми переменными представляются булевыми функциями, которые подобно числовым функциям могут зависеть от одной, двух и, вообще, n переменных (аргументов). Запись у = f(x₁, x₂, …,x_N) означает , что у – функция аргументов x₁, x₂, …,x_N. Важнейшая особенность булевых функций состоит в том, что они, как и их аргументы, принимают свои значения из двухэлементного множества {0,1}, или (И, Л}, т. е. характеризуются одним из двух возможных состояний.

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

Отрицание – функция у = f(х), принимающая значения 1, когда х = 0, и значение 0, когда х = 1; она обозначается у = x̅ (читается «не х»).

Дизъюнкция – функция у = f(x₁, x₂), принимающая значение 0 тогда и только тогда, когда оба аргумента имеют значение 0; она обозначается у = x₁ ∨ x₂ (читается «у = x₁ или x₂»).

Конъюнкция—функция у = f(x₁, x₂), принимающая значение 1 тогда и только тогда, когда оба аргумента имеют значение 1; она обозначается у = x₁ ∧ x₂ («у = x₁ и x₂»).

Таблицы для этих функций имеют вид:

3. Логические операции и формулы.Булевы функции можно рассматривать как логические операции над величинами, принимающими два значения – 0 и 1. Отрицание – это одноместная операция, а дизъюнкция и конъюнкция – двухместные операции. При этом выражения x̅ , x₁ ∨ x₂, x₁ ∧ x₂ являются логическими формулами.

Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки. Например, положив x₁ = a̅ и x₂ = b ∧ c из x₁ ∨ x₂,имеем ( a̅ ) ∨ (b ∧ c).

– 63 -

Каждая формула определяет некоторую булеву функцию. Ее значение при различных значениях переменных определяется на основании таблиц функций, приведенных в (2). Так, при а = 0, b = 1 и с = 0 имеем:

x₁ = a̅ = 0̅ =1, x₂ = b ∧ с = 1 ∧ 0 = 0 и x₁ ∨ x₂ = a̅ ∨ (b ∨ c) = 1 ∨ 0 = 1. Аналогично получаем значения функции и при других комбинациях значений аргументов.

Две функции (как и определяющие их формулы) считаются равносильными,если при любых значениях аргументов эти функции (формулы) принимают одинаковые значения. Равносильные функции соединяются знаком равенства, например: (х ∧ у) ∨ z̅ = ( ) ∧ z или ((х ∨ x̅ ) ∧ у) ∨ (у ∨ х) == х ∨ у. Равносильность функций проверяется по таблицам основных операций, причем необходимо сравнить их значения для всех комбинаций значений переменных.

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

На основе определения основных операций нетрудно убедиться в справедливости следующих тождеств (свойств) булевой алгебры:

коммутативность

х ∨ y = y ∨ х, х ∧ y = y ∧ х;

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