26. Задание функций алгебры логики.

Булевую функцию n-переменных можно задать таблицей истинности:

х1	х2	х3	f(x1,x2,x3)
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

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

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

Число булевых функций от n переменных быстро возрастает с увеличением n.

27. Существенная и несущественная переменные.

Пусть задана булева функция

f(x₁,x₂,…,x_i-1,x_i,x_i+1,…x_n).

Будем говорить, что функция f существенно зависит от переменной xi, если:

f(x₁,x₂,…,x_i-1,x_i,x_i+1,…x_n) f(x₁,x₂,…,x_i-1,x_i+1,…x_n).

Переменная называется существенной, если при ее отсутствии меняется значение функции.

Будем говорить, что функция f не существенно зависит от переменной xi, если:

f(x₁,x₂,…,x_i-1,x_i,x_i+1,…x_n)=f(x₁,x₂,…,x_i-1,1,x_i+1,…x_n).

В случае если одна из переменных является не существенной, то функция зависит от n-1 переменных и соответственно:

f(x₁,x₂,…,x_i-1,x_i,x_i+1,…x_n)=g(x₁,x₂,…,x_i-1,x_i+1,…x_n).

Не существенная (фиктивная) переменная может быть удалена.

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

Например f(x₁x₂x₃)=g(x₁x₂)

28. Примеры логических функций.

Функции одной переменной:

х	ноль	один	тожд.	обратн.
0	0	1	0	1
1	0	1	1	0

Ф-ция 0 и 1 задает константы, поэтому для них х – несущественная переменная. Тождественная ф-ция возвращает х, а обратная – обратное значение х.

Функции 2-х переменных

Ф-ция	переменная х	0	0	1	1
	переменная х	0	1	0	1
название	обозначение
ноль	0	0	0	0	0
конъюнкция	, , 	0	0	0	1
		0	0	1	0
х		0	0	1	1
		0	1	0	0
у		0	1	0	1
сложение по модулю 2	+, , 	0	1	1	0
дизъюнкция		0	1	1	1
стрелка Пирса		1	0	0	0
эквивалентность	, 	1	0	0	1
не у		1	0	1	0
		1	0	1	1
не х		1	1	0	0
имплекация	, , 	1	1	0	1
штрих Шеффера	|	1	1	1	0
один	1	1	1	1	1