Булевы функции от 1-ой и 2-х переменных

Представим вначале в табличном виде все булевы функции от 1-ой переменной. Как мы знаем, их всего четыре.

В этой таблице представлены следующие функции:

1. f₁(x₁)= 0 - константа 0;
2. f₂(x₁)= 1 - константа 1;
3. f₃(x₁)= x₁ - тождественная функция;
4. f₄(x₁)= x₁ - отрицание x₁ (используется также обозначение x ₁ , а в языках программирования эта функция часто обозначается как NOTx₁ ).

В следующей таблице представлены все 16 функций от 2-х переменных.

Многие из этих функций часто используются в качестве "элементарных" и имеют собственные обозначения.

1. f₁(x₁,x₂)= 0 - константа 0;
2. f₂(x₁,x₂)= 1 - константа 1;
3. f₃(x₁,x₂)= x₁ - функция, равная 1-му аргументу ;
4. f₄(x₁,x₂)= x₁ - отрицание x₁ ;
5. f₅(x₁,x₂)= x₂ - функция, равная 2-му аргументу ;
6. f₆(x₁,x₂)= x₂ - отрицание x₂ ;
7. f₇(x₁,x₂)= (x₁ x₂) - конъюнкция, читается " x₁ и x₂ " (используются также обозначения (x₁ & x₂) , (x₁x₂) , min(x₁,x₂) и (x₁ AND x₂) );
8. f₈(x₁,x₂)= (x₁ x₂) - дизъюнкция, читается " x₁ или x₂ " (используются также обозначения (x₁ x₂) , (x₁ + x₂) , max(x₁,x₂) и (x₁ OR x₂) );
9. f₉(x₁,x₂)= (x₁ x₂) - импликация, читается "x_1 влечет x_2" или "из x₁ следует x₂ " (используются также обозначения ( x₁ x₂ ), и ( IF x₁ THEN x₂ ));
10. f₁₀(x₁,x₂)= (x₁ + x₂) - сложение по модулю 2, читается " x₁ плюс x₂ " (используется также обозначение (x₁ x₂) );
11. f₁₁(x₁,x₂)= (x₁ ~ x₂) - эквивалентность, читается " x₁ эквивалентно (равносильно) x₂ " (используется также обозначение (x₁ x₂) );
12. f₁₂(x₁,x₂)= (x₁ | x₂) - штрих Шеффера (антиконъюнкция), иногда читается как "не x₁ и x₂ ";
13. f₁₃(x₁,x₂)= (x₁ x₂) - стрелка Пирса (антидизъюнкция), иногда читается как "не x₁ или x₂ ".

В качестве элементарных функций будем также рассматривать 0-местные функции-константы 0 и 1.

Отметим, что функции f₁(x₁,x₂) и f₂(x₁,x₂) фактически не зависят от значений обоих аргументов, функции f₃(x₁,x₂) и f₄(x₁,x₂) не зависят от значений аргумента x₂, а функции f₅(x₁,x₂) и f₆(x₁,x₂) не зависят от значений аргумента x₁.

Определение 3.1. Функция f(x₁,…, x_i,…, x_n) не зависит от аргумента x_i, если для любого набора значений σ₁,…,σ_i-1>, σ_i+1,…, σ_n остальных аргументов f имеет место равенство

Такой аргумент x_i называется фиктивным. Аргументы, не являющиеся фиктивными, называются существенными.

Функции f₁(x₁,…, x_n) и f₂(x₁,…,x_m) называются равными, если функцию f₂ можно получить из функции f₁ путем добавления и удаления фиктивных аргументов.

Например, равными являются одноместная функция f₃(x₁) и двухместная функция f₃(x₁,x₂) , так как вторая получается из первой добавлением фиктивного аргумента x₂ . Мы не будем различать равные функции и, как правило, будем использовать для обозначения равных функций одно и то же имя функции. В частности, это позволяет считать, что во всяком конечном множестве функций все функции зависят от одного и того же множества переменных.