вираженні не грає ролі.
. Диз'юнкція, кон'юнкція, сума по модулю 2 мають властивості асоціативності (коли результат обчислення не залежить від порядку виконання операцій між декількома змінними (розстановки дужок), тому дозволено опускати дужки у запису), яку також називають сполучний закон, і дистрибутивності, звану також розподільним законом.
. Закон ДеМоргана
=?
=
4. Закон подвійного заперечення
=х
5. Вираз диз'юнкції через кон'юнкцію і суму по модулю 2
? ?
. Вираз кон'юнкції через імплікацію
. Вираз заперечення через штрих Шеффера, стрілку Пірса, суму по модулю 2 і еквівалентність
8. Вираз кон'юнкції через штрих Шеффера
. Вираз диз'юнкції через стрілку Пірса
10. Закон поглинання
11. Закон склеювання
Для кон'юнкції, диз'юнкції і суми по модулю 2 існує кілька справедливих тотожностей
Полінома Жегалкина ДЛЯ ЛОГІЧНИХ ОПЕРАЦІЙ
Поліном (багаточлен) Жегалкина від n змінних - це функція виду
(1)
де - коефіцієнти, що приймають значення або нуля, або одиниці, або в більш загальному вигляді
(2)
де - елементарна кон'юнкція, тобто поліном Жегалкина є многочлен, що являє собою суму по модулю 2 n елементарних кон'юнкція.
Будь-яку булеву функцію можливо представити у вигляді многочлена Жегалкина, і при тому тільки єдиним чином. Це твердження також називають теоремою Жегалкина.
По суті, операція приведення логічної функції являє собою вираження логічних операцій через кон'юнкцію і суму по модулю 2.
ВЛАСТИВОСТІ АЛГЕБРИ Жегалкина
Безліч булевих функцій, в яких можуть бути задіяні лише операції кон'юнкції і суми по модулю 2 і одиниця (також говорять, що ці булеві функції задані в базисі Жегалкина S={?,?, 1}), називається алгеброю Жегалкина.
Основні властивості алгебри Жегалкина
. Комутативність
. Асоціативність
. Дистрибутивність
. Властивості констант
Твердження: через операції алгебри Жегалкина можна виразити всі інші булеві функції
? X
СПОСОБИ ПОБУДОВИ Полінома Жегалкина
Існує кілька способів побудови поліномів Жегалкина, кожен з яких зручний по-своєму в певних випадках.
ПОБУДОВА Полінома Жегалкина ЗА ДОПОМОГОЮ таблиці істинності (метод невизначених КОЕФІЦІЄНТІВ)
Побудова поліномів Жегалкина за допомогою таблиць істинності або, як ще кажуть, методом невизначених коефіцієнтів - процес кропіткий, що вимагає уваги і певної вправності, а також повного усвідомлення того, що треба робити.
Цей спосіб можна застосовувати і тоді, коли функція задана таблицею істинності, і тоді, коли функція представлена ??логічною формулою.
Приклад 1: побудувати поліном Жегалкина для функції
Складемо таблицю істинності для функції
000100001000010111011000100101101001110111111001 1. Тепер, використовуючи формулу (1), побудуємо поліном Жегалкина для нашої функції в загальному вигляді (для трьох змінних):
. (3)
2. Знайдемо значення коефіцієнтів
Тому що те.
3. Складемо поліном Жегалкина, підставивши отримані значення коефіцієнтів у формулу (3)
Відповідь: поліном Жегалкина, побудований для функції, буде дорівнює
Приклад 2: побудувати многочлен Жегалкина, використовуючи дану таблицю істинності
00010011010101111001101111011110
Рішення:
. Запишемо загальний вигляд полінома Жегалкина (з невизначеними коефіцієнтами), тобто формулу (1) для 3 змінних
. Знайдемо коефіцієнти
Тому що те.
