Материал: Diskretnaya_matematika

Третий этап

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

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

Таблица 2.9. Логические элементы и их обозначения

9. По аналитическому выражению строим логическую схему. При этом необходимо соблюдать очередность, раскрывая выраже­ние «изнутри наружу». Полученная в результате логическая схема может оказаться избыточной.

Пример. Пусть функция y = f(х₁, х₂, х₃, х₄) задана мини­мальной булевой формулой:

F = (х₁  х₂) х₃  (х₁  х₂) х₄.

При построении логической схемы по этой формуле потребуется шесть элементов, реализующих 6 операций. Но два из них реализуют одну и ту же функцию (х₁х₂). Поэтому можно упростить логическую схему, используя 5 логических элементов и задавая соответствующие связи между ними. Окончательно получим схему, изобра­женную на рис. 2.1.

Четвертый этап

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

Рис. 2.1. Логическая схема

2.6. Контрольные вопросы и упражнения

1. Для высказывания А: «Любые два треугольника подоб­ны» сформулируйте отрицание и двойное отри­цание. Какие из этих трех высказываний истинны?

2. Даны высказывания: «Я купил велосипед» (А); «Я путешествовал по России» (В) и «Я участвовал в соревнованиях по велосипеду» (С). Сформулируйте высказывания, соответствующие формулам:

А В, А  В  С, А С, А  В, В С.

3. Даны высказывания:

«Четырехугольник MNPQ – парал­лело­грамм» (А);

«Диагонали четырехугольника MNPQ в точке пере­сечения делятся пополам» (В). Сформулируйте высказывания, соответ­ст­вующие формулам: А  В, В  А, А, В, А  В, В  А.

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

F₁ = X  (Y  Z) и F₂ = (X Y)  (X  Z).

5. Покажите, что формулы являются тавтологиями:

F₁ = X   Y ~ Y  X;

F₂ = X   Y ~ Y  X;

F₃ = ((X  Y)  X)  Y.

6. Докажите равносильность формул:

а) F₁ = X  (Y  Z) и F₂ = (X  Y)  (X  Z);

б) F₁ = X  (Y  Z) и F₂ = (X  Y)  (X  Z);

в) F₁ = X  Y и F₂ =X Y;

г) F₁ = X  Y и F₂ =X Y;

д) F₁ = X  (Y  Z) и F₂ = (X  Y)  Z;

е) F₁ = (X  Y)  (X  Z) и F₂ = X  (Y  Z).

7. Постройте совершенные ДНФ и КНФ функций:

x₁ | x₂, x₁  x₂, x₁ ~ x₂.

8. Запишите СДНФ и СКНФ для логической функции f(x₁, х₂, х₃), принимающую значение 1 на наборах с номерами: 0, 3, 7. Определите, к каким классам функций относится эта функция.

9. Проверьте справедливость равенств:

а) х =х  1;

б) х₁  х₂ =х₁  x₂ .

10. Составьте таблицу свойств логической функции двух переменных. Из таблицы выпишите все полные системы булевых функций.

11. Проверьте линейность логической функции f(x₁, x₂, x₃), прини­мающей значение 1 на наборах с номерами: 0, 1, 5, 6.

12. Синтезируйте логические схемы функций из задач № 9, 12.

13. Найдите минимальную ДНФ функции f(х₁, х₂, х₃, х₄), прини­мающей значение 1 на наборах с номерами: 0, 1, 2, 5, 6, 7, 8, 12, 13.

14. Приведите примеры:

а) монотонной функции, которая одновре­менно была бы линейной;

б) самодвойственной функции, кото­рая одновре­менно была бы линейной;

в) линейной и монотонной функций.

15. Покажите, что функции Шеффера и Пирса не явля­ются ни ли­нейными, ни монотонными, ни самодвойственными.

16. Докажите полноту системы функций  = {, ~ , 0}, состоящей из дизъюнкции, эквивалентности и константы 0.

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

На практике часто бывает полезно изобразить некоторую си­туацию в виде рисунков, составленных из точек (вершин), представ­ляющих основные ситуации, и линий (ребер), соединяющих опреде­ленные пары этих вершин и представляющих связи между ними. Таким способом удобно представлять структуру системы, в которой вершины – это блоки, а ребра – связи между блоками. Такие рисунки известны под общим названием графов. Графы встречаются в разных областях под разными названиями: «структуры» в гражданском строительстве, «сети» в электротехни­ке, «социограммы» в социологии и экономике, «молекулярные структуры» в химии и т.д. Удобны графы и при исследо­вании систем методом пространства состояний. В этом случае вер­шины – состояния системы, процесса, ребра – действия, которые могут изменить состояние. При решении оптимизационных задач вершинами могут быть предполагаемые решения, ребрами – прави­ла для их нахождения.

Начало теории графов как математической дисциплины было положено Эйлером в 1736 г., когда им была написана статья о Кенигсбергских мостах. Однако она была единственной в течение почти ста лет. Интерес к этой науке возродился около сере­дины XIXв связи с развитием естественных наук (исследования электрических сетей, моделей кристаллов и структур молекул), формальной логики. Кроме того, оказалось, что многие математические голово­ломки могут быть сформулированы в терминах теории графов.

Последние 35-40 лет ознаменовали новый период интенсив­ных разработок теории графов. Появились новые области прило­жения: системы телекоммуникаций, биология, психоло­гия и другие.

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

3.1.1. Общие понятия

Граф Gзадается множествомвершин(точек) Х = {х₁, ..., х_n} и множествомребер(линий) А = {а₁, .., а_n}, соединяющих между собой все или часть этих вершин. Таким образом, графGполностью определяется заданием двух множеств (Х, А).

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

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

Пример.Для графа, изображенного на рис. 3.1: множество вершинX= {х₀,х₁,х₂,х₃,х₄,х₅} и закон соот­ветствия между вершинами:

G(x ₀) = {x₁, x₂},

G(x₁) = {x₀, x₂, x₄},

G(x₂) = {x₀, x₁, x₅},

G(x₃) = {x₄},

G(x₄) = {x₁, х₃},

G(x₅) = {x₂},

G(x₆) = .

Рис. 3.1. Пример задания графа

Ребра графа– линии, соединяющие вершины, указывают на соответствие между вершинами в графе.

Запись g= (x_i,x_j) говорит, что реброgинцидентновершинам х_iиx_j, а вершины х_i,x_jинцидентныребруg. Две вершины х_i,x_jназы­ваютсясмежными, если они определяют ребро графа. Два ребра графа называютсясмежными, если их концы имеют общую верши­ну.

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

3.1.2. Ориентированные и неориентированные графы

Ребро графа называется неориентированным, если порядок расположения его концов (направление стрелок) в графе не прини­мается во внимание.

Ребро графа называетсяориентированным, если этот порядок существенен. В этом случае говорят, что для ребраg= (x_i,x_j):x_i– начальная,ax_j– конечная вершины ребра.