Функии алгебры логики

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

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

Функция задается своей истинностной таблицей (табл. 4).

Таблица 4

		…
		…
		…
…	…	…	…	…

Из этой таблицы видно, что число различных двоичных наборов длины n x₁, x₂,…, x_n конечно и равно 2ⁿ.

Ясно, что тавтологии и тождественно ложные функции алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию. Каждая функция определяется таблицей истинности, состоящей из 2ⁿ строк, т.е. принимает 2ⁿ значений. Общее число наборов из 0 и 1 длины 2ⁿ равно . Это число равно числу различных функций алгебры логики n переменных.

Функция алгебры логики f(x₁,…,x_i-1,x_i,x_i+1,…,x_n) зависит существенным образом от аргумента x_i, если существуют такие значения
a₁,…,a_i-1,a_i,a_i+1,… a_n переменных x₁,…,x_i-1,x_i,x_i+1,…,x_n, что f(a₁,…,a_i-1,0,a_i+1,… a_n) f(a₁,…,a_i-1,1,a_i+1,… a_n). В этом случае переменная x_i называется существенной, в противном случае – несущественной, или фиктивной. Очевидно, что постоянные функции не имеют существенных переменных.

Рассмотрим подробнее функции в случае

1. Число функций Буля в этом случае равно Возможные значения функции одной переменной приведены в таблице (табл. 5).

Таблица 5

=1 (постоянная, не зависит от x, x – фиктивная переменная),

=0 (постоянная, не зависит от x, x – фиктивная переменная)

= x, = , в и x – существенная переменная.

2. Число различных функции двух переменных равно . Перечислим их в таблице истинности (табл. 6).

Таблица 6

Выразим теперь все эти функции через значения аргументов x и y:

Каждой формуле алгебры логики соответствует своя функция. Если формулы А и В равносильны, то соответствующие им функции равны: . Это значит, что при всех значениях переменных значения и совпадают.