Основоположником алгебры логики является английский математик Джордж Буль (1815 - 1864). Он впервые высказал идеи логического истолкования теории множеств.

Рассмотрим 2-элементное множество В, элементы которого 0 и 1. Однако они не являются числами в обычном смысле. Наиболее распространенная интерпретация двоичных переменных - это логическая. Например, в языках программирования вводится специальный тип переменной - логическая переменная, значения которой обозначаются TRUE и FALSE.

Таким образом, элементы множества В={0,1} будем рассматривать как формальные символы, а не числа.

Алгебра, образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй логики или булевой алгеброй.

Элементарные булевы функции

Определение 2.1. Булевой функцией f(x1, x2, ..., xn) называется функция, которая принимает два значения 0 или 1 в зависимости от переменных хj, каждая из которых может также принимать только два значения 0 или 1.

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

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

Представление булевой функции

x1 x2 x3 f(х1,х2,х3)

Для формирования столбца значений переменных удобен лексико­графический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления, например, 100 = 011+ 1.

Булева функция п переменных может иметь 2n наборов. Поскольку функция принимает только два значения, общее число булевых функций и перемен­ных равно 22n. Таким образом, функция одной переменой может иметь четыре значения: у = х; у = -x (отрицание х); у = 0 (константа 0); у = 1 (константа 1).

Из них выделим функцию "отрицание x" (обозначается -x). Эта функция представлена в таблице

Функция отрицания

x -x

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

Булевы функции двух переменных

 

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

Формулы логики булевых функций

Формула логики булевых функций определяется индуктивно следующим образом:

Пример 2.1.

Часть формулы, которая сама является формулой, называется подформулой.

Пример 2.2.

Функция/есть суперпозиция функций f1,f2, ... ,fn если f получается с помощью подстановок этих формул друг в друга и переименованием переменных.

Пример 2.3.

f1 = х1&х2 (конъюнкция); f2 -x (отрицание).

Возможны две суперпозиции:

1)f=f1(f2) = (—х1)&(—х2) - конъюнкция отрицаний;

2)f=f2(f1) = -(x1&х2) - отрицание конъюнкции.