Функциональные элементы и схемы

Пусть имеется некоторое устройство, внутренняя структура которого нас не интересует, а известно лишь, что оно имеет п упорядоченных входов (занумерованных числами от 1 до п) и один “выход”. На каждый из входов может подаваться один из двух сигналов: 0 или 1 (“отсутствие тока” или “наличие его”) и при каждом наборе сигналов на входе возникает один из двух сигналов 0 или 1 на выходе. Такое устройство называется функциональным элементом (ФЭ). ФЭ, соответствующий функции j от нескольких переменных, может быть изображен следующим образом:

Ясно, что каждому ФЭ соответствует некоторая булева функция f (x ₁, x ₂,…, x_n). Некоторые входы могут быть фиктивными (т. е. при любом наборе сигналов на остальных входах сигнал на выходе не зависит от сигнала на этом входе, и соответствующая булева функция зависит от меньшего числа переменных). Если имеется несколько ФЭ, то из них можно получать новые сложные ФЭ (например, один из входов ФЭ можно соединить с выходом другого. В этом случае полученное соединение соответствует суперпозиции двух функций. Можно также соединять некоторые входы, что означает отождествление некоторых переменных).

Следующие соединения, очевидно, являются логическими функциями: (x + y) | (y ~ z) и (x | y) ~ (x× y).

Более точно: будем называть соединение нескольких ФЭ схемой, если выполнены следующие естественные требования:

а) всякий ФЭ является схемой;

б) если S ₀ – схема и два ее входа соединены вместе, то получившаяся в результате конструкция S также является схемой;

в) если S ₁и S ₂ – схемы, то схемой будет также конструкция S, полученная соединением какого-либо входа S ₁с выходом S ₂;

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

Ясно, что не всякое соединение ФЭ является схемой.

Соединение S конечного числа функциональных элементов является схемой тогда и только тогда, когда выполнены 3 условия:

среди ФЭ есть один и только один свободный выход (т.е. выход, не соединенный ни с каким входом);

каждый вход любого ФЭ может быть соединен не более чем с одним выходом другого ФЭ;

в соединении S нет циклов (т.е. нет такого упорядоченного набора ФЭ, когда вход следующего соединен с выходом предыдущего и вход первого соединен с выходом последнего. Цикл в соединении иначе называют обратной связью).

Теперь посмотрим, как на языке схем перефразируется задача о полноте системы функций. Пусть имеется некоторый набор функциональных элементов j ₁, j ₂,…,j _п (точнее, типов ФЭ, т. е. считаем, что имеется неограниченное число элементов, реализующих каждую из функций j _k). Спрашивается, при каких условиях любую булеву функцию можно реализовать при помощи схемы, состоящей из данных ФЭ. Из предыдущего ясно что ответ на этот вопрос дается теоремой Поста.

Замечание. Ясно, что при реализации описанных выше устройств необходимо учитывать, что для работы конкретных ФЭ требуется некоторое время, что влияет на фактор полноты ФЭ. Подробнее об этом можно узнать в [3].

Заметим, что на практике часто используются функции “конъюнкция” и “дизъюнкция”. Для них часто схемы изображаются несколько иначе. Дадим более точное определение. Релейно-контактной схемой или РКС будем называть некоторое соединение, состоящее из следующих элементов:

переключателей (это могут быть как механические устройства, так и лампы, электромагнитные реле и т. д.) Каждый переключатель может принимать значение 1 (через него пройдет ток) или 0 (через него ток не проходит). Будем считать, что любой переключатель соответствует либо логической переменной x,либо ;

проводников, могущих соединять переключатели либо последовательно, либо параллельно (это соответствует замене ФЭ, определяющих конъюнкцию или дизъюнкцию);

входа и выхода из системы (вход и выход называются полюсами системы).

Иначе РКС называют переключательной схемой (П-схемой).

Будем говорить, что конкретная РКС принимает значение 1 при данных значениях переключателей, если через нее проходит ток, в противном случае мы считаем, что она принимает значение 0.

