Основные определения. Основные определения

Лекции 1-3. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

Основные определения

Булевой (логической) переменной называют переменную, принимающую значение из множества {0,1}. Название «логическая» следует из того, что её значения трактуются чаще всего как «истина» (для 1) и «ложь» (для 0).

Функцией алгебры логики (переключательной или булевой функцией) от n переменных называют однозначное отображение множества всевозможных наборов значений n булевых переменных в множество {0,1}.

Такую функцию можно представить в виде таблицы из n+1столбцов и 2ⁿ строк. Эта таблица называется таблицей истинности.

Наборы значений переменных располагают в лексикографическом порядке (в порядке возрастания),как в примере в табл. 5.1 для n = 3.

Число всевозможных наборов значений переменных составляет N=2ⁿ. Число различных функций, которые могут быть записаны в таблице, равно 2^N.

Второй способ описания функции состоит в том. что перечисляются наборы значений, на которых функция равна 1 (множество Т1), или равна 0 (множество Т0).

Для приведённого примера функцию можно представить как Т1={001,010,100, 111}.

Третий способ описания – представление функций в виде вектора. Так как порядок перечисления наборов входных переменных установлен, то достаточно указать только столбец функции. Для приведенного примера это будет вектор <01101001> .

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

ПримерПример. Пусть функция на наборах значений переменных <00110> и <01110> равна, соответственно, 1 и 0. Эта функция существенно зависит от второй переменной, потому что её значение на этих наборах определяется только значением этой переменной.

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

Среди четырех функций одной переменной, приведенных в табл.5.2, две функции, первая и последняя, являются константами (не зависящими ни от одной переменной). Их обозначают соответственно как 0и 1. Вторая функция повторяет переменную. Третья противоположна ей, называется инверсией и обозначается `xx.

Пусть [n] – число функций, существенно зависимых от n переменных. Тогда [1] = 2, [0] = 2. Для любого n это число можно подсчитать по рекуррентной формуле

[n] = 2^N- [0] - CC_n¹[1] - CC_n²[2] - .... CC_n^n-1[n-1].

Здесь N=2ⁿ, первая компонента – число функций от n переменных, из которого последовательно для i=0,1,..., n-1 вычитаются произведения числа функций, существенно зависимых от i переменных, на число способов, которыми можно выбрать i переменных из n.

Так, для n = 2 [2]=16-2-2×2=10. Для n=3 [3]=256-2-3×2-3×10=218.