Свойства элементарных функций алгебры логики

Функция сложения по модулю два (по mod 2)

Пусть  Операция  “сложениe по mod p “ определяется следующим образом: а  b = c, где с – остаток от деления на p числа a + b. Например, если р = 7, то . Тогда , .

При сложении по mod 2: р = 2, . Тогда при а = х₁, b = x₂ получим:

х1	х2
0	0	0
0	1	1
1	0	1
1	1	0

.

 

Справедливы коммутативный и ассоциативный законы. Дистрибутивный закон имеет вид:

 

 

Аксиомы:

Связь  с функциями ¯:

 

.

 

Функция Вебба (Пирса)

 

 

Аксиомы: .

Коммутативность: .

Формулы преобразования функций  ¯ через ↓:

 

.

 

Функция импликации

 

Аксиомы: .

Импликация обладает свойством коммутативности в виде:

;

ассоциативность не выполняется.

Формулы преобразования функций  ¯ через →:

 

.

 

Функция Шеффера

 

Аксиомы: .

Свойство коммутативности верно только для двух переменных:

 

 

ассоциативность не выполняется.

Формулы преобразования:

 

Системы функций алгебры логики

Функциональная полнота

 

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

 

 

а также соотношения булевой алгебры, относящиеся только к конъюнкции и константам (с конъюнкцией).

Отрицание и дизъюнкция в этой алгебре выражаются следующим образом:

 

 

Формулы, содержащие знаки  называют полиномами.

Полином вида: , где  есть либо 1, либо переменная, либо конъюнкция различных переменных,  при , называется полиномом Жегалкина.

Теорема.

Любая булева функция может быть представлена полиномом Жегалки- на

 

где k_i – коэффициенты, принимающие значения 0 или 1: .

 

3.2 Класс линейных функций (К _Л)

Булева функция называется линейной, если она представима полиномом первой степени

 

.

 

Количество линейных функций равно , где п – число перемен-ных.

Для п = 2 их 8:

 

3.3 Класс функций, сохраняющих ноль (К ₀)

 

Если булева функция на нулевом наборе переменных равна нулю, то говорят, что функция сохраняет ноль:

3.4 Класс функций, сохраняющих единицу (К ₁)

Если булева функция на единичном наборе переменных равна единице, то говорят, что функция сохраняет единицу:

 

3.5 Класс монотонных функций (К _м)

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

 

3.6 Класс самодвойственных функций (К _с)

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

 

 

Например, конъюнкция и дизъюнкция двойственны друг другу, отрицание двойственно самому себе.

 Функция, совпадающая со своей двойственной, называется самодвойственной.

 Самодвойственная функция на противоположных наборах  и  принимает противоположные значения. Противоположными являются наборы, сумма десятичных эквивалентов которых равна 2ⁿ – 1, где п – количество переменных, от которых зависит функция.

Распределение булевых функций двух переменных по классам

 

Функция	К л	К 0	К 1	К м	К с
f 0	*	*		*
f 1		*	*	*
f 2		*
f 3	*	*	*	*	*
f 4		*
f 5	*	*	*	*	*
f 6	*	*
f 7		*	*	*
f 8	-	-	-	-	-
f 9	*		*
f 10	*				*
f 11			*
f 12	*				*
f 13			*
f 14	-	-	-	-	-
f 15	*		*	*