Две РКС считаются равносильными,если они принимают одинаковые значения при одних и тех же значениях переключателей.

Очевидно, что любая суперпозиция функций конъюнкции, дизъюнкции и отрицания может быть изображена в виде РКС. Например, функции соответствует следующая РКС.

Следующая РКС соответствует функции (в ней 12 переключателей).

После сокращения СДНФ по правилу Блейка можно получить равносильную формулу: L = xz Úyz Ú xz, для которой РКС будет иметь 6 переключателей. Если ставить целью уменьшение числа переключателей, то последнее выражение можно преобразовать к виду L = (x Úy) z Úxy (РКС будет иметь 5 переключателей).

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

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

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

Пример 1. Пытаясьвспомнитьпобедителей прошлогоднего турнира, 5 бывших зрителей турнира заявили:

1) Антон был вторым, а Борис пятым.

2) Виктор был вторым, а Денис третьим.

3) Григорий был первым, а Борис третьим.

4) Антон был третьим, а Евгений шестым.

5) Виктор был третьим, а Евгений четвертым.

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

Решение. Будем обозначать высказывания зрителей Х _k, где Х – первая буква имени участника турнира, а k – номер места, которое он занял в турнире. В высказываниях зрителей одно высказывание может быть ложным, поэтому будут истинными дизъюнкции этих высказываний А₂Ú Б₅, В₂ Ú Д₃, Г₁Ú Б₃ , А₃ Ú Е₆ , В₃Ú Е₄. Но тогда истинной будет конъюнкция: K = (А₂ ÚБ₅)(В₂ÚД₃)(Г₁ ÚБ₃ )(А₃ Ú Е₆)(В₃Ú Е₄ ) = 1.

Учитывая, что Х _k Х _п = 0 при k ¹ п и Х _k Y _k = 0 при X¹ Y, получаем путем последовательного раскрытия скобок в К:

К = (А₂Д₃ ÚБ₅В₂ ÚБ₅Д₃)(Г₁А₃Ú Г₁Е₆ ÚБ₃Е₆)(В₃Ú Е₄) =

= (А₂Д₃Г₁Е₆ ÚБ₅В₂Г₁А₃ Ú Б₅В₂Г₁Е₆ Ú Б₅Д₃Г₁Е₆)(В₃Ú Е₄) = А₃Б₅В₂Г₁Е₄ = 1

Полученное соотношение дает распределение первых 5 мест и автоматически получаем, что Денис был шестым т. е. Д₆ = 1.

Пример 2. По подозрению в совершении преступления задержали Брауна, Джонса и Смита. Вот что они показали:

Браун: Я совершил это. Джонс не виноват.

Джонс: Браун не виноват. Преступление совершил Смит.

Смит: Я не виноват. Виновен Браун.

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

Решение. Обозначимбуквами B, D, C высказывания: виноват Браун, виноват Джонс, виноват Смит соответственно. Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций , из которых по условию задачи, две ложны, а одна истинна. Истинной будет формула, но из этой формулы решение получится только дополнительным рассуждением: пусть B = 1, тогда по условию C = 0 и D = 0. Но тогда из трех конъюнкций, составляющих К две будут верны: , а это противоречит условию. Значит В= 0. Видно, что C= 1удовлетворяетусловиюзадачи, и это решение единственно, так как если предположить, что D = 1, то это будет означать, что , а значит, что либо В, либо С равно 1, но это противоречит тому, что преступник только один.

Таким образом, преступник – Смит, оба его высказывания ложны, у Брауна одно высказывание ложно, одно нет, а Джонс сказал правду.

Все эти рассуждения используются не только для решения логических задач (которые действительно приходится решать следователям), но и для составления игровых программ (компьютерная игра ШЕРЛОК, содержащая больше 60 тыс. логических задач, составлена с использованием тех же самых конъюнкций, дизъюнкций и отрицаний).

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

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

Общие понятия теории графов

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

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

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

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

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

Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).

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

Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.

Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).

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

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

Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).

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

Лемма 1. Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.

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