Алгоритм БыстроеЗамыкание(X,f)

// Инициализация:

for t F

СЧЕТ[t] := |Lt|;

for a Lt ВЫПОЛНЯТЬ

добавить t в СПИСОК[a];

НОВЫЕ := X; ОБНОВА := X;

// Вычисление:

while ОБНОВА <> ВЫПОЛНЯТЬ

выбрать a ОБНОВА;

ОБНОВА := ОБНОВА \ {a};

for t СПИСОК[a]

СЧЕТ[t] := СЧЕТ[t] - 1;

if СЧЕТ[t] = 0 then

if {bt} НОВЫЕ then

НОВЫЕ := НОВЫЕ {bt}

ОБНОВА := ОБНОВА {bt}

вернуть(НОВЫЕ).

Следующая теорема утверждает корректность приведенного алгоритма.

Теорема:Алгоритм БыстроеЗамыкание(X,F) строит замыкание Cl(X,F).

Отметим, что число шагов алгоритма БыстроеЗамыкание(X,F) пропорционально размеру его входа, т.е. числу продуктов в и . Такие алгоритмы называются линейными. Действительно, при инициализации каждый элемент рассматривается 2 раза, а в основном цикле общее число рассматриваемых элементов и операций уменьшения на 1 значенийСЧЕТ [] не больше суммы размеров всех , т.е. также не превосходит размера входа.

Пример 10.3:Рассмотрим работу алгоритма БыстроеЗамыкание на следующем примере. Пусть={a, b, c, d, e, f, g, h},= {b, f}, а множествосостоит из следующих 6 процессов:

a, b, c, h d;

b, c, d a;

a, b e;

e,fc;

f,ed;

b,fg;

Тогда при инициализации будут построен массив СЧЕТ = [4, 3, 2, 2, 2, 2] и следующие списки:

СПИСОК[a] = (1)

СПИСОК[b] = (1, 2, 3, 6)

СПИСОК[c] = (1, 2)

СПИСОК[d] = (2)

СПИСОК[e] = (4, 5)

СПИСОК[f] = (4, 5, 6)

СПИСОК[g] = (3)

СПИСОК[h] = (1)

Множества ДОБАВКА и НОВЫЕ будут инициализированы булевскими массивами 01000100 с 1 на местах, соответствующих продуктам b и f. Дальнейшие изменения этих структур представлены в следующей таблице.

СЧЕТ						ДОБАВКА	НОВЫЕ
1	2	3	4	5	6	abcdefgh	abcdefgh
4	3	2	2	2	2	01000100	01000100
3	2	1	2	2	1	00000100	01000100
3	2	1	1	1	0	00000010	01000110
3	2	0	1	1	0	00001000	01001110
3	2	0	0	0	0	00110000	01111110
2	1	0	0	0	0	00010000	01111110
2	0	0	0	0	0	10000000	11111110
1	0	0	0	0	0	00000000	11111110

Алгоритм завершает работу, когда множество ДОБАВКА становится пустым. В этот момент результат Cl(X,F) представлен множеством НОВЫЕ. В нашем примере оно равно {a,b,c, d,e,f,g}.

Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия

В самом начале нашего курса мы говорили, что значения, которые может принимать логическая переменная, могут быть интерпретированы, как «включено», «выключено». Это связано с возможностью использования аппарата булевой алгебры для описания и использования релейно-контактных схем. На это указал ещё в 1910 году физик Эренфест. Однако его идеи стали реализовываться значительно позже. Использование булевой алгебры в конструировании РКС оказалось возможным в связи с тем, что каждой схеме можно поставить в соответствие некоторую формулу булевой алгебры, и каждая формула булевой алгебры реализовывается с помощью некоторой схемы. Это обстоятельство позволяет выявить возможность заданной схемы, анализируя соответствующую формулу, а упрощение схемы свести к упрощению формулы.

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

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

• переключателей, которыми могут быть механически действующие устройства (выключатели, кнопочные устройства, электромагнитные реле, электролампы, полупроводниковые элементы и т.д.);

• схемы соединяющих их проводов;

• входов и выходов в схему (клемм на которые подается электрическое напряжение).

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

Рассмотрим простую схему, содержащую единственный переключатель , имеющую один входи один выход. Переключателюпоставим в соответствие высказывание: «Переключатель замкнут». Еслиистинно, то импульс поступающий на вход, можно снять на выходе, без потерь напряжения. В этом случае будем говорить, что схема проводит ток. Еслиложно, то переключатель разомкнут и схема тока не проводит, или на полюсеснимается минимальное напряжение при подаче на полюсмаксимального напряжения. Если принять во внимание не смысл высказываний, а только его значение, то можно считать, что любому высказыванию может быть поставлена в соответствие схема:

Формулам, включающим & и также могут быть поставлены в соответствие переключательные схемы.

Конъюнкция ипредставляется двуполюсной схемой с последовательным соединением двух переключателейи. Эта схема пропускает ток тогда и только тогда, когда истинныиодновременно, т.е.

Дизъюнкция ипредставляется двуполюсной схемой с параллельным соединением двух переключателейи.

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

А тождественно ложная схемой, которая никогда не проводит ток.

Мы уже говорили, что любая формула булевой алгебры может быть представлена в виде формулы, содержащей только {,&,}.

Следовательно, любая формула Булевой алгебры может быть представлена схемой, и любая схема, может быть представлена формулой Булевой алгебры.