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

Пусть – логическая переменная. При введем обозначение

Легко проверить, что , тогда и только тогда, когда . Следовательно, конъюнкция – равна 1 на единственном наборе значений аргументов , , , .

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

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

(4.23)

где дизъюнкция берется по всевозможным наборам значений аргументов . Например, при ,

.

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

Эта величина совпадает со значением левой части. Теорема доказана.

Представление функции в виде (4.23) называется разложением по переменным . Переменные называются переменными разложения или переменными исключения.

Частный случай разложенияфункции при имеет вид:

(4.24)

Используя формулу (4.24), можно представить логическую функцию в виде бинарного графа, в котором имеется ровно одна вершина без входящих в нее дуг (начальная); все вершины, по числу выходящих дуг, делятся на два типа: вершины с двумя выходящими дугами (условные вершины), вершины без выходящих дуг (заключительные вершины). Дуги помечаются символами 0 и 1. Условные вершины помечаются символом переменной, заключительные – комадой " ".

Пример бинарного графа для функции приведен на рис. 4.2. Здесь вершины – начальная; , и - условные; и – заключительные.

 

 

 

Каждому набору значений аргументов в бинарном графе соответствует путь из начальной вершины в заключительную вершину. Таким образом, бинарный граф каждому набору значений аргументов ставит в соответствие значение функции и может служить для ее задания и вычисления. Разным наборам может соответствовать один и тот же путь. Например, для графа, изображенного на рис.4.2, наборам (010) и (011) соответствует путь .

Следует отметить, что всякую логическую функцию, заданную булевой формулой F, содержащую N букв, можно представить бинарным графом, содержащим N условных вершин. Однако, сложность остаточных функций, а, следовательно, и число условных вершин в БГ зависит от порядка исключения переменных. Так, если в функции на первом ярусе исключить переменную , то получится бинарный граф (рис. 4.3), содержащий три условные вершины, т.е., на одну меньше, чем бинарный граф той же функции полученный ранее (см. рис. 4.2). Число всевозможных способов исключения переменных растет комбинаторно. Например, если на каждом ярусе бинарного графа будет исключаться одна и та же переменная, то это число равно , но на каждом ярусе можно исключать и различные переменные. Поэтому, выбор оптимального исключения перебором всех способов исключения – трудоемкий процесс. Оптимальное исключение переменных ищут, используя эвристические критерии.