🗊Презентация Булевы функции

Тема 4. Булевы функции

4.1 Способы задания булевой функции Пусть х1, х2, ... , хn – некоторые булевы переменные, т. е. переменные, принимающие значение из множества {0, 1}. Упорядоченную совокупность булевых переменных (х1, х2, ... , хn) можно рассматривать как n‑компонентный булев вектор х. Число компонент вектора определяет его длину, или размерность.

При фиксации значений всех переменных получается набор значений переменных (х1, х2, ..., хn), задаваемый булевым вектором длины n, состоящим из констант 0 и 1. Очевидно, 2n – число всех таких векторов. Они образуют булево пространство. Булевой функцией называется функция f : {0, 1}n  {0, 1}. Областью определения булевой функции является булево пространство М = {0, 1}n, областью значений – множество {0, 1}. При фиксации значений всех переменных получается набор значений переменных (х1, х2, ..., хn), задаваемый булевым вектором длины n, состоящим из констант 0 и 1. Очевидно, 2n – число всех таких векторов. Они образуют булево пространство. Булевой функцией называется функция f : {0, 1}n  {0, 1}. Областью определения булевой функции является булево пространство М = {0, 1}n, областью значений – множество {0, 1}.

Задание булевой функции f на булевом пространстве М делит его на две части: Mf1 – область, где функция принимает значение 1, и Mf0 – область, где функция принимает значение 0. Множество Mf1 называется характеристическим множеством функции f. Задание булевой функции f на булевом пространстве М делит его на две части: Mf1 – область, где функция принимает значение 1, и Mf0 – область, где функция принимает значение 0. Множество Mf1 называется характеристическим множеством функции f. Универсальным способом задания для любой дискретной функции является табличный способ. Таблица, представляющая функцию и называемая таблицей истинности, имеет два столбца. В левом столбце перечислены все наборы значений аргументов, в правом столбце – соответствующие им значения функции.

Пример задания булевой функции от трех аргументов

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

Компактность представления характеристического множества Mf1 можно повысить, используя троичные векторы, компоненты которых могут принимать в качестве своих значений кроме символов 0 и 1 также символ «–». В этом случае значения булевой функции будут задаваться не на отдельных элементах, а на интервалах пространства переменных х1, х2, ..., хn. Чтобы определить понятие интервала булева пространства, введем отношение  на множестве булевых векторов. Компактность представления характеристического множества Mf1 можно повысить, используя троичные векторы, компоненты которых могут принимать в качестве своих значений кроме символов 0 и 1 также символ «–». В этом случае значения булевой функции будут задаваться не на отдельных элементах, а на интервалах пространства переменных х1, х2, ..., хn. Чтобы определить понятие интервала булева пространства, введем отношение  на множестве булевых векторов.

Булевы векторы а = (а1, а2, … , аn) и b = (b1, b2, … , bn) находятся в отношении  (а  b) и говорят, что а меньше b, если аi  bi  для любого i = 1, 2, … , n, в противном случае они несравнимы. При этом считается, что 0  1. Интервалом булева пространства называется множество векторов, среди которых есть минимальный и максимальный векторы, а также все векторы, меньшие максимального и большие минимального. Интервал представляется троичным вектором, который задает множество всех булевых векторов, получаемых заменой символа «–» на 1 или 0. Булевы векторы а = (а1, а2, … , аn) и b = (b1, b2, … , bn) находятся в отношении  (а  b) и говорят, что а меньше b, если аi  bi  для любого i = 1, 2, … , n, в противном случае они несравнимы. При этом считается, что 0  1. Интервалом булева пространства называется множество векторов, среди которых есть минимальный и максимальный векторы, а также все векторы, меньшие максимального и большие минимального. Интервал представляется троичным вектором, который задает множество всех булевых векторов, получаемых заменой символа «–» на 1 или 0.

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

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

Векторное задание булевой функции представляет собой булев вектор, компоненты которого соответствуют наборам значений аргументов. Эти наборы упорядочиваются обычно согласно порядку чисел, двоичные коды которых они представляют. Рассмотренная выше булева функция f(x1, x2, x3) представляется вектором (0 1 1 1 0 1 0 1), показывающим, что функция принимает значение 0 на наборах (0 0 0), (1 0 0), (1 1 0) и значение 1 на наборах (0 0 1), (0 1 0), (0 1 1), (1 0 1), (1 1 1) Векторное задание булевой функции представляет собой булев вектор, компоненты которого соответствуют наборам значений аргументов. Эти наборы упорядочиваются обычно согласно порядку чисел, двоичные коды которых они представляют. Рассмотренная выше булева функция f(x1, x2, x3) представляется вектором (0 1 1 1 0 1 0 1), показывающим, что функция принимает значение 0 на наборах (0 0 0), (1 0 0), (1 1 0) и значение 1 на наборах (0 0 1), (0 1 0), (0 1 1), (1 0 1), (1 1 1)

Если значения булевой функции определены для всех 2n наборов значений вектора x, она называется полностью определенной, в противном случае – не полностью определенной, или частичной. Задание не полностью определенной булевой функции f разбивает булево пространство на три множества: кроме Mf1 и Mf0 в нем присутствует множество Mf –, где значения функции f не определены. Для задания частичной булевой функции необходимо задать не менее двух множеств. Обычно это Mf1 и Mf0 . Если значения булевой функции определены для всех 2n наборов значений вектора x, она называется полностью определенной, в противном случае – не полностью определенной, или частичной. Задание не полностью определенной булевой функции f разбивает булево пространство на три множества: кроме Mf1 и Mf0 в нем присутствует множество Mf –, где значения функции f не определены. Для задания частичной булевой функции необходимо задать не менее двух множеств. Обычно это Mf1 и Mf0 .

4.2 Элементарные булевы функции и алгебраические формы Рассматривая векторную форму задания булевой функции, легко определить число булевых функций от n переменных – это число всех 2n-компонентных булевых векторов, т. е. . Однако это число учитывает также функции и от меньшего числа аргументов. Любую функцию от n аргументов можно считать функцией от большего числа аргументов. Для этого вводится понятие существенной зависимости и несущественной зависимости.

Функция f(х1, х2, ... , хn) существенно зависит от аргумента хi, если Функция f(х1, х2, ... , хn) существенно зависит от аргумента хi, если f(х1, х2, ... , хi -1, 0, хi + 1, … , хn)      f(х1, х2, ... , хi – 1, 1, хi + 1, … , хn). Переменная хi в этом случае называется существенным аргументом. В противном случае она является несущественным или фиктивным аргументом.

Элементарными булевыми функциями являются функции от одной и двух переменных. Число функций от одной переменной равно 221= 4. Эти функции представлены в таблице. Элементарными булевыми функциями являются функции от одной и двух переменных. Число функций от одной переменной равно 221= 4. Эти функции представлены в таблице. Две из них, f0 и f3, являются константами 0 и 1, переменная x для них является несущественным аргументом

Функция f1 также является тривиальной, любое ее значение совпадает со значением аргумента: f1(x) = x. Нетривиальной функцией является функция f2(x) =x, называемая отрицанием, или инверсией. Функция f1 также является тривиальной, любое ее значение совпадает со значением аргумента: f1(x) = x. Нетривиальной функцией является функция f2(x) =x, называемая отрицанием, или инверсией.

В таблице приведены все булевы функции fi (х1, х2) от двух аргументов. В левом столбце показаны их выражения в терминах нескольких функций, принятых за основные. В таблице приведены все булевы функции fi (х1, х2) от двух аргументов. В левом столбце показаны их выражения в терминах нескольких функций, принятых за основные.

Продолжение таблицы