Бинарная операция ассоциативна, если тождественно выполняется: ;

бинарная операция коммутативна, если тождественно выполняется: ;

бинарная операция дистрибутивна по отношению к бинарной операции , если тождественно выполняется:

;

Утверждение 1. , конъюнкция ассоциативна.

x1	x2	x3	x2 x3	x1 (x2 x3)	x1 x2	(x1 x2) x3
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	1	0	0	0
1	0	0	0	0	0	0
1	0	1	0	0	0	0
1	1	0	0	0	1	0
1	1	1	1	1	1	1

Утверждение 2. ,

дизъюнкция ассоциативна.

x1	x2	x3	x2 x3	x1 (x2 x3)	x1 x2	(x1 x2 ) x3
0	0	0	0	0	0	0
0	0	1	1	1	0	1
0	1	0	1	1	1	1
0	1	1	1	1	1	1
1	0	0	0	1	1	1
1	0	1	1	1	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

Утверждение 3. , конъюнкция

коммутативна; , дизъюнкция также

коммутативна;

x1	x2	x1 x2	x2 x1
0	0	0	0
0	1	0	0
1	0	0	0
1	1	1	1

Предложение 1. Результат выполнения ассоциативной операции не зависит от расположения скобок в скобочном выражении.

Например: Если ассоциативная операция, тогда

.

Доказательство предлагается в качестве домашнего упражнения.

Примечание: использовать индукцию по числу скобок в выражении.

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

Например:

Тогда в силу независимости значения выражений конъюнкций от расположения скобок корректно определение как значение логического произведения при каком-либо порядке расположения скобок. Точно также для дизъюнкции .

Предложение 2. Конъюнкция равна 0, т. и т.т., когда хотя бы один из множителей равен 0.

Дизъюнкция равна 1, т. и т.т., когда хотя бы одно из слагаемых равно 1.

Доказательство предлагается в качестве домашнего упражнения.

Утверждение 4.

, конъюнкция дистрибутивна по отношению к дизъюнкции.

x1	x2	x3	x2 x3	x1 (x2 x3)	x1 x2	x1 x3	(x1 x2 ) (x1 x3 )
0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	0	0	0	0	0
1	0	1	1	1	0	1	1
1	1	0	1	1	1	0	1
1	1	1	1	1	1	1	1

Утверждение 5.

, дизъюнкция дистрибутивна по отношению к конъюнкции.

x1	x2	x3	x2 x3	x1 (x2 x3)	x1 x2	x1 x3	(x1 x2) (x1 x3)
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

Утверждение 6. , следствие не ассоциативная операция.

x1	x2	x3	x2 x3	x1 (x2 x3)	x1 x2	(x1 x2) x3
0	0	0	1	1	1	0
0	0	1	1	1	1	1
0	1	0	0	0	1	1
0	1	1	1	1	1	1
1	0	0	1	1	0	1
1	0	1	1	1	0	0
1	1	0	0	0	1	1
1	1	1	1	1	1	1

Утверждение 7.

x1	x2	x3	x2 x3	x1 (x2 x3)	x1+x2	x1+x3	(x1+x2) (x1+x3)
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	0	0
1	1	0	0	1	0	1	0
1	1	1	1	0	0	0	0

Утверждение 8.

,

конъюнкция дистрибутивна по отношению к сумме по модулю два.

x1	x2	x3	x2+x3	x1 (x2+x3)	x1 x2	x1 x3	(x1 x2)+(x1 x3)
0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	0	0	0	0	0
1	0	0	0	0	0	0	0
1	0	1	1	1	0	1	1
1	1	0	1	1	1	0	1
1	1	1	0	0	1	1	0

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

Определение

Переменная x булевой функции f(x…) называется существенной, если существует набор значений остальных переменных функции, что изменение значения переменной при данном наборе остальных переменных изменяет значение функции.

Пример: x₁ и x₂  существенные переменные (x_{1 по 8 –му и по 5-му наборам;} x₂

_{по 6 и 8 наборам).}

x₃  не существенная переменная

x1	x2	x3	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Определение

Две функции равны, если они одинаковы после отбрасывания несущественных переменных.