Закони алгебри Жегалкіна.

Закони асоціативності

Закони комутативності

Дистрибутивний закон для кон’юнкції відносно додавання за mod2

Співвідношення для констант

.

Закон ідемпотентності для кон’юнкції

.

Закон зведення подібних членів у разі додавання за тоді

Правильність цих еквівалентностей доводять за допомогою таблиць.

Наведені еквівалентності залишаються правильними й у разі підстановки замість змінних довільних булевих функцій (тобто фор­мул, які ці функції задають). Важливо лише виконувати таке правило підстановки формули замість змінної: під час підстановки формули F замість змінної х усі входження змінної х у дану еквівалентність повинні бути одночасно замінені формулою F. Наприклад, з отримаємо .

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

Приклад 8.6. Доведемо, що

а) ;

б) .

Двічі використовуючи закони дистрибутивності, одержимо:

а) ;

б) .▲

Приклад 8.7. Доведемо, що . Використову­ючи закони де Моргана, подвійного заперечення та асоціативності, можемо записати

. ▲

Наведемо еквівалентності, які дозволяють перетворити будь-яку формулу булевої алгебри у рівносильну їй формулу алгебри Жегалкіна та навпаки:

Зазначимо, що за допомогою законів алгебр Буля та Жегалкіна можна спрощувати різні формули в цих алгебрах.

Приклад 8.8. Перетворимо у рівносильну формулу алгебри Жегалкіна. Отриману формулу спростимо.

.▲

Виразимо х → у тах~у через операції алгебри Буля. Оскільки х~у=(х→ у)(у→ х), то достатньо виразитих→ у. Порівняємо таблицю для х→ у з таблицею для x ∨ y. Скориставшись тим, що в обох таблицях є єдиний набір, для якого значення функції дорівнює нулю, отримаємо еквівалентність .

Розглянемо тепер ще одне важливе поняття. Функцію f ^*(х ₁,..., x_n) називають двоїстою до функції f (х ₁,..., x_n), якщо . Візьмемо заперечення над обома части­нами рівності і підставимо замість . Отримаємо , тобто функція f двоїста до f*: (f)*⁼f. Отже, відношення двоїстості між функціями симетричне. Пару двоїстих функцій складають, наприклад, кон'юнкція та диз'юнкція. Таблицю для двоїстої функції у разі вибраного порядку наборів отримують із таблиці для функції інвертуванням (тобто заміною 0 на 1 і 1 на 0) стовпчика функції і перевертанням цього стовпчика.

Розглянемо тепер ще одне важливе поняття. Функцію f ^*(х ₁,..., x_n) називають двоїстою до функції f (х ₁,..., x_n), якщо . Візьмемо заперечення над обома части­нами рівності і підставимо замість . Отримаємо , тобто функція f двоїста до f*: (f)*⁼f. Отже, відношення двоїстості між функціями симетричне. Пару двоїстих функцій складають, наприклад, кон'юнкція та диз'юнкція. Таблицю для двоїстої функції у разі вибраного порядку наборів отримуєть із таблиці для функції інвертуванням (тобто заміною 0 на 1 і 1 на 0) стовпчика функції і перевертанням цього стовпчика.

Із означення двоїстості зрозуміло, що для довільної функції дво­їсту функцію визначають однозначно. Зокрема, може з'ясуватись, що функція є двоїстою до самої себе. У цьому випадку її називають самодвоїстою. Наприклад, заперечення та функціяx⊕ y⊕ z- самодвоїсті функції.

Нехай функція задана формулою F. Який вигляд має формула F*, яка виражає двоїсту функцію? Відповідь на це запитання дає наступ­на теорема.

Теорема 8 .2. Якщо