Закрыть

Булевы функции.

Автор: Васин Алексей
Опубликовано 08.02.2008 в 15:56
Раздел: Дискретная математика
Рис.1
Рис.1

Основные понятия

Определение. Функция f, зависящая от n переменных $x_1, x_2, ...., x_n$, называется булевой, или переключательной, если функция f и любой из ее аргументов $x_i$, (i = 1..n) принимают значения только из множества {0, 1}. Аргументы булевой функции также называются булевыми.

Произвольная булева функция задается одним из трех способов: матричным (табличным), геометрическим и аналитическим. При матричном способе булева функция $f(х_1, ...,х_n)$ задается таблицей истинности (таблицы 1 и 2), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах.

Таблица 1

$\begin{array}{rr} x_1 x_2 x_3 & f \\ 0 0 0 & 0 \\ 0 0 1 & 1 \\ 0 1 0 & 0 \\ 0 1 1 & 0 \\ 1 0 0 & 1 \\ 1 0 1 & 1 \\ 1 1 0 & 0 \\ 1 1 1 & 1 \\ \end{array}$

Таблица 2

$\begin{array}{rr} Номер вектора & f \\ 0 & 0 \\ 1 & 1 \\ 2 & 0 \\ 3 & 0 \\ 4 & 1 \\ 5 & 1 \\ 6 & 0 \\ 7 & 1 \\ \end{array}$

Под двоичным набором $y = \lt y_1, y_2,...,y_n \gt$, $y_i$ принадлежит множеству {0, 1}, понимается совокупность значений аргументов $х_1, х_2, ..., x_n$ булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В табл. 1 передставлены все двоичные наборы длины 3.

Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов. Запишем аргументы $х_1, х_2, ..., x_n$ в порядке возрастания их индексов. Тогда любой двоичный набор $y = \lt y_1, y_2,...,y_n \gt$, $y_i$ принадлежит множеству {0, 1}, можно рассматривать как целое двоичное число N:

$N=y_1*2^{n-1}+y_2*2^{n-2}+...+y_n$

называемое номером набора y. Например, двоичные наборы 101 и 111 имеют номера 5 и 7 соответственно. Очевидно, любая булева функция может быть задана таблицей истинности, в которой двоичные наборы заменены своими номерами (табл. 2).

Булевы функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности булевой функции от 8 переменных будет содержать $2^8 = 256$ строк. Поэтому для задания функций многих переменных удобно использовать модификацию таблицы истинности.

Рассмотрим способ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: $х_1, х_2, ..., х_{j-1}$ и $х_j, х_{j+1}, ..., х_n$. Переменными $x_1, x_2, ..., x_{j-1}$ отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными $x_j, x_{j+i}, ..., x_n$ отмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длины n-j+1. Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл. 3)

Таблица 3

$\begin{array}{rr} & x_j, x_{j+1}, ...,x_n \\ \begin{array}{r}x_1,x_2,...x_{j-1} \\00..0 \\ 00..1 \\ \cdots \\ 11..1 \end{array} & \begin{array}{r} 00..0 & 00..1 & \cdots & 11..1 \\ & & \cdots & \\ & & \cdots & \\ \cdots & \cdots & \cdots & \cdots \\ & & \cdots & \\ \end{array} \\ \end{array}$

При геометрическом способе булева функция $f(х_1, ..., х_n)$ задается с помощью n-мерного куба. В геометрическом смысле каждый двоичный набор $y = \lt y_1, y_2,...,y_n \gt$, $y_i$ принадлежит множеству {0, 1}, есть n-мерный вектор, определяющий точку n-мерпого пространства. Исходя из этого, все множество наборов, на которых определена функция n переменных, представляется вершинами n-мерного куба. Отмечая точками вершины куба, в которых функция принимает единичное (либо нулевое) значение, получим геометрическое представление функции. Например, булева функция, заданная табл. 1, геометрически представляется 3-мерным кубом (рис. 1).

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

Рассмотрим области определения булевых функций. Как уже отмечалось, между двоичными наборами и двоичными числами существует взаимно однозначное соответствие. Следовательно, существует $2_n$ различных наборов двоичных переменных.

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

Булеву функцию, определенную на всех своих наборах, называют полностью определенной. В табл. 1, 2 приведены примеры полностью определенных булевых функций.

Булеву функцию n переменных называют неполностью определенной или частичной, если она определена не на всех двоичных наборах длины n. Неполностью определенная булева функция не попадает под определение, данное в начале , но при произвольном доопределении (на всех наборах, на которых она не определена) это несоответствие снимается.

Легко убедиться, что если булева функция f не определена на m наборах аргументов, то путем ее доопределения можно получить 2m различных полностью определенных функций. В табл. 4 приведен пример неполностью определенной булевой функции трех переменных.

Таблица 4

