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

Теорема

Пример.

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

Число всех функций, зависящих от переменных , равно .

Действительно, булева функция аргументов определена на наборах, на которых она может принимать «0» или «1» из общего количества . Поэтому в соответствие каждой булевой функции можно поставить -разрядное двоичное число. Но количество различных -разрядных чисел равно , а следовательно и количество различных булевых функций равно .

От двух аргументов существует 16 булевых функций, т.е. ; от трех – 256 (), от четырех – 65536 функций ().

Способы задания булевых функций

Существует четыре способа задания булевой функции:

- вербальный (словесный);

- табличный (с помощью таблицы истинности);

- порядковым номером, который имеет функция;

- аналитический (в виде формулы).

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

Дата добавления: 2014-10-22