Алгебри булевих функцій

Нехай функція задана формулою F₁ а функція ƒ ₂ - формулою F_2. Підстановка F₁ та наприклад, у диз'юнкцію x₁˅ x₂ дає формулу F₁˅ F₂. Якщо взяти формулу Ф1, рівносильну F₁ (тобто Ф₁ також реалізує ) і , рівносильну , то отримаємо формулу Ф₁∨ Ф₂, рівносильну F ₁∨ F ₂.

Отже, диз'юнкцію можна розглядати як двомісну операцію на множині всіх булевих функцій. Ця операція кожній парі функцій f ₁та f ₂, незалежно від вигляду формул, якими ці функції зображені, однозначно ставить у відповідність функцію f₁∨ f₂. Аналогічно й інші булеві функції можна розглядати як операції на множині Р ₂ усіх булевих функцій. Наприклад, заперечення є одномісною операці­єю, кон'юнкція та диз'юнкція - двомісними.

Множину Р₂ булевих функцій разом із уведеною на ній системою операцій називають алгеброю булевих функцій.

Розглянемо дві алгебри. Алгебру (Р ₂; ̅, ∧, ∨), операціями якої є заперечення, кон'юнкція та диз'юнкція, називають алгеброю Буля.

Алгебру (Р ₂; ∧, ⊕), операціями якої є кон'юнкція й додавання за mod2, називають алгеброю Жегалкіна.

Формули алгебри Буля та алгебри Жегалкіна будують із знаків операцій відповідної алгебри, круглих дужок, символів змінних і констант 0 та 1.

Порядок виконання операцій у разі відсутності дужок у булевій алгебрі такий: заперечення, кон'юнкція, диз'юнкція. В алгебрі Жегалкіна спочатку виконують кон'юнкцію, а потім - додавання за mod2. У разі наявності дужок спочатку повинні виконувати опе­рації всередині них. У булевій алгебрі роль дужок у разі заперечення складних виразів відіграє сам символ заперечення.

Приклад 8.5. Замість можна написати , а замість (xy)⊕ (yz) записуютьxy⊕ yz. ▲

Однією з найважливіших задач є виявлення основних еквіваленгностей, які є в алгебрах, що розглядаються. Ці еквівалентності називають законами відповідної алгебри.