Скачать

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

1.Основные понятия булевой алгебры

Технические вопросы, связанные с составлением логических схем ЭВМ, можно решить с помощью математического аппарата, объектом исследования которого являются функции, принимающие, так же как и их аргументы, только два значения - “0” и “1”.

Таким аппаратом является математическая логика (алгебра логики, булева алгебра).

Логика - это наука о законах и формах мышления.

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

Основное понятие алгебры логики - высказывание. Высказывание - это некоторое предложение, о котором можно утверждать, что оно истинно или ложно.

Любое высказывание можно обозначить символом х и считать, что х=1, если высказывание истинно, а х=0 - если высказывание ложно. Истинному высказыванию соответствует утверждение -“Да”, ложному высказыванию - утверждение - “Нет”.

Логическая (булева) переменная - такая величина х, которая может принимать только два значения х={0,1}.

Высказывание абсолютно истинно, если соответствующая ей логическая величина принимает значение х=1 при любых условиях.

Высказывание абсолютно ложно, если соответствующая ей логическая величина принимает значение х=0 при любых условиях.

Функция f, зависящая от n переменных x1,x2,...,xn, называется булевой, или переключательной, если функция f и любой из ее аргументов  принимают значения только из множества {0,1}. Аргументы булевой функции также называются булевыми.

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

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

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

Под двоичным набором понимается совокупность значений аргументов x1,x2,...,xn булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В табл. 1 и 2 перечислены все двоичные наборы соответственно длины 3 и 4.

Таблица 1      Таблица 3