Введение в схемы, автоматы и алгоритмы



   Риск в менеджменте            

Логические схемы (схемы из функциональных элементов) - часть 2


Определение 2.4. Схема S реализует набор булевых функций g1, g2, … , gm, если для каждого i

[1,m] в схеме существует такая вершина vi, что
 f_{v_i} = g_i
.

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

Определение 2.5. Сложность L(S) схемы S - это число функциональных элементов в S. Сложность L(f) булевой функции f(x1, …, xn) - это наименьшая из сложностей схем, реализующих эту функцию.

Отношения между булевыми функциями и схемами естественно приводят к двум следующим основным проблемам.

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

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

Пример 2.1. Рассмотрим схему S1

с тремя входными переменными x, y и z, изображенную на рис. 2.1 и решим для нее проблему анализа.

Схема S1

Рис. 2.1.  Схема S1

В соответствии с данным выше определением вершины схемы S1 реализуют следующие функции:

fa(x,y,z) = x

y, fb(x,y,z) = ¬ z, fc(x,y,z) = ¬ fa(x,y,z)=¬( x
y), fd(x,y,z) = fc(x,y,z)
z = ¬( x
y)
z, fe(x,y,z) =fa(x,y,z)
fb(x,y,z)= x
y
¬ z и, наконец, ff(x,y,z) =fd(x,y,z)
fe(x,y,z) = (¬( x
y)
z)
((x
y )
¬ z).

Глубина этой схемы D(S1)= 4, а ее сложность L(S1)=6. В то же время формула для результирующей функции ff содержит 7 функциональных знаков. За счет чего достигнута экономия? За счет того, что функция (x

y) в схеме S1 вычисляется один раз в вершине a, а в формуле приходится вычислять ее дважды.

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




Содержание  Назад  Вперед