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

Канонические формы логических формул.

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

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

Определение 2.1. Логической (булевой) функцией называют функцию , аргументы которой (независимые переменные) и сама функция (зависимая переменная) принимают значение 0 или 1.
Логические функции могут быть заданы логичным способом или аналитически – в виде соответствующих формул.

Общее количество различных булевых функций от n аргументов равно.

Для n = 1 существует четыре различных булевых функции.

x

, , , .

Для n = 2 существует 16 различных булевых функций.

x

y

– константа «истина»;

– дизъюнкция;

– обратная импликация;

– импликация;

– отрицание конъюнкции;

– функция равна первому аргументу;

– эквиваленция;

– отрицание первого аргумента;

– отрицание эквивалента;

– отрицание второго аргумента;

– функция равна второму аргументу;

– отрицание дизъюнкции;

– отрицание обратной импликации;

– отрицание импликации;

– конъюнкция;

– константа «ложь».

С увеличением числа аргументов количество логических функций возрастает.

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

Дата добавления: 2014-01-07; Просмотров: 511; Нарушение авторских прав?; Мы поможем в написании вашей работы!