$\begin{array}{rr} x_1 x_2 x_3 & f \\ 0 0 0 & 0 \\ 0 0 1 & 1 \\ 0 1 0 & - \\ 0 1 1 & 0 \\ 1 0 0 & 1 \\ 1 0 1 & - \\ 1 1 0 & 0 \\ 1 1 1 & - \\ \end{array}$

Существует не более чем $2^{2^n}$ различных булевых функций n переменных. К этому выводу легко прийти, пользуясь простыми комбинаторными рассуждениями, и вспомнив, что на каждом из $2^n$ наборов функции могут принимать два значения.

Функции двух переменных представлены в табл. 5.

Наиболее часто употребляются следующие:

Таблица 5

$\begin{array}{rr} x_1 & x_2 & f_0 & f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 & f_9 & f_{10} & f_{11} & f_{12} & f_{13}& f_{14}& f_{15} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ \end{array}$

$f_0 (x_1, x_2) = 0$ - тождественный ноль (константа 0);

$f_1 (x_1, x_2) = x_1 * x_2$ - конъюнкция. Вместо знака "*" иногда употребляется знак & или /\. Эту функцию часто называют логическим произведением или логическим умножением;

$f_3 (x_1, х_2) = x_1$ - повторение x1;

$f_5 (x_1, x_2) = x_2$ - повторение х2;

$f_6 (x_1, x_2) = х_1+x_2$ - сложение по модулю 2 или сумма mod 2;

$f_7 (х_1, х_2) = x_1 \vee x_2$ - дизъюнкция (логическое ИЛИ);

$f_8 (x_1, x_2) = x_1 | х_2$ - функция Вебба (стрелка Пирса);

$f_9 (х_1, х_2) = x_1 \sim x_2$ - эквивалентность;

$f_13(x_1, x_2) = x_1 \to x_2$ - импликация;

$f_14(x_1, x_2) = x_1\x_2$ - штрих Шеффера;

$f_15(x_1, x_2) = 1$-тождественная единица (константа 1).

Рассмотренные простейшие булевы функции позволяют строить новые булевы функции с помощью обобщенной операции, называемой операцией суперпозиции. Фактически операция суперпозиции заключается в подстановке вместо аргументов других булевых функций (в частности аргументов). Например, из функции $f_1(x_1, x_2) с помощью подстановки $f_3(х_4, x_8), $f_2 = x_3$ вместо аргументов $х_1$ и $х_2$ соответственно получаем функцию $f_1(f_3 (x_4, x_8), x_3). Последняя от переменных $х_1, и х_2$ уже не зависит.

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

Операция суперпозиции позволяет увидеть качественный переход от n = 1 к n = 2. Действительно, суперпозиция функций одного аргумента порождает функции одного аргумента. Суперпозиция функций двух аргументов дает возможность строить функции любого числа аргументов (в приведенном примере построена функция трех переменных).

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

* одна и та же функция может быть представлена разными формулами;

* каждой формуле соответствует своя суперпозиция и, следовательно, своя схема соединений элементов;

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

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

Для булевой алгебры определены одна одноместная (унарная) операция "отрицание", две двухместные (бинарные) операции конъюнкция и дизъюнкция (обозначаются "*" (прим. далее "*" упускается), "v" соответственно).

В этой алгебре справедливы три аксиомы:

* закон коммутативности - х v у = у V х, ху = ух;

* закон ассоциативности - (х v у) v z = х v(y v z), (х y) z = х(у z);

* закон дистрибутивности - х (у v x) = ху v хz, х v y * z = (х v y)(х v z).

Под бинарной операцией на множестве А, в общем случае пони-мают отображение декартового произведения множеств (A Х А) в множество А. Иными словами, результат применения бинарной операции к любой упорядоченной паре элементов из А есть также элемент из множества А.

Под унарной операцией на множестве А понимают выделение (фиксацию) какого-либо элемента множества А.

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

Алгебра Жегалкина

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

Алгебра Жегалкина включает две двухместные операции: конъюнкцию и сложение по модулю 2 (*,+), а также константу 1. Здесь имеют место те же законы:

* х + y = y + х, х у = у х (закон коммутативности);

* х + (у + z) = (х + у) + z, х(у z) = (х у)z (закон ассоциативности)

* x (y + z) = x y + x z (закон дистрибутивности).

Для упрощения формул могут быть использованы следующие соотношения:

х + 0 = х;

х 1 = х

х 0 = 0

х + х = 0

х х = х

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

Законы де Моргана

$\bar{x \vee y} = \bar{x}\bar{y}$; $\bar{x y} = \bar{x}\vee\bar{y}$

$x \vee xy =x$; $x(x \vee y) = x$

$x \vee x = x$; $xx=x$; $\bar{\bar{x}} = x$

$x \vee \bar{x}y = x \vee y$; $x \vee \bar{x} = 1$; $x \bar{x} = 0$; $x \vee 1 =1$; $x 0 = 0$

$xy \vee x \bar{y} = x$; $(x \vee y )(x \vee \bar{y}) = x$

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей