5.3. Особенности k – значной логики

Во многом k – значная логика подобна двухзначной. В ней сохраняются многие результаты, имеющие место в двузначной логике. Однако ряд результатов, верных для функций алгебры логики, т.е. при k=2, уже не переносятся на случай, когда k ³3.

Например, как показал Пост, каждый замкнутый класс в P₂ имеет конечный базис и поэтому, число замкнутых классов в P₂ счетно. С другой стороны для k ³ 3 в :

а) существует замкнутый класс не имеющий базиса;

б) существует замкнутый класс имеющий счетный базис;

в) имеется бесчисленные множества различных замкнутых классов.

6.. Основные понятия теории графов.

6.1. Задачи теории графов.

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

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

П ервая задача. Задача о Кенигсбергских мостах была поставлена и решена Эйлером в 1786 году. Город располагался на берегах и двух островах реки Преголи. Острова между собой и берегами были связаны семью мостами, как показано на рисунке.

Рис. 15

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

В торая задача. Задача о трех домах и трех колодцах. Имеется три дома и три колодца.

Рис. 16

Требуется провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Задача была решена Понтрягиным и независимо от него Куратовским в 1930 году.

Т ретья задача. О четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.

Рис. 17

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

6.2. Основные определения.

Графом G=(V,E) называется совокупность двух множеств - непустого множества вершин V и множества неупорядоченных и упорядоченных пар вершин E. В дальнейшем будут рассматриваться конечные графы, т.е. графы с конечным множеством вершин и конечным семейством пар. Неупорядоченная пара вершин называется ребром, а упорядоченная - дугой.

Обычно граф изображается диаграммой: вершины - точками (или кружками), ребра – линиями произвольной конфигурации. На дуге дополнительно стрелкой указывается её направление. Отметим, что при изображении графа несущественны геометрические свойства ребер (длина, кривизна), а также взаимное расположение вершин на плоскости.

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

Говорят, что ребро (u,v) соединяет вершины u и v, а дуга (u,v) начинается в вершине u и заканчивается в вершине v, при этом u называется началом, а v – концом этой дуги.

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

Пара вершин может соединяться двумя или более ребрами (дугами одного направления). Такие ребра (дуги) называются кратными. Дуга (или ребро) может начинаться или кончаться в одной и той же вершине. Такая дуга (ребро) называется петлёй. Граф, содержащий петли, называется псевдо графом. Граф, имеющий кратные ребра (дуги), называется мультиграфом.

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

Рис. 18

Граф, состоящий из одной изолированной вершины (K₁), называется тривиальным.

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

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