Правила

1. Якщо в логічному добутку один із співмножників дорівнює нулю, то логічний добуток дорівнює 0.

2. Якщо в логічному добутку, що містить не менше двох співмножників, є співмножник, який дорівнює 1, то цей співмножник можна вилучити.

3. Якщо в логічній сумі, що містить не менше двох доданків, є доданок, який дорівнює нулю, то цей доданок можна вилучити.

4. Якщо в логічній сумі один із доданків дорівнює 1, то ця сума дорівнює 1.

Принцип двоїстості

Означення. Функція [f(x₁, x₂, …, x_n)]*, що дорівнює ( , , …, ) називається двоїстою функцією до функції f(x₁, x₂, …, x_n).

Для двоїстих функцій справедливі наступні твердження:

1. функція 0 двоїста до 1;

2. функція 1 двоїста до 0;

3. функція x двоїста до ;

4. функція двоїста до x;

5. функція x₁x₂ двоїста до x₁ + x₂;

6. функція x₁ + x_­2­ двоїста до x₁x₂.

З двох останніх тверджень випливає, що кон’юнкція та диз’юнкція – взаємно двоїсті функції.

x1	x2	x3	f(x1, x2, x3)	[f(x1, x2, x3)]*	[f]* = ( , , )
0	0	0	1	1	( , , ) = (1, 1, 1) = = 1
0	0	1	0	1	( , , ) = (1, 1, 0) = = 1
0	1	0	1	1	( , , ) = (1, 0, 1) = = 1
0	1	1	1	0	( , , ) = (1, 0, 0) = = 0
1	0	0	1	0	( , , ) = (0, 1, 1) = = 0
1	0	1	0	0	( , , ) = (0, 1, 0) = = 0
1	1	0	0	1	( , , ) = (0, 0, 1) = = 1
1	1	1	0	0	( , , ) = (0, 0, 0) = = 0

Типи булевих функцій

Існує п’ять типів булевих функцій

1. Позначимо T₀ клас усіх булевих функцій f(x₁, x₂, …, x_n), що зберігають константу 0, тобто f(0, 0, …, 0) = 0.

2. Позначимо T₁ – клас булевих функцій, що зберігають константу 1, тобто f(1, 1, …, 1) = 1.

3. S – клас самодвоїстих функцій f  P таких, що f* = f, тобто справедлива тотожність.

( , , …, ) = f(x₁, x₂, …, x_n)

4. M – клас монотонних функцій. Нехай  = (₁, ₂, …, _n) і  = (₁, ₂, …, _n) – будь-які набори.

Означення 1. Для будь-яких наборів  = (₁, …, _n) та  = (₁, …, _n) виконується відношення передування, якщо ₁  ₁, ₂  ₂, …, _n  _n.

Приклад: 1)  = (0, 1, 0, 1) й  = (1, 1, 0, 1) – відношення передування;

2)  = (0, 1),  = (1, 0) не знаходяться у відношенні передування.

Означення 2. Функція f(x₁, …, x_n) називається монотонною, якщо для будь-яких двох наборів  і , що знаходяться у відношенні передування (тобто значення наборів не зменшується), справджується нерівність f()  f().

5. L – клас лінійних функцій.

Булева функція двох змінних називається лінійною, якщо вона може бути подана поліномами першого степеня:

f(x₀, x₁) = k₀  k₁x₀  k₂x₁ = k₀ + k₁x₀ + k₂x₁ (k₀, k₁, k₂ = 0 або 1).

Означення 3. Система функцій (f₁, f₂, …, f_s) з P (f_i  P) називається функціонально повною, якщо будь-яка булева функція може бути записана у вигляді формули через функції цієї системи.

Означення 4. Система функцій (f₁, f₂, …, f_s)  P, суперпозицією яких може бути подана будь-яка функція з деякої множини булевих функцій, називається функціонально повною.

Означення 5. Система функцій називається мінімально повним базисом, якщо вилучення з неї будь-якої функції перетворює цю систему на неповну.

Теорема 1. Нехай задано дві системи функцій

(1) A = {f₁, …, f_m},

(2) B = {g₁, …, g_s},

відносно яких відомо, що система (1) повна і кожна її функція виражається у вигляді формули через функції системи (2). Тоді система (2) також є повною.

Доведення. Нехай h – довільна система функцій h  P. З урахуванням повноти системи (1) h можна виразити так: h = C(f₁, …, f_m). За умовою f_i = C_i(g₁, …, g_s), i = 

 h = C(C₁(g₁, …, g_s), …, C_m(g₁, …, g_s)) = C₂(g₁, …, g_s) 

 h = C₂(g₁, …, g_s)  B належить до повних систем за означенням.

Теорема 2. Будь-яка перемикальна функція f  P може бути зображена за допомогою полінома Жегалкіна вигляду

k₀  k₁x  k₂x₂  k₃x₁x₂  …  k_nx₁x₂…x_n,

де k₁, …, k_n – коефіцієнти, що набувають значення 0 або 1.

Кількість членів наборів ( , …, ) = 2ⁿ. Оскільки f дорівнює 0 або 1, то загальна кількість членів (поліномів) дорівнює .

Приклад. Виразити x₁ + x₂ у вигляді композиції полінома Жегалкіна.

Нехай x₁ + x₂ = ax₁x₂  bx₁  cx₂  d. Тоді:

x₁ = x₂ = 0  x₁ + x₂ = 0 = d d = 0;

x₁ = 0, x₂ = 1  x₁ + x₂ = 1 = c  c = 1;

x₁ = 1, x₂ = 0  x₁ + x₂ = 1 = b  b = 1;

x₁ = 1, x₂ = 1  x₁ + x₂ = 1 = a  b  c  a = 1.

Отже, x₁ + x₂ = x₁x₂  x₁  x₂.

Означення 6. Нехай A – деяка підмножина функцій з P (A  P). Замиканням А називається множина всіх булевих функцій, зображених у вигляді формул через функції множини А. Замикання множини А позначатимемо [A].

Означення 7. Клас (множина) A називається функціонально замкненим, якщо [A] = A.