Булевий простір

Часто для спрощення запису перемикальної функції замість повного переліку термів використовують двійкові значення наборів, для яких функція набуває одиничних значень. Наприклад,

f(x₁, x₂, x₃) =

означає, що функція набуває одиничних значень в наборах 1, 4, 7. Таку форму запису називають числовою.

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

Булевим простором називається множина набору всіх булевих функцій M. Поставимо у взаємно однозначну відповідність елементам x₁, x₂, …, x_n множини X двійкові змінні, що позначаються тими самими літерами x₁, x₂, …, x_n, але набувають значень із множини {0, 1}, а у відповідність елементам булевого простору M поставимо набори (кортежі) змінних, вважаючи, що змінна x_i, i  {1, …, n} набуває значення 1 в деякому кортежі, якщо елемент x_i множини X належить відповідному простору M, і набуває значень 0 – в іншому випадку.

Таким чином упорядковану сукупність двійкових змінних x₁, x₂, …, x_n можна розглядати як деякий змінний вектор X = (x₁, x₂, …, x_n), що набуває значень з множини M усіх сталих n-компонентних булевих векторів.

Сукупність значень вектора X, на яких булева функція набуває значень 1, позначимо M ¹, на яких 0 – M ⁰. Очевидно, що M ¹ M ⁰ = M.

Властивості функцій

Означення 1. Функція f(x₁, x₂, …, x_n) залежить від аргумента x_i, якщо існують такі значення ₁, …, _n змінних , …, , що f(₁, ₂, …, _{i – 1}, 0, _{i + 1}, …, _n)  f(₁, ₂, …, _{i – 1}, 1, _{i + 1}, …, _n), тоді змінна x_i називається суттєвою, якщо x_i не є суттєвою, то вона називається фіктивною.

Нехай для функції f(x₁, x₂, …, x_n) x_i – фіктивна змінна.

Розглянемо таблицю функцій

x1		xi		xn	f(x1, x2, …, xn)
x1		xi		xn	F1
					
x1		xi		xn	Fn

а за нею побудуємо нову таблицю, викреслюючи рядки вигляду (₁, ₂, …, _{i – 1}, 1, _{i + 1}, …, _n) та стовпці аргументу x_i.

Одержана таблиця визначатиме деяку функцію g(x₁, … x_{i – 1}, x_{i + 1}, …, x­_n). Будемо говорити, що функція g здобута з f вилученням змінної x_i, а функцію f з g – введенням фіктивної змінної x_i.

Означення 2. Функції f₁ та f₂ називаються рівними, якщо функцію f₂ можна одержати з f₁ додаванням і вилученням фіктивних змінних.

Існують два типи функцій, які не мають суттєвих змінних: функція, тотожна 0 (константа 0) та функція, тотожна 1 (константа 1). Їх можна розглядати як функції порожньої множини змінних.

Означення 3. Булева функція f(x₁, …, x_n) називається симетричною відносно змінних x₁, …, x_k, якщо для будь-якої підстановки справджується рівність

f(x₁, … x_k, x_{k + 1}, …, x­_n) = f( ).

Функції константа 1 та константа 0 є симетричними відносно сукупності змінних.