Пример 2. Рассмотрим несколько функций двух переменных x1 x2 (x1&x2) f3 f15

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

Покажем, что (х ₁& x ₂) существенно зависит от х ₁. Рассмотрим наборы (0,1) и (1,1), здесь a ₂=1, f (0, a ₂)=0 и не равно f (1, a ₂)=1. Покажем, что х ₂ тоже существенная переменная. Рассмотрим наборы (1,0) и (1,1). Здесь a ₁=1, f (1,0)=0 и не равно f (1,1)=1. Для функции f ₃(x ₁, x ₂) покажем, что х ₂ – фиктивная переменная, т.е. надо показать, что не существует наборов (a ₁,0) и (a ₁,1) таких, что f ₃(a ₁,0)¹ f ₃(a ₁,1). Пусть a ₁=0, т.е. рассмотрим наборы (0,0) и (0,1), f (0,0)= f (0,1)=0. Пусть a ₁=1, но f (1,0)= f (1,1)=1.

Для функции f ₁₅ и x ₁ и x ₂ являются фиктивными переменными. x ₁ – фиктивная переменная, если не существует наборов (0, a ₂) и (1, a ₂), таких, что f (0, a ₂)¹ f (1, a ₂). Если a ₂=0, то f (0,0)= f (1,0)=1. Пусть a ₂=1, тогда f (0,1)= f (1,1)=1.

Пусть х_i является фиктивной переменной для функции f (x ₁,..., x_i,..., x_n). Тогда ее можно удалить из таблицы истинности, вычеркнув все строки вида: (a ₁,... a_{i– 1}, 1, a_{i +1},... a_n) или, наоборот, все строки вида: (a ₁,..., a_{i– 1}, 0, a_{i +1},... a_n) и столбец для переменной х_i. При этом получим таблицу для некоторой функции g (x ₁,..., x_{i –1}, x_{i +1},... x_n). Будем говорить, что функция g (x ₁,... x_{i –1}, x_{i +1},... x_n) получена из функции f (x ₁,..., x _i,... x_n) путем удаления фиктивной переменной х_i или f получена из g путем введения фиктивной переменной х_i.

Определение 4. Функции f ₁ и f ₂ называются равными, если f ₂ можно получить из f ₁ путем добавления или удаления фиктивной переменной.

Пример 3.

Вычеркнули строки типа (a,1), т.е. (0,1) и (1,1) и столбец для х ₂.

Получили f ₃(x ₁ x ₂) = g (x ₁) = x ₁.