Функции алгебры высказываний

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

Пусть логическая функция зависит от n аргументов. Различных наборов значений истинности и ложности аргументов существует (строки истинностной таблицы). Зададимся вопросом, сколько существует различных логических функций, зависящих от n аргументов, т.е. сколько существует различных столбцов в истинностной таблице, содержащей строк. Так как каждой из строк может быть поставлено в соответствие одно из двух значений 1 или 0, то всего столбцов существует . Итак, число логических функций, зависящих от n аргументов N= , - конечное число. Различных формул алгебры высказываний, включающих в себя n переменных, существует бесчисленное множество. Оно разбивается на конечное число классов равносильных между собой формул.

Сформируем определение логической функции. Пусть М - множество функций f(x₁,... x_n), переменные которых x_i определены на множестве Е₂ (1, 0), для которых f(a₁,... a_n)Î Е₂, если a_iÎ Е₂. Функции из множества М есть функции алгебры логики, или Булевы функции.

Среди переменных логической функции есть существенные переменные и фиктивные. Функция f(x₁,... x_i-1, x_i, x_i+1,... x_n) существенно зависит от переменной x_i, если найдутся два набора

s=(s₁,... s_i-1, 0, s_i+1,... s_n) и

=(s₁,... s_i-1, 1, s_i+1,... s_n)

такие, что f(s)¹ f(). В этом случае переменная x_i является существенной переменной и фиктивной в противном случае.

Если переменная x_i - фиктивная, то функцию f(x₁,... x_i-1, x_i, x_i+1,... x_n) можно свести к равной ей функции g(x₁,... x_i-1, x_i+1,... x_n) от (n-1)^ой переменной. Для этого нужно в таблице функции f вычеркнуть все строки, где x_i=1 (или x_i=0) и столбец, соответствующий переменной x_i.