1.Элементы функциональной полноты в классе двоичных функций.

1.1 Основные двоичные функции и их своства. Булевой функцией f(x1 … xn) называют функцию, аргументы которой принимают значения из множества , и значение функции также из множества {0;1}.

1.Табличные способы задания булевых функций :

x1	…	xn	F(x1…xn)
0	…	0	*
0	…	1	*
…	…	…	…
1	…	1	*

В начале выписываются двоичные наборы из n нулей и единиц. Это удобно делать в двоичной системе счисления – то есть начиная с нуля прибавлять единицу в двоичной системе счисления. На каждом наборе надо задать значение функции.

Пример табличного задания функции:

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

2.Основные булевые функции и их таблицы.

0 – константа ноль ;

1 – константа один ;

x - тождественная ;

- отрицание ;

- конъюнкция (логическое умножение) ;

- дизъюнкция (логическое сложение) ;

+ - модульная сумма ;

~ - эквивалентность (отрицание модульной суммы) ;

- следствие .

x1	x2	0	1	x1		x1x2	x1x2	x1+ x2	x1 ~ x2	x1x2
0	0	0	1	0	1	0	0	0	1	1
0	1	0	1	0	1	0	1	1	0	1
1	0	0	1	1	0	0	1	1	0	0
1	1	0	1	1	0	1	1	0	1	1

3.Свойства булевых функций :

Определения.

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

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

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

;

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

x1	x2	x3	x2 x3	x1(x2x3)	x1x2	(x1x2) 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)	x1x2	(x1x2 )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	x1x2	x2x1
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(x2x3)	x1x2	x1x3	(x1x2 )(x1x3 )
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	x2x3	x1(x2x3)	x1x2	x1x3	(x1x2)(x1x3)
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	x2x3	x1(x2x3)	x1x2	(x1x2)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	x2x3	x1(x2x3)	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)	x1x2	x1x3	(x1x2)+(x1x3)
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

Определение